Матрица стоимостей (условные единицы)

Узел №	Пункты	Исходный пункт	Токио	Гонконг	Лондон	Сидней	Рим
	Исходный пункт	-
	Токио		-
	Гонконг			-
	Лондон				-
	Сидней					-
	Рим						-

 

Примечание. В процессе проведения расчетов все стоимости будут уменьшены в 10 раз.

Подобные задачи в математическом программировании носят название «задача коммивояжера». Ее формулируют следующим образом. Коммивояжер должен выехать из исходного пункта и побывать в каждом из остальных (n -1) пунктов ровно один раз и вернуться в исходный пункт. Задача заключается в определении последовательности объезда пунктов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: стоимость проезда, время пути, суммарное расстояние и т.д. Здесь требуется выбрать один или несколько оптимальных маршрутов из (n -1)! возможных. Если некоторые города для коммивояжера недоступны, то минимальное значение целевой функции должно быть бесконечно большим.

Рассмотрим решение задачи коммивояжера методом ветвей и границ. Вначале определяют некоторое допустимое решение (допустимый маршрут). После этого множество всех оставшихся маршрутов разбивают на все более мелкие подмножества и при каждом разбиении вычисляют нижнюю границу целевой функции текущего наилучшего маршрута. С помощью найденных границ проводят дальнейшее разбиение подмножеств допустимых маршрутов и в конечном итоге определяют оптимальный маршрут. Это разбиение подмножеств маршрутов можно рассматривать как узлы дерева. Поэтому данный метод называют методом поиска по дереву решений, или методом ветвей и границ. Матрица стоимостей содержит неотрицательные элементы с_ij. Маршрут Т можно представить как множество упорядоченных пар пунктов T={(i₁, i₂), (i_2, i₃),…,(i_n-1, i_n), (i_n, i₁)}. Каждый допустимый маршрут – это цикл, проходя по которому коммивояжер посещает каждый пункт один раз и возвращается в исходную точку. Каждая упорядоченная пара (i, j) является дугой, или звеном маршрута. Стоимость маршрута Т равна сумме соответствующих элементов матрицы стоимостей, но только тех, что лежат на маршруте Т: ɀ(T)= .

Величина ɀ(T) определена для любого допустимого маршрута и не может быть меньше стоимости оптимального маршрута, т.е. текущее значение ɀ (T)является верхней границей ɀ_в (T) стоимости оптимального маршрута Т.

Для вычисления нижних границ стоимости маршрута используют понятие редукции строк и столбцов матрицы стоимости. Процедуру вычитания из каждого элемента строки наименьшего элемента этой же строки и из каждого элемента столбца наименьшего элемента этого же столбца называют соответственно редукцией строк и редукцией столбцов. Матрицу с неотрицательными элементами, в каждой строке и в каждом столбце которой содержится по крайней мере один нулевой элемент, называют редуцированной. Она может быть получена в результате последовательной редукции ее строк и столбцов. Если вычесть из каждого элемента некоторой строки матрицы стоимости постоянную величину с, то стоимость любого маршрута, определяемая новой матрицей, меньше стоимости того же маршрута, определяемого старой матрицей, на величину с,так как для любого допустимого маршрута каждая строка и каждый столбец матрицы содержат по одному элементу, соответствующему этому маршруту. При редукции относительные стоимости всех маршрутов останутся неизменными. Следовательно, останутся неизменными и все оптимальные маршруты.

Если ɀ(T) – стоимость маршрута Т, определяемая матрицей стоимости до выполнения редукции, ɀ₁(T) – стоимость того же маршрута, определяемая редуцированной матрицей, Н – сумма всех констант, используемых при вычислении редуцированной матрицы, то ɀ(T)=ɀ₁(T)+Н. поскольку редуцированная матрица содержит только неотрицательные элементы, то Н является нижней границей стоимости маршрута Т для нередуцированной матрицы стоимости.

В алгоритме метода ветвей и границ диагональные элементы исходной матрицы стоимости полагают равными ∞, т.е. с_ij =∞.

Выберем произвольный допустимый маршрут, например состоящий из звеньев (1,4) (4,5); (5,3); (3,6); (6,2); (2,1). Стоимость данного маршрута ɀ_в(T)=16+18+27+0+5+9=73, т.е. для оптимального маршрута стоимость поездки коммивояжера не может превышать ɀ_в(T).

Выполним редукцию строк, а затем столбцов матрицы и стоимости; для этого в каждой определим минимальный элемент и найденное значение с_i вычтем из элементов соответствующей строки. Получим табл. 3.2.

Проведем редукцию столбцов в полученной табл. 3.2. Из таблицы видно, что следует осуществить только редукцию первого столбца, так как остальные столбцы содержат нулевые элементы. Редукция столбцов показана в таблице 3.3.

Таблица 3.2

Редукция строк

Узел							Сi
	∞
		∞
			∞
				∞
					∞
						∞

 

Таблица 3.3

Редукция столбов

Узел							Ci
	∞
		∞
			∞
				∞
					∞
						∞
Qj							H=48

Строка Q_j содержит вычитаемые константы для каждого столбца при редукции столбцов. Значение нижней границы для всех маршрутов в рассматриваемой задаче ровно Н – сумме всех вычитаемых констант: _i+ _j=48.

Теперь выберем оптимальный маршрут. Если бы в каждой строке и каждом столбце было бы ровно по одному нулевому элементу, оптимальная стоимость проезда равнялась бы Н.

Однако нулевые элементы не единственные в строках и столбцах. Вместо того чтобы одновременно определять все звенья оптимального маршрута с помощью текущей матрицы стоимости, воспользуемся алгоритмом, на каждом шаге которого по матрице стоимости строится одно звено оптимального маршрута. Естественно вначале выбрать звено нулевой длины, а затем последовательно добавить звенья нулевой и минимальной длины. Если выбрать звено (i, j), то решение не должно содержать других звеньев, соответствующих элементам i -й строки и j -го столбца; если звено (i, j) можно не рассматривать при выполнении последующих операций. Следовательно, для каждого звена достаточно рассмотреть следующие два случая: в первом случае звено включают в текущее и все последующие решения до определения оптимального решения; во втором – звено исключают из дальнейшего рассмотрения. В нашем примере мы уже получили начальный узел дерева ветвления, соответствующий множеству всех маршрутов с нижней границей стоимости всех маршрутов с Н =48, и верхней, равной ɀ_в(T)=73.

На следующем шаге процедуры выберем звено, на котором будет базироваться ветвление. Так как в каждой строке и каждом столбце не единственный элемент с_ij =0,то надо рассмотреть маршруты, не содержащие звено (i, j), должен содержать звено А, у которого стоимость не меньше минимального элемента в i -й строки, не считая с_ij =0. Стоимость звена А обозначим А_i.. Таким образом, чтобы А_i. равно нулю, в строке должно быть не менее двух нулевых элементов. Аналогично, чтобы в пункт j можно было бы попасть из некоторого другого города, маршрут, не содержащий узел (i, j), должен содержать звено В, у которого стоимость не меньше минимального элемента j -ого столбца, не считая с_ij =0. Обозначим стоимость проезда по звену В через В_j, а сумму величин А_i. и В_j через Ф _ij. Величина Ф _ij называется вторичным штрафом, и она равна минимальному штрафу, которому мы подвергаемся, если не включаем звено (i, j) в оптимальны маршрут. Если штраф за неиспользование звена вычислить для всех звеньев, у которых с_ij =0, то можно сравнить соответствующее значение Ф _ij и включить в текущий маршрут звено (i, j), за неиспользование которого мы заплатили бы максимальный штраф, т.е. включая звено (i, j), мы получаем выигрыш в стоимости, равный максимальному значению Ф _ij. Нижняя граница для соответствующей ветви должна быть выбрана таким образом, чтобы она не превосходила стоимости ни одного из маршрутов, не содержащих звена (i, j). Данное требование будет выполнено, если значение новой нижней границы положить равным сумме значений текущей нижней границы и максимального штрафа за неиспользование звена (i, j). Для определения максимального значения Ф _ij будем использовать все элементы с _ij=0; при с _ij≠0 величина Ф _{i j}=0. Данное утверждение справедливо в силу того, что если положить с_ij =∞, а затем провести редукцию i -й строки и j -го столбца, то сумма вычитаемых констант будет равна Ф _ij. Для нашего случая А_i и В_j, приведены в таблице 3.13, а значение Ф _{i j} для узлов, соответствующих с_ij =0, - в табл. 3.14. Максимальное значение Ф _ij= 10 соответствует звену (1, 4). Следовательно, в качестве базового звена ветвления выбираем звено (1, 4).

Нижняя граница для маршрутов, не включающих звено (1, 4), равна Н +Ф ₁₄ =48+10=58. Чтобы определить новую нижнюю границу для маршрутов, включающих звено (1, 4), необходимо преобразовать матрицу стоимости. Если мы включили в маршрут некоторое звено (k, l), то в дальнейшем мы не рассматриваем k -ю строку и l- й столбец. Кроме того, звено (k, l) является тогда звеном некоторого ориентированного цикла и не может принадлежать этому же маршруту. Последнее условие можно выполнить, положив с_lk =∞.

Таблица 3.4

Значения А_i и В_J

Узел							Сi	Аi
	∞	∞	∞	∞	∞	∞
Qj							Н=48
Вi

Таблица 3.5

Значения Ф _ij

Звено (i, j)	(1, 4)	(2, 4)	(3, 6)	(4, 1)	(4, 2)	(5, 6)	(6, 2)	(6, 3)	(6, 5)
Фij=Аi+Bj

 

Из рассмотрения следует исключить и так называемые запрещенные звенья – звенья, с помощью которых в дальнейшем могут быть образованы циклы, включающие неполное множество пунктов (могут быть образованны подмаршруты). Элементы матрицы стоимости, соответствующие этим звеньям, берут равными ∞. Преобразованная матрица стоимости приведена в таблице 3.6. запрещенных звеньев в данном случае не существует. Вторая матрица решений после редукции строк и столбцов, а также с указанием значения с_i, A_i, B_j для 2-й матрицы приведена в таблице 3.6. нижняя граница маршрута, включающего звено (1, 4), может быть вычислена как сумма всех новых вычитаемых констант Н₁ и старой нижней границы, т.е. нижняя граница 48+1=49.

 

Таблица 3.6

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: