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

(3.4)

(3.5)

не ограничен в знаке, (3.6)

Двойственная ЗЛП строится по следующим правилам:

1. Каждому ограничению исходной задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи равно числу ограничений исходной задачи.

2. Каждой переменной исходной задачи соответствует ограничение двойственной задачи, т.е. число ограничений двойственной задачи равно числу переменных исходной задачи.

3. Матрица функциональных ограничений двойственной задачи получается путём транспонирования матрицы функциональных ограничений исходной задачи.

4. Вектор целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а вектор правой части прямой задачи – вектором целевой функции двойственной задачи.

5. Целевая функция исходной задачи максимизируется, целевая функция двойственной задачи минимизируется, а ограничения имеют вид больше либо равно.

Итак:

Исходная задача	Двойственная задача
max P =   - множество планов ИЗ	Q = – не ограничен в знаке - множество планов ДЗ	(3.7)

Пример 3.1. Пусть исходная задача имеет вид:

min

(3.8)

Приведем ее к каноническому виду, т.е. будем максимизировать функцию .

(3.9)

По определению, задачей двойственной к (3.9), будет задача:

, не ограничен в знаке

(3.10)

Если обозначить через

, то (3.10) примет вид:

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

(3.11)

Из примера 3.1 следует, что если функция ИЗ минимизируется, то функция ДЗ максимизируется и ограничения меняют знак на противоположный (меньше либо равно).

Пример 3.2. Пусть ИЗ записана в виде основной ЗЛП:

(3.12)

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

(3.13)

Тогда ДЗ к основной ЗЛП будет иметь вид:

.

(3.14)

Пара задач (3.12), (3.14) называется симметричной парой двойственных задач.