Линейное программирование. Филькин Г.В. - 12 стр.

      Введённые х4, х5, х6 называются дополнительными переменными и в
данной задаче показывают величину неиспользуемого соответствующего ре-
сурса: х4 – для первого, х5 – для второго, х6 – для третьего.
      Решение задачи симплексным методом проводим в симплексных таб-
лицах. Они заполняется по следующему правилу: Число столбцов таблицы на
три больше, чем число всех переменных задачи, в нашем случае 6+3=9. В
первом столбце стоят векторы, входящие в базис ( единичные вектора, в на-
шем это вектора, являющиеся коэффициентами при х4, х5, х6). Во втором
стодбце стоят коэффициенты в целевой функции для соответствующих пере-
менных, в нашем случае при переменных х4, х5, х6 . В третьем столбце распо-
лагается столбец свободных членов, затем в последующих 6 столбцах распо-
лагаются коэффициенты при переменных, входящих в левую часть ограни-
чений и в целевую функцию. В последней строке находятся числа, вычис-
ляемые по формуле Zj-Cj =Cб*Аj-Cj , здесь Cб*Аj - скалярное произведение
векторов, стоящих во втором столбце и столбце j.

                    0        9       10       16      0        0        0
Базис     Сб
                   А0       А1       А2       А3      А4       А5       А6
    А4     0       360      18       15       12      1        0        0
  ←
           0       192       6       4        8        0        1       0
  А5
    А6     0       180       5       3        3        0        0       1
 Zj-Cj              0       -9      -10     -16 ↑      0        0       0

     Таблица 1. Первоначальное опорное решение.

      Получили первое опорное решение задачи, оно извлекается из таблицы
следующим образом: все xj у которых вектор с коэффициентом Сб не входит
в базис равны 0, а те, у которых вектор входит в базис равны соответствую-
щему значению из столбца А0.
      А1, А2, А3– не входят в базис , следовательно соответствующие х1,х2,х3
равны 0, х3 ,х4 ,х равны соответственно 360,192,180 . Следовательно первое
опорное решение - ( 0, 0, 0, 360, 192, 180), Z=0 (первая, вторая, третья про-
дукция не производится суммарная стоимость равна 0).
      Это опорное решение не является оптимальным т.к. не выполняется
критерий оптимальности. Критерий оптимальности в симплексном методе
является следующим: в строке Zj - Cj не должно быть отрицательных членов,
а они у нас есть, следовательно, решение не оптимальное. Выбираем то от-
рицательное число, модуль которого наибольший, соответствующий вектор
войдёт в новый базис, это будет вектор А3. Выясним, какой при этом вектор
выйдет из базиса. Для этого надо рассмотреть так называемые симплексные
отношения. Они рассматриваются только для тех элементов вектора, входя-
щего в базис, которые являются положительными. Симплексные отношения
равны отношению элемента стоящего в столбце А0 к соответствующему эле-
менту вводимого в базис вектора Имеем
                                     11