Алгоритмы определения экстремальных путей в графах (то есть

путей максимальной или минимальной длины) достаточно хорошо

известны и описаны в литературе [1]. Для нашего случая наиболее

эффективен алгоритм определения кратчайших путей при правильной

нумерации вершин сети. Напомним, что нумерация вершин называется

правильной, если для любой дуги (i, j) имеет место i < j. В этом случае

кратчайший путь определяется на основе последовательного

присвоения вершинам сети индексов qi согласно следующей процедуре

(индекс вершины 1 принимается равным 0):

j ji 

j i

qi min q s



,

где sji – длина дуги (j, i). В этом случае индекс последней вершины qm+1

будет равен длине кратчайшего пути или величине минимальных

затрат. Путь минимальной длины определяется на основе процедуры

«обратного хода». Опишем эту процедуру. Находим вершину i1, такую

что

m 1 i1 i1,m 1 q q s .

Если i1 1, то находим вершину i2, такую что

qi1 qi2 si2 ,i1 .

Продолжаем таким образом, пока на очередном шаге k не получим

ik = 1, то есть

qik 1 q1 s1,ik 1 

.

Путь = (1, ik-1, ik-2, ... , i1, m+1) и является путем минимальной длины.

Применим этот алгоритм к сети, рис. 2.6. Индексы вершин указаны в

нижней половине соответствующего кружка. Имеем:

q1 = 0;

q2 = 0 + 50 = 50;

q3 = 50 + 50 = 100;

q4 = 100 + 15 = 115;

41 q = 0 + 111,6 = 111,6;

42 q = 50 + 114,1 = 164,1;

q5 = min [111,6 + 75; 115 + 85; 50 + 139,5; 164,1 + 25] = 186,6

q6 = min [216,9; 186,6 + 20; 111,6 + 84; 115 + 89,6; 100 + 104,6;

164,1 + 56; 50 +160,7] = 195,6.

(2.1)

Кратчайший путь, определенный методом «обратного хода»

выделен толстыми дугами. Это путь (1, 41, 6), которому соответствует

следующий вариант закупок. В момент 1 = 5 закупается партия

продукции в объеме 25 ед. по льготной цене. Такая же партия в 25 ед.

по льготной цене закупается в момент 4 = 20. Суммарные затраты на

оплату продукции и ее хранение на складе с учетом дохода от 6 ед.

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

оптовой закупкой всей продукции в объеме 44 ед. в момент 1 = 5

получаем экономию 216,9 – 195,6 = 21,3 тыс. руб. По сравнению с

другим крайним вариантом закупки объемов i в момент i получаем

экономию 220 – 195,6 = 24,4 тыс. руб.