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

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

Известно, что любой упорядоченный набор n чисел можно геометрически интерпретировать как точку или вектор n -мерного пространства. Поэтому и планы задачи линейной оптимизации =(х₁,х₂,…,х_n) будем интерпретировать как точки или векторы.

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

Рассмотрим модель вида (1.2) ─ (1.4) с двумя переменными

f =С₁х₁ +С₂х₂ max (3.1.)

а₁₁х₁ + а₁₂х₂ b₁

а₂₁х₁ + а₂₂х₂ b₂ (3.2.)

_{…………………………….}

а_m1х₁ + а_m2х₂ b_m

х₁ 0, х₂ 0 (3.3.)

На координатной плоскости Ох₁х₂ линейное уравнение вида а_ijх_j+а_ijх_j=b_i изображается прямой, а линейное неравенство а_ijх_j+а_ijх_j b_i или а_ijх_j+а_ijх_j b_i является полуплоскостью. Условия неотрицательности определяют полуплос­кости соответственно с граничными прямыми х₁=0 и х₂=0. Если система ограничений совместна, то полуплоскости как выпуклые множества, пересекаясь, образуют общую часть, которая яв­ляется выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область.

Пусть наша система неравенств (3.2.) и (3.3.) образует область допустимых решений в виде многоугольника решений (непустого множества) (рисунок 1).

Придадим целевой функции произвольное значение, например равное k. Получим С₁х₁ +С₂х₂ = k. А это уравнение прямой линии, в каждой точке которой целевая функция сохраняет одно и то же постоянное значение равное k. Если теперь k считать параметром, а не константой, то мы получим семейство параллельных прямых, называемых линиями уровня целевой функции.

Осталось найти направление возрастания и убывания целевой функции. Найдем частные производные целевой функции по переменным х₁ и х₂: , .

Рис 1.

Они показывают скорость возрастания целевой функции вдоль осей х₁ и х₂ соответственно. Вектор = (С₁, С₂) показывает направление наискорейшего возрастания целевой функции и называется вектором-градиентом целевой функции. Вектор (- ) =(-С₁;-С₂) называют антиградиентом и он указывает направление наискорейшего убывания целевой функции. Вектор = (С₁, С₂) перпендикулярен к прямым семейства f=const.

Таким образом, геометрически задача линейной оптимизации (3.1.)-(3.3.) пред­ставляет собой поиск такой точки многогранника решений, координаты которой доставляют линейной функции наи­большее (наименьшее) значение, причем допустимыми ре­шениями являются все точки многогранника решений.

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

Этап 1. Сначала на координатной плоскости Ох₁х₂ стро­ится допустимая многоугольная область (область допусти­мых решений, область определения), соответствующая огра­ничениям. Далее строится вектор-градиент линейной функ­ции. Начало вектора находится в точке с координатами (0; 0), а вершина ― в точке с координатами (С₁, С₂). Следует заметить, что значения С₁ и С₂ и есть коэффициенты при переменных целевой функции задачи.Для удобства можно строить век­тор, пропорциональный вектору . В какой-нибудь точке, принадлежащей допус­тимой области строится прямая семейства f=const, которая всегда будет проходить перпендикулярно вектору-градиенту.

Этап 2. Прямая f=const, перпендикулярная век­тору-градиенту, перемещается в направлении этого вектора в случае максимизации функции (или в противоположном направлении задачи минимизации) до тех пор, пока не покинет пределов многоугольной области. Крайняя (предельная) точка (или точки) области при этом движении и является точкой мак­симума (минимума) целевой функции.

Этап 3. Для нахождения координат точки максимума (минимума) достаточно решить систему из двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума (минимума). Например это значения а₁ и а₂. Значение функции, найденное в получаемой точке, является максимальным (минимальным). И затем останется выписать ответ, который будет иметь вид: ^*= (а₁,а₂),f_max = f(а₁,а₂).

В случае минимизации целевой функциипрямую f=const надо перемещать в направлении, противоположном вектору-гра­диенту (по направлению вектора-антиградиента). Ясно, что если прямая при своем движении не по­кидает допустимой области, то соответствующий максимум

или минимум целевой функции не существует (целевая функция неограниченна на множестве планов).

Пример 3. Решить графическим методом задачу примера 1:

f = 80 х₁ + 100 х₂ max.

5 х₁ + 10 х₂ 1000,

4 х₁ +6 х₂ 900,

4 х₁ +4 х₂ 600,

30 х₁ +50 х₂ 6000,

х₁ 0,

х₂ 0.

Решение: Ограничения х₁ 0, х₂ 0 означают, что область решений будет лежать в первой четверти декартовой системы координат. Отметим эту область на рис. 2 (первая четверть, указываем направление стрелочками).

Этап 1. Определим множество решений первого нера­венства. Оно состоит из решения уравнения 5 х₁ + 10 х₂ = 1000 и строгого не­равенства 5 х₁ +10 х₂ <1000. Решением уравнения служат точки прямой 5 х₁ + 10 х₂ = 1000. Построим прямую по двум точкам (0; 100) и (200; 0), которые легко получить в результате последовательного обнуления одной из переменных: пусть х₁=0, тогда х₂= (1000 - 5*0) / 10 = 100, пусть х₂=0, тогда х₁= (1000- 10*0) / 5 = 200.

На рисунке обозначим эту прямую цифрой I. Множество решений строгого неравенства — одна из по­луплоскостей, на которую делит плоскость построенная пря­мая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взя­той точке, не принадлежащей прямой, неравенство выпол­няется, то оно выполняется и во всех точках той полуплос­кости, которой принадлежит контрольная точка, и не вы­полняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Подставим ко­ординаты (0; 0) в неравенство, получим 5*0+10*0 = 0 < 1000, т.е. оно вы­полняется. Следовательно, областью решения неравенства служит «нижняя» полуплоскость.

Аналогичным образом построим области решения трех других неравенств

Ø 4 х₁ +6 х₂ 900,

(0; 150) и (225; 0) на рисунке прямая II и берется «нижняя» полуплоскость;

Ø 4 х₁ +4 х₂ 600,

(0; 150) и (150; 0) на рисунке прямая III и берется «нижняя» полуплоскость;

Ø 30 х₁ +50 х₂ 6000,

(0; 120) и (200; 0) на рисунке прямая IV и опять берется «нижняя» полуплоскость.

Заштрихуем общую область для всех неравенств, обозна­чим вершины многоугольника латинскими буквами ОABD (рисунок 2). Это и будет область допустимых решений рассмат­риваемой задачи в виде замкнутого четырехугольника.

Этап 2. Для определения направления движения к оп­тимуму построим вектор-градиент (на рисунке это grad), координаты которого (80; 100). Вектор-градиент (80, 100) показывает направление наискорейшего возрастания целевой функции. Чтобы построить этот вектор, нужно соединить начало координат c точкой (80; 100). Для удобства можно строить век­тор, пропорциональный вектору . Приравняем целевую функцию постоянной ве­личине а: 80х₁+ 100х₂ = а. Пусть а=3200, вычис­лим координаты двух точек, удовлетворяющих соответст­вующему уравнению 80х₁ + 100х₂ = 3200. В качестве одной из этих точек удобно взять точку (40; 0), в качестве второй точки возьмем точку (0; 32). Через эти две точки проведем линию уровня (пунктирная прямая f(x) на рис. 2), следует еще раз заметить, что данная линия перпендикулярна вектору-градиенту.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16. Рис 2.

Так как мы находим решение задачи максимизации, то перемещать нашу прямую линии уровня необходимо по вектору градиенту. В нашем случае движение линии уровня (пунктирная прямая f(x)) будем осущест­влять до ее пересечения с точкой В; далее она выходит из области допустимых решений. Следовательно, именно в этой точке достигается максимум целевой функции. Найдем координаты этой точки, решив систему уравнений прямых пересечения в данной точке (это первая и третья прямые).

5 х₁ + 10 х₂ = 1000, х₁ = 100

4 х₁ +4 х₂ = 600, х₂ = 50

Вычислим значение целевой функции в данной точке, подставив найденные значения в выражение f = 80х₁ + 100х₂ = 80*100+100*50 = 13000. Отсюда лег­ко записать решение исходной задачи линейного программирования:

х₁^* = 100, х₂^* = 50, f_max = 13000.

Ответ: ^* = (100;50), f_max = 13000. Итак, чтобы доход был максимальным и равен 13000 ден.ед. при ограничениях на ресурсы (материал, время, затраты) в течение месяца необходимо выпускать 10000 плит (100 партий в 100 плит) обычного вида и 5000 плит (50 партий в 100 плит) улучшенного качества. ■

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

Если область допустимых решений является выпуклым незамкнутым многоугольником в направлении оптимизации целевой функции, то целевая функция будет неограниченной и задача не будет иметь решений; в этом случае условно можно записать, что, например, max f(X) = + (рисунок 3 (б)).

а)

б)

в)

Рис. 3.

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