ДОКАЗАТЕЛЬСТВО. Т.к. любая задача сводится к каноническому виду, достаточно рассмотреть лишь ее и двойственную к ней. I) II)

Т.к. любая задача сводится к каноническому виду, достаточно рассмотреть лишь ее и двойственную к ней.

I)

II)

1-2) Достаточно показать, что из разрешимости I вытекает разрешимость II (т.к. пара взаимодвойственная)

Предположим, что задача I разрешима. Следовательно существует оптимальное опорное решение

Рассмотрим

Покажем, – оптимальное решение двойственной задачи. Убедимся, что это допустимое решение:

В качестве столбцов единичный вектор (?)

В векторной форме

Получили новую формулу для относительных оценок

– допустимое решение задачи II, т.к. . Теперь покажем, что это опорное решение. Воспользуемся леммой 3:

Из леммы 3, – оптимальное решение. Следовательно, обе задачи одновременно разрешимы и значения совпадают. Или же одновременно неразрешимы.

3) Докажем последнее утверждение.

Пусть целевая функция задачи I не ограничена сверху, т.е.

Метод от противного:

Тогда

Что противоречит, что функция неограниченна сверху. ¤

Поиск по сайту: