Пересмотренный симплексный метод

В математической оптимизации пересмотренный симплекс-метод является вариантом Джорджа Данцига для симплекс-метода линейного программирования .

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

Формулировка задачи

В оставшейся части обсуждения предполагается, что задача линейного программирования приведена к следующей стандартной форме:

{\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}

где $А € ℝ m \times n$ . Без ограничения общности предполагается, что матрица ограничений $A$ имеет полный ранг строки и что задача разрешима, т. е. существует хотя бы один $x \geq 0$ такой, что $Ax = b$ . Если $A$ имеет недостаточный ранг, то либо существуют избыточные ограничения, либо проблема неразрешима. Обе ситуации можно решить с помощью предварительного шага.

Алгоритмическое описание

Условия оптимальности

Для линейного программирования условия Каруша – Куна – Такера являются одновременно необходимыми и достаточными для оптимальности. Условия ККТ задачи линейного программирования в стандартной форме:

{\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}

где $λ$ и $s$ — множители Лагранжа , связанные с ограничениями $Ax = b$ и $x \geq 0$ соответственно. ^[2] Последнее условие, которое эквивалентно $s i x i = 0$ для всех $1 < i < n$ , называется дополнительным условием нежесткости .

Согласно тому, что иногда называют фундаментальной теоремой линейного программирования , вершина $x$ допустимого многогранника может быть идентифицирована как базис $B$ многогранника $A,$ выбранный из столбцов последнего. ^[а] Поскольку $A$ имеет полный ранг, $B$ неособа. Без ограничения общности предположим, что $A = [B N]$ . Тогда $x$ определяется выражением

{\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}

где $Икс В \geq 0$ . Раздел $c$ и $s$ соответственно на

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}

Чтобы удовлетворить дополнительному условию нежесткости, пусть $s B = 0$ . Отсюда следует, что

{\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}

что подразумевает, что

{\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}

Если $s N \geq 0$ в этой точке, условия ККТ выполняются, и, следовательно, $x$ является оптимальным.

Операция поворота

При нарушении условий ККТ сводная операция, заключающаяся во введении в базис столбца $N$ за счет существующего столбца в $B.$ выполняется В отсутствие вырождения операция поворота всегда приводит к строгому уменьшению $c Т х$ . Следовательно, если задача ограничена, пересмотренный симплексный метод должен завершиться в оптимальной вершине после повторных операций поворота, поскольку существует только конечное число вершин. ^[4]

выберите индекс $m < q \leq n$ такой, что $s q < 0$ В качестве входного индекса . Соответствующий столбец $A$ , $A q$ , будет перемещен в базис, и $x q$ будет разрешено увеличиваться с нуля. Можно показать, что

{\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},

на единицу $т. е. каждое увеличение x q$ приводит к уменьшению $-s на q$ in $c Т х$ . ^[5] С

{\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},

$x B$ необходимо соответственно уменьшить на $Δ x B = B -1 A q x q$ при условии $x B - Δ x B \geq 0$ . Пусть $d = B -1 А q$ . Если $d \leq 0$ , независимо от того, насколько $x q$ увеличивается $, x B - Δ x B$ останется неотрицательным. Следовательно, $c Т x$ можно произвольно уменьшить, и, таким образом, задача не ограничена. В противном случае выберите индекс $p = argmin 1\leq i \leq m {x i / d i | d i > 0}$ в качестве индекса ухода . Этот выбор эффективно увеличивает $x q$ от нуля до тех пор, пока $x p$ не уменьшится до нуля, сохраняя при этом осуществимость. Операция поворота завершается заменой $A p$ на $A q$ в базисе.

Численный пример

Рассмотрим линейную программу, в которой

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}

Позволять

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}

изначально, что соответствует допустимой вершине $x = [0 0 0 10 15] Т$ . В этот момент,

{\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

Выберите $q = 3$ в качестве входного индекса. Тогда $d = [1 3] Т$ на единицу $, что означает, что увеличение x 3$ приводит к $x 4$ и $x 5$ уменьшению $на 1$ и $3$ соответственно. Следовательно, $x 3$ увеличивается до $5$ , после чего $x 5$ уменьшается до нуля, и $p = 5$ становится индексом ухода.

После поворотной операции

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}

Соответственно,

{\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

Положительное значение $s N$ указывает на то, что $x$ теперь является оптимальным.

Практические вопросы

Вырождение

Поскольку пересмотренный симплекс-метод математически эквивалентен симплекс-методу, он также страдает вырождением, когда операция поворота не приводит к уменьшению $c. Т x$ , а цепочка операций поворота вызывает циклическое движение базиса. Чтобы предотвратить зацикливание и гарантировать завершение, можно использовать пертурбацию или лексикографическую стратегию. ^[6]

Базовое представление

два типа линейных систем с участием $B$ В пересмотренном симплекс-методе присутствуют :

{\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}

Вместо рефакторизации $B$ обычно LU-факторизация напрямую обновляется после каждой операции поворота, для чего существует несколько стратегий, таких как методы Форреста-Томлина и Бартельса-Голуб. Однако объем данных, представляющих обновления, а также числовые ошибки, со временем накапливается и делает необходимым периодический рефакторинг. ^[1]^[7]

Примечания и ссылки

Примечания

^ Та же теорема также утверждает, что допустимый многогранник имеет хотя бы одну вершину и что существует хотя бы одна оптимальная вершина. ^[3]

Ссылки

^ Jump up to: ^а ^б Морган 1997 , §2.
^ Носедал и Райт 2006 , с. 358, уравнение. 13.4.
^ Носедал и Райт 2006 , с. 363, Теорема 13.2.
^ Носедал и Райт 2006 , с. 370, Теорема 13.4.
^ Носедал и Райт 2006 , с. 369, уравнение. 13.24.
^ Носедал и Райт 2006 , с. 381, §13.5.
^ Носедал и Райт 2006 , с. 372, §13.4.

Библиография

Морган, СС (1997). Сравнение алгоритмов симплекс-метода (магистерская диссертация). Университет Флориды . Архивировано из оригинала 7 августа 2011 года.
Носедаль, Дж.; Райт, С.Дж. (2006). Микош, ТВ; Резник, С.И.; Робинсон, С.М. (ред.). Численная оптимизация . Серия Springer по исследованию операций и финансовой инженерии (2-е изд.). Нью-Йорк, штат Нью-Йорк, США: Springer . ISBN 978-0-387-30303-1 .

[4] Та же теорема также утверждает, что допустимый многогранник имеет хотя бы одну вершину и что существует хотя бы одна оптимальная вершина. ^[3]

[FOOTNOTEMorgan1997§2-1] Jump up to: ^а ^б Морган 1997 , §2.

[FOOTNOTENocedalWright2006358Eq.&nbsp;13.4-2] Носедал и Райт 2006 , с. 358, уравнение. 13.4.

[FOOTNOTENocedalWright2006363Theorem&nbsp;13.2-3] Носедал и Райт 2006 , с. 363, Теорема 13.2.

[FOOTNOTENocedalWright2006370Theorem&nbsp;13.4-5] Носедал и Райт 2006 , с. 370, Теорема 13.4.

[FOOTNOTENocedalWright2006369Eq.&nbsp;13.24-6] Носедал и Райт 2006 , с. 369, уравнение. 13.24.

[FOOTNOTENocedalWright2006381§13.5-7] Носедал и Райт 2006 , с. 381, §13.5.

[FOOTNOTENocedalWright2006372§13.4-8] Носедал и Райт 2006 , с. 372, §13.4.

[1]

[2]

[а]

[4]

[5]

[6]

[7]

[3]

v т и Проблемы дополнительности и алгоритмы
Complementarity Problems	Linear programming (LP) Quadratic programming (QP) Linear complementarity problem (LCP) Mixed linear (MLCP) Mixed (MCP) Nonlinear (NCP)
Basis-exchange algorithms	Simplex (Dantzig) Revised simplex Criss-cross Lemke