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

Симплексный метод – универсальный метод решения ЗЛП. Позволяет решать задачи с любым количеством переменных и неравенств. Метод является пошаговым. На каждом шаге решение становится лучше или, по крайней мере, не хуже. В основе симплексного метода лежат три правила:

1) выбор первоначального (базисного) решения;

2) переход к более лучшему (более близкому к оптимальному) решению;

3) критерий оптимальности найденного решения.

Чтобы решить задачу симплексным методом необходимо: 1) систему неравенств привести к системе равенств с помощью введения дополнительных переменных: если знак неравенства « », то переменная вводится со знаком «-», а если « », то со знаком «+». 2) Далее все переменные делятся на две группы: основные и не основные. В качестве основных переменных на первом шаге можно взять дополнительные переменные, если их знаки соответствуют знакам свободных коэффициентов, если не соответствуют, то за основные переменные принимаются те, знаки которых совпадают. 3) После разделения переменных необходимо основные переменные через не основные и найти базисное решение (все компоненты базисного решения должны быть неотрицательными, в противном случае необходимо выбрать другую основную переменную в соответствующем уравнении). 4) Выразить целевую функцию через не основные переменные и проверить выполнение критерия оптимальности. 5) Если критерий не выполняется, то выбрать не основную переменную для перевода в основные и наоборот, для этого составляется система оценок для не основной переменной и выбирается наименьшая из оценок. 6) Повторить пункты 3) – 5).

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

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