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

Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n=2 и n=3. Наиболее наглядна эта интерпретация для случая n=2, т.е. для случая двух переменных x 1 и x 2. Пусть нам задана задача линейного программирования в стандартной форме c 1 x 1 +c 2 x 2 max a 11 x 1 +a 12 x 2 b 1, a 21 x 1 +a 22 x 2 b 2, ………………. a m1 x 1 +a m2 x 2 b m, x 1 0; x 2 0.

Геометрическая интерпретация Возьмём на плоскости декартову систему координат и каждой паре чисел (x 1, x 2 ) поставим в соответствие точку на этой плоскости. Обратим прежде всего внимание на ограничения x 1 0 и x 20. Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1).

Геометрическая интерпретация Рассмотрим теперь, какие области соответствуют неравенствам вида a 1 x 1 +a 1 x 2 b. Сначала рассмотрим область, соответствующую равенству a 1 x 1 +a 1 x 2 =b. Это прямая линия. Строить её проще всего по двум точкам. Пусть b0. Если взять x 1 =0, то получится x 2 =b/a 2. Если взять x 2 =0, то получится x 1 =b/a 1. Таким образом, на прямой лежат две точки (0, b/a 2 ) и (b/a 1, 0).

Геометрическая интерпретация Дальше через эти две точки можно по линейке провести прямую линию (смотри рисунок 2). Если же b=0, то на прямой лежит точка (0,0). Чтобы найти другую точку, можно взять любое отличное от нуля значение x 1 и вычислить соответствующее ему значение x 2.

Геометрическая интерпретация Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части a 1 x 1 +a 1 x 2 b. Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая- то точка плоскости, например, начало координат, т.е. точка (0,0). Пример Определить полуплоскость, определяемую неравенством 4x 1 -6x 23.

Геометрическая интерпретация

Вернёмся теперь к задаче линейного программирования. Там имеют место m неравенств a 11 x 1 +a 12 x 2 b 1, a 21 x 1 +a 22 x 2 b 2, ………………. a m1 x 1 +a m2 x 2 b m. Каждое из них задает на плоскости некоторую полуплоскость. Нас интересуют те точки, которые удовлетворяют всем этим m неравенствам, т.е. точки, которые принадлежат всем этим полуплоскостям одновременно. Следовательно, область, определяемая неравенствами, геометрически изображается общей частью (пересечением) всех полуплоскостей, определяемых отдельными ограничениями (к ним, естественно, надо добавить ограничения x 1 0 и x 2 0). Как уже говорилось выше, эта область называется допустимой областью задачи линейного программирования.

Пример Найти допустимую область задачи линейного программирования, определяемую ограничениями -x 1 +x 2 1, x 1 -2x 2 1, x 1 +x 2 3, x 1 0, x 2 0.

Пример

Возможные случаи Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (см. рис. 6). Неосновной случай - получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 7. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение x 1 +x 2 3. Оставшаяся часть будет неограниченным выпуклым многоугольником. Наконец, возможен случай, когда неравенства противоречат друг другу, и допустимая область вообще пуста.

Геометрическая интерпретация Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция c 1 x 1 +c 2 x 2 max. Рассмотрим прямую c 1 x 1 +c 2 x 2 =L. Будем увеличивать L. Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором (c 1, c 2 ), так как это - вектор нормали к нашей прямой и одновременно вектор градиента функции f(x 1, x 2 )=c 1 x 1 +c 2 x 2.

Решение А теперь сведем всё вместе. Итак, надо решить задачу c 1 x 1 +c 2 x 2 max a 11 x 1 +a 12 x 2 b 1, a 21 x 1 +a 22 x 2 b 2, ………………. a m1 x 1 +a m2 x 2 b m, x 1 0; x 2 0. Ограничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая c 1 x 1 +c 2 x 2 =L пересекает допустимую область. Это пересечение дает какие-то значения переменных, которые являются планами. Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 9). В конце концов эта прямая выйдет на границу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой c 1 x 1 +c 2 x 2 =L с допустимой областью будет пустым. Поэтому то положение прямой c 1 x 1 +c 2 x 2 =L, при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.

Пример Решить задачу x 1 +2x 2 max -x 1 +x 21, x 1 -2x 21, x 1 +x 22, x 1 0; x 2 0.

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

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

Задание 1. 4x 1 +2x 2 max 2x 1 +3x 218, -x 1 +3x 29, 2x 1 -x 210, x 1 0; x x 1 +4x 2 max 3x 1 +2x 211, -2x 1 +x 22, x 1 -3x 20, x 1 0; x 2 0.

Задание 3. x 1 -2x 2 min x 1 -x 21, x 1 +x 2 2, x 1 -2x 20, x 1 0; x x 1 +4x 2 max -x 1 +x 2 3, x 1 +2x 2 12, 3x 1 -x 2 15, x 1 0; x 2 0.

Задание 5. x 1 +3x 2 max x 1 -x 21, 2x 1 +x 2 2, x 1 -x 20, x 1 0; x x 1 +x 2 max x 1 +2x 2 10, x 1 +2x 22, 2x 1 +x 2 15, x 1 0; x 2 0.

Задание 7. x 1 +x 2 max(min) 2x 1 +4x 216, -4x 1 +2x 2 8, x 1 +3x 2 9, x 1 0; x x 1 +3x 2 max 2x 1 +x 2 10, -2x 1 +3x 2 6, 2x 1 +4x 2 8, x 1 0; x 2 0.

Задание 9. x 1 +x 2 max x 1 +2x 214, -5x 1 +3x 2 15, 4x 1 +6x 2 24, x 1 0; x x 1 +2x 2 max 4x 1 -2x 2 12, -x 1 +3x 2 6, 2x 1 +4x 2 16, x 1 0; x 2 0.