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

Для понимания свойств ЗЛП и сути методов решения ЗЛП полезно рассмотреть сначала случай n = 2 и n = 3, когда возможна наглядная геометрическая интерпретация. Мы ограничимся рассмотрением случая двух переменных. Пусть дана ЗЛП в первой стандартной форме:

(1)

- - - - - - - - - - - - -

Удобно план этой ЗЛП изображать точкой в некоторой декартовой системе координат. Условие неотрицательности переменных «вырезает» первый квадрант. Неравенство вида

(2)

определяет полуплоскость, лежащую по одну сторону прямой

(3)

и содержащую точки этой прямой.

Для построения прямой достаточно найти две ее точки. Если прямая (3) не проходит через начало координат, то в качестве таких точек можно взять и . Для определения полуплоскости, соответствующей неравенству (2), можно поступить так. Берется любая точка (p, q), не лежащая на прямой (3). Удобно брать точку (0, 0), если она не лежит на прямой (3). Если эта точка удовлетворяет неравенству (2), то искомой полуплоскостью является та, в которой лежит точка (p, q). Если эта точка не удовлетворяет неравенству (2), то искомой полуплоскостью является та, в которой не лежит точка (p, q).

Таким образом, допустимая область в ЗЛП (1) получается как пересечение m полуплоскостей и первого квадранта и представляет собой многогранную область.

Линии уровня целевой функции являются прямыми, проходящими перпендикулярно вектору нормали Перемещение с одной линии уровня на другую в направлении вектора нормали соответствует увеличению значения целевой функции.

Если оптимальный план ЗЛП (1) существует, то он получается как точка касания одной из линий уровня, причем такой, что при дальнейшем перемещении вдоль вектора нормали линии уровня не будут иметь общих точек с допустимой областью.

В этом состоит сущность геометрического метода решения ЗЛП. Чтобы проиллюстрировать этот метод, рассмотрим

Пример. Требуется найти решение ЗЛП

(4)

Решение. Построим допустимую область и линии уровня целевой функции.

1) Полуплоскость лежит левее и выше прямой, проходящей через точки (1; 0) и (0; -1).

2) Полуплоскость лежит правее и ниже прямой, проходящей через точки (-1; 0) и (0; 1).

3) Полуплоскость лежит левее и ниже прямой, проходящей через точки (2; 0) и (0; 2).

4) Линии уровня целевой функции проходят перпендикулярно вектору нормали Одна из линий уровня проходит через точки (2; 0) и (0; 1).

Проиллюстрируем сказанное на рисунке.

Рис. 1. Геометрическая иллюстрация решения ЗЛП

Из рисунка видно, что одна из линий уровня касается допустимой области в точке пересечения прямых и . Легко определить, что это точка (0,5; 1,5).

Таким образом, оптимальный план рассматриваемой ЗЛП есть

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

Из геометрической интерпретации ЗЛП в случае n = 2 и n = 3 можно сделать следующий вывод: оптимальный план, если он существует, соответствует вершине многоугольной допустимой области при n = 2 или многогранной допустимой области при n = 3.

Дата добавления: 2014-01-11