 |
Этапы решения графического метода задач линейного программирования
|
|
|
|
Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно.
Пусть задача линейного программирования задана в двумерном пространстве, т. е. ограничения содержат две переменные.
Если в ЗЛП ограничения заданы в виде неравенств с двумя переменными, она может быть решена графически. Графический метод решения ЗЛП состоит из следующих этапов.
Этап 1.
Сначала на координатной плоскости x 1 Ox 2 строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям:
| (1.31) |
Не приводя строгих доказательств, укажем те случаи, которые тут могут получится.
1. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (рис. 3а)).
2. Неосновной случай - получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 3.б. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение 
. Оставшаяся часть будет неограниченным выпуклым многоугольником.
|
|
|
Наконец, возможен случай, когда неравенства (1.31) противоречат друг другу, и допустимая область вообще пуста.
Рассмотрим теорию на конкретном примере:
Найти допустимую область задачи линейного программирования, определяемую ограничениями
| (1.32) |
|
|
|
Решение:
1. Рассмотрим прямую 
. При 
, а при 
. Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Беря 
получим, что -0+0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.а.
2. Рассмотрим прямую 
. При 
, а при. Таким образом, эта прямая проходит через точки (0, -1/2) и (1,0). так как 
(4.б).
3. Наконец, рассмотри 
м прямую 
. Она проходит через точки (0,3) и (3,0) и так как 0+0<3, то интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.в.
Сводя все вместе и добавляя условия 
получим рисунок 5, где выделена область, в которой выполняются одновременно все ограничения (1.32). Обратите внимание на то, что получившаяся область имеет вид выпуклого многоугольника.
Этап 2.
Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция 
.
|
Рассмотрим прямую 
. Будем увеличивать L. Что будет происходить с нашей прямой?
Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором 
, так как это - вектор нормали к нашей прямой и одновременно вектор градиента функции 
.
А теперь сведем всё вместе. Итак, надо решить задачу
Oграничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая пересекает допустимую область. Это пересечение дает какие-то значения переменных 
, которые являются планами.
Этап 3
Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 7). В конце концов эта прямая выйдет награницу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение
|
прямой с допустимой областью будет пустым. Поэтому то положение прямой , при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.
|
|
|
1.4 Примеры задач, решаемых графическим методом.
Пример:
Решить задачу
| (1.41) |
Решение
Допустимую область мы уже строили - она изображена на рис. 5.
Повторим еще раз этот рисунок, оставив только допустимую область и
нарисовав дополнительно прямые (см. рис. 8).
|
Пусть, например, L =2. Тогда прямая 
проходит через точки (2,0) и (0,1) и изображена на рис. 8. Будем теперь увеличивать L. Тогда прямая начнёт двигаться параллельно самой себе в направлении, указанном стрелкой. Легко догадаться, что максимальное значение L получится тогда, когда прямая пройдет через вершину многоугольника, указанную на рисунке, и дальнейшее увеличение L приведет к тому, что прямая выйдет за пределы многоугольника и её пересечение с допустимой областью будет пустым.
Выделенная вершина лежит на пересечении прямых
и поэтому имеет координаты 
. Это и есть решение нашей задачи, т.е. есть оптимальный план задачи (1.41). При этом значение целевой функции 
, что и дает её максимальное значение.
Обратите внимание на то, что оптимальный план, как правило, соответствует какой-то вершине многоугольника, изображающего допустимую область. И лишь в том случае, когда прямая случиться так, что решение не будет единственным. Но и в этом случае вершины, соответствующие границам этой стороны, дают оптимальные планы нашей задачи линейного программирования. Таким образом, вершины допустимой области играют в решении задач линейного программирования особую роль.
|
Ну, а если допустимая область неограничена, то и значение целевой функции может быть неограниченным.
Подводя итог этим примерам, можно сформулировать следующие положения:
1. допустимая область - это выпуклый многоугольник;
2. оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста);
3. ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи.
|
|
|
