0000105

jogo poprzedniki z CT"¹(x) cechaai (x” ,min { C( x), f(z,x) -- l(z.x)J) o ilo opołniajo werunok f(z,x) >l(z,x).

12.4. Przepływ minimalny w sieci S ■ <G. {•} ,{1 ,h}>

Stooujęc założenia i oznaczonia jak w punkcie 12.3, przepływ alnlaalny w rozpatrywanej aieci okreólomy Joko taki przepływ dopuszczalny f_oln^e F . który apołnia warunek

^v<'.ln) ■ _f“ⁿF^V<,)

Przopływ minimalny możemy wyznaczyć wykorzystując algorytm wyznaczanio przopływu dopuozczalnogo (punkt 12.2) oraz odpowiod-nio zmodyfikowano procedurę wyznaczonia łańcuchów powiękozal -nych, wykorzyotywano w algorytmie wyznaczonia maksymalnego przepływu w oieci otandordowej

Procedura »

(1)    wyznaczony przepływ dopuszczalny f.

Dożęli przepływ dopuszczalny nie istnieje, to nie istnieje również przepływ minimalny (KONIEC).

(2)    Przyjmujoc f Jako przopływ poczotkowy, realizujemy procedurę wyznaczonia przopływu maksymalnego, przy nootępujo -cym zmienionym spooobie ocochowonia wierzchołków. Spraw -dzajoc ocechowany i niesprawdzony wierzchołek x, cechujemy wszystkie Jego następniki y er(x), spełniajęce warunek f(x,y) > l(x,y), cochg (x". min{c(x), f(x,y) - l(x,y)}, natomiast wszystkie Jogo poprzedniki zer ^ł(x), spełnia-Jęco warunek f(z,x)< h(z,x), cechę (x⁺, ain{c,(x), h(z,x) -- f(z,x)}).

Rozdział 13

NAJTAŃSZY PRZEPŁYW ZA6POKA3A3ĄCY

\

13.1. Przepływ zaepokajejęcy

Oędzlo rozpetrywono sytuacje, w której nomy do czynionln ze zbiorem magazynów M oraz zbiorem odbiorców T. W magazynach eo zapaay towaru a(m); men. natomlaet odbiorcy maję zapotrzebowania o wortoóclach o(t); t £T. Towary naloty przeełać pa elecl dróg o ograniczonych przepustowbściach. w tej sytuacji, pomimo dostatecznej Hotel zapasów moto być nionoillwo zaspo -kojenie potrzob odbiorców (w tędanym okroole czasu) ze względu na nlewyatarczajęcę przepustowość elocl dróg.

Foroolnlo, sytuację przodatawiony zo ponocę eiecl S (ry -eunek 13.1)

S ■ <C.{a} ,{h.k}>    , gdzie

C ■ <X, U> graf Berge'a bez pętli;

X • MuLuT ; UC X » X ;

■ «    ;    a(x) ■ O ;

M ■    { x C    X    J    a( x )    >    0} ;

L •    { x £    X    X    a(x)    -    o) I

T •    (x €    X    j    a(X)    <    O} ;

L - X\(HWT) ;

h j U -* S. {o} ,h(x,y) - przepustowość łuku <x.y> ; ^{k 1} V-*® . k(x,y) - koszt przesyłania jednostki towaru przez

odcina* drogi reprezentowany łuklea <x,y>.

209