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

Содержание

Введение…………………………………………………………………………….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