162 163

162 Zadanie transportowe i problem komiwojażera

3.5. Bilansowanie

zadania transportowego

' i

Metodę potencjałów możemy stosować do rozwiązywania zbilansowanych zadań transportowych, w których łączna podaż dostawców jest równa łącznemu popytowi odbiorców. Często zadanie, które chcemy rozwiązać, nie ma tej własności. Może się zdarzyć, że podaż przewyższa popyt lub odwrotnie — popyt przewyższa podaż. W obu przypadkach możemy zadanie zbilansować, a następnie rozwiązać, stosując metodę potencjałów.

3.5.i. Podaż przewyższa popyt

Jeżeli podaż przewyższa popyt, czyli:

m    t)

Ia> X bj,

'“i    j=i

to pewna część towaru pozostaje u dostawców. Zadanie bilansujemy przez wprowadzenie fikcyjnego odbiorcy. Ponieważ w rzeczywistości towar pozostaje u dostawców, więc przyjmujemy, że koszty przewozu na trasach od kolejnych dostawców do fikcyjnego odbiory są równe 0.

Dokonując pewnych modyfikacji zagadnienia rozpatrywanego w przykładzie 3.1, pokażemy, w jaki sposób doprowadzamy zagadnienia niezbilansowane, w których popyt przewyższa podaż, do postaci zbilansowanej.

Przykład 3.3

Możliwości produkcyjne zakładu A, rozpatrywanego w przykładzie 3.1, zwiększyły się i wynoszą obecnie 25 jednostek, popyt jest taki sam. jak to opisano w przykładzie 3.1. Należy przekształcić powstałe w ten sposób zadanie niezbilansowane do postaci zbilansowanej, a następnie je rozwiązać.

Wprowadzamy fikcyjnego odbiorcę, którego zapotrzebowanie jest równe całkowitej podaży pomniejszonej o wielkość całkowitego popytu. Ponieważ podaż jest równa ai = 25, <32 = 20, a.3 = 30, a popyt wynosi ż>i=10, />j=15, bi- 45, otrzymujemy popyt dla fikcyjnego odbiorcy:

Im = (a i + «₂ + a.0 - (fti + bi + bi) = (25 + 20 + 30) - (10 + 15 + 45) = 5.

Oznaczymy przez jcm ilość towaru przekazaną fikcyjnemu odbiorcy przez i-tego dostawcę.

Rozwiązanie początkowe otrzymane metodą minimalnego elementu wraz z dołączoną macierzą kosztów przedstawiono w tablicy 3.33.

Tablica 3.33

Rozwiązanie początkowe (metoda minimalnego elementu)				Podaż
10*	10*	0	5*	25
0	5*	15*	0	20
0	0	30*	0	30
10	15	45	5	Popyt
Macierz kosztów jednostkowych				Wątłość funkcji celu 510
1	4	7	0
3	5	11	0
6	7	9	0

Stosując metodę potencjałów, otrzymujemy w iteracji 4 rozwiązanie optymalne. Ma ono postać:

JCl 1 = 10,    *12 = 0,    *!3=15,    *14    =    0,

*21 = 0,    *22=15,    *23 = 0,    *24    =    5,

*31= 0,    *32= 0,    *33 = 30,    *34    =    0.

Optymalna wartość funkcji celu jest równa 460.

Łatwo sprawdzić, że jeżeli jako rozwiązanie początkowe przyjmiemy rozwiązanie otrzymane metodą kąta północno-zachodniego, to rozwiązanie optymalne otrzymamy w trzeciej iteracji. Wykorzystując w fazie początkowej metodę VAM, rozwiązanie optymalne otrzymamy jeszcze szybciej —już w drugiej iteracji.

3.5.2. Popyt przewyższa podaż

Jeżeli zadanie jest niezbilansowane i popyt przewyższa podaż, czyli:

m    n

X a< < X bj,

;=]    ;-1

to zapotrzebowanie części odbiorców będzie niezaspokojone. Zadanie bilansujemy przez wprowadzenie fikcyjnego dostawcy. Ponieważ w rzeczywistości towaru nie ma, więc przyjmujemy, że jednostkowe koszty transportu na trasach od fikcyjnego dostawcy do kolejnych odbiorców są równe 0.

W kolejnym przykładzie pokażemy, w jaki sposób rozwiązujemy zadanie, w którym popyt przewyższa podaż.