Решить задачу линейного программирования
Z=CX→max
AX=B
X≥0
используя алгоритм двойственного симплексного метода:
C=-3,-2,-4,-3, 2,
B=-16,-10,-11,
A=0-310101-110 021-501.
Решение
Перепишем условие задачи в следующем виде:
Z=-3x1-2x2-4x3-3x4+2x5→max,
-3x2+x3+2x5=-16,
x2+x4-5x5=-10,
x1-11x2+x5=-11,
xi≥0, i=1,5.
Поскольку в системе ограничений A есть единичная матрица, то в качестве базисных переменных можно принять x1, x3, x4. Выразим базисные через остальные:
x3=3x2-2x5-16,
x4=-x2+5x5-10,
x1=11x2-x5-11.
Тогда целевая функция:
Z=-311x2-x5-11-2x2-43x2-2x5-16-
-3-x2+5x5-10+2x5→max,
Z=-44x2-2x5+127→max.
Первый опорный план: X=-11,0,-16,10,0
. Составим симплексную таблицу:
Базис B
x1
x2
x3
x4
x5
x3
–16 0 –3 1 0 2
x4
–10 0 1 0 1 –5
x1
–11 1 –11 0 0 1
0 0 44 0 0 2
Наибольшее по модулю значение соответствует базисной переменной x3, которую необходимо вывести из базиса. Минимальное значение соответствует второму столбцу, т.е. переменную x2 необходимо ввести в базис. Обнулим все элементы столбца x2, кроме ведущего элемента (на пересечении строки x3 и столбца x2):
Базис B
x1
x2
x3
x4
x5
x2
163
0 1 -13
0 -23
x4
-463
0 0 13
1 -133
x1
1433
1 0 -113
0 -193
-7043
0 0 443
0 943
Среди базисных значений есть отрицательные, поэтому выбранный ранее план не является оптимальным