Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании

Найдите решение задачи симплексным методом, проиллюстрировав его графически. Составьте двойственную задачу и, на основании теорем двойственности, сделайте вывод о ее решении. F=2x1-7x2→min -3x1+2x2≤6;-2x1+5x2≤26;4x1+x2≤36;2x1-3x2≤4; x1≥0; x2≥0.

Решим задачу симплекс-методом. Для этого приведем задачу к каноническому виду
F=2x1-7x2→min
-3x1+2x2+x3=6;-2x1+5x2+x4=26;4x1+x2+x5=36;2x1-3x2+x6=4; xi≥0; i=1, 6.
Внесём данные задачи в симплекс-таблицу.
План Базис Сб
bi
2 -7 0 0 0 0 di
x1
x2
x3
x4
x5
x6
I
x3
0 6 -3 2
1 0 0 0 62=3 ←
x4
0 26 -2 5 0 1 0 0 265=5,2
x5
0 36 4 1 0 0 1 0 361=36
x6
0 4 2 -3 0 0 0 1 ∞
F
= 0 -2 7 0 0 0 0
↑
Базисное решение получаем в виде X=(x1, x2, x3, x4, x5, x6) при свободных переменных равных нулю, а базисных – равных соответствующим свободным членам bi.
Таким образом, базисным решением на первом шаге будет X1=0, 0, 6, 26, 36, 4 (точка X1=0; 0 рисунке), на котором целевая функция будет F равна 0, то есть F1=0.
Получаем новую симплекс-таблицу, соответствующую II плану:
План Базис Сб
bi
2 -7 0 0 0 0 di
x1
x2
x3
x4
x5
x6
II
x2
-7 3 -32
1 12
0 0 0 ∞
x4
0 11 112
0 -52
1 0 0 11:112=2 ←
x5
0 33 112
0 -12
0 1 0 33:112=6
x6
0 13 -52
0 32
0 0 1 ∞
F
= -21 172
0 -72
0 0 0
↑
Базисным решением на втором шаге будет X2=0, 3, 0, 11, 33, 13 (точка X2=0; 3 на рисунке), на котором целевая функция будет F равна -21, то есть F2=-21.
После вычислений, получаем новую симплексную-таблицу.
План Базис Сб
bi
2 -7 0 0 0 0 di
x1
x2
x3
x4
x5
x6
III
x2
-7 6 0 1 -211
311
0 0 ∞
x1
2 2 1 0 -511
211
0 0 ∞
x5
0 22 0 0 2
-1
1 0 222=11 ←
x6
0 18 0 0 411
511
0 1 18:411=49,5
F
= -38 0 0 411
-1711
0 0
↑
Базисным решением на третьем шаге будет X3=2, 6, 0, 0, 22, 18 (точка X3=2; 6 на рисунке), на котором целевая функция будет F равна -38, то есть F3=-38.
После вычислений, получаем четвертую симплексную-таблицу.
План Базис Сб
bi
2 -7 0 0 0 0
x1
x2
x3
x4
x5
x6
IV
x2
-7 8 0 1 0 211
111
0
x1
2 7 1 0 0 -122
522
0
x3
0 11 0 0 1 -12
12
0
x6
0 14 0 0 0 711
-211
1
F
= -42 0 0 0 -1511
-211
0
Базисным решением на четвертом шаге будет X4=7, 8, 11, 0, 0, 14 (точка X4=7; 8 на рисунке), на котором целевая функция будет F равна -42, то есть F4=-42.
Для базисного решения X4 выполнен критерий оптимальности, так как у целевой функции нет положительных элементов