Двойственность для задач линейного программирования в симметричной форме записи. Критерии оптимальности

Двойственные задачи линейного программирования называют симметричными, если они удовлетворяют следующим свойствам:
– число переменных одной задачи равно числу ограничений другой задачи;
– в одной задаче ищется максимум целевой функции, в другой – минимум;
– коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи;
– в каждой задаче система ограничений задается в виде неравенств, причем, в задаче на отыскание максимум, все неравенства вида «≤», а в задаче на отыскание минимума, все неравенства вида «≥»;
– матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;
– условия неотрицательности переменных сохраняются в обеих задачах.

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