Сетевые модели перевозок. Кратчайший маршрут на сети.

Некоторые определения. Пусть задано множество X = { х₀, х₁, …}, состоящее из элементов х₀, х₁, … х_i, … x_n. Число элементов n может быть конечным или бесконечным. Элементы множества X назовем вершинами графа. Графом – называется множество вершин, соединенных в каком – либо порядке линиями, называемыми ребрами графа. Ребро графа – это линия, соединяющая две его вершины. Ребро обозначается указанием вершин, которые оно соединяет, например g(х₀, х₁), g(х_i, x_j). Форма линии ребра, как правило, не имеет значения.

Ребро может быть ориентированным или неориентированным. Ориентация на ребре указывается стрелками. На ориентированном ребре g(х_i, x_j) одна из вершин х_i является начальной, а другая вершина х_j – конечной. Ориентированное ребро называется дугой.

Граф называется ориентированным, если все его ребра являются ориентированными. В ориентированном графе каждая вершина имеет входящие дуги и исходящие дуги.

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

аршрут на графе задается начальной вершиной х₀, конечной вершиной х_к и последовательностью ребер, их соединяющей. Цепью (для неориентированного графа) называется последовательность ребер

S = (g₁, g₂, …, g_k-1, g_k, g_k+1, …, g_n),

в которой у каждого промежуточного ребра g_k, к = 2, …, n -1 одна из вершин является вершиной предшествующего ребра g_k-1, а другая вершина – вершиной последующего ребра g_k+1. Первое ребро g₁ начинается из начальной вершины и не имеет предшествующих ребер. Последнее ребро g_n заканчивается в конечной вершине и не имеет последующих ребер.

Путь – это цепь, построенная для ориентированных графов. Путь состоит из начальной, конечной вершин и последовательности дуг, у которых начальная вершина каждой промежуточной дуги совпадает с конечной вершиной предыдущей дуги.

Цикл – это цепь, у которой начальная и конечная вершина совпадает. Цикл это замкнутая цепь или замкнутый путь. Сеть, не имеющая циклов называется ациклической.

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

Сетью называется связный ориентированный граф без петель. Вершины сети называются узлами. Узлы удобно обозначать (нумеровать) цифрами. Дуга, соединяющая узел i (начальный узел дуги) и узел j (конечный узел дуги) обозначается парой чисел (i, j). Для каждой дуги (i, j) определена ее мера, называемая длиной дуги. Длина дуги обозначается С_ij. В приложениях длина дуги имеет смысл расстояния (км) между узлами, стоимости перевозки из i -го в j -ый узел, времени движения. Она также называется обобщенной стоимостью.

Система уравнений для длины кратчайших маршрутов. Пусть задана сеть, содержащая n узлов. Пример приведен на рис. 9.1. Первый узел будем считать начальным, а n -ый – конечным. На рис.9.1 число узлов n=8, восьмой узел является конечным. Заданы длины дуг С_ij сети. С помощью длин дуг можно ввести квадратную матрицу

С = (С_ij), i, j = 1, …, n,

число строк и столбцов в которой равно числу узлов; (i, j) – ый элемент матрицы С положим равным длине дуги между i - ым и j -ым узлами, если такая дуга существует, или равным бесконечности, если дуг нет. Диагональные элементы С_ij положим равным нулю, хотя это не всегда имеет смысл. Например, матрица С сети, представленной на рис. 9.1 имеет вид

Построение матрицы осуществляется построчно. Для элементов 1 –ой строки (соответствующих длине дуг, исходящих из 1 –го узла) указываются три значения С₁₂ = 4, С₁₃ = 1, С₁₄ = 6 по всем трем исходящим дугам; элемент С₁₁ = 0; остальные элементы полагаются равными бесконечности. Далее процесс повторяется для 2 – ой и последующих строк.

Сеть – связный граф. Для любых двух узлов существует, по крайней мере, один путь, их связывающий. Следовательно, существует и кратчайший путь. Кратчайший путь представляет собой особый интерес, поскольку он определяет оптимальный маршрут между двумя узлами.

Рассмотрим задачу об определении кратчайшего пути между двумя узлами (для определенности – между начальным первым узлом и конечным n -ым). Для каждого из узлов сети введем длину

U₁, U₂, …, U_i, …U_n

кратчайшего маршрута соответственно между 1, 2, …, n -ым узлами и конечным n-ым узлом. Величина U_n = 0, величину U₁ предстоит определить, величины U₂, …, U_n-1 являются вспомогательными. Мы увидим далее, чтобы найти кратчайший маршрут из 1-го узла нужно вначале определить все величины U_i.

Может быть показано, что величины U₁, …, U_n связаны между собой следующей системой нелинейных алгебраических уравнений[ ]

U_i = min {C_ij + U_j}, i=1, 2, … n-1, U_n=0. (9.2)

j, j≠ i

Уравнения (9.2) записываются для каждого из узлов сети. Минимум в правой части уравнений находится перебором по всем j, что соответствует исходящим дугам. Уравнение (9.2) означает, что оптимальный путь из i -го узла (в конечный n -ый узел) следует в тот узел j_*, в котором сумма

_ij + U_j

принимает минимальное значение. Например, для узла, 2 сети (рис. 9.1) уравнение (9.2) имеет вид

U₂=min{C₂₄+U₄, C₂₅+U₅}.

Для узлов i = 4, 5, связанных между собой двойными дугами, уравнения (9.2) выражают величины U₄ и U₅ друг через друга:

U₄ = min{C₄₈+U₈, C₄₅+U₅}, U₅ = min{C₅₄+U₄, C₅₈+U₈, C₅₆+U₆}.

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

Метод последовательных приближений. Вводятся промежуточные величины:

U₁⁰, U₂⁰, …, U_n⁰;

U₁¹, U₂¹, …, U_n¹; …

U₁^k, U₂^k, …, U_n^k;

где к = 0, 1, …, n -2 – номер приближения (итерации). Значения этих величин при к = n -2 равны искомым значениям

U₁^n-2=U₁, …, U_i^n-2=U_i, …, U_n^n-2=U_n

длин кратчайших маршрутов. Величины U_i^k определяются последовательно по шагам. При к = 0 положим в качестве начального приближения

U_n⁰ = 0, U_i⁰ = C_in, при i = 1, 2, …, n-1,. (9.3)

Нулевое приближение U _i ⁰ равно длине прямого маршрута (без промежуточных узлов) из i -го узла в конечный n -ый узел, если дуга, соединяющая эти узлы, существует. В противном случае величина U_i⁰ полагается равной бесконечности. Значения U_i⁰ равны n -му столбцу матрицы С.

Первое приближение при к = 1 вычисляется по формуле

U_i¹ = min{C_ij + U_j⁰}, i= 1, 2, …, n-1, U_n¹=0. (9.4)

j ≠ i

Здесь в отличие от формул (9.2) все числовые величины в правой части уже известны. Поэтому минимум и, следовательно, величины U_i¹ легко находятся.

Величины U_i¹ определяют длину кратчайшего маршрута с числом промежуточных (транзитных) узлов не более 1. Если для некоторого i -го узла величина U_i¹ = ¥, это означает, что отсутствуют как дуги, связывающие его напрямую с конечным узлом, так и пути через 1 промежуточный узел. Если величина U_i¹ - конечна и минимум в равенстве (9.4) достигается при некотором узле j_*, j_* ≠ n, то ее значение определяет длину маршрута

i → j_* → n

с одним промежуточным узлом. Если же величина U_i¹ - конечна и минимум достигается в узле j_* = n, то значение U_i¹ равно длине пути i → n без промежуточных узлов. Заметим, что такой маршрут может и не быть оптимальным.

Произвольные к -ые итерации далее вычисляются по формуле

U_i^k = min{C_ij + U_j^(k-1)}, I = 1, 2, …, n-1, U_n^k = 0, (9.5)

j ≠ i

где значения U_i^(k-1) определяются на предыдущих шагах. Значение U_i^k определяют длину кратчайшего пути из i -го в n -ый узел с числом промежуточных узлов не более k. Поскольку для искомого кратчайшего маршрута из 1-го узла в n -ый число промежуточных узлов не может быть более (n-2), то итерации при к = n -2 прекращаются. Полученные значения U_i^(n-2) определяют длину кратчайшего маршрута.

Прокладка оптимального маршрута. После определения величин U₁, …, U_n нахождение кратчайшего маршрута осуществляется с помощью уравнений (9.2), которые записываются для узлов, лежащих на оптимальном маршруте. При i = 1 имеем равенство

U₁ = min{C_1j + U_j}, (9.5)

j ≠ 1

находим узел j₁ на котором этот минимум достигается. Первая дуга кратчайшего маршрута проложена 1 → j₁. Записываем далее уравнения (9.2) для узла i = j₁:

U_j1 = min{C_{j1, j} + U_j}.

j≠ j₁

Найдя узел j₂, на котором здесь достигается минимум, прокладываем кратчайший маршрут далее: 1 → j₁ → j₂. Этот процесс обрывается по достижению конечного n -го узла. Число шагов, которые необходимо сделать, как уже нами отмечалось, не может быть более (n -2).