Программирования

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

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

(8)

при ограничениях

(9)

(10)

Равенство (8) называется приведенным выражением для функции а система ограничений (9) называется приведенной к единичному базису. Переменные называются базисными, - свободными. Коэффициенты называются оценками соответствующих свободных переменных.

Запишем исходные данные в виде таблицы.

Базис	В	А1	А2	…			…
А1				…			…
А2				…			…
…	…	…	…	…	…	…	…	…
				…			…
=				…			…

Положив все свободные переменные равными нулю, найдем значения базисных переменных из системы (9): Решение является допустимым, т.к. Это

решение называется опорным решением или опорным планом задачи (8)-(10). Известно, что если задача (8)-(10) имеет решение (т.е. функция достигает максимального значения при ограничениях (8)-(10)), то это решение является ее опорным планом. Алгоритм симплексного метода заключается в том, что от данного опорного плана Х мы переходим к другому опорному плану с таким расчетом, чтобы значение увеличивалось или, по крайней мере, не уменьшалось, т.е. На каждом шаге в опорном плане одна из базисных переменных заменяется свободной При этом в таблице в столбце «базис» заменяется на Это означает, что по определенным правилам выбирается разрешающий элемент который стоит на пересечении разрешающей строки и разрешающего столбца На месте разрешающего элемента мы получаем единицу с помощью элементарной операции над - ой строкой таблицы.

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

При выборе разрешающего элемента должны выполняться следующие два условия.

1. Значение функции должно возрастать или, по крайней мере, не уменьшаться. Поэтому р выбирают таким, чтобы выполнялось неравенство Тогда, если переменная примет вместо нулевого положительное значение, то возрастет.

2. Столбец свободных членов В должен остаться неотрицательным. Условие будет выполняться при Условия будут выполняться, если либо либо и т.е.