Решение

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

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

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

(см. рис. 10).

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

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

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

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

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

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

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

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

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

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

Задачи

Решить графически следующие задачи линейного программирования.

2. Симплекс-метод

2.1. Выпуклые множества и многогранники

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

Рассмотрим n - мерное евклидово пространство  и пусть  точка в этом пространстве.

Рассмотрим две точки и , принадлежащие .Множество точек , которые могут быть представлены в виде

(в координатах это записывается так:

,

называется выпуклой комбинацией точек и

, или

отрезком, соединяющим точки и . Сами точки и называются концами отрезка. В случаях n =2 и n =3 это  отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при  =0 , а при  =1 , т.е. при  =0 и  =1 получаются концы отрезка.

 

Пусть в

заданы k точек

. Точка

,

где все и называется выпуклой комбинацией точек .

Пусть есть некоторая область в пространстве (другими словами,

G есть некоторое множество точек из

).

Определение. Множество (область) называется выпуклым, если из того, что и следует, что для   [0,1]. Другими словами, G  выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.

 

На этих рисунках "а" и "б" - выпуклые множества, а "в" не является выпуклым множеством, так как в нём есть такая пара точек, что соединяющий их отрезок не весь принадлежит этому множеству.

Теорема 1. Пусть G  выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.