Двойственный симплекс-метод решения задач ЛП

Метод, при котором вначале симплекс-методом решается одна из взаимно двойственных задач, а затем оптимум и оптимальное решение другой задачи находятся с помощью теорем двойственности, называется двойственным симплекс-методом.

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

. (5.41)

Если целевая функция исходной задачи не ограничена, то система ограничений двойственной задачи несовместна.

Примечание: утверждение, обратное по отношению ко второй части первой теоремы двойственности, в общем случае неверно.

Установим соответствие между переменными взаимно двойственных задач.

Таблица 5.12