Алгоритм обычного симплекс метода

 

Обычный симплекс-метод можно применять только тогда, когда дополнительные переменные, введенные в задачу при переходе к канонической форме могут сформировать начальное допустимое базисное решение. Это возможно только в том случае, когда во всех ограничениях задачи в канонической форме есть дополнительные переменные с коэффициентом 1. Другими словами обычный симплекс-метод применим, только если все ограничения исходной задачи (до перехода к канонической форме) были неравенства вида ≤.

Переменные входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми – в остальные, называются базисными. Значения базисных переменных образуют базисное решение.

Симплекс метод работает с так называемой симплекс-таблицей. Симплекс-таблица имеет следующую структуру:

 

 

Первый столбец симплекс-таблицы содержит все базисные переменные. – это базисная переменная в первом ограничении, – во втором, и так далее. Далее идут столбцы, содержащие коэффициенты при каждой из переменных в ограничениях и целевой функции. Последний столбец – столбец значений. В нем записываются правые части ограничений.

Первая строка симплекс таблицы чисто информативная. В ней записаны заголовки столбцов. Вторая строка – это z -строка. В ней записаны коэффициенты при переменных в целевой функции.

 

Алгоритм симплекс-метода

 

1. Задача линейного программирования записывается в канонической форме.

2. Определяется начальное допустимое базисное решение.

3. Определяется вводимая переменная (ведущий столбец). Вводимой переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая наименьший отрицательный (наибольший положительный) коэффициент в z -строке. Если в z -строке есть несколько таких коэффициентов, то выбор вводимой переменной делается произвольно. Оптимальное решение достигнуто тогда, когда в z -строке все коэффициенты при небазисных переменных будут неотрицательными (неположительными).

4. Определяется выводимая переменная (ведущая строка). Как в задаче максимизации, так и в задаче минимизации в качестве исключаемой выбирается базисная переменная, для которой положительное отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если таких базисных переменных несколько, то выбор исключаемой переменной выполняется произвольно. Таким образом после выполнения этого шага выбраны ведущая строки и столбец. Элемент расположенный на их пересечении называется ведущим.

5. Вычисляется новое базисное решение методом Гаусса–Жордана. Пересчет симплекс-таблицы выполняется в 3 этапа:

– все элементы ведущего столбца принимают значение 0. Ведущий элемент – значение 1;

– все элементы ведущей строки делятся на ведущий элемент;

– все остальные элементы вычисляются по следующей формуле: модифицированный элемент = элемент минус коэффициент в ведущем столбце умноженный на модифицированный коэффициент в ведущей строке.

6. Переход к шагу 3.