ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
CHÖÔNG 3
BAØI TOAÙN VAÄN TAÛI
(Xem)
1. BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT
2. CAÙC TÍNH CHAÁT VAØ TIEÂU CHUAÅN TOÁI ÖU CUÛA
(Xem)
BAØI TOAÙN VAÄN TAÛI
Ths. Nguyeãn Coâng Trí
3. CAÙC PHÖÔNG PHAÙP TÌM PHÖÔNG AÙN CÖÏC
(Xem)
BIEÂN ÑAÀU TIEÂN CUÛA BAØI TOAÙN VAÄN TAÛI
Copyright 2001
4. THUAÄT GIAÛI THEÁ VÒ CHO BAØI TOAÙN VAÄN TAÛI (Xem)
5. CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI (Xem)
Ths. Nguyeãn Coâng Trí
(Xem)
6. BAØI TAÄP
Copyright 2001
BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT NOÄI DUNG BAØI TOAÙN VAÄN TAÛI Giaû söû caàn vaän chuyeån moät loaïi haøng hoùa (xi maêng, saét theùp, ...) töø m ñieåm cung caáp (traïm phaùt), kyù hieäu laø A1, A2, ..., Am ñeán n ñieåm tieâu thuï (traïm thu), kyù hieäu laø B1, B2, ..., Bn, bieát raèng (1) Soá löôïng haøng coù ôû caùc traïm phaùt A1, A2, ..., Am laàn löôït laø a1, a2,..., am (2) Soá löôïng haøng caàn ôû caùc traïm thu B1, B2, ..., Bn laàn löôït laø b1, b2,..., bn. (3) Chi phí vaän chuyeån moät ñôn vò haøng hoùa töø traïm phaùt Ai ñeán traïm thu Bj laø cij. Haõy laäp keá hoaïch vaän taûi haøng hoùa sao cho toång chi phí vaän taûi thaáp nhaát vaø thoûa maõn yeâu caàu thu – phaùt.
traïm
m n
min
BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT MOÂ HÌNH BAØI TOAÙN VAÄN TAÛI Ñaët xij laø soá löôïng haøng caàn vaän chuyeån töø phaùt Ai ñeán traïm thu Bj. Ta coù toång chi phí vaän taûi:
min
Z
c x ij ij
c x ij ij
BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT Vaäy, moâ hình toaùn cuûa baøi toaùn vaän taûi (BTVT) daïng toång quaùt nhö sau: Tìm {xij} sao cho: m n Z
i
1
j
1
j
1
i
1 n
n
1,
m
(1) Traïm phaùt, phaùt heát haøng:
x ij
a i , i
1,
m
x ij
a i , i
j
1
j
1
m
m
(2) Traïm thu, thu ñuû haøng:
1,
n
x ij
b j , j
1,
n
x ij
b j , j
i
1
i
1
(3) Yeâu caàu traïm phaùt, traïm thu ñöôïc thoûa
n
m
n
m
(ñk caân baèng thu – phaùt).
b
0;
0;
0;
b
0;
b
j
x ij
c ij
a i
j
j
a i
a i
j
1
i
1
j
1
i
1
1
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT BTVT vieát döôùi daïng vectô vaø ma traän nhö sau
BAØI TOAÙN VAÄN TAÛI DAÏNG TOÅNG QUAÙT BAØI TOAÙN VAÄN TAÛI DÖÔÙI DAÏNG BAØI TOAÙN QHTT khai trieån BTVT vaø xeáp heä raøng buoäc döôùi daïng heä m + n phöông trình cuûa m n bieán nhö sau
T C X AX
min b
x 11
x 12
x 1
n
a 1
x
x
x
a
X
0
21
22
2
n
* **
z
2
x
x
m
1
m
2
mn
x x
x
m
1
a m b 1
x 11
21
x
x
m
2
x 12
22
b 2
x
2
n
n
x 1
b n
mn
x Kyù hieäu Am+n,mn ma traän heä soá cuûa hpt treân. XT = (x11 x12 ...…x1n x21 x22 ... x2n ... xm1 xm2…... xmn) laø vectô coät goàm mn thaønh phaàn; C = (c11 c12 ...…c1n c21 c22 ... c2n… cm1 cm2 ...…cmn) laø vectô doøng goàm mn thaønh phaàn; bT = (a1 a2 ...…am b1 b2 ...…bn) laø vectô coät goàm m+ n thaønh phaàn.
Moät vectô X thoûa (*) vaø (**) goïi laø phöông aùn. Moät P.A ñaït cöïc tieåu thì goïi laø P.A.T.Ö cuûa BTVT. laø P.A.C.B khi caùc Moät phöông aùn X ñöôïc goïi vectô coät Aj cuûa ma traän heä soá A öùng vôùi caùc thaønh phaàn xij > 0 laø ñoäc laäp tuyeán tính. Moät P.A.C.B cuûa BTVT coù nhieàu nhaát laø m + n – 1 thaønh phaàn döông. Neáu moät P.A.C.B cuûa BTVT coù ñuùng m + n – 1 thaønh phaàn döông thì ñöôïc goïi laø laø khoâng suy bieán. Ngöôïc laïi, ñöôïc goïi phöông aùn cöïc bieân suy bieán.
TTrraaïïmm tthhuu BBjj
BB11
BB22
BBnn
bb11
bb22
bbnn
TTrraaïïmm pphhaaùùtt AAii AA11
cc11nn
cc1111
cc1122
xx11nn
aa11
xx1111
xx1122
cc22nn
cc2211
cc2222
AA22
xx22nn
aa22
xx2211
xx2222
ccmmnn
ccmm11
ccmm22
AAmm
xxmmnn
aamm
xxmm11
xxmm22
MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI
2
MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI (1) Kyù hieäu (i, j) laø oâ treân doøng i vaø coät j. (2) Chi phí vaän chuyeån cij ñöôïc ghi ôû goùc treân beân traùi cuûa oâ (i, j), löôïng haøng caàn vaän chuyeån xij ñöôïc ghi ôû goùc döôùi beân phaûi cuûa oâ (i, j) bieåu dieãn tuyeán ñöôøng vaän chuyeån töø traïm phaùt Ai ñeán traïm thu Bj. laø oâ (3) Trong BAÛNG VAÄN TAÛI, moät oâ ñöôïc goïi treo neáu noù laø oâ duy nhaát treân doøng hay treân coät. (4) Nhöõng oâ öùng vôùi xij > 0 trong BAÛNG VAÄN TAÛI ñöôïc goïi laø oâ choïn, nhöõng oâ khaùc goïi laø oâ loaïi. (5) Moät daõy caùc oâ choïn, trong ñoù 3 oâ lieân tieáp khoâng naèm treân cuøng moät doøng hay moät coät thì ñöôïc goïi laø moät daây chuyeàn.
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
laø moät
VÍ DUÏ 3.1.
(6) Moät daây chuyeàn kheùp kín ñöôïc goïi chu trình hay moät voøng.
(7) Moät ma traän (xij) laø moät P.A cuûa BTVT neáu noù thoaû heä raøng buoäc. Moät P.A (xij) laøm cöïc tieåu haøm muïc tieâu thì (xij) laø P.A.T.Ö. cuûa baøi toaùn.
Hình 2.4.
Hình 2.2.
(8) Moät P.A cuûa BTVT khoâng taïo thaønh chu trình (voøng) thì ñöôïc goïi laø Phöông aùn cöïc bieân.
laø P.A.C.B khoâng suy bieán, neáu coù
(9) Moät P.A.C.B cuûa BTVT coù ñuû m+n-1 oâ choïn thì ñöôïc goïi ít hôn m+n-1 oâ choïn ñöôïc goïi laø P.A.C.B suy bieán.
Hình 2.5. Hình 2.3. Hình 2.1. Hình 2.1. caùc oâ choïn, coù daáu “”, taïo thaønh daây chuyeàn, caùc oâ (1,1) vaø (4,3) laø caùc oâ treo. Hình 2.2. caùc oâ choïn taïo thaønh daây chuyeàn, caùc oâ (4,1) vaø (3,3) laø caùc oâ treo. Hình 2.3., Hình 2.4 vaø Hình 2.5. caùc oâ choïn taïo thaønh chu trình, khoâng coù oâ treo.
MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI MOÂ TAÛ BAØI TOAÙN DÖÔÙI DAÏNG BAÛNG VAÄN TAÛI
Xeùt baøi toaùn vaän taûi sau
Vieát laïi baøi toaùn
toaùn vaän taûi
luoân luoân coù
m n
m n
Z
min
Z
min
c x ij ij
c x ij ij
i
1
j
1
1
j
1
i n
m
1,
m
1,
n
x ij
a i , i
x ij
b j , j
CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN VAÄN TAÛI TIEÂU CHUAÅN TOÁI ÖU CUÛA BAØI TOAÙN VAÄN TAÛI
TÍNH CHAÁT 1: Baøi phöông aùn toái öu. TÍNH CHAÁT 2: Vôùi moät phöông aùn baát kyø, soá oâ choïn cuûa phöông aùn khoâng vöôït quaù toång soá traïm phaùt vaø traïm thu.
j
1
i
1
n
m
1,
m
1,
n
x ij
a i , i
x ij
b j , j
j
1
1 i 0;
0;
0;
b
0;
0;
0;
0;
b
0;
x ij
c ij
a i
j
x ij
c ij
a i
j
m
n
m
n
b
b
j
j
a i
a i
i
1
j
1
i
1
j
1
≤ m + n –1 (vôùi laø soá oâ choïn cuûa P.A) TÍNH CHAÁT 3: Vôùi moät phöông aùn coù ñuû m+n–1 oâ choïn thì vôùi moät oâ loaïi baát kyø ñöôïc ñöa vaøo phöông aùn seõ taïo thaønh chu trình vaø chu trình naøy laø duy nhaát. TÍNH CHAÁT 4: Neáu löôïng cung ai vaø löôïng caàu bj laø soá nguyeân thì baøi toaùn coù lôøi giaûi nguyeân.
3
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT
n
m
*
Z
max
j
b v j
a u i i
Treân baûng vaän taûi, choïn oâ ñaàu tieân coù cöôùc phí vaän chuyeån beù nhaát vaø choïn xij nhö sau:
i
j
1
1
b
a i
m
in
j
b
x
a b , i
j
a i
j
ij
j
TIEÂU CHUAÅN TOÁI ÖU CUÛA BAØI TOAÙN VAÄN TAÛI
i
a : loaïi doøng i, b j i b : loaïi coät j, a i b : loaïi doøng i vaø coät j a
j Laëp laïi quaù trình treân cho oâ tieáp theo cho ñeán ñeán khi yeâu caàu traïm phaùt vaø traïm thu ñöôïc thoaû maõn.
Baøi toaùn ñoái ngaãu cuûa BTVT Tìm {ui,vj} sao cho: Vôùi caùc caëp ñoái ngaãu: xij 0 vaø vj – ui ≤ cij, i,j Theo ñònh lyù ñoä leäch buø thì phöông aùn {xij} cuûa BTVT coù P.A.T.Ö laø toàn taïi heä thoáng {ui, vj} sao cho: Neáu xij > 0 thì vj – ui = cij, Neáu vj – ui < cij thì xij = 0. Vaäy tieâu chuaån toái öu cuûa BTVT: vj – ui cij, i,j ui: ñöôïc goïi laø theá vò doøng. vj: ñöôïc goïi laø theá vò coät.
Baûng thu ñöôïc vôùi caùc xij > 0 laø phöông aùn cöïc bieân cuûa baøi toaùn.
PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT
PHÖÔNG PHAÙP CHI PHÍ BEÙ NHAÁT
T
30
40
25
35
45
P
42
13
8
7
2
13
35
7
Ví duï 3.2. Duøng phöông phaùp chi phí beù nhaát, tìm phöông aùn cöïc bieân cuûa baøi toaùn vaän taûi coù daïng baûng sau ñaây
28
5
1
10
5
11
28
45
16
5
3
7
16
25
20
60
6
3
4
14
10
T 30 40 25 35 45 P
12
30
42 28 45 60 13 5 16 6 8 1 5 3 7 10 3 4 2 5 7 14 13 11 16 10
18 P.A.C.B treân khoâng suy bieán, vôùi giaù trò Z = 980.
4
Kieåm tra ai = bj = 175
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
PHÖÔNG PHAÙP VOGELS
PHÖÔNG PHAÙP VOGELS Phöông phaùp Vogels (1958) cho P.A.C.B khaù toát theo nghóa giaù trò haøm muïc tieâu cuûa noù khaù gaàn vôùi P.A.T.Ö. Phöông phaùp ñöôïc moâ taû nhö sau
(1) Treân baûng vaän taûi, tính hieäu soá giöõa chi phí beù thöù hai vôùi chi phí beù thöù nhaát.
Ví duï 3.3: Duøng phöông phaùp Vogels, tìm phöông aùn cöïc bieân cuûa baøi toaùn vaän taûi coù daïng baûng sau
T 30 40 25 35 45 P
42 28 45 60 13 5 16 6 8 1 5 3 7 10 3 4 2 5 7 14 13 11 16 10
(2) Choïn soá lôùn nhaát trong caùc hieäu treân vaø phaân phoái toái ña cho oâ coù chi phí beù nhaát moät löôïng xij = min(ai, bj), sau ñoù tính laïi hieäu soá doøng (coät). (3) Quaù trình treân ñöôïc laëp laïi cho ñeán khi chæ coøn laïi moät doøng hay moät coät duy nhaát. (4) Baûng thu ñöôïc vôùi caùc {xij} laø phöông aùn cöïc bieân cuûa baøi toaùn.
PHÖÔNG PHAÙP VOGELS T
35
30
25
40
45
P
5
,1
,5
K
42
13
8
2
7
13
35
7
4
K
28
5
1
5
10
11
HÖÔÙNG GIAÛI BAØI TOAÙN (1) Tìm P.A.C.B khoâng suy bieán ñaàu tieân baèng phöông phaùp chi phí beù nhaát hoaëc Vogels. (2) Duøng tieâu chuaån toái öu vi – uj ≤ cij, i,j ñeå kieåm tra P.A.C.B vöøa tìm ñöôïc. (3) Neáu P.A.C.B thoaû maõn tieâu chuaån toái öu thì P.A.C.B ñoù laø P.A.T.Ö.
28
45
16
5
7
3
16
,11 2
K
25
8
12
(4) Neáu P.A.C.B vöøa tìm chöa thoaû maõn tieâu chuaån toái öu thì tìm caùch söûa ñoåi P.A.C.B cuõ ñeå coù P.A.C.B môùi.
60
6
3
4
14
10
1
K
(5) trôû veà böôùc (2), sau moät soá böôùc laëp höõu haïn, ta seõ coù P.A.T.Ö.
Z = 932
3 K
Phöông phaùp treân goïi laø thuaät toaùn theá vò
30 1 7 K
2 3 K
1 4 K
30 1 3 K
5
Kieåm tra ai = bj = 175
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
LAÄP BAÛNG VAÄN TAÛI
THUAÄT TOAÙN THEÁ VÒ
SÔ ÑOÀ THUAÄT GIAÛI THEÁ VÒ CUÛA BAØI TOAÙN VAÄN TAÛI
Böôùc 1. Laäp baûng vaän taûi
XAÙC ÑÒNH P.A.C.B ÑAÀU TIEÂN (phöông phaùp chi phí beù nhaát hoaëc Vogels)
(1) Kieåm tra ñieàu kieän caân baèng thu – phaùt.
Suy bieán?
Coù Theâm oâ xij=0
(2) Xaùc ñònh P.A.C.B (baèng phöông phaùp chi phí beù nhaát).
(3) Kieåm tra P.A.C.B coù suy bieán hay khoâng
khoâng Tính: Vj = Ui + Cij Ui = Vj – Cij
Neáu P.A.C.B. suy bieán: theâm vaøo oâ (i,j) baát kyø
ij
Coù
ijx
ij
vôùi xij = 0, khoâng taïo thaønh chu trình.
Baøi toaùn coù P.A.T.Ö
ij 0?
Xaùc ñònh P.A môùi q daáu ( ). q daáu ( ). khoâng daáu.
x x x
ij
Neáu P.A.C.B khoâng suy bieán, chuyeån sang [2]
Keát thuùc thuaät giaûi
Böôùc 2. Kieåm tra tính toái öu cuûa baøi toaùn (1) Tính vj = ui + cij
SOÁ BÖÔÙC LAËP LAØ HÖÕU HAÏN
ui = vj – cij, trong ñoù oâ (i,j) laø oâ choïn.
khoâng Choïn oâ vaøo: Maxij Xaùc ñònh voøng ñieàu chænh vaø ñaùnh daáu (+); daáu (–). q = min{xij/ (i, j) daáu (–)}
THUAÄT TOAÙN THEÁ VÒ
THUAÄT TOAÙN THEÁ VÒ
Böôùc 4. Xaùc ñònh P.A.C.B môùi
Choïn ui = 0 taïi doøng baát kyø. (2) Ñaët ij = vj – ui – cij
ij
x x
q daáu ( ); q daáu ( );
ijx
ij
x
khoâng daáu.
ij
Neáu ij ≤ 0: ta coù P.A.T.Ö. Neáu ij > 0: chuyeån sang [3] Böôùc 3. Xaùc ñònh voøng ñieàu chænh (1) Choïn oâ vaøo: Maxij (ij > 0) (2) Choïn oâ ra
Quay veà böôùc [2].
toaùn coù
Sau moät soá böôùc laëp höõu haïn, baøi phöông aùn toái öu.
xaùc ñònh voøng ñieàu chænh oâ vaøo seõ ñöôïc ñaùnh daáu (+). Xen keû daáu (-) vaø daáu (+) treân voøng ñieàu chænh. löôïng ñieàu chænh q = min{xij/ (i,j) coù daáu (-)}
6
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
THUAÄT TOAÙN THEÁ VÒ
THUAÄT TOAÙN THEÁ VÒ
CHUÙ YÙ.
Ví duï 3.4. Giaûi baøi toaùn vaän taûi
T
45
55
30
70
50
40
P
(1) Trong thuaät giaûi baøi toaùn vaän taûi, neáu Maxij ñaït taïi nhieàu oâ, ta choïn moät oâ tuøy yù trong soá caùc oâ ñoù laøm oâ ñieàu chænh.
40 75 60 70 45
9 10 5 2 6
12 12 3 9 11
10 11 6 7 10
8 13 9 8 9
6 9 1 2 8
(2) Trong P.A.T.Ö tìm ñöôïc Xopt, neáu coù ij = 0, maø (i,j) laø oâ loaïi thì ñoù laø daáu hieäu baøi toaùn coù nhieàu P.A.T.Ö khaùc. Ñeå tìm P.A.C.B.T.Ö khaùc, ta choïn oâ (i, j) ñoù laøm oâ ñieàu chænh, roài aùp duïng thuaät toaùn theá vò ñeå xaùc ñònh P.A.C.B.T.Ö khaùc X/
opt.
7 13 7 6 10 Kieåm tra ñieàu kieän caân baèng thu phaùt
(3) Taäp phöông aùn toái öu laø
X = {Xopt + (1 – )X/
opt, 0, 1}
ai = 40 + 75 + 60 + 70 + 45 = 290 bj = 45 + 55 + 30 + 70 + 50 + 40 = 290
Baûng 1
Baûng 2
T
45
55
30
70
50
40
T
45
55
30
70
50
40
P
P
12
9
10
6
12
9
10
6
40
40
10
30
30
10
+2
8 - 13
10
7 + 13
9
10
11
7 + 13
9
0 0
75
75
12 -
12 -
70
25
5
50
+1
+1
+1
+2
7
11 + 6
5
9
7
6
8 - 13 + 9
5
-2 -7
60
60
40
20
20
40
3 + 9
7
2
8
3 + 9
7
8
2
7 2
70
70
40
30
20
20
30
+1
+5
11
6 - 10
1 - 2 + 8
6
11
6 - 10
1 - 2 + 8
10
9
6
1 1
45
45
10 -
9 +
20
+1
-1 -1
25 8
45 8
7
q= 20 q= 5 10 3 9 7 8 5 3 4 7 3
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
Baûng 3
THUAÄT TOAÙN THEÁ VÒ
T
45
55
30
70
50
40
P
•Do caùc ij 0 i,j neân P.A.T.Ö cuûa baøi toaùn laø
12
8
9
10
7
6
40
35
5
12
13
10
11
13
9
-1
75
70
5
0 0 45
5 5 0
0 0 0
0 70 0
35 0 0
0 0 15
optx
3
1
7
6
5
9
-6
60
45
15
9
2
6
7
2
8
0 0
0 45
30 0
0 0
15 25 0 0
1
70
30
15
25
11
8
10
10
6
9
0
45
Vaø Zmin = 1.875 ñôn vò tieàn teä. Ngoaøi ra, baøi toaùn khoâng coù P.A.T.Ö khaùc vì khoâng coù ij = 0, vôùi (i, j) laø oâ loaïi
45 7
-2
Baûng 1
4 2 5 6 2
THUAÄT TOAÙN THEÁ VÒ
Ví duï 3.5. Giaûi baøi toaùn vaän taûi
T 76 62 88 45 40 P
T
76
62
88
45
40
-
+
64
15
P
0 10 19 15 6 7 79
14
88
5 13 7 8 11 4 102
- 10
+ 17
79 102 70 60
10 13 12 12
19 11 17 18
15 8 10 18
6 7 5 10
7 4 3 9
+
30
40
Kieåm tra ñieàu kieän caân baèng thu phaùt
- 10
12
48
ai = 79 + 102 + 70 + 60 = 311 bj = 76 + 62 + 88 + 45 + 40 = 311
+ 10
- 16
1 12 5 3 70 +2 -2 12 18 18 9 60
8
4 13 6 q=30
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
Baûng 2
THUAÄT GIAÛI THEÁ VÒ
T
76
62
88
45
40
P
•Do caùc ij 0 i,j neân
P.A.T.Ö cuûa baøi toaùn vaän taûi
79
34
45
0 10 19 15 6 7
102
44
58
optx
5 13 7 11 8 4
70
0 0 34 44 58 0 30 0 0 0 42 18
45 0 0 0
0 0 40 0
30
40
3 12 5 17 10 3
Vaø Zmin = 2.806 ñôn vò tieàn teä.
60
42
18
-2 12 18 18 10 9
Baøi toaùn khoâng coù P.A.T.Ö naøo khaùc vì khoâng coù ij = 0, vôùi (i, j) laø oâ loaïi.
BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT
6 10 16 13 6
1. TRÖÔØNG HÔÏP 1. ai > bj
CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI
(Xem)
1. BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG
Theâm traïm thu giaû thöù Bn+1 Vôùi nhu caàu thu bn+1 = ai – bj Cöôùc phí vaän taûi ci,n+1 = 0, i = 1, 2, ..., m.
2. TRÖÔØNG HÔÏP 2. ai < bj
THU – PHAÙT
(Xem)
2. BAØI TOAÙN VAÄN TAÛI COÙ DAÏNG HAØM MUÏC
(Xem)
TIEÂU LAØ MAX
(Xem)
3. BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM
Theâm traïm phaùt giaû thöù Am+1 Vôùi nhu caàu phaùt am+1 = bj – ai Cöôùc phí vaän taûi cm+1,j = 0, j = 1, 2, ..., n. Vôùi caùc oâ coù cöôùc phí vaän taûi baèng khoâng ñöôïc goïi laø oâ giaû. Löu yù khi duøng thuaät toaùn theá vò ñeå giaûi baøi toaùn treân, vôùi P.A.C.B ñaàu tieân, ta öu tieân phaân phoái vaøo caùc oâ thöïc.
9
4. BAØI TOAÙN VAÄN TAÛI XE KHOÂNG
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
Baûng 1
BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT
T
65
45
50
30
Ví duï 3.6. Giaûi baøi toaùn vaän taûi sau
P
T
65
45
50
30
60
P
5
25
30
60
10
9
12
7
10 9 0 12 7
+ 9
- 10
55
55
9
11
10
15
55
1 11 15
50
8
7
14
12
- 8
+1
+ 14
50
5
45
Kieåm tra ñieàu kieän caân baèng thu – phaùt
7 12 2
25
25
12 0 0 0 0
ai= 165 < bj= 190 Theâm moät traïm phaùt giaû A4, vôùi a4 = 190 – 165 = 25 vaø c4j = 0, j=1, 2, 3, 4
Baûng 2
T
65
45
50
30
BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT
P
q = 25 10 9 12 7
60
-
+
30
30
0 10 9 12 7
55
30
25
30 30
0 0
0 25
30 0
optx
0 •Phöông aùn cöïc bieân toái öu cuûa baøi toaùn vaän taûi laø 1 9 11 10 15
50
5
45
45
0
0
+ 0
8 14 12 7 2
- 0
5 •vaø Zmin = 1.385
25
25
0 0 11
Coù P.A.T.Ö khaùc
10
q = 30 11 7 9 10
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TOAÙN VAÄN TAÛI KHOÂNG CAÂN BAÈNG THU-PHAÙT
T
65
45
50
30
•P.A.C.B.T.Ö khaùc cuûa baøi toaùn
P
60
30
30
0 30
30 0
0 25
30 0
0 10 9 12 7
35 15
0
0
optx
•Vaø Z’
min =1.385
55
30
25
•Taäp P.A.T.Ö cuûa baøi toaùn
1 9 11 10 15
50
•Zopt = Xopt + (1 – ) X/
opt
35
15
8 7 14 12 2
25
•Hay
30 30
30 30 0
0 25
30 0
optZ
25
35 30
15 30
0
0
0 0 0 0 11
MOÂ HÌNH BAØI TOAÙN VAÄN TAÛI COÙ HAØM MUÏC TIEÂU LAØ MAX
Tìm {xij} sao cho:
m n
Z
max
c x ij ij
i
1
j
1
n
1,
m
x ij
a i , i
j
1
10 9 11 7
m
1,
n
x ij
b j , j
i
1
m
n
0;
0;
0;
b
0;
1,
m j ;
1,
n .
x ij
c ij
a i
j
b i j
a i
i
1
j
1
1. Khi xaây döïng P.A.C.B ñaàu tieân, ta phaân phoái toái ña vaøo oâ coù cöôùc phí lôùn nhaát. 2.Tieâu chuaån toái öu laø vj – ui cij, i,j 3.OÂ ñieàu chænh laø oâ coù {minij, vôùi ij < 0}
11
THUAÄT GIAÛI BAØI TOAÙN VAÄN TAÛI COÙ HAØM MUÏC TIEÂU LAØ MAX Gioáng nhö baøi toaùn QHTT coù haøm muïc tieâu laø max, chuùng ta coù theå ñöa baøi toaùn vaän taûi coù haøm muïc tieâu Z max veà Z/ = – Z min, sau ñoù duøng thuaät toaùn theá vò ñeå giaûi. Tuy nhieân, chuùng ta cuõng coù theå giaûi tröïc tieáp baøi toaùn naøy baèng thuaät toaùn theá vò vôùi moät vaøi thay ñoåi trong thuaät giaûi nhö sau:
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM MUÏC TIEÂU Z Max
THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM MUÏC TIEÂU Z Max
T
200
400
600
800
P
650
400
250
25 20 18 22 10
-2 -3
1000
Ví duï 3.7. Moät coâng ty coù 3 xí nghieäp cuøng saûn xuaát moät loaïi boùng ñeøn. Naêng suaát trong thaùng cuûa 3 xí nghieäp laàn löôït laø Ai = (650, 1.000, 350) boùng. Hôïp ñoàng coâng ty phaûi giao cho 4 nhaø phaân phoái laø Bj = (200, 400, 600, 800) boùng. Ñôn giaù baùn cuûa moãi boùng ñeøn töông öùng vôùi caùc nhaø phaân phoái ñöôïc cho bôûi ma traän sau: Ñvt: 1.000 ñoàng
22 25 20 18
200
400
400
30 32 25 28
ijc
32 0 + 25 – 28 30
350
29 28 25 23
350
28 5 25 + 23 – 29
Haõy tìm keá hoaïch phaân phoái haøng sao cho coâng ty ñaït doanh soá lôùn nhaát
THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM MUÏC TIEÂU Z Max
THUAÄT GIAÛI THEÁ VÒ VÔÙI HAØM MUÏC TIEÂU Z Max
T
200
400
600
800
T
200
400
600
800
P
P
-4 -1 q = 200 + 30 – 30 32 28
650
650
200
200
450
450
22 25 20 18 22 25 20 18 10 7
-3
1000
1000
400
600
200
800
30 + 32 25 – 28 0 30 32 25 28 0
350
350
150
150
200
200
29 – 28 25 + 23 5 29 28 25 23 2
12
-1 q = 200 Z = 52.350 34 31 30 27 32 28 32 28
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM
THUAÄT GIAÛI BAØI TOAÙN VAÄN TAÛI COÙ HAØM MUÏC TIEÂU LAØ MAX
Baøi toaùn vaän taûi coù oâ caám laø baøi toaùn vaän taûi vôùi P.A.T.Ö cuûa noù phaûi thoûa ñieàu kieän cho tröôùc.
•Do caùc ij 0, i, j
0
200 450
0
Ñeå giaûi baøi toaùn naøy, ta laäp baøi toaùn vaän taûi môû roäng VTM baèng caùch cho giaù cöôùc vaän chuyeån ôû caùc oâ caám baèng M, vôùi M > 0 lôùn tuøy yù roài duøng thuaät toaùn theá vò. Coù 2 tröôøng hôïp xaûy ra
optx
0 200
200 0
0 150
800 0
1.Trong P.A.T.Ö cuûa baøi toaùn VTM, neáu caùc oâ caám coù xij = 0 thì P.A.T.Ö cuûa baøi toaùn VTM cuõng chính laø P.A.T.Ö cuûa baøi toaùn goác.
•P.A.T.Ö CUÛA BAØI TOAÙN
2.Trong P.A.T.Ö cuûa baøi toaùn VTM, neáu caùc oâ caám coù xij 0 thì baøi toaùn goác khoâng coù P.A.T.Ö.
BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM
•Vaø ZMax = 52.350
T
140
150
180
25
P
Ví duï 3.8. Giaûi baøi toaùn vaän taûi sau ñaây vôùi
Nhu caàu traïm phaùt a = (150, 100, 145, 100)
Baûng 1
150
Nhu caàu traïm thu b = (140, 150, 180)
5
4
6
5 4 6 0 4
Ma traän cöôùc vaän chuyeån
0 150
100
ijc
8 5 9 +3 M-4 0 1
8 9 5 11 6 12
100 +2
9
7 13
145
1 – 11 6 12 +3 M-1 + M
145 +1
100
9 7 13 M 0
vôùi ñieàu kieän traïm A3, A4 phaûi phaùt heát haøng. Kieåm tra ñieàu kieän caân baèng thu – phaùt ai = 150 + 100 + 145 + 100 = 495 bj = 140 + 150 + 180 = 470 Laäp traïm thu giaû, vôùi b4= 25 vaø M > 0 tuøy yù.
+ 9
13
40 35 25 +1 q = 25 8 13 – M
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
T
140
150
180
25
T
140
150
180
25
P
P
Baûng 3 Baûng 2
150
150
5 4 6 0 5 4 6 0 3 4
+ 8
0 150 0 150 +3
100
100
– 5 9 0 8 5 9 0 0 1
+ 12
+ 12
145
145
75 25 35 40 25 +2 +2 +3 -3 1 – 11 6 M – 11 6 M
145 145 +1 +4
+ 7
100
100
9 – 13 M 9 7 13 M -1 0
+ 9
65 35 100 +1 +1 q = 40 q = 35 – 13 8 7 9 0 8 1
T
140
150
180
25
T
140
150
180
25
P
P
Baûng 4 Baûng 5
150
150
5 4 6 0 5 4 6 0 0 0
40 40 110 5 105 +4 +1
+ 9
+ 9
100
100
8 – 5 0 8 – 5 0 -3 1
25 25 75 75 +2
+ 6
145
145
-2 -2 11 – 12 M 11 6 12 M
145 40 105
+ 7
100
100
9 7 13 M 9 – 13 M -4 -4
14
100 +1 +1 100 +1 q = 5 q =105 5 4 -3 5 4 10 1 6
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM
T
140
150
180
25
P
Baûng 6
150
•Do caùc ij 0 i,j neân 5 6 4 0 3 •P.A.C.B.T.Ö cuûa baøi toaùn vaän taûi treân laø 40 110
+ 9
40
0
110
100
– 8 5 0 0
0
5
70
5 25 70 0
+ 11
145
optx
-1 – 12 6 M
145
0 100
145 0
0 0
100
9 13 7 M -1
•vaø Zmin= 3.285
100 Z =3.285 9 0 5 q = 40 8 P.A.T.Ö khaùc
BAØI TOAÙN VAÄN TAÛI COÙ OÂ CAÁM
T
140
150
180
25
P
Baûng 7
150
4 5 6 0 3
o p tx
1 5 0 3 0 0
0 5 1 4 5
0 4 0 0
150 0
•vaø Zmin= 3.285
100
1 0 0
0
0
5 8 9 0 0
•P.A.C.B.T.Ö khaùc cuûa baøi toaùn vaän taûi treân laø
•Taäp phöông aùn toái öu
5 25 30 40
opt
145
-1 6 11 12 M
145
•Zopt = Xopt + (1 – ) X/ 4 0
4 0
4 0
0 5
1 5 0 3 0
4 0 4 0
•Hay
100
o p tZ
7 9 13 M -1
0 1 0 0
1 4 5 0
0 0
15
100 Z =3.285 5 8 9 0
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI
trôû
MOÂ HÌNH BAØI TOAÙN VAÄN TAÛI XE KHOÂNG Ñieàu kieän raøng buoäc cuûa baøi toaùn vaän taûi xe khoâng laø moät soá traïm phaùt Ai phaûi phaùt ñuû haøng cho traïm Bj (ñöôïc chæ ñònh). Xaùc ñònh loä trình xe chaïy khoâng taûi töø Bj ñeán Ai laø ít nhaát. Khi ñoù thaønh traïm thu xe traïm phaùt Ai khoâng, traïm thu Bj trôû thaønh traïm phaùt xe khoâng vaø khi ñoù ma traän (cij) laø ma traän khoaûng caùch töông öùng giöõa Ai vaø Bj.
ijx
lieân tieáp nhau,
xij
Qui öôùc söû duïng caùc kyù hieäu nhö sau: : löôïng haøng hoùa coù vaän taûi. : löôïng haøng cuûa xe khoâng taûi. : tuyeán xe chaïy coù taûi. : tuyeán xe chaïy khoâng taûi
1. Laäp baûng vaän taûi töông öùng vôùi ma traän khoaûng caùch. Duøng thuaät toaùn theá vò tìm P.A.T.Ö cuûa baøi toaùn xe khoâng taûi. 2. Taïo baûng phoái hôïp P.A.T.Ö cuûa baøi toaùn xe khoâng taûi vôùi keá hoaïch vaän taûi ñaõ cho tröôùc. Laäp tuyeán ñieàu ñoäng töông öùng. 3. Giaûm löôïng cheânh leäch giöõa “oâ troøn” vaø “oâ vuoâng” ñeå coù baûng môùi thu goïn. 4. Laäp voøng ñieàu ñoäng goàm caùc oâ coù taûi vaø oâ löôïng ñieàu ñoäng q= khoâng taûi min{xij}, vôùi xij coù taûi vaø xij khoâng taûi. Trôû veà [3]. Sau moät soá böôùc laëp höõu haïn [3] vaø [4], ta seõ thu ñöôïc keá hoaïch ñieàu ñoäng haøng hoùa toái öu.
THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI
THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI
Ví duï 3.9. Moät coâng ty vaän taûi coù keá hoaïch vaän chuyeån haøng hoùa theo hôïp ñoàng, ñöôïc theå hieän qua baûng yeâu caàu nhö sau
Cho bieát khoaûng caùch giöõa ñòa ñieåm cung caáp haøng vaø ñòa ñieåm nhaän haøng (km) ñöôïc theå hieän qua ma traän nhö sau:
Kyù hieäu
Loaïi haøng
Löôïng (taán)
Ñòa ñieåm caáp haøng Ai
L
20
Nôi nhaän haøng Bj Coâng ty rau quaû
Cam
A1
30 25
Cöûa haøng soá 3 Cöûa haøng soá 1
Döa haáu
A2
3412 4625 5243 Haõy xaùc ñònh loä trình vaän chuyeån haøng hoùa thoûa yeâu caàu hôïp ñoàng vaø toång taán – km xe chaïy khoâng taûi nhoû nhaát.
Saàu rieâng
A3
15 10 50 20
Coâng ty rau quaû Cöûa haøng soá 3 Cöûa haøng soá 4 Coâng ty rau quaû
B2 B3 B1 B2 B3 B4 B2
16
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
Baûng 2
Böôùc 1 (tìm P.A.T.Ö cuûa baøi toaùn xe khoâng taûi)
Baûng 1
Böôùc 2 (taïo baûng phoái hôïp) 55
25
40
50
Bj
25
55
40
50
Bj
Ai
Ai
20
30
50
50
1 4 3 2 2 1 4 3 2
25
15
10
50 50
50
50
20
50
5 2 6 4 5 2 6 4 1 5 45 5 45
70
70
4 2 5 3 0 3 4 2 5
25 40 25 40 5
1km 2km
5km
3 3 2 5
A1 A2 A3
B2 B2 B4
Baûng 3
Baûng 4
Böôùc 3 (laäp tuyeán ñieàu ñoäng)
Böôùc 3 (laäp tuyeán ñieàu ñoäng)
25
55
40
50
25
55
40
50
Bj
Bj
Ai
Ai
30
Zmin= 420 taán – km 5 A1: 20 T X 1km = 20T – km A2: 5 T X 2km = 10T – km A3: 5 T X 5km = 25T – km
10
50
50
2 1 4 3 1 4 3 2
25
10
10
30 10
5
10
10
50
50
5 2 6 4 5 2 6 4
20
45
45 25
25
70
70
3 4 2 5 4 2 5 3
3km
1km
3km
A2
2km
4km
B1 A3
B2 A1 A2:20Tx10km=200T-km
17
40 5 20 q=5 q=20 B3 A3 B4 25 A3 B4 A2 4km B1 A2: 5T x 7km = 35T–km.
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
Baûng 5
Baûng 6
Böôùc 3 (laäp tuyeán ñieàu ñoäng)
Böôùc 3 (laäp tuyeán ñieàu ñoäng)
25
55
40
50
25
55
40
50
Bj
Bj
Ai
Ai
10
50
50
2 1 4 3 2 1 4 3
10
10
10
10
50
50
5 2 6 4 5 2 6 4
20
10
20 10
70
70
3 4 2 5 3 4 2 5
1km
2km
2km
4km
4km
20 10 q=10 q=10 A2 B3 A3 A2 A3 B4
THUAÄT GIAÛI BAØI TOAÙN XE KHOÂNG TAÛI
BAØI TAÄP CHÖÔNG 3
LAÄP MOÂ HÌNH CUÛA BAØI TOAÙN VAÄN TAÛI
[1]
[2]
B2 B4 A1 A2: 10T x 7km = 70T–km B3 A2 : 10 T x 6km = 60T–km
TÌM PHÖÔNG AÙN CÖÏC BIEÂN ÑAÀU TIEÂN
BAÛNG ÑIEÀU ÑOÄNG XE 1km 2km
Ths. Nguyeãn Coâng Trí
[3c*] [3d]
[3a]
[3b]
[3e]
5km 3km
GIAÛI BAØI TOAÙN VAÄN TAÛI CAÂN BAÈNG THU - PHAÙT
2km
4km
[4]
[6]
[8]
[7]
[9]
[5]
3km
A1 A2 A3 A2 A1 B3
Copyright 2001
1km
CAÙC DAÏNG KHAÙC CUÛA BAØI TOAÙN VAÄN TAÛI
1km B2 A2: 20 T 4km B4 2km B3
4km
[10a]
[10b]
[10c]
2km
4km
[11a]
[11b]
[11c]
[11d]
A2 A2 A2: 5 T A3
18
A2 B2 B2 B4 B1 A3 B1 B2 B4 B3 A1: 20 T A2: 5 T A3: 5 T A3 B4 A3 A1 A2: 10 T A3 B4 A2: 10 T
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
max
5
4
4
5
3
4
z
BAØI TAÄP CHÖÔNG 3 Goïi xij laø soá lao ñoäng trình ñoä i (i = kyõ sö, trung caáp, coâng nhaân) ñöôïc boá trí vaøo nhieäm vuï j (j = maùy tröôûng, maùy 1, maùy 2, maùy 3). x 5 33
x 23
x 32
x 34
x 22 25
x 11
x 12
20
x 12 x 22
x 13 x 23
x 21 x 14 x 24
BAØI TAÄP CHÖÔNG 3 1. Moät coâng ty vaän taûi bieån caàn 110 ngöôøi ñeå boá trí vaøo caùc nhieäm vuï: 10 maùy tröôûng; 25 thôï maùy 1; 30 thôï maùy 2; 45 thôï maùy 3. Phoøng toå chöùc nhaân söï tuyeån ñöôïc 90 ngöôøi, trong ñoù goàm 25 kyõ sö maùy; 20 kyõ thuaät vieân trung caáp vaø 45 coâng nhaân coù kinh nghieäm.
45
x 32
x 33
Nhieäm vuï
x 34 10
Trình ñoä
25
x 31 x 32
30
45
x 21 x 22 x 23 x 24
x 33 x 34
x 11 x 21 x 31 x 11 x 12 x 13 x 14
Kyõ sö Trung caáp Coâng nhaân
Ñieåm ñaùnh giaù naêng löïc (aij) Maùy tröôûng Maùy 1 Maùy 2 Maùy 3 4 5 1
0 4 5
0 0 4
5 3 0
0,
i
1,3,
j
1, 4
x ij
Haõy boá trí nhaân löïc sao cho coâng vieäc toái öu.
BAØI TAÄP CHÖÔNG 3 Goïi xij laø ñaáu thuû i cuûa ñoäi I ñöôïc xeáp thi ñaáu
0, 4
0, 7
0, 6
0, 5
0,8
z
x 14
x 12
x 11
x 13
vôùi ñaáu thuû j cuûa ñoäi II (i, j = 1, 2, ..., 5). x 15 x
0, 4
0, 4
0, 7
0, 3
x
Ñoäi II
0, 2
0, 6
0, 4
0,3
0, 5
x 22 x 32
Ñaáu Thuû 1
0, 6
0,3
x
0, 4
x 24 x 34 x
0, 7
25 x 35 x
0, 6
x 31 x 41
42
44
23 x 33 x 43
45
0, 2
0,3
0, 4
0, 6
max
x 52
x 53
x 54
x 55
5
1,
i
1,5
x ij
j
1
5
1,
j
1,5
BAØI TAÄP CHÖÔNG 3 2. Hai ñoäi tuyeån boùng baøn, moãi ñoäi coù 5 ngöôøi. Qua thoáng keâ nhieàu traän ñaáu trong quaù khöù, ngöôøi ta döï ñoaùn xaùc suaát thaéng cuoäc moãi ñaáu thuû cuûa moãi ñoäi ñöôïc theå hieän qua baûng sau Ñaáu Thuû 5 0,8 0,7 0,5 0,6 0,6
Ñoäi I Ñaáu thuû 1 0,4 Ñaáu thuû 2 0 Ñaáu thuû 3 0,2 Ñaáu thuû 4 0,6 0 Ñaáu thuû 5
Ñaáu Thuû 3 0,6 0,4 0,4 0,4 0,3
Ñaáu thuû 4 0,7 0,4 0,3 0,7 0,4
x ij
i
1
0,1
i
,
j
1, 5
x ij
Ñaáu Thuû 2 0,5 0,3 0,6 0,3 0,2 Haõy saép xeáp caùc ñaáu thuû cuûa ñoäi I sao cho xaùc suaát thaéng toaøn ñoaøn cuûa ñoäi I cao nhaát.
19
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TAÄP CHÖÔNG 3 3.b) Tìm phöông aùn cöïc bieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels
BAØI TAÄP CHÖÔNG 3 3.a) Tìm phöông aùn cöïc bieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels
Bj
Bj
3 5 10 14
20 25 30 15
Ai 10 1 3 7 1 15 2 4 2 3 6 5 4 1 7
4 5 1 2 3 4 7 8 2 6 9 3
Ai 40 20 30
Kieåm tra ñieàu kieän caân baèng thu phaùt ai = 40 + 20 + 30 = 90 bj = 20 + 25 + 30 + 15 = 90
BAØI TAÄP CHÖÔNG 3 3.c*) Tìm phöông aùn cöïc bieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels
BAØI TAÄP CHÖÔNG 3 3.d) Tìm phöông aùn cöïc bieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels
Bj
Bj
10 30 50
40 30 20 50
Ai 25 10 45
7 6 5 2 1 4 3 5 2
3 7 4 6 4 6 2 5 1 5 7 8
Ai 30 40 70
Kieåm tra ñieàu kieän caân baèng thu phaùt ai = 25 + 10 + 45 = 80 bj = 10 + 30 + 50 = 90 Thêm trạm phát giả thứ 4, với a4 = bj - ai = 10, c4j = 0, j = 1, 2, 3.
20
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TAÄP CHÖÔNG 3
4. Giaûi baøi taäp [3], vôùi
BAØI TAÄP CHÖÔNG 3 3.e) Tìm phöông aùn cöïc bieân baèng hai phöông phaùp chi phí beù nhaát vaø phöông phaùp Vogels
a) Phöông aùn cöïc bieân ñaàu tieân thu ñöôïc baèng
Bj
phöông phaùp chi phí beù nhaát,
30 20 25 35 40
b) Phöông aùn cöïc bieân ñaàu tieân thu ñöôïc baèng
phöông phaùp Vogels.
13 7 6 2 12 5 1 10 5 11 10 5 3 7 14 6 3 2 11 10
Ai 30 20 40 60
BAØI TAÄP CHÖÔNG 3
BAØI TAÄP CHÖÔNG 3
6. a) Giaûi baøi toaùn vaän taûi
5. a) Giaûi baøi toaùn vaän taûi
50
160
120
80
Bj
Bj
20 100 45 15
Ai
10 3 9
6 4 4
4 2 3
1 5 7
Ai 90 40 50
220 100 90
5 5 10
4 9 6
3 7 8
10 12 15
b) Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? Neáu coù, chæ ra taäp phöông aùn toái öu.
b) Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? Neáu coù, chæ ra phöông aùn toái öu ñoù.
21
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TAÄP CHÖÔNG 3
BAØI TAÄP CHÖÔNG 3
8. Cho baøi toaùn vaän taûi coù daïng
7. Cho baøi toaùn vaän taûi coù daïng
4 2 5 7 6
20, 110, 120
ia
38, 45, 66, 45
ia
5 8 3 4 5
ijc
ijc
70, 40,30,60,50
jb
52, 45, 38, 59
2 1 4 3 2
jb
5 9 10 7 10 10 8 4
14 6 15 9 6 7 13 14
a) Tìm P.A.T.Ö cuûa baøi toaùn treân.
a) Tìm P.A.T.Ö cuûa baøi toaùn treân.
b) Theo baïn daáu hieäu naøo cho ta bieát BTVT coù
nhieàu P.A.T.Ö? P.A.C.B.T.Ö tìm ñöôïc ôû caâu
b) Phöông aùn toái öu vöøa tìm ñöôïc coù duy thích). Chæ ra moät
a) coù duy nhaát khoâng? Neáu coù, haõy chæ ra
nhaát khoâng? (coù giaûi phöông aùn toái öu khaùc? (neáu coù).
P.A.C.B.T.Ö khaùc?
c) Tìm taäp caùc P.A.T.Ö vaø chæ ra 3 P.A.T.Ö?
BAØI TAÄP CHÖÔNG 3
BAØI TAÄP CHÖÔNG 3 10. a) Giaûi baøi toaùn vaän taûi sau ñaây vaø tìm
9. Giaûi baøi taäp [1], [2].
phöông aùn toái öu khaùc (neáu coù).
Bj
60 60 80 100
4 10 6
5 3 4
6 12 5 9 9 7
Ai 80 70 100
22
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TAÄP CHÖÔNG 3
BAØI TAÄP CHÖÔNG 3
10. b) Giaûi baøi
toaùn vaän taûi sau ñaây vaø
tìm
10. c) Giaûi baøi
toaùn vaän taûi sau ñaây vaø
tìm
phöông aùn toái öu khaùc (neáu coù).
Traïm phaùt
Traïm phaùt
phöông aùn toái öu khaùc (neáu coù).
Traïm thu
Traïm thu
79, 50, 60, 50 46, 45, 76, 20, 52
100, 20, 30, 50 70, 60, 25, 50
ia jb Ma traän cöôùc phí vaän taûi
ia jb Ma traän cöôùc phí vaän taûi
8 10 14 24 30 20 18 14
10 1 5
5 6 10
13 8
8 13
ijc
ijc
2 8
7 6 12 16 14 36
2 3 13 5
8 7
6 9 10 13
BAØI TAÄP CHÖÔNG 3
BAØI TAÄP CHÖÔNG 3
11. a) Giaûi baøi toaùn vaän taûi coù oâ caám sau ñaây vaø
11. b) Giaûi baøi toaùn vaän taûi coù oâ caám sau ñaây vaø
tìm phöông aùn toái öu khaùc (neáu coù).
Traïm phaùt
Traïm phaùt
Traïm thu
Traïm thu
100, 80, 50 65, 90, 50, 30
tìm phöông aùn toái öu khaùc (neáu coù). 90, 40, 50 20, 100, 45
ia jb Ma traän cöôùc phí vaän taûi
ia jb Ma traän cöôùc phí vaän taûi
10 6 4
10
9 12
7
ijc
ijc
3 9
4 2 4 3
9 8
11 10 15 7 14 12
Ñieàu kieän A3 phaûi phaùt heát haøng.
Ñieàu kieän B2 phaûi thu ñuû haøng.
23
ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 3
BAØI TAÄP CHÖÔNG 3
BAØI TAÄP CHÖÔNG 3
11. c) Giaûi baøi toaùn vaän taûi coù oâ caám sau ñaây vaø
11. d) Giaûi baøi toaùn vaän taûi coù oâ caám sau ñaây vaø
tìm phöông aùn toái öu khaùc (neáu coù).
tìm phöông aùn toái öu khaùc (neáu coù).
Traïm phaùt
Traïm phaùt
Traïm thu
Traïm thu
220, 100, 90 50, 160, 120, 80
90, 40, 50 20, 100, 45
ia jb Ma traän cöôùc phí vaän taûi
ia jb Ma traän cöôùc phí vaän taûi
5
4 3 10
10 6 4
ijc
ijc
5 9 7 12 10 6 8 15
3 9
4 2 4 3
Ñieàu kieän traïm phaùt A3 khoâng ñöôïc phaùt cho traïm thu B2.
Ñieàu kieän traïm thu B2 khoâng ñöôïc thu cuûa traïm phaùt A1.
24
