Путь максимальной эффективности.

пути m определяется как отношение его эффекта Э^) = ^ Э*}- к

m

затратам S(m) = ^ sij, то есть K(m) = Э^) / S(m). Задача заключа-

m

ется в поиске пути m максимальной эффективности: K(m) ® max.

Если решение K = K(m*) этой задачи известно, то по определению K выполнено:

(8) э^) - k* S(m) < 0 vm

Следовательно, задача свелась к поиску минимального значения K , для которого имеет место (8). Другими словами, необходимо найти минимальное K, такое, что все пути (длина которых определяется как li](K) = Эу - K Siy) в сети имеют неположительную длину (неравенство (8) должно выполняться, в том числе, и для пути максимальной длины).

Алгоритм 6. 1) Положим K = 0. Находим путь mi максимальной длины. Положим K1 = Э^) /S(m1) (заметим, что при K = K1 длина пути m(K1) равна нулю).

2) Находим максимальный путь m2 при K = K1. Если длина пути m2, которую мы обозначим L(K1), равна нулю, то задача решена. Если L(K1) > 0, то вычисляем K2 = Э(^ц2) / S(m2) и находим максимальный путь m2 при K = K2 и т.д.