Задачи линейной оптимизации

Геометрическая интерпретация

Задана математическая модель:

, (2.19)

(2.20)

, . (2.21)

Каждое из неравенств системы ограничений (2.20) и (2.21) является полупространством с граничными гиперплоскостями

, (),

, (.

Пересечение полупространств, заданных системой ограничений, если она совместна, будет выпуклым многогранником, который образует область допустимых решений (ОДР) системы ограничений.

Любая внутренняя и граничная точка ОДР является решением задачи. Приравняем функцию (2.19) к нулю, тогда уравнение

представляет собой гиперплоскость, проходящую через начало координат и перпендикулярную вектору-градиенту. Направление вектора-градиента показывает направление возрастания функции. Поэтому, чтобы найти максимум функции, нужно передвигать гиперплоскость в направлении вектора как можно дальше от начала координат, но чтобы она имела с ОДР хотя бы одну общую точку. Чтобы найти минимум функции, нужно определить ближайшую точку в ОДР от начала координат.

Для двумерного пространства на рис. 3.1 показано, что в угловой точке А максимальное значение функции, а в точке В - минимальное.

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

Рис. 2.2. Область допустимых решений задачи с множеством решений

Рис. 2.2 отражает случай, когда прямая функции параллельна отрезку АВ, принадлежащему ОДР. Максимум функции 2 достигается в точке А и в точке В, следовательно, и в любой точке отрезка АВ, так как эти точки могут быть выражены в виде линейной комбинации угловых точек А и В.

Рис. 2.3. Множество, неограниченное сверху

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

На рис. 2.4 представлен случай несовместной системы ограничений.

Рис. 2.4. Несовместная система ограничений

Дата добавления: 2015-05-26