СИМПЛЕКС-МЕТОД

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

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

где вектор переменных, — заданные векторы, Т — знак транспонирования, отличные от нуля компоненты опорного плана, расположенные для простоты изложения на первых местах вектора базис этого плана. Тогда

где значение линейной формы на данном плане. Т. к. вектор-столбцы матрицы А линейно независимы, любой из векторов условий имеет по ним единственное разложение:

где коэфф. разложения. Система условий

при заданном к определяет в пространстве переменных задачи луч, исходящий из точки, которая соответствует рассматриваемому опорному плану. Пусть значение переменной при движении по этому лучу равно 0, тогда значение базисных переменных равны . В этих обозначениях ур-ние (5) представимо в виде

Умножив ур-ние (3) на 0 при и вычтя из ур-ния (1), получим

Из ур-ний (7—8) получаем

Т. к. (0) при определяют план задачи, то наибольшее 0, не нарушающее ограничений определяется из условия

где .

В силу невырожденности задачи минимум достигается не больше, чем для одного Значение линейной формы при определяется из ур-ний (9), (4), (2)

где . Очевидно, для т.

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

Если рассматриваемый план оптимален; если вектор А к вводится в базис; 2) найти для которого из формулы (10). Если пустое мн-во, линейная форма неограничена сверху; если

Симплекс-алгоритм (первая итерация вычислительного процесса)

(табл. см. скан)

, вектор выводится из базиса; 3) по найденным I, к вычислить новые значения элементов таблицы по формулам

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

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

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

Описанный выше алгоритм наз. первым (или прямым) алгоритмом Широко известен также второй алгоритм (алгоритм с обратной матрицей). В нем преобразовывается лишь матрица обратная базисной матрице.

Лит. см. к Программирование линейное.

В. А. Трубин.