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

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