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

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

• решения задач с двумя переменными, когда ограничения выра­жены неравенствами;

• решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных пере­менных.

Запишем задачу линейного программирования с двумя переменными:

1. целевая функция:

(8.34)

2. ограничения:

(8.35)

. (8.36)

Каждое из неравенств (8.35) — (8.36) системы ограничений за­дачи геометрически определяет полуплоскость соответственно с граничными прямыми . В том случае, если система неравенств (8.35) — (8.36) совместна, об­ласть ее решений есть множество точек, принадлежащих всем ука­занным полуплоскостям. Так как множество точек пересечения данных полуплоскостей - выпуклое, то областью допустимых ре­шений является выпуклое множество, которое называется много­угольником решений. Стороны этого многоугольника лежат на пря­мых, уравнения которых получаются из исходной системы ограни­чений заменой знаков неравенств на знаки равенств.

Областью допустимых решений системы неравенств (8.35) — (8.36) может быть:

• выпуклый многоугольник;

• выпуклая многоугольная неограниченная область;

• пустая область;

• луч;

• отрезок;

• единственная точка.

Целевая функция (8.34) определяет на плоскости семейство па­раллельных прямых, каждой из которых соответствует определен­ное значение Z.

Вектор С = (с₁; с₂) с координатами с₁ и с₂ перпендикулярный к этим прямым, указывает направление наискорейшего возраста­ния Z, а противоположный вектор — направление убывания Z.

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (8.35) — (8.36) и семей­ство параллельных прямых (8.34), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z= const, и которая соответствует наибольшему значению параметра Z.

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

Для определения данной вершины построим линию уровня Z =c₁x₁+ c₂x₂= 0, проходящую через начало координат и перпен­дикулярную вектору , и будем передвигать ее в направ­лении вектора до тех пор, пока она не коснется послед­ней крайней (угловой) точки многоугольника решений. Коорди­наты указанной точки и определяют оптимальный план данной задачи.

Заканчивая рассмотрение геометрической интерпретации зада­чи (7.34) — (8.36), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 8.1 — 8.4. Рис. 8.1 харак­теризует такой случай, когда целевая функция принимает макси­мальное значение в единственной точке А. Из рис. 8.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ.

На рис. 8.3 изображен случай, когда максимум недостижим, а на рис. 8.4 — случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уров­ня Z передвигается не в направлении вектора , а в про­тивоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минималь­ного значения.

Для практического решения задачи линейного программирования (8.34) — (8.36) на основе ее геометрической интерпретации необходи­мо следующее.

2. Построить прямые, уравнения которых получаются в резуль­тате замены в ограничениях (8.35)—(8.36) знаков неравенств на знаки равенств.

3. Найти полуплоскости, определяемые каждым из ограниче­ний задачи.

• Определить многоугольник решений.

• Построить вектор .

2. Построить прямую , проходящую через на­чало координат и перпендикулярную вектору .

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

4. Определить координаты точки максимума функции и вычис­лить значение целевой функции в этой точке.

Пример 8.10. Рассмотрим решение задачи об ассортименте про­дукции (пример 8.2) геометрическим способом.

Решение

Построим многоугольник решений (рис. 8.5). Для этого в системе координат на плоскости изобразим граничные прямые:

Взяв какую-либо точку, например начало координат, устано­вим, какую полуплоскость определяет соответствующее неравенст­во. Полуплоскости, определяемые неравенствами, на рис. 8.5 пока­заны стрелками. Областью решений является многоугольник OABCD.

Для построения прямой строим вектор-гради­ент = (3;4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемешаем параллельно самой себе в направлении вектора . Из рис. 7.5 следует, что по отноше­нию к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L₁ и L₃. Для определения ее коорди­нат решим систему уравнений:

Оптимальный план задачи x₁= 2,4; х₂=1,4. Подставляя значе­ния x₁ и х₂ в линейную функцию, получим:

Полученное решение означает, что объем производства продук­ции П₁ должен быть равен 2,4 ед., а продукции П₂ - 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д. е.

Геометрическим способом можно также решать задачи линей­ного программирования с числом переменных более двух. Для это­го исходную задачу преобразуют методом Жордана—Гаусса.

Пример 8.11.

Используя метод Жордана – Гаусса, произведем два полных исключения х₁ и х₄:

В результате приходим к системе

откуда

Подставляя эти значения в линейную функцию Z и отбрасывая в последней системе базисные переменные, получим задачу, выраженную только через свободные неизвестные х₂ и х₃. Найдем максимальное значение линейной функции

Z = 5.9-5.9x₃-1.5x₂

при следующих ограничениях:

.

Построим многоугольник решений и линейную функцию в системе координат Х₂0Х₃ (рис. 8.6). Согласно рис. 8.6, линейная функция принимает максимальное значение в точке А, которая лежит, на пересечении прямых L₂ и Х₂ = 0. Ее координаты (0;0,23).

Максимальное значение функции

Для отыскания оптимального плана исходной задачи подстав­ляем в преобразованную систему х₂ и х₃. Окончательно получаем Х= (1,078; 0; 0,23; 0,001).