Page 41 - 4336

При ррозглядіі шляхуу M(e , e ,…, ee ), за ййого ваагу (абоо
m
2
1
доввжину, аббо вартість) берруть числло L(M), рівне суумі ваг ввсіх дуг,,
m
що входятьь в шлях,, тобто L ML( )    i m
c дляя всіх e M.
i1

Прикллад 4.1. На рисс. 4.2 зоображенний графф зі звааженимии

дуггами, якиий преддставляє мережуу припуустимих маршруутів дляя

деякого траанспортнного зассобу. Коожна дуга має ппозначкуу (a, b),,

приичому a дорівнюює вигодді, що оддержуєтьься при обслугоовуванніі

данного марршруту, а b – чаасу обсллуговуваання марршруту. Знайтии

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

зоруу швидккості обоороту каппіталу:

1) ABСDEA;

2) ABСEDA;

3) ADBСEA;

4) AСEDBA.

Рисунокк 4.2.

Дуги ВВага ДДуги ВВага Д Дуги Вагга

AB (1, 2) BBC (66, 9) DDB (3, 2)

AC (9,6) CCB (44, 9) DDE (8, 8)

AD (10, 3) CCD (114, 4) EA (155, 9)

AE (20, 9) CCE (88, 6) ED (155, 8)

BA (1, 2) DDA (110, 4)

41