ПРАВИЛА СОСТАВЛЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ
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'.