Реферат: Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера

y_Б + l_1Б =16,64+8=24,64 > y₁ =8,32

Теперь проверим условие l_ij ³ y_i - y_j для всех дуг сети.

l_4A = у₄ - у_А 9=9-0

l_4Д >у₄ – у_Д 8,32>9-17

l_Д4 = у_Д – у₄ 8=17-9

l_ДВ >у_Д – у_В 12>17-13

l_BA = y_B - y_A 13=13-0

l_BД > y_B – y_Д 12,32>13-17

l_BБ > y_B – y_Б 15,32>13-16,64

l_B4 > y_B – y₄ 7>13-9

l_B1 > y_B – y₁ 10>13-8,32

l_БВ >у_Б - у_В 15>16,64-13

l_Б1 = у_Б – у₁ 8,32=16,64-8,32

l_1А = у₁ – у_А 8,32=8,32-0

l_1В >у₁ – у_В 9>8,32-13

l_1Б >у₁ – у_Б 8>8,32-16,64

Чтобы найти кратчайшие пути, найдем дуги для которых выполняется условие:

l_ij = y_i - y_j

Таковыми являются:

l_4A = у₄ - у_А 9=9-0

l_Д4 = у_Д – у₄ 8=17-9

l_BA = y_B - y_A 13=13-0

l_Б1 = у_Б – у₁ 8,32=16,64-8,32

l_1А = у₁ – у_А 8,32=8,32-0

Кратчайшие расстояния до пункта А равны:

пункт	4	Д	Б	1	В
расстояние до А	9	17	16,64	8,32	13

Аналогичным образом находятся кратчайшие расстояния до других пунктов.

2. Построить матрицу кратчайших расстояний между пунктами А, Б, В, Г, Д.

А	Б	В	Г	Д
А	---	16	13,32	---	17,64
Б	16,64	---	15	21	---
В	13	15,32	---	15	12,32
Г	---	21,64	15,32	---	16
Д	17	---	12	16,32	---

3. Математическая модель задачи коммивояжера:

Найти минимальное значение целевой функции z