Пример 3.3.

Прямая задача:

Прямая задача с ограничениями в канонической форме:

S₁ ≥ 0

Двойственная задача:

y _{1, 2} не ограничены в знаке.

Ограничение , т.е. , является более жестким, чем условие неограниченности у ₁ в знаке, поэтому двойственная задача может быть записана в следующем виде:

у ₂ не ограничена в знаке.

Если формулировать ДЗ к ИЗ, минуя ее приведение к КЗЛП, то на основании примера 3.3. можно сделать следующие выводы:

1. Если ограничение ИЗ является нестрогим, то соответствующая двойственная переменная ограничена в знаке;

2. Если ограничение ИЗ является строгим, то соответствующая двойственная переменная не ограничена в знаке.

Пример 3.4. Прямая задача:

min(5X₁ – 2X₂);

–X₁ + X₂ ≥ –3;

2X₁ + 3X₂ ≤ 5;

X_{1, 2} ≥ 0.

Прямая задача с ограничениями в канонической форме:

min(5X₁ – 2X₂ + 0S₁ + 0S₂);

–X₁ + X₂ – S₁ = –3;

2X₁ + 3X₂ + S₂ = 5;

Двойственная задача:

max(–3У₁ + 5У₂);

–У₁ + 2У₂ ≤ 5;

У₁ + 3У₂ ≤ –2;

–У₁ + 0У₂ ≤ 0;

0У₁ + У₂ ≤ 0.

У_{1, 2} не ограничены в знаке.

Отбрасывая избыточные ограничения, получаем:

max(–3У₁ + 5У₂);

–У₁ + 2У₂ ≤ 5;

У₁ + 3У₂ ≤ –2;

У₁ ≥ 0, У₂ ≤ 0.

Из решения примера 3.4 следует:

если в ИЗ ограничение является «неправильным» (в задаче на минимум - ≤, в задаче на максимум - ≥), то соответствующая двойственная переменная будет неположительной (У₂ ≤ 0).

Пример 3.5. ИЗ:

max(5X₁ + 6X₂);

X₁ + 2X₂ = 5;

–X₁ + 5X₂ ≥ 3;

4X₁ + 7X₂ ≤ 8.

X₁ не ограничена в знаке, X₂ ≥ 0.

ИЗ в канонической форме:

max(5 – 5 + 6X₂ + 0S₁ + 0S₂);

+ 2X₂ = 5;

+ 5X₂ – S₁ = 3;

4 + 7X₂ + S₂ = 8;

ДЗ:

min(5У₁ + 3У₂ + 8У₃);

У₁ – У₂ + 4У₃ ≥ 5;

–У₁ + У₂ – 4У₃ ≥ –5;

2У₁ + 5У₂ + 7У₃ ≥ 6;

0У₁ – У₂ + 0У₃ ≥ 0;

0У₁ + 0У₂ + У₃ ≥ 0.

У_{1, 2, 3} не ограничены в знаке.

Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У₂ и У₃ можно отбросить. В итоге получаем:

min(5У₁ + 3У₂ + 8У₃);

У₁ – У₂ + 4У₃ = 5;

2У₁ + 5У₂ + 7У₃ ≥ 6;

У₁ не ограничена в знаке;

У₂ ≤ 0, У₃ ≥ 0.

Из решения примера 3.5 следует:

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

Теорема 3.1. Задача, двойственная к двойственной, совпадает с исходной, т.е. . Доказательство очевидно.

На основании выводов, сделанных при решении примеров 3.1.-3.5., можно формулировать общие правила построения ДЗ для ИЗ, записанной в произвольной форме.

1. Если целевая функция ИЗ максимизируется, то целевая функция ДЗ минимизируется, и наоборот.

2. Если в ИЗ на максимум (минимум) i-е ограничение имеет вид ≥ (≤) («неправильное»), то в ДЗ i-я переменная будет неположительной.

3. Если i-е ограничение ИЗ имеет вид строгого равенства, то i-я переменная ДЗ будет не ограничена в знаке.