Перекрестный алгоритм
-
История и описание алгоритма «крест-накрест»
- Алгоритм «крест-накрест» был опубликован независимо Тамасом Терлаки и Чжэ-Мин Вангом.
- Алгоритм является комбинаторным и отличается от симплексного алгоритма линейной оптимизации.
- Он был разработан для решения задач линейного программирования и имеет полиномиальную сложность в худшем случае.
-
Сравнение с симплексным алгоритмом
- Симплексный алгоритм включает две фазы: нахождение выполнимой основы и переключение между решениями.
- Алгоритм «крест-накрест» проще и использует только одну фазу, а его правила сводки аналогичны правилу Бланда.
- Симплексный алгоритм является монотонным, в то время как алгоритм «крест-накрест» не всегда имеет монотонную функцию полезности.
-
Вычислительная сложность
- Алгоритм имеет наихудшую и среднюю сложность, определяемую количеством арифметических операций.
- Существуют алгоритмы с экспоненциальной сложностью, в то время как «крест-накрест» имеет полиномиальную сложность.
-
Расширения и применение
- Алгоритм был расширен для решения задач линейного программирования, квадратичного программирования и линейной дополнительности.
- Он также использовался для перечисления вершин многогранников и в теории ориентированных матроидов.
-
Резюме
- Алгоритм «крест-накрест» является простым и комбинаторным алгоритмом линейного программирования.
- Он не является симплексоподобным и не всегда обеспечивает выполнимость, но не имеет полиномиальной временной сложности.
- Алгоритм был расширен для решения многих задач оптимизации и остается простым в изложении.
Полный текст статьи: