Линейное программирование в примерах и задачах. Методические указания. Корытов И.В - 9 стр.

Комментарий к симплекс-таблице 1.                                               ⎛                                                     ⎞
     Решение (допустимое базисное) в 6-мерном простран-                         ⎜ 1 − 12 − 10   6  5 0 0                             0⎟
                                                                                ⎜                                                     ⎟
стве Y =(0,0,0,0,3,5).                                                          ⎜0     2    3   0 −1 1 0                             3⎟
     Решение в 4-мерном (по количеству исходных пере-                           ⎜                                                     ⎟
менных в условии двойственной задачи) пространстве                              ⎜           1   1      1                             5⎟
Y =(0,0,0,0). Данная точка является угловой в многогранни-                      ⎜0     1      −    0 0                                ⎟
                                                                                ⎝           2   4      4                             4⎠
ке решений.
     Значение целевой функции в начальной точке                   Далее выполняются элементарные преобразования над
Z (0,0,0,0)=0.                                               строками матрицы,
     Проверка критерия оптимальности: задача на макси-
мизацию, в строке целевой функции имеются отрицатель-        ⎛                                  1        1                                    1             5       ⎞
ные коэффициенты при свободных переменных y1 и y 2 ,         ⎜1 + 0 ⋅12 −12 +1⋅12         −10 + ⋅12 6 − ⋅12 5 + 0 ⋅12        0 + 0 ⋅12     0 + ⋅12       0 + ⋅12 ⎟
                                                             ⎜                                  2        4                                    4             4       ⎟
                                                             ⎜ 0 + 0 ⋅ (−2) 2 +1⋅ ( −2)      1           1                                    1             5
следовательно, оптимальное решение не достигнуто. Необ-                                   3 + ⋅ (−2) 0 − ⋅ (−2) −1+ 0 ⋅ (−2) 1+ 0 ⋅ (−2)   0 + ⋅ ( −2)   3 + ⋅ (−2) ⎟
                                                             ⎜                               2           4                                    4             4       ⎟
ходимо выбрать среди свободных включаемую в базис пе-        ⎜                            1            1                                   1             5          ⎟
                                                             ⎜0             1                        −          0            0                                      ⎟
ременную.                                                    ⎝                            2            4                                   4             4          ⎠
     Выбор включаемой в базис переменной: наибольший
по модулю отрицательный коэффициент b1 = −12 при пе-         в результате которых на месте ведущего столбца окажется
ременной y1 .                                                столбец единичной матрицы:
     Проверка критерия допустимости: все оценочные от-
ношения конечные положительные, следовательно, возмо-                             ⎛                       ⎞
                                                                                  ⎜1 0 −4   3 5 0    3 15 ⎟
жен выбор исключаемой из базиса переменной.                                       ⎜                       ⎟
     Выбор исключаемой переменной: среди оценочных                                ⎜0 0      1        1 1⎟
                                                                                        2     −1 1 −
отношений минимальным является отношение, соответст-                              ⎜         2        2 2⎟
вующее переменной y 6 , которая и будет исключена из ба-                          ⎜     1   1        1 5⎟
                                                                                  ⎜0 1    −    0 0        ⎟
зиса на этом шаге.                                                                ⎝     2   4        4 4⎠
     Ведущим элементом при пересчете будет элемент,
стоящий на пересечении ведущей строки, соответствующей               Базисные переменные: Z , y1 , y 5 .
исключаемой переменной y 6 , и ведущего столбца, соответ-            Свободные переменные: y 2 , y 3 , y 4 , y 6 .
ствующего включаемой переменной y1 .
                                                             Шаг 2. Составление следующей симплекс-таблицы
Пересчет таблицы в матричной записи.                             Новая таблица соответствует допустимому базисному
     Элементы ведущей строки делятся на ведущий эле-         решению.
мент:

16                                                                                                                                                          17