5848

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Метод сетевого программирования в симметричной задаче коммивояжера

Наименование источника: 

  • Проблемы управления

Город: 

  • -

Издательство: 

  • -

Год издания: 

2008

Страницы: 

7-10
Аннотация
Метод сетевого программирования применен для получения нижних оценок в симметричной задаче коммивояжера. Сформулирована двойственная задача, состоящая в разбиении ограничений на две группы с соответствующим делением длин дуг на две части и решении двух полученных оценочных задач. Сумма целевых функций оптимальных решений оценочных задач дает нижнюю оценку для исходной задачи. Показано, что решение оценочной задачи сводится к построению i-деревьев кратчайшей длины. Предложен новый способ получения нижних оценок для оценочных задач, в основе которого лежит построение дерева кратчайших путей. Показано, что построение i-деревьев и дерева кратчайших путей для исходной матрицы расстояний не дает оптимального решения двойственной задачи.

Библиографическая ссылка: 

Буркова И.В. Метод сетевого программирования в симметричной задаче коммивояжера // Проблемы управления. 2008. С. 7-10.