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