Транспортные задачи в сетевой постановке (транспортные сети)
Модель Тd-задачи в сетевой постановке имеет вид: åå Cijxij ®min; В модели использованы обозначения: Алгоритм Дейкстры-Форда: Суть задачи сводится к поиску самого короткого пути, который бы соединял две точки ориентированного графа. Суть алгоритма в постепенной пометке всех вершин графа, т.е. поиске наикратчайших путей от начальной вершины ко всем остальным.
Пример: Итерация 1:E0=0 R={0}
Итерация 2: Ит. 3: Итерация 5: Два пути: 1)
|
Транспортную задачу можно представить в виде ориентированного графа с одним истоком (в него не входит ни одна дуга) и с одним стоком (из него не выходят дуги), - сеть. Вершины графа - ПО, ПН и промежуточные пункты. Параметр вершины – количество груза. Дуги отображают коммуникации. Им могут быть приписаны количество груза, затраты на перевозку, пропускная способность. Исходный граф транспортной задачи легко сводится к сети с одним стоком и одним истоком путем введения фиктивных пунктов t (исток) и s (сток). Фиктивным дугам приписываются значения параметров: dti=ai, djs=bj, Cti=Cjs =0.
k ¹ t, k ¹ s; 
В сбалансированной транспортной задаче Z =å a i=å bj; 0£ xij £ dij.
– множество дуг, входящих в вершину k и выходящих из нее, Z – новая величина - поток сети.
Первая формула вычисляет длину пути от начальной вершины до данной непомеченной по указанному пути, а вторая формула выбирает какую вершину внести во множество помеченных вершин и с какой пометкой.
Так же используется проверка, что путь через новую помеченную вершину к какой-либо другой помеченной вершине не окажется меньше уже помеченного: 
. Если проверка не проходит, то меняем пометку у указной вершины.
E1=2R={0,1}
E2=7R={0,1,2}
E4=11, E2=5 R={0,1,2,4} Ит. 4: 
E3=13 R={0,1,2,3,4}
Et=14
2) 
