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

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

n=2 и n=3.
Наиболее наглядна эта интерпретация для случая n=2, т.е. для случая двух переменных x1 и x2. Пусть нам задана задача линейного программирования в стандартной форме
c1x1+c2x2→max
a11x1+a12x2≤b1,
a21x1+a22x2≤b2,
……………….
am1x1+am2x2≤bm,
x1≥0; x2≥0.

чисел (x1, x2) поставим в соответствие точку на этой плоскости.
Обратим

прежде всего внимание на ограничения x1≥0 и x2≥0. Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1).

рассмотрим область, соответствующую равенству a1x1+a1x2=b. Это прямая линия. Строить её

проще всего по двум точкам.
Пусть b≠0. Если взять x1=0, то получится x2=b/a2. Если взять x2=0, то получится x1=b/a1. Таким образом, на прямой лежат две точки (0, b/a2) и (b/a1, 0).

прямую линию (смотри рисунок 2).
Если же b=0, то на прямой

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

В одной её части a1x1+a1x2b.

Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).
Пример
Определить полуплоскость, определяемую неравенством 4x1-6x2≤3.

m неравенств
a11x1+a12x2≤b1,
a21x1+a22x2≤b2,
……………….
am1x1+am2x2≤bm.
Каждое из них задает на плоскости некоторую полуплоскость. Нас

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

многоугольника (см. рис. 6).
Неосновной случай - получается неограниченный выпуклый

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

кроме системы неравенств, есть еще целевая функция c1x1+c2x2→max.
Рассмотрим прямую c1x1+c2x2=L.

Будем увеличивать L. Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором (c1, c2), так как это - вектор нормали к нашей прямой и одновременно вектор градиента функции f(x1, x2)=c1x1+c2x2.

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

прямая c1x1+c2x2=L пересекает допустимую область. Это пересечение дает какие-то значения переменных , которые являются планами.
Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 9). В конце концов эта прямая выйдет на границу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой c1x1+c2x2=L с допустимой областью будет пустым. Поэтому то положение прямой c1x1+c2x2=L, при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.

соответствует какой-то вершине многоугольника, изображающего допустимую область. И лишь в

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

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

следующие положения:
допустимая область - это выпуклый многоугольник;
оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста);
ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи.