Tài liệu Phương pháp giải một số lớp bài toán tối ưu đa mục tiêu và ứng dụ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 GIẢI MỘT SỐ LỚP BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ ỨNG DỤNG LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2017 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 GIẢI MỘT SỐ LỚP BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 62460112 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS. TS. Nguyễn Thị Bạch Kim 2. GS. TSKH. Đinh Thế Lục HÀ NỘI - 2017 LỜI CAM ĐOAN Luận án này được hoàn thành tại Viện Toán ứng dụng và Tin học, Trường Đại học Bách Khoa Hà Nội dưới sự hướng dẫn khoa học của PGS. TS. Nguyễn Thị Bạch Kim và GS. TSKH. Đinh Thế Lục. Các kết quả được trình bày trong luận án là mới và chưa từng được ai công bố trong bất kỳ công trình nào khác. Các kết quả được công bố chung với PGS. TS. Nguyễn Thị Bạch Kim và GS. TSKH. Đinh Thế Lục đã được sự đồng ý của các đồng tác giả khi đưa vào luận án. Thay mặt tập thể hướng dẫn PGS. TS. Nguyễn Thị Bạch Kim Tác giả Trần Ngọc Thăng Lời cảm ơn Luận án được thực hiện dưới sự hướng dẫn tận tình và nghiêm khắc của PGS. TS. Nguyễn Thị Bạch Kim và GS. TSKH. Đinh Thế Lục. Trong suốt quá trình nghiên cứu và thực hiện luận án, thầy cô đã từng bước dẫn dắt, truyền cho tác giả niềm đam mê nghiên cứu cùng nhiều kinh nghiệm, kỹ năng, kiến thức quý báu, đồng thời luôn động viên khích lệ để tác giả vượt qua những thử thách trên bước đường làm khoa học. Tác giả xin chân thành gửi tới thầy cô sự kính trọng và lòng biết ơn sâu sắc nhất. Trong quá trình học tập, nghiên cứu và thực hiện luận án, tác giả đã nhận được sự quan tâm, giúp đỡ với những lời khuyên thiết thực và quý báu của GS. Lê Dũng Mưu, GS. Trần Vũ Thiệu, PGS. Nguyễn Văn Châu, PGS. TSKH. Huỳnh Văn Ngãi, PGS. TS. Phan Nhật Tĩnh. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới các thầy. Tác giả xin trân trọng cảm ơn Ban Giám hiệu, Phòng Tổ chức cán bộ, 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ả trong suốt quá trình hoàn thành luận án. Tác giả chân thành cảm ơn Ban lãnh đạo cùng toàn thể cán bộ Viện Toán ứng dụng và Tin học, Trường Đại học Bách Khoa Hà Nội, đã luôn động viên, giúp đỡ và hỗ trợ nhiều mặt để tác giả yên tâm học tập và nghiên cứu. Tác giả cũng xin cảm ơn Quỹ Phát triển Khoa học và Công nghệ Quốc gia (NAFOSTED) đã hỗ trợ kinh phí nghiên cứu và thực hiện luận án. Xin chân thành cảm ơn TS. Lê Quang Thủy, TS. Nguyễn Cảnh Nam, TS. Nguyễn Thị Toàn, TS. Nguyễn Thị Thanh Huyền, TS. Nguyễn Quang Thuận, TS. Vũ Thành Nam, TS. Tạ Anh Sơn, ThS. Lê Quang Hòa, TS. Trần Minh Hoàng, ThS. Đỗ Xuân Hưng, ThS. Phạm Thị Hoài, KS. Bùi Văn Chung cùng các anh chị em nghiên cứu sinh và bạn bè đồng nghiệp xa gần về sự động viên khích lệ cũng như những trao đổi hữu ích trong quá trình tác giả học tập và nghiên cứu. Tác giả xin gửi lời cảm ơn tới các phản biện độc lập vì đã dành nhiều thời gian để đọc và đưa ra các góp ý, nhận xét quý báu để tác giả chỉnh sửa luận án được hoàn thiện hơn. Cuối cùng, sự cảm thông, động viên và chia sẻ của những người thân trong gia đình chính là động lực để tác giả từng bước hoàn thành luận án. Vì vậy, tác giả xin dành tặng luận án này cho gia đình thân yêu của mình như một món quà tinh thần để bày tỏ lòng biết ơn chân thành và sâu sắc. Mục lục Một số ký hiệu và chữ viết tắt iii Danh mục hình vẽ và danh mục bảng vi Lời mở đầu 1 2 3 viii Bài toán quy hoạch đa mục tiêu lồi suy rộng 1.1 Hàm lồi suy rộng . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 1.2 Điểm hữu hiệu và hướng pháp tuyến . . . . . . . . . . . . . . . . 9 1.3 Bài toán quy hoạch đa mục tiêu lồi suy rộng . . . . . . . . . . . . 17 Thuật toán hướng pháp tuyến giải bài toán quy hoạch đa mục tiêu lồi suy rộng 21 2.1 2.2 Xác định điểm ảnh hữu hiệu yếu và hướng pháp tuyến . . . . . . . Thuật toán hướng pháp tuyến trên không gian ảnh . . . . . . . . . 23 27 2.3 Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . 33 2.4 Tính toán thử nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 41 Thuật toán giải một số bài toán quy hoạch tích mở rộng 3.1 Thuật toán giải bài toán quy hoạch tích lồi suy rộng (GMP) . . . . 55 56 Thuật toán giải bài toán quy hoạch tích lõm mở rộng (GIMP) . . . 3.2.1 Các thao tác cơ bản của lược đồ nhánh cận . . . . . . . . 64 69 3.2.2 Thuật toán nhánh cận trên không gian ảnh . . . . . . . . . 74 3.2.3 Tính toán thử nghiệm . . . . . . . . . . . . . . . . . . . . 78 3.2 i 4 Thuật toán giải bài toán tối ưu trên tập nghiệm hữu hiệu 4.1 4.2 83 Thuật toán giải bài toán (QP) với ϕ là hàm tựa lõm . . . . . . . . 4.1.1 Phân hoạch và bài toán con . . . . . . . . . . . . . . . . . 85 86 4.1.2 4.1.3 Thuật toán nhánh cận trên không gian ảnh . . . . . . . . Tính toán thử nghiệm . . . . . . . . . . . . . . . . . . . . 90 94 Thuật toán giải bài toán (DP) với ϕ là hàm đơn điệu tăng . . . . . 4.2.1 Đơn hình xấp xỉ ngoài và lược đồ rẽ nhánh . . . . . . . . 98 99 4.2.2 4.2.3 Thuật toán nhánh cận - xấp xỉ ngoài . . . . . . . . . . . . 101 Tính toán thử nghiệm . . . . . . . . . . . . . . . . . . . . 106 Kết luận chung 111 Danh mục các công trình đã công bố 114 Danh mục tài liệu tham khảo 115 Danh mục thuật ngữ 124 ii Một số ký hiệu và chữ viết tắt Rn không gian Euclide n chiều Rn+ tập các véc tơ không âm của Rn kxk chuẩn Euclide của véc tơ x ∈ Rn |x|  i x giá trị tuyệt đối của x ∈ R dãy điểm trong Rn hx, yi tích vô hướng của x và y [x, y] đoạn thẳng nối hai điểm x, y ∈ Rn , tức [x, y] = {q ∈ Rn | q = λ x + (1 − λ )y, 0 ≤ λ ≤ 1} B [x, y] Hộp chữ nhật tạo bởi hai đỉnh x, y ∈ Rn , tức B [x, y] = {q ∈ Rn | x ≤ q ≤ y} VolP Thể tích của đa diện P ⊂ Rn  conv x1 , x2 , . . . , xk bao lồi của các điểm x1 , x2 , . . . , xk là tập  x = ∑ki=1 λi xi : λi ≥ 0, ∑ki=1 λi = 1 intX phần trong tương đối của tập X ∂X biên của tập X NX (x0 ) nón pháp tuyến của X tại x0 ∈ X A+B tổng véc tơ của hai tập A và B A−B hiệu véc tơ của hai tập A và B t.ư. viết tắt của cụm từ "tương ứng" v.đ.k. viết tắt của cụm từ "với điều kiện" iii (LMOP) Bài toán quy hoạch đa mục tiêu tuyến tính (CMOP) Bài toán quy hoạch đa mục tiêu lồi (CBOP) Bài toán quy hoạch hai mục tiêu lồi (GMOP) Bài toán quy hoạch đa mục tiêu lồi suy rộng (QP) Bài toán (P) với hàm ϕ tựa lõm (DP) Bài toán (P) với hàm ϕ đơn điệu (MP) Bài toán quy hoạch tích (LMP) Bài toán quy hoạch tích tuyến tính (CMP) Bài toán quy hoạch tích lồi (GMP) Bài toán quy hoạch tích tựa lồi suy rộng (GIMP) Bài toán quy hoạch tích lõm mở rộng XE Tập nghiệm hữu hiệu của bài toán quy hoạch đa mục tiêu (MOP) theo nghĩa cực tiểu XW E Tập nghiệm hữu hiệu yếu của bài toán quy hoạch đa mục tiêu (MOP) theo nghĩa cực tiểu MinQ Tập các điểm hữu hiệu của tập Q theo nghĩa cực tiểu WMinQ Tập các điểm hữu hiệu yếu của tập Q theo nghĩa cực tiểu MaxQ Tập các điểm hữu hiệu của tập Q theo nghĩa cực đại WMaxQ Tập các điểm hữu hiệu yếu của tập Q theo nghĩa cực đại Min(Q, θ ) Tập các điểm hữu hiệu θ - xấp xỉ của tập Q theo nghĩa cực tiểu WMin(Q, θ ) Tập các điểm hữu hiệu yếu θ - xấp xỉ của tập Q theo nghĩa cực tiểu iv Danh mục hình vẽ 1.1 Minh họa tập S . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 q1 ∈ WMinQ, q2 6∈ WMinQ và q3 ∈ MinQ . . . . . . . . . . . . . 10 1.3 1.4 Hai nón pháp tuyến NQ (q1 ) và NQ (q2 ) . . . . . . . . . . . . . . . Hướng pháp tuyến dương (t.ư., không âm) của Q tại điểm hữu hiệu 11 1.5 q3 (t.ư. hữu hiệu yếu q1 ) . . . . . . . . . . . . . . . . . . . . . . . Minh họa tập Q và Q+ . . . . . . . . . . . . . . . . . . . . . . . 12 14 1.6 Cách xác định một điểm hữu hiệu yếu của tập Q+ . . . . . . . . . 15 2.1 Minh họa Ví dụ 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2 Hình bên trái bao gồm các đường thẳng biểu diễn các siêu phẳng cắt chứa các diện của Y out , còn hình bên phải biểu diễn các điểm hữu hiệu yếu của tập ảnh Y trong Ví dụ 2.4 . . . . . . . . . . . . . Tập xấp xỉ ngoài Y out của Y  và các điểm hữu hiệu yếu của tập ảnh 46 Y trong Ví dụ 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Bên trái là tập xấp xỉ ngoài Y out ; bên phải là tập các đỉnh của tập 47 xấp xỉ trong Y in ở Ví dụ 2.6 . . . . . . . . . . . . . . . . . . . . . Tập ảnh hữu hiệu yếu WMinY và phân phối của các điểm ảnh hữu 48 2.3 2.5 hiệu yếu được sinh ra bởi ba phương pháp trong Trường hợp 1 của Ví dụ 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 49 Tập ảnh hữu hiệu yếu WMinY và phân phối của các điểm ảnh hữu hiệu yếu được sinh ra bởi ba phương pháp trong Trường hợp 2 của Ví dụ 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.1 Đường cong hữu hiệu MaxY − . . . . . . . . . . . . . . . . . . . 67 3.2 Sinh điểm hữu hiệu mới bằng phép chiếu . . . . . . . . . . . . . . 68 v 3.3 Minh họa Trường hợp 1 và Trường hợp 2 của đoạn cong hữu hiệu E 70 3.4 3.5 Minh họa Trường hợp 3 của đoạn cong hữu hiệu E . . . . . . . . Minh họa thao tác phân hoạch và chia nhánh . . . . . . . . . . . . 71 77 4.1 4.2 Đường cong hữu hiệu MinY + . . . . . . . . . . . . . . . . . . . . Cách xác định điểm chia đôi ynew . . . . . . . . . . . . . . . . . 86 87 4.3 4.4 Đơn hình S(yL , yR ) . . . . . . . . . . . . . . . . . . . . . . . . . Minh họa cách sinh dãy các đa diện {Sk } . . . . . . . . . . . . . 89 93 4.5 4.6 Đơn hình S(yL , yR ) . . . . . . . . . . . . . . . . . . . . . . . . . 99 Đường cong Γ(yL , yR ) . . . . . . . . . . . . . . . . . . . . . . . . 100 4.7 Lược đồ rẽ nhánh áp dụng cho đơn hình S(yL , yR ) . . . . . . . . . 101 vi Danh mục bảng 2.1 Kết quả tính toán của Ví dụ 2.2 . . . . . . . . . . . . . . . . . . . 44 2.2 Kết quả tính toán cho Ví dụ 2.6 . . . . . . . . . . . . . . . . . . . 48 2.3 2.4 Kết quả tính toán của Ví dụ 2.7 khi p = 3 . . . . . . . . . . . . . Kết quả tính toán của Ví dụ 2.7 khi p > 3 . . . . . . . . . . . . . 51 51 2.5 Kết quả tính toán của Ví dụ 2.8 . . . . . . . . . . . . . . . . . . . 53 3.1 3.2 Kết quả tính toán của Ví dụ 3.1 . . . . . . . . . . . . . . . . . . . Kết quả tính toán của Ví dụ 3.2. . . . . . . . . . . . . . . . . . . 63 79 3.3 Kết quả tính toán của Ví dụ 3.3. . . . . . . . . . . . . . . . . . . 81 4.1 Kết quả tính toán của Ví dụ 4.2 trong trường hợp ϕ = ϕ0 . . . . . 96 4.2 4.3 Kết quả tính toán của Ví dụ 4.2 trong các trường hợp của ϕ . . . . Kết quả tính toán với bài toán sinh ngẫu nhiên trong Ví dụ 4.4 . . 96 98 4.4 Kết quả tính toán của Ví dụ 4.6 . . . . . . . . . . . . . . . . . . . 110 vii Lời mở đầu 1. Giới thiệu bài toán tối ưu đa mục tiêu Trong những năm 50 của thế kỷ 20, Quy hoạch đa mục tiêu, hay còn được gọi là Tối ưu đa mục tiêu hoặc Tối ưu véc tơ, đã trở thành một chuyên ngành toán học, thu hút sự quan tâm của nhiều tác giả và được phát triển mạnh mẽ suốt gần 70 năm qua. Các thành tựu của Quy hoạch đa mục tiêu được ứng dụng rộng rãi trong thực tế, đặc biệt là trong lý thuyết ra quyết định, kinh tế, tài chính, kỹ thuật, viễn thông,... (xem [23], [64], [83], [93], [94],...). Bài toán quy hoạch đa mục tiêu được phát biểu dưới dạng Min f (x) = ( f1 (x), f2 (x), . . . , f p (x)) với điều kiện x ∈ X, (MOP) trong đó X ⊂ Rn là tập các phương án chấp nhận được, f j : X → R, j = 1, . . . , p, p ≥ 2, là các hàm mục tiêu. Do không gian giá trị R p không có thứ tự đầy đủ nên thay vì khái niệm nghiệm tối ưu thông thường, tối ưu véc tơ sử dụng khái niệm nghiệm hữu hiệu được xác định theo thứ tự từng phần do G. Cantor (1845-1918) [21] và F. Hausdorff (1868-1942) [37] đề xuất. Bài toán (MOP) được gọi là bài toán quy hoạch đa mục tiêu lồi, ký hiệu là (CMOP), nếu X là tập lồi và f1 , . . . , f p là các hàm lồi. Đây là trường hợp đặc biệt của bài toán quy hoạch đa mục tiêu lồi suy rộng, ký hiệu là (GMOP), trong đó f1 , . . . , f p là các hàm lồi suy rộng và tập chấp nhận được X cũng là tập lồi. Nếu tất cả các hàm mục tiêu f1 , . . . , f p đều là hàm tuyến tính và X là tập lồi đa diện thì ta gọi (MOP) là bài toán quy hoạch đa mục tiêu tuyến tính và ký hiệu là (LMOP). Như đã biết, bài toán (LMOP) là trường hợp đơn giản nhất của bài toán (MOP) nói chung và của bài toán (CMOP) nói riêng. Theo tiếp cận trên không gian quyết định (decision space), việc giải bài toán (MOP) được xem như việc xác định toàn bộ hay một phần của tập nghiệm hữu hiệu XE hoặc tập nghiệm hữu hiệu yếu XW E . Đây là một việc khó, vì ngay cả trong trường hợp đơn giản nhất của (MOP) là bài toán quy hoạch đa mục tiêu tuyến tính viii (LMOP), tập nghiệm hữu hiệu XE và tập nghiệm hữu hiệu yếu XW E đã là các tập không lồi với cấu trúc rất phức tạp. Theo H.P. Benson [11], khối lượng tính toán để sinh ra toàn bộ tập nghiệm hữu hiệu XE hoặc tập nghiệm hữu hiệu yếu XW E của bài toán (LMOP) tăng rất nhanh khi kích thước của bài toán (tức số biến n, số hàm mục tiêu p và số ràng buộc biểu diễn tập chấp nhận được) tăng. Với hy vọng giảm khối lượng tính toán, các thuật toán theo hướng tiếp cận trên không gian ảnh hay không gian giá trị (outcome space) được thiết kế để xác định toàn bộ hay một phần của tập ảnh hữu hiệu YE = f (XE ) hoặc tập ảnh hữu hiệu yếu YW E = f (XW E ). Theo định nghĩa, YE và YW E tương ứng là tập điểm hữu hiệu và tập điểm hữu hiệu yếu của tập ảnh Y = f (X) của tập chấp nhận được X qua ánh xạ f . Lý do chính cho hướng tiếp cận này là: i) Các bài toán tối ưu đa mục tiêu nảy sinh trong thực tế thường có số hàm mục tiêu p nhỏ hơn rất nhiều so với số biến n, hay thứ nguyên của không gian ảnh R p nhỏ hơn rất nhiều so với thứ nguyên của không gian quyết định Rn ; ii) Nhiều điểm của tập nghiệm hữu hiệu (tương ứng1 , tập nghiệm hữu hiệu yếu) có thể có cùng một ảnh qua ánh xạ f nên tập ảnh hữu hiệu YE (t.ư., tập ảnh hữu hiệu yếu YW E ) có cấu trúc đơn giản hơn XE (t.ư., XW E ); iii) Trong quá trình đưa ra quyết định, người ta thường lựa chọn phương án dựa trên giá trị hữu hiệu hơn là dựa trên nghiệm hữu hiệu (xem [11]). Trong tối ưu đa mục tiêu, việc nghiên cứu để giải bài toán quy hoạch đa mục tiêu tuyến tính (LMOP) có thể xem gần như hoàn chỉnh. Đã có nhiều cuốn sách chuyên khảo về bài toán (LMOP) (xem [57], [59], [92], [93],... và danh mục tài liệu tham khảo kèm theo). Rất nhiều thuật toán đã được đề xuất theo cả hai hướng tiếp cận trên không gian quyết định và không gian ảnh để giải bài toán này bằng nhiều phương pháp khác nhau như phương pháp đơn hình đa mục tiêu, phương pháp tham số, phương pháp vô hướng hóa, phương pháp nón pháp tuyến, phương pháp xấp xỉ ngoài hoặc kết hợp của các phương pháp đó, chẳng hạn xem các công trình của M. Zeleny [94], P. Armand and C. Malivert [7], R.E. Steuer [83], J.P. Dauer và Y.H. Liu [27], H.P. Benson [11], N.T.B. Kim và D.T. Lục [44], [45], M. Ehrgott, A. Löhne và L. Shao [29],... 1 Từ sau đây đến hết luận án, cụm từ "tương ứng" sẽ được viết tắt là "t.ư.". ix Với bài toán quy hoạch đa mục tiêu lồi và không lồi, đã có một số thuật toán được đề xuất. Hầu hết các thuật toán theo tiếp cận trên không gian quyết định được thiết kế dựa trên các phương pháp trọng số [25], phương pháp ε−ràng buộc [36], phương pháp hàm lợi ích [93], phương pháp lexicographic [20], phương pháp Tchebycheff [83],... để sinh một phần tập nghiệm hữu hiệu hay hữu hiệu yếu của bài toán. Theo tiếp cận trên không gian ảnh, các thuật toán thường sử dụng kỹ thuật xấp xỉ ngoài để xây dựng một dãy các tập xấp xỉ tập ảnh, trong đó ta có thể dễ dàng xác định được tập hữu hiệu các tập xấp xỉ này. Với cách tiếp cận này, một mặt, thuật toán sinh ra một phần của tập ảnh hữu hiệu của bài toán, mặt khác, nó sinh ra tập xấp xỉ của tập ảnh hữu hiệu chứa toàn bộ tập ảnh hữu hiệu (xem [30], [34], [62] và danh mục tài liệu tham khảo kèm theo). Trong [65], K. Miettinen đã phân loại chi tiết và so sánh các phương pháp hiện có để giải các bài toán quy hoạch đa mục tiêu phi tuyến. Các phương pháp để sinh ra tập xấp xỉ của tập nghiệm hữu hiệu và tập ảnh hữu hiệu được thống kê trong [78]. Hai bài toán tối ưu toàn cục quan trọng có liên quan chặt chẽ đến bài toán quy hoạch đa mục tiêu là bài toán tối ưu một hàm thực trên tập nghiệm hữu hiệu của bài toán quy hoạch đa mục tiêu (gọi tắt là Bài toán tối ưu trên tập nghiệm hữu hiệu) và bài toán quy hoạch tích cũng như các dạng mở rộng của nó. Bài toán tối ưu trên tập nghiệm hữu hiệu có mô hình toán học như sau min h(x) v.đ.k. x ∈ XE , (P) trong đó h(x) là một hàm số thực xác định trên Rn và XE là tập nghiệm của bài toán quy hoạch đa mục tiêu (MOP). Việc giải bài toán này có ý nghĩa đặc biệt vì nó giúp ta chọn được nghiệm hữu hiệu tốt nhất theo một tiêu chuẩn nào đó mà không nhất thiết phải xác định được toàn bộ tập nghiệm hữu hiệu. Tuy nhiên, đây là một bài toán khó, thậm chí khi h là hàm tuyến tính và XE là tập nghiệm hữu hiệu của bài toán quy hoạch đa mục tiêu tuyến tính (LMOP), vì tập chấp nhận được XE , nói chung, là tập không lồi với cấu trúc phức tạp và không có mô tả tường minh. Bài toán (P) do Philip [73] đưa ra lần đầu tiên vào năm 1972 và đã thu hút được sự quan tâm đặc biệt của rất nhiều tác giả trong và ngoài nước. Nhiều thuật toán đã được đề xuất để giải bài toán (P). Các thuật toán này cũng có thể được phân x loại theo hai hướng tiếp cận bao gồm tiếp cận trên không gian quyết định Rn (xem H.P. Benson [10], J.P. Dauer và T.A. Fosnaugh [26, 1995], L.T.H. An, L.D. Mưu và P.D. Tảo [4], L.T. Lực và L.D. Mưu [60], L.D. Mưu [67], N.T.B. Kim [42], N.V. Thoại [87], L.D. Mưu và H.Q. Tuyến [70], N.V. Thoại, Y. Yamamoto và D. Zenke [39], L.T.H. An, P.D. Tảo, N.C. Nam và L.D. Mưu [5], L.D. Mưu và L.Q. Thủy [69],...) và tiếp cận trên không gian ảnh R p (xem R. Horst và N.V. Thoại [38], J. Fulop and L.D. Mưu [31], Y. Yamamoto [91], N.T.B. Kim và L.D. Mưu [47], N.V. Thoại [88], H.P. Benson [16],...). Ta cũng có thể phân loại các thuật toán dựa theo phương pháp được dùng để xây dựng thuật toán, như thuật toán xấp xỉ ngoài, thuật toán nhánh cận, thuật toán theo tiếp cận đối ngẫu, thuật toán tìm đỉnh kề, thuật toán tìm đỉnh không kề,... (xem [92]) Bài toán quy hoạch tích và các dạng mở rộng của nó (gọi chung là bài toán quy hoạch tích mở rộng) có nhiều ứng dụng quan trọng trong các lĩnh vực khác nhau như kinh tế tài chính, tối ưu hóa quy trình sản xuất, tối ưu danh mục đầu tư, thiết kế chip VLSI,... Đây cũng là lớp các bài toán tối ưu toàn cục khó và thú vị nên đã thu hút sự quan tâm đặc biệt của nhiều tác giả. Bài toán quy hoạch tích được phát biểu như sau p min ∏ f j (x), v.đ.k. x ∈ X, (MP) j=1 trong đó X ⊂ Rn là tập các phương án chấp nhận được và f j , j = 1, . . . , p, p ≥ 2, là các hàm số thực xác định trên X. Tương tự như cách phân loại các bài toán quy hoạch đa mục tiêu, nếu X là tập lồi đóng trong Rn và các hàm f1 , . . . , f p là các hàm lồi trên X thì (MP) được gọi là bài toán quy hoạch tích lồi, ký hiệu là (CMP). Bài toán (MP) được gọi là bài toán quy hoạch tích tuyến tính, ký hiệu là (LMP), khi f1 , . . . , f p là các hàm tuyến tính và X là tập lồi đa diện. Trong [63], T. Matsui đã chỉ ra rằng, ngay cả trường hợp đơn giản nhất của bài toán (MP), tức là bài toán (LMP) với p = 2 và X là đa diện khác rỗng, cũng thuộc lớp bài toán NP−khó. Hiện nay đã có nhiều thuật toán được đề xuất để giải bài toán quy hoạch tích tuyến tính (LMP) (xem H. Konno và T. Kuno [52], S. Schaible và C. Sodini [80], H.P. Benson và G.M. Boger [17], T. Kuno [53], N.T.B. Kim [43], N.T.B. Kim, T.T.H. Yên và N.T.L. Trang [48], L. xi Shao và M. Ehrgott [82],...) và quy hoạch tích lồi (CMP) (xem N.V. Thoại [86], T. Kuno, Y. Yajima, và H. Konno [54], H.P. Benson [12], R.M. Oliveira, và P.A.V. Ferreira [71], Y. Gao, G. Wu và W. Ma [32], N.T.B. Kim, N.C. Nam, L.Q. Thủy [46], L. Shao và M. Ehrgott [81],...). Theo hiểu biết của tác giả, mặc dù có nhiều ứng dụng trong thực tiễn nhưng có rất ít công trình nghiên cứu bài toán quy hoạch tích mở rộng. 2. Mục đích nghiên cứu và ý nghĩa của đề tài Như đã trình bày, mặc dù bài toán quy hoạch đa mục tiêu lồi và các vấn đề liên quan đã được nghiên cứu tương đối hoàn chỉnh nhưng cho đến nay vẫn còn rất ít thuật toán giải bài toán tối ưu đa mục tiêu lồi suy rộng [92]. Hơn nữa, do nhu cầu ứng dụng, việc nghiên cứu xây dựng các thuật toán hiệu quả để giải bài toán quy hoạch đa mục tiêu lồi suy rộng, bài toán quy hoạch tích mở rộng, cũng như bài toán tối ưu trên tập nghiệm hữu hiệu là các vấn đề thời sự và luôn cần đầu tư nhiều công sức. Luận án này nghiên cứu và đề xuất các thuật toán mới để giải các bài toán sau: 1. Bài toán quy hoạch đa mục tiêu lồi suy rộng Min f (x) = ( f1 (x), f2 (x), . . . , f p (x)) v.đ.k. x ∈ X, (GMOP) trong đó tập chấp nhận được X ⊂ Rn là tập lồi compact khác rỗng và hàm mục tiêu f là hàm véc tơ giả lồi vô hướng trên X. 2. Bài toán quy hoạch tích lồi suy rộng tương ứng với bài toán (GMOP) m min ∏ f j (x), v.đ.k. x ∈ X, (GMP) j=1 trong đó các hàm số f j : Rn → R, j = 1, . . . , m và tập chấp nhận được X được giả thiết như trong phát biểu của bài toán (GMOP). 3. Bài toán quy hoạch tích lõm mở rộng, trong đó hàm mục tiêu có dạng tổng của một hàm với tích các hàm và tập chấp nhận được là tập lồi compact khác rỗng. Cụ thể, đó là bài toán xii k max Φ(x) = f0 (x) + ∏ fi (x) v.đ.k. x ∈ X, (GIMP) i=1 trong đó X ⊂ Rn là tập lồi compact khác rỗng và f j , j = 0, 1, . . . , k, là các hàm lõm nhận giá trị dương trên X. Bài toán quy hoạch tích mở rộng liên quan gần gũi nhất với bài toán (GIMP) và đã được nghiên cứu trong [41] là bài toán k min Φ(x) = f0 (x) + ∏ fi (x) v.đ.k. x ∈ X, i=1 trong đó X ⊂ Rn là tập lồi compact khác rỗng và f j , j = 0, 1, . . . , k, là các hàm lồi nhận giá trị dương trên X. Trong trường hợp đặc biệt, khi k = 2, thì bài toán (GIMP) trở thành bài toán cực đại tổng một hàm lõm với tích hai hàm lõm, và đã có một số thuật toán hữu hiệu được đề xuất để giải bài toán này (xem [6], [14], [68],...). Theo hiểu biết của chúng tôi, cho đến nay, hầu như chưa có thuật toán nào được đề xuất để giải bài toán (GIMP) trong trường hợp tổng quát. 4. Hai bài toán tối ưu trên tập nghiệm hữu hiệu XE của bài toán quy hoạch hai mục tiêu lồi. Đó là bài toán min h(x) = ϕ( f (x)) v.đ.k. x ∈ XE , (QP) trong đó ϕ : R2 → R là hàm tựa lõm trên tập ảnh Y và bài toán max h(x) = ϕ( f (x)) v.đ.k. x ∈ XE , (DP) với ϕ : R2 → R là hàm đơn điệu tăng trên tập ảnh Y . Dạng hàm mục tiêu h(x) = ϕ( f (x)) với hàm số thực ϕ : Y → R xuất hiện nhiều trong các bài toán nảy sinh từ thực tế và cũng đã được nhiều tác giả quan tâm nghiên cứu, chẳng hạn [47], [87], [88], [91] và danh sách tài liệu tham khảo kèm theo. Tất cả các thuật toán được đề xuất trong luận án đều được chứng minh là hội tụ, đồng thời được tính toán thử nghiệm và so sánh với một số thuật toán đã có. Ngoài các bài toán trên, chúng tôi đã nghiên cứu và đề xuất thuật toán giải bài toán cực đại tổng một hàm lõm với các cặp tích hai hàm lõm trên tập lồi compact khác rỗng, xiii cụ thể là bài toán s max g(x) = f1 (x) + ∑ f2i (x)f2i+1 (x) v.đ.k. x ∈ X, (GCMP) i=1 trong đó X ⊂ Rn là tập lồi compact khác rỗng và f j , j = 1, . . . , 2s + 1, là các hàm lõm trên X. Bài toán này được H.P. Benson [14] đưa ra lần đầu tiên, sau đó được nghiên cứu bởi A.M.M. Ashtiani và P.A.V. Ferreira [6]. Bằng phép biến đổi thích hợp, chúng tôi chuyển bài toán (GCMP) về một bài toán tương đương và đề xuất phương pháp nón pháp tuyến trên không gian ảnh để giải bài toán này [84]. Kết quả này đã được nhận đăng ở Pacific Journal of Optimization. Tuy nhiên, do khuôn khổ có hạn nên luận án không bao hàm kết quả này. 3. Cấu trúc và kết quả của luận án Luận án bao gồm phần mở đầu, lời cảm ơn, bốn chương, kết luận chung, danh mục các công trình đã công bố của tác giả có liên quan đến luận án và danh mục tài liệu tham khảo. Sau đây là nội dung chính của các chương. Chương 1. “Bài toán quy hoạch đa mục tiêu lồi suy rộng” dành để giới thiệu mô hình toán học của bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) cùng một số khái niệm và kết quả cơ bản liên quan. Các khái niệm và kết quả được trình bày trong chương này là cơ sở lý thuyết cho các thuật toán được đề xuất trong các chương sau của luận án. Mục 1.1 giới thiệu về một số hàm lồi suy rộng như hàm tựa lồi, hàm giả lồi, hàm véc tơ giả lồi vô hướng cùng các tính chất hữu dụng của chúng. Định lý KKT về điều kiện tối ưu cho bài toán quy hoạch lồi suy rộng một mục tiêu được trình bày trong mục này là công cụ lý thuyết nhằm xác định siêu phẳng cắt trong thuật toán xấp xỉ ngoài được đề xuất trong Chương 2 để giải bài toán (GMOP). Các khái niệm điểm hữu hiệu, điểm hữu hiệu yếu của một tập, điều kiện nhận biết thông qua khái niệm hướng pháp tuyến và các kết quả về cấu trúc của các tập điểm này được trình bày ở Mục 1.2. Cuối cùng, Mục 1.3 giới thiệu bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP), cùng các khái niệm cơ bản như nghiệm hữu hiệu, nghiệm hữu hiệu yếu, nghiệm hữu hiệu θ -xấp xỉ, nghiệm hữu hiệu yếu θ -xấp xỉ cũng như cấu trúc của tập giá trị hữu hiệu và của tập giá trị hữu hiệu yếu của bài toán (GMOP). xiv Chương 2. “Thuật toán hướng pháp tuyến giải bài toán quy hoạch đa mục tiêu lồi suy rộng” đề xuất một thuật toán hướng pháp tuyến giải bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP), trong đó sử dụng kỹ thuật xấp xỉ ngoài trên không gian ảnh để xác định tập nghiệm hữu hiệu yếu θ −xấp xỉ của bài toán (GMOP). Cách xác định điểm giá trị hữu hiệu yếu và hướng pháp tuyến tại mỗi bước lặp điển hình được giới thiệu ở Mục 2.1. Thuật toán chi tiết được mô tả trong Mục 2.2. Tiếp theo, Mục 2.3 sẽ trình bày chi tiết chứng minh tính hội tụ của thuật toán đề xuất. Đây là một đóng góp chính và quan trọng về mặt lý thuyết cho các phương pháp xấp xỉ ngoài giải bài toán quy hoạch đa mục tiêu. Các kết quả tính toán thử nghiệm được giới thiệu trong Mục 2.4 chứng tỏ tính hiệu quả và những ưu điểm của thuật toán so với một số thuật toán xấp xỉ ngoài giải bài toán quy hoạch đa mục tiêu lồi trước đó. Chương 3. “Thuật toán giải một số bài toán quy hoạch tích mở rộng” đưa ra các thuật toán theo tiếp cận trên không gian ảnh để giải hai bài toán quy hoạch tích: Bài toán quy hoạch tích lồi suy rộng (GMP) và Bài toán quy hoạch tích lõm mở rộng (GIMP). Thuật toán giải bài toán (GMP) được giới thiệu trong Mục 3.1. Thuật toán này được thiết lập dựa trên mối quan hệ của bài toán quy hoạch tích lồi suy rộng (GMP) và bài toán quy hoạch đa mục tiêu (GMOP) tương ứng. Đây cũng được xem như là một ứng dụng của thuật toán giải bài toán (GMOP) đã thiết lập ở Chương 2. Mục 3.2 dành để trình bày thuật toán giải bài toán (GIMP). Bằng các biến đổi thích hợp, việc giải bài toán này được đưa về việc giải bài toán cực đại một hàm đơn điệu tăng trên tập các điểm hữu hiệu của một tập lồi đóng trong R2 . Các tính toán thử nghiệm chứng tỏ tính hiệu quả của thuật toán đề xuất. Chương 4. “Thuật toán giải bài toán tối ưu trên tập nghiệm hữu hiệu” đề xuất các thuật toán trên không gian ảnh để giải hai bài toán (QP) và (DP) nhằm tối ưu một hàm hợp trên tập nghiệm hữu hiệu của bài toán quy hoạch hai mục tiêu lồi, tức bài toán (CMOP) với p = 2. Bằng cách biến đổi các bài toán gốc về bài toán tương đương trên không gian ảnh và tận dụng cấu trúc đặc biệt của tập ảnh hữu hiệu và tính chất đặc thù của các hàm mục tiêu, Mục 4.1 đề xuất một thuật toán nhánh cận giải bài toán (QP) và Mục 4.2 đưa ra một thuật toán nhánh cận kết hợp với lược đồ xấp xỉ ngoài giải bài toán (DP). xv