11/5/2011<br />
<br />
ÑAÏI HOÏC TAØI CHÍNH – MARKETING<br />
BOÄ MOÂN TOAÙN – KHOA CÔ BAÛN<br />
<br />
Baøi giaûng<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
ThS.<br />
ThS. Nguyeãn Vaên Phong<br />
Email : nvphong1980@gmail.com, nv.phong@ufm.edu.com<br />
<br />
Chương<br />
Chương 4. BAØI TOAÙN VAÄN TAÛI<br />
1. PHAÙT BIEÅU BAØI TOAÙN.<br />
2. BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG<br />
3. MOÄT SOÁ KHAÙI NIEÄM<br />
4. MOÄT SOÁ TÍNH CHAÁT<br />
5. PHÖÔNG PHAÙP TÌM PHÖÔNG AÙN XUAÁT PHAÙT<br />
6. THUAÄT TOAÙN THEÁ VÒ<br />
<br />
2<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
PHAÙT BIEÅU BAØI TOAÙN<br />
PHAÙT BIEÅU BAØI TOAÙN.<br />
m : ÑIEÅM PHAÙT n : ÑIEÅM THU<br />
B1<br />
a1<br />
<br />
LAÄP BAØI TOAÙN<br />
cij : cöôùc phí töø Ai ñeán B j<br />
x ij : löôïng haøng töø Ai ñeán B j<br />
<br />
b1<br />
<br />
A1<br />
<br />
m<br />
<br />
B2<br />
<br />
b2<br />
<br />
I)<br />
a2<br />
<br />
A2<br />
<br />
B3<br />
<br />
b3<br />
<br />
m<br />
<br />
II )<br />
<br />
i =1 j =1<br />
<br />
n<br />
∑ x i j<br />
j =1<br />
m<br />
x<br />
∑ i j<br />
i =1<br />
<br />
= ai<br />
<br />
, i = 1, m,<br />
<br />
= bj<br />
<br />
, j = 1,n,<br />
<br />
n<br />
<br />
∑ a = ∑b<br />
i =1<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
n<br />
<br />
Muïc tieâu: f = ∑∑ cij x ij → min<br />
<br />
i<br />
<br />
III ) x ij ≥ 0<br />
<br />
j =1<br />
<br />
j<br />
<br />
3<br />
NGUYEÃN VAÊN PHONG<br />
<br />
1<br />
<br />
11/5/2011<br />
<br />
BAØI TOAÙN VAÄN TAÛI DAÏNG BAÛNG<br />
Bj<br />
<br />
⋅⋅⋅<br />
<br />
b1<br />
<br />
Ai<br />
<br />
⋅⋅⋅<br />
<br />
bj<br />
<br />
bn<br />
<br />
c11<br />
<br />
a1<br />
<br />
x 11<br />
<br />
⋅⋅⋅<br />
Moät oâ (i, j )<br />
<br />
cij<br />
<br />
ai<br />
<br />
x ij<br />
<br />
⋅⋅⋅<br />
cmn<br />
<br />
am<br />
<br />
x mn<br />
4<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
MOÄT SOÁ KHAÙI NIEÄM<br />
T = {(i, j ) i = 1, 2,..., m; j = 1, 2,..., n}<br />
<br />
Taäp caùc oâ<br />
<br />
{<br />
<br />
}<br />
<br />
Taäp caùc oâ choïn<br />
<br />
G (x ) = (i, j ) x ij > 0<br />
<br />
Caùc oâ loaïi<br />
<br />
(i, j ) ∉G (x )<br />
<br />
|G(x)| laø soá phaàn töû cuûa G(x)<br />
Phöông aùn cöïc bieân : laø phöông aùn coù khoâng quaù m + n -1<br />
oâ choïn<br />
Phöông aùn cöïc bieân khoâng suy bieán : laø phöông aùn coù ñuùng<br />
m+nm+n-1 oâ choïn<br />
trình:<br />
i,j)<br />
Chu trình: Taäp caùc oâ (i,j) ñöôïc goïi laø moät chu trình neáu<br />
i) Hai oâ caïnh nhau phaûi naèm treân cuøng haøng hay moät coät,<br />
ii)<br />
ii) Khoâng coù 3 oâ naèm treân cuøng moät haøng hay moät coät,<br />
iii)<br />
nhau.<br />
iii) OÂ ñaàu tieân vaø oâ cuoái cuøng truøng nhau.<br />
5<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
MOÄT SOÁ KHAÙI NIEÄM<br />
Ví duï<br />
<br />
Bj<br />
Ai<br />
<br />
b1<br />
<br />
⋅⋅⋅<br />
<br />
bj<br />
<br />
⋅⋅⋅<br />
<br />
bn<br />
<br />
a1<br />
⋅⋅⋅<br />
<br />
ai<br />
⋅⋅⋅<br />
<br />
am<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
6<br />
NGUYEÃN VAÊN PHONG<br />
<br />
2<br />
<br />
11/5/2011<br />
<br />
MOÄT SOÁ TÍNH CHAÁT<br />
1. Phöông aùn x laø phöông aùn cöïc bieân neáu G(x) khoâng<br />
chöùa chu trình<br />
2. Moïi taäp G coùù |G(x)|=m+n ñeàu chöùa chu trình.<br />
co<br />
)|=m<br />
trình.<br />
3. Cho P laø taäp goàm m+n -1 oâ khoâng chöùa chu trình vaø<br />
(i0, j0) khoâng thuoäc veà P. Khi ñoù P ∪ (i0 , j 0 ) seõ chöùa moät<br />
chu trình duy nhaát<br />
<br />
7<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
TÌM PHÖÔNG AÙN XUAÁT PHAÙT<br />
1. Phöông phaùp Goùc taây baéc<br />
- Ñi töø oâ (1,1) ñeán oâ (m,n) theo höôùng töø treân xuoáng döôùi<br />
töø traùi sang phaûi.<br />
- Phaân phoái toái ña haøng vaøo oâ (i,j).<br />
ai neáu a i ≤ bj<br />
<br />
x ij = min {ai ,bj } = <br />
bj neáu a i ≤ bj<br />
<br />
<br />
2. Phöông phaùp Cmin<br />
- Duyeät taát caû caùc oâ töø (1,1) ñeán oâ (m,n)<br />
- Phaân phoái toái ña haøng vaøo oâ (i,j) coù cmin.<br />
<br />
8<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUAÄT TOAÙN THEÁ VÒ<br />
1. Ñieàu kieän toái öu:<br />
öu:<br />
- Ñieàu kieän caàn vaø ñuû ñeå moät phöông aùn X laø phöông aùn toái<br />
öu,<br />
öu, neáu toàn taïi caùc theá vò<br />
ui , v j , i = 1, 2,.., m; j = 1, 2,..., n<br />
<br />
thoaû maõn<br />
ui + v j = cij ; neáu (i, j ) ∈G (X )<br />
<br />
<br />
ui + v j ≤ cij ; neáu (i, j ) ∉G (X )<br />
<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
9<br />
NGUYEÃN VAÊN PHONG<br />
<br />
3<br />
<br />
11/5/2011<br />
<br />
THUAÄT TOAÙN THEÁ VÒ<br />
2. Thuaät toaùn<br />
0<br />
Böôùc 1: Tìm phöông aùn suaát phaùt X 0 = (x ij ) (Goùc taây baéc, Cmin)<br />
ui , v j , i = 1, 2,.., m; j = 1, 2,..., n<br />
Böôùc 2: Tìm caùc theá vò<br />
ui + v j = cij ; neáu (i, j ) ∈G (X 0 )<br />
thoaû maõn<br />
∆ ij = ui + v j − cij ; taïi (i, j ) ∉G (X 0 )<br />
Böôùc 3: Tính ñoä cheânh leäch<br />
Böôùc 4: Kieåm tra tính toái öu<br />
- Neáu ∀ (i, j ) ∉G (X 0 ): ∆ij ≤ 0 Thì X laø PATÖ<br />
- Neáu ∃(i, j ) ∉G (X 0 ): ∆ ij > 0 Chuyeån qua böôùc 5<br />
Böôùc 5: Ñieàu chænh phöông aùn<br />
- Xaùc ñònh oâ hieäu chænh (is , js ) ∆is js = max{∆ij > 0 |(i, j ) ∉G (X 0 )}<br />
- Tìm moät chu trình ñieàu chænh duy nhaát K trong G (X 0 ) ∪ (is , js )<br />
+<br />
(- Ñaùnh daáu (+), (-) xen keû vaøo caùc oâ trong K vôùi (is , js ) ∈ K<br />
- Xaùc ñònh löôïng hieäu chænh θ = x i0 , j = min{x i0, j |(i, j ) ∈ K − }<br />
r r<br />
10<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUAÄT TOAÙN THEÁ VÒ<br />
1<br />
- Xaây döïng phöông aùn môùi X1 = (x ij ) vôùi<br />
0<br />
x ij + θ<br />
0<br />
<br />
x = x ij − θ<br />
0<br />
x ij<br />
<br />
1<br />
ij<br />
<br />
Trong ñoù<br />
<br />
neáu (i, j ) ∈ K +<br />
neáu (i, j ) ∈ K −<br />
neáu (i, j ) ∉ K<br />
<br />
K + = {Caùc oâ trong K ñöôïc ñaùnh daáu +}<br />
K − = {Caùc oâ trong K ñöôïc ñaùnh daáu -}<br />
<br />
Khi ñoù,<br />
- Ta coù moät phöông aùn xuaát phaùt môùi. (Quay laïi böôùc 1)<br />
- Vôùi giaù trò cuûa haøm muïc tieâu môùi ñöôïc xaùc ñònh<br />
f (X1) = f (X 0 ) − θ × ∆is js<br />
11<br />
NGUYEÃN VAÊN PHONG<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
THUAÄT TOAÙN THEÁ VÒ<br />
Ví duï.<br />
Bj<br />
<br />
60<br />
<br />
Ai<br />
<br />
50<br />
70<br />
80<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
30<br />
<br />
40<br />
<br />
70<br />
<br />
2<br />
<br />
4<br />
<br />
5<br />
<br />
1<br />
<br />
3<br />
<br />
6<br />
<br />
4<br />
<br />
8<br />
<br />
1<br />
<br />
2<br />
<br />
5<br />
<br />
3<br />
<br />
12<br />
NGUYEÃN VAÊN PHONG<br />
<br />
4<br />
<br />
11/5/2011<br />
<br />
CAÙC TRÖÔØNG HÔÏP SUY BIEÁN<br />
i) Khoâng caân baèng thu phaùt<br />
m<br />
<br />
n<br />
<br />
∑ a > ∑b<br />
i =1<br />
<br />
i<br />
<br />
j =1<br />
<br />
j<br />
<br />
hay<br />
<br />
m<br />
<br />
n<br />
<br />
∑ a < ∑b<br />
i =1<br />
<br />
i<br />
<br />
j =1<br />
<br />
j<br />
<br />
ii) Phöông aùn xuaát phaùt X0 suy bieán<br />
|G (X 0 )|< m + n − 1<br />
iii) Baøi toaùn coù oâ caám: Khi ta khoâng theå chuyeån haøng töø ai ñeán<br />
bj (trong moät soá ñieàu kieän naøo ñoù) thì oâ (i,j ) laø oâ caám<br />
<br />
QUY HOAÏCH TUYEÁN TÍNH<br />
<br />
13<br />
NGUYEÃN VAÊN PHONG<br />
<br />
5<br />
<br />
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
