Геометрическая интерпретация двойственных задач.

Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя геометрическую интерпретацию ЗЛП, можно легко найти решение данной меры задач. При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) планы имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто.

П р и м е р 1. Z(x)=x₁–10x₂+2x₃–x₄+7x₅  max

2x₁–x₂  1,

x₁–x₂+2x₃–x₄+x₅  4,

x₂ +x_3–x₄ = 0,

x₁ –x₃ +2x₅ 3,

x₁0, x₃0.

Р е ш е н и е. Чтобы записать задачу, двойственную к данной, приведем систему ограничений к виду

2x₁ –x₂  1,

–x₁ +x₃ –2x₅–3,

–х₁+x₂ –2x₃+x₄ –4,

х₂ + x₃ –x₄ = 0,

x₁0, x₃0.

Теперь воспользуемся определением 1 и запишем задачу, двойственную к данной: Z^*(y)=y₁-3y₂-4y₃  min,

y₁–y₂ – y₃ 1,

–y₁ + y₃+2y₄ =–10,

y₂–2y₃ +y₄  2,

–2y₂ –y₃ = 7,

y₁0, y₂0, y₃0.