Основные принципы решения транспортной задачи (стр. 2 из 2)

т.е.

равна сумме констант приведения.

Обозначим через l * решение задачи коммивояжера, т. е.

,

где минимум берется по всем вариантам s, удовлетворяющим условию (a). Тогда величина

будет простейшей нижней оценкой решения:

(5)

Будем рассматривать теперь задачу коммивояжера с матрицей С

, которую мы будем называть приведенной матрицей.

Рассмотрим путь, содержащий непосредственный переход из города номера i в город номера j , тогда для пути s , содержащего этот переход, мы будем иметь, очевидно, следующую нижнюю оценку:

Следовательно, для тех переходов, для которых

, мы будем иметь снова оценку (5). Естественно ожидать, что кратчайший путь содержит один из таких переходов - примем это соображение в качестве рабочей гипотезы. Рассмотрим один из переходов, для которого , и обозначим через множество всех тех путей, которые не содержат перехода из i в j. Так как из города i мы должны куда-то выйти, то множество содержит один из переходов i®k, где k¹i; так как в город номера j мы должны прийти, то множество содержит переход т®i, где т¹ i. Следовательно, некоторый путь , из множества , содержащий переходы i®k и т®i , будет иметь следующую нижнюю оценку:

.

Обозначим через

Тогда очевидно, что для любого

множества путей мы будем иметь оценку

(6)

Мы предполагаем исключить некоторое множество вариантов

, поэтому мы заинтересованы выбрать такой переход i®j, для которого оценка (6) была бы самой высокой. Другими словами, среди нулевых элементов матрицы С выберем тот, для которого максимально. Это число обозначим через . Таким образом, все множество возможных вариантов мы разбили на два множества I и I . Для путей из множества I , мы имеем сценку (5). Для путей из множества I оценка будет следующей:

. (7)

Рассмотрим теперь множество I

, и матрицу С . Так как все пути, принадлежащие этому множеству, содержат переход i®j, то для его исследования нам достаточно рассмотреть задачу коммивояжера, в которой города номеров i и j совпадают. Размерность этой задачи будет уже равна N - 1, а ее матрица получится из матрицы С вычеркиванием столбца номера j и строки номера i.

Поскольку переход i®j невозможен, то элемент

принимаем равным бесконечности.

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

Рис. 4б.