Tiểu luận: Thuật toán nhánh cận

Chia sẻ: Văn Hiệp | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

314
lượt xem 63
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Ta sẽ thực hiện việc đánh giá theo từng bước, nếu không có khả năng tìm thấy kết quả tốt hơn thì sẽ cắt nhánh đó, không thực hiện tìm tiếp mà chuyển ngay sang nhánh khác. Khi đó, chỉ ghi nhận các kết quả tốt hơn lúc ban đầu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tiểu luận: Thuật toán nhánh cận

TRƯ NG Đ I H C BÁCH KHOA HÀ N I VI N TOÁN NG D NG VÀ TIN H C ------------------------- THU T TOÁN NHÁNH C N T I ƯU T H PI Chuyên ngành : TOÁN TIN NG D NG Th y hư ng d n: TS. Nguy n Quang Thu n Sinh viên th c hi n: Vũ H u Ninh L p: Toán Tin 2 - K54 HÀ N I - 2012
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh M cl c 1 L i nói đ u 3 2 M t s khái ni m cơ b n và ki n th c b tr 4 2.1 Phân ho ch . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Bài toán con . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 C n dư i - c n trên . . . . . . . . . . . . . . . . . . . . . 4 2.4 Thu t toán đơn hình gi i bài toán quy ho ch tuy n tính 5 2.5 Bài toán quy ho ch nguyên . . . . . . . . . . . . . . . . 6 3 Thu t toán nhánh c n 7 3.1 Ý tư ng c a thu t toán nhánh c n . . . . . . . . . . . . 7 3.2 Thu t toán nhánh c n Land-Doig gi i bài toán quy ho ch nguyên hoàn toàn . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Thu t toán nhánh c n gi i bài toán cái túi . . . . . . . . 14 4 K t lu n 17 5 Tài li u tham kh o 18 2
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 1 L i nói đ u Quy ho ch nguyên là mô hình toán h c c a r t nhi u bài toán n y sinh trong các lĩnh v c khác nhau. Tuy nhiên, khác v i baiftoans quy ho ch tuy n tính thông thư ng, bài toán quy ho ch nguyên r t khó gi i. Th c t chưa có m t thu t toán t i ưu nào th c s h u hi u đ gi i t t c các bài toán quy ho ch nguyên. Năm 1960, Land và Doig đưa ra thu t toán nhánh c n d gi i bài toán quy ho ch nguyên. Đ n năm 1965, Dakin đã hoàn thi n phương pháp nhánh c n và nó tr thành phương pháp ưu thê rõ r t so v i các phương pháp trư c đ gi i bài toán quy ho ch nguyên. N i dung chính trong báo cáo này c a em ch y u là nói v thu t toán nhánh c n đ gi i bài toán quy ho ch nguyên. 3
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 2 M t s khái ni m cơ b n và ki n th c b tr 2.1 Phân ho ch M t h P ch a h u h n các t p con c a t p D, P := {Di ⊆ D | i ∈ I}, trong đó I là t p h u h n các ch s , đư c g i là m t phân ho ch c a D n u D= Di và Di ∩ Dj = ∅ i = j. i∈I Nói r ng ta phân ho ch t p D b i các t p con Di , i ∈ I có nghĩa là ta có {Di ⊆ D | i ∈ I} là m t phân ho ch c a D. 2.2 Bài toán con Xét bài toán quy ho ch nguyên sau: maxf (x) v.đ.k. x∈D (IP ) trong đó D là t p ch p nh n đư c. Bài toán maxf (x) v.đ.k. x ∈ Di (IPi ) đư c g i là bài toán con c a bài toán quy ho ch nguyên (IP ) (cùng hàm m c tiêu nhưng t p ch p nh n đư c bé hơn ). 2.3 C n dư i - c n trên • S th c α đư c g i là c n dư i c a bài toán (IP ) n u α ≤ fopt . N u tìm đư c phương án ch p nh n đư c x ∈ D thì f (x) ≤ fopt . Khi đó x đư c g i là k l c và f (x) đư c g i là m t giá tr k l c. • S th c β đư c g i là c n dư i c a bài toán (IP ) n u β ≥ fopt . N u tìm đư c phương án ch p nh n đư c x ∈ D và m t c n trên β c a bài toán (IP ) sao cho f (x) = β thì x chính là nghi m t i ưu c a bài toán. 4
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 2.4 Thu t toán đơn hình gi i bài toán quy ho ch tuy n tính Xét bài toán quy ho ch tuy n tính chính t c không suy bi n f (x) = cT x → min (LP ) v.đ.k. x ∈ D, n trong đó c ∈ R , và t p ch p nh n đư c là t p l i đa di n không suy bi n xác đ nh b i D = {x ∈ Rn |Ax = b, x ≥ 0}, trong đó b = (b1 , b2 , · · · , bm )T ≥ 0, A là ma tr n c p m × n, v i m < n. Gi s ta đã bi t phương án c c biên x0 = (x0 , x0 , · · · , x0 )T . Ký hi u 1 2 n J(x0 ) := {j ∈ {1, 2, · · · , n}|x0 > 0}. j H các véc tơ đ c l p tuy n tính {Aj |j ∈ J(x0 )} là cơ s duy nh t c a ma tr n A tương ng v i x0 . Vì v y m i véc tơ Ak đư c bi u di n dư i d ng Ak = zjk Aj j∈J(x0 ) và b s th c zjk , j ∈ J(z 0 ) là đư c xác duy nh t.Ta g i ∆k = zjk cj − ck k ∈ {1, 2, · · · , n} j∈J(x0 ) là ư c lư ng ng v i phương án xk . Thu t toán Bư c 1:( Bư c chu n b ) Xây d ng b ng đơn hình xu t phát tương ng v i phương án c c biên xu t phát x0 . Bư c 2: (Ki m tra đi u ki n t i ưu) Xét dòng cu i c a b ng đơn hình If ∆k ≤ 0 v i m i k = 1, 2, · · · , n Then D ng thu t toán , k t lu n nghi m t i ưu là phương án c c biên ng v i b ng này. Else chuy n sang Bư c 3. Bư c 3: (Ki m tra bài toán không có l i gi i) If T i t i k ∈ JB sao cho ∆k > 0 và zjk ≤ 0 v i m i j ∈ JB Then D ng / thu t toán, k t lu n bài toán không có l i gi i 5
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Else chuy n sang Bư c 4. Bư c 4: • Tìm c t xoay. Tìm ch s s th a mãn ∆s = max{∆k |∆k > 0}. Khi đó c t tương ng v i véc tơ As s đưa vào cơ s m i. • Tìm dòng xoay. Tính các θj , j ∈ JB , như sau zj zjs n u zjs > 0, j ∈ JB θj = +∞ n u zjs ≤ 0, j ∈ JB và xác đ nh ch s r th a mãn θr = min{θj |j ∈ JB } khi đó dòng r g i là dòng xoay. Ph n t zjs n m trên dòng xoay và c t xoay đư c g i là ph n t chính c a phép quay. Các ph n t zjs , (j = r) đư c g i là các ph n t xoay. Bư c 5: (Chuy n b ng đơn hình tương ng v i phương án c c biên m i) • Trong c t h s CB thay giá tr cr b i cs . Trong c t h s cơ s thay tên Ar b i As . • Dòng xoay m i đư c tính theo quy t c là Dòng quay (cũ) Dòng chính (m i) := ; ph n t chính • Các dòng còn l i đư c tính như sau Dòng m i := (- Ph n t quay tương ng) × Dòng chính + Dòng cũ. • Quay l i Bư c 2. 2.5 Bài toán quy ho ch nguyên Xét bài toán quy ho ch nguyên đư c phát bi u như sau min f (x) = f (x1 , · · · , xn ) v.đ.k x = (x1 , · · · , xn ) ∈ D, (P 1) trong đó D ∈ Rn là t p các véc tơ x = (x1 , · · · , xn )T mà m t s ho c t t c các thành ph n c a x ch nh n giá tr nguyên. i) N u mà t t c các thành ph n c a bi n x nh n giá tr nguyên thì ngư i ta g i là bài toán (P 1) là bài toán quy ho ch nguyên hoàn toàn. 6
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh ii) N u ch có m t s thành ph n c a bi n x nh n giá tr nguyên thì ngư i ta g i bài toán (P 1) là bài toán quy ho ch nguyên b phân. Ví d 1. Xét bài toán quy ho ch tuy n tính nguyên sau −9x1 − 5x2 − 6x3 − 4x4 → min v.đ.k. 6x1 +3x2 +5x3 +3x4 ≤ 9 x3 +x4 ≤1 −x1 +x3 ≤0 −x2 +x4 ≤0 x1 , x2 , x3 x4 nguyên 3 Thu t toán nhánh c n 3.1 Ý tư ng c a thu t toán nhánh c n Ý tư ng c a phương pháp nhánh c n là "chia đ tr ", t c thay vì gi i tr c ti p bài toán quy ho ch tuy n tính (IP ) ta gi i bài toán con max f (x) v.đ.k. x ∈ Di , (IPi ) trong đó Di thu c m t phân ho ch P := {Di ⊆ D | i ∈ I}. Hi n nhiên là vi c gi i các bài toán con (IPi ), i ∈ D, cũng s m c ph i nh ng khó khăn tương t như vi c gi i bài toán quy ho ch nguyên (IP ). Tuy nhiên ta có th xác đ nh đư c c n trên β(D)i c a bài toán con này, nh đó ta có th xác đ nh đư c c n trên c a bài toán ban đ u. Đ c đi m c a thu t toán nhanh c n là xu t phát t t p ch p nh n đư c ban đ u D, qua các vòng l p, b ng cách phân ho ch d n t p D và xác đ nh các c n trên c a bài toán con ta s lo i d n đư c nh ng t p con Dk ⊂ D mà ta bi t ch c ch n nghi m t i ưu c a bài toán ban đ u (IP ) không th thu c Dk ho c ta đã bi t m t phương án t t nh t trong Dk r i. Đ n khi "ki m duy t" đư c h t các t p con c n xét thì thu t toán k t thúc và ta nh n đư c nghi m c a bài toán t i ưu ban đ u. 7
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 3.2 Thu t toán nhánh c n Land-Doig gi i bài toán quy ho ch nguyên hoàn toàn Xét bài toán quy ho ch nguyên tuy n tính max f (x) = c, v.đ.k. x ∈ D0 , (IP0 ) trong đó D0 ⊂ Rn xác đ nh b i D0 = {x ∈ Rn | Ax ≤ b, x ≥ 0, và nguyên}, Ký hi u D0 := {x ∈ Rn |Ax ≤ b, x ≥ 0} nl là t p l i đa di n có ràng bu c như t p D0 nhưng b đi tính nguyên c a x. Thu t toán Bư c chu n b • Gi i bài toán n i l ng max {f (x) | x ∈ D0 } đư c nghi m t i ưu x0 . nl • If x0 nguyên Then D ng thu t toán. Else Đ t β(D0 ) := f (x0 ); • If Bi t m t phương án x ∈ D Then Đ t α := f (x) Else Đ t α := −∞; • Đ t D := {D0 }; Bư c 1: (Ch n t p đ chia) • Ch n Dk ⊂ D là t p ch p nh n đư c c a bai toán quy ho ch nguyên (IPk ) mà bài toán có c n trên β(Dk ) l n nh t trong các bài toán con có t p ch p nh n đư c thu c D. G i xk là phương án t i ưu c a bài toán n i l ng tương ng v i bài toán (IPk ). • Gi s xk là m t thành ph n không nguyên đ u tiên c a xk . Phân j ho ch t p Dk thành hai t p Dk1 = {x ∈ Dk |xj ≤ xk } j Dk2 = {x ∈ Dk |xj ≥ xk } j 8
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh • Đ t D := (D \ {Dk } ∪ {Dk1 , Dk2 }) Bư c 2: (L p các t p con) • V i m i i ∈ {1, 2}, gi i bài toán quy ho ch tuy n tính n i l ng (LPki ). Có th g p m t trong các trư ng h p sau: – Bài toán không ch p nh n đư c , t c là Dki = ∅. D := D \ {Dk }. – Tìm đư c phương án t i ưu xk nguyên. Khi đó tính l i giá tr k l c α = max {α, f(xki )} G i x là k l c hi n t i tương ng v i giá tr k l c hi n t i α = f (x). Lo i Dki kh i vi c xem xét ti p theo. D := D\{Dk } – Tìm đư c phương án t i ưu xki là không nguyên. Đ t β(Dki ) = f (xki ). • Lo i b kh i D t t c cac t p ch p nh n đư c c a bài toán con có c n trên bé hơn ho c b ng k l c hi n t i α (n u có). Bư c 3: (Ki m tra đi u ki n d ng) If D = ∅ Then D ng thu t toán Else Quay l i bư c 1. Ví d Gi i bài toán quy ho ch tuy n tính nguyên sau: max − x1 + 4x2 v.đ.k.   −10x1 +20x2  ≤ 22 5x1 +10x2 ≤ 49   x1  ≤5 x1 , x2 , ≥ 0, nguyên  9
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Hình 1: Hình 1 Gi i bài toán n i l ng c a bài toán trên max − x1 + 4x2 v.đ.k.   −10x1 +20x2  ≤ 22 5x1 +10x2 ≤ 49   x1  ≤5 x1 , x2 , ≥0  ta đư c nghi m là (3.8, 3) và giá tr t i ưu β = 8.2. Khi đó ta thêm hai ràng bu c là x1 ≥ 4 và x1 ≤ 3, ta đư c mi n ch p nh n đư c như Hình 2. 10
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Hình 2: Ti p t c gi i bài toán n i l ng max − x1 + 4x2 v.đ.k. x ∈ D1 Ta đư c nghi m t i ưu là (4, 2.9) và giá tr t i ưu là β = 7.6. Hình 3: Ta l i ti p t c chia mi n D1 thành hai mi n khi thêm hai ràng bu c x2 ≤ 2 và x2 ≥ 3. Ta th y trên mi n D4 không có nghi m nguyên, nên ta lo i mi n này. Còn trên mi n D3 ta đư c nghi m là (4, 2) và giá tr t i ưu f = 4 (xem Hình 4). 11
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Hình 4: Ti p theo ta xét trên mi n D2 . Gi i bài toán trên mi n D2 ta đư c nghi m là (3, 2.6) và giá tr t i ưu là 7.6. Hình 5: Vì nghi m chưa nguyên nên ta chia mi n D2 b i lát c t x2 ≤ 2 và x2 ≥ 3. Trên mi n D6 không có nghi m nguyên nên ta lo i, còn mi n D5 có nghi m là (1.8, 2) và giá tr t i ưu là 6.2 (Hình 5). Ta l i chia mi n D5 thành 2 mi n b i lát c t x1 ≤ 1 và x1 ≥ 2. (Hình 6) 12
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Hình 6: Trên mi n D8 ta có nghi m là (2, 2) và giá tr t i ưu là 6 >4 (Hình 7). Còn trên mi n D7 ta gi i đư c nghi m là (1, 1.6) và giá tr t i ưu là 5.4 < 6 (Hình 8), trư ng h p này ta lo i. Hình 7: 13
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Hình 8: 3.3 Thu t toán nhánh c n gi i bài toán cái túi Xét bài toán ba lô 0 -1 n f (x) = cj xj → max (P ) j=1 n n v.đ.k. x ∈ D = {x ∈ R | aj xj ≤ b, xj ∈ {0, 1}j = 1, 2, · · · , n}, j=1 trong đó cj , aj , j = 1, · · · , n và b là các s th c cho trư c. Gi s r ng c1 cn ≥ ··· ≥ . a1 an Đ xây d ng hàm tính c n dư i, ta xét n n ∗ g = max{f (x) = cj xj : aj xj ≤ b, j = 1, · · · , n} (1) j=1 j=1 M nh đ 3.1. Phương án t i ưu c a bài toán (1) là véc tơ x = (x1 , · · · , xn ) v i các thành ph n đư c xác đ nh b i công th c b x1 = , x2 = · · · = xn = 0 a b và giá tr t i ưu là g ∗ = c1 a1 . 1 14
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Gi s ta có phương án b ph n c p k: (u1 , · · · , un ). Khi đó giá tr s d ng các đ v t đang có trong túi là σk = c1 u1 + · · · ck uk và tr ng lư ng còn l i c a túi là bk = b − (a1 u1 + · · · + ak uk ) Ta có max {f (x) : x ∈ D, xj = uj , j = 1, · · · , n} n n =max {σk + cj xj : aj xj ≤ b, xj ∈ Z+ , j = k + 1, · · · , n} j=1 j=1 n n ≤ σk + { cj xj : aj xj ≤ b, xj ∈ Z+ , j = k + 1, · · · , n} j=1 j=1 bk = σk + ck+1 ak+1 V y ta có th tính c n trên cho phương án b ph n (u1 , · · · , uk ) b i công th c sau: bk g(u1 , · · · , uk ) = σk + ck+1 . ak+1 Ví d : G i bài toán cái túi sau theo thu t toán nhánh c n f (x) = 10x1 + 5x2 + 3x3 + 6x4 → max 5x1 + 3x2 + 2x3 + 4x4 ≤ 8 xj ∈ Z+ , j = 1, 2, 3, 4 Thu t toán nhánh c n đư c trình bày Hình 9. Trong đó σ là giá tr các đ v t đang ch t trong túi, w là tr ng lư ng còn l i c a túi và g là c n trên. 15
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh Hình 9: σ 16
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 4 K t lu n Đ k t thúc, em xin tóm t t l i nh ng v n đ đư c trình bày trong báo cáo c a em. Trong báo cáo em đã nh c l i môt s khái ni m cơ b n và thu t toán đơn hình gi i bài toán quy ho ch tuy n tính, và n i dung chính c a báo cáo là thu t toán nhánh c n đ gi i bài toán quy ho ch nguyên. Do th i gian có h n nên trong báo cáo v n còn m t s thi u sót, r t mong đư c s đóng góp ý ki n c a th y và b n đ c. 17
T i ưu t h p I - Thu t toán nhánh c n Vũ H u Ninh 5 Tài li u tham kh o [1] Nguy n Th B ch Kim, Giáo trình Các Phương Pháp T i Ưu Lý Thuy t Và Thu t Toán, Nhà xu t b n đ i h c bách khoa, Hà n i, 2006. [2] Stephen Boyd and Jacob Mattingley,Branch and Bound Methods, Stanford University, Winter 2006-07 March 11, 2007. [3] Jens Clausen, Branch and Bound Algorithms - Principles and Ex- amples, March 12, 1999. [4] Nguy n Đ c Nghĩa - Nguy n Tô Thành, Toán r i r c, Nhà xu t b n đ i h c Qu c Gia Hà N i, 2006. 18