МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МАДИ (ТУ)

КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ

СИСТЕМ

Выполнил: Белоногов М.В.

Группа 4ВЭДС3

Проверил: Беляков Г.С.

Москва 1999-2000

Раздел 1.

Выбор оптимального маршрута поездки.

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

Машина с инкассатором ежедневно забирает выручку 4-х торговых точек (пункты
Б, В, Г, Д), расположенных на разных улицах города и отвозит ее в банк
(пункт А). Определено время на проезд по различным улицам с учетом интенсивности движения по ним транспортного потока. Требуется найти маршрут движения инкассаторской машины, который начинался и заканчивался бы в пункте А, позволял посетить каждую торговую точку и проехать по соответствующей улице только один раз и характеризовался минимальными затратами времени на поездку. Маршрут должен включать переезд из пункта Б в пункт Г.

Порядок решения задачи:

1. Определить кратчайшие расстояния между различными парами пунктов используя алгоритм поиска кратчайших путей на циклической сети.

А 1 Б

4 В 2

Д 3 Г

Найдем кратчайшие расстояния до пункта А.

|пункт |А |Б |В |Д |1 |4 |
|i | | | | | | |
|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

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