ЗАДАЧА О КОММИВОЯЖЕРЕ

— одна из комбинаторных задач дискретного программирования. Общая формулировка 3. о к.: торговец, выезжающий из некоторого города, должен посетить каждый из других городов только один раз и вернуться в исходный город. Матрица расстояний известна. Требуется определить, в каком порядке торговец должен посещать города, чтобы общее пройденное расстояние было минимальным. Если «у рассматривать как время, издержки или другой показатель, то к 3. о к. сведется ряд прикладных задач, связанных с обходом ряда пунктов, проведением коммуникаций между ними, составлением расписания выполнения работ, оптимизацией программ для ЭВМ и др. Решение 3. о к. может быть найдено путем перебора возможных маршрутов. Однако с ростом число вариантов быстро достигает астрономических цифр, что вынуждает отказаться от прямого их перебора.

Один из способов решения 3. о к. состоит в сведении ее к задаче целочисленного программирования линейного, состоящей в минимизации линейной формы затрат приограничениях

где - некоторые специально подобранные вспомогательные целые числа. Условие (1) выражает однократность посещения городов, (2) — неотрицательность переменных, (3) — односвязность маршрута.

Использование идеи программирования динамического состоит в том, что 3. о к. представляют в виде многошагового процесса наращивания звеньев пути, минимизируя затраты. Основное рекуррентное ур-ние при этом имеет вид:

где — длина оптим. пути возврата от до исходного города через оставшиеся города следующий за -тым город пути. Решение достигается перебором вариантов. Наиболее эффективным из известных способов получения точного решения 3. о к. считается ветвей и границ метод. Л. Н. Закашанский.