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

 

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

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

Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D, можно предложить следующий план решения ЗЛП:

 построить область решений системы ограничений;

 построить прямую, соответствующую целевой функции, и параллельным переносом этой прямой найти точку «входа» или «выхода» (в зависимости от требования минимизировать или максимизировать целевую функцию);

 определить координаты этой точки, вычислить в них значение целевой функции.

 

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

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

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

Геометрическая интерпретация, которой мы пользовались при решении задач ЛП, перестает быть пригодной для этой цели при числе свободных переменных n – m > 3, а затруднительна уже при n – m = 3. Для нахождения решения задачи ЛП в общем случае применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод.

Универсальный метод решения задач ЛП называется симплекс-методом. Пример. Решить следующую задачу ЛП в канонической форме симплекс-методом.

Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.

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

Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.