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

Двойственность в линейном программировании [duality in linear programming] — принцип, заключающийся в том, что для каждой задачи линейного программирования путем замены некоторых ее элементов на двойственные можно сформулировать двойственную задачу (см.)

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

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

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

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

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