Задача комбинаторной оптимизации

Комбинаторная оптимизация – это отрасль оптимизации в прикладной математике и информатике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности, которая находится на пересечении нескольких областей, включая искусственный интеллект, математику и разработку программного обеспечения. Алгоритмы комбинаторной оптимизации решают задачи, которые в целом считаются сложными, путем исследования обычно большого пространства решений этих примеров. Алгоритмы комбинаторной оптимизации достигают этого за счет уменьшения размера пространства и его эффективного исследования.
Примерами задачи комбинаторной оптимизации могут быть, например, линейное программирование, задача о рюкзаке (из заданного множества предметов с известными значениями стоимости и веса требуется выбрать такое подмножество, которое имеет максимальную стоимость всех предметов, учитывая при этом ограничение на суммарный вес рюкзака), задача о построении минимального остовного дерева (многие практические проблемы возникают вокруг физических сетей, которые могут быть представлены в виде графа, таких как городские улицы, шоссе, железнодорожные системы), задача о расстановки 8 ферзей (расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого) и т.д.
Задачи комбинаторной оптимизации связаны с эффективным распределением ограниченных ресурсов для достижения желаемых целей, когда значения некоторых или всех переменных ограничены числовыми значениями. Ограничения на основные ресурсы, такие как рабочая сила, материалы или капитал, ограничивают возможные альтернативы, которые считаются осуществимыми. Тем не менее, в большинстве таких задач есть много возможных альтернатив, которые следует учитывать, и одна общая цель определяет, какая из этих альтернатив лучше

. Например, большинству авиакомпаний необходимо определять графики работы экипажа, которые минимизируют общие эксплуатационные расходы; производители автомобилей могут захотеть определить структуру парка автомобилей, которая максимизирует их долю на рынке; гибкое производственное предприятие должно планировать производство для завода без предварительного уведомления о том, какие детали необходимо будет изготовить в этот день. В сегодняшней меняющейся и конкурентной промышленной среде разница между использованием быстро получаемого «решения» и использованием сложных математических моделей для поиска оптимального решения может определить, выживет ли компания.
Универсальность комбинаторной модели оптимизации проистекает из того факта, что во многих практических задачах деятельность и ресурсы, такие как машины, самолеты и люди, неделимы. Кроме того, многие проблемы имеют только конечное число альтернативных вариантов и, следовательно, могут быть соответствующим образом сформулированы как задачи комбинаторной оптимизации – здесь слово «комбинаторная» относится к тому факту, что существует только конечное число альтернативных возможных решений. Комбинаторные модели оптимизации часто называют моделями целочисленного программирования, где программирование относится к «планированию», так что это модели, используемые при планировании, где некоторые или все решения могут принимать только конечное число альтернативных вариантов.
Комбинаторная оптимизация – это процесс поиска одного или нескольких лучших (оптимальных) решений в четко определенном дискретном пространстве задач