SHPORA.net :: PDA

[ Back ]

1. Каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи и, наоборот, каждому j-му ограничению двойственной задачи соответствует переменная исходной задачи.

2. Матрицы А ограничений 1 – 2 и А' ограничений 3' – 4' (см. табл. 11.1) взаимно транспонированы. Следовательно, строка коэффициентов в j-м ограничении двойственной задачи есть столбец коэффициентов при в ограничениях 1 – 2 исходной задачи, и наоборот.

3. Свободные члены ограничений одной из задач являются коэффициентами при соответствующих переменных в целевой функции другой задачи. При этом максимизация меняется на минимизацию, и наоборот.

4. В каждой задаче ограничения-неравенства следует записывать со знаком «?» при максимизации и со знаком «?» – при минимизации.

5. Каждому i-му ограничению-неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности , а равенству – переменная без ограничения на знак. Наоборот, неотрицательной переменной соответствует в двойственной задаче j-е ограничение - неравенство, а произвольной переменной – равенство.

ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования (табл. 11.1).

Таблица 11.1

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

1. 1'.

2. 2'.

3. 3'.

4. 4'.

5. 5'.