Phương pháp nón pháp tuyến giải bài toán tối ưu hóa đa mục tiêu và bài toán quy hoạch tích Phương pháp nón pháp tuyến giải bài toán tối ưu hóa đa mục tiêu và bài toán quy hoạch tích Phương pháp nón pháp tuyến giải bài toán tối ưu hóa đa mục tiêu và bài toán quy hoạch tích luận văn tốt nghiệp,luận văn thạc sĩ, luận văn cao học, luận văn đại học, luận án tiến sĩ, đồ án tốt nghiệp luận văn tốt nghiệp,luận văn thạc sĩ, luận văn cao học, luận văn đại học, luận án tiến sĩ, đồ án tốt nghiệp
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - - - - - - - - - - -o0o- - - - - - - - - - - ĐỖ XUÂN HƯNG PHƯƠNG PHÁP NÓN PHÁP TUYẾN GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ BÀI TỐN QUI HOẠCH TÍCH LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: TOÁN TIN Hà Nội - 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - - - - - - - - - - -o0o- - - - - - - - - - - ĐỖ XUÂN HƯNG PHƯƠNG PHÁP NÓN PHÁP TUYẾN GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ BÀI TỐN QUI HOẠCH TÍCH Chun ngành: Tốn Tin LUẬN VĂN THẠC SĨ KHOA HỌC NGÀNH: TOÁN TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS TS NGUYỄN THỊ BẠCH KIM Hà Nội - 2013 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 ix Nón pháp tuyến tập lồi 1.1 Nón pháp tuyến tập lồi 1.1.1 Định nghĩa 1.1.2 Mối quan hệ nón pháp tuyến tập lồi đa diện 1.2 Điểm hữu hiệu điểm hữu hiệu yếu tập 15 1.2.1 Định nghĩa 15 1.2.2 Điều kiện hữu hiệu theo nón pháp tuyến 19 Bài toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính 21 2.1 Bài toán qui hoạch lồi đa mục tiêu 22 2.2 Thuật tốn nón pháp tuyến giải tốn qui hoạch tuyến tính đa mục tiêu 29 2.2.1 29 Cơ sở lý thuyết thuật toán i 2.2.2 Thuật toán 34 2.2.3 Ví dụ minh họa 42 Bài tốn qui hoạch tích hàm tuyến tính tập lồi 46 3.1 Giới thiệu tốn 47 3.2 Cơ sở lý thuyết thuật toán giải toán (MP Y ) 50 3.3 Thuật toán giải toán (MP Y ) 58 Tài liệu tham khảo 71 Phụ lục 76 ii Lời cảm ơn Đầu tiên, 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, bảo để luận văn hoàn thành, giúp tăng trưởng niềm đam mê nghiên cứu khoa học Tôi xin chân thành cảm ơn Viện Toán ứng dụng Tin học, 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 q trình học tập nghiên cứu trường Tơi xin cảm ơn dạy dỗ, bảo quan tâm thầy Viện Tốn ứng dụng Tin học suốt thời gian theo học nghiên cứu Tôi xin chân thành cảm ơn Phịng Giải tích số Tính tốn khoa học, Viện Tốn học, nơi tơi cơng tác, tạo điều kiện thuận lợi cho tơi có hội học tập Tôi xin chân thành cảm ơn ThS Trần Ngọc Thăng việc hợp tác nghiên cứu trao đổi hữu ích giúp cho luận văn hồn thiện Cuối cùng, muốn gửi lời cảm ơn chân thành tới gia đình bạn bè đồng nghiệp, người ln động viên khích lệ giúp tơi hồn thành luận văn Xin chân thành cảm ơn Học viên: Đỗ Xuân Hưng Lớp: 11BTT-KH iii Lời mở đầu Bài toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính, kí hiệu (MOP ), toán tối ưu đồng thời p ≥ hàm mục tiêu tuyến tính fj (x) = cj , x , cj ∈ Rn , i = 1, , p, tập lồi đóng khác rỗng X ⊂ Rn Mơ hình tốn học tốn Min Cx với điều kiện x ∈ X, (MOP ) C ma trận cấp p × n với hàng c1 , , cp Trường hợp đặc biệt, tập chấp nhận X tập lồi đa diện, toán (MOP ) trở thành tốn qui hoạch tuyến tính đa mục tiêu kí hiệu (MOLP ) Đây trường hợp đơn giản tối ưu đa mục tiêu Như biết, tập nghiệm hữu hiệu XE tập nghiệm hữu hiệu yếu XW E tốn qui hoạch tuyến tính đa mục tiêu (MOLP ) tập liên thông đường gấp khúc, bao gồm số hữu hạn diện đóng tập chấp nhận X, nói chung, chúng tập khơng lồi có cấu trúc phức tạp Bài tốn qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính có ý nghĩa ứng dụng quan trọng thực tế đặc biệt lý thuyết định, kinh tế, quản lý, cơng nghiệp, tài Vì vậy, dành quan tâm nghiên cứu nhiều nhà toán học, chẳng hạn xem [3-4], [8], [15] danh mục tài liệu tham khảo kèm theo iv Một tốn tối ưu tồn cục nảy sinh nhiều lĩnh vực thực tế khác kinh tế, tài chính, thiết kế chip điện tử liên quan gần gũi với toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính tốn qui hoạch tích hàm tuyến tính tập lồi, kí hiệu (MP X) Đó tốn cực tiểu hàm mục tiêu tích p ≥ hàm tuyến tính fj (x) = cj , x , cj ∈ Rn , i = 1, , p, tập lồi X khác rỗng Rn Cho đến nay, có nhiều thuật tốn đưa để giải toán này, chẳng hạn xem [5-7], [12], [14-16], [21], [22], [26] danh mục tham khảo kèm theo Mục đích luận văn nghiên cứu tốn qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính tốn qui hoạch tích hàm tuyến tính tập lồi Do nhu cầu ứng dụng, việc nghiên cứu để đề xuất thuật toán giải hai tốn ln vấn đề có ý nghĩa khoa học tính thời Chúng nghiên cứu điều kiện hữu hiệu toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính thơng qua nón pháp tuyến tập lồi chấp nhận giới thiệu thuật toán nón pháp tuyến [15] N.T.B Kim Đ.T Lục đề xuất năm 2000 để giải toán qui hoạch tuyến tính đa mục tiêu Chương Chương đề xuất thuật tốn khơng gian ảnh để giải tốn qui hoạch tích hàm tuyến tính tập lồi Kết báo cáo Hội thảo Tối ưu Tính tốn khoa học lần thứ 11, tổ chức Ba Vì, ngày 24 - 27/04/2013 v Nội dung Luận văn trình bày ba chương Cụ thể: Chương 1: Nón pháp tuyến tập lồi Chương dành để nghiên cứu nón pháp tuyến tập lồi điều kiện nhận biết điểm hữu hiệu, hữu hiệu yếu tập lồi thơng qua nón pháp tuyến Như biết, cơng thức tường minh để tính nón pháp tuyến tập lồi đa diện biết đến, chẳng hạn xem [15] [24] Chúng tơi khơng tìm cơng thức tính nón pháp tuyến tập lồi tài liệu Ở đây, công thức đưa Mệnh đề 1.1 Đây sở để chứng minh điều kiện hữu hiệu toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính đề xuất Chương (Mệnh đề 2.2) Chương 2: Bài toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính Mục đích chương là: i) Nghiên cứu toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính đưa điều kiện nhận biết nghiệm hữu hiệu nghiệm hữu hiệu yếu tốn thơng qua nón pháp tuyến tập lồi chấp nhận được; ii) Giới thiệu thuật tốn nón pháp tuyến [15] N.T.B Kim Đ.T Lục đề xuất năm 2000 để xác định toàn tập nghiệm hữu hiệu tốn qui hoạch tuyến tính đa mục tiêu Như biết, biết toàn tập đỉnh hữu hiệu tốn qui hoạch tuyến tính đa mục tiêu việc giải tốn qui hoạch tích hàm tuyến tính tập lồi đa diện tương ứng với (trường hợp đặc biệt tốn (MP X)) đơn giản việc so sánh giá trị hàm mục tiêu đỉnh hữu hiệu (Nhận vi xét 3.2) Tuy nhiên, cấu trúc phức tạp tập nghiệm hữu hiệu toán (MOLP ) nên khối lượng tính tốn để xác định tồn tập đỉnh hữu hiệu toán tăng nhanh kích thước tốn (tức số biến n, số hàm mục tiêu p, số ràng buộc tập lồi đa diện chấp nhận được) tăng Chương 3: Bài toán qui hoạch tích hàm tuyến tính tập lồi Trong chương này, chúng tơi nghiên cứu tốn qui hoạch tích hàm tuyến tính tập lồi (MP X) đề xuất thuật toán với kỹ thuật xấp xỉ ngồi để giải tốn khơng gian ảnh (MP Y ) tương ứng với Thuật tốn xây dựng dựa vào mối quan hệ nghiệm tối ưu toán (MP Y ) điểm hữu hiệu tập ảnh Y = C(X), C ma trận cấp p × n với hàng c1 , , cp Khi thuật toán kết thúc, ta nhận nghiệm tối ưu hai toán (MP X) (MP Y ) Do p ≪ n nên thuật tốn cho phép tiết kiệm thời gian khối lượng tính tốn Thuật toán chứng minh hội tụ (Mệnh đề 3.10) lập trình tính tốn thử nghiệm Kết tính tốn chứng tỏ tính hữu hiệu thuật toán Phụ lục Luận án giới thiệu chương trình giải tốn (MP X) Chương trình viết ngơn ngữ lập trình MATLAB R2009a chạy mơi trường Win vii Luận văn hồn thành Viện Toán ứng dụng Tin học, 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 khơng tránh khỏi thiếu sót Rất mong nhận góp ý thầy bạn Xin chân thành cảm ơn Hà Nội, ngày 26 tháng 05 năm 2013 viii Các hàm ràng buộc gi(x) nhập vào file funof.m Hình 3.2: Các hàm ràng buộc Hàm funof(x) trả giá trị véc tơ g = (g1 (x), , gm(x))T 78 Hàm mục tiêu toán α v.đ.k.αv k + (1 − α)y M ≥ Cx x ∈ X, ≤ α ≤ lưu file funalpha.m Hình 3.3: Hàm mục tiêu toán (P (v k )) 79 (P (v k )) Các gradient fˆ g nhập vào file gradfun.m gradfunof.m Hình 3.4: Gradient fˆ Hình 3.5: Gradient g 80 Chạy chương trình Hình 3.6: Màn hình chương trình Lấy kết Hình 3.7: Kết 81 Chạy thử ví dụ Ví dụ Giải toán f (x) = f1(x)f2(x), v.đ.k x ∈ X, f1 (x) = e1 , x , f2(x) = e2 , x , e1 = (1, 0)T , e2 = (0, 1)T ; X = {x ∈ R2 : (x1 − 3)2 + (x2 − 3)2 − ≤ 0} Ở ǫ = 0, 01 Kết quả: xopt = (1.5858, 1.5858)T , fopt = 2.5147 Ví dụ Giải tốn f (x) = f1(x)f2(x), v.đ.k x ∈ X, f1 (x) = e1 , x , f2(x) = e2 , x , e1 = (1, 0)T , e2 = (0, 1)T ; X ⊂ R2 tập nghiệm hệ (x1 − 5)2 + (x2 − 5)2 − ≤ 0, (x1 − 2)2 + (x2 − 2)2 − ≤ Ở ǫ = 0, 05 Kết quả: xopt = (2.8787, 2.8787)T , fopt = 8.2868 82 Ví dụ Giải toán f (x) = f1(x)f2(x), v.đ.k x ∈ X, f1 (x) = e1 , x , f2(x) = e2 , x , e1 = (1, 0)T , e2 = (0, 1)T ; X tập nghiệm hệ −x1 − ≤ −x2 − ≤ −x1 − x2 + ≤ x + x − 10 ≤ Ở ǫ = 0, 01 Kết quả: xopt = (4, 1)T , fopt = 83 ... qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính 21 2.1 Bài toán qui hoạch lồi đa mục tiêu 22 2.2 Thuật tốn nón pháp tuyến giải tốn qui hoạch tuyến tính đa mục tiêu ... toàn tập nghiệm hữu hiệu tốn qui hoạch tuyến tính đa mục tiêu (MOLP ) 21 2.1 Bài toán qui hoạch lồi đa mục tiêu Xét toán qui hoạch lồi đa mục tiêu với hàm mục tiêu tuyến tính Min Cx, v.đ.k x ∈ X,...huật tốn nón pháp tuyến [15] N.T B Kim Đ.T Lục đề xuất năm 2000 giải toán qui hoạch tuyến tính đa mục tiêu dựa phương pháp nón pháp tuyến 45 Chương Bài tốn qui hoạch tích hàm tuyến tính tập l