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

В этом разделе будет показано, что в задаче ЛП с двумя переменными можно получить решение графическим способом. Хотя такая задача редко встречается на практике (типовая задача ЛП обычно содержит тысячи переменных), идеи, вытекающие из графического способа нахождения оптимального решения, будут положены в основу построения общего метода решения задачи ЛП (называемого симплекс-методом).

Графический способ решения задачи ЛП состоит из двух этапов:

1 Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.

2 Нахождение оптимального решения среди всех точек пространства допустимых решений.

Далее графический способ решения описан на примере задачи (1.1), (1.2).

Этап 1 Построение пространства допустимых значений.

Сначала проведем оси: на горизонтальной будут указываться значения переменной х₁, а на вертикальной – х₂ (рисунок 1.1). Далее рассмотрим условие неотрицательности переменных: х₁ ≥ 0, х₂ ≥ 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте.

Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получим уравнения прямых, а затем на плоскости проведем эти прямые. Например, неравенство 6х₁+4х₂≤24 заменяется уравнением прямой 6х₁+4х₂=24. Чтобы провести эту линию, надо найти две различные точки, лежащие на этой прямой. Можно положить х₁=0, тогда х₂=24/4=6. Аналогично для х₂=0, тогда х₁=24/6=4. Итак, наша прямая проходит через две точки (0,6) и (4,0). Эта прямая обозначена на рисунке 1.1 как линия (1).

Рисунок 1.1 - Область допустимых решений задачи (1,1), (1,2).

Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость (х₁,х₂) на два полупространства, которые располагаются по обе стороны прямой, которая, как показано выше, соответствует данному неравенству. Точки плоскости, расположенные по одну сторону прямой, удовлетворяют неравенству (допустимое пространство), а точки, лежащие по другую сторону, - нет. “Тестовой” точкой, проверяющей, точки какого полупространства удовлетворяют неравенству, а какого – нет, может служить точка (0,0). Например, эта точка удовлетворяет первому неравенству 6х₁+4х₂≤24 (здесь 6 × 0+4 × 0=0≤24). Это означает, что точки полупространства, содержащего начальную точку (0,0), удовлетворяют этому неравенству. На рисунке 1.1 допустимые полупространства показаны стрелочками.

Этап 2  Нахождение оптимального решения.

Точки пространства допустимых решений, показанного на рисунке 1.1, удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках A, B, C, D, E и F. Любая точка, расположенная внутри или на границе области, ограниченной ломаной ABCDEF, является допустимым решением, т.е. удовлетворяет всем ограничениям. Поскольку пространство допустимых решений содержит бесконечное число точек, необходима некая процедура поиска оптимального решения.

 Нахождение оптимального решения требует определения направления возрастания целевой функции z =5x ₁ +4x ₂ (напомним, что мы максимизируем функцию z). Мы можем приравнять z к нескольким возрастающим значениям, например, 10 и 15. Эти значения, подставленные вместо z в выражение целевой функции, порождают уравнения прямых; для значений 10 и 15 получаем уравнения прямых 5 x ₁ +4x ₂ =10 и 5 x ₁ +4x ₂ =15. На рисунке 1.2 эти прямые показаны штриховыми линиями, а направление возрастания целевой функции – толстой стрелкой. Целевая функция может возрастать до тех пор, пока прямые, соответствующие возрастающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей максимально возможному значению целевой функции, и будет точкой оптимума.

На рисунке 1.2 видно, что оптимальное решение соответствует точке С. Эта точка является местом пересечения прямых (1) и (2), поэтому ее координаты х₁ и х₂ находятся как решение системы уравнений, задающих эти прямые:

Решением этой системы будет х₁=3 и х₂=1,5, при этом значение целевой функции равно z =5x ₁ +4x ₂ =5 × 3+4 × 1,5=21. Полученное решение обозначает, что для компании из примера 1.1 оптимальным выбором будет ежедневное производство 3т краски для наружных работ и 1,5т – для внутренних работ с ежедневным доходом 21тыс.руб.

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

Рисунок 1.2 - Графическое решение задачи  ЛП (1.1), (1.2)