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

Модель задачи имеет вид:

L = 12 x ₁+ 15 x ₂® max

x ₁ + x ₂ ≤ 6

2 x ₁ + x ₂ ≤ 10

x ₁ + 2 x ₂ ≤ 10

x _1,2 ≥ 0

Ограничения x _1,2 ≥ 0 образуют первую четверть системы координат, то есть угол х ₁0 х ₂, за пределы которого допустимое множество выходить не может.

Определим полуплоскости каждого условия. Берем первое условие:

x ₁ + x ₂ ≤ 6.

Заменяем на равенство: x ₁ + x ₂ = 6.

Чтобы построить эту прямую, подбором выбираем две точки:

х ₁ = 0 х ₁ = 6

х ₂ = 6 х ₂ = 0

Аналогично строим две другие прямые:

2 x ₁ + x ₂ ≤ 10 x ₁ + 2 x ₂ ≤ 10

2 x ₁ + x ₂ = 10 x ₁ + 2 x ₂ = 10

х ₁ = 2 х ₁ = 5 х ₁ = 0 х ₁ = 6

х ₂ = 6 х ₂ = 0 х ₂ = 5 х ₂ = 2

х ₂

С

L ^* (3)

х ₁

L (2) (1)

Рисунок 1 – Графическое решение задачи

Допустимым множеством будет выпуклый многогранник, любая точка которого удовлетворяет всем условиям задачи и может быть ее решением. Чтобы найти оптимальное решение, нужно построить линию критерия. Для этого сначала строят вектор , начало которого лежит в точке (0;0), а конец – в точке (12;15) или (4;5). Перпендикулярно этому вектору в точке (0;0) проводим прямую критерия L.

В сторону вектора критерий всегда увеличивается.

Координаты точки, через которую проходит прямая L ^* и будут оптимальными значениями х ₁ ^* и х ₂^*:

х ₁^* = 2, х ₂^* = 4.

L ^* = 12 · 2 + 15 · 4 = 84.

Таким образом, для получения максимальной стоимости продукции в размере 84 денежные единицы необходимо выпустить 2 машины и 4 мотоцикла.

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