Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 6 стр.

Линейное программирование



                       Z*max=3

                         .
                      X2max

               X2
            X1max
            1
                  .          d=1




                         d=0

                                   2       X1


                             рис 3.
Из рисунка видно, что допустимое множество неограниченно. Линии уровня
целевой функции параллельны прямой −x1 +x 2 =3 , соответствующей пер-
вому ограничению. Перемещая линии уровня в направлении возрастания
целевой функции, получаем, что линия уровня с максимально возможным
значением целевой функции совпадает с прямой −x1 +x 2 =3 . Таким обра-
зом, целевая функция достигает своего максимального значения L*max =3 во
всех точках луча, выходящего из точки x 1max =(0,3). Задача имеет бесчис-
ленное множество решений. Для того чтобы выписать решение в общем ви-
де, возьмем на луче еще одну точку x max    2
                                              =(1,4 ). Уравнение луча записывает-
ся следующим образом:
                          *
                        x max =(1 −λ )x 1max +λx max
                                                 2
                                                     ,λ ∈[0, ∞) .
Таким образом, любое решение данной задачи записывается в виде
  *
x max =(λ,3 +λ ),λ ∈[0,∞).
       Пример 4. Решить графически задачу
                                 3x 1 +3x 2 → min
                                   x1 +x 2 ≥2 (1)
                                −2 x1 +x 2 ≥2 (2)
                                    x1 −x 2 ≥0 (3)
       Решение. Допустимое множество данной задачи пусто. Это видно из
следующего рисунка




                                       8