0000118

O a n e x Macierz prostokątna K- [^kjj]„,_n kosztów jednostkowych przydziału dla poszczególnych krawędzi grafu możliwości przydziału C •<AUD,U,P> . k^, ■ k*(u), gdzie u : <i.J,u> £Pj 1C A, J€ D. Dla takich per <1,J> , to nie istnieje krawędź u x <i,J.u>€P, przyjmujemy k^ • oo .

Procedura x

(ij Noraallzujeay macierz K do postaci macierzy kwadratowoj

[^klj]r»r ’ ^r *    dodając odpowiednią Ilość zerowych

wierszy lub koluan.

(Ę^ó) Wyznaczany zbiór oczek, które w danym kroku algorytau będą traktowane Jako oczka dopuszczalne. W tym celu, w każdym wierszu macierzy odejmujemy, od każdego elementu wiersza, element minimalny w tym wierszu. Następnie w każdej kolumnie odejmujemy, od każdego elementu kolumny,* element minimalny w tej kolumnie. Oczkami dopuszczalnymi są oczka re -prezentowana przez elementy zerowe w tak zmodyfikowanej oe-darzy.

(yy Ola utworzonego zbioru oczek dopuszczalnych wyznaczamy najliczniejszy zbiór niezależnych oczek dopuszczalnych 1 ze -pemiętujomy cechy wierszy 1 kolumn uzyskane w ostatnim kroku cechowania.

Pytamy, czy llcznoóć wyznaczonego zbioru jest równa r ?

TAK: Wyznaczony zbiór określa rozwiązanie optymelne. KONIEC.

©

NIE t Na podstawie zapamiętanych wartości cech dzielimy zbiór wszystkich oczek na pokryte l niepokryte, gdzie nlepokry-tyml nazywamy oczka łożące na przecięciu ocechowanych wierszy 1 nleocechowanych kolumn. Wszystkie pozostałe oczka eą pokryte. Wśród pokrytych oczek wyróżniamy oczka pokryte podwójnie, to znaczy te, które leżą na przecięciu ocechowanych kolumn 1 nleocechowanych wierszy.

Wśród nlepokrytych oczek wybieramy, w zmodyfikowanej aa -cierzy element minimalny 1 odejmujemy go od wartości wszystkich oczek nlepokrytych tej macierzy, a dodajemy do war -toścl oczek pokrytych podwójnie, w ten sposób dostajemy nową, zmodyfikowaną macierz 1 nowy zbiór oczek dopuszczalnych o zerowych wartościach, z którym przechodzimy do punktu

Przykład 14,3

Wyznaczymy oploonym algorytcion przydział najllcznloJazy o nojmnicJozym koazcle dla olocl dwudziolnoj aoillwoócl przydziału 1 aaclarzy K , przadotowionych w rozdziała 13 na rya.13.3. Tablica kooztów K aa poatać naetępujęcę (rya.14.9)

^x4 ^x5 ^xfi

^xl'*l ^X2'*2 ^X3’*3

Rya.14.9 •

Po wykonaniu punktu    otrzyaujaay tablicę (ryo.14.lOo).Zbiór

oczak dopuazczalnych przedatawla rya.i4.i0b.

o)    b)

5	8	0
1	/	0
0	0	0,

Wyznaczając na J Ucznia Jazy zbiór nlazalatnych oczak do -puazczalnych otrzymujany ostatnia cechowanie przedstawione na rye.14.11 (porównaj z ryo. 13.0).

p m	1	i i
i	1	i i
-1 ■		T"
		“1“

-1 A-L. oczko pokryte T j I podrtójnii

Ryo.14.11