| Меню сайта |
|
 |
| Категории раздела |
|
|
| Статистика |
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
|
|
 | |  |
| Главная » 2017 » Май » 25 » Комбинаторная оптимизация
19:47 Комбинаторная оптимизация |
[править | править вики-текст]
Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов[1], чем очень похожа на дискретное программирование. Некоторые источники [2] под дискретным программированием понимают целочисленное программирование, противопоставляя ему комбинаторную оптимизацию, имеющую дело с графами, матроидами и похожими структурами. Однако оба термина очень близко связаны и в литературе часто переплетаются. Комбинаторная оптимизация часто сводится к определению эффективного распределения ресурсов, используемых для поиска оптимального решения.
Во многих задачах комбинаторной оптимизации полный перебор нереален. Комбинаторная оптимизация включает в себя задачи оптимизации, в которых множество допустимых решений дискретно или может быть сведено к дискретному множеству.
Содержание
[скрыть]
1 Приложения
2 Методы
3 Частные задачи
4 См. также
5 Литература
6 Примечания
Приложения[править | править вики-текст]
Комбинаторная оптимизация используется при:
Определении оптимальной сети аэрофлота;
Определении, какая машина из парка такси подберёт пассажиров;
Определении оптимального пути доставки посылок;
Определении правильных атрибутов перед тестированием концепций.
Однако этими примерами приложение комбинаторной оптимизации не ограничивается.
Методы[править | править вики-текст]
Имеется большое число литературы по полиномиальным по времени алгоритмам, работающим на некоторых классах задач дискретного программирования и существенная часть этих алгоритмов принадлежит теории линейного программирования. Некоторые примеры комбинаторной оптимизации, попадающие в эту область — это задача поиска кратчайшего пути и дерева кратчайших путей, определение максимального потока, нахождение остовных деревьев, нахождение паросочетаний, задачи с матроидами.
Задачи комбинаторной оптимизации можно рассматривать как поиск лучшего элемента в некотором дискретном множестве, поэтому, в принципе, могут быть использованы любые алгоритмы поиска или метаэвристические алгоритмы. Однако общие алгоритмы поиска не гарантируют ни оптимального решения, ни быстрого решения (за полиномиальное время). Поскольку некоторые задачи дискретной оптимизации NP-полны, как, например, задача о коммивояжёре, это же следует ожидать и для других задач (если не P=NP).
Частные задачи[править | править вики-текст]
Оптимальный путь коммивояжёра по крупнейшим 15 городам Германии. Это кратчайший путь из 43.589.145.600 = 14!/2 возможных.
Задача выбора маршрута
Задача коммивояжёра
Минимальное остовное дерево
Линейное программирование (в части выбора переменной, которую следует вводить в базис)
Целочисленное программирование
Задача о восьми ферзях — задача удовлетворения ограничений. Если использовать стандартные методы комбинаторной оптимизации для этой задачи, в качестве целевой функции используется число невыполненных ограничений (то есть число атак).
Задача о ранце
Задача раскроя
Задача о назначениях
Задача о назначении целей
См. также[править | править вики-текст]
Математическое программирование
Литература[править | править вики-текст]
Schrijver Alexander. Combinatorial Optimization: Polyhedra and Efficiency. — Springer. — Vol. 24.
Glover F., Kochenberger G.A. Handbook of Metaheuristics. New York: Kluwer Academic Publishers, 2003. 560 p.
Ватутин Э. И., Титов В. С., Емельянов С. Г. Основы дискретной комбинаторной оптимизации. М.: Аргамак-Медиа, 2016. 270 с. ISBN 978-5-00-024057-1
Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: МГТУ им. Н. Э. Баумана, 2014. 446 с. ISBN 978-5-7038-3949-2
Примечания[править | править вики-текст]
↑ Alexander Schrijver. Algorithms and Combinatorics // Combinatorial Optimization: Polyhedra and Efficiency. — Springer. — С. 1.
↑ Discrete Optimization. Elsevier. Проверено 8 июня 2009. Архивировано 24 июня 2013 года.
Для улучшения этой статьи желательно:
Проверить качество перевода с иностранного языка.
Источник — «https://ru.wikipedia.org/w/index.php?title=Комбинаторная_оптимизация&oldid=82645411»
Категории: Исследование операцийКомбинаторная оптимизацияКомбинаторикаСкрытые категории: Википедия:Плохой переводСтраницы, использующие волшебные ссылки ISBN
|
|
Категория: Творчество |
Просмотров: 119 |
Добавил: alena_soboleva_70
| Рейтинг: 0.0/0 |
| |
 | |  |
|
| Вход на сайт |
|
|
| Поиск |
|
|
| Календарь |
| « Май 2017 » | | Пн | Вт | Ср | Чт | Пт | Сб | Вс | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | 15 | 16 | 17 | 18 | 19 | 20 | 21 | | 22 | 23 | 24 | 25 | 26 | 27 | 28 | | 29 | 30 | 31 |
|
|
| Архив записей |
|
|
|
