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

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

Пусть дана задача

,           (1)

,         (2)

.                     (3)

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

Пусть область допустимых решений – непустое множество, например многоугольник A ₁ A ₂ A ₃ A ₄ A ₅ (рис. 3.4).

 

Рис. 3.4. Схема поиска решения задачи
графо-аналитическим методом

 

Выберем произвольное значение целевой функции Z = Z ₀. Получим с ₁ х ₁ + с ₂ х ₂ = Z ₀. Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение Z ₀. Считая в равенстве (1) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные целевой функции по х ₁ и х ₂:

(4),        (5).

Частные производные (4) и (5) функции показывают скорость её возрастания вдоль соответствующих осей. Следовательно, с ₁ и с ₂ – скорости возрастания Z вдоль осей O х ₁ и O х ₂. Вектор с = (с ₁, с ₂) называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

.

Вектор с указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор с = (с ₁, с ₂) перпендикулярен к прямым Z = const семейства с ₁ х ₁ + с ₂ х ₂ = Z.

Из геометрической интерпретации элементов задачи вытекает общий порядок её графического решения:

1) с учетом системы ограничений строим область допустимых решений;

2) определяем вектор с = (с ₁, с ₂) наискорейшего возрастания целевой функции, т. е. вектор градиентного направления;

3) проводим произвольную линию уровня Z = Z ₀;

4) при решении задачи на максимум перемещаем линию уровня Z = Z ₀ в направлении вектора  так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке). В случае решения задачи на минимум линию уровня Z = Z ₀ перемещают в антиградиентном направленииж

5) определяем оптимальное решение х ^* = (х ₁^*, х ₂^*) и экстремальное значение целевой функции Z ^* = z (x ^*).

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

у = х ₁ + 2 х ₂ ® max,

при ограничениях на значения переменных

2 х ₁ + х ₂ £ 10, х ₁ + 3 х ₂ £ 18,  х ₁ ³ 0,   х ₂ ³ 0.

Для формирования области допустимых решений ОДР необходимо в системе координат х ₁O х ₂ построить линии, соответствующие ограничениям, приравнивая их левые и правые части, и определить направления расположения допустимых значений искомых переменных в соответствии со знаками неравенств (рис. 3.5).

Вычисления для построения первых двух ограничений:

2 х ₁ + х ₂ £ 10 ® 2 х ₁ + х ₂ = 10 Þ х ₂ = 10 – 2 х ₁;

х ₁ + 3 х ₂ £ 18 ® х ₁ + 3 х ₂ = 18 Þ х₂ = (18 – х₁) / 3;

 

Рис. 3.5. Область допустимых решений задачи

 

В соответствии с третьим ограничением значения переменной х ₁ должны находиться выше оси Ох ₂, а в соответствии с четвертым ограничением значения переменной х ₂ должны находиться правее оси Ох ₁. Следует иметь в виду, что границы ОДР в область допустимых решений входят.

Для окончательного определения оптимальных значений переменных х ₁ и х ₂ необходимо сначала построить произвольную прямую для целевой функции, приравняв её выражение к любому числу, так, чтобы эта прямая располагалась в пределах выбранного масштаба рисунка. Приравняем выражение целевой функции, например, к числу «16» и построим соответствующую прямую линию.

у = х ₁ + 2 х ₂ ® max; х ₁ + 2 х ₂ = 16 Þ х₂ = (16 – х₁) / 2;

После этого необходимо построить прямую линию, параллельную данной прямой, так, чтобы она коснулась границы ОДР. Координаты точки касания этой прямой с границей ОДР будут оптимальными значениями переменных х _1опт и х _2опт.

Для точного определения координат точки касания линии целевой функции границы ОДР необходимо решить систему, включающую в себя два уравнения: 2 х ₁ + х ₂ = 10 и х ₁ + 3 х ₂ = 18. При этом максимальное значение целевой функции у _max = х ₁ + 2 х ₂ = 2,4 + 2 × 5,2 = 12,8.