Курсовая работа: Основные принципы решения транспортной задачи

Рассмотрим случай N=3 (рис. 4, а) и предположим, что мы рассматриваем тот вариант, который содержит переход 3®2. Тогда задача коммивояжера после вычеркивания третьей строки и второго столбца вырождается в тривиальную. Ее матрица изображена на рис. 4, б). В этом случае мы имеем единственный путь, и его длина будет, очевидно, равна сумме

1 3 1 ¥ C1 2 C2 ¥ Рис. 4б.

1 2 3 1 ¥ С1 С1 2 С2 ¥ С2 3 С3 С3 ¥ Рис. 4а.

Итак, если в результате вычеркивания строки номера i и столбца номера j мы получим матрицу второго порядка, то задачу можно считать решенной.

Пусть теперь N > 3. После вычеркивания мы получим матрицу порядка N-1 >2. С этой матрицей (N-1)-го порядка совершим процедуру приведения. Матрицу, которую таким образом получим, обозначим через , а через - сумму ее констант приведения. Тогда для , мы будем иметь оценку

. (8)

На этом первый шаг алгоритма закончен. В результате одного шага мы разбили множество всех возможных вариантов на два множества , и для путей, принадлежащих этим множеством, мы получили оценки (8) и (7) (рис. 5).

_ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3