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

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ [duality in linear programming] — принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу, Связь между прямой и двойственной задачами устанавливается двумя теоремами. 1. “Теорема двойственности”. Если обе задачи имеют допустимые решения, то они имеют и оптимальные решения, причем значение целевых функций у них будет одинаково: (обозначения см. в ст. “Линейное программирование”). Если же хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения. 2. “Признак оптимальности”. Чтобы допустимое решение x прямой задачи было оптимальным, необходимо и достаточно, чтобы нашлось такое решение двойственной задачи v, что Принцип двойственности как ключ к решению широкого класса экстремальных задач распространяется также на ряд других областей математического программирования, на математическую теорию оптимальных процессов.