СИМПЛЕКС-МЕТОД
— метод решения задачи линейного программирования, в котором осуществляется направленное движение по опорным планам до нахождения оптимального решения: С.-м. наз. еще методом последовательного улучшения плана.
Пусть невырожденная задача программирования линейнозо представлена в каноническом виде
где
вектор переменных,
— заданные векторы, Т — знак транспонирования,
отличные от нуля компоненты опорного плана, расположенные для простоты изложения на первых
местах вектора
базис этого плана. Тогда
где
значение линейной формы на данном плане. Т. к. вектор-столбцы матрицы А линейно независимы, любой из векторов условий
имеет по ним единственное разложение:
где
коэфф. разложения. Система условий
при заданном к определяет в пространстве переменных задачи луч, исходящий из точки, которая соответствует рассматриваемому опорному плану. Пусть значение переменной
при движении по этому лучу равно 0, тогда значение базисных переменных равны
. В этих обозначениях ур-ние (5) представимо в виде
Умножив ур-ние (3) на 0 при
и вычтя из ур-ния (1), получим
Из ур-ний (7—8) получаем
Т. к. (0) при
определяют план задачи, то наибольшее 0, не нарушающее ограничений
определяется из условия
где
.
В силу невырожденности задачи минимум достигается не больше, чем для одного
Значение линейной формы при
определяется из ур-ний (9), (4), (2)
где
. Очевидно,
для
т.
Пусть
начальный базис из
единичных векторов. Все данные задачи записываются в виде симплекс-таблицы (первой итерации вычислительного процесса). Симплекс-алгоритм решения задачи линейного программирования составляется из выполнения следующих операций: 1) найти
.
Если
рассматриваемый план оптимален; если
вектор А к вводится в базис; 2) найти
для которого
из формулы (10). Если
пустое мн-во, линейная форма неограничена сверху; если
Симплекс-алгоритм (первая итерация вычислительного процесса)
(табл. см. скан)
, вектор
выводится из базиса; 3) по найденным I, к вычислить новые значения элементов таблицы по формулам
где
и перейти к выполнению операции (1) с новыми значениями всех
Преобразование (12) заменяет вектор коэфф.
на единичный вектор
. В силу монотонного увеличения
возврат к уже однажды пройденному плану невозможен, а из конечности числа опорных планов следует конечность алгоритма. Начальный опорный план с единичным базисом можно получить, решив описанным алгоритмом вспомогательную задачу
при ограничениях
которая содержит единичный базис, состоящий из векторов
Этим векторам соответствуют искусственные переменные со значениями
. Если в оптим. решении этой задачи
исходная задача не имеет решения. Если же
и задача невырождена, оптим. базис состоит только из векторов исходной задачи, крторые по формулам (12) преобразованы в единичную матрицу. Если задача обладает вырожденными планами, значение
может не увеличиваться на ряде итераций. Это происходит из-за того, что значение соответствующих равно нулю и определяется неоднозначно. В таких случаях монотонность метода нарушается и может произойти зацикливание, т. е. возврат к уже пройденному базису. Небольшое изменение вектора ограничений задачи, которое заключается в замене величин на
где достаточно малы, при подходящем выборе не изменяет множества векторов оптим. опорного плана исходной задачи и делает ее невырожденной.
Описанный выше алгоритм наз. первым (или прямым) алгоритмом
Широко известен также второй алгоритм (алгоритм с обратной матрицей). В нем преобразовывается лишь матрица
обратная базисной матрице.
Лит. см. к
Программирование линейное.
В. А. Трубин.