Toán học - Chương 4: Bài toán vận tải

Nội dung text: Toán học - Chương 4: Bài toán vận tải

1. Chương 4 BÀI TOÁN VN TI 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 1
2. NI DUNG 1. Bài toán vn ti dng tng quát 1.1 Phát bi u bài toán vn ti (BTVT) 1.2 Đ t bài toán vn ti dưi dng bng 1.3 Các tính ch t ca bài toán vn ti 2. Thu t toán th v 2.1 Tiêu chu n ti ưu 2.2 Thu t toán 3. Các tr ưng hp đ c bi t ca BTVT 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 2
3. Bài toán vn ti dng tng quát 1. Phát bi u bài toán Có m đim phátS i , vi lưng phát tương ng = ai , i 1, , m ; phát hàng đ n n đim thuT j , vi = lưng thu tương ng bj , j 1, , n . S: a→xij T : b iicij jj vi: c ij là cưc phí vn chuy n 1 đơn v hàng t = = đim phát Si , i 1, , m đ n đim thu Tj , j 1, , n xij là lưng hàng đưc vn chuy n tS i đ n Tj, i=1, , mj ; = 1, , n . 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 3
4. Bài toán vn ti dng tng quát Vn đ :Lp k ho ch vn chuy n nh ư th nào đ tng cưc phí vn chuy n là bé nh t? Bi t rng hàng hóa có th vn chuy n t mt đim phát bt kỳ đ n mt đim thu bt kỳ. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 4
5. Bài toán vn ti dng tng quát Mô hình bài toán có dng : n m = → fX()∑∑ cxij ij min j=1 i = 1  n = = ∑ xij a i , i 1, , m  j =1  m  = = ∑ xij bj j , 1, , n  i =1 x≥0, i = 1, , mj ; = 1, , n  ij  20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 5
6. Bài toán vn ti dng tng quát Điu ki n cân bng thu phát: m n = ∑ai ∑ b j i=1 j = 1 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 6
7. Bài toán vn ti dng tng quát 2. Đ t bài toán dưi dng bng Thu T : b T : b T : b Phát 1 1 j j n n c11 c1j c1n S1 : a 1 x11 x1j x1n ⋮ ci1 cij cin Si : ai x x i1 xij in ⋮ c c c S : a m1 mj mn m m xm1 xmj xmn 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 7
8. Bài toán vn ti dng tng quát Đ nh nghĩa 1 Mt tp hp các ô th a mãn tính ch t: • 2 ô liên ti p cùng nm trên cùng 1 hàng hay 1 ct; • 3 ô liên ti p không cùng nm trên cùng 1 hàng hay 1 ct đưc gi là mt dây chuy n. Mt dây chuy n khép kín đưc gi là mt chu trình . 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 8
9. Bài toán vn ti dng tng quát Đ nh nghĩa 2 > Nh ng ô có x ij 0 đưc gi là ô ch n, nh ng ô còn li đưc gi là ô lo i. Đ nh nghĩa 3 Mt ph ương án (PA) mà các ô ch n không to thành chu trình đgl PA cơ bn (PACB). Mt PACB đ (m + n – 1) ô chn đgl PACB không suy bi n. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 9
10. Bài toán vn ti dng tng quát 3. Các tính ch t ca BTVT i. BTVT cân bng thu phát luôn luôn có PATƯ. ii. Trong 1 PACB bt kỳ, tng s ô ch n luôn nh hơn ho c bng tng s đim phát và thu tr đi 1. (S ô ch n≤(m + n − 1) ). iii. Vi PACB có đ (m+ n − 1) ô ch n, thì vi 1 ô lo i bt kỳ s to thành mt chu trình duy nh t vi mt s ô ch n. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 10
11. Thut toán th v 1. Tiêu chu n ti ưu Xét BTVT cân bng thu phát m n = → fx()∑ ∑ cxij ij min i=1 j = 1  n = = ∑ xij a i , i 1, , m  j =1  m = = ∑ xij bj j , 1, , n  i =1 x≥0, i = 1, , mj ; = 1, , n  ij  20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 11
12. Thut toán th v Bài toán đ i ng u ca bài toán trên: m n = + → guv(,)∑ auii ∑ bv jj max i=1 j = 1 + ≤ = = ui v j c ij ,i 1, m ;j 1, n . 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 12
13. Thut toán th v Đ nh lý 1 = PA X ( x ij ) ca BTVT là PATƯ khi và ch khi tìm = = đưc các s uvii, j , 1, mj ; 1, n th a mãn: + ≤ ∀ uvi j c ij , (,) ij  + = ∀ ∈ ui v j c ij , (,) i j G ( X ), = > GX( ) {(,): ij x ij 0} 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 13
14. Thut toán th v 2. Thu t toán th v - Bưc 1 (Bưc kh i to) 0= 0 Tìm PACB xu tphátX( x ij ) theo nguyên tc phân ph i ti đa: Gi s cn phân ph i cho ô (i,j). Lưng hàng ti đa = có th phân ph i là xijmin{ a i , b j } Sau đó, điu ch nh li các yêu cu: ′ = − ai a i x ij  ′ = − bj b j x ij 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 14
15. Thut toán th v ′ = • Nuai 0 , thìlo i dòng i. ′ = • Nubj 0 , thìlo i ct j. ′= ′ = • Nuai b j 0 , thìlo i c dòng i và ct j. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 15
16. Thut toán th v Ví dụ 1 x 19 bj 30 60 46 25 ai 50 4 7 12 7 51 70 5 9 6 1 19 8 2 9 1 x 41 41 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 16
17. Thut toán th v Ta đưc bng mi thu gn. Lp li hai phép toán trên vi bng mi thu gn đ n khi yêu cu ca đim phát và đim thu đưc th a mãn. > Các ô đưc phân ph icóxij 0, nh ng ô còn li = có xij 0. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 17
18. Thut toán th v Da vào nguyên tc phân ph i ti đa và cách th c ch n ô ưu tiên phân ph i, xét 3 ph ương pháp: i. Ph ương pháp góc Tây Bc: ô đ u tiên đưc ch n đ phân ph i là ô v trí góc Tây Bc (ô (1,1)). ii. Ph ương pháp cc ti u cưc phí : ô đ u tiên đưc ch n đ phân ph i là ô có cưc phí bé nh t. iii. Ph ương pháp Fogel : trên mi hàng, ct ch n ra hai ô có cưc phí bé nh t (bé nhì), ly hi u s ca chúng. Ô có cưc phí bé nh t tương ng hàng, ct có hi u s ln nh t s là ô đ u tiên đưc ch n đ phân ph i. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 18
19. Thut toán th v Nu PACB tìm đưc có đ (m+ n − 1) ô ch n, thì sang Bưc 2. Ng ưc li, thêm vào ô ( i , j ) nào đó mt lưng hàng = xij 0 sao cho: • đ s (m+ n − 1) • và ô ( i , j ) này không to thành chu trình vi các ô ch n. → Bưc 2. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 19
20. Thut toán th v - Bưc 2 (Bưc lp) đ u bưc lp đã có PACB đ (m+ n − 1) ô ch n. = = i. Xác đ nh các th v ui, v j , i 1, m ; j 1, n + = ∀ ∈ ui v j c ij ,(,) i j G ( X ) Ch n u1 = 0 . ii. Tính các ưc lưng theo công th c: ∆ = + − ∀ iju i v j c ij , (, ij ) 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 20
21. Thut toán th v iii. Ki m tra tiêu chu n ti ưu ∆ ≤ ∀ Nuij 0, (i , j ) thì PA đang xét là PATƯ. Ng ưc li, chuy n sang iv. iv. Ch n ô ( i * , j * ) là ô có ưc lưng dương ln nh t: ∆ =max{ ∆ : ∆ > 0} i* j * ij ij Khi đó, ô ( i * , j * ) s to nên mt chu trình duy nh t vi mt s ô ch n. → Ô ( i * , j * ) s là ô ch n bng mi. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 21
22. Thut toán th v Đ t tên chu trình là K. Đánh du +, - xen k vào các ô thu c K, bt đ u t ô ( i * , j * ) mang du +. Đ t : K + = { nh ng ô mang du +} − K = { nh ng ô mang du -} 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 22
23. Thut toán th v = Ti n hành điu ch nh PA X ( x ij ), ta có PA mi X= ( x ij ), vi x(,) i j∉ K ,  ij = +θ ∈ + xij x ij (,) i j K ,  −θ ∈ − xij (,) i j K , θ =x =min{ x :(,) i j ∈ K − } trong đó, i0 j 0 ij → Ô ( i 0 , j 0 ) là ô lo i bng mi. Thay X biX và lp li Bưc lp. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 23
24. Thut toán th v b j 30 60 46 25 ai 4 7 12 7 u = 0 50 1 30 20-8 -1 5 9 6 1 + 70 - u = 2 1 24 46 7 2 8 2 9 1 - 41 u = -5 -9 + 16 -10 25 3 v = 4 v = 7 v = 4 v = 6 θ = 24 1 2 3 4 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 24
25. Thut toán th v Ví dụ 2 (tt ) b j 30 60 46 25 ai 4 7 12 7 u = 0 50 1 30 20-1 -1 5 9 6 1 70 u = -5 -6 -7 46 24 2 8 2 9 1 41 u = -5 -9 40 -3 1 3 v1= 4 v2= 7 v3= 11 v4= 6 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 25
26. Thut toán th v ∆ ≤ ∀ Vìij 0, (i , j ) nên 30 20 0 0  * =   PATƯ X 0 0 46 24    0 40 0 1  Giá tr ti ưu: f( X * )=× 4 30 +× 7 20 +× 6 46 + 24 +× 2 40 + 1 = 641. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 26
27. Các tr ưng hp đc bi t ca BTVT i. BTVT không cân bng thu phát a. Phát > Thu: m n > ∑ai ∑ b j i=1 j = 1 → Đưa v BTVT cân bng thu phát → Thêm mt đim thu gi , lưng hàng tương ng m n = − = ∀ = bn+1 ∑ a i ∑ b j ; ci( n + 1) 0, i 1, m. i=1 j = 1 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 27
28. Các tr ưng hp đc bi t ca BTVT b. Phát < Thu m n < ∑ai ∑ b j i=1 j = 1 → Đưa v BTVT cân bng thu phát → Thêm mt đim phát gi , lưng hàng tương ng n m = − = ∀ = am+1 ∑ b j ∑ a i ; c(m+ 1) j 0, j 1, n. j=1 i = 1 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 28
29. Các tr ưng hp đc bi t ca BTVT ii. BTVT có ô cm Ô cm: ô không đưc nh n hàng. Gi s ô ( i , j ) là ô cm. → = Thay cij M, vi M là s dương rt ln. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 29
30. Các tr ưng hp đc bi t ca BTVT iii. “BTVT” vi hàm mc tiêu cc đ i Có mô hình gi ng BTVT, nh ưng hàm mc tiêu cc đ i. ∆ ≥ ∀ • Du hi u ti ưu: ij 0, (i , j ) • Ch n ô (i* , j * ) ∆ =min{ ∆ : ∆ < 0} i* j * ij ij = − • Nu có ô cm(i , j ) , thaycij M , viM là s dương rt ln. • Ch n ô có cij ln nh t phân ph i tr ưc. 20/6/2012 MaMH: C01019 Ch ươ ng 4: Bài toán v n t i 30