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

                         Переменные                          Свободный                          Ζ 1 min = Ζ 1 ( Χ ( 3 ) ) = − 9 .
     БП
             x1     x2         x3         x4           x5       член         Итак, решением исходной задачи является:
     x3     1/ 2     0          1         0        –1/2         3/2                     Χ * = ( 3 , 2 , 0 , 1,0 )Т , а Z max = –Z1min=9.
                                                                             Дадим геометрическую интерпретацию процесса нахожде-
     x4     3/2      0          0         1        –1/2        11/2      ния решения. Для этого прежде всего перейдем от канонической
                                                                         формы модели:
     x5     1/2      1          0         0            1/2      7/2                    Ζ = 2 x1 + x 2 − x 3 + х 4 − х 5 → max
     Z1     –1/2     0          0         0            3/2     15/2      при ограничениях:
                                                                                                 ⎧ x1 + x 2 + x 3 = 5,
     Значение же функции цели Z1 уменьшилось от значения                                         ⎪⎪
Z1 = 3 до значения Z1 = –15/2. (Напомним, что значение функции                                    ⎨ 2 x1 + x 2 + x 4 = 9,
цели из таблицы берется с противоположным знаком.)                                                ⎪
     Очевидно, что на следующем шаге необходимо в базис вве-                                      ⎩⎪ x1 + 2 x 2 + x 5 = 7,
сти переменную х1, соответствующую отрицательной компоненте                                      x j ≥ 0,    j = 1, 2, K ,5
r1 = –1/2. И первый столбец в последней таблице становится раз-
решающим. Для выбора разрешающей строки найдем:                          к стандартной форме модели данной задачи. Это нетрудно сде-
                                                                         лать, так как система ограничений задачи уже приведена к еди-
                         ⎧ 3 2 11 2 7 2 ⎫                                ничному базису.
                     min ⎨    ,    ,    ⎬ = 3.                                Выразим из системы ограничений базисные переменные че-
                         ⎩1 2 3 2 1 2 ⎭                                  рез свободные:
    Минимальное из отношений соответствует первой строке.                                         x3 = 5 − x1 − x 2 ≥ 0 ,
Сделав один шаг симплексных преобразований с разрешающим
                                                                                                 x 4 = 9 − 2 x1 − x 2 ≥ 0 ,
элементом а11=1/2, получим таблицу:
                         Переменные                          Свободный                           x5 = 7 − x1 − 2 x 2 ≥ 0 ,
    БП
             x1     x2         x3        x4            x5       член     и, подставив вместо х3, х4, х5 их выражения в функцию цели Z,
                                                                         получим:
     x3      1      0          2          0            –1        3                            Ζ = − 3 + 2 x1 + 3 х 2 → max .
     x4      0      0         –3          1            –2        1
                                                                              Стандартная форма модели примет вид
                                                                                              Ζ = − 3 + 2 x1 + 3 х 2 → max
     x5      0      1         –1          0            1         2       при ограничениях:
                                                                                                     ⎧ x1 + x 2 ≤ 5,
     Z1      0      0          1          0            1         9                                   ⎪⎪
Из таблицы следует, что полученный опорный план:                                                      ⎨ 2 x1 + x 2 ≤ 9,
                                                                                                      ⎪
                         Χ ( 3 ) = ( 3, 2, 0,1, 0 )Т                                                  ⎪⎩ x1 + 2 x 2 ≤ 7 ,
является единственным оптимальным планом задачи, так как
                                                                                                      x1, х 2 ≥ 0.
r =(1; 1)>0. При этом значение функции уменьшилось:
                                    73                                                                        74