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

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

Графическим методом решение получают в результате последовательно выполняемых шагов, содержание которых составляют:

1) построение области допустимых решений (ОДР);

2) поиск точки ОДР, соответствующей оптимальному ре- шению;

3) определение координат этой точки.

1. Построение области допустимых решений. Область допустимых решений представляет собой часть плоскости (в многомерном случае — часть гиперпространства), все точки которой удовлетворяют всем ограничениям, имеющимся в дан- ной задаче ЛП. Условие неотрицательности переменных x1 ≥ 0, x2 ≥ 0 ограничивает область их допустимых значений первым квадрантом. Другие границы ОДР на плоскости x10 x2 изобра- жаются прямыми линиями, построенными на основе ограниче-

ний при замене в них знаков неравенства знаками равенства. Каждая линия определяет на плоскости две области: в одной из них все точки удовлетворяют заданным ограничениям, в другой — нет. Ту область, в которой выполняются ограниче- ния в виде неравенств, указывают стрелками, направленными в сторону допустимых значений переменных. Кроме того, для удобства восприятия возле каждой линии проставляют номер соответствующего ограничения.

В каждой точке ОДР, принадлежащей внутренней области или границе образовавшегося выпуклого многоугольника, все ограничения выполняются. Поэтому решения, соответствующие этим точкам, являются допустимыми. С содержательной точки зрения каждая точка ОДР представляет собой конкретную стра- тегию проведения операции u = (x1, x2), а множество всех точек ОДР — множество всех возможных стратегий U = {u}.

2. Поиск оптимальной точки ОДР. Построенная ОДР представляет собой выпуклый многоугольник. В теории линей- ного программирования доказывается, что своего оптимального значения ЦФ достигает в угловой (или экстремальной) точке выпуклого многоугольника решений. Если ЦФ задавать неко- торые фиксированные возрастающие значения W(x) = c1x1 +

+ c2x2 = const, то полученные уравнения на плоскости  опре-

2

делят семейство параллельных прямых линий. Вектор C = (c1,  c)^т, перпендикулярный этим линиям, указывает направление наискорейшего возрастания ЦФ, т. е. является вектором гра- диента ЦФ. Соответственно, направление, противоположное направлению, указываемому вектором градиента, характери- зует направление убывания ЦФ (при решении задач ее мини- мизации).

Для практического осуществления поиска оптимальной точки ОДР необходимо:

1) определить вектор градиента ЦФ ∇ W(x) = (∂W(x)/∂x1;

∂W(x)/∂x)^т = (c, c)^т. Длина вектора градиента не связана со зна-

2             1  2

чением ЦФ, поэтому достаточно указать лишь его направление;

2) построить прямую, перпендикулярную вектору гради- ента;

3) перемещая эту прямую параллельно самой себе в на- правлении вектора градиента дойти до угловой точки ОДР, где ЦФ достигает максимального допустимого значения.

3. Определение значений управляемых переменных. Ре- шение задачи ЛП составляют координаты (x1, x2) угловой точки ОДР, через которую проходит линия, соответствующая урав- нению ЦФ. Числовые значения этих переменных получают из решения системы линейных уравнений, которым на графике соответствуют пересекающиеся линии.

Пример 9.1.

Определить max W(x) = x1 + 4x2 при ограничениях: x1 + x2 ≤ 4;

− x1 + x2 ≤ 2;

x1, x2 ≥ 0.

Графическое решение задачи представлено на рис. 9.1.

Рис. 9.1. Графическое решение задачи ЛП

Решение задачи составляют:

1) значение целевой функции W(x) = 13;

2) координаты экстремальной точки u = {x1 = 1, x2 = 3}. Нахождение решения задачи ЛП на основе ее геометри-

ческой интерпретации включает следующие этапы:

1. Строят прямые, уравнения, которых получаются в ре- зультате замены в ограничениях знаков неравенств на знаки точных равенств.

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

3. Находят многоугольник решений.

4. Строят вектор С = (с1; с2).

5. Строят прямую с1x1 + c2x2 = h, проходящую через мно- гоугольник решений.

6. Передвигают прямую с1x1 + c2x2 = h в направлении век- тора С, в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность свер- ху функции на множестве планов.

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

Пример 9.2.

Для производства двух видов изделий (А и В) предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в табл. 9.1. В ней же указана прибыль от реализации одного изде- лия каждого вида и общее количество сырья данного вида, кото- рое может быть использовано предприятием.

Таблица 9.1

Вид сырья