Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

Моделирование транспортных процессов

Автор:   •  Декабрь 1, 2024  •  Контрольная работа  •  1,579 Слов (7 Страниц)  •  16 Просмотры

Страница 1 из 7

Содержание

Введение…………………………………………………………………………….6

Цель работы………………………………………………………………………..7

1 Модели транспортных сетей………………………………………….8

2  Метод Дейкстры (потенциалов) расчёта кратчайших расстояний и пути проезда….…………………………………………………………………11

3 Постановка транспортной задачи, математическая модель…..14

4 Построение матрицы оптимальных грузопотоков……………….15

Заключение………………………………………………………………………18

Список литературы……………………………………………………………..19

Введение

Транспортная сеть (или линейный граф) состоит из определенного числа узлов (вершин) и дуг, соединяющих различные пары узлов. На каждой дуге задана определенная ориентация (определенное направление). Поэтому говорят, что сеть является ориентированной. Для описания ориентированной сети необходимо пронумеровать узлы числами натурального ряда 1, 2, и т.д. и обозначить дуги, исходящие из узла i и входящие в узел j, парой номеров (i, j). Последовательность дуг (без учета их ориентации), соединяющая узлы i и j, называется путем между этими узлами. Если i = j, то путь называется контуром. Сеть является связной при условии, что существует, по крайней мере, один путь между любой парой узлов. Сеть, содержащая P узлов и P1 дуг, носит название дерева и не содержит контуров. При определении сети задают пропускную возможность дуг Rij ≥ 0 по отношению к общему потоку, выходящему из узла i и входящему в узел j. При решении транспортной задачи в матричной форме величина Rij принимается равной бесконечности, либо нулю. В первом случае это означает, что никаких ограничений на величину потока по дуге не накладывается, а во втором – что поток непосредственно между узлами i и j не допускается. Кроме этого, в прикладных задачах, сеть дополнительно характеризуется величиной чистого потока и стоимостью доставки единицы потока из узла i в узел j, то есть стоимостью единичного потока по дуге (i, j). Если значение величины чистого потока Qk положительно, то из узла должно выходить на Qk единиц потока больше, чем входить в него, и наоборот, когда значение Qk отрицательно. Если значение Qk равно нулю, то весь поток, входящий в узел, равен потоку, выходящему из него


  1. Модели транспортных сетей

[pic 1]

Рисунок 3 – Модель транспортной системы

  1. Метод Дейкстры (потенциалов) расчета кратчайших расстояний и путй проезда

Вершине, от которой требуется определить кратчайшее расстояние, присваивается потенциал, равный нулю.

Шаг 1. Отыскиваются звенья, в которых начальные вершины i имеют потенциалы vi, а конечные j не имеют. Значения потенциалов конечных вершин vj определяются по формуле:

vj = vi + cij,

где cij – длина звена (i,j).

Шаг 2. Если потенциал вершины j определен неоднозначно, в расчетах оставляют наименьшее значение vj. Из всех полученных от начала расчетов и неприсвоенных вершинам потенциалов выбирается наименьший. Его значение присваивается конечной вершине.

Шаг 3. Звено (i,j) отмечается стрелкой.

 Действия повторяются, начиная с шага 1, до присвоения потенциалов всем вершинам. Величина потенциала у соответствующей вершины показывает кратчайшее расстояние до данного пункта. Звенья со стрелками образуют кратчайший маршрут движения от исходной вершины до всех остальных.

Рассчитаем расстояния до каждой из вершин:

Таблица 1 – Расчёт для вершины 8

Вершины с однозвенной связью

-

V8=0

8

V7=0+5=5, V13=0+6=6, V9=0+7=7, min (V7, V13, V9)=V7=5

7

V6=5+4=9, V8=5+5=10,min (V13, V9, V6)=V13=6

13

V8=6+6=12, V9=6+8=14, V10=6+6=12, V11=6+6=12, V12=6+8=14, V20=6+7=13 min (V9, V6, V11,V12,V20)=V9=7

9

V8=7+7=14, V13=7+8=13, V10=7+5=12, min (V6, V11, V12, V20,V10)=V6=9

6

V5=9+4=13, V20=9+7=16, V7=9+4=13 min (V11, V12, V20, V10, V5)=V11=12

11

V10=12+4=16, V12=12+5=17, V13=12+6=18, min (V12, V20, V10, V5,)=V10=12

10

V9=12+5=17, V13=12+6=18, V11=12+4=16, min (V12, V20, V5)=V5=13

5

V6=13+4=17, V4=13+8=21, min (V12, V20)=V20=13

20

V6=13+7=20, V4=13+7=20, V15=13+5=18, V14=13+5=18, V13=13+7=20, min (V12, V4, V15, V14)=V12=14

12

V20=14+5=19, V12=14+5=19, min (V4, V15, V14)=V14=18

14

V20=18+5=23, V12=18+5=23, min (V4, V15)=V15=18

15

V17=18+5=23, V16=18+5=23, V12=18+7=25, V20=18+5=23, min (V4)=V4=20

4

V3=20+3=23, V5=20+8=28, V17=20+8=28, V20=20+7=27, min (V3, V16, V17)=V3=23

3

V1=23+5=28, V4=23+3=26, V2=23+5=28, min (V1, V16, V17)=V16=23

16

V12=23+8=31, V15=23+5=28, V17=23+5=28, V18=23+7=30 min (V17)=V17=23

17

V16=23+5=28, V15=23+5=28, V4=23+5=28, V2=23+5=28, V18=23+2=25,min (V18, V1, V2)=V18=25

18

V16=25+7=32, V17=25+2=27 , V2=25+5=30, V19=25+5=30,min (V19, V2, V1)=V2=28

2

V3=28+5=33, V1=28+4=32, V18=28+5=33, V17=28+5=33 min (V19, V1)=V1=28

1

V3=28+5=33, V2=28+4=32, V19=28+5=33, min (V19)=V19=30

Таблица 2 – Расчёт для вершины ГОП микрорайона №19

Вершины с однозвенной связью

-

V19=0

19

V18=0+5=5, V1=0+5=5, min (V18, V1)=V18=5

18

V16=5+7=12, V17=5+2=7, V2=5+5=10, V2=5+5=10, V19=5+5=10,min (V1, V17)=V1=5

1

V19=5+5=10, V2=5+4=9,V3=5+5=10, min (V17, V2,V3)=V17=7

17

V16=7+5=12, V15=7+5=12, V4=7+8=15, V2=7+5=12, V18=7+2=9 min (V2, V3,V15,V16)=V2=9

2

V18=9+5=14, V17=9+5=14, V3=9+5=14, V1=9+4=13, min (V3,V15,V16)=V3=10

3

V1=10+5=15, V2=10+5=15, V4=10+3=13, min (V6, V15,V16,V4)=V15=12

15

V16=12+5=17, V12=12+7=19, V20=12+5=17, V17=12+5=17, min (V12,V20, V4)=V16=12

16

V12=12+8=20, V15=12+5=17, V17=12+5=17, V18=12+7=19, min (V12, V20, V4)=V4=13

4

V5=13+8=21, V20=13+7=20, V17=13+8=21, V3=13+3=16, min (V12, V20, V5)=V20=17

20

V15=17+5=22, V14=17+5=22, V13=17+7=24, V6=17+7=24, V4=17+7=24, min (V6, V12, V13, V14)=V12=19

12

V11=19+5=24, V13=19+8=27, V14=19+5=24, V15=19+7=26, V16=19+8=27, min (V6, V13, V14, V11)=V5=21

5

V6=21+4=25, V4=21+8=29, min (V6, V13, V14,V11)=V14=22

14

V12=22+5=27, V20=22+5=27, min (V6, V13,V11)=V11=24

11

V10=24+4=28, V13=24+6=30, V12=24+5=29, min (V6, V13, V10)=V13=24

13

V12=24+8=32, V11=24+6=30, V10=24+6=30, V9=24+8=32, V8=24+6=30, V20=24+7=31, min (V6, V10, V8, V9)=V6=24

6

V7=24+4=28, V20=24+7=31, V5=24+4=28, min (V10, V8, V9,V7)=V7=28

7

V8=28+5=33, V6=28+4=32, min (V10, V8, V9)=V10=28

10

V9=28+5=33, V13=28+6=34, V11=28+4=32,min (V9,V8)=V8=30

8

V13=30+6=36, V9=30+7=37, V7=30+5=35,min (V9)=V9=32

...

Скачать:   txt (19.9 Kb)   pdf (250.8 Kb)   docx (102.5 Kb)  
Продолжить читать еще 6 страниц(ы) »
Доступно только на Essays.club