Транспортные задачи в сетевой постановке (транспортные сети)

Транспортную задачу можно представить в виде ориентированного графа с одним истоком (в него не входит ни одна дуга) и с одним стоком (из него не выходят дуги), - сеть. Вершины графа - ПО, ПН и промежуточные пункты. Параметр вершины – количество груза. Дуги отображают коммуникации. Им могут быть приписаны количество груза, затраты на перевозку, пропускная способность. Исходный граф транспортной задачи легко сводится к сети с одним стоком и одним истоком путем введения фиктивных пунктов t (исток) и s (сток). Фиктивным дугам приписываются значения параметров: d_ti=a_i, d_js=b_j, C_ti=C_js =0.

Модель Т_d-задачи в сетевой постановке имеет вид: åå C_ijx_ij ®min; k ¹ t, k ¹ s; В сбалансированной транспортной задаче Z =å a _i=å b_j; 0£ x_ij £ d_ij.

В модели использованы обозначения: – множество дуг, входящих в вершину k и выходящих из нее, Z – новая величина - поток сети.

Алгоритм Дейкстры-Форда:

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

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

Так же используется проверка, что путь через новую помеченную вершину к какой-либо другой помеченной вершине не окажется меньше уже помеченного: . Если проверка не проходит, то меняем пометку у указной вершины.

Пример:

Итерация 1:E₀=0 R={0}

E₁=2R={0,1}

Итерация 2: E₂=7R={0,1,2}

Ит. 3: E₄=11, E₂=5 R={0,1,2,4} Ит. 4: E₃=13 R={0,1,2,3,4}

Итерация 5: E_t=14

Два пути: 1) 2)