Luận văn Thạc sĩ Toán học: Thuật toán giải bài toán phân thức tuyến tính với hệ số khoảng ở hàm mục tiêu

Mục tiêu của luận văn là trình bày về bài toán qui hoạch phân tuyến tính, tính chất nghiệm tối ưu của bài toán, mô hình bài toán qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu và một số thuật toán xử lý mô hình. Đóng góp chính của luận văn là tổng hợp và giới thiệu có chọn lọc hai thuật toán giải bài toán qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Thuật toán giải bài toán phân thức tuyến tính với hệ số khoảng ở hàm mục tiêu ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN THU HẰNG THUẬT TOÁN GIẢI BÀI TOÁNPHÂN THỨC TUYẾN TÍNH VỚI HỆ SỐ KHOẢNG Ở HÀM MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN THU HẰNG THUẬT TOÁN GIẢI BÀI TOÁNPHÂN THỨC TUYẾN TÍNH VỚI HỆ SỐ KHOẢNG Ở HÀM MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số : 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. Trần Vũ Thiệu THÁI NGUYÊN - 2016 iMục lụcDanh mục các hình vẽ iiMở đầu 11 Một số kiến thức chuẩn bị 4 1.1. Bài toán qui hoạch phân tuyến tính . . . . . . . . . . . . . . . . 4 1.2. Tính chất nghiệm của bài toán . . . . . . . . . . . . . . . . . . 8 1.3. Minh họa hình học . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.1. Nghiệm tối ưu duy nhất . . . . . . . . . . . . . . . . . 10 1.3.2. Nhiều nghiệm tối ưu . . . . . . . . . . . . . . . . . . . 11 1.3.3. Nghiệm tối ưu hữu hạn và vô cực . . . . . . . . . . . . 12 1.3.4. Nghiệm tối ưu tiệm cận . . . . . . . . . . . . . . . . . . 13 1.3.5. Bài toán vô nghiệm . . . . . . . . . . . . . . . . . . . . 13 1.4. Biến đổi về bài toán tuyến tính tương đương . . . . . . . . . . . 142 Qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu 18 2.1. Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2. Thuật toán đưa về qui hoạch tuyến tính . . . . . . . . . . . . . . 21 2.3. Thuật toán dùng phép tính khoảng . . . . . . . . . . . . . . . . 25 2.3.1. Phép tính khoảng . . . . . . . . . . . . . . . . . . . . . 25 2.3.2. Qui hoạch phân tuyến tính khoảng . . . . . . . . . . . . 28 2.4. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 31Kết luận 38 iTài liệu tham khảo 39 iiDanh mục các hình vẽHình 1.1. Phân bổ công suất phát sóng tối ưuHình 1.2. Năm tập mức trong R2 với γ1 > 0 > γ2 > γ3 > γ4 .Hình 1.3. Nghiệm tối ưu duy nhất đạt tại x∗Hình 1.4. Nhiều nghiệm tối ưu: xopt ∈ [x∗ , x∗∗ ]Hình 1.5. Nghiệm tối ưu hữu hạn và vô cựcHình 1.6. Nghiệm tối ưu tiệm cận ( f ∗ hữu hạn, không đạt được)Hình 1.7. Bài toán vô nghiệm ( f (x) ց −∞)Hình 1.8. Tập ràng buộc của bài toán ở Ví dụ 1.1Hình 2.1. Tập ràng buộc X của bài toán ở Ví dụ 2.1Hình 2.2. Tập ràng buộc X của bài toán ở Ví dụ 2.2Hình 2.3. Tập ràng buộc X của bài toán ở Ví dụ 2.4 1Lời mở đầuQui hoạch phân tuyến tính (LFP) là bài toán tìm cực tiểu (hay cực đại) của mộthàm phân thức afin (tỉ số hai hàm tuyến tính afin) với các ràng buộc đẳng thứchay bất đẳng thức tuyến tính. Qui hoạch phân tuyến tính là một trường hợp riêng của qui hoạch phân thứcphi tuyến, thường dùng để mô hình hóa các bài toán thực tế với một hay nhiềumục tiêu (chẳng hạn lợi nhuận / chi phí, sản phẩm / số lao động, ...) và được ứngdụng rộng rãi trong nhiều ngành khác nhau của kỹ thuật, kinh tế, tài chính, ... Một trong những bài toán qui hoạch phân thức tuyến tính đang được nhiềungười quan tâm nghiên cứu là bài toán phân thức tuyến tính với hệ số khoảng ởhàm mục tiêu (không cố định như trước). Bài toán này có dạng: p(x) [a1 , b1 ] x1 + . . . + [an , bn ] xn + [a0 , b0 ] f (x) = = → min q(x) [c1 , d1 ] x1 + . . . + [cn , dn ] xn + [c0 , d0 ]với điều kiện Ax < b, x ≥ 0, (A ∈ Rm×n , b ∈ Rm ). Mô hình bài toán này linh hoạt và dễ áp dụng hơn. Có một số tài liệu mới([4], [5] và [6] năm 2012, 2013) đề cập tới các phương pháp giải bài toán này.Đáng chú ý là hai phương pháp nêu ở [4] và [6]. Vì thế chúng tôi chọn đề tài luận văn: Thuật toán giải bài toán phân thức tuyến tính với hệ số khoảng ở hàm mục tiêunhằm mục đích tìm hiểu và trình bày các ý tưởng, phương pháp và thuật toángiải mô hình bài toán nêu trong hai tài liệu tham khảo gần đây [4, 6]. Cả haiphương pháp tuy khác nhau, nhưng đều mở rộng và phát triển thuật toán giảiqui hoạch phân tuyến tính đã có. Vì thế trước hết cần tìm hiểu qua về bài toán 2qui hoạch phân tuyến tính và một số tính chất nghiệm tối ưu của bài toán ...