Поняття двоїстої задачі

Нехай є наступна задача лінійного програмування, її будемо називати прямою:

Задача 1.

Легко бачити, що до такого вигляду можна привести будь-яку ЗЛП. Двоїста задача для задачі 1 записуються так:

Задача 2.

Можна показати, що має місце принцип взаємної двоїстості: двоїстою до задачі 2 є задача 1. Таким чином, несуттєво, яку із задач 1 або 2 називати прямою, а яку двоїстою.

Приклад 1. Дана ЗЛП

Побудувати двоїсту задачу.

Задачу потрібно привести до вигляду, в якому записана задача 1. Всі обмеження, крім вимог невід’ємності змінних, повинні бути нерівностями вигляду ≤. Першу нерівність помножимо на (-1). Потім замінимо рівність – x₁+x₂=2 двома нерівностями -x₁+x₂≤2 і -x₁+x₂≥2; другу із цих нерівностей помножимо на (-1). У результаті ЗЛП прийме вигляд:

Тепер запишемо двоїсту задачу. Кожному лінійному обмеженню (крім вимог невід’ємності змінних) поставимо у відповідність змінну двоїстої задачі. Потім, рухаючись уздовж стовпців, запишемо цільову функцію й обмеження двоїстої задачі. Одержимо:

Дата добавления: 2014-01-07