Temat:

Dane są cztery hurtownie towaru i=1,2,3,4, z zapasami a_i oraz 5 sklepów j=1,2,3,4,5, z zapotrzebowaniem b_j . Koszt przesłania jednostki towaru z hurtowni „i” do sklepu „j” jest równy a_ij . Znaleźć przepływ towarów „f_ij” zaspokajający zapotrzebowanie sklepów i minimalizujący całkowity koszt przewozu.

DANE:

Zapasy w hurtowniach i zapotrzebowanie sklepów:

Macierz kosztów:

ROZWIĄZANIE:

KROK A:

Ustalenie wartości początkowych zmiennych dualnych:

α_i=0;β_j=min a_ij

βj αi	10	12	11	10	15
0	10	15	16	12	20
0	11	22	11	14	18
0	15	12	12	25	28
0	17	25	17	10	15

KROK B:

Wyznaczenie miejsc dopuszczalnych:

-α_i+β_j=a_ij , i=1,...,m

j=1,...,n

βj αi	10	12	11	10	15
0	10	15	16	12	20
0	11	22	11	14	18
0	15	12	12	25	28
0	17	25	17	10	15

KROK C:

Ustalenie wartości początkowych przepływów:

ဠဠဠဠဠဠဠ bj	8	14	7	10	12	ai-fij	Cechy:
ai
8	8	0	0	0	0	0
12	0	0	7	0	0	5	(-, 5)
14	0	14	0	0	0	0
18	0	0	0	10	8	0
bj-fij	0	0	0	0	4
Cechy:			(2, 5)

KROK E:

Nie ocechowano kolumny dla której b_j-Σf_ij>0

KROK I:

Zmiana zmiennych dualnych:

α_i'=α_i gdy i∈I

α_i+δ gdy i∈I

β_j'=β_j gdy j∈J

β_j+δ gdy j∈J∈

δ=min (a_ij+α_i-β_j) , I=(2) , J=(1,2,4,5)

δ_2,1=11+0-10=1

δ_2,2=22+0-12=10

δ_2,4=14+0-10=4

δ_2,5=18+0-15=3

δ_min= 1

KROK K:

Wyznaczanie nowych miejsc dopuszczalnych:

-α_i'+β_j'=a_ij , i=1,...,m

j=1,...,n

β^'j α^'i	11	13	11	11	16
1	10	15	16	12	20
0	11	22	11	14	18
1	15	12	12	25	28
1	17	25	17	10	15

KROK C:

Ustalenie wartości przepływów:

bj	8	14	7	10	12	ai-fij	Cechy:
ai
8	8	0	0	0	0	0	(1, 5)
12	0	0	7	0	0	5	(-, 5)
14	0	14	0	0	0	0
18	0	0	0	10	8	0
bj-fij	0	0	0	0	4
Cechy:	(2, 5)		(2, 5)

KROK E:

Nie ocechowano kolumny dla której b_j-Σf_ij>0

KROK I:

Zmiana zmiennych dualnych:

α_i'=α_i gdy i∈I

α_i+δ gdy i∈I

β_j'=β_j gdy j∈J

β_j+δ gdy j∈J∈

δ=min (a_ij+α_i-β_j) , I=(1,2) , J=(2,4,5)

δ_1,2=15+1-13=3

δ_1,4=12+1-11=2

δ_1,5=20+1-16=5

δ_2,2=22+0-13=9

δ_2,4=14+0-11=3

δ_2,5=18+0-16=2

δ_min=2

KROK K:

Wyznaczanie nowych miejsc dopuszczalnych:

-α_i'+β_j'=a_ij , i=1,...,m

j=1,...,n

β^'j α^'i	11	15	11	13	18
1	10	15	16	12	20
0	11	22	11	14	18
3	15	12	12	25	28
3	17	25	17	10	15

KROK C:

Ustalenie wartości przepływów:

bj	8	14	7	10	12	ai-fij	Cechy:
ai
8	8	0	0	0	0	0	(1, 1)
12	0	0	7	0	4	1	(-, 1)
14	0	14	0	0	0	0
18	0	0	0	10	8	0	(5, 1)
bj-fij	0	0	0	0	0
Cechy:	(2, 1)		(2, 1)	(1, 1)	(2, 1)

KROK E:

Nie ocechowano jednej kolumny (brak przejścia)

KROK I:

Zmiana zmiennych dualnych:

α_i'=α_i gdy i∈I

α_i+δ gdy i∈I

β_j'=β_j gdy j∈J

β_j+δ gdy j∈J∈

δ=min (a_ij+α_i-β_j) , I=(1,2,4) , J=(2)

δ_1,2=15+1-15=1

δ_2,2=22+0-15=7

δ_4,2=25+3-15=8

δ_min=1

KROK K:

Wyznaczanie nowych miejsc dopuszczalnych:

-α_i'+β_j'=a_ij , i=1,...,m

j=1,...,n

β^'j α^'i	11	16	11	13	18
1	10	15	16	12	20
0	11	22	11	14	18
4	15	12	12	25	28
3	17	25	17	10	15

KROK C:

Ustalenie wartości przepływów:

bj	8	14	7	10	12	ai-fij	Cechy:
ai
8	8	0	0	0	0	0	(1, 1)
12	0	0	7	0	4	1	(-, 1)
14	0	14	0	0	0	0	(2, 1)
18	0	0	0	10	8	0	(5, 1)
bj-fij	0	0	0	0	0
Cechy:	(2, 1)	(1, 1)	(2, 1)	(1, 1)	(2, 1)

Zapotrzebowania zostały wykorzystane!

Minimalny całkowity koszt przewozu wynosi:

a₁ b₁

a₂ b₂

a₃ b₃

a₄ b₄

b₅

K=Σ f_ij⋅a_ij =8⋅10+7⋅11+4⋅18+14⋅12+10⋅10+8⋅15=617

---