Решение двойственных задач

Теория двойственности находит широкое практическое применение. Сформулированные теоремы двойственности позволяют получить решение одной задачи, процесс решения которой по той или иной причине затруднителен, по оптимальному решению двойственной к ней. К такой причине относится значительное превышение числа ограничений над числом переменных задачи, так как объем вычислений при решении задач линейного программирования симплекс-методом определяется, в основном, числом ограничений. Также при необходимости решения задачи с ограничениями вида «> =» можно перейти к решению двойственной, которая будет иметь ограничения вида «< =», что позволяет избежать ввода искусственных переменных.

Рассмотрим процесс получения решения двойственной задачи на основании оптимального решения исходной. Подставим в ограничения исходной задачи значения переменных x₁^* = 2, x₂^* = 4 в оптимальном плане:

6*2 +6*4 < = 36

4*2 + 8*4 < = 40

4*2 + 2*4< = 20

На основании второй основной теоремы двойственности переменная двойственной задачи y₂, соответствующая второму ограничению исходной, которое обратилось при подстановки оптимального плана в строгое неравенство, равна нулю (y₂^* = 0).

Поскольку переменные x₁, x₂ в оптимальном плане имеют положительные значения, то соответствующие им ограничения двойственной задачи при подстановке в них ее оптимального плана обращаются в равенство. Учитывая, что y₂^* = 0, получим

6y₁ + 4y₃ = 12,

6y₁ + 8y₃ = 15.

Решив полученную систему двух линейных уравнений с двумя переменными, найдем оптимальный план двойственной задачи: y₁^* = 3/2, y₂^* = 0, y₃^* = ¾. Согласно первой основной теореме двойственности f_max = z_min = 84.

Контрольные вопросы и упражнения

1. Какая задача называется двойственной?

2. Сформулируйте правило построения двойственной задачи.

3. В чем отличие симметричных задач двойственной пары от несимметричных?

4. Как по решению исходной задачи можно найти решение двойственной?

5. Постройте задачи, двойственные к данным:

а) f = x₁ – 2x₂ + 3x₃ – x_i → max;

2x1 – x2 + 2x3 – 3x4 ≤ 5,

x1 + 2x2 – x3 + x4 ≤ 3,

__

x_j ≥ 0 (j = 1, 4);

б) f = 3x₂ – x₄ → max;

x₁ - 2x₂ + x₄ = 8,

x₂ + x₃ – 3x₄ = 6,

__

x_j ≥ 0 (j = 1, 4);

в) f = 5x₁ + x₂ → max;

x₁ – x₂ ≤ 2,

x₁ – 3x₂ ≤ 3,

x₁ ≥ 0, x₂ ≤ 0;

г) f = x₁ – 2x₂ → min;

x₁ – x₂ ≥ 5,

-x₁ + x₂ ≥ 1,

x₁ ≥ 0, x₂ ≥ 0.