Симплекс-метод решения задачи линейного программирования
Если же решена задача 2, то аналогичные выводы можно сделать для двойственной ей задачи 1.
При решении одной из двойственных задач симплекс-методом в тех же симплексных таблицах одновременно преобразовывается и другая задача. Если решенная задача имеет оптимальный план, который содержится в столбце свободных членов последней симплексной таблицы, то и двойственная задача имеет оптимальный план, и он содержится в индексной строке последней симплексной таблицы решенной задачи.
Справедливы следующие теоремы.
Теорема 1. Для того, чтобы план X* одной из двойственных задач был оптимальным, необходимо и достаточно, чтобы существовал план Y* другой задачи, такой что значения целевых функций для этих планов равны, то есть f(X*) = g(Y*).
Назовем парой сопряженных неравенств любые два неравенства, оказавшиеся в одной строке, при условии, что двойственные задачи записаны по вышеуказанной схеме, например,
Теорема 2. Для того, чтобы план X* одной из двойственных задач был оптимальным, необходимо и достаточно, чтобы существовал план Y* другой задачи, такой что в каждой паре сопряженных неравенств строгому неравенству соответствовало бы равенство, то есть хотя бы одно из пары сопряженных неравенств должно выполняться как равенство.