На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна.
Скорость оборота капитала n -го пути судна найдем как суммарную выгоду пути, деленную на суммарное время, т. е.
vn=∑ ai/ ∑ bi