Перекрестный алгоритм

• История и описание алгоритма «крест-накрест»

  • Алгоритм «крест-накрест» был опубликован независимо Тамасом Терлаки и Чжэ-Мин Вангом. 
  • Алгоритм является комбинаторным и отличается от симплексного алгоритма линейной оптимизации. 
  • Он был разработан для решения задач линейного программирования и имеет полиномиальную сложность в худшем случае. 

• Сравнение с симплексным алгоритмом

  • Симплексный алгоритм включает две фазы: нахождение выполнимой основы и переключение между решениями. 
  • Алгоритм «крест-накрест» проще и использует только одну фазу, а его правила сводки аналогичны правилу Бланда. 
  • Симплексный алгоритм является монотонным, в то время как алгоритм «крест-накрест» не всегда имеет монотонную функцию полезности. 

• Вычислительная сложность

  • Алгоритм имеет наихудшую и среднюю сложность, определяемую количеством арифметических операций. 
  • Существуют алгоритмы с экспоненциальной сложностью, в то время как «крест-накрест» имеет полиномиальную сложность. 

• Расширения и применение

  • Алгоритм был расширен для решения задач линейного программирования, квадратичного программирования и линейной дополнительности. 
  • Он также использовался для перечисления вершин многогранников и в теории ориентированных матроидов. 

• Резюме

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