Решение. Допустимая область изображена на рис

Пример

Решить задачу:

(7)

Допустимая область изображена на рис. 5. Повторим еще раз этот рисунок, оставив только допустимую область и нарисовав дополнительно прямые с₁ х₁+с₂ х₂=L (рис. 10).

Пусть, например, L =2. Тогда прямая х₁+2х₂=2 проходит через точки (2,0) и (0,1) и изображена на рис. 10. Будем теперь увеличивать L. Тогда прямая начнёт двигаться параллельно самой себе в направлении, указанном стрелкой. Максимальное значение L получится тогда, когда прямая пройдет через вершину многоугольника, указанную на рисунке, и дальнейшее увеличение L приведет к тому, что прямая выйдет за пределы многоугольника и её пересечение с допустимой областью будет пустым.

Выделенная вершина лежит на пересечении прямых:

и поэтому имеет координаты х₁= 1, х₂= 2. Это и есть решение нашей задачи, т.е. х₁= 1, х₂= 2 есть оптимальный план задачи (7). При этом значение целевой функции L=1+2·2=5, что и дает её максимальное значение.

Следует обратить внимание на то, что оптимальный план, как правило, соответствует какой-то вершине многоугольника, изображающего допустимую область. И лишь в том случае, когда прямая с₁ х₁+с₂ х₂=L совпадает со стороной многоугольника (рис. 11), решение не будет единственным. Но и в этом случае вершины, соответствующие границам этой стороны, дают оптимальные планы нашей задачи линейного программирования. Таким образом, вершины допустимой области играют в решении задач линейного программирования особую роль.

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

Подводя итог этим примерам, можно сформулировать следующие положения:

1. допустимая область - это выпуклый многоугольник;

2. оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста);

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

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