Тема 3. Геометрическая интерпретация и графический метод решения задач линейного программирования

3.1. Геометрическая интерпретация задачи лп

Геометрическая интерпретация дает возможность наглядно представить структуру задачи, выявить ее особенности и открывает путь к исследованию более сложных свойств. На практике графически можно решить только задачи линейного программирования с двумя переменными.

Напомним, что в общем случае задача линейного программирования с двумя переменными может быть записана в виде

(3)

Еще раз отметим, что задача может состоять как в максимизации, так и в минимизации целевой функции. В дальнейшем будем рассматривать задачу максимизации, так как все утверждения легко переносятся на случай минимизации целевой функции с учетом того, что .

Каждое из ограничений задает на плоскости некоторую полуплоскость, которая, как известно, является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (3) — выпуклое множество (как пересечение выпуклых множеств). В практически важных случаях область допустимых решений чаще всего представляет собой либо выпуклый многоугольник, либо выпуклую многоугольную область.

Рассмотрим геометрическую интерпретацию целевой функции. Выбирая произвольные значения целевой функции , такие, что получаем семейство параллельных прямых, называемых линиями уровня целевой функции. Задача состоит в нахождении максимального значения целевой функции для точек , образующих область допустимых решений, т.е. в нахождении предельного положения линии уровня целевой функции, соответствующего ее максимальному значению. Вектор градиента целевой функции перпендикулярен к прямым, образующим линии уровня целевой функции и указывает направление наискорейшего возрастания целевой функции.

Из геометрической интерпретации элементов задачи линейного программирования вытекает следующий порядок ее графического решения. Графический метод решения основан на теореме об оптимальных экстремальных точках, которая говорит о том, что если в задаче линейного программирования существует оптимальное решение, то существует и оптимальная экстремальная (угловая) точка. Под экстремальной точкой здесь понимается угловая точка (вершина) множества допустимых решений задачи ЛП.

1. С учетом системы ограничений на плоскости построить множество (пространство) допустимых решений, т.е. точек, удовлетворяющих всем ограничениям модели;

2. Выбрать произвольное значение (например ) и построить соответствующую линию уровня целевой функции .

3. Построить вектор градиента целевой функции, т.е. вектор , указывающий направление наискорейшего возрастания целевой функции;

4. В задаче на максимум перемещать линию уровня целевой функции параллельно в направлении вектора градиента до тех пор, пока она имеет общие точки с пространством допустимых решений. В задаче на минимум линию уровня перемещаем в направлении, противоположном вектору .

5. Крайняя (угловая) точка, лежащая на пересечении линии уровня и пространства допустимых решений и будет оптимальным решением.

6. Определить координаты крайней (угловой) точки, которые и образуют оптимальный план . Вычислить оптимально значение целевой функции в найденной точке, соответствующей оптимальному решению.

При решении задачи линейного программирования возможны следующие случаи:

1. Оптимальный план единственный: линия уровня и область допустимых решений в предельном положении имеют единственную общую точку;

2. Оптимальных планов бесконечно много: в предельном положении линия уровня проходит через сторону области допустимых решений;

3. Область допустимых решений состоит из одной точки, в которой целевая функция достигает одновременно максимального и минимального значений;

4. Задача не имеет решения: целевая функция не ограничена, линия уровня, сколько бы ее ни перемещали, не имеет предельного положения;

5. Область допустимых решений — пустое множество (т.е. система ограничений задачи несовместна), задача не имеет решения.