Алгоритм применения условия оптимальности при решении задач ЛП

Дан n -мерный вектор и задача ЛП (L). С помощью условия оптимальности определить, будет ли данный вектор оптимален в задаче (L).

1) Проверяем (принадлежит ли данный вектор множеству допустимых решений задачи L) – подставить в условие задачи, проверить выполнимость ограничений.

2) Определить вид множества U – ограничения двойственной задачи

3) Написать условие дополняющей нежесткости с подстановкой . Получим систему линейных алгебраических уравнений для определения .

4) Решаем эту систему, находим .

5) Проверяем (принадлежит ли данный вектор множеству допустимых решений двойственной задачи) – подставить в условие задачи L *, проверить выполнимость ограничений.

6) Если да (принадлежит), то – оптимальный в задаче L, если нет (не принадлежит) то не оптимальный в задаче L.