7.4. Thu t toán quy không c c phí ậ ướ
gi i bài toán v n t i: ả ậ ả
B c 1: Thành l p m t ph ng án ban ướ ậ ộ ươ
đ u, s ô ch n là ầ ố ọ m+n-1, cũng có th có ô ể
ch n không. ọ
B c 2: Quy không c c phí các ô ch n . ướ ướ ọ
N u các ô lo i có c c phí không âm thì ế ạ ướ
ph ng án đang xét là ph ng án t i u. ươ ươ ố ư
K t thúc thu t toán . Ng c l i có ô lo i ế ậ ượ ạ ạ
có c c phí âm ta qua b c 3.ướ ướ
B c 3: Xây d ng ph ng án m i nh ướ ự ươ ớ ư
đ nh lý 7.ị
B c 4: Quay v b c 2. ướ ề ướ
Sau đây là các ví d và bài t p.ụ ậ
Ví d 1: Gi i bài toán v n t i cho b i ụ ả ậ ả ở
b ng v n t i sau:ả ậ ả
j
i
30 40 50 60
80 1
5 7 2
45 5 7 4
9
55 12 2
3
6
B c 1: Thành l p m t ph ng án ban ướ ậ ộ ươ
đ u.ầ j
i
30 40 50 60
80 1
30
5 7 2
45 5 7 4
9
55 12 2
3
6
V i b ng v n t i nh trên ta th y ô có c c phí th p nh t là ớ ả ậ ả ư ấ ướ ấ ấ
ô (1,1), ô này có c c phí là 1. V y l ng hàng có th phân ướ ậ ượ ể
nhi u nh t vào ô này là 30. L ng hàng này là t n i phát 1 ề ấ ượ ừ ơ
ch đ n n i nh n 1. Ta xóa c t 1 đi. Lúc này n i nh n 1 đã ở ế ơ ậ ộ ơ ậ
đ hàng và n i phát 1 ch còn 50 đ n v hàng.ủ ơ ỉ ơ ị
j
i
30 40 50 60
80 1
30
5 7 2
45 5 7 4
9
55 12 2
3
6
j
i
30 40 50 60
80 1
30
572
50
45 5 7 4
9
55 12 2
3
6