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

• Обзор пересмотренного симплексного метода

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

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

  • Условия Каруша-Куна-Такера являются необходимыми и достаточными для оптимальности решения. 
  • В стандартном виде задачи линейного программирования условия ККТ включают множители Лагранжа и ограничения на переменные. 

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

  • Если условия ККТ не выполняются, выполняется операция поворота, которая может привести к уменьшению целевой функции. 
  • Операция поворота включает в себя выбор индекса для увеличения переменной и последующее уменьшение другой переменной. 

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

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

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

  • В пересмотренном методе присутствуют две линейные системы, включающие базисные векторы. 
  • Факторизация LU матрицы обновляется после каждой операции поворота, что может требовать периодической рефакторизации.