Симплекс-метод

Рассмотренный выше графический метод решения систем линейных уравнений не всегда применим. Универсальным методом решения систем линейных уравнений является симплексный метод.

Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

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

Схема симплексного метода имеет алгоритмический характер (характер четкого предписания о выполнении последовательных операций), что позволяет успешно программировать и реализовывать этот метод на ЭВМ. Задачи же с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.

Вычисления по симплекс-методу организуются в виде симплекс-таблиц, которые являются сокращенной записью ЗЛП в канонической форме.

Канонической формой ЗЛП называется задача следующего вида:

Алгоритм приведения задачи линейного программирования к каноническому виду

1. Если целевая функция стремится к максимуму, то все её коэффициенты умножаются на (-1), тогда min меняется на max.

2. Для приведения задачи к канонической форме все ограничения должны иметь вид равенств. Если ограничение имеет вид неравенства со знаком меньше либо равно ( ), то к нему добавляют дополнительную неотрицательную переменную, а из неравенства со знаком больше либо равно ( ) вычитают дополнительную переменную. В целевую функцию эти дополнительные переменные включают с коэффициентом 0, т.е. фактически они в целевой функции отсутствуют.

3. После этого знаки и меняют на знак =.

Пример приведения задачи линейного программирования к каноническому виду

Привести задачу линейного программирования к каноническому виду.

Вводим дополнительные переменные, согласно п.2 алгоритма.

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

Теперь можно сформулировать алгоритм симплекс-метода для решения задач линейного программирования, заданных в канонической форме.

Для реализации данного алгоритма необходимо построение симплекс-таблицы.

Правило построения симплекс-таблицы

1. В первой строке перечисляются все переменные задачи, как исходные ( ), так и дополнительные, введенные при приведении к канонической форме ( ).

2. В первом столбце таблицы («Базис») перечисляются переменные, составляющие начальный базис задачи. Их количество всегда равно количеству ограничений.

3. Во втором столбце указываются значения .

4. В последней строке целевой функции указываются коэффициенты целевой функции с обратным знаком. Для переменных, не входящих в целевую функцию (например, для переменных ), указываются нули.

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

Если таблица построена правильно, то в столбце каждой базисной переменной должна присутствовать только одна единица, остальные коэффициенты – нулевые.

Общий вид симплекс-таблицы