Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Допустимая область изображена на рис. 5. Повторим еще раз этот рисунок, оставив только допустимую область и нарисовав дополнительно прямые с1 х1+с2 х2=L (рис. 10).
Пусть, например, L =2. Тогда прямая х1+2х2=2 проходит через точки (2,0) и (0,1) и изображена на рис. 10. Будем теперь увеличивать L. Тогда прямая начнёт двигаться параллельно самой себе в направлении, указанном стрелкой. Максимальное значение L получится тогда, когда прямая пройдет через вершину многоугольника, указанную на рисунке, и дальнейшее увеличение L приведет к тому, что прямая выйдет за пределы многоугольника и её пересечение с допустимой областью будет пустым.
Выделенная вершина лежит на пересечении прямых:
и поэтому имеет координаты х1= 1, х2= 2. Это и есть решение нашей задачи, т.е. х1= 1, х2= 2 есть оптимальный план задачи (7). При этом значение целевой функции L=1+2·2=5, что и дает её максимальное значение.
Следует обратить внимание на то, что оптимальный план, как правило, соответствует какой-то вершине многоугольника, изображающего допустимую область. И лишь в том случае, когда прямая с1 х1+с2 х2=L совпадает со стороной многоугольника (рис. 11), решение не будет единственным. Но и в этом случае вершины, соответствующие границам этой стороны, дают оптимальные планы нашей задачи линейного программирования. Таким образом, вершины допустимой области играют в решении задач линейного программирования особую роль.
Если же допустимая область неограниченна, то и значение целевой функции может быть неограниченным.
Подводя итог этим примерам, можно сформулировать следующие положения:
1. допустимая область - это выпуклый многоугольник;
2. оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста);
3. ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи.
Дата публикования: 2014-12-10; Прочитано: 318 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!