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

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

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

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

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

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

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

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

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

куда λ и s являются Множители Лагранжа связанные с ограничениями Топор = б и Икс ≥ 0, соответственно.[2] Последнее условие, которое эквивалентно sяИкся = 0 для всех 1 < я < п, называется условие дополнительной расслабленности.

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

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

Чтобы удовлетворить условию дополнительной нежесткости, пусть sB = 0. Следует, что

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

Если sN ≥ 0 в этот момент выполняются условия KKT, и, следовательно, Икс оптимально.

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

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

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

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

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

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

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

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

Позволять

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

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

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

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

Положительный sN указывает, что Икс сейчас оптимально.

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

Вырождение

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

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

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

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

Вместо рефакторинга 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 г.CS1 maint: ref = harv (связь)
  • Nocedal, J .; Райт, С. Дж. (2006). Mikosch, T. V .; Resnick, S.I .; Робинсон, С. М. (ред.). Численная оптимизация. Серия Springer по исследованию операций и финансовому инжинирингу (2-е изд.). Нью-Йорк, Нью-Йорк, США: Springer. ISBN  978-0-387-30303-1.CS1 maint: ref = harv (связь)