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

                                                                            Z − 12 y1 − 10 y 2 + 6 y 3 + 5 y 4 = 0
     Решение двойственной задачи симплекс-
                   методом                                             ⎧2 y1 + 3 y 2        − y 4 + y5         = 3
                                                                       ⎨
                                                                       ⎩4 y1   2 y 2 − y3                 + y6 = 5
     Пример 3. Решить двойственную задачу, построенную                               y j ≥ 0, j = 1, K,6.
в примере 2, симплекс-методом.
                                                                  Расширенная матрица канонической формы двойст-
            Z = 12 y1 + 10 y 2 − 6 y 3 − 5 y 4 → max         венной задачи:
               ⎧2 y1 + 3 y 2            − y4 ≤ 3
               ⎨                                                            ⎛ 1 − 12 − 10 6 5 0 0 0 ⎞
               ⎩4 y1     2 y 2 − y3          ≤ 5                            ⎜                          ⎟
                     y j ≥ 0, j = 1, K ,4.                                  ⎜0     2    3 0 − 1 1 0 3⎟
                                                                            ⎜0     4    2 − 1 0 0 1 5 ⎟⎠
                                                                            ⎝
Приведение условия к каноническому виду
     Так как система ограничений состоит из неравенств,          Ранг расширенной матрицы rang = 3 , следовательно,
для приведения условия к каноническому виду нужно вве-       количество базисных переменных равно трем.
сти в каждое неравенство балансовые переменные y 4 , y 5 :       Базисные переменные: Z , y 5 , y 6 .
                                                                 Свободные переменные: y1 , y 2 , y 3 , y 4 .
         ⎧2 y1 + 3 y 2           − y 4 + y5      = 3
         ⎨                                                   Шаг 1. Составление первой симплекс-таблицы
         ⎩4 y1   2 y 2 − y3                 + y6 = 5
                       y j ≥ 0, j = 1,K,6.                        В задаче с естественным базисом первая симплекс-
                                                             таблица соответствует первому допустимому базисному
                                                             решению.
     Матрица системы ограничений
                                                                                                             Симплекс-таблица 1
                 ⎛ 2 3 0 − 1 1 0 3⎞
                 ⎜⎜                ⎟⎟                        БП    Z   y1       y2     y3     y4     y5    y 6 Реше- Отноше-
                  ⎝ 4 2 − 1 0 0 1 5⎠                                                                            ние     ние
                                                              Z    1   -12     -10     6      5      0     0     0
содержит в себе единичную матрицу, следовательно, балан-                                                                   3
                                                              y5   0    2       3      0      -1     1     0     3    3:2=
совые переменные образуют естественный базис.                                                                              2
     Условие задачи в каноническом виде:                                                                                   5
                                                              y6   0    4       2      -1     0      0     1     5    5:4=
                                                                                                                           4

14                                                                                                                          15