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

(2)

причем сумма (2) распространена по i, j так, что каждый из индексов встречается в ней один и только один раз. Величины с двумя одинаковыми индексами мы приняли равными ¥.

Так как в каждый из вариантов s входит только один элемент из каждой строки и столбца, то мы можем проделать следующую операцию, которая здесь называется приведением матрицы. Обозначим через h, наименьший элемент из строки номера i и построим новую матрицу C элементами

.

Матрица C определяет новую задачу коммивояжера, которая, однако, в качестве оптимальной будет иметь ту же последовательность городов. Между величинами и будет существовать, очевидно, следующая связь:

Заметим, что в каждой из строк матрицы C будет теперь, по крайней мере, один нулевой элемент. Далее обозначим через наименьший элемент матрицы C, лежащий в столбце номера j, и построим новую матрицу С с элементами

Величины h и называются константами приведения. Оптимальная последовательность городов для задачи коммивояжера с матрицей С будет, очевидно, такой же, как и для исходной задачи, а длины пути для варианта номера s в обеих задачах будут связаны между собой равенством

, (3)

Где

, (4)

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

Обозначим через 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.