СИМПЛЕКСНЫЙ МЕТОД

Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования, записанную в каноническом виде.

Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному.

1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1–го шага, за исключением строки Δj (индексная строка), заполняем по данным системы ограничений и целевой функции.

Индексная строка для переменных находится по формуле

и по формуле

Возможны следующие случаи при решении задачи на максимум:

— если все оценки Δj ≥ 0, то найденное решение оптимальное;

— если хотя бы одна оценка Δj ≤ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как L() → , т.е. целевая функция неограничена в области допустимых решений;

— если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

— если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

Если хотя бы одна оценка Δk < 0, то k–й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (bi) к положительным коэффициентам k–гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

3. Заполняем симплексную таблицу 2–го шага:

— переписываем ключевую строку, разделив ее на ключевой элемент;

— заполняем базисные столбцы;

— остальные коэффициенты таблицы находим по правилу "прямоугольника"[1]. Оценки можно считать по приведенным выше формулам или по правилу "прямоугольника" Получаем новое опорное решение, которое проверяем на оптимальность, и т.д.

Примечание. Если целевая функция L() требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Δj при всех j = .