Сформулировать двойственную задачу к задаче 1 и решить ее

Решение:

Прямая задача: F = 4×2 + x4 max.

x1 + x2 + x3 = 11.

• 2x1 — 3×2 — x4 = 1
• -x1 + x2 + x5 = - 3, x1, x2, x3, x4, x5 0

Расширенная матрица A прямой задачи.

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

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

Z (Y) = 11y1 + y2 — 3y3 > min.

y1+2y2-y3?0.

y1−3y2+y3?4.

y1?0.

— y2?1.

y3?0, y1 y2 y3 — любое число.

Hайдём её решение по теоремам двойственности.

Поскольку в оптимальном плане прямой задачи x1* > 0, x4* > 0, x5* > 0, то I, IV и V ограничения в двойственной задаче будут равенствами.

Получим систему.

y1 + 2y2 — y3 = 0.

— y2 = 1.

y3 = 0 ,.

решая которую, находим оптимальный план двойственной задачи :

y1 = 2, y2 = -1, y3 = 0 или Y* = (2; -1; 0).

maxZ (Y) = Z (Y*) = 11*2+(-1)+(-3)*0 = 21.

Ответ: y1* = 2, y2* = - 1, y3* = 0; Zmin = 21.

Решить задачу линейного программирования двумя методами:

графически в трехмерном пространстве и симплекс-методом.

F = 3x + 4y + 2z max.

при условиях 2x + 5y + 4z 20, 4x + 3y + 5z 30, x, y, z 0.

Решение:

ОДР — многогранник АВСОKD. Находим координаты угловых точек (его вершин). Обозначим плоскости :

: 4x + 3y + 5z = 30 ,.

: 2x + 5y + 4z = 20 .

a) A = OY; подставим в уравнение: х =0, z = 0 y = 4; A (0; 4; 0).

• б) В = ХOY; подставим в уравнение и: z = 0
• 4x + 3y = 30 ,
• 2x + 5y = 20 x = 45/7; y = 10/7 B (45/7; 10/7; 0)
• в) С = OХ ;

подставим в уравнение: у =0, z = 0 x = 7,5; C (7,5; 0; 0).

г) D = ХOZ ;

подставим в уравнение и: y = 0.

• 4x + 5z = 30 ,
• 2x + 4z = 20

x = 10/3; z = 10/3 D (10/3; 0; 10/3).

д) K = OZ ;

подставим в уравнение: х =0, y = 0 z = 5; K (0; 0; 5).

Найдём значения ЦФ в найденных угловых точках, подставляя в ЦФ их координаты.

f (O) = 0, f (A) = 16, f (B) = 25, f© = 22.5, f (D) = 50/3, f (K) = 10.

Cравнивая значения, получим максимум в т. В :

fmax = 25, x* = 45/7, y* = 10/7, z* = 0.

Применим симплекс-метод.

Задача ЛП :

F = 3x + 4y + 2z max.

• 2x + 5y + 4z 20,
• 4x + 3y + 5z 30, x, y, z 0.

Перейдём к канонической форме.

• 2x + 5y + 4z + 1×4 + 0×5 = 20
• 4x + 3y + 5z + 0×4 + 1×5 = 30

Первый опорный план: X0 = (0,0,0,20,30).

План не оптимален, т.к. в индексной строке есть отрицательные коэффициенты.

Определение новой базисной переменной. За ведущий выберем столбец y (наибольший по модулю).

Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

min (20: 5, 30: 3) = 4.

Значит 1-я строка ведущая. Разрешающий элемент равен (5).

Выводим из базиса x4, вводим y.

Получаем новую симплекс-таблицу:

Опорный план неоптимален, повторяем шаг симплекс-метода.

Получаем новую симплекс-таблицу.

В индексной строке нет отрицательных. Получили оптимальный план задачи :

x* = 45/7, y* = 10/7, z* = 0; (или Х* = (45/7; 10/7; 0)) ;

maxF (X) = F (X*) =3*63/7 + 4*13/7 + 2*0 = 25.

Решения совпадают.