И ее следствия

Основная теорема теории линейного программирования

Пример применения признака оптимальности в развернутой форме

Пример применения признака оптимальности в развернутой форме

Проверить вектор на оптимальность в следующей задаче ЛП: Максимизировать при условиях:

еaijyi + cj, = 0, если хj >0 для jОJ2, iI – условие г)   Запишем условие г) признака оптимальности: ( т.к. , следовательно, в первом и третьем ограничении условия 20 двойственной задачи достигается равенство)

Проверить вектор на оптимальность в следующей задаче ЛП: Максимизировать при условиях:

д) отсутствует, т.к. ни одно ограничение 20 основной задачи не выполняется как строгое неравенство. Из условия г) находим . Найден вектор . Проверяем его допустимость в двойственной задаче, т.е. выясняем, выполняются ли условия I0 и 20 двойственной задачи. Т.к. все условия выполняются, вектор yявляется оптимальным в двойственной задаче, а векторх=(1, 0, 1, 0)- оптимальным в основной задаче.

Для разрешимости задачи математического программирования (как и в любой оптимизационной задачи) необходимо, чтобы множество допустимых решений было не пусто, и целевая функция на этом множестве была ограничена сверху (если задача на максимум), либо снизу (если задача на минимум).

Теорема двойственности. Каковы бы ни были исходные данные, для задач 1 и 1* имеет место один из следующих взаимоисключающих случаев.

1. В задачах 1 и 1* имеются оптимальные векторы х и у и , т.е. обе задачи разрешимы.

2. В задаче 1 существуют допустимые векторы х из некоторого множества Х, но линейная функция на множестве этих векторов не ограничена сверху, т.е., тогда в задаче 1* нет допустимых векторов.

3. В задаче 1* существуют допустимые векторы , но функция не ограничена снизу на множестве этих векторов, т.е. , тогда в задаче 1 нет допустимых векторов.

4. В задачах 1 и 1* нет допустимых векторов, то есть