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

Определение. Любое решение системы ограничений называется допустимым решением ЗЛП.
Определение. Допустимое решение, в котором целевая функция достигает максимального или минимального значения, называется оптимальным решением.

В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с1x +  с2y.
Заметим, что переменные x, y в ЗЛП принимают, как правило, неотрицательные значения (x≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости.

Рассмотрим линейную функцию F = с1x + с2y и зафиксируем какое-нибудь ее значение F. Пусть, к примеру, F = 0, т.е. с1x + с2y  =  0. Графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис.).


Рисунок

При изменении этого фиксированного значения F = d, прямая с1x+ с2y = d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с1x + с2y =  d, при некотором значении d = d 1 достигнет многоугольника D, назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении d =  d2 будем иметь с ним последнюю общую точку В, назовем В «точкой выхода».
Очевидно, что своего наименьшего и наибольшего значения целевая функция F=с1x + с2y достигнет в точках «входа» А и «выхода» В.
Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D, можно предложить следующий план решения ЗЛП:
  1. построить область решений системы ограничений;
  2. построить прямую, соответствующую целевой функции, и параллельным переносом этой прямой найти точку «входа» или «выхода» (в зависимости от требования минимизировать или максимизировать целевую функцию);
  3. определить координаты этой точки, вычислить в них значение целевой функции.

Заметим, что вектор (с1, с2), перпендикулярный прямой, показывает направление роста целевой функции.

При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения.

Случай 1


Рисунок 6

При перемещении прямой с1xс2y= d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с1х с2у =  d .
В этом случае точек «выхода» (« входа») бесчисленное множество, а именно – любая точка отрезка АВ. Это означает, что целевая функция принимает максимальное(минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D.

Случай 2
Рассмотрим случай, когда область допустимых значений неограниченна.
В случае неограниченной области целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена.


Рисунок

Необходимо найти максимальное значение целевой функции F = 4x + 6y → max , при системе ограничений

Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
x + y = 18

x

12

9

y

6

9

0,5x + y = 12


x

12

18

y

6

3

x =  12 – параллельна оси OY ;
y =  9 – параллельна оси OX ;
x =  0 – ось OY ;
y =  0 – ось OX;
x≥ 0 – полуплоскость правее оси OY;
y ≥ 0 – полуплоскость выше оси OX;
y ≤ 9 – полуплоскость ниже y =  9;
x≤ 12 – полуплоскость левее x  =  12;
0,5x + y≤ 12 – полуплоскость ниже прямой 0,5x + y = 12;
x + y≤ 18 – полуплоскость ниже прямой x +  y =  18.

Рисунок

Пересечением всех этих полуплоскостей является очевидно, пятиугольник ОАВСД, с вершинами в точках О(0; 0), А(0; 9), В(6; 9), С(12; 6), Д(12; 0). Этот пятиугольник и образует область допустимых решений задачи.

Рассмотрим целевую функцию задачи F  =  4x +  6y → max.


x

3

0

y

–2

0

Построим прямую, отвечающую значению функции F = 0 : 4x + 6y = 0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x+ 6y = const последней вершиной, через которую пройдет прямая при выходе за границу многоугольника, будет вершина С (12; 6). Именно в ней F =  4x +  6y достигнет своего максимального значения.
Значит, при x =  12, y =  6 функция F достигает своего максимального значения F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12; 6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F*  =  84 (оптимальное значение будем обозначать «*»).
Задача решена. Итак, необходимо выпустить 12 изделий I вида и 6 изделий II вида, при этом прибыль составит 84 тыс. руб.

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

загрузка...