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

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

f = 12x₁ + 15x₂  max

x₁ + x₂ ≤ 6

2x₁ + x₂ ≤ 10

x₁ + 2x₂ ≤ 10

x_1,2 ≥ 0

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

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

x₁ + x₂ ≤ 6.

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

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

х₁ = 0 х₁ = 6

х₂ = 6 х₂ = 0

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

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

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

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

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

х₂

С

f ^* (3)

х₁

f (2) (1)

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

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

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

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

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

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

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

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

Глава 3 Построение и решение двойственной задачи

Модель прямой задачи имеет вид:

f = 12x₁ + 15x₂  max

x₁ + x₂ ≤ 6

2x₁ + x₂ ≤ 10

x₁ + 2x₂ ≤ 10

x_1,2 ≥ 0

Двойственная пара задач будет симметричной, так как все условия имеют вид неравенств и все переменные ограничены по знаку.

Каждому условию прямой задачи ставим в соответствие двойственную переменную и построим двойственную задачу:

f = 6y₁ + 10y₂ + 10y₃  min

y₁ + 2y₂ + y₃  12

y₁ + y₂ + 2y₃  15

y_i  0, i = 1, 3

Двойственная задача описывает ту ситуацию, при которой предприятие вместо выпуска продукции продает ресурсы.

Экономический смысл двойственной переменной – стоимость единицы ресурса.

Условие двойственной задачи:

1y₁ + 2y₂ + 1y₃  12,

где 1 – это количество двигателей, необходимое для производства машины,

y₁ – это стоимость одного двигателя.

Следовательно, 1y₁ – это стоимость всех двигателей, идущих на одну машину.

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

Правая часть условия – это те деньги, которые предприятие получит от продажи готовой продукции.

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

Интересы покупателя отражает критерий

f = 6y₁ + 10y₂ + 10y₃  min

где 6 – количество (запасы) двигателей,

6y₁ – стоимость всех двигателей.

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