Zestaw 16

Temat: Optymalny rozdział ładunku

Z trzech hut dysponujących: 900, 600, 900 tonami stali 55 należy przetransportować ją do czterech zakładów przemysłowych potrzebujących odpowiednio: 600, 500, 700, 200 ton. Jednostkowe koszty transportu między każda hutą, a każdym zakładem podano w macierzy kosztów [c_ij]. Opracować rozdział stali charakteryzujący się najmniejszym kosztem transportu.

	1	2	3	4
1	9	7	6	10
2	7	5	4	5
3	8	3	6	1

1.WYZNACZENIE POTENCJAŁU DLA ROZWIĄZANIA BAZOWEGO

U_i+U_j=K_ij

	O1	O2	O3	O4	O5	Podaż "Z"
D1	x11	x12	x13	x14	x15	900
D2	x21	x22	x23	x24	x25	600
D3	x31	x32	x33	x34	x35	900
Popyt "P"	600	500	700	200	400	P=Z=2400

	O1	O2	O3	O4	O5	Δrz
D1	9	7	6	10	0	6
D2	7	5	4	5	0	4
D3	8	3	6	1	0	1
Δk	1	2	2	4	0

9· x₁₁+7· x₁₂+6· x₁₃+10· x₁₄+0·x₁₅+7· x₂₁+5· x₂₂+4· x₂₃+4· x₂₄+0·_x25+8· x₃₁+3· x₃₂+6· x₃₃+5· x₃₄+0· x₃₅ → min

Dla odbiorców: Dla dostawców:

x₁₁+x₂₁+x₃₁ =600 x₁₁+x₁₂+x₁₃+x₁₄+x₁₅ =900
x₁₂+x₂₂+x₃₂ =500 x₂₁+x₂₂+x₂₃+x₂₄+x₂₅ =600
x₁₃+x₂₃+x₃₃ =700 x₃₁+x₃₂+x₃₃+x₃₄+x₃₅ =900
x₁₄+x₂₄+x₃₄ =200
x₁₅+x₂₅+x₃₅ =400

METODA KĄTA PÓŁNOCNO-ZACHODNIEGO

	O1	O2	O3	O4	O5	Z
D1	600	300				900
D2		200	400			600
D3			300	200	400	900
P	600	500	700	200	400

FC: 9·600+7·300+5·200+4·400+6·300+1·200+0·400=12100

METODA NAJMNIEJSZYCH KOSZTÓW JEDNOSTKOWYCH

	O1	O2	O3	O4	O5	Z
D1	500				400	900
D2			600			600
D3	100	500	100	200		900
P	600	500	700	200	400

FC: 9·500+8·100+3·500+6·100+4·600+1·200+0·400=10000

METODA VAM

	O1	O2	O3	O4	O5	Z
D1		500 6			400 1	900
D2			600 3			600
D3	600 4		100 5	200 2		900
P	600	500	700	200	400

FC: 8·600+7·500+4·600+6·100+1·200+0·400=11500

2. WYZNACZENIE POTENCJAŁU DLA ROZWIĄZANIA BAZOWEGO

Potencjał wierszy i kolumn k_ij>0

SPRAWDZENIE 1

	O1	O2	O3	O4	O5	Z
D1	600	300				900
D2		200	400			600
D3			300	200	400	900
P	600	500	700	200	400

	O1	O2	O3	O4	O5	Ui
D1	9	7	6	10	0	0
D2	7	5	4	5	0	-2
D3	8	3	6	1	0	0
Vj	9	7	6	1	0

Sprawdzenie optymalności rozwiązania
Δ_ij=(U_i+V_j)-k_ij≤0

k₁₁=9 to Δ=(0+9)-9=0 k₁₂=7 to Δ=(0+7)-7=0 k₁₃=6 to Δ=(0+6)-6=0
k₂₁=7 to Δ=(-2+9)-7=0 k₂₂=5 to Δ=(-2+7)-5=0 k₂₃=4 to Δ=(-2+6)-4=0
k₃₁=8 to Δ=(0+9)-8=1 k₃₂=3 to Δ=(0+7)-3=4 k₃₃=6 to Δ=(0+6)-6=0

k₁₄=10 to Δ=(0+1)-10=-9 k₁₅=0 to Δ=(0+0)-0=0
k₂₄=5 to Δ=(-2+1)-5=-6 k₂₅=0 to Δ=(-2+0)-0=-2
k₃₄=1 to Δ=(0+1)-1=0 k₃₅=0 to Δ=(0+0)-0=0
Rozwiązanie nie jest optymalne, ponieważ nie spełnia warunku: Δ_ij≤0.
Poszukujemy kolejnego optymalnego rozwiązania.

SPRAWDZENIE 2

	O1	O2	O3	O4	O5
D1	0	0	0	-9	0
D2	0	0-Q	0+Q	-6	-2
D3	1	4+Q	0-Q	0	0

Q=200

	O1	O2	O3	O4	O5	Z
D1	600	300				900
D2			600			600
D3		200	100	200	400	900
P	600	500	700	200	400

	O1	O2	O3	O4	O5	Ui
D1	9	7	6	10	0	0
D2	7	5	4	5	0	-6
D3	8	3	6	1	0	-4
Vj	9	7	10	5	4

Sprawdzenie optymalności rozwiązania
Δ_ij=(U_i+V_j)-k_ij≤0

k₁₁=9 to Δ=(0+9)-9=0 k₁₂=7 to Δ=(0+7)-7=0 k₁₃=6 to Δ=(0+10)-6=4
k₂₁=7 to Δ=(-6+9)-7=-4 k₂₂=5 to Δ=(-6+7)-5=-4 k₂₃=4 to Δ=(-6+10)-4=0
k₃₁=8 to Δ=(-4+9)-8=-3 k₃₂=3 to Δ=(-4+7)-3=0 k₃₃=6 to Δ=(-4+10)-6=0

k₁₄=10 to Δ=(0+5)-10=-5 k₁₅=0 to Δ=(0+4)-0=4
k₂₄=5 to Δ=(-6+5)-5=-6 k₂₅=0 to Δ=(-6+4)-0=-2
k₃₄=1 to Δ=(-4+5)-1=0 k₃₅=0 to Δ=(-4+4)-0=0
Rozwiązanie nie jest optymalne, ponieważ nie spełnia warunku: Δ_ij≤0.
Poszukujemy kolejnego optymalnego rozwiązania.

SPRAWDZENIE 3

	O1	O2	O3	O4	O5
D1	0	0-Q	4	-5	4+Q
D2	-4	-4	0	-6	-2
D3	-3	0+Q	0	0	0-Q

Q=300

	O1	O2	O3	O4	O5	Z
D1	600				300	900
D2			600			600
D3		500	100	200	100	900
P	600	500	700	200	400

	O1	O2	O3	O4	O5	Ui
D1	9	7	6	10	0	0
D2	7	5	4	5	0	-2
D3	8	3	6	1	0	0
Vj	9	3	6	1	0

Sprawdzenie optymalności rozwiązania
Δ_ij=(U_i+V_j)-k_ij≤0

k₁₁=9 to Δ=(0+9)-9=0 k₁₂=7 to Δ=(0+3)-7=-4 k₁₃=6 to Δ=(0+6)-6=0
k₂₁=7 to Δ=(-2+9)-7=0 k₂₂=5 to Δ=(-2+3)-5=-4 k₂₃=4 to Δ=(-2+6)-4=0
k₃₁=8 to Δ=(0+9)-8=1 k₃₂=3 to Δ=(0+3)-3=0 k₃₃=6 to Δ=(0+6)-6=0

k₁₄=10 to Δ=(0+1)-10=-9 k₁₅=0 to Δ=(0+0)-0=0
k₂₄=5 to Δ=(-2+1)-5=-6 k₂₅=0 to Δ=(-2+0)-0=-2
k₃₄=1 to Δ=(0+1)-1=0 k₃₅=0 to Δ=(0+0)-0=0
Rozwiązanie nie jest optymalne, ponieważ nie spełnia warunku: Δ_ij≤0.
Poszukujemy kolejnego optymalnego rozwiązania.

SPRAWDZENIE 4

	O1	O2	O3	O4	O5
D1	0-Q	-4	0	-9+Q	0
D2	0	-4	0	-6	-2
D3	1+Q	0	0	0-Q	0

Q=100

	O1	O2	O3	O4	O5	Z
D1	500				400	900
D2			600			600
D3	100	500	100	200		900
P	600	500	700	200	400

	O1	O2	O3	O4	O5	Ui
D1	9	7	6	10	0	0
D2	7	5	4	5	0	-3
D3	8	3	6	1	0	-1
Vj	9	4	7	1	0

Sprawdzenie optymalności rozwiązania
Δ_ij=(U_i+V_j)-k_ij≤0

k₁₁=9 to Δ=(0+9)-9=0 k₁₂=7 to Δ=(0+4)-7=-3 k₁₃=6 to Δ=(0+7)-6=1
k₂₁=7 to Δ=(-3+9)-7=-1 k₂₂=5 to Δ=(-3+4)-5=-4 k₂₃=4 to Δ=(-3+7)-4=0
k₃₁=8 to Δ=(-1+9)-8=0 k₃₂=3 to Δ=(-1+4)-3=0 k₃₃=6 to Δ=(-1+7)-6=0

k₁₄=10 to Δ=(0+1)-10=-9 k₁₅=0 to Δ=(0+0)-0=0
k₂₄=5 to Δ=(-3+1)-5=-7 k₂₅=0 to Δ=(-3+0)-0=-3
k₃₄=1 to Δ=(-1+1)-1=-1 k₃₅=0 to Δ=(-1+0)-0=-1
Rozwiązanie nie jest optymalne, ponieważ nie spełnia warunku: Δ_ij≤0.
Poszukujemy kolejnego optymalnego rozwiązania.

SPRAWDZENIE 5

	O1	O2	O3	O4	O5
D1	0-Q	-3	1+Q	-9	0
D2	-1	-4	0	-7	-3
D3	0+Q	0	0-Q	-1	-1

Q=100

	O1	O2	O3	O4	O5	Z
D1	400		100		400	900
D2			600			600
D3	200	500		200		900
P	600	500	700	200	400

	O1	O2	O3	O4	O5	Ui
D1	9	7	6	10	0	0
D2	7	5	4	5	0	-2
D3	8	3	6	1	0	-1
Vj	9	4	6	2	0

Sprawdzenie optymalności rozwiązania
Δ_ij=(U_i+V_j)-k_ij≤0

k₁₁=9 to Δ=(0+9)-9=0 k₁₂=7 to Δ=(0+4)-7=-3 k₁₃=6 to Δ=(0+6)-6=0
k₂₁=7 to Δ=(-2+9)-7=0 k₂₂=5 to Δ=(-2+4)-5=-3 k₂₃=4 to Δ=(-2+6)-4=0
k₃₁=8 to Δ=(-1+9)-8=0 k₃₂=3 to Δ=(-1+4)-3=0 k₃₃=6 to Δ=(-1+6)-6=-1

k₁₄=10 to Δ=(0+2)-10=-8 k₁₅=0 to Δ=(0+0)-0=0
k₂₄=5 to Δ=(-2+2)-5=-5 k₂₅=0 to Δ=(-2+0)-0=-2
k₃₄=1 to Δ=(-1+2)-1=0 k₃₅=0 to Δ=(-1+0)-0=-1

Rozwiązanie to jest rozwiązaniem optymalnym, ponieważ został spełniony warunek Δ_ij≤0.

OPTYMALNY ROZKŁAD

	O1	O2	O3	O4	O5	Z
D1	400		100		400	900
D2			600			600
D3	200	500		200		900
P	600	500	700	200	400

FC: 9·400+8·200+5·500+6·100+4·600+1·200+0·400=9900

WNIOSKI:

Optymalny rozkład ładunku okazał się być inny niż ten wyznaczony metodą najmniejszych kosztów jednostkowych, kąta północno-zachodniego oraz VAM. Metoda sprawdzająca pozwoliła wyznaczyć taki rozkład ładunku, w którym całkowity koszt transportu jest najmniejszy.