Решить каноническую задачу ЛП f=3x1+2x4→max

Итак, имеем следующую задачу линейного программирования:
f=3x1+2x4→max,
2x1+x2+4x4=2
3x1+x3+2x4=6
3x1+4x4+x5=4
x1,…,x5≥0.
Система ограничений имеет исходное опорное решение:
Xисх=0,2,6,0,4.
Из системы ограничений удалим базисные переменные x2,x3,x5. Получим следующую задачу:
f=3x1+2x4→max,
2x1+4x4≤2
3x1+2x4≤6
3x1+4x4≤4
x4,x5≥0.
Решаем задачу графически.
Находим оптимальное решение: x1=1, x4=0, fmax=3*1=3.
Найдем значение остальных переменных в оптимальном решении.
Имеем:
2∙1+x2+4∙0=2
3∙1+x3+2∙0=6
3∙1+4∙0+x5=4
Откуда x2=0, x3=3, x5=1.
3 . Решим задачу симплекс-методом.
Так как функция цели уже выражена через свободные переменные, то сразу заполняем симплекс-таблицу. Выбираем в качестве разрешающего столбец x1, который имеет отрицательную оценку -3. Тогда разрешающей будет первая строка. Выполняем одну итерацию метода Жордана-Гаусса.
cj
xj
0 3 0 0 2 2 Ai0/aip
Ai0 X1 X2 X3 X4 X5
0 X2 2 -6667502 1 0 4 0 1
0 X3 6 3 0 1 2 0 2
0 X5 4 3 0 0 4 1 4/3
f 0 -3 0 0 -2 0
Получаем:
cj
xj
0 3 0 0 2 2 Ai0/aip
Ai0 X1 X2 X3 X4 X5
3 X1 1 1 1/2 0 2 0
0 X3 3 0 -3/2 1 -4 0
0 X5 1 0 -3/2 0 -2 1
f 3 0 3/2 0 4 0
Получено оптимальное решение (нет отрицательных оценок):
Xopt=(1,0,3,0,1), fmax=3.
Сформулируем теперь двойственную задачу:
F=2y1+6y2+4y3→min
2y1+3y2+3y3≥3
y1≥0
y2≥0
4y1+2y2+4y3≥2
yj≥0, j=1,2,3.
Из симплекс-таблицы с оптимальным решением находим оптимальное решение двойственной задачи:
Yopt=(3/2,0,0), Fmin=3.
4