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

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

Рассмотрим следующую задачу:

(5.1)

(5.2)

(5.3)

(5.4)

(5.5)

Допустимым решением ЗЛП называется такая совокупность значений переменных , которая удовлетворяет всем ограничениям задачи. Тогда можно сказать, что оптимальное решение задачи ЗЛП – это такое из допустимых решений, при котором значение целевой функции максимально (минимально).

Например: пара чисел =2, =9 не будет допустимым решением , т. к. не удовлетворяет ограничению (5.2) и (5.3), а пара чисел =1, =1 – допустимое решение, так как удовлетворяет всем ограничениям. Решение же =-5, =3 как и любое другое содержащее отрицательное значение переменной, допустимым решением не будет т. к. не удовлетворяет ограничению (5.4) и (5.5).

Будем изображать все возможные решения ЗЛП с 2-мя переменными и точками на координатной плоскости.

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

Построим координатную плоскость (рис.5.1) у которой по оси абcцисс будут откладываться значения , а по оси ординат –.

Рис. 5.1

Точки (решения) удовлетворяющие ограничению (5.4) будут находятся правее оси ординат в 1-м и 4-м квадрантах. Ограничению (5.5) удовлетворяют точки (решения) расположенные выше оси абcцисс, в 1-м и 2-м квадрантах. Таким образом решения одновременно удовлетворяющие ограничениям (5.4) и (5.5) находятся в 1-м квадранте. Следовательно, допустимые решения любой задачи линейного программирования всегда находятся в первой четверти координатной плоскости.

Рассмотрим неравенство (5.2). Для этого запишем, сначала, соответствующе равенство

6+ 5=30 (5.5)

Это уравнение прямой. Чтобы построить эту прямую, достаточно найти координаты двух точек: А и В. (cм. Рис 5.2) В точке А =0. Подставив =0 в выражение (5.5) получаем:

5=30, (5.6)

Откуда находим :

=6. (5.7)

Следовательно ордината точки А равна 6 . Найдем теперь координаты точки В. Для этого подставим в выражение (5.5) значение =0. Получим

6=30, (5.8)

Откуда

=5. (5.9)

Следовательно, абcцисcа точки В: =5. Соединив точки А и В получаем прямую АВ. Учитывая знак неравенства ограничения (5.2), можно сделать вывод о том, что точки удовлетворяющие ему, лежат ниже прямой АВ или на ней самой. Одновременно трем (5.2), (5.4) и (5.5) ограничениям удовлетворяют точки лежащие внутри и на границе треугольника ОАВ.

Аналогично учитывается ограничение (5.3). Все точки, для которых оно выполняется, лежат ниже прямой СD или на ней. Уравнение этой прямой

4+ 7=28, (5.10)

А координаты точек С и D можно найти также, как и координаты точек А и В:

Ордината точки С - =4, а абcцисcа точки D - =7.

Рис. 5.2

Из рисунка 5.2 видно что точки удовлетворяющие всем ограничениям (5.2) -(5.5) находятся внутри и на границе многоугольника ОСЕВ. Множество этих точек и образуют область допускаемых решений (ОДР). ОДР называется геометрический образ (изображение) множества допускаемых решений.

Оказалось таким образом, что для ЗЛП с 2-мя переменными ОДР – это выпуклый многоугольник на координатной плоскости.

Среди множества допустимых решений необходимо найти оптимальное. Для этого рассмотрим целевую функцию (5.1). Будем придавать ей различные значения и определять, где находятся соответствующие им точки в ОДР. Построим прямую, соответствующую случаю, когда значение целевой функции будет равно 1:

(5.11)

В выражении (5.11) используется индексная переменная , которая показывает, что ищется прямая, которая соответствует значению целевой функции равной 1:

(5.12)

Найдем ординату =0, =1/4 и абcцисcу =0, =1/3 точек пересечения прямой c координатными осями и построим эту прямую на рис.5.2. Среди всех точек этой прямой области допустимых решений принадлежат только точки отрезка , для каждой из которых =1.

Пусть теперь значение целевой W функции равно 6:

(5.13)

Это уравнение* прямой, параллельной предыдущей и расположенной выше

нее. Стрелкой указано направление смещения прямой, соответствующее возрастанию целевой функции. Среди точек этой прямой области допустимых решений принадлежат только точки отрезка . Очевидно, теперь, что максимальное значение целевой функции на множестве допустимых решений достигается при самом верхнем положении прямой W, когда она еще проходит хотя бы через одну точку, принадлежащую ОДР. Это прямая L, проходящая через точку Е. Ее координаты определяются из решения системы уравнений (5.5) и (5.10):

= 3.18, = 2,18. Эта пара чисел является оптимальным решением данной задачи линейного программирования. Значение целевой функции для него равно:

W= 3∙3,18+4∙2,18=18,26 (5.14)

Анализируя полученные результаты можно сделать следующие выводы.

_____________________________________________________________________

* Точки пересечения прямой W c координатными осями можно найти также, как были найдены аналогичные точки для прямой W.

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

При n=2 - ОДР– выпуклый многоугольник, n=3 – ОДР – выпуклый многогранник в 3^х мерном пространстве.

2.Оптимальное решение, если оно существует, всегда достигается на границе ОДР, а именно в одной из вершин многогранника допустимых решений. Допустимое решение, находящееся в одной из вершин этого многогранника, называется опорным решение, а сама вершина- опорной точкой. В рассмотренном примере вершинам многогранника соответствуют опорные точки ОСЕВ. Поэтому задачу линейного программирования можно решать путем перебора всех вершин (опорных решений) многогранника соответствующего ОДР, выбирая ту вершину, которая соответствует max или min целевой функции..

На этой идее и базируется основной метод решения ЗЛП, называемый симплекс – метод. Согласно этому методу реализуется непростой, а направленный перебор опорных решений, при котором каждому последующему опорному решению соответствует лучшее значение целевой функции.

Рассмотрим различные случаи, которые могут быть при решении ЗЛП.

Случай 1.

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

Случай 2.

ЗЛП не имеет решений. Это может быть в 2^х случаях:

А) Множество допустимых решений пусто. Например, система ограничений задачи имеют вид

(5.15)

(5.16)

Рис. 5.3

Эта система не имеет решений, поэтому допустимых решений задачи не существует. Как видно из рис. 5.3, точки удовлетворяющие первому ограничению (выражение (5.15), находятся ниже прямой 1, а допустимые решения удовлетворяющие второе ограничение (выражение (5.16)), выше прямой 2.

Б) Целевая функция не ограничена, т.е. Может принимать сколь угодно большие значения. Этот случай иллюстрирует следующий пример:

Рис. 5.4

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

Случай 3

Оптимальное решение в некоторых случаях может лежать не только в вершине многогранника, но и в точках на некотором его ребре. В этом случае задача имеет не одно, а множество решений. Так, например, произойдёт если в предыдущем примере ( 5.1 )- (5.5 ) прямая W будет параллельна отрезку АВ (см. рис5.2).

Например выражение для целевой функции будет иметь вид:

W=6+5max

В этом случае оптимальным решением будет любая точка отрезка АВ. Такой случай называется вырожденным.