Luận văn Thạc sĩ Toán học: Thuật toán giải một số bài toán tối ưu phân thức tuyến tính và phi tuyến

Luận văn nhằm tìm hiểu và trình bày một số thuật toán mới gần đây, nêu ở các tài liệu tham khảo, giải quy hoạch phân tuyến tính (nhờ đưa về quy hoạch tuyến tính) và giải quy hoạch phân thức phi tuyến (theo tiếp cận tham số). 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 một số bài toán tối ưu phân thức tuyến tính và phi tuyến ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- LÊ ĐÌNH THẢNTHUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU PHÂN THỨC TUYẾN TÍNH VÀ PHI TUYẾN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- LÊ ĐÌNH THẢNTHUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU PHÂN THỨC TUYẾN TÍNH VÀ PHI TUYẾN Chuyên ngành: Toán ứng dụng Mã số : 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. Trần Vũ Thiệu THÁI NGUYÊN - 2018 iiiMục lụcDanh mục các ký hiệu 1Danh mục các hình vẽ 3 Mở đầu 41 KIẾN THỨC CHUẨN BỊ 7 1.1. HÀM PHÂN THỨC AFIN . . . . . . . . . . . . . . . . . . 7 1.2. BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH . . . . . 9 1.3. CÁCH TIẾP CẬN CHARNES - COOPER . . . . . . . . . 11 1.4. PHƯƠNG PHÁP GIẢI CỔ ĐIỂN . . . . . . . . . . . . . . 142 THUẬT TOÁN CẢI TIẾN GIẢI QUY HOẠCH PHÂN TUYẾN TÍNH 18 2.1. PHƯƠNG PHÁP ĐƯA VỀ MỘT BÀI TOÁN (LP) . . . . 18 2.1.1. Biến đổi (LFP) về bài toán tuyến tính (LP) . . . . 18 2.1.2. Thuật toán . . . . . . . . . . . . . . . . . . . . . . 20 2.1.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 20 2.2. PHƯƠNG PHÁP ĐƯA VỀ HAI BÀI TOÁN (LP) . . . . . 25 2.2.1. Cơ sở của phương pháp . . . . . . . . . . . . . . . . 26 2.2.2. Phương pháp hạn chế hàm mục tiêu ở mẫu số . . . 27 2.2.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . 28 2.2.4. Bài toán cực tiểu . . . . . . . . . . . . . . . . . . . 293 TIẾP CẬN THAM SỐ GIẢI QUY HOẠCH PHÂN THỨC PHI TUYẾN 32 iv 3.1. THUẬT TOÁN DINKELBACH . . . . . . . . . . . . . . . 32 3.1.1. Ký hiệu và kết quả chuẩn bị . . . . . . . . . . . . . 32 3.1.2. Sự hội tụ toàn cục của thuật toán . . . . . . . . . . 34 3.2. THUẬT TOÁN DINKELBACH RÚT GỌN . . . . . . . . 36 3.3. ÁP DỤNG GIẢI QUY HOẠCH PHÂN TUYẾN TÍNH . . 39 Kết luận 44Tài liệu tham khảo 45 1DANH MỤC CÁC KÝ HIỆUR Tập các số thựcRn Không gian véctơ n chiềuRn+ Tập các véctơ không âm trong RnT Ký hiệu chuyển vị véctơ hay ma trậnkxk Chuẩn Euclid của véctơ x ∈ Rn|x| Giá trị tuyệt đối của x ∈ R{xk }, {xk } Dãy điểm trong Rnhx, yi Tích vô hướng của hai vectơ x và y[x, y] Đoạn thẳng nối x và y trong Rnx≤y Véctơ x nhỏ hơn hay bằng véctơ y, (xi ≤ yi , ∀i = 1, ... , n)x≥y Véctơ x lớn hơn hay bằng véctơ y, (xi ≥ yi , ∀i = 1, ... , n)x∈X x là một phần tử của tập Xx∈ /X x không là phần tử của tập Xint X Phần trong của tập XC Bao đóng của tập C∅ Tập hợp rỗngA+B Tổng véctơ của hai tập A và BA∪B Hợp của hai tập A và BA∩B Giao của hai tập A và BA×B Tích Đề các của hai tập A và B 2A⊂B A là tập con của B (mọi phần tử của A là phần tử của BA⊆B A là tập con (có thể bằng) của BS ⊆ Rn Tập lồi đa diện trong Rn 3DANH MỤC CÁC HÌNH VẼChương 1: - Hình 1.1. Tập ràng buộc S của bài toán ở Ví dụ 1.1 - Hình 1.2. Tập ràng buộc S của bài toán ở Ví dụ 1.2Chương 2: - Hình 2.1. Tập ràng buộc S của bài toán ở Ví dụ 2.1 - Hình 2.2. Tập ràng buộc S của bài toán ở Ví dụ 2.2 - Hình 2.3. Tập ràng buộc S của bài toán ở Ví dụ 2.6Chương 3: - Hình 3.1. Sơ đồ khối thuật toán Dinkelbach 4MỞ ĐẦU Quy hoạch phân tuyến tính (Linear Fractional Programming, viếttắt LFP), rộng hơn là quy hoạch phân thức phi tuyến, là một mở rộngtrực tiếp của quy hoạch tuyến tính (Linear Programming, viết tắt LP),với đối tượng nghiên cứu là các bài toán tìm cực tiểu (cực đại) một hàmphân tuyến tính (tỉ số hai hàm tuyến tính afin), trên một tập ràng buộcđược xác định bởi các đẳng thức hay bất đẳng thức tuyến tính. Các bài toán quy hoạch phân tuyến tính thường dùng để mô tảtoán học cho nhiều bài toán thực tế với các hàm mục tiêu phân thức,chẳng hạn: lợi nhuận/chi phí, sản phẩm/số lao động, v.v ... và được ứngdụ ...