Лекция: Основная теорема двойственности
Если одна из двойственных задач имеет оптимальное решение, то вторая задача также имеет оптимальное решение, причем экстремальные значения целевых функций на этих решениях совпадают:
.
Если же одна из задач неразрешима из-за неограниченности целевой функции ( или ), то допустимое множество решений второй задачи пусто.
Из двух задач (1.8) и (1.9) первая решается симплекс-методом обычно легче.
Если в (1.8) все, то, приводя исходную задачу к основной форме, получим следующую систему ограничений:
Тем самым, сразу становится известен первый опорный план:
и, соответственно, первая симплекс-таблица:
| Базис | x1 | … | xn | xn+1 | … | xn+m | bi |
| xn+1 | a11 | … | a1n | … | b1 | ||
| … | … | … | … | … | … | … | … |
| xn+m | am1 | … | amn | … | bm | ||
| -c1 | … | -cn | … |
Предположим, что данная задача имеет единственное решение. Можно показать, что последняя симплекс-таблица, по которой был рассчитан оптимальный план задачи, определяет также и оптимальный план двойственной задачи. Его компоненты находятся в правом нижнем углу этой симплекс-таблицы в столбцах, соответствующих добавленным компонентам :
| Базис | x1 | … | xn | xn+1 | … | xn+m | bi |
| … | … | … | … | … | … | … | … |
| … | … | .. | … |