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

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

Thêm vào BST

Báo xấu

46
lượt xem 4
download

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

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!

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 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ÁN PHÂ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ÁN PHÂ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
i Mục lục Danh mục các hình vẽ ii Mở đầu 1 1 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 . . . . . . . . . . . 14 2 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Kết luận 38
i Tài liệu tham khảo 39
ii Danh mục các hình vẽ Hình 1.1. Phân bổ công suất phát sóng tối ưu Hì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ực Hì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.1 Hình 2.1. Tập ràng buộc X của bài toán ở Ví dụ 2.1 Hình 2.2. Tập ràng buộc X của bài toán ở Ví dụ 2.2 Hình 2.3. Tập ràng buộc X của bài toán ở Ví dụ 2.4
1 Lời mở đầu Qui 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ột hà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ức hay 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ức phi 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ều mục tiêu (chẳng hạn lợi nhuận / chi phí, sản phẩm / số lao động, ...) và được ứng dụ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ều ngườ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êu" nhằ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án giả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ả hai phương pháp tuy khác nhau, nhưng đều mở rộng và phát triển thuật toán giải qui 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
2 qui 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 phân tuyến tính. Sau đó sẽ tìm hiểu và trình bày từng cách tiếp cận riêng ở [4] và [6]. Về đại thể phương pháp [4] nêu cách đưa bài toán ban đầu về một qui hoạch tuyến tính, phương pháp [6] dựa trên phép tính khoảng tìm cách đưa bài toán được xét về bài toán với hàm mục tiêu khoảng. Đây là đề tài mới về qui hoạch phân tuyến tính, đang được nhiều người quan tâm tìm hiểu, nghiên cứu. Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo [1] - [6]. Kết quả cần đạt được: hiểu và 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. Luận văn được viết trong hai chương. Chương 1 "Kiến thức chuẩn bị" đề cập tới bài toán tối ưu với hàm mục tiêu phân tuyến tính và với các ràng buộc tuyến tính. Nêu một số ví dụ thực tế có mô hình toán học là qui hoạch phân tuyến tính (bài toán sản xuất) và qui hoạch phân tuyến tính suy rộng (bài toán tăng trưởng kinh tế Von Neumann và bài toán phân bổ tối ưu công suất phát sóng). Tiếp đó nêu các tính chất nghiệm của bài toán thông qua các minh họa hình học nghiệm tối ưu của bài toán qui hoạch phân tuyến tính. Cuối chương trình bày phép biến đối Charnes - Cooper đưa bài toán qui hoạch phân tuyến tính về bài toán qui hoạch tuyến tính tương đương, mà không cần giả thiết tập ràng buộc của bài toán phân tuyến tính bị chặn. Chương 2 "Qui hoạch phân tuyến tính với hệ số khoảng ở hàm mục tiêu" giới thiệu cách tiếp cận đưa ra trong [4, 6] tìm nghiệm tối ưu cho bài toán qui hoạch phân tuyến tính với các hệ số mục tiêu thay đổi trong một khoảng. Thuật toán giải [4] dùng phép biến đổi Charnes - Cooper và thuật toán giải [6] dựa trên phép tính khoảng. Cuối chương nêu một số ví dụ minh hoạ cho các thuật toán giải đã trình bày. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn GS.TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn.
3 Tác giả cũng xin chân thành cảm ơn các GS, PGS, TS của Khoa Toán-Tin, Trường Đại học Khoa học Thái Nguyên và 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. Thái Nguyên, tháng 5 năm 2016 Học viên Nguyễn Thu Hằng
4 Chương 1 Một số kiến thức chuẩn bị Chương này đề cập tới bài toán tối ưu với hàm mục tiêu phân tuyến tính (tỉ số của hai hàm tuyến tính afin) và với các ràng buộc tuyến tính. Các bài toán như thế gọi là qui hoạch phân tuyến tính. Phần đầu trình bày nội dung và ý nghĩa bài toán, tiếp đó nêu tính chất và minh họa hình học nghiệm tối ưu của bài toán. Cuối chương giới thiệu cách đưa bài toán về qui hoạch tuyến tính tương đương. Nội dung của chương được tham khảo từ các tài liệu [1], [2] và [3]. 1.1. Bài toán qui hoạch phân tuyến tính Một cách tổng quát có thể phát biểu bài toán như sau. Cho tập lồi C ⊆ Rn và các hàm f , g, hi : Rn → R(i = 1, . . . , m). Xét bài toán tối ưu với hàm mục tiêu phân thức (tỉ số của hai hàm số), ký hiệu bài toán (FP): f (x) (FP) inf , x∈X g(x) trong đó X = x ∈ C : hi (x) ≤ 0, i = 1, . . . , m. Ta phân biệt các loại bài toán sau: • Khi f , g và hi là các hàm afin thì (FP) gọi là bài toán qui hoạch phân tuyến tính (Linear Fractional Program). • Khi f và g là các hàm toàn phương và hi là các hàm afin thì (FP) gọi là bài toán qui hoạch phân thức toàn phương (Quadratic Fractional Program).
5 • Khi f ≥ 0 là hàm lồi, g > 0 là hàm lõm và hi là các hàm lồi thì (FP) gọi là bài toán qui hoạch phân thức lồi (Convex Fractional Program). Trong bài toán (FP) chỉ xét một hàm phân thức. Tuy nhiên, trong nhiều ứng dụng ta còn có thể xét nhiều hàm phân thức. Chẳng hạn, • Qui hoạch phân thức suy rộng (Generalized Fractional Program): n f (x) o ∗ i λ = min max (gi > 0 ∀i). x∈X 1≤i≤k gi (x) • Qui hoạch tổng các hàm phân thức (Sum-of-ratios Program): k n f (x) o ∗ i λ = min ∑ (gi > 0 ∀i). x∈X i=1 gi (x) • Qui hoạch phân thức đa mục tiêu (Multi-Objective Fractional Program): n f (x) fk (x) o ∗ 1 λ = min ,..., (gi > 0 ∀i). x∈X g1 (x) gk (x) Luận văn này chủ yếu tập trung xét bài toán qui hoạch phân tuyến tính: p(x) pT x + α (LFP) min f (x) = = : Ax ≤ b, x ≥ 0, (1.1) q(x) qT x + β trong đó p, q ∈ Rn , α , β ∈ R, A ∈ Rm×n , b ∈ Rm . Ký hiệu X = {x ∈ Rn : Ax ≤ 0, x ≥ 0}. Tương tự, có thể xét bài toán tìm cực đại: max{ f (x) : x ∈ X}. Khi cần ta có thể dùng qui ước a/0 = +∞ nếu a > 0 và a/0 = −∞ nếu a ≤ 0. Qui hoạch tuyến tính là một trường hợp riêng của qui hoạch phân tuyến tính khi q = 0 và β = 1. Trong [2] phân tích một số trường hợp riêng khác cho phép đưa bài toán qui hoạch phân tuyến tính về bài toán tuyến tính thích hợp.
6 • Để tiện giải thích ý nghĩa thực tiễn của mô hình qui hoạch phân tuyến tính và qui hoạch phân tuyến tính suy rộng ta xét bài toán tìm cực đại. a) Bài toán sản xuất. Giả sử một xí nghiệp có thể dùng m loại vật tư hiện có để sản xuất ra n loại sản phẩm. Gọi bi là lượng vật tư i (i = 1, . . . , m) mà xí nghiệp có và ai j là định mức tiêu hao vật tư i để sản xuất một đơn vị sản phẩm j ( j = 1, . . . , n). Mỗi đơn vị sản phẩm j sản xuất ra sẽ cho lợi nhuận là p j và tốn chi phí sản xuất là q j , α là lợi nhuận cố định thu được và β là chi phí cố định cần bỏ ra (α , β không phụ thuộc số lượng sản phẩm sản xuất). Hỏi với số vật tư đã có xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm mỗi loại sao cho hiệu quả sản xuất của xí nghiệp (đo bằng tỉ số giữa tổng lợi nhuận thu được trên tổng chi phi sản xuất) là lớn nhất? Bài toán này dẫn đến mô hình qui hoạch phân tuyến tính. b) Bài toán tăng trưởng kinh tế Von Neumann. Xét mô hình tăng trưởng kinh tế đơn giản với n ngành, sản xuất và tiêu dùng m loại hàng. Ký hiệu: • xi(t) là cường độ hoạt động của ngành i ở năm t (biến cần tìm); • a x(t) là lượng hàng i tiêu dùng ở năm t cho mọi ngành; • b x(t) là lượng hàng i do mọi ngành sản xuất ra ở năm t. Tốc độ tăng trưởng của ngành i đo bằng tỉ số xi (t)/xi (t − 1), i = 1, . . . , n. Tỉ số thấp nhất được dùng làm thước đo tốc độ tăng trưởng năm t của nền kinh tế. Bài toán đặt ra là các ngành hoạt động sao cho cả nền kinh tế đạt tốc độ tăng trưởng lớn nhất? Bài toán này dẫn đến mô hình qui hoạch phân tuyến tính suy rộng: xi(t) ˜ max{ f (x) = min : Ax(t) ≤ Bx(t − 1), x(t) ≥ 1}, 1≤i≤n t − 1 trong đó x(t) = (x1 (t), . . . , xn (t))T . c) Phân bổ tối ưu công suất phát sóng.
b b b 7 trạm phát k b máy thu (i,j) b b trạm phát i b b Hình 1.1. Phân bổ công suất phát sóng tối ưu b b Giả sử • có m trạm phát âm (k = 1, . . . , m) và m × n máy thu, tất cả cùng một tần số. • trạm phát i muốn truyền tín hiệu tới n máy thu, đánh số (i, j), j = 1, . . . , n. • ai jk là lợi thế về đường đi từ trạm phát k tới máy thu (i, j). • ni j là mức độ ồn nội tại (tạp âm) của máy thu (i, j). • các biến số: công suất phát sóng pk , k = 1, . . . , m. Ở máy thu (i, j) có các thông số: • cường độ tín hiệu thu: si j = ai ji pi . • cường độ nhiễu và ồn: fi j = ∑k6=i ai jk pk + ni j . • tỉ số cường độ tín hiệu thu trên cường độ nhiễu và ồn: si j / fi j . Các trạm phát k 6= i gây nhiễu đối với các máy thu (i, j). Cần xác định các công suất phát sóng pi (i = 1, . . . , m) sao cho làm cực đại tỉ số si j / fi j nhỏ nhất đối với mọi máy thu (i, j)? Mô hình toán học cho bài toán này như sau. ai ji pi max{min : 0 ≤ pi ≤ pmax , i = 1, . . . , n}. i, j ∑k6=1 ai jk pk + ni j Đây là một bài toán qui hoạch phân tuyến tính suy rộng.
8 1.2. Tính chất nghiệm của bài toán Bây giờ ta trở lại xét bài toán qui hoạch phân tuyến tính (1.1). Để bài toán có nghĩa ta giả thiết mẫu số q(x) ≡ qT x + b 6= 0 ∀x ∈ X = {x : Ax ≤ b, x ≤ 0}. Nếu q(x) có dấu khác nhau trên X, tức là có x1 , x2 ∈ X sao cho qT x1 + β > 0 và qT x2 + β < 0 thì do q(x) liên tục nên tồn tại x ∈ x1 , x2 , tức x ∈ X, sao cho q(x) = 0, trái với giả thiết. Vì thế, không mất tổng quát, ta có thể giả thiết q(x) > 0 với mọi x ∈ X. (Nếu có q(x) < 0 thì nhân cả tử số p(x) và mẫu số q(x) của hàm mục tiêu f (x) với (−1), ta sẽ có q(x) > 0). Hơn nữa, ta giả thiết m ≤ n và rankA = m. Sau đây là một số khái niệm và định nghĩa cần thiết đối với bài toán (LFP), tương tự như trong lý thuyết qui hoạch tuyến tính. Trong bài toán (LFP), f (x) gọi là hàm mục tiêu (objective function). Tập X gọi là tập ràng buộc hay miền chấp nhận được (feasible set). Véctơ x ∈ X gọi là một phương án hay nghiệm chấp nhận được (feasible solution), một phương án mà đồng thời là đỉnh của tập ràng buộc X gọi là một phương án cực biên hay nghiệm cơ sở (basic feasible solution). Phương án đạt giá trị nhỏ nhất của hàm mục tiêu f (x) gọi là một phương án tối ưu hay nghiệm tối ưu (optimal solution). Ta nói bài toán (1.1) là bất khả thi hay không chấp nhận được (infeasible) nếu tập X = ∅, bài toán gọi là giải được (solvable) nếu tập X 6= ∅ và hàm f (x) có cận dưới (đối với bài toán min) hữu hạn trên X. Nếu hàm mục tiêu f (x) không bị chặn dưới trên X thì bài toán được gọi là không bị chặn (unbounded): inf f (x) = −∞. x∈X Ta biết rằng hàm phân tuyến tính f (x) = p(x)/q(x) có tính chất đáng chú ý là f (x) đơn điệu trên mỗi đoạn thẳng nằm trong tập {x : q(x) > 0}, do đó cực tiểu (hay cực đại) của f (x) trên mỗi đoạn thẳng sẽ đạt tại một đầu mút của đoạn thẳng đó. Từ đó, nếu hàm f (x) có cực tiểu (hay cực đại) trên một tập lồi đa diện có đỉnh thì cực tiểu (hay cực đại) đó sẽ đạt được tại một đỉnh của tập đa diện đó. Với bài toán qui hoạch phân tuyến tính, có thể xảy ra các trường hợp sau:
9 a. Tập ràng buộc X = ∅ (bài toán bất khả thi). b. Nghiệm tối ưu duy nhất (đạt tại một đỉnh của X). c. Vô số nghiệm tối ưu hữu hạn (đạt tại một diện bị chặn của X). d. Có nghiệm tối ưu hữu hạn và vô cực (đạt tại một diện vô hạn của X). e. Nghiệm tối ưu tiệm cận ( f ∗ = infx∈X f (x) > −∞ và ∄x∗ ∈ X : f (x∗ ) = f ∗ ). f. Không có nghiệm tối ưu (infx∈X f (x) = −∞ - bài toán không bị chặn). 1.3. Minh họa hình học Ta nhắc lại bài toán (LFP): Tìm x ∈ Rn , f ∗ ∈ R sao cho ∗ p(x) pT x + α f = min{ f (x) = = : Ax ≤ b, x ≥ 0}. q(x) qT x + β Ký hiệu X = {x ∈ Rn : Ax ≤ b, x ≥ 0}. Giả thiết ∅ 6= X ⊆ {x : qT x + β > 0}. Như đã nhận xét: cực tiểu (nếu có) của hàm phân tuyến tính f (x) = p(x)/q(x) trên tập lồi đa diện X đạt được tại một trong các đỉnh của X. Để tiện cho việc giải thích các nghiệm tối ưu của bài toán, ta thêm biến mới γ ∈ R và viết lại (LFP) dưới dạng tương đương sau (các biến γ ∈ R, x ∈ Rn ): min{γ : pT x + β ≤ γ (qT x + β ), Ax ≤ b, x ≥ 0}. Trong bài toán này, hàm mục tiêu là tuyến tính, nhưng các ràng buộc không còn là tuyến tính nữa. Tuy nhiên, dạng bài toán này tiện cho việc minh họa. Các tập mức của hàm mục tiêu của bài toán (LFP) có dạng: Cγ = {x ∈ Rn : qT x + β > 0, (pT x + α )/(qT x + β ) = γ } = {x ∈ Rn : (p − γ q)T x = (γβ − α )}, mức γ ∈ R. Trong R2 , mỗi tập mức Cγ là một đường thẳng đi qua giao điểm F của hai đường thẳng p(x) = 0 và q(x) = 0 (⇒ p(x) − γ q(x) = 0, tức là x ∈ Cγ , ∀γ ∈ R).
10 qT x + β > 0 qT x + β 0 C0 pT x + α < 0 Cγ2 Cγ3 Cγ4 Hình 1.2. Năm tập mức trong R2 với γ1 > 0 > γ2 > γ3 > γ4 . Bài toán qui hoạch phân tuyến tính với X 6= ∅ có thể có các tình huống sau. 1.3.1. Nghiệm tối ưu duy nhất Nghiệm tối ưu duy nhất, đạt tại đỉnh x∗ ∈ X (Hình 1.3 a) và b)).
11 qT x + β = 0 X F b Cf ∗ x∗ p q pT x + α = 0 a) Miền ràng buộc X bị chặn qT x + β = 0 b X p F b b b x∗ pT x + α = 0 q Cf ∗ b) Miền ràng buộc X không bị chặn Hình 1.3. Nghiệm tối ưu duy nhất đạt tại x∗ 1.3.2. Nhiều nghiệm tối ưu Vô số nghiệm tối ưu hữu hạn (đạt được trên một diện bị chặn của X).
b b 12 b qT x + β = 0 X p F b pT x + α = 0 x∗ q x∗∗ C f ∗ Hình 1.4. Nhiều nghiệm tối ưu: xopt ∈ [x∗ , x∗∗ ] 1.3.3. Nghiệm tối ưu hữu hạn và vô cực Nếu tập ràng buộc X không bị chặn và một cạnh vô hạn của X nằm trên đường mức mục tiêu (Hình 1.5) thì bài toán có vô số nghiệm tối ưu, một trong số đó là đỉnh x∗ và các nghiệm tối ưu khác là các điểm còn lại trên cạnh vô hạn đi từ x∗ . Điều đáng chú ý ở đây là trong các nghiệm tối ưu khác x∗ , có một nghiệm b ở vô cực. Vì thế, trong trường hợp này ta nói bài toán có "nghiệm tối ưu hỗn b b hợp" (mixed solutions): nghiệm tối ưu hữu hạn và nghiệm tối ưu vô cực. Trong b b trường hợp này các nghiệm tối ưu đạt được tại một diện vô hạn của X. b qT x + β = 0 b b X p F b pT x + α = 0 b x∗ q Cf ∗ Hình 1.5. Nghiệm tối ưu hữu hạn và vô cực
13 b b b 1.3.4. Nghiệm tối ưu tiệm cận b b b Trường hợp này xảy ra khi f∗ = infx∈X f (x) > −∞ và ∄x∗ ∈ X : f (x∗ ) = f ∗ . qT x + β = 0 b b X p b F b b b pT x + α = 0 q b b Cf ∗ Hình 1.6. Nghiệm tối ưu tiệm cận ( f ∗ hữu hạn, không đạt được) 1.3.5. Bài toán vô nghiệm Xảy ra khi f ∗ = infx∈X f (x) = −∞ (hàm mục tiêu không bị chặn dưới). qT x + β = 0 b b b p F X b pT x + α = 0 q Cγ Hình 1.7. Bài toán vô nghiệm ( f (x) ց −∞)
14 1.4. Biến đổi về bài toán tuyến tính tương đương • Xét bài toán qui hoạch phân tuyến tính (LFP): pT x + α min{ f (x) = T : Ax ≤ b, x ≥ 0}. q x+β Giả thiết tập X = {x : Ax ≤ b, x ≥ 0} 6= ∅ và qT x + β > 0 với mọi x ∈ X. Bài toán qui hoạch phân tuyến tính (LFP) có thể đưa được về bài toán qui hoạch tuyến tính, nhờ dùng phép đổi biến số Charnes - Cooper: 1 t= T > 0, y = t.x ∈ Rn , x ∈ X. q x+β Nhân ràng buộc Ax ≤ b với t > 0, ta đưa (LFP) về bài toán tuyến tính: (LP) min{g(y,t) ≡ pT y + α .t : Ay − bt ≤ 0, qT y + β .t = 1, y ≥ 0, t ≥ 0}. So với (LFP), bài toán (LP) có thêm một biến và một ràng buộc mới. Các nghiệm (tối ưu) của hai bài toán (LP) và (LFP) có những mối liên hệ như sau. Định lý 1.1. Với các ký hiệu trên, ta có các kết luận sau đây: a) Nếu (y0 ,t 0 ) là nghiệm chấp nhận được của (LP) và t 0 > 0 thì x0 = y0 /t 0 là nghiệm chấp nhận được của (LFP) và f (x0 ) = t 0 (pT x0 + α ) = pT y0 + α t 0 = g(y0 ,t 0 ). b) Nếu x0 là một nghiệm chấp nhận được của (LFP) thì (y0 ,t 0 ) là một nghiệm chấp nhận được của (LP) với 1 t0 = T 0 , y0 = x0 .t 0 q x +β và g(y0 ,t 0 ) = pT y0 + α t 0 = t 0 (pT x0 + α ) = f (x0 ). Định lý 1.2.
15 a) Nếu (y∗ ,t ∗ ) là nghiệm tối ưu của (LP) và t ∗ > 0 thì x∗ = y∗ /t ∗ là nghiệm tối ưu của (LFP). b) Giả sử (LFP) chấp nhận được. Khi đó, (LP) không bị chặn dưới khi và chỉ khi (LFP) không bị chặn dưới. Định lý 1.3. Giả sử (LFP) có nghiệm chấp nhận được. Khi đó, (LP) có nghiệm tối ưu và mọi nghiệm tối ưu đều có t = 0 thì giá trị mục tiêu của (LFP) có cận dưới đúng hữu hạn, nhưng cận dưới đó không đạt tới được. Đó là trường hợp (LFP) có nghiệm tối ưu tiệm cận. Trong trường hợp này, có thể tạo ra các nghiệm ε - tối ưu với bất kỳ ε > 0, nghĩa là trong X tồn tại một cạnh vô hạn mà dọc theo cạnh đó giá trị mục tiêu của (LFP) tiến dần về cận dưới đúng nói trên. Định lý 1.4. Nếu X 6= ∅ và qT x + β = 0 với mọi x ∈ X thì (LP) không có nghiệm chấp nhận được (bài toán (LP) là bất khả thi). Các định lý trên cũng áp dụng được vào cặp ràng buộc {x : Ax = b, x ≥ 0} và {(y,t) : Ay − bt = 0, y ≥ 0,t ≥ 0}. • Dựa vào phép biến đổi Charnes - Cooper, ta có thể giải bài toán qui hoạch phân tuyến tính (LFP) bằng cách lập và giải bài toán qui hoạch tuyến tính (LP) tương ứng. Kết quả giải (LP) cho ra một trong các khả năng sau: a) (LP) bất khả thi ⇒ X = ∅ hoặc (LFP) không xác định (Định lý 1.1 và 1.4). b) (LP) có nghiệm tối ưu (y∗ ,t ∗ ) với t ∗ > 0 ⇒ (LFP) có nghiệm tối ưu x∗ = y∗ /t ∗ (Phần a) Định lý 1.2). c) Mọi nghiệm tối ưu (y∗ ,t ∗ ) của (LP) đều có t ∗ = 0 ⇒ (LFP) có nghiệm tối ưu tiệm cận (Định lý 1.3). d) (LP) không bị chặn dưới ⇒ (LFP) không bị chặn dưới hoặc X = ∅ (Phần b) Định lý 1.2). • Để minh họa thuật toán giải (LFP) dựa trên phép biến đổi Charnes - Cooper ta xét ví dụ sau.