TRẦN NGỌC THĂNG BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - TRẦN NGỌC THĂNG PHƯƠNG PHÁP XẤP XỈ NGOÀI VỚI KỸ THUẬT RẼ NHÁNH GIẢI BÀI TOÁN TỐI ƯU TOÀN CỤC TOÁN TIN LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: TOÁN TIN 2010B HÀ NỘI – 2011 Mục lục Lời cảm ơn iii Lời mở đầu iv Danh mục kí hiệu, chữ viết tắt Danh mục hình vẽ vii ix Bài toán quy hoạch lồi với ràng buộc tích Bài toán tối ưu tập Pareto 1.1 Hàm lõm, hàm tựa lõm hàm đơn điệu 1.2 Bài toán quy hoạch lồi với ràng buộc tích 1.2.1 Mô hình toán học 1.2.2 Dạng toán tương đương 1.3 Bài toán tối ưu tập Pareto 19 1.3.1 Giới thiệu toán 19 1.3.2 Bài toán tương đương với (OPY ) 23 Thuật toán giải toán quy hoạch lồi với ràng buộc tích 24 2.1 Cơ sở lý thuyết thuật toán 26 2.2 Thuật toán 37 2.3 Ví dụ minh họa 44 i Thuật toán giải toán tối ưu tập Pareto 51 3.1 Cơ sở lý thuyết thuật toán 53 3.2 Thuật toán giải Bài toán (OPG ) 63 3.3 Ví dụ minh họa 66 Kết luận chung 72 Tài liệu tham khảo 73 ii Lời cảm ơn Lời đầu tiên, tác giả xin bày tỏ lòng biết ơn chân thành sâu sắc tới PGS.TS Nguyễn Thị Bạch Kim, người tận tình nghiêm khắc hướng dẫn để luận văn hoàn thành Tác giả chân thành cảm ơn Khoa Toán Tin ứng dụng, Viện Đào tạo Sau Đại học, trường Đại học Bách khoa Hà Nội, tạo điều kiện thuận lợi cho tác giả trình học tập nghiên cứu Cảm ơn thầy cô đồng nghiệp trao đổi tác giả kiến thức kinh nghiệm quý báu để giúp cho luận văn hoàn thiện Bên cạnh đó, quan tâm gia đình, bạn bè nguồn động viên thiếu để giúp tác giả hoàn thành luận văn Xin chân thành cảm ơn Học viên: Trần Ngọc Thăng Lớp iii : 10BTT-KH Lời mở đầu Mục đích luận văn nghiên cứu Bài toán quy hoạch lồi với ràng buộc tích Bài toán tối ưu tập Pareto Đây hai toán tối ưu toàn cục có nhiều ứng dụng để giải toán nảy sinh từ thực tế Do nhu cầu ứng dụng, hai toán thu hút quan tâm đặc biệt nhiều tác giả nước Và vậy, việc nghiên cứu xây dựng thuật toán hiệu để giải toán vấn đề cần quan tâm Bài toán quy hoạch lồi với ràng buộc tích phát biểu sau p min{f0 (x) | x ∈ X, i=1 fi (x) ≤ 0}, (P ) fi : Rn → R, i = 0, 1, , p, hàm lồi X tập lồi compact khác rỗng Tương tự toán cực tiểu tích p ≥ hàm lồi tập lồi đóng khác rỗng Rn , toán quy hoạch lồi với ràng buộc tích (P ) toán NP-khó, chí trường hợp đơn giản p = 2, hàm f1 , f2 tuyến tính X đa diện (xem [5]) Và (P ) mô hình toán học nhiều toán thực tế lĩnh vực khác như: hình học tính toán, phân tích kinh tế vi mô, tối ưu danh mục đầu tư, thiết kế chip VLSI v.v Cho đến nay, có nhiều thuật toán theo phương pháp khác đề xuất để giải toán quy hoạch lồi với ràng buộc tích, chẳng hạn xem [12], [13], [18], [22], danh mục tài liệu tham khảo kèm theo Chương luận án giới thiệu thuật toán [5] theo phương pháp xấp xỉ kết hợp với kỹ thuật rẽ nhánh H.P Benson đề xuất năm 2010 để giải toán Một lớp toán quan trọng khác quy hoạch toán học toán tối ưu đồng thời p ≥ hàm mục tiêu (có thể đối kháng nhau) tập chấp nhận X khác rỗng Rn Bài toán gọi Bài toán quy hoạch đa mục tiêu Do không gian giá trị (outcome space) toán thứ iv tự đầy đủ, tức hai điểm lúc so sánh với nhau, nên thay khái niệm nghiệm tối ưu thông thường, quy hoạch đa mục tiêu người ta sử dụng khái niệm nghiệm hữu hiệu Như biết, trường hợp tất hàm mục tiêu hàm tuyến tính tập chấp nhận đa diện tập nghiệm hữu hiệu toán quy hoạch tuyến tính đa mục tiêu tập không lồi có cấu trúc phức tạp Vì vậy, việc xác định toàn tập nghiệm hữu hiệu toán quy hoạch đa mục tiêu đòi hỏi chi phí tính toán lớn khối lượng tính toán tăng nhanh kích thước toán (tức số biến n, số hàm mục tiêu p số ràng buộc biểu diễn tập chấp nhận được) tăng Năm 1972, lần Philip [16] đưa mô hình toán học Bài toán tối ưu tập Parero Đó toán tối ưu hàm thực tập nghiệm hữu hiệu toán quy hoạch đa mục tiêu Việc giải toán cho phép ta xác định nghiệm hữu hiệu tốt theo mục tiêu mà không cần phải xác định toàn tập nghiệm hữu hiệu Nhiều tác giả đề xuất thuật toán để giải toán này, chẳng hạn xem J Philip [16], H.P Benson D Lee [6], R Horst N.V Thoai [7], N.V Thoai [19, 20, 21], L.D Muu [15], L.T.H An, P.D Tao L.D Muu [3], N.T.B.Kim [10], N.T.B Kim L.D Muu [11], Y Yamamoto [23] Trong luận văn này, dựa cấu trúc đặc biệt tập ảnh hữu hiệu (outcome efficient set) toán quy hoạch lồi hai mục tiêu phương pháp xấp xỉ với kỹ thuật rẽ nhánh, đề xuất thuật toán để giải toán cực đại hàm đơn điệu tập nghiệm hữu hiệu toán Sự hội tụ thuật toán ví dụ minh họa kết tính toán trình bày đầy đủ Kết công bố ”http://www.optimizationonline.org/DB_HTML/2011/10/3195.html” gửi đăng tạp chí Pacific Journal of Optimization với tiêu đề "Optimization over the Efficient Set of a Bicriteria Convex Programming Problem" Ngoài Lời cảm ơn, Lời mở đầu, Kết luận Danh sách Tài liệu tham khảo, nội dung luận văn trình bày ba chương Cụ thể: v Chương 1: "Bài toán quy hoạch lồi với ràng buộc tích Bài toán tối ưu tập Pareto", dành để nhắc lại số khái niệm kết cần dùng giới thiệu hai toán quan tâm nghiên cứu luận án Việc đưa hai toán dạng tương đương lược đồ giải chúng giới thiệu với chứng minh đầy đủ Chương 2: "Thuật toán giải toán quy hoạch lồi với ràng buộc tích" giới thiệu thuật toán H.P Benson giải toán từ sở lý thuyết, thuật toán chi tiết, định lý hội tụ ví dụ minh họa Đây nội dung báo: H.P Benson (2010), Simplicial Branch-and-Reduce Algorithm for Con- vex Programs with a Multiplicative Constraint, Journal of Optimization Theory and Application, 145, pp 213 - 233 Chương 3: "Thuật toán giải toán tối ưu tập Pareto" trình bày thuật toán đề xuất để giải toán cực đại hàm mục tiêu có dạng ϕ(f (x)), ϕ hàm đơn điệu tăng, tập nghiệm hữu hiệu toán quy hoạch lồi hai mục tiêu Vmin{f (x) = (f1 (x), f2 (x)) | x ∈ X} với X ⊂ Rn tập compact khác rỗng f1 , f2 hai hàm lồi nhận giá trị dương X Chúng tiếp tục nghiên cứu xây dựng thuật toán giải toán tối ưu hàm điệu tập nghiệm hữu hiệu toán quy hoạch lồi đa mục tiêu trường hợp có số hàm mục tiêu Luận văn hoàn thành Khoa Toán Tin ứng dụng, Trường Đại học Bách khoa Hà Nội, hướng dẫn PGS TS Nguyễn Thị Bạch Kim Mặc dù cố gắng, song luận văn chắn nhiều thiếu sót Tác giả mong nhận góp ý thầy cô đồng nghiệp để luận văn hoàn thiện Xin chân thành cảm ơn Hà Nội, ngày 02 tháng 11 năm 2011 vi Danh mục kí hiệu, chữ viết R tập số thực Rn không gian Euclid n chiều x∈X x thuộc tập X x∈ /X x không thuộc tập X ∅ tập rỗng C \D hiệu tập C D C ∩D giao tập C D x, y tích vô hướng x y [x, y] đoạn thẳng nối hai điểm x y convX bao lồi tập X intX phần tương đối tập X epi(f ) epigraph hàm f hypo(f ) hypograph hàm f AT ma trận chuyển vị ma trận A t.ư, viết tắt cụm từ "tương ứng" v.đ.k viết tắt cụm từ "với điều kiện" (CM OP ) kí hiệu Bài toán quy hoạch lồi đa mục tiêu (LM OP ) kí hiệu Bài toán quy hoạch tuyến tính đa mục tiêu vii (PX ) kí hiệu Bài toán tối ưu tập hữu hiệu (OPY ) kí hiệu Bài toán tối ưu tập hữu hiệu không gian ảnh (OPG ) kí hiệu Bài toán tương đương với toán tối ưu tập hữu hiệu không gian ảnh viii Danh sách hình vẽ 1.1 Hypograph hàm f (x) = logx 1.2 Tập mức hypograph hàm f (x) = tgx 1.3 Biểu diễn hình học tập G 1.4 Biểu diễn hình học tập Gm với p = 16 1.5 Miền Gmb 18 1.6 y , y ∈ QE , y ∈ QE 20 2.1 Đơn hình T 0,1 2.2 Tập F k 29 2.3 Tập T k,γ 31 2.4 Lược đồ rẽ nhánh rút gọn 2.5 k,γ Xác định điểm vMB 34 3.1 Hai điểm hữu hiệu yˆ1 , yˆ2 GE 53 3.2 Tập S 55 3.3 Hai trường hợp đường cong Γ 57 3.4 Lược đồ rẽ nhánh 59 3.5 Minh họa cho Mệnh đề 3.2 62 12 27 33 ix Để xác định cận βk toán (OPG ), ta cần tìm nghiệm y k toán max{ϕ(y)|y ∈ U k } Vì U k = S∈T k S nên max{ϕ(y)|y ∈ U k } = max {max{ϕ(y)|y ∈ S}} S∈T k Tại Bước lặp k, thuật toán không dừng, ta chọn đơn hình S = S k,¯η ∈ T k thỏa mãn βk = β(S k,¯η ) S sinh hai điểm y L y R biết Gọi y ω điểm x∗ tương ứng với điểm xác định mô tả Mệnh đề 3.1 Khi đó, áp dụng lược đồ nhánh cận cho đơn hình S với điểm chia y ω ta hai đơn hình S S Nhận xét 3.3 Đặt T k+1 = T k \ {S} ∪ {S , S } U k+1 = S S∈T k+1 Từ Nhận xét 3.3 ta có GE ⊂ U k+1 ⊂ U k Hơn nữa, ϕ(y ω ) > αk cập nhật cận tốt tức đặt αk+1 = ϕ(y ω ) Khi đó, nghiệm chấp nhận tốt y best = y ω nghiệm hữu hiệu tương ứng với y best xbest = x∗ Bây ta xét toán max{ϕ(y)|y ∈ S}, (P (S)) ϕ(y) hàm đơn điệu tăng R2+ S 2−đơn hình sinh hai điểm y L , y R Mệnh đề 3.2 Nghiệm tối ưu Bài toán (P (S)) đạt cạnh y L , y R đơn hình S Chứng minh Gọi y ∗ nghiệm tối ưu toán max{ϕ(y)|y ∈ S} Giả sử phản chứng y ∗ ∈ [y L , y R ] Vì đơn hình S có hai cạnh song song với trục tọa độ nên tồn yˆ ∈ [y L , y R ] cho yˆ = y ∗ y ∗ ≤ yˆ Vì hàm ϕ(y) hàm đơn điệu tăng nên ϕ(y ∗ ) < ϕ(ˆ y ) Điều mâu thuẫn với giả thiết y ∗ ∈ Argmax{ϕ(y)|y ∈ S} suy điều phải chứng minh 61 y2 Y G yˆ yL y∗ yO yR y1 O Hình 3.5: Minh họa cho Mệnh đề 3.2 Theo Mệnh đề 3.2, Bài toán P (S) có nghiệm tối ưu nằm cạnh [y L , y R ] đơn hình S Cạnh tập nghiệm hệ    d, y = α (a) (3.1.8)  y1 ≥ y1L , y2 ≥ y2R (b) Từ (3.1.8(a)), ta có y2 = α d1 − y1 d2 d2 Do đó, Bài toán P (S) đưa toán cực đại hàm biến khoảng đóng R max{θ(y1 )|y1L ≤ y1 ≤ y1R }, θ(y1 ) = ϕ y1 , 62 α d1 − y1 d2 d2 (P (S)) Ví dụ: Xét hàm ϕ(y) = y1 y2 Khi θ(y1 ) = α d1 y1 − L y12 d2 d2 Đây hàm đa thức bậc nên dễ dàng tìm cực đại đoạn y1L , y1R Nhận xét 3.4 Theo lý luận trên, thay giải Bài toán (P (S)), ta giải toán cực đại hàm biến (P (S )) Nếu y1opt nghiệm tối ưu Bài toán (P (S )) y opt = (y1opt , y2opt ) nghiệm tối ưu Bài toán (P (S)), y2opt = 3.2 α d1 − y1opt d2 d2 Thuật toán giải Bài toán (OPG) Thuật toán xấp xỉ kết hợp với kỹ thuật rẽ nhánh OAB (Outer Approximation with Branching technique ) giải toán (OPG ) mô tả chi tiết sau Thuật toán OAB ♦ Bước khởi tạo Thực bước đây: – Xác định giá trị tối ưu αi Bài toán (SPi ) với i = 1, – Giải Bài toán (P1 ) Bài toán (P2 ) để xác định hai điểm hữu hiệu yˆ1 , yˆ2 ∈ GE hai nghiệm hữu hiệu xˆ1 , xˆ2 tương ứng với yˆ1 , yˆ2 – If yˆ1 ≡ yˆ2 Then STOP, yˆ1 nghiệm tối ưu Bài toán (OPG ) xˆ1 nghiệm tối ưu Bài toán (PX ) – If ϕ(ˆ y ) < ϕ(ˆ y ) Then α0 = ϕ(ˆ y ) y best = yˆ1 , xbest = xˆ1 ; 63 Else α0 = ϕ(ˆ y ) y best = yˆ2 , xbest = xˆ2 ; (α0 cận tốt tại, y best điểm chấp nhận tốt tại, xbest nghiệm hữu hiệu tương ứng với y best ) – Đặt y L = yˆ1 y R = yˆ2 Đặt S 0,1 = S , S 2−đơn hình sinh hai điểm y L y R Đặt T := {S 0,1 } U := S 0,1 ; – Tìm giá trị tối ưu β(S ) Bài toán P (S ); – Đặt k := 0; Chuyển sang Bước lặp k; Bước lặp k, (k = 0, 1, 2, ) Thực bước k1 đến k3 ♦ Bước k1 (Chọn đơn hình tính cận trên) – Tìm S k,¯η ∈ T k , S = S k,¯η đơn hình sinh hai điểm y L y R biết, thỏa mãn β(S k,¯η ) := max{β(S ) | S ∈ T k } – Đặt βk := β(S k,¯η ) (cận tốt tại) – If βk − αk ≤ ε Then STOP (y best nghiệm tối ưu ε−xấp xỉ Bài toán (OPG ) xbest nghiệm xấp xỉ Bài toán (PX )) Else Đặt S k = S k,¯η chuyển sang Bước k2 ♦ Bước k2 (Tìm điểm chia cập nhật cận dưới) – Xác định gốc y O đơn hình S k (3.1.3), y L y R hai điểm sinh đơn hình S k – Giải Bài toán (T (y O )) để tìm nghiệm tối ưu (λ∗ , x∗ )T – Đặt y ωk = λ∗ y O ∈ GE (điểm chia đơn hình S k ) x∗ nghiệm hữu hiệu tương ứng với y ωk 64 – If ϕ(y ωk ) > αk Then αk+1 = ϕ(y ωk ) (cận tốt tại) y best = y ωk (nghiệm chấp nhận tốt tại) xbest = x∗ ; (nghiệm hữu hiệu tương ứng với y best ) Else Chuyển sang Bước k3 ♦ Bước k3 (Áp dụng lược đồ rẽ nhánh cho S k với điểm chia y ωk ) – Đặt S1k 2−đơn hình sinh hai điểm y L y R = y ωk S2k 2−đơn hình sinh hai điểm y L = y ωk y R ; – Với i = 1, 2, tìm giá trị tối ưu β(Sik ) Bài toán (P (Sik )); – Đặt T k+1 = T k \ {S k } ∪ {S1k , S2k }; – Đặt k := k + Chuyển sang Bước lặp k Bổ đề sau coi trường hợp đặc biệt Bổ đề 4.2 [5] Bổ đề 3.1 Giả sử thuật toán OAB lặp vô hạn {S k } dãy 2−đơn hình sinh thuật toán, với k lược đồ rẽ nhánh rút gọn áp dụng cho S k Khi {S k }có dãy {S kq } thỏa mãn lim S kq = y ∗ ∈ GE q Định lý 3.1 Thuật toán dừng sau hữu hạn bước sinh nghiệm ε−xấp xỉ Bài toán (OPG ) Khi ε = 0, chuỗi {y ωk } có điểm tụ nghiệm tối ưu toàn cục Bài toán (OPG ) Chứng minh Ký hiệu f∗ giá trị tối ưu Bài toán (OPG ) Nếu thuật toán không dừng sinh dãy đơn hình vô hạn {S k }, {y optk ∈ S k } nghiệm tối ưu Bài toán P (S k ), với k lược đồ rẽ nhánh 65 áp dụng cho S k Hơn nữa, theo Bổ đề 3.1, cách lấy dãy cần, ta giả thiết limk S k = y ∗ ∈ GE Từ suy y optk → y ∗ Vì dãy cận {βk } đơn điệu βk = β(S k ) = ϕ(y optk ) nên ta có lim βk = lim ϕ(y optk ) = ϕ(y ∗ ) ≥ f∗ k k Vì y ∗ ∈ GE nghiệm chấp nhận Bài toán (OPG ) nên suy y ∗ nghiệm tối ưu toàn cục Bài toán (OPG ) 3.3 Ví dụ minh họa Ví dụ 3.1 Xét Bài toán (PX ) với h(x) = (x1 + x2 − 0.4)(x1 + 4x2 + 0.2), XE tập nghiệm hữu hiệu Bài toán (CM OP ), f1 (x) = x1 + x2 , f2 (x) = x1 + 4x2 + 1, g1 (x) = (x1 − 1)2 + 4x22 − 0.2, g2 (x) = 3x1 − 8x2 − Dễ thấy ϕ(y) = (y1 − 0.4)(y2 − 0.8) Bây ta giải Bài toán (OPG ) để tìm nghiệm ε−xấp xỉ với ε = 0.0001 ♦ Bước khởi tạo: Giải Bài toán (SP1 ) (SP2 ) giá trị tối ưu tương ứng α1 = 0.500000, α2 = 1.000000 66 Giải Bài toán (P1 ) (P2 ) nghiệm tối ưu (ˆ x1 , yˆ1 ) = (0.599782, −0.099782, 0.500000, 1.998910), (ˆ x2 , yˆ2 ) = (0.799562, 0.199890, 0.999452, 1.000000), xˆ1 = (0.599782, −0.099782), xˆ2 = (0.799562, 0.199890), hai nghiệm hữu hiệu tương ứng với hai điểm ảnh hữu hiệu yˆ1 = (0.500000, 1.998910), yˆ2 = (0.999452, 1.000000) Vì ϕ(ˆ y ) = 0.119891 > ϕ(ˆ y ) = 0.119890 nên chọn α0 = ϕ(ˆ y ) = 0.119890 y best = yˆ2 , xbest = xˆ2 Đặt y L = yˆ1 , y R = yˆ2 S 0,1 := S , S sinh y L y R Đặt T := {S 0,1 } U := S 0,1 Giải Bài toán P (S ) giá trị tối ưu β(S ) = 0.244618 ♦ Bước lặp k = – Bước 0.1 Vì T = {S 0,1 }, nên β0 := β(S 0,1 ) = 0.244618 Vì β0 − α0 = 0.124728 > ε = 0.0001 nên đặt S = S 0,1 Chuyển sang Bước 0.2 – Bước 0.2 Từ (3.1.3), xác định điểm y O = (y1L , y2R ) = (0.500000, 1.000000) Giải Bài toán (T (y O )), ta tìm nghiệm tối ưu (λ∗ , x∗ ) = (1.292892, 0.575735, 0.070711) Đặt y ω0 = λ∗ y O = (0.646446, 1.292892) 67 Vì ϕ(y ω0 ) = 0.121471 > α0 = 0.119890 nên α1 = 0.121471 y best = y ω0 = (0.646446, 1.292892), xbest = x∗ = (0.575735, 0.070711) – Bước 0.3 Đặt S10 2−đơn hình sinh hai điểm y L y R = y ω0 , S20 2−đơn hình sinh điểm y L = y ω0 y R Giải Bài toán P (S10 ) P (S20 ) nhận giá trị tối ưu tương ứng β(S10 ) = 0.146536 β(S20 ) = 0.146536 Đặt T = {S10 , S20 } = {S 1,1 , S 1,2 }, S 1,1 = S10 S 1,2 = S20 ♦ Bước lặp k = – Bước 1.1 Vì β(S 1,1 ) = max{β(S ) | S ∈ T } nên đặt β1 = β(S 1,1 ) = 0.146536, S 1,1 sinh hai điểm y L = (0.500000, 1.998910) y R = (0.646446, 1.292892) Vì β0 − α0 = 0.025065 > ε = 0.0001 nên đặt S = S 1,1 chuyển sang Bước 1.2 – Bước 1.2 Từ (3.1.3), xác định điểm y O = (y1L , y2R ) = (0.500000, 1.292892) Giải Bài toán (T (y O )), ta tìm nghiệm tối ưu (λ∗ , x∗ ) = (1.145344, 0.554299, 0.018373) Đặt y ω0 = λ∗ y O = (0.572672, 1.480806) Vì ϕ(y ω1 ) = 0.117556 < α1 = 0.121471 nên cận không cập nhật – Bước 1.3 Đặt S11 2−đơn hình sinh hai điểm y L y R = y ω1 , S21 2−đơn hình sinh điểm y L = y ω1 y R Giải Bài toán P (S11 ) P (S21 ) nhận giá trị tối ưu tương 68 ứng β(S11 ) = 0.128172 β(S21 ) = 0.123256 Đặt T = T \ {S 1,1 } ∪{S11 , S21 } = {S 1,2 , S11 , S21 } = {S 2,1 , S 2,2 , S 2,3 } Sau bước lặp, β7 − α7 = 0.000089 < ε = 0.0001 nên thuật toán dừng với nghiệm tối ưu ε−xấp xỉ Bài toán (OPG ) y best = (0.646446, 1.292892) Đồng thời ta có nghiệm tối ưu toán (PX ) tương ứng xbest = (0.575735, 0.070711) giá trị tối ưu ϕ(y best ) = 0.1214710 Ví dụ 3.2 Xét toán PX cho dạng sau max ϕ(f (x)) = (f1 (x) − β1 )(f2 (x) − β2 ) v.đ.k x ∈ XE , với βi = min{fi (x) | x ∈ X}, i = 1, XE tập nghiệm hữu hiệu Bài toán (CM OP ), fi (x) = αi x + xT Di x, i = 1, 2, n X = {x ∈ Rn | −2 + j=1 xj j ≤ 100, Ax ≤ b, x ≥ 0} tham số xác định sau ♦ α1 , α2 ∈ Rn véctơ với thành phần ngẫu nhiên thuộc đoạn [0,1] ♦ A = (aij ) ∈ Rm×n ma trận ngẫu nhiên với thành phần thuộc đoạn [-1,1] ♦ b = (b1 , b2 , , bm )T vectơ ngẫu nhiên thỏa mãn n bi = aij + 2b0 , j=1 69 với b0 số thực ngẫu nhiên đoạn [0,1] ♦ Di ∈ Rn×n ma trận đường chéo với phần tử đường chéo nhận giá trị ngẫu nhiên đoạn [0,1] Áp dụng thuật toán xây dựng cho lớp toán với trường hợp n m nhằm tìm nghiệm tối ưu ε− xấp xỉ với ε = 0.005 Gap xác định U B−LB UB với U B, LB cận cận dưới, ta thu bảng sau n m 60 40 4.103116 4.096561 0.001598 70 50 1.865636 1.860822 0.002580 80 80 1.137924 1.136717 0.001061 100 60 5.153709 5.138920 0.002870 100 80 4.169557 4.166498 0.000731 120 120 15.94133 15.94088 0.000029 150 100 55.40159 55.29604 0.001905 150 120 7.587685 7.559456 0.003720 ■♥t❡r UB LB Gap Từ bảng kết ta thấy thuật toán thực tốt, chí trường hợp toán có kích thước lớn Số bước tính toán nhỏ thời gian chạy bước tương đối nhỏ bước phải giải toán quy hoạch lồi với hàm mục tiêu tuyến tính hai toán tìm cực đại đa thức bậc Hơn nữa, nghiệm đạt cuối chấp nhận với độ xấp xỉ nhỏ ε = 0.005 Kết luận: Chương trình bày chi tiết sở lý thuyết thuật toán giải toán tối ưu hàm đơn điệu tăng tập hữu hiệu quy hoạch lồi hai mục tiêu Thuật toán xây dựng theo phương pháp xấp xỉ kết hợp với kỹ thuật rẽ nhánh tính cận Ưu điểm thuật toán 70 bước thuật toán, ta cần giải quy hoạch lồi với hàm mục tiêu tuyến tính hai toán tối ưu hàm biến Như vậy, so với thuật toán khác đề xuất, thuật toán cho hội tụ nhanh Điều thể qua sở lý thuyết ví dụ chạy thực nghiệm 71 Kết luận chung Luận văn nghiên cứu phương pháp xấp xỉ kết hợp với kỹ thuật rẽ nhánh giải hai toán tối ưu toàn cục nhiều tác giả quan tâm ứng dụng để giải nhiều toán nảy sinh thực tế: toán quy hoạch lồi với ràng buộc tích toán tối ưu tập Pareto Cụ thể, luận văn thực hiện: i) Trình bày mô hình toán học toán quy hoạch lồi với ràng buộc tích toán tối ưu tập Pareto khái niệm kết liên quan đến hai toán ii) Giới thiệu thuật toán H.P Benson đề xuất để giải toán quy hoạch lồi với ràng buộc tích (P ) iii) Đề xuất thuật toán để giải toán tối ưu tập Pareto (PX ) iv) Đưa ví dụ xây dựng chương trình tính toán để thử nghiệm thuật toán Do hạn chế mặt thời gian kinh nghiệm, luận văn không tránh khỏi sai sót Tác giả mong nhận đóng góp thầy cô bạn đồng nghiệp để luận văn hoàn thiện 72 Tài liệu tham khảo Tài liệu tiếng Việt Nguyễn Thị Bạch Kim (2008), Giáo trình Các Phương pháp Tối ưu: Lý thuyết Thuật toán, Nhà xuất Bách Khoa, Hà Nội Hoàng Tụy (2006), Lý thuyết tối ưu, Viện Toán học, Hà Nội Tài liệu tiếng Anh An L.T.H., Tao P D., Muu L D (1996), Numerical solution for optimization over the efficient set by d.c optimization algorithm, Oper Res Lett., 19, pp 117-128 Bank B., Guddat J., Klatte D., Kummar B., Tammer K (1982), Nonlinear Parametric Optimization, Akademie-Verlag, Berlin Benson H.P (2010), Simplicial Branch-and-Reduce Algorithm for Convex Programs with a Multiplicative Constraint, J Optim Theory Appl., 145, pp 213–233 Benson H.P., Lee D (1996), Outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem, J Optim Theory Appl., 88, pp 77–105 Horst R., Thoai N.V (1999), Maximizing a concave function over the efficient or Weakly-efficient set, Eur J Oper Res., 117, pp 239–252 Horst R., Tuy H (1996), Global Optimization: Deterministic Approach, Springer, Berlin 73 Horst R., Thoai N.V., Benson H.P (1991), Concave minimization via conical partitions and polyhedral outer approximation, Math Program., 50, pp 259–274 10 Kim N.T.B (2000), An algorithm for optimizing over the efficient set, Vietnam Journal of Mathematics, 28(4), pp 329-340 11 Kim N.T.B., Muu L.D (2002), On the projection of the efficient set and potential applications, Optimization, 51(2), pp 401-421 12 Kuno T., Yamamoto Y (1998), A finite algorithm for globally optimizing a class of rank-two reverse convex programs, J Glob Optim., 12, pp 247–265 13 Kuno T., Yajima Y., Yamamoto Y., Konno H (1994), Convex programs with an additional constraint on the product of several convex functions, Eur J Oper Res., 77, pp 314–324 14 Luc D.T (1989), Introduction to Nonlinear Optimization, Cinvestar IPN, Mexico, D.F 15 Muu L.D (2000), A convex-concave programming method for optimizing over the effiient set, Acta Mathematica Vietnamica, 25, pp 67-85 16 Philip J (1972), Algorithms for the vector maximization problem, Math Programming, 2, pp 207–229 17 Phu H X (2005), On Efficient Sets in R2 , Vietnam Journal of Mathematics, 33(4), pp 463-468 18 Thoai N.V (1993), Canonical d.c programming techniques for solving a convex program with an additional constraint of multiplicative type, Computing, 50, pp 241-253 74 19 Thoai N.V (2000), Conical algorithm in global optimization for optimizing over efficient sets, J Glob Optim., 18, pp 321–336 20 Thoai N.V (2008), Decomposition branch and bound algorithm for optimization problems over efficient set, J Ind Manag Optim 4, pp 647-660 21 Thoai N.V (2010), Reverse Convex Programming Approach in the Space of Extreme Criteria for Optimization over Efficient Sets, J Optim Theory and Appl., 147, pp 263-277 22 Tuy H., Luc L.T (2000), A New Approach to Optimization Under Monotonic Constraint, J Glob Optim., 18, pp 1-15 23 Yamamoto Y.(2002), Optimization over the efficient set: overview, J Glob Optim., 22, pp 285–317 75 ... mối quan hệ Bài toán (S) Bài toán (P ) Mệnh đề 1.4 (i) Điểm x∗ nghiệm tối ưu toàn cục Bài toán (P ) tồn điểm y ∗ thỏa mãn (x∗ , y ∗ ) nghiệm tối ưu toàn cục Bài toán (S) (ii) Bài toán (P ) không... efficient set) toán quy hoạch lồi hai mục tiêu phương pháp xấp xỉ với kỹ thuật rẽ nhánh, đề xuất thuật toán để giải toán cực đại hàm đơn điệu tập nghiệm hữu hiệu toán Sự hội tụ thuật toán ví dụ minh... nghiên cứu Bài toán quy hoạch lồi với ràng buộc tích Bài toán tối ưu tập Pareto Đây hai toán tối ưu toàn cục có nhiều ứng dụng để giải toán nảy sinh từ thực tế Do nhu cầu ứng dụng, hai toán thu