Решение задачи о коммивояжёре методом ветвей и границ

Задание на выполнение индивидуальной работы по дисциплине

«Математика: Математическое программирование»

«Задача о коммивояжёре »

Коммивояжёр должен объехать 7 городов. Выезжая из одного из них (безразлично какого) коммивояжёр должен объехать все города и вернуться в исходный город, преодолев минимальное расстояние.

При этом в каждый город он может и должен только 1 раз въехать и только 1 раз выехать. При известных расстояниях между городами (км) составить экономико-математическую модель задачи и решить задачу методом ветвей и границ.

Решение задачи о коммивояжёре методом ветвей и границ

Имеется пять городов. Коммивояжёр выезжает из одного из городов (безразлично какого) и должен объехать все города и вернуться в исходный город, преодолев минимальное расстояние. При этом в каждый город он может и должен только один раз въехать и только один раз выехать. При известных расстояниях между городами составить экономико-математическую модель задачи и решить задачу методом ветвей и границ.

Составляем экономико-математическую модель задачи.

2. Составим приведенную матрицу S¹

Найдем константу приведения: . Она определяет нижнюю границу множества всех гамильтоновых контуров (в дальнейшем ГК), то есть .

Найдем степени нулей для приведенной по строкам и столбцам матрицы

	∞	018
	021	∞	05
		00	∞	00
				∞		05
					∞	016
				00	016	∞	016
						016	∞

Для этого нуль в матрице , степень которого отыскивается, мысленно заменяем на ∞ и находим сумму минимальных элементов строки и столбца, где он находится.

Выбираем дугу, для которой степень нулевого элемента наибольшая. В нашем случае она равна 21 и соответственно дуге (2; 1). Т.о. претендентом на включение в ГК является дуга (2; 1).Если в решении задачи таких дуг несколько, то выбирается любая из этих дуг. Возможно, что при дальнейшем решении выбор дуги не повлияет на оптимальность ответа, т.е. может быть получено несколько ответов с одинаковой минимальной стоимостью, или все решения приведут к единственному ответу. Хотя и возможна следующая ситуация, что от произвольного выбора на данном этапе дуги существенным образом зависит от оптимальности решения. Т.о. для его нахождения необходимо перебрать все варианты.

Разбиваем множество всех ГК на два: и (решим две подзадачи):

	018
	00	∞	00
			∞		05
				∞	016
			00	016	∞	016
					016	∞

Матрицу ГК , содержащую дугу (6; 2) получаем из последней таблицы, вычеркивая строки 6 и столбца 2. Чтобы не допустить образование негамильтонова контура, заменяем элемент на ∞:                 ∞               00 ∞ 00               ∞   05             ∞ 016           00 016 ∞ 016             016 ∞                   ∞             00 ∞ 00             ∞   05           ∞ 016         00 016 ∞ 016           016 ∞               Находим . Итак, нижняя граница множества равна

Матрицу ГК , не содержащую дугу (6; 2) получаем из последней таблицы путем замены элемента на ∞:                   ∞ 018               ∞ ∞ 05               00 ∞ 00                 ∞   05               ∞ 016             00 016 ∞ 016               016 ∞                     ∞ 018             ∞ ∞ 05             00 ∞ 00               ∞   05             ∞ 016           00 016 ∞ 016             016 ∞                 Находим . Итак, нижняя граница множества равна

Сравниваем нижние границы подмножеств и . Так как , дальнейшему ветвлению подвергаем подмножество . Находим степени нулей этой матрицы: Находим степени нулей этой матрицы: Находим степени нулей этой матрицы:

	∞	018
	∞	∞	06
		00	∞	00
	0115			∞		05
					∞	016
				00	016	∞	016
						016	∞

	018
	∞	01
	00	∞	00
				∞	016
			00	016	∞	016
					016	∞

Разбиваем множество всех ГК на два: и (решим две подзадачи):

Матрицу ГК , содержащую дугу (4; 1) получаем из последней таблицы, вычеркивая строки 4 и столбца 1. Чтобы не допустить образование негамильтонова контура, заменяем элемент на ∞:                 018   ∞           ∞ 01             00 ∞ 00                 ∞ 016           00 016 ∞ 016             016 ∞                   018   ∞         ∞ 01           00 ∞ 00               ∞ 016         00 016 ∞ 016           016 ∞               Находим . Итак, нижняя граница множества равна

Матрицу ГК , не содержащую дугу (4; 1) получаем из последней таблицы путем замены элемента на ∞:                   ∞ 018               ∞ ∞ 06               00 ∞ 00           ∞     ∞   05               ∞ 016             00 016 ∞ 016               016 ∞                       ∞ 018             ∞ ∞ 06             00 ∞ 00         ∞     ∞   05             ∞ 016           00 016 ∞ 016             016 ∞                 Находим . Итак, нижняя граница множества равна

Сравниваем нижние границы подмножеств и . Так как , дальнейшему ветвлению подвергаем подмножество . Находим степени нулей этой матрицы:

	0131		∞
	∞	0119
	00	∞	00
				∞	016
			00	016	∞	016
					016	∞

	0119
	∞	00
			∞	016
		00	016	∞	016
				016	∞

Разбиваем множество всех ГК на два: и (решим две подзадачи):

Матрицу ГК , содержащую дугу (1; 2) получаем из последней таблицы, вычеркивая строки 1 и столбца 2. Чтобы не допустить образование негамильтонова контура, заменяем элемент на ∞:                   0119             ∞ 00               ∞ 016         00 016 ∞ 016           016 ∞   Находим . Итак, нижняя граница множества равна

Матрицу ГК , не содержащую дугу (1; 7) получаем из последней таблицы путем замены элемента на ∞:                 ∞   ∞           ∞ 0119             00 ∞ 00                 ∞ 016           00 016 ∞ 016             016 ∞   Находим . Итак, нижняя граница множества равна

Сравниваем нижние границы подмножеств и . Так как , дальнейшему ветвлению подвергаем подмножество . Находим степени нулей этой матрицы:

	0119
	∞	00
			∞	016
		00	016	∞	016
				016	∞

	00
		∞	016
	00	016	∞	016
			016	∞

Разбиваем множество всех ГК на два: и (решим две подзадачи):

Матрицу ГК , содержащую дугу (2; 3) получаем из последней таблицы, вычеркивая строки 2 и столбца 3. Чтобы не допустить образование негамильтонова контура, заменяем элемент на ∞:             00             ∞ 016       00 016 ∞ 016         016 ∞               Находим . Итак, нижняя граница множества равна

Матрицу ГК , не содержащую дугу (2; 3) получаем из последней таблицы путем замены элемента на ∞:           min   ∞             ∞ 00               ∞ 016         00 016 ∞ 016           016 ∞                 Находим . Итак, нижняя граница множества равна

Сравниваем нижние границы подмножеств и . Так как , дальнейшему ветвлению подвергаем подмножество . Находим степени нулей этой матрицы:

	0113
		∞	016
	00	016	∞	016
			016	∞

	0113
		∞	016
			016

Претендентом на включение в ГК является дуга (6; 7) с наибольшей степенью 0. Разбиваем множество всех ГК на два: и (решим две подзадачи):

0113           ∞ 016         ∞             0113         ∞ 016       ∞ Находим . Итак, нижняя граница множества равна

0113             ∞ 016       00 016 ∞ ∞         016 ∞               0113           ∞ 016     00 016 ∞ ∞       016 ∞           Находим . Итак, нижняя граница множества равна

Сравниваем нижние границы подмножеств и . Так как , дальнейшему ветвлению подвергаем подмножество .

	0113
		∞	0113
		0760	∞

	0113
		0113

Дальнейшему ветвлению подвергаем подмножество . Но его матрица имеет размерность 2×2. Поэтому в гамильтонов контур следует включить дуги (хотя может быть и не все), соответствующие в матрице подмножества нулевым элементам, т.е. дуги (3; 6) и (5; 4).

Определим полученный ГК:

Его длина:

.