Математическое программирование (линейное программирование). Киселева Э.В - 37 стр.

    Решение последней задачи можно найти, используя геомет-          Пример 6.4. Решить симплекс-методом ЗЛП:
рическую интерпретацию решения ЗЛП, приведенную на рисун-                              Ζ = 2 x1 + х2        + х4 → max ,
ке.
                                                                                           ⎧ x1 + x 2 + x3 + х 4 = 2,
                                                                                           ⎪⎪
                                                                                            ⎨ x1 − x 2 − х3     = 0,
                                                                                            ⎪
                                                                                            ⎪⎩ x1 + x 2 + 2 х3   = 1,

                                                                                              x j ≥ 0, ( j = 1,4).
                                                                     Решение. Особенностью данной задачи является то, что сис-
                                                                 тема ограничений не приведена к базисному виду, нет разграни-
                                                                 чения переменных на базисные и свободные (есть только одна
                                                                 базисная переменная х4). Поэтому прежде всего с помощью пре-
                                                                 образований Жордана–Гаусса приведем систему к базисному ви-
                                                                 ду. Для этого коэффициенты системы ограничений и целевой
                                                                 функции Z1= –Z занесем в таблицу:
                                                                                            Переменные                  Свободный
          Геометрическая интерпретация симплекс-метода                   БП
                                                                                  x1         x2        x3       x4         член
    Исходный опорный план                                                 x4      1          1         1        1          2
                       Χ ( 1 ) = (0, 0, 5, 9,7)Т
                                                                                  1         –1         –1       0          0
соответствует точке О (0,0) ОДР.
    После одного шага симплекс-метода (одной итерации) был                        1          1         2        0          1
получен новый опорный план
                                   7 3 11
                                                                          Z1     –2         –1         0       –1          0
                     Χ ( 2 ) = (0 , , ,         , 0 )Т ,
                                   2 2 2                              За разрешающий столбец выберем любой столбец, содержа-
                                      7                          щий хотя бы один положительный элемент, например первый.
которому соответствует точка А ( 0, ).                                Выбор разрешающей строки осуществим по тому же прави-
                                      2
    На рисунке переход от одного опорного плана (вершины) к      лу, что при переходе от одного опорного решения к другому. Это
другому опорному плану происходит по ребру ОА.                   правило гарантирует, что свободные члены новой таблицы оста-
    После второй итерации получен план                           нутся неотрицательными.
                                                                                          ⎧2   0 1⎫ 0
                          Χ * = (3, 2 , 0, 1, 0)Т ,                   Имеем           min ⎨ ,    ,   ⎬= ,
                                                                                          ⎩1   1 1⎭ 1
который является оптимальным. Он соответствует на чертеже
точке В, т.е. осуществлен переход от точки А к точке В по реб-   т.е. за разрешающую строку примем вторую, а за разрешающий
ру АВ.                                                           элемент а21=1. Выполнив шаг преобразований Жордана–Гаусса,
                                                                 придем к таблице:
                                 75                                                                76