3848093737

14

Rozdział 1. Zagadnienie transportowe

Tablica 1.6. Rozwiązanie początkowe wyznaczone metodą VAM

	1	2	3	4	Ui
1	1000 0 3	4000 0 2	0 9 7	0 7 6	0
2	2500 0 7	0 -1 5	2000 0 2	1500 0 3	-4
3	2500 0 2	0 4 5	0 7 4	0 7 5	1
^V3	-3	-2	2	1

dającego najmniejszej wartości zerowej macierzy równoważnej i wyznaczenie nowego wierzchołka w grafie rozwiązania. Sposób postępowania opisuje poniższy Algorytm transportowy.

Algorytm transportowy

Krok 1. Znaleźć wstępne rozwiązanie bazowe zadania zbilansowanego. Krok 2. Rozwiązać układ równań: Cij + Ui + Vj = 0 dla i,j(żB Krok 3. Wyznaczyć równoważną macierz zerową c-.

Krok 4. Zbadać, czy c- > 0 dla i = 1    = 1, ...,n. Jeśli tak, to

aktualne rozwiązanie jest optymalne - zakończ.

Krok 5. Wprowadzić do bazy zmienną Xki taką, że cjy = min{c- : c- < 0}. Krok 6. Wyznaczyć cykl 7 ⁺(/c, Z) oraz 7

Krok 7. Usunąć z bazy zmienną x_rs taką, że x_rs =    {xij : (i, j) €

B} = 6

Krok 8. Wyznaczyć nowe rozwiązanie bazowe:

{Xij — 6 dla (i,j) G 7“

Xij dla (i,j) £ (7“U7⁺)    (1.12)

Xij + 6 dla (i, j) e 7⁺

Krok 9. Wrócić do kroku 2.

Zmienna #22 wejdzie do bazy, co spowoduje powstanie cyklu 7 w grafie rozwiązania. W rozwiązywanym przykładzie cykl wyznaczają wierzchołki (1,1), (1,2), (2,1) i (2,2). W cyklu wyznaczamy wierzchołki nieparzyste, które oznaczone znakiem ” + ” tworzą zbiór 7+ oraz parzyste, które oznaczone znakiem ” — ” tworzą zbiór 7“. Nową zmienną bazową traktujemy jako początek cyklu i oznaczamy znakiem ” + ”. Następnie poruszamy się wzdłuż cyklu, oznaczając kolejne wierzchołki na zmianę znakiem ” — ” i ” + ”. Spośród zmiennych ze zbioru 7“ wybieramy zmienną o najmniejszej wartości 6 i tę wartość odejmujemy od wszystkich zmiennych ze zbioru 7“, a dodajemy ją do zmiennych ze zbioru 7⁺. Graf rozwiązania z zaznaczonym cyklem przedstawiono na rys 1.7. Zmienna, która przyjmuje wartość zero jest usuwana z bazy. Jeżeli graf rozwiązania zawiera mniej niż (n + ra-1) wierzchołków, to mamy do czynienia z rozwiązaniem zdegenerowanym, w którym co najmniej jedna zmienna bazowa jest równa zero. Postępowanie w takim przypadku polega na dołączeniu brakującej liczby zmiennych bazowych z wartościami zerowymi. Wybór zmiennych powinien gwarantować uzyskanie grafu spójnego i bez cykli.

Dla nowej bazy wyznaczamy równoważną macierz zerową. Otrzymaną macierz przedstawia tablica 1.8. Jak widać jest to rozwiązanie optymalne, gdyż wszystkie elementy tej macierzy są nieujemne.