BÀI 3
̣ ̃
ng hang phat ra t ng ươ ́ ượ ̀ ̣ ́ ̀ ́
ng la a ̀
1,…,am
ng hang t ng ̣ ượ ươ ̀ ̣ ̀ ̀
̀
1,…,bn
tram ̣ ơ ́ ừ ́ ̣ ̉ ̣ ̀ ̣
m
n
j
1. Đinh nghia: A1, …,Am la m tram phat, co l ứ B1,…, Bn la n tram thu cân nhâp l ng la b ứ cij c ướ phat Á ́ ̣
= 1
i
= 1
j
… …
Phat́
B1 b1
B2 b2
Bn bn
c phi vân chuyên môt đ n vi hang hoa t j. i đên tram thu B =� � Thu b a i
c11
c12
A1 a1
c1n
c21
c22
A2 a2
c2n
Am am
cm1
cm2
cmn
Điêu kiên: ̀ ̣
2. Mô hinh toan hoc cua bai toan vân tai: ̀ ́ ̣ ̉ ̀ ́ ̣ ̉
ng hang hoa ta se vân chuyên t tram Goi x̣ ́ ượ ̉ ừ ̀ ̀ ́ ̃ ̣ ̣
ij la khôi l
phat Á ́ ̣ ́
i đên tram thu B
j (i = 1,..,m; j = 1,…,n), ta co mô
hinh: ̀
(cid:0)
min
c xij ij
m n � � = = i j 1 1 n
=
=
(cid:0)
1,...,
m
x ij
a i , i
= 1 j m
=
=
(cid:0)
b
,
j
1,...,
n
x ij
j
= 1
i
=
=
(cid:0)
0,
i
1,...,
m j ;
1,...,
n
x ij
3. Ph ng an cua bai toan vân tai: ươ ́ ̉ ̀ ́ ̣ ̉
̣ ́ ̉ ̀ ́ ̣ ̉ ̀ ̣ ̣
X
Môt ph ( = ́ ̀ ́ ́
0 ijx trong đo la cac sô không âm sao
(cid:0) ng an cua bai toan vân tai la môt ma trân ươ )0 x ij m n
0 cho:
m
n
=
=
=
=
1,...,
n
1,...,
m
0 x ij
b j , j
(cid:0) (cid:0)
a i , va ̀ i
0 x ij
= 1
j
= 1
i
4. Ph ng an c ban cua bai toan vân tai: ươ ơ ́ ̉ ̉ ̀ ́ ̣ ̉
ng an c ban cua bai toan - Ô choṇ : trong môt ph ươ ơ ̣ ́ ̉ ̉ ̀ ́
vân tai cac ô co l ng hang d ng đ c goi la ô ́ ượ ươ ượ ̣ ̉ ́ ̀ ̣ ̀
chon, cac ô co l ng hang băng 0 đ c goi la ô loai. ́ ượ ượ ̣ ́ ̀ ̀ ̣ ̀ ̣
- Vong: Môt day cac ô chon cua môt ph ng an nao ươ ̀ ̣ ̃ ́ ̣ ̉ ̣ ́ ̀
đo đ c goi la tao nên môt vong nêu môi ô trong day ́ ượ ̣ ̀ ̣ ̣ ̀ ́ ̃ ̃
ô đo đêu phai năm trên cung môt dong (côt) chi v i ̉ ớ ́ ̀ ̉ ̀ ̀ ̣ ̀ ̣
môt ô đ ng tr c no đông th i phai năm trên cung ứ ướ ờ ̣ ́ ̀ ̉ ̀ ̀
môt côt (dong) chi v i môt ô đ ng sau no. ̉ ớ ứ ̣ ̣ ̀ ̣ ́
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Vong th ng co dang sau: ườ ̀ ́ ̣
Sô ô chon trong vong luôn la môt sô chăn: ́ ̣ ̀ ̀ ̣ ́ ̃
Ph ng an c ban: môt PA cua bai toan vân tai đ c ươ ơ ̉ ượ ́ ̉ ̣ ̉ ̀ ́ ̣
goi la PA c ban nêu cac ô chon cua PA đo không tao ơ ̣ ̀ ̉ ́ ́ ̣ ̉ ́ ̣
thanh vong. ̀ ̀
́ ́
Chu y: Môt ph ng an cua bai toan vân tai co m + n ô ươ ̣ ́ ̉ ̀ ́ ̣ ̉ ́
ng an không c ban. ở ươ ơ ̣ ̀ ̣ ́ ̉
chon tr lên luôn la môt ph PACB co sô ô chon băng m + n -1 goi la PACB ́ ́ ̣ ̀ ̣ ̀
không suy biêń PACB co sô ô chon nho h n m + n – 1 goi la PACB ̉ ơ ́ ́ ̣ ̣ ̀
suy biêń “Ô chon không” la ô loai đ c bô sung đê co ̣ ượ ̣ ̀ ̉ ̉ ́
PACB không suy biên. ́
ng an c ban: ơ ́ ̉
ươ ́ ́
ự ươ ng phap tây – băc: u tiên phân phôi tôi đa hang lân l t vao cac ô phia ̀ ượ ở ́ ́ ̀ ̀ ́ ́
́ ̉ ̉ ́ ́ ̣ ́ ́ ́
̀ ̀ ́ ̣ ̣ ̉ ̀
5. Xây d ng ph a. Ph Ư Tây băc cua bang cho đên khi cac tram phat phat hêt hang va cac tram thu nhân đu hang. Vi du: ́ ̣
B1:25 B2:25 B3:10
A1:10 5
3
1
A2:30 7
6
8
A3:20 3
2
2
ng phap c ươ ướ ́ ́ ́ ́
t vao cac ô co c phi thâp nhât: ̀ ượ ́ ́ ̀ ̀ ́ ́
c phi thâp nhât cho đên khi cac tram phat phat hêt u tiên phân phôi tôi đa hang lân l ướ ́ ́ ́ ́ ́ ̣ ́ ́ ́
̀ ̀ ́ ̣ ̣ ̉ ̀
b. Ph Ư c hang va cac tram thu nhân đu hang. Vi du: ́ ̣
B1:25 B2:25 B3:10
A1:10 5
3
1
A2:30 7
6
8
A3:20 3
2
2
6. Tính ch t c a bài toán v n t i: ấ ủ ậ ả
Tính ch t 1: M i bài toán v n t ọ ậ ả ề i đ u có PAT . Ư ấ
Tính ch t 2: S ô ch n trong m t ph ng án c b n ộ ọ ố ấ ươ ơ ả
c a m t bài toán v n t i không bao gi t quá m + ậ ả ủ ộ v ờ ượ
n – 1 ô.
Tính ch t 3: Khi thêm vào m t ph ng án c b n ộ ấ ươ ơ ả
không suy bi n c a m t bài toán v n t i m t ô ch n ậ ả ủ ộ ế ọ ộ
ng thì ô ch n đó cũng t o v i m t s ô ch n c a ph ớ ộ ố ủ ọ ọ ạ ươ
án thành m t vòng duy nh t. ộ ấ
7. Gi i bài toán v n t i b ng ph ả ậ ả ằ ươ ng pháp th v : ế ị
ế ậ ấ
B c 1: ướ 1) Xây d ng PACB xu t phát. L p PACB không suy bi n xu t phát ự ấ
ủ ế ấ
ườ ọ
2) Ki m tra tính không suy bi n c a PACB xu t phát: N u t ng s ô ch n là m + n – 1 ố ng án không suy bi n, ươ ế
ướ N u t ng s ô ch n < m + n – 1 c 2. ế ổ ườ ố ọ
ể Tr ng h p 1: ế ổ ợ thì PACB xu t phát là ph ấ ta chuy n qua b ể Tr ng h p 2: ợ thì
ả ổ
ộ ố ng án không suy c 2. ta ph i b sung vào PACB xu t phát m t s “ô ch n không” đ đ ọ bi n tr ướ ế ấ c m t ph ươ ộ ể ượ c khi chuy n sang b ướ ể
ố ư ấ
c xây ế ị ượ ấ
Đánh giá tính t B c 2: ủ ướ i, vj). 1) Xây d ng h th ng th v (u ệ ố ự H th ng th v (u d ng theo công th c u
i, vj) c a PACB xu t phát đ ứ
ệ ố ự i u c a PACB xu t phát. ế ị ủ i + vj = cij.
2) Tính các h s c l ng Δ ệ ố ướ ượ
ij.
Các h s c l ng c a các s đ c tính theo quy t c ệ ố ướ ượ ố ượ ủ ắ
c l ng c a các ô ch n là 0. ệ ố ướ ượ ủ ọ
sau: H s H s c l ng c a ô lo i (i, j) đ c tính theo công ệ ố ướ ượ ủ ạ ượ
th c Δứ
ij = ui + vj – cij
3) Đánh giá tính t i u c a PACB xu t phát. ố ư ủ ấ
Tr c l ng các ô đ u ườ ng h p 1: n u các h s ế ệ ố ướ ượ ợ ở ề
không d ng thì PACB xu t phát là PAT c a bài toán, ươ Ư ủ ấ
thu t toán k t thúc v i PAT là PACB xu t phát. Ư ớ ế ấ ậ
Tr ng h p 2: N u có m t ô lo i có h s c l ng ườ ệ ố ướ ượ ộ ợ ế ạ
d ng thì PACB xu t phát ch a t i u, bài toán ti p t c ươ ư ố ư ế ụ ấ
b ng cách l p PACB m i. ậ ớ ằ
Chú ý: n u các h s c l ng c a các ô lo i đ u là ệ ố ướ ượ ế ạ ề ủ
s âm thì PACB xu t phát là PAT duy nh t c a bài ấ ủ Ư ố ấ
toán. Ng i c l ượ ạ i thì bài toán có th có nhi u PACB t ể ề ố
u.ư
Xây d ng PACB m i. B c 3: ướ ự ớ
ệ ố ọ
ọ ớ
1) Tìm ô lo i đ a vào h th ng ô ch n. Ô lo i đ h s ng l n nh t. ạ ư c đ a vào làm ô ch n trong PACB m i là ô có ư ạ ượ ng d c l ệ ố ướ ượ ươ ớ ấ
Xây d ng PACB m i. B c 3: ướ ự ớ
ọ ư
ị ọ c ô đ a ra kh i h th ng ô ch n ta ỏ ệ ố
ệ ự ể ả
2) Tìm ô đ a ra kh i h th ng ô ch n ỏ ệ ố Đ xác đ nh đ ư ượ ệ ề Tìm vòng đi u ch nh: T ô ch n m i đ a vào ta n i ố ừ ớ ư ọ
ph i th c hi n các công vi c sau: ỉ i đ tìm vòng g i là vòng đi u ọ ạ ể ể
Xác đ nh ô ch n, l ẽ ẵ ấ ỉ
trong vòng đi u ch nh: L y ô ề ố ố
ẽ ỉ
v i ô ch n còn l ọ ớ ch nh. ỉ ị m i đ a vào làm ô s 1, ta đánh s các ô trong vòng ớ ư ; các ô 2, 4, … là các ô đi u ch nh. Các ô 1,3,… là ô l ề ch n.ẵ
ẵ ỏ ấ
ượ ấ
Tìm ô ch n có l Ô ch n có l ượ ẵ ỏ ệ ố ng hàng nh nh t. ượ ng hàng q nh nh t là ô đ ỏ ng hàng q g i là l ọ ượ ọ c đ a ra ư ng ượ
kh i h th ng ô ch n. L hàng đi u ch nh. ề ỉ
Xây d ng PACB m i. B c 3: ướ ự ớ
ng án 3) C i ti n ph ả ế ươ
c xây d ng theo quy t c sau: ớ ượ ự ắ
PACB m i đ Các ô l trong vòng đi u ch nh đ c c ng vào ẽ ề ỉ ượ ộ
ng hàng đi u ch nh. ề ỉ
l ượ Các ô ch n trong vòng đi u ch nh b tr đi l ng ị ừ ề ẵ ỉ ượ
ỉ
hàng đi u ch nh. ề Các ô còn l i gi nguyên l ng hàng. ạ ữ ượ
: Đánh giá tính t B c 4 ướ ố ư i u c a PACB m i ớ ủ
Đ c th c hi n nh b c 2. ư ướ ượ ự ệ
Chú ý:
a) Khi b sung “ô ch n không” hay ch n ô đ a vào: ư ọ ọ ổ
n u có nhi u ô cùng th a mãn đi u ki n thì ta nên u ư ỏ ề ế ệ ề
phía tây – b c. tiên ch n các ô ọ ở ắ
ng hàng nh nh t trong các ô b) Khi ô đ a ra, n u l ư ế ượ ỏ ấ
ch n c a vòng đi u ch nh là 0 thì ô đó v n đ c ch n ủ ề ẫ ẵ ỉ ượ ọ
làm ô đ a ra. Trong tr ng h p này, PACB v n không ư ườ ợ ẫ
thay đ i nh ng h th ng ô ch n có thay đ i, k t qu ả ệ ố ư ọ ổ ổ ế
đánh giá tính t i u c a PACB có th thay đ i. ố ư ủ ổ ể
Ví d 1: ụ Gi i bài toán v n t i sau: ả ậ ả
20
40
30
30
1
3
5
25
5
4
2
35
8
5
4
Gi i:ả
B ng ph ng pháp c c phí th p nh t ta l p đ c ằ ươ ướ ấ ậ ấ ượ
PACB xu t phát sau: ấ
20
40
30
3 10
5 0
30
1 20
25
5 0
4 0
2 25
35
8 0
5 30
4 5
ng án trên không suy ọ ươ
S ô ch n là 5 = 3 + 2 – 1 nên ph ố bi n.ế
1
3
5 - 3
u1 = 0
20
10
0
5 -4
4 -1
2
u2 = 0
0
0
25
8 -5
4
5
u3 = 2
5
0
30 v1 = 1 v2 = 3 v3 = 2
Ví d 2: Cho bài toán v n t i sau: ậ ả ụ
25 5 7 3
25 3 6 2
10 1 8 2
10 30 20
i bài toán v n t i trên. Tìm PAT khác (n u có) c a ậ ả Ư ủ ế ả
Gi bài toán.
Gi i:ả
B ng 1: L p PACB xu t phát b ng ph ng pháp c c ằ ả ậ ấ ươ ướ
phí th p nh t. S ô ch n là 4 < 3 + 3 – 1 = 5 nên ta b ổ ọ ố ấ ấ
sung vào m t “ô ch n không” là ô (1, 1). Xây d ng h ệ ự ọ ộ
th ng th v và tính các h s c l ệ ố ướ ượ ế ị ố ng ta th y h s ệ ố ấ
ng ô (1, 2) d ng nên PACB xu t phát ch a c l ướ ượ ở ươ ư ấ
t i u. ố ư
25
25
10
10
0
5 - 0
3 1 + 0
1 10
30
2
7 + 25
6 - 5
8 -5 0
20
-2
3 0 0
2 20
2 -3 0
5 4 1
0
3 0
1 10
6
8 -4
7
3
- 25
+ 5
3 0
2
2 -2
-1
+
- 20
Bài toán có l
4 3 1 i u là: i gi
0
10
=
=
oX
225
min
5 20
0 � � 25 � � 0 �
i t ờ ả ố ư
� � 0 , f � � 0 �
Ô lo i (3, 1) trong b ng 2 có h s c l ng 0 nên ệ ố ướ ượ ả ạ
PAT trên không duy nh t. Ư ấ
Xây d ng PACB m i v i ô đ c đ a vào là ô (3, 1) thì ta ớ ớ ự ượ ư
c b ng 3 nh sau: l p đ ậ ượ ư ả
ng án t ố ư
3
i u th Ph ứ 2 c a bài toán đã cho: ươ ủ
0
1 10
0
8 -4
0
10
3
oX =
6 25
7 5
25 0
0 0
0 � � 5 � � 20 �
� � � � �
3 0
2 -2
-1
20
4 3 1
BÀI TOÁN V N T I KHÔNG CÂN B NG THU PHÁT Ằ Ả Ậ
Tr bài toán có t ng phát > t ng thu ườ ng h p 1: ợ ổ ổ
ậ ạ ng hàng b ng hi u ằ ượ ụ ệ
ộ ạ ằ
B c 1: ướ c a t ng phát v i t ng thu. Các ô n m trên c t có tr m ủ ổ thu ph có c ụ l p tr m thu ph có l ớ ổ c phí b ng 0. ằ ướ
gi ng nh ng khi l p ả ư ậ
ng án c b n xu t phát thì u tiên phân ph i ố
i nh bài toán bình th B c 2: ườ ư ướ ph ư ấ ơ ả ươ hàng vào các ô chính tr c.ướ
B c 3: k t lu n bài toán g c. ướ ố ế ậ
Ư ủ Ư ủ ụ ỏ
PAT c a bài toán g c là PAT c a bài toán ph b đi ố c t ng v i tr m ph . ụ ớ ạ ộ ứ
Tr t ng phát < t ng thu ườ ng h p 2: ợ ổ ổ
i nh tr ng h p 1 nh ng l p thêm tr m phát ph Gi ả ư ườ ư
ợ
ạ ậ ụ
100
50
30
70
80
3
5
6
5
70
4
5
7
8
50
3
4
4
3
BÀI TOÁN V N T I CÓ Ô C M Ấ Ả Ậ
B c 1: ướ
Thay c c phí c c phí M ướ ủ ằ ướ
ij c a ô c m b ng c ấ
gi i bài toán m r ng B c 2: ướ ả ở ộ
ng nh ng khi xây d ng ư ườ ư ự
ả ươ ố
i nh bài toán bình th Gi ph ơ ả vào các ô bình th ấ ng tr ng án c b n xu t phát u tiên phân ph i hàng ư c. ướ ườ
k t lu n bài toán g c B c 3: ướ ố ế ậ
ế ở ộ ượ
ng hàng ố ủ ằ ủ ấ
TH1: n u PATU c a bài toán m r ng có l trong các ô c m b ng 0 thì PATU c a bài toán g c trùng v i PATU bài toán m r ng. ở ộ ớ
ng ấ ượ
TH2: N u PATU bài toán m r ng có ô c m có l hàng d ở ộ ng thì bài toán g c không có PATU. ố ế ươ
i sau, trong đó các ô (2,2) và ả ậ ả
50
100
25
25
16
15
10
50
8
9
5
15
100
10
14
11
13
50
10
Gi i bài toán v n t (2,4) là các ô c m.ấ
