Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжераРефераты >> Математика >> Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера
Раздел 1.
Выбор оптимального маршрута поездки.
Постановка задачи:
Машина с инкассатором ежедневно забирает выручку 4-х торговых точек (пункты Б, В, Г, Д), расположенных на разных улицах города и отвозит ее в банк (пункт А). Определено время на проезд по различным улицам с учетом интенсивности движения по ним транспортного потока. Требуется найти маршрут движения инкассаторской машины, который начинался и заканчивался бы в пункте А, позволял посетить каждую торговую точку и проехать по соответствующей улице только один раз и характеризовался минимальными затратами времени на поездку. Маршрут должен включать переезд из пункта Б в пункт Г.
Порядок решения задачи:
1. Определить кратчайшие расстояния между различными парами пунктов используя алгоритм поиска кратчайших путей на циклической сети.
А 1 Б
 |  | ||||||||
 | |||||||||
 | |||||||||
 | |||||||||
4 В 2
 | |||||||||||
 | |||||||||||
 |  | ||||||||||
| |||||||||||
| |||||||||||
Д 3 Г
Найдем кратчайшие расстояния до пункта А.
|
пункт i |
А |
Б |
В |
Д |
1 |
4 |
|
yi |
0 |
¥ |
¥ |
¥ |
¥ |
¥ |
|
28 |
13 |
17 |
8,32 |
9 | ||
|
16,64 |
Первоначально принимаем расстояния до пункта А равными бесконечности, а расстояние от А до самого себя равным нулю.
Затем пересчитываем величины yi используя правило:
Если yj + lij < yi , то величина yi = yj + lij , в противном случае yi оставляем без изменений. Расчет начинаем с пункта А и дуг, которые в него входят.
yA + l4A=0+9=9 < y4=¥ Þ y4=9
yA + lBA=0+13=13 < yB=¥ Þ yB=13
yA + l1A=0+8,32=8,32 < y1=¥ Þ y1=8,32
Теперь рассматриваем пункт i для которого yi перестала быть равной бесконечности и дуги, которые в него входят.
y4 + lB4=9+7=16 > yB=13
y4 + lД4=9+8=17 < уД=¥ Þ yД=17
yВ + lДВ=13+12=25 > yД=17
yВ + lБВ=13+15=28 < уБ=¥ Þ yБ=28
yВ + l1В=13+9=22 > у1=8,32
y1 + lВ1=8,32+10=18,32 > yВ=13
y1 + lБ1=8,32+8,32=16,64 < уБ=28 Þ yБ=16,64
yД + l4Д=8,32+17=25,32 > y4=9
yД + lВД=17+12,32=29,32 > yВ=13
yБ + lВБ=16,64+15,32=31 > yВ=13
yБ + l1Б=16,64+8=24,64 > y1=8,32
Теперь проверим условие lij ³ yi - yj для всех дуг сети.
l4A = у4 - уА 9=9-0
l4Д > у4 – уД 8,32>9-17
lД4 = уД – у4 8=17-9
lДВ > уД – уВ 12>17-13
lBA = yB - yA 13=13-0
lBД > yB – yД 12,32>13-17
lBБ > yB – yБ 15,32>13-16,64
lB4 > yB – y4 7>13-9
lB1 > yB – y1 10>13-8,32
lБВ > уБ - уВ 15>16,64-13
lБ1 = уБ – у1 8,32=16,64-8,32
l1А = у1 – уА 8,32=8,32-0
l1В > у1 – уВ 9>8,32-13
l1Б > у1 – уБ 8>8,32-16,64
