Математическое моделирование экономических систем Раздел 1. Выбор оптимального маршрута поездки.

Постановка задачи:

Машина с инкассатором ежедневно забирает выручку 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

Рекомендуем скачать другие рефераты по теме: таможенные рефераты, изложение по русскому языку 7.



1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки