Решение. Найти допустимую область задачи линейного программирования, определяемую ограничениями (1.21)

Пример

Найти допустимую область задачи линейного программирования, определяемую ограничениями

(1.21)

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.21). Обратите внимание на то, что получившаяся область имеет вид выпуклого многоугольника.

Вернемся теперь к общему случаю, когда одновременно выполняются неравенства

(1.22)

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

1.
Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (см. рис. 6).

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

3.
Наконец, возможен случай, когда неравенства (1.22) противоречат друг другу, и допустимая область вообще пуста.

Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция .

Рассмотрим прямую. Будем увеличивать L. Что будет происходить с нашей прямой?

Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором , так как это  вектор нормали к нашей прямой и одновременно вектор градиента функции .

А теперь сведем всё вместе. Итак, надо решить задачу

Oграничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая пересекает допустимую область. Это пересечение дает какие-то значения переменных , которые являются планами.

Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 9). В конце концов эта прямая выйдет награницу допустимой области  как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение

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