Решение и постоптимальный анализ задачи линейного программирования

Теорема (фундаментальная). Если ЗЛП имеет оптимальное решение (в ограниченной области всегда, а в неограниченной - в зависимости от ограниченности целевой функции Z), то оно совпадает, по крайней мере, с одним из допустимых базисных решений (ДБР) системы ограничений.

Согласно фундаментальной теореме вместо исследования бесконечного множества допустимых решений, необходимо исследовать лишь конечное число ДБР. Таким образом, принципиальная схема решения ЗЛП такова:

найти все ДБР;

вычислить для каждого из них соответствующее значение ЦФ z;

сравнить и определить наилучшее.

Но, в общем случае при больших значениях п и т количество ДБР может быть огромным (порядка С пт) и практическое осуществление перебора всех ДБР станет невозможным. Эти трудности обусловлены тем, что указанная принципиальная схема связана с беспорядочным перебором ДБР, без учета, насколько новое проверяемое ДБР изменяет ЦФ z и приближает ли оно нас к искомому оптимуму. Если же указанный перебор ДБР производить целеустремленно, добиваясь на каждом шаге монотонного изменения ЦФ z, т.е. чтобы каждое следующее ДБР было лучше предыдущего (или по крайней мере не хуже), то число анализируемых ДБР можно резко сократить.

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

> способ определения исходного ДБР;

> правило перехода к следующему "лучшему" ДБР;

> критерий, по которому можно определить оптимальность найденного решения или необходимость его дальнейшего улучшения.