Основная идея и алгоритм симплексного метода

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

Пусть задача записана в канонической форме:

max; (11)

(i = ); (12)

(j = ). (13)

Известно, что если задача (11) -(13) разрешима, то ее оптимальный план совпадает по крайней мере с одним из опорных решений (планов) системы уравнений (12). Именно этот опорный план отыскивается симплекс-методом в результате упорядоченного перебора опорных планов. Применительно к задаче (11) -(13) упорядоченность понимается в том смысле, что при переходе от одного опорного плана к другому соответствующие им значения целевой функции (11) возрастают (не убывают). Поэтому симплекс-метод называют методом последовательного улучшения плана. Поскольку общее число опорных планов не превышает то через конечное число шагов будет либо найден оптимальный опорный план, либо установлена неразрешимость задачи.

Решение задачи (11) -(13) складывается из двух этапов: на первом находят какой-либо начальный опорный план на втором - по специальным правилам переходят от начального плана к другому, более близкому к оптимальному, опорному плану затем к следующему и так до тех пор, пока задача не будет решена.

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

Нахождение начального опорного плана. В примере 2 было подробно рассмотрено, как находится опорное решение системы линейных уравнений, так что первый этап нам в сущности знаком.

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

Таблица 14.

		...
0=		...
...	...	............
0=		...
Z =		...

Итак, для нахождения начального опорного плана задачи (11) -(13) можно предложить следующий алгоритм:

1) записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство (). Те уравнения системы, в которых свободные члены отрицательны, предварительно умножаются на (-1). Таблицу называют симплексной;

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

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

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

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

Таблица 15.

		...
		...
...	...	.........
=		...
Z =		...

Чтобы выписать из таблицы 15 компоненты опорного плана нужно положить равными нулю свободные переменные, тогда базисные переменные будут равны соответствующим свободным членам: ,..., = , =0, =0 или =(,..., , 0,..., 0). Отвечающее опорному плану значение функции Z равно свободному члену , т.е. _.

В некоторых случаях построение начального опорного плана значительно упрощается. Рассмотрим эти случаи.