Математическое моделирование экономических систем
Постановка задачи:
Машина с инкассатором ежедневно забирает выручку 4-х торговых точек (пункты Б, В, Г, Д), расположенных на разных улицах города и отвозит ее в банк (пункт А). Определено время на проезд по различным улицам с учетом интенсивности движения по ним транспортного потока. Требуется найти маршрут движения инкассаторской машины, который начинался и заканчивался бы в пункте А, позволял посетить каждую торговую точку и проехать по соответствующей улице только один раз и характеризовался минимальными затратами времени на поездку. Маршрут должен включать переезд из пункта Б в пункт Г.
Порядок решения задачи:
Определить кратчайшие расстояния между различными парами пунктов используя алгоритм поиска кратчайших путей на циклической сети.
Найдем кратчайшие расстояния до пункта А.
|
пункт 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
Чтобы найти кратчайшие пути, найдем дуги для которых выполняется условие:
lij = yi - yj
Таковыми являются:
l4A = у4 - уА 9=9-0
lД4 = уД – у4 8=17-9
lBA = yB - yA 13=13-0
lБ1 = уБ – у1 8,32=16,64-8,32
l1А = у1 – уА 8,32=8,32-0
Кратчайшие расстояния до пункта А равны:
|
пункт |
4 |
Д |
Б |
1 |
В |
|
расстояние до А |
9 |
17 |
16,64 |
8,32 |
13 |
Аналогичным образом находятся кратчайшие расстояния до других пунктов.
Построить матрицу кратчайших расстояний между пунктами А, Б, В, Г, Д.|
А |
Б |
В |
Г |
Д |
|
|
А |
--- |
16 |
13,32 |
--- |