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

Пусть задана сеть, в которой для каждой дуги (i; j) определены два числа (Э*}-; Sj), интерпретируемые как эффект при осуществлении соответствующей операции - Эу и затраты на эту операцию - Sj. Эффективность K(m)
пути 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 и т.д.
<< | >>
Источник: В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. 2001

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

  1. Путь максимальной эффективности с учетом штрафов.
  2. Зрительный путь и путь зрачкового рефлекса
  3. ПРОИЗВОДИТЕЛЬНОСТЬ ТРУДА И ЭФФЕКТИВНОСТЬ ПРОИЗВОДСТВА. ЭВОЛЮЦИЯ СИСТЕМЫ КРИТЕРИЕВ ЭФФЕКТИВНОСТИ ТРУДОВОЙ ДЕЯТЕЛЬНОСТИ
  4. Максимальный гуманизм
  5. Вероятный максимальный убыток
  6. Максимально возможный фонд времени
  7. 1.4.3. Максимальная сила и божественная благость
  8. Задача о максимальном потоке
  9. Вероятный максимальный убыток
  10.   ОБ ИЗМЕНЕНИЯХ, ПРЕТЕРПЕВАЕМЫХ МАКСИМАЛЬНОЙ И БЕСКОНЕЧНОЙ ЛИНИЕЙ 
  11. Максимально возможный фонд рабочего времени
  12. 26. Принцип максимальной дифференциации
  13. 3.4.3. Алгоритм построения максимального потока в транспортной сети
  14. 5.3. Формирование максимальных по объему подмножеств оптимальных последовательностей
  15. Максимальная анонимность.
  16. ЗАЛОГ МАКСИМАЛЬНЫЙ
  17. МАКСИМАЛЬНО ИЗМЕНЧИВЫЙ