Przykład AT-1
Wyznaczyć startowy, dopuszczalny i bazowy plan przewozów dla zadania transportowego:
Trzej producenci:
1
D
,
2
D
,
3
D półfabrykatów zaopatrują cztery place budowy:
1
O ,
2
O ,
3
O ,
4
O . 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,
170, 360, 140 [zestawów]. Macierz jednostkowych kosztów ma postać:
1
3
5
6
5
2
3
4
6
8
3
6
=
C
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
i
D (
3
,
2
,
1
=
i
) do wszystkich odbiorców; w
j-tej kolumnie wpisujemy przewozy zestawów półfabrykatów do odbiorcy
j
O
(
4
,
3
,
2
,
1
=
j
)
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
ij
x
dla
3
,
2
,
1
=
i
oraz
4
,
3
,
2
,
1
=
j
.
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
11
x
12
x
13
x
14
x
300
2
D
21
x
22
x
23
x
24
x
150
3
D
31
x
32
x
33
x
34
x
430
popyt
210
170
360
140
880
Ustalanie startowego planu dostaw rozpoczynamy od określenia dostawy od dostawcy
1
D
do odbiorcy
1
O
, przyjmujemy:
210
}
210
,
300
{
min
}
,
{
min
1
1
11
=
=
=
b
a
x
. Dostawa ta
jest równa zapotrzebowaniu odbiorcy
1
O
, zatem
0
21
=
x
i
0
31
=
x
. Mamy więc ustalone
liczby w pierwszej kolumnie.
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
210
12
x
13
x
14
x
300
2
D
0
22
x
23
x
24
x
150
3
D
0
32
x
33
x
34
x
430
popyt
210
170
360
140
880
Wyznaczamy teraz wielkość dostawy
12
x jako:
90
}
210
,
90
min{
}
,
210
min{
1
1
=
=
−
b
a
.
Ponieważ
11
x +
12
x =
0
0
300
14
13
1
=
∧
=
⇒
=
x
x
a
.Zapis w tablicy będzie następujący:
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
210
90
0
0
300
2
D
0
22
x
23
x
24
x
150
3
D
0
32
x
33
x
34
x
430
popyt
210
170
360
140
880
880
Dalsze rachunki są następujące:
0
80
}
80
,
150
min{
}
,
min{
32
12
2
2
22
=
⇒
=
=
−
=
x
x
b
a
x
;
0
70
}
360
,
70
min{
}
,
min{
24
3
22
2
23
=
⇒
=
=
−
=
x
b
x
a
x
;
140
}
,
min{
290
}
290
,
430
min{
}
,
min{
4
33
3
34
23
3
3
33
=
−
=
⇒
=
=
−
=
b
x
a
x
x
b
a
x
Ostatecznie startowy plan dostaw wyznaczony metodą kąta północno zachodniego jest
następujący:
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
210
90
0
0
300
2
D
0
80
70
0
150
3
D
0
0
290
140
430
popyt
210
170
360
140
880
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.
Łączne koszty przewozów dla tego planu wynoszą:
2920
140
1
290
3
70
2
80
3
90
3
210
6
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
KC
.
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”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
6
11
x
3
12
x
8
13
x
6
14
x
300
2
D
4
21
x
3
22
x
2
23
x
5
24
x
150
3
D
6
31
x
5
32
x
3
33
x
1
34
x
430
popyt
210
170
360
140
880
Budowę planu rozpoczynamy o ustalenia wielkości dostawy na tej trasie, na której
jednostkowy koszt transportu jest najmniejszy. Ponieważ
1
}
{
min
34
=
=
c
c
ij
, ustalamy
dostawę
34
x jako
140
}
140
,
430
{
min
=
. Zatem
34
x =140, co odpowiada zapotrzebowaniu
odbiorcy
4
O , czyli
14
x = 0 i
24
x = 0.
W tablicy mamy teraz następujący zapis:
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
6
11
x
3
12
x
8
13
x
6
0
300
2
D
4
21
x
3
22
x
2
23
x
5
0
150
3
D
6
31
x
5
32
x
3
33
x
1
140
430
popyt
210
170
360
140
880
Spośród elementów macierzy kosztów w trzech pierwszych kolumnach wybieramy
element
najmniejszy,
jest
nim
2
23
=
c
,
to
ustalamy
wielkość
dostawy:
150
}
360
,
150
min{
23
=
=
x
. Wówczas
0
22
21
=
=
x
x
.
Wyznaczyliśmy w ten sposób wielkości dostaw w kolumnie czwartej i w wierszu drugim.
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
6
11
x
3
12
x
8
13
x
6
0
300
2
D
4
0
3
0
2
150
5
0
150
3
D
6
31
x
5
32
x
3
33
x
1
140
430
popyt
210
170
360
140
880
Dalej postępujemy analogicznie: wybieramy najmniejszy koszt jednostkowy dla
pozostałych „kratek”, uwzględniamy tylko te trasy
)
,
( j
i
dla których nie określiliśmy dostaw.
Ponieważ:
33
12
33
32
31
13
12
11
3
}
,
,
,
,
,
min{
c
c
c
c
c
c
c
c
=
=
=
, to wybieramy trasę
)
2
,
1
(
lub
)
3
,
3
(
.
Wybierzmy najpierw
)
2
,
1
(
, wówczas
0
170
}
170
,
300
min{
32
12
=
⇒
=
=
x
x
.
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
6
11
x
3
170
8
13
x
6
0
300
2
D
4
0
3
0
2
150
5
0
150
3
D
6
31
x
5
0
3
33
x
1
140
430
popyt
210
170
360
140
880
Ustalamy
teraz
wielkość
dostawy
na
trasie
)
3
,
3
(
jako:
210
}
150
360
,
140
430
min{
33
=
−
−
=
x
. Zatem
13
x =0. Pozostało nam jeszcze wyznaczyć
brakujące dostawy w pierwszej kolumnie:
11
x
i
31
x . Mamy więc:
11
x
=300-170=130 oraz
31
x =210-130=80.
Wyznaczony plan dostaw, metodą minimalnego elementu macierzy kosztów,
zapiszemy w tablicy końcowej:
Odbiorca „j”
Dostawca „i”
1
O
2
O
3
O
4
O
podaż
1
D
130
170
0
0
300
2
D
0
0
150
0
150
3
D
80
0
210
140
430
popyt
210
170
360
140
880
Łączne koszty transportu dla tego planu dostaw wynoszą:
KC=2840. Plan ten jest
lepszy niż poprzednio wyznaczony (łączne koszty są niższe).