Симплексный метод решения ЗЛП

Аналитический метод основывается на следующих утверждениях:

1. Область допустимых решений ЗЛП является выпуклым множеством с конечным числом угловых точек, т.е. многогранником или многоугольной областью.

2. Оптимальное решение ЗЛП достигается в одной из угловых точек области допустимых решений.

3. Угловые точки области допустимых решений алгебраически представляют собой опорные планы системы ограничений (1.18) ЗЛП.

Симплексные метод решения ЗЛП – это метод последовательного улучшения плана, который позволяет за конечное число шагов либо найти оптимальный план, либо установить его отсутствие.

Симплексный метод состоит из трех основных этапов:

1. Отыскание начального опорного плана.

2. Переход от одного опорного плана к другому, значение целевой функции в котором больше, чем в предыдущем.

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

Симплекс - метод основан на следующих теоремах, которые приводятся без доказательства.

Теорема 1.2 (о существовании опорного плана)

Если линейная форма ограничена сверху на непустом множестве D, то ЗЛП разрешима, то есть существует такая точка , что .

Теорема 1.3 (признак оптимальности опорного плана)

Опорный план задачи (1.18) является оптимальным, если для всех j, выполняется , где величина

(1.21)

называется симплекс – разностью или оценкой.

Теорема 1.4 (признак отсутствия оптимального плана)

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

Теорема 1.5 (признак существования лучшего опорного плана)

Если опорный план задачи (1.18) не вырожден и для некоторых k, но среди чисел , есть хоты бы одно положительное, т.е. не все , то существует опорный план , в котором целевая функция принимает значение не меньше, чем в предыдущем плане: .