Пересмотренный симплексный метод - Revised simplex method

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

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

Постановка проблемы

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

${\displaystyle {\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}}}$

куда А ∈ р^м×п. Без ограничения общности предполагается, что матрица ограничений А имеет полный ранг строки и что проблема допустима, т. е. имеется хотя бы один Икс ≥ 0 такой, что Топор = б. Если А имеет недостаточный ранг, либо имеются избыточные ограничения, либо проблема недопустима. Обе ситуации могут быть обработаны на этапе предварительного решения.

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

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

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

${\displaystyle {\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 являются Множители Лагранжа связанные с ограничениями Топор = б и Икс ≥ 0, соответственно.^[2] Последнее условие, которое эквивалентно s_яИкс_я = 0 для всех 1 < я < п, называется условие дополнительной расслабленности.

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

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

куда Икс_B ≥ 0. Раздел c и s соответственно в

${\displaystyle {\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. Следует, что

${\displaystyle {\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}}}$

откуда следует, что

${\displaystyle {\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 ≥ 0 в этот момент выполняются условия KKT, и, следовательно, Икс оптимально.

Поворотная операция

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

Выберите индекс м < q ≤ п такой, что s_q < 0 как ввод индекса. Соответствующий столбец А, А_q, будет перемещен в базу, и Икс_q будет разрешено увеличиваться с нуля. Можно показать, что

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

т.е. на каждую единицу увеличения Икс_q приводит к уменьшению на −s_q в c^ТИкс.^[5] С

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

Икс_B должно быть соответственно уменьшено на ΔИкс_B = B⁻¹А_qИкс_q при условии Икс_B - ΔИкс_B ≥ 0. Позволять d = B⁻¹А_q. Если d ≤ 0, Неважно, сколько Икс_q увеличена, Икс_B - ΔИкс_B останется неотрицательным. Следовательно, c^ТИкс можно произвольно уменьшить, и, таким образом, проблема не ограничена. В противном случае выберите индекс п = argmin_1≤я≤м {Икс_я/d_я | d_я > 0} как оставив индекс. Этот выбор эффективно увеличивает Икс_q с нуля до Икс_п сводится к нулю при сохранении осуществимости. Операция поворота завершается заменой А_п с А_q в основании.

Числовой пример

Смотрите также: Симплексный метод § Пример

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

${\displaystyle {\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}}}$

Позволять

${\displaystyle {\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}}}$

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

${\displaystyle {\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]^Т, что означает увеличение единицы Икс₃ приводит к Икс₄ и Икс₅ уменьшается на 1 и 3, соответственно. Следовательно, Икс₃ увеличивается до 5, в этот момент Икс₅ сводится к нулю, а п = 5 становится индексом выхода.

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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 указывает, что Икс сейчас оптимально.

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

Вырождение

Смотрите также: Симплексный метод § Вырождение: остановка и езда на велосипеде

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

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

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

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

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

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

Примечания

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

Рекомендации

1. Морган 1997, §2.
2. Нокедал и Райт 2006, п. 358, уравнение. 13.4.
3. Нокедал и Райт 2006, п. 363, теорема 13.2.
4. Нокедал и Райт 2006, п. 370, теорема 13.4.
5. Нокедал и Райт 2006, п. 369, уравнение. 13.24.
6. Нокедал и Райт 2006, п. 381, §13.5.
7. Нокедал и Райт 2006, п. 372, §13.4.

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

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