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

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

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

S₁ ≥ 0

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

y _1,2 не ограничены в знаке.

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

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

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

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.

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

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.

Очевидно, что задача, двойственная к двойственной, совпадает с прямой.

Дата добавления: 2014-12-29