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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

35
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ẢN 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 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ẢN 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 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
iii Mục lục Danh mục các ký hiệu 1 Danh mục các hình vẽ 3 Mở đầu 4 1 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 . . . . . . . . . . . . . . 14 2 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 . . . . . . . . . . . . . . . . . . . 29 3 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 44 Tài liệu tham khảo 45
1 DANH MỤC CÁC KÝ HIỆU R Tập các số thực Rn Không gian véctơ n chiều Rn+ Tập các véctơ không âm trong Rn T Ký hiệu chuyển vị véctơ hay ma trận kxk 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 Rn hx, 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 Rn x≤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 X x∈ /X x không là phần tử của tập X int X Phần trong của tập X C Bao đóng của tập C ∅ Tập hợp rỗng A+B Tổng véctơ của hai tập A và B A∪B Hợp của hai tập A và B A∩B Giao của hai tập A và B A×B Tích Đề các của hai tập A và B
2 A⊂B A là tập con của B (mọi phần tử của A là phần tử của B A⊆B A là tập con (có thể bằng) của B S ⊆ Rn Tập lồi đa diện trong Rn
3 DANH 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.2 Chươ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.6 Chương 3: - Hình 3.1. Sơ đồ khối thuật toán Dinkelbach
4 MỞ ĐẦU Quy hoạch phân tuyến tính (Linear Fractional Programming, viết tắt LFP), rộng hơn là quy hoạch phân thức phi tuyến, là một mở rộng trự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àm phâ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 ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của kinh tế, tài chính, kỹ thuật, v.v... Quy hoạch phân tuyến tính có nhiều điểm tương đồng với quy hoạch tuyến tính, cả về lý thuyết lẫn phương pháp giải. Trong một số trường hợp riêng, bài toán quy hoạch phân tuyến tính trở thành bài toán quy hoạch tuyến tính và do đó có thể giải theo thuật toán đơn hình quen thuộc của quy hoạch tuyến tính. Trong trường hợp tổng quát, nhiều tác giả cũng đã tìm cách đưa việc giải quy hoạch phân tuyến tính về giải một hay nhiều bài toán quy hoạch tuyến tính. Luận văn với đề tài "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" 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 [5] - [7], 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ố).
5 Nội dung luận văn được trình bày trong ba chương. Chương 1. "Kiến thức chuẩn bị" nhắc lại về hàm phân thức afin và tính chất, bài toán quy hoạch phân tuyến tính, mối liên hệ giữa quy hoạch phân tuyến tính với quy hoạch tuyến tính và cuối chương giới thiệu phương pháp tiêu biểu dựa trên thuật toán đơn hình để giải quy hoạch phân tuyến tính. Chương 2. "Thuật toán cải tiến giải quy hoạch phân tuyến tính" trình bày thuật toán cải tiến của M. B. Hasan và S. Acharjee nêu ở [5] giải bài toán quy hoạch phân tuyến tính (LFP) bằng cách đưa về một bài toán quy hoạch tuyến tính (LP) và thuật toán của P. Pandian và M. Jayalakshmi nêu ở [7] đưa (LFP) về giải hai bài toán (LP). Chương 3. "Tiếp cận tham số giải quy hoạch phân thức phi tuyến" trình bày các kết quả nghiên cứu của A. Jeflea nêu ở [6] về tiếp cận tham số giải bài toán phân thức phi tuyến: Thuật toán Dinkelbach, thuật toán Dinkelbach rút gọn cho phép giải gần đúng các bài toán tham số và sự hội tụ của các thuật toán. Áp dụng cách tiếp cận tham số giải bài toán phân thức tuyến tính (LFP). Do thời gian có hạn nên luận văn này chủ yếu chỉ dừng lại ở việc tìm hiểu, tập hợp tài liệu, sắp xếp và trình bày các kết quả nghiên cứu đã có theo chủ đề đặt ra. Trong quá trình viết luận văn cũng như trong soạn thảo văn bản chắc chắn không tránh khỏi có những sai sót nhất định. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Trần Vũ Thiệu, người thầy đã định hướng chọn đề tài và tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn quý thầy cô trong Khoa Toán - Tin, Trường Đại học Khoa học, Đại học Thái Nguyên và các GS, PGS, TS của Viện Toán học, Viện Công nghệ thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.
6 Thái Nguyên, ngày 21 tháng 4 năm 2018 Tác giả luận văn Lê Đình Thản
7 Chương 1 KIẾN THỨC CHUẨN BỊ Chương này nhắc lại một số tính chất đáng chú ý của hàm phân thức afin (tỉ số hai hàm tuyến tính afin), giới thiệu bài toán quy hoạch phân tuyến tính và thuật toán giải quy hoạch phân tuyến tính, dựa trên phép biến đổi Charnes - Cooper. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [3] và [4]. 1.1. HÀM PHÂN THỨC AFIN Hàm phân thức afin thường gặp trong các bài toán tối ưu. Hàm này có dạng p(x) pT x + α f (x) = = T q(x) q x+β trong đó p, q ∈ Rn , α, β ∈ R và domf = {x ∈ Rn : q T x + β 6= 0}. Ký hiệu S là tập lồi sao cho q T x + β 6= 0 với mọi x ∈ S. Nếu q(x) có dấu khác nhau trên S, tức là có x, y ∈ S sao cho q T x + β > 0 và q T y + β < 0 thì do hàm q(x) liên tục nên tồn tại z ∈ [x, y], tức z ∈ S sao cho q(z) = 0. Vì thế, không giảm tổng quát, ta có thể giả thiết q(x) > 0 với mọi x ∈ S. Trường hợp q(x) < 0 với mọi x ∈ S thì nhân cả tử số p(x) với mẫu số q(x) của hàm số f (x) với (−1) sẽ có q(x) > 0 với mọi x ∈ S. Định lý sau nêu tính chất đơn điệu theo phương của hàm phân thức afin.
8 p(x) Định lý 1.1 f (x) = là hàm đơn điệu trên mỗi đoạn thẳng nằm q(x) trọn trong tập lồi S = {x : q T x + β > 0}. Chứng minh. Lấy hai điểm tùy ý a, b ∈ S và tính giá trị hàm f tại điểm x bất kỳ trên đoạn thẳng nối a và b, tức là x = λa + (1 − λ)b với 0 ≤ λ ≤ 1. Ta thấy p[λa + (1 − λ)b] λp(a) + (1 − λ)p(b) f (x) = = q[λa + (1 − λ)b] λq(a) + (1 − λ)q(b) Đạo hàm của f theo λ:
df (x) 1
p(a) p(b)
p(a)q(b) − p(b)q(a) = 2 ×
=
dλ q (x)