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

1. Опорное решение – базисное решение, являющееся допустимым.

2. Оптимальное решение – опорное решение, приводящее к экстремуму целевую функцию.

ПРИНЦИП ПОИСКА ОПТИМАЛЬНОГО РЕШЕНИЯ СИМПЛЕКС – МЕТОДОМ

1. Систему ограничений приводят к виду, когда все знаки в ограничениях одинаковы.

2. Задача ЛП записывается в канонической форме.

3. Определяют любое базисное решение. Наиболее простое решение: когда основные переменные являются свободными и = 0, а дополнительные переменные являются базисными и равны правым частям СЛУ.

4. Проверяют, является ли базисное решение опорным.

5. Если не является опорным, то из базиса вычёркивают определённую переменную и вводят в базис другую (свободную).

6. Последовательной заменой находят опорное решение.

7. Проверяют опорное решение на оптимальность по определённому алгоритму.

8. Если решение не оптимальное опять проводят замену переменных: базисные на свободные.

9. В результате многократного повторения будет получено либо оптимальное решение, либо противоречивость ограничениям, либо не ограниченность целевой функции.

Такая процедура пересчёта коэффициентов в уравнениях при переходе к новому базису может быть формализована и сведена к заполнению стандартных симплексных таблиц.