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

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

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

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

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

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

1. По исходным данным запишем матрицу расстояний

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

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

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

	∞			044
		∞	01
		00	∞			00
	044	00		∞
				00	∞		037
			037			∞
		00			036	00	∞

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

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

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

		∞	01
		00	∞		00
	044	00
				∞		037
			037		∞
		00		036	00	∞

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

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

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

		∞	037
		00	∞		00
	∞	013
				∞		080
			01		∞
	01	00		036	00	∞

		∞	037
		00	∞		00
	∞	013
			01		∞
	01	00		036	00

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

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

Матрицу ГК , не содержащую дугу (1; 7) получаем из последней таблицы путем замены элемента на ∞:                 ∞ 037             00 ∞   00       ∞ 013                   ∞   ∞         01   ∞       01 00   036 00 ∞

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

		∞	073
		00	∞		00
	∞	00		044
			01		∞
	01	00		∞	00

		00		00
	∞	00	044
				∞
	01	00	∞	00

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

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

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

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

		∞		056
	∞	00	043
	043			∞
	00	00	∞	00

	∞	00	043
	043
	00	00	∞

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

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

∞   ∞     ∞ 00 043       043     ∞     00 00 ∞ 00

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

	∞	00	043
	043
	00	00	∞

	0735
	00	0735

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

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

Его длина:

.

Составим геометрическую интерпретацию найденного маршрута

При этом семь маршрутов (полученные один из другого по циклу):

Минимальная длина маршрута составляет 1235 км.