Геометрическая интерпретация задач линейного программирования

Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n =2 и n =3.

Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных и . Пусть нам задана задача линейного программирования в стандартной форме

Возьмём на плоскости декартову систему координат и каждой паре чисел поставим в соответствие точку на этой плоскости.

Обратим прежде всего внимание на ограничения и . Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида . Сначала рассмотрим область, соответствующую равенству . Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам.

Пусть . Если взять , то получится . Если взять , то получится . Таким образом, на прямой лежат две точки и . Дальше через эти две точки можно по линейке провести прямую линию (смотри рисунок 2).

Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение и вычислить

соответствующее ему значение .

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части , а в другой наоборот . Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).

Пример

Определить полуплоскость, определяемую неравенством .

Решение

Сначала строим прямую . Полагая получим или . Полагая получим или . Таким образом, наша пря- мая проходит через точки (0, -1/2) и (3/4, 0) (см. рис. 3)

Теперь посмотрим, в какой полуплоскости лежит точка (0,0), т.е. начало координат. Имеем , т.е. начало координат принадлежит полуплоскости, где . Тем самым определилась и нужная нам полуплоскость (см. рис. 3).

Вернёмся теперь к задаче линейного программирования. Там имеют место m неравенств

(1.20)

Каждое из них задает на плоскости некоторую полуплоскость. Нас интересуют те точки, которые удовлетворяют всем этим m неравенствам , т.е. точки, которые принадлежат всем этим полуплоскостям одновременно. Следовательно, область, определяемая неравенствами вида (1.20), геометрически изображается общей частью (пересечением) всех полуплоскостей, определяемых отдельными ограничениями (к ним,

естественно, надо добавить ограничения и ).

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

Пример

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

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

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

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

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

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

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

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

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

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

Пример

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

(1.23)

Решение

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

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

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

(см. рис. 10).

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

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

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

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

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

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

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

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

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

Задачи

Не нашли, что искали? Воспользуйтесь поиском по сайту: