Przykład AT-1
Wyznaczyć startowy, dopuszczalny i bazowy plan przewozów dla zadania transportowego:
Trzej producenci: D1, D2 , D3 półfabrykatów zaopatrują cztery place budowy: O1 ,
O2 , O3 , O4 . Półfabrykaty są przewożone w zestawach. Podaż dostawców wynosi
odpowiednio: 300, 150, 430 [zestawów]; zapotrzebowanie odbiorców jest następujące: 210,
6 3 8 6
îÅ‚ Å‚Å‚
170, 360, 140 [zestawów]. Macierz jednostkowych kosztów ma postać: C=ïÅ‚4 3 2 5śł
ïÅ‚ śł
ïÅ‚ śł
ðÅ‚6 5 3 1ûÅ‚
Obliczyć łączne koszty dla wyznaczonego planu przewozów
RozwiÄ…zanie:
Zadanie jest zamkniętym zadaniem transportowym (łączny popyt jest równy łącznej
podaży). Plan dostaw będziemy zapisywać w tablicy, w której: w i-tym wierszu wpisujemy
przewozy zestawów półfabrykatów od dostawcy Di (i = 1,2,3 ) do wszystkich odbiorców; w
j-tej kolumnie wpisujemy przewozy zestawów półfabrykatów do odbiorcy Oj ( j = 1,2,3,4 )
od wszystkich dostawców. W tablicy notujemy także popyt odbiorców i podaż dostawców.
1. Wyznaczanie startowego planu dostaw metodą kąta północno zachodniego
Na początek, dla ustalenia uwagi, wpiszemy do tablicy wielkości dostaw jako
niewiadome xij dla i = 1,2,3 oraz j = 1,2,3,4 .
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
300
D1 x11 x12 x13 x14
150
D2 x21 x22 x23 x24
430
D3 x31 x32 x33 x34
880
popyt
210 170 360 140
Ustalanie startowego planu dostaw rozpoczynamy od określenia dostawy od dostawcy
O1
D1 do odbiorcy , przyjmujemy: x11 = min {a1, b1} = min {300, 210} = 210 . Dostawa ta
O1
jest równa zapotrzebowaniu odbiorcy , zatem x21 = 0 i x31 = 0 . Mamy więc ustalone
liczby w pierwszej kolumnie.
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
210 300
D1 x12 x13 x14
0 150
D2 x22 x23 x24
0 430
D3 x32 x33 x34
880
popyt
210 170 360 140
Wyznaczamy teraz wielkość dostawy x12 jako: min{a1 - 210, b1} = min{90, 210} = 90 .
Ponieważ x11 + x12 = a1 = 300 Ò! x13 = 0 '" x14 = 0 .Zapis w tablicy bÄ™dzie nastÄ™pujÄ…cy:
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
210 90 0 0 300
D1
0 150
D2 x22 x23 x24
0 430
D3 x32 x33 x34
880
popyt
210 170 360 140
880
Dalsze rachunki są następujące:
x22 = min{a2 , b2 - x12} = min{150, 80} = 80 Ò! x32 = 0 ;
x23 = min{a2 - x22 , b3} = min{ 70, 360} = 70 Ò! x24 = 0 ;
x33 = min{a3, b3 - x23} = min{ 430, 290} = 290 Ò! x34 = min{a3 - x33, b4} = 140
Ostatecznie startowy plan dostaw wyznaczony metodą kąta północno zachodniego jest
następujący:
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
210 90 0 0 300
D1
0 80 70 0 150
D2
0 0 290 140 430
D3
880
popyt
210 170 360 140
880
Zwróćmy uwagę, w tym planie dostaw, liczba dostaw dodatnich wynosi N=6= m+n-1,
jest to bazowy plan dostaw. Wyznaczając plan dostaw nie braliśmy pod uwagę wartości
jednostkowych kosztów transportu.
A
ączne koszty przewozów dla tego planu wynoszą:
KC = 6 Å" 210 + 3Å"90 + 3Å"80 + 2 Å" 70 + 3Å" 290 +1Å"140 = 2920 .
2. Wyznaczanie startowego planu dostaw metodÄ… minimalnego elementu
macierzy kosztów
W tej metodzie wyznaczania startowego, bazowego planu dostaw bierzemy pod uwagÄ™
wartości jednostkowych kosztów transportu. Dlatego wpiszemy je do tablicy (w lewych
górnych rogach poszczególnych kratek  do odróżnienia w kolorze czerwonym), w której
plan budujemy.
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
6 3 8 6
300
D1
x11 x12 x13 x14
4 3 2 5
150
D2
x21 x22 x23 x24
6 5 3 1
430
D3
x31 x32 x33 x34
880
popyt
210 170 360 140
Budowę planu rozpoczynamy o ustalenia wielkości dostawy na tej trasie, na której
jednostkowy koszt transportu jest najmniejszy. Ponieważ min {cij} = c34 = 1, ustalamy
dostawÄ™ x34 jako min {430, 140} = 140. Zatem x34 =140, co odpowiada zapotrzebowaniu
odbiorcy O4 , czyli x14 = 0 i x24 = 0.
W tablicy mamy teraz następujący zapis:
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
6 3 8 6
300
D1
0
x11 x12 x13
4 3 2 5
150
D2
0
x21 x22 x23
6 5 3 1
430
D3
140
x31 x32 x33
880
popyt
210 170 360 140
Spośród elementów macierzy kosztów w trzech pierwszych kolumnach wybieramy
element najmniejszy, jest nim c23 = 2 , to ustalamy wielkość dostawy:
x23 = min{150,360} = 150 . Wówczas x21 = x22 = 0 .
Wyznaczyliśmy w ten sposób wielkości dostaw w kolumnie czwartej i w wierszu drugim.
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
6 3 8 6
300
D1
0
x11 x12 x13
4 3 2 5
150
D2
0 0 150 0
6 5 3 1
430
D3
140
x31 x32 x33
popyt
210 170 360 140 880
Dalej postępujemy analogicznie: wybieramy najmniejszy koszt jednostkowy dla
pozostałych  kratek , uwzględniamy tylko te trasy (i, j) dla których nie określiliśmy dostaw.
Ponieważ: min{ c11, c12 , c13,c31,c32 ,c33} = 3 = c12 = c33 , to wybieramy trasę (1,2) lub (3,3) .
Wybierzmy najpierw (1,2) , wówczas x12 = min{300,170} = 170 Ò! x32 = 0 .
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
6 3 8 6
300
D1
170 0
x11 x13
4 3 2 5
150
D2
0 0 150 0
6 5 3 1
430
D3
0 140
x31 x33
popyt
210 170 360 140
880
Ustalamy teraz wielkość dostawy na trasie (3,3) jako:
x33 = min{430 -140, 360 -150} = 210. Zatem x13 =0. Pozostało nam jeszcze wyznaczyć
brakujące dostawy w pierwszej kolumnie: x11 i x31 . Mamy więc: x11 =300-170=130 oraz
x31 =210-130=80.
Wyznaczony plan dostaw, metodą minimalnego elementu macierzy kosztów,
zapiszemy w tablicy końcowej:
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
130 170 0 0 300
D1
0 0 150 0 150
D2
80 0 210 140 430
D3
popyt
210 170 360 140 880
A
Ä…czne koszty transportu dla tego planu dostaw wynoszÄ…: KC=2840. Plan ten jest
lepszy niż poprzednio wyznaczony (łączne koszty są niższe).