Гілкування по множині G2 призводить до тієї ж самої схеми, тільки рух судна буде здійснюватися в зворотному напрямку

Одеса – Стамбул – Хайфа – Александрія – Валета – Барселона-Неаполь – Афіни – Одеса

Протяжність лінії складає:

L = 652 + 737 + 558 + 671 + 818 + 235 + 247 + 298 = 4216 миль.

Решение задачи коммивояжера с использованием надстройки MS EXCEL «Поиск решения»

Задача. Найти решение задачи коммивояжера для графа с заданной матрицей расстояний с использованием надстройки «Поиск решения».

Исходные данные:

Порты захода	Порты захода
Одесса	Афины	Неаполь	Барселона	Валлетта	Алек-я	Хайфа	Стамбул
Одесса (1)
Афины (2)
Неаполь (3)
Барселона (4)
Валлетта (5)
Александрия (6)
Хайфа (7)
Стамбул (8)

1) Представим на рабочем листе MS EXCEL исходные данные, подготовим ячейки для переменных, ограничений (массив для ограничений должен иметь на 1 строку и 1 столбец меньше чем в исходных данных) и целевой функции:

2) В ячейки В19:I19 введем формулы для расчета суммы переменных по столбцам:

	B	C	D	E	F	G	H	I
	=СУММ(B11:B18)	=СУММ(C11:C18)	=СУММ(D11:D18)	=СУММ(E11:E18)	=СУММ(F11:F18)	=СУММ(G11:G18)	=СУММ(H11:H18)	=СУММ(I11:I18)

В ячейки J11:J18 введем формулы для расчета суммы переменных по строкам:

	J
	=СУММ(B11:I11)
	=СУММ(B12:I12)
	=СУММ(B13:I13)
	=СУММ(B14:I14)
	=СУММ(B15:I15)
	=СУММ(B16:I16)
	=СУММ(B17:I17)
	=СУММ(B18:I18)

В целевую ячейку С32 введем формулу, рассчитывающую сумму произведений двух массивов – исходных данных (B2:I9) и переменных (B11:I18).

	С
	=СУММПРОИЗВ(B2:I9;B11:I18)

В ячейки С24:I30 (ограничения) введем формулы:

	C	D	E	F	G	H	I
		=$C$21-D21+8*D12	=$C$21-E21+8*E12	=$C$21-F21+8*F12	=$C$21-G21+8*G12	=$C$21-H21+8*H12	=$C$21-I21+8*I12
	=$D$21-C21+8*C13		=$D$21-E21+8*E13	=$D$21-F21+8*F13	=$D$21-G21+8*G13	=$D$21-H21+8*H13	=$D$21-I21+8*I13
	=$E$21-C21+8*C14	=$E$21-D21+8*D14		=$E$21-F21+8*F14	=$E$21-G21+8*G14	=$E$21-H21+8*H14	=$E$21-I21+8*I14
	=$F$21-C21+8*C15	=$F$21-D21+8*D15	=$F$21-E21+8*E15		=$F$21-G21+8*G15	=$F$21-H21+8*H15	=$F$21-I21+8*I15
	=$G$21-C21+8*C16	=$G$21-D21+8*D16	=$G$21-E21+8*E16	=$G$21-F21+8*F16		=$G$21-H21+8*H16	=$G$21-I21+8*I16
	=$H$21-C21+8*C17	=$H$21-D21+8*D17	=$H$21-E21+8*E17	=$H$21-F21+8*F17	=$H$21-G21+8*G17		=$H$21-I21+8*I17
	=$I$21-C21+8*C18	=$I$21-D21+8*D18	=$I$21-E21+8*E18	=$I$21-F21+8*F18	=$I$21-G21+8*G18	=$I$21-H21+8*H18

3) На панели инструментов открываем Сервис à Поиск решения и в открывшемся диалоговом окне вводим следующие значения и параметры:

Нажимаем ОК и получаем значение целевой функции и оптимальный контур:

Таким образом, оптимальная протяженность маршрута 4216 миль.

Оптимальный маршрут: Одесса – Стамбул – Хайфа – Александрия – Валлетта – Барселона – Неаполь – Афины – Одесса.

Дата добавления: 2015-06-27