Комбинаторная оптимизация

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Комбинаторная оптимизация – область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов[1], чем очень похожа на дискретное программирование. Некоторые источники [2] под дискретным программированием понимают целочисленное программирование, противопоставляя ему комбинаторную оптимизацию, имеющую дело с графами, матроидами и похожими структурами. Однако оба термина очень близко связаны и в литературе часто переплетаются. Комбинаторная оптимизация часто сводится к определению эффективного распределения ресурсов, используемых для поиска оптимального решения.

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

Приложения[править | править вики-текст]

Комбинаторная оптимизация используется при:

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

Однако этими примерами приложение комбинаторной оптимизации не ограничивается

Методы[править | править вики-текст]

Имеется большое число литературы по полиномиальным по времени алгоритмам, работающих на некоторых классах задач дискретного программирования, и существенная часть этих алгоритмов принадлежат теории линейного программирования. Некоторые примеры комбинаторной оптимизации, попадающие в эту область – это задача поиска кратчайшего пути и дерева кратчайших путей, определение максимального потока, нахождение остовных деревьев, нахождение паросочетаний, задачи с матроидами.

Задачи комбинаторной оптимизации можно рассматривать как поиск лучшего элемента в некотором дискретном множестве, поэтому, в принципе, могут быть использованы любые алгоритмы поиска или метаэвристические алгоритмы. Однако общие алгоритмы поиска не гарантируют ни оптимального решения, ни быстрого решения (за полиномиальное время). Поскольку некоторые задачи дискретной оптимизации NP-полны, как, например, задача о коммивояжёре, это же следует ожидать и для других задач (если не P=NP).

Частные задачи[править | править вики-текст]

Оптимальный путь коммивояжёра по крупнейшим 15 городам Германии. Это кратчайший путь из 43.589.145.600 = 14!/2 возможных.

См. также[править | править вики-текст]

Математическое программирование

Дальнейшее чтение[править | править вики-текст]

  • Schrijver Alexander Combinatorial Optimization: Polyhedra and Efficiency. — Springer. — Vol. 24.

Ссылки[править | править вики-текст]

  1. Schrijver, p. 1
  2. Discrete Optimization. Elsevier. Проверено 8 июня 2009. Архивировано из первоисточника 24 июня 2013.