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

Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 1937 году.

Описание

Переход от одной вершины к другой

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

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

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

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

Алгоритм симплекс-метода

Усиленная постановка задачи

Рассмотрим следующую задачу линейного программирования:

$c^Tx \to max, Ax\leqslant b, x\geqslant 0.$

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

$\begin{bmatrix} 1 & -c^T & 0\\ 0 & A & F\end{bmatrix} \begin{bmatrix} Z\\ x\\ x_s \end{bmatrix}= \begin{bmatrix} 0\\ b \end{bmatrix}, x,x_s\geqslant 0$

Здесь x — переменные из исходного линейного функционала, x_s — новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c — коэффициенты исходного линейного функционала, Z — переменная, которую необходимо максимизировать. Полупространства $x\geqslant 0$ и $x_s\geqslant 0$ в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно : $\mathbf{x}_{s i}=\mathbf{b}_i$.

Алгоритм

Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:

$\begin{bmatrix} 1 & c_B^TB^{-1}A - c^T & c_B^TB^{-1}\\ 0 & B^{-1}A & B^{-1} \end{bmatrix} \begin{bmatrix} Z\\ x\\ x_s \end{bmatrix}= \begin{bmatrix} c^T_BB^{-1}b\\ B^{-1}b \end{bmatrix},$

где c_B — коэффициенты вектора c соответствующие простым переменным (переменным x_s соответствуют 0), B — столбцы $[\mathbf{A}\mathbf{E}]$, соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг.

Выбираем начальное допустимое значение, как указано выше. На первом шаге B — единичная матрица, так как простыми переменными являются x_s. c_B — нулевой вектор по тем же причинам.

Второй шаг

Покажем, что в выражении $(c^T_BB^{-1}A - c^T)x+(c_B^TB^{-1})x_s$ только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+x_s=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ' — простые, а x ' ' — непростые переменные на данной итерации. Уравнение Ax+x_s=b можно переписать, как Bx '+Dx ' '=b. Умножим его на $B^{-1}$ слева: $x'+B^{-1}Dx''=B^{-1}b$. Таким образом мы выразили простые переменные через непростые, и в выражении $B^{-1}Ax+B^{-1}x_s$, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству $Z-c^Tx=0$ равенство $c^T_BB^{-1}Ax+c_B^TB^{-1}x_s$, то в полученном равенстве все простые переменные будут иметь нулевой коэффициент — все простые переменные вида x сократятся, а простые переменные вида x_s не войдут в выражение $c_B^TB^{-1}x_s$.

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

$(c^T_BB^{-1}A - c^T)x+(c_B^TB^{-1})x_s$.

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

Третий шаг

Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

$\begin{bmatrix} B^{-1}A B^{-1} \end{bmatrix} \begin{bmatrix} x\\ x_s \end{bmatrix}=B^{-1}b$

При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами — входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор c_B в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу. x''

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

Двухфазный симплекс-метод

Причины использования

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

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

Модификация ограничений

Все ограничения задачи модифицируются согласно следующим правилам:

• ограничения типа «≤» переводятся на равенства созданием дополнительной переменной с коэффициентом «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис.
• ограничения типа «≥» дополняются одной переменной с коэффициентом «−1». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1».
• ограничения типа «=» дополняются одной вспомогательной переменной.

Соответственно, будет создано некоторое количество дополнительных и вспомогательных переменных. В исходный базис выбираются дополнительные переменные с коэффициентом «+1» и все вспомогательные. Осторожно: решение, которому соответствует этот базис, не является допустимым.

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

Несмотря на то, что и дополнительные, и вспомогательные переменные создаются искусственно и используются для создания исходного базиса, их значения в решении сильно отличаются:

• дополнительные переменные сообщают, насколько соответствующее им ограничение «недоиспользовано». Значение дополнительной переменной, равное нулю, соответствует равенству значений правых и левых частей ограничения.
• вспомогательные переменные сообщают, насколько данное условие далеко от допустимого (относительно конкретного ограничения). Если значение вспомогательной переменной больше нуля, то данное решение не выполняет определённое ограничение, а значит не является допустимым.

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

Фазы решения

После того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как y_i, i∈{1, .., k}, то вспомогательную функцию определим, как

$z' = \sum_{i=1}^k y_i \to min$.

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

Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:

• оптимальное значение $z'$ больше нуля. Это значит, что как минимум одна из вспомогательных переменных осталась в базисе. В таком случае можно сделать вывод, что допустимых решений данной задачи линейного программирования не существует.
• оптимальное значение $z'$ равно нулю. Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым.

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

Модифицированный симплекс-метод

В модифицированном методе матрица

$\begin{bmatrix} 1 & c_B^TB^{-1}A - c^T & c_B^TB^{-1}\\ 0 & B^{-1}A & B^{-1} \end{bmatrix}$

не пересчитывается, хранится и пересчитывается только матрица $B^{-1}$. В остальном алгоритм похож на вышеописанный.

1. Вычисляем двойственные переменные $d = c_B^TB^{-1}$

2. Проверка оптимальности. $c^T_BB^{-1}A - c^T$ преобразуется в $d^TA - c^T$.

Проверка заключается в вычислении $d^TA_n - c_n$ для всех столбцов $n \in N$. Столбец со значением < 0 можно вводить вводить в базис.

Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.

Чаще выбирают значение, меньшее некоторого заданного значения $-\varepsilon$

Если такого столбца не обнаружится, за $\varepsilon$ принимается максимальное найденное абсолютное значение и соответствующий столбец $A_J$ вводится в базис.

3. Определение выводимого.

Пусть $A_J$ - вводимый столбец, соответствующий переменной $x_J$ Базиный план - это решение системы $A_B p = b$ Увеличиваем $A_B p + \vartheta A_J = b$.

Умножим слева на $B^{-1}$, т.е. $B^{-1}A_B p + \vartheta B^{-1} A_J = B^{-1}b$.

Здесь $B^{-1} b$ - базисный план, $q = B^{-1} A_J$ - разложение вводимого столбца по базису.

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

4. Пересчет опорного(базисного) плана.

Вычисляем новый опорный план по уже приведенной формуле $x = p + \vartheta B^{-1} A_J$ с найденным значением $\vartheta$.

5. Пересчитываем обратную к базисной $B^{-1}$.

Пусть $B^{-1} A_F$ - выводимый столбец.

Матрица B представима в виде $[B_G A_F]$

где $B_G$ - базисная матрица без выводимого столбца.

После замены столбца базисная матрица будет иметь вид $[B_G A_J]$

Нам нужно найти матрицу $B_1$, такую что

$[B_G , A_J] B_1^{-1} = E$ => $[B^{-1}B_G B_1^{-1} , B^{-1}A_J] = B^{-1}$ => $[B^{-1}B_G , q]B_1^{-1} = B^{-1}$ =>

$\begin{bmatrix} E & q' \\ 0 & q_f \end{bmatrix} B_1^{-1} = B^{-1}$

Откуда $B_1^{-1} = \begin{bmatrix} E & -q'/q_f \\ 0 & 1/q_f \end{bmatrix} B^{-1}$

Замечание.

При пересчете матрицы $B^{-1}$ накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется "повторением".

Мультипликативный вариант симплекс-метода

В мультипликативном варианте матрица $B^{-1}$ не хранится, хранятся лишь множители $\begin{bmatrix} E & -q'/q_f \\ 0 & 1/q_f \end{bmatrix}$

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

Другие варианты симплекс-метода

Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.

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

Метод основан на том, что базисная матрица может быть представлена в виде

$\begin{bmatrix} A_B & 0 \\ A_E & E \end{bmatrix}$

Обратная к ней имеет вид

$\begin{bmatrix} A_B^{-1} & 0 \\ -A_B^{-1}A_E & E \end{bmatrix}$

При относительно небольших размерах матрицы $A_B^{-1}$ остальная часть матрицы может не храниться.

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

Двойственный симплекс-метод

Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:

$g = \sum_{i=1}^n b_i y_i \to max$

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

$\sum_{i=1}^n a_{ij} y_i <= c_j$.

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

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

Вычислительная эффективность

Симплекс-метод удивительно эффективен на практике, но в 1972 Кли и Минти ^[1] привели пример, в котором симплекс-метод перебирал все вершины симплекса, что показывает экспоненциальную сходимость метода в худшем случае. С тех пор для каждого варианта метода был найден пример, на котором метод вел себя исключительно плохо.

Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности.

Симплекс-метод имеет среднюю полиномиальную сходимость при широком выборе распределения значений в случайных матрицах.^[2][3]

Вычислительная эффективность оценивается обычно при помощи двух параметров:

1) Числа итераций, необходимого для получения решения;

2) Затрат машинного времени.

В результате численных экспериментов получены результаты:

1) Число итераций при решении задач линейного программирования в стандартной форме с $M$ ограничениями и $N$ переменными заключено между $M$ и $3M$. Среднее число итераций $2M$. Верхняя граница числа итераций равна $2M+N$.

2) Требуемое машинное время пропорционально $M^3$.

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

Примечания

1. ↑ How good is the simplex algorithm? // Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin). — New York-London: Academic Press, 1972. — P. 159–175.
2. ↑ Ошибка в сносках^?: Неверный тег <ref>; для сносок Schrijver не указан текст
3. ↑ The simplex algorithm takes on average D steps for a cube. Шаблон:Harvtxt: Borgwardt Karl-Heinz The simplex method: A probabilistic analysis. — Berlin: Springer-Verlag, 1987. — Vol. 1. — P. xii+268. — ISBN 3-540-17096-0

Литература

• Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8
• Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9
• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4

Ссылки

• Краткое описание симплекс-метода на сайте Института дистанционного обучения ИНТУИТ

Для улучшения этой статьи желательно?: Проставив сноски, внести более точные указания на источники. Викифицировать статью.