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

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

                                                        *
     В результате получим искомое оптимальное решение X max =(6,2) с
значением целевой функции L*max =28 .
      Пример 2. Решить графически следующую задачу:
                            2x 1 +4 x 2 → max
                           3x 1 +2x 2 ≥11 (1)
                           −2x 1 +x 2 ≤2 (2)
                             x1 −3x 2 ≤0 (3)
                               x 1 ≥0, x 2 ≥0 .
Решение. Первый этап - построение допустимой области - выполняется так-
же как и в предыдущей задаче. В результате получаем неограниченную мно-
гогранную область.
                1
                                   Z*max= +
            2
                      3                     d=22
       X2


                           .   X*min


                                  X1
                                       Рис. 2.
                     d=0


 На втором этапе решения - параллельном перемещении линии уровня в на-
правлении возрастания целевой функции устанавливаем, что такое переме-
щение можно производить неограниченно. Следовательно, целевая функция
неограниченна сверху, т.е. L max =∞, а сама задача линейного программиро-
вания неразрешима. Заметим, что если при тех же исходных данных требова-
лось бы целевую функцию минимизировать, то получили бы оптимальное
решение в точке x min
                  *
                      =(3,1) с L*min =10 .

Пример 3. Решить задачу
                            −x 1 +x 2 → max
                           −x 1 +x 2 ≤3 (1)
                            x 1 −2x 2 ≤3 (2)
                              x 1 ≥0, x 2 ≥0 .
        Решение.    Допустимая область в данной задаче имеет вид



                                       7