Численные методы. Корнюшин П.Н. - 73 стр.

                                              73




       После этого проведем какую-нибудь определенную линию уровня Z=const целевой
функции, например, прямую c1x1+c2x2=l и покажем стрелками, куда ее надо двигать, чтобы
целевая функция увеличивала свое значение. Очевидно, что искомый оптимум найдется, когда
прямая (l), двигаясь к границе многоугольника ограничений, покинет этот многоугольник – это
произойдет в некоторой вершине многоугольника ограничений. Определив координаты x1B и x2B
вершины B, найдем оптимальный план: x1опт=x1В, x2опт=x2В. Вычислив затем значение целевой
функции в вершине B, найдем искомый оптимум:
                                        Zmax=c1x1B+c2x2B.
       Если бы при тех же ограничениях была поставлена задача на минимум, то ясно, что линию
уровня целевой функции – прямую (l) – надо двигать в противоположную сторону, и мы получим
минимум в некоторой вершине C многоугольника ограничений.
       Это свойство является общим: оптимальное значение целевой функции, если оно
существует, всегда достигается в некоторой вершине многоугольника ограничений.
       Если область, задаваемая ограничениями, бесконечна (см. рис.6.7), то один из оптимумов
(максимум или минимум) может стать бесконечным, но другой по-прежнему достигается в
некоторой вершине. Может, однако, случиться что линия уровня целевой функции – прямая (l) –
окажется параллельной какому-то звену многоугольника ограничений (рис.6.13). В этом случае
(при отыскании одного из оптимумов – максимума или минимума) прямая (l), покидая
многоугольник ограничений, ляжет на параллельное ей звено, и координаты любой точки этого
звена дадут оптимальный план, так что оптимальных планов будет бесконечное множество. Но
для любого из них целевая функция имеет одно и то же значение (т.к. точки лежат на одной и той
же линии уровня), поэтому оптимум, конечно, будет один. В этом случае говорят, что имеются
альтернативные оптимальные планы.


                                       4.6.2.3. Задачи

       Рассмотрим несколько задач для иллюстрации графического метода. Первая из них –
численный пример, а остальные имеют экономическое содержание.
       Задача 1. Найти максимум функции Z=x1–5x2 при ограничениях
                                        − x1 + 2 x2 ≤ 5;
                                          x1 + x2 ≤ 7;
                                        2 x1 + x2 ≤ 11;
                                         x1 + 2 x2 ≥ 7;
                                        x1 ≥ 0; x 2 ≥ 0.
       Решение. Построим прямые