Двойственность в линейном программировании

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу,

Связь между прямой и двойственной задачами устанавливается двумя теоремами.

1. “Теорема двойственности”. Если обе задачи имеют допустимые решения, то они имеют и оптимальные решения, причем значение целевых функций у них будет одинаково:

(обозначения см. в ст. “ Линейное программирование ”). Если же хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения.

2. “Признак оптимальности”. Чтобы допустимое решение x прямой задачи было оптимальным, необходимо и достаточно, чтобы нашлось такое решение двойственной задачи v, что

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

Билет 27