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

     Свободные переменные: x1 , x 2 , x3 , x 4 .                         Выбор включаемой в базис переменной: наибольший
                                                                   положительный коэффициент с 2 = 6 M − 5 при переменной
Шаг 1. Составление первой симплекс-таблицы                         x2 .
     В задаче с искусственным базисом первая симплекс-                   Проверка критерия допустимости: среди оценочных
таблица соответствует первому искусственному базисному             отношений (последний столбец таблицы) встречаются ко-
решению.                                                           нечные положительные, следовательно, возможен выбор
                                                                   исключаемой из базиса переменной.
                                             Симплекс-таблица 1          Выбор исключаемой переменной: среди оценочных
                                               Реше                отношений минимальным является отношение, соответст-
БП   F    x1    x2    x3 x 4    x5 x6    r1 r2 ние Отноше-
                                                     ние           вующее переменной r1 , которая и будет исключена из бази-
F    1   5M-3 6M-5 -M -M        0    0   0   0     22M             са на этом шаге.
r1   0    2      4    -1   0    0    0   1   0     12     12:4=3
                                                                         Ведущим элементом при пересчете будет элемент,
                                                                   стоящий на пересечении строки, соответствующей исклю-
r2   0    3      2     0   -1   0    0   0   1     10     10:2=5   чаемой переменной r1 (ведущей строки), и столбца, соот-
x5   0    0      1     0   0    1    0   0   0      6     6:1=6    ветствующего включаемой переменной x 2 (ведущего
x6   0    1      0     0   0    0    1   0   0      5    5:0 → ∞   столбца). В таблице ведущий элемент обведен рамкой.

Комментарий к симплекс-таблице 1.                                  Пересчет таблицы в матричной записи.
     Решение (искусственное базисное) в 8-мерном про-                   Элементы ведущей строки делятся на ведущий эле-
странстве X =(0,0,0,0,6,5,12,10).                                  мент:
     Решение в двумерном (по количеству исходных пере-
менных в условии задачи) пространстве X =(0,0). Данная             ⎛                                                 ⎞
точка находится за пределами многоугольника решений.               ⎜ 1 5M − 3 6 M − 5 − M − M 0 0 0          0 22 M ⎟
                                                                   ⎜                                                 ⎟
     Значение целевой функции F (0,0)=22 M – «штраф-               ⎜0      1            1          1
ное», так как точка не принадлежит многоугольнику реше-                             1 −      0 0 0           0     3⎟
                                                                   ⎜       2            4          4                 ⎟
ний.                                                               ⎜                                                 ⎟
     Проверка критерия оптимальности: задача на мини-              ⎜0       3       2    0  −1 0 0 0         1    10 ⎟
мизацию, в строке целевой функции имеются положитель-              ⎜                                                 ⎟
                                                                   ⎜0       0       1    0   0 1 0 0         0     6⎟
ные коэффициенты при свободных переменных x1 и x 2 ,               ⎜                                                 ⎟
следовательно, оптимальное решение не достигнуто. Необ-            ⎜                                                 ⎟
ходимо выбрать среди свободных включаемую в базис пе-              ⎜0       1       0    0   0 0 1 0         0     5⎟
                                                                   ⎝                                                 ⎠
ременную.


6                                                                                                                         7