Решение

Допустимую область мы уже строили  она изображена на рис. 5.

Повторим еще раз этот рисунок, оставив только допустимую область и

нарисовав дополнительно прямые

(см. рис. 10).

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

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

и поэтому имеет координаты . Это и есть решение нашей задачи, т.е. есть оптимальный планзадачи (1.23). При этом значение целевой функции , что и дает её максимальное значение.

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

 

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

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

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

Дальнейшее будет посвящено более строгому обоснованию этих утверждений и формулировке алгоритма решения.

 

Задачи