Решение задачи линейного программирования графически и симплекс-методом

 

Данное решение является оптимальным, так как все коэффициенты в строке целевой функции положительные.

ω1=224/37=6,054,

X1=132/37=3,5676,

ω2=346/37=9,3514,

Х2=28/37=0,7568,

Z=-292/37=-7,8919,

ω3=0,

ω4=0.

 

Вывод:

Получили максимальное значение целевой функции Z(X)=-7,8919 и точку максимума целевой функции Z (132/37; 28/37).

Таким образом, наилучшим вариантом продажи продукции молокозавода является продажа творога в количестве 3,5676 единиц и продажа масла в количестве 0,7568 единиц. Доход от продажи творога и масла составит 7,8919 единицы.

 

 

 

 

Двойственная задача

Количество переменных в двойственной задаче равно количеству неравенств в исходной.

Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

Все неравенства должны иметь знак ≤, так как задача решается на максимум:

-x1+2x2≤4,

-5x1-2x2≤-10,

4x1-3x2≤12,

7x1+4x2≤28,

x1, x2 ≥0.

 

Расширенная матрица A:

 

-1	2
-5	-2
4	-3
7	4

 

 

Транспонированная матрица AT:

-1	-5	4	7
2	-2	-3	4

 

 

 

 

 

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Неравенства, соединенные стрелочками (↔), называются сопряженными.

-1y1-5y2+4y3+7y4≥2

2y1-2y2-3y3+4y4≥1

y1,2,3,4 ≥ 0

F’= 4y1-10y2+12y3+28y4 → min

y1≥0,

y2≥0,

y3≥0,

y4≥0.

Решение, соответствующее двойственной задаче:

ω1=0, ω2=0, ω3=1/37, ω4=10/37.

Исходная задача I		Двойственная задача II
x1 ≥ 0	↔	- y1 - 5y2 + 4y3 + 7y4≥2
x2 ≥ 0	↔	2y1 - 2y2 - 3y3 + 4y4≥1
2x1 + x2 → max	↔	4y1 - 10y2 + 12y3 + 28y4 → min
- x1 + 2x2≤4	↔	y1 ≥ 0
- 5x1 - 2x2≤-10	↔	y2 ≥ 0
4x1 - 3x2≤12	↔	y3 ≥ 0
7x1 + 4x2≤28	↔	y4 ≥ 0

 

 

 

 

Список использованной литературы

1. Бодров В.И., Лазарева Т.Я., Мартемьянов Ю.Ф., «Математические методы принятия решений» Учебное пособие. Тамбов, 2004. 124 с.
2. Большакова И.В., Кураленко М.В. «Линейное программирование», 2004, 148 с.
3. Ляшенко И.Н., Карагодова Е.А. Линейное и нелинейное программирование. «Вища школа», 1975. - 369 с.