Tài liệu 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 Tài liệu tham khảo 44 45 1 DANH MỤC CÁC KÝ HIỆU R Rn Tập các số thực Không gian véctơ n chiều Rn+ Tập các véctơ không âm trong Rn T kxk Ký hiệu chuyển vị véctơ hay ma trận Chuẩn Euclid của véctơ x ∈ Rn |x| {xk }, {xk } Giá trị tuyệt đối của x ∈ R Dãy điểm trong Rn hx, yi [x, y] Tích vô hướng của hai vectơ x và 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∈ /X x là một phần tử của tập 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 A∪B Tổng véctơ của hai tập A và B Hợp của hai tập A và B A∩B A×B Giao của hai tập A và B Tích Đề các của hai tập A và B 2 A⊂B A là tập con của B A⊆B (mọi phần tử của A là phần tử củ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) 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}. Định lý 1.1 f (x) = 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 f (x) = p[λa + (1 − λ)b] λp(a) + (1 − λ)p(b) = q[λa + (1 − λ)b] λq(a) + (1 − λ)q(b) Đạo hàm của f theo λ:     p(a)q(b) − p(b)q(a) p(a) p(b) 1 df (x)   = 2 × = dλ q (x)  q(a) q(b)  q 2 (x) Dấu của đạo hàm phụ thuộc dấu của biểu thức [p(a)q(b)−p(b)q(a)]. Vì thế, khi λ thay đổi trong đoạn [0, 1] thì hàm f (x) hoặc tăng hoặc giảm hoặc đồng nhất bằng hằng số trên [a, b].  Ta nhắc lại rằng hàm khả vi f : Rn → R được gọi là giả lồi nếu với mọi x, y ∈ S ta có 5f (x)T (y − x) ≥ 0 kéo theo f (y) ≥ f (x), nghĩa là nếu f (y) < f (x) thì 5f (x)T (y − x) < 0. Hàm f được gọi là giả lõm nếu −f là giả lồi. Định lý sau nêu một tính chất quan trọng khác của hàm phân thức afin. pT x + α và S là tập lồi sao cho q T x+β 6= 0 T q x+β trên S. Khi đó, hàm f (x) vừa giả lồi, vừa giả lõm trên S. Định lý 1.2 Giả sử f (x) = Chứng minh. Ta để ý rằng hoặc q T x + β > 0 với mọi x ∈ S hoặc q T x + β < 0 với mọi x ∈ S, vì nếu trái lại sẽ có a ∈ S, b ∈ S sao cho q T a + β > 0 và q T b + β < 0, do đó sẽ có q T z + β = 0 với z là một tổ hợp lồi của a và b, trái với giả thiết định lý. Trước hết ta chứng minh f giả lồi. Thật vậy, giả sử x, y ∈ S thỏa mãn 5f (x)T (y − x) ≥ 0. Ta cần chỉ rõ f (x) ≥ f (y). Ta có ∇f (x) = (q T x + β)p − (pT x + α)q (q T x + β)2 Do 5f (x)T (y − x) ≥ 0 và do q T x + β > 0 nên 9 0 6 [(q T x + β)p − (pT x + α)q]T (y − x) = (pT y + α)(qT x + β) − (qT y + β)(pT x + α) Vì thế, (pT y+α)(q T x+β) ≥ (q T y+β)(pT x+α). Nhưng do (q T x+β) và (q T y + β) cùng dương hoặc cùng âm nên chia cả hai vế cho (q T x + β)(q T y + β) > 0, ta nhận được pT x + α pT y + α ≥ T , tức là f (y) ≥ f (x). qT y + β q x+β Vì vậy, f giả lồi. Tương tự, có thể chứng minh được rằng, 5f (x)T (y − x) ≤ 0 kéo theo f (y) ≤ f (x). Vì thế, f giả lõm và định lý được chứng minh.  Từ các định lý trên cho thấy hàm phân thức afin f (x) đạt cực tiểu (cực đại) trên tập lồi compac khác rỗng tại một điểm cực biên của tập lồi đó. Nói riêng, f (x) đạt cực tiểu (cực đại) trên đa diện lồi tại một đỉnh của đa diện đó. 1.2. BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH Quy hoạch phân tuyến tính 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 với các ràng buộc đẳng thức hay bất đẳng thức tuyến tính. Sau đây ta xét bài toán quy hoạch phân tuyến tính, ký hiệu (LFP), có dạng: n P (LF P ) : p(x) j=1 f (x) = = P n q(x) p j xj + α → min (hay max) (1.1) qj xj + β j=1 với điều kiện: n X aij xj 6 bi , i = 1, 2, ..., m, (1.2) xj ≤ 0, j = 1, 2, ..., n, (1.3) j=1 10 Kí hiệu A = (aij )m×n , b = (b1 , ..., bm )T và S = {x ∈ Rn : Ax 6 b, x > 0} được gọi là tập chấp nhận được của bài toán. Rõ ràng, S là một tập lồi đa diện. Ta luôn giả thiết rằng q(x) 6= 0, ∀x ∈ S. Từ đó, do q(x) là hàm tuyến tính afin nên ta có thể giả thiết q(x) > 0, ∀x ∈ S, bởi vì nếu có x1 ∈ S với q(x1 ) > 0 và x2 ∈ S với q(x2 ) < 0 thì sẽ tồn tại x3 ∈ [x1 , x2 ] ⊆ S sao cho q(x3 ) = 0, trái với giả thiết q(x) 6= 0, ∀x ∈ S. Trường hợp, q(x) < 0, ∀x ∈ S, ta có thể nhân cả tử số p(x) và mẫu số q(x) của hàm mục tiêu với (- 1) để đưa về trường hợp q(x) > 0, ∀x ∈ S. Hơn nữa, ta giả thiêt m ≤ n và rank A = m. • Có thể giải thích ý nghĩa thực tế của bài toán (LFP) như sau: 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à aij 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à pj và tốn chi phí sản xuất là qj , α 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 quy hoạch phân tuyến tính (LFP) dạng (1.1) - (1.3). Quy hoạch tuyến tính là một trường hợp riêng của quy hoạch phân tuyến tính khi q = 0 và β = 1. Trong [3] phân tích một số trường hợp riêng khác cho phép đưa bài toán quy hoạch phân tuyến tính về bài toán tuyến tính thích hợp. Chẳng hạn, nếu p = 0 và α = 1 thì bài toán quy hoạch phân tuyến tính (1.1) - (1.3) có thể quy về bài toán quy hoạch tuyến tính q(x) + β −→ max (hay min) với điều kiện (1.2) - (1.3). Sau đây là một số khái niệm và định nghĩa cần thiết, tương tự như trong lý thuyết quy hoạch tuyến tính. 11 Trong bài toán (LFP), f (x) gọi là hàm mục tiêu. Tập S gọi là tập ràng buộc hay miền chấp nhận được. Véctơ x ∈ S gọi là một phương án hay nghiệm chấp nhận được, một phương án mà đồng thời là đỉnh của tập ràng buộc S gọi là một phương án cực biên hay nghiệm cơ sở. 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. Ta nói bài toán (1.2) là bất khả thi hay không chấp nhận được nếu tập S = ∅, bài toán gọi là giải được nếu tập S 6= ∅ và hàm f (x) có infimum hữu hạn (đối với bài toán min) trên S. Nếu hàm mục tiêu f (x) không bị chặn dưới trên S thì bài toán được gọi là không bị chặn dưới (infx∈S f (x) = −∞). Với bài toán quy hoạch phân tuyến tính, có thể xảy ra các trường hợp sau: a. Tập ràng buộc S = ∅ (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 S). c. Vô số nghiệm tối ưu hữu hạn (đạt tại một diện bị chặn của S). 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 S). e. Nghiệm tối ưu tiệm cận (f ∗ = infx∈S f (x) > −∞ và @x ∈ S : f (x∗ ) = f ∗ ). f. Không có nghiệm tối ưu (infx∈S f (x) = −∞ - bài toán không bị chặn dưới). 1.3. CÁCH TIẾP CẬN CHARNES - COOPER A. Charnes và W. Cooper (1962) đã chỉ ra rằng bài toán quy hoạch phân tuyến tính với tập ràng buộc khác rỗng có thể đưa được về bài toán quy hoạch tuyến tính, nhờ phép đổi biến số, gọi là biến đổi Charnes - Cooper. Ta nhắc lại, bài toán quy hoạch phân tuyến tính có dạng: pT x + α : Ax 6 b, x > 0}, (LFP) min{f (x) = T q x+β trong đó p, q là các véctơ trong Rn , α, β là các số thực, A là ma trận 12 cấp m × n, b là véctơ trong Rm (p, q, α, β, A, b cho trước), x ∈ Rn là véctơ biến cần tìm. Ký hiệu S = {x ∈ Rn : Ax ≤ b, x ≥ 0}. Ta giả thiết tập S 6= ∅. Nhận xét 1.1 Bài toán sẽ không có nghĩa (không xác định) nếu ∃x0 ∈ S, q T x0 + β = 0. Vì thế, để bài toán được hoàn toàn xác định ta phải có hoặc q T x + β > 0, ∀x ∈ S hoặc q T x + β < 0, ∀x ∈ S. Có thể kiểm tra điều này bằng cách giải quy hoạch tuyến tính qmin := min {q T x + β : x ∈ S} hoặc qmax := max {q T x + β : x ∈ S}. (qmin > 0 ⇒ q T x+β > 0, ∀x ∈ S hoặc qmax < 0 ⇒ q T x+β < 0, ∀x ∈ S). Không giảm tổng quát, từ đây về sau ta luôn giả thiết q T x + β > 0, ∀x ∈ S (Nếu cần, có thể đổi dấu tử số và mẫu số của hàm f (x)). • Phép biến đổi Charnes - Cooper Dùng phép đổi biến số: t= 1 > 0, y = tx ∈ Rn , ∀x ∈ S T q x+β và nhân ràng buộc Ax ≤ b với t > 0, ta đưa bài toán (LFP) về bài toán tuyến tính (LP): min{g(y, t) ≡ pT y + αt : Ay − bt ≤ 0, q T 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. Giữa hai bài toán (LFP) và (LP) có mối quan hệ được nêu ra trong các mệnh đề sau. Mệnh đề 1.1 Với các ký hiệu trên, ta có các kết luận sau đây: a) Nếu x0 là một nghiệm chấp nhận được của (LFP) thì (y 0 , t0 ) là một nghiệm chấp nhận được của (LP) với t0 = 1 , y 0 = x0 t0 và +β qT x g(y 0 , t0 ) = pT y 0 + αt0 = t0 (pT x0 + α) = f (x0 ). 13 b) Nếu (y 0 , t0 ) là nghiệm chấp nhận được của (LP) và t0 > 0 thì y0 x0 = 0 là nghiệm chấp nhận được của (LFP) và t f (x0 ) = t0 (pT x0 + α) = pT y 0 + αt0 = g(y 0 , t0 ). Mệnh đề 1.2 a) Nếu (y ∗ , t∗ ) là nghiệm tối ưu của (LP) và t∗ > 0 thì y∗ ∗ x = ∗ là nghiệm tối ưu của (LFP). t 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. Mệnh đề 1.3 Nếu (LFP) có nghiệm chấp nhận được, (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ó infimum (cận dưới đúng) hữu hạn, nhưng infimum đó 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 S 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. Mệnh đề 1.4 Nếu S 6= ∅ và q T x + β = 0 với mọi x ∈ S thì (LP) không có nghiệm chấp nhận được (bài toán (LP) là bất khả thi). Mối liên hệ rất cơ bản giữa các tập ràng buộc của (LFP) và (LP) được trình bày tóm tắt trong các định lý sau. Định lý 1.3 Các đỉnh của tập lồi đa diện S ≡ {x : Ax ≤ b, x ≥ 0} tương ứng một - một với các đỉnh của tập lồi đa diện T ≡ {(y, t) : Ay − b.t ≤ 0, q T y + βt = 1, y ≥ 0, t ≥ 0} với t > 0. (Ta giả thiết q T x + β > 0, ∀x ∈ S). Định lý 1.4 Các đỉnh của tập lồi đa diện T với t = 0 tương ứng một một với các cạnh vô hạn Γ của tập lồi đa diện S với q T d > 0, trong đó d là véctơ chỉ phương của cạnh Γ. Định lý 1.5 Mỗi cạnh vô hạn của tập lồi đa diện T tương ứng với một cạnh vô hạn Γ của tập lồi đa diện S với q T d = 0, trong đó d là véctơ chỉ phương của cạnh Γ. 14 Các định lý này và cách chứng minh của chúng 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}. 1.4. PHƯƠNG PHÁP GIẢI CỔ ĐIỂN Dựa vào phép biến đổi Charnes - Cooper trình bày ở trên, ta có thể giải bài toán quy hoạch phân tuyến tính (LFP) bằng cách lập và giải bài toán quy hoạch tuyến tính (LP) tương ứng. Kết quả giải (LP) cho ra một trong các trường hợp sau: a) (LP) bất khả thi ⇒ (LFP) không xác định hoặc S = ∅ (Mệnh đề 1.4). b) (LP) có nghiệm tối ưu (y ∗ , t∗ ) với t∗ > 0 ⇒ (LFP) có nghiệm y∗ tối ưu x∗ = ∗ (Phần a) Mệnh đề 1.2). t 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 (Mệnh đề 1.3). d) (LP) không bị chặn dưới ⇒ (LFP) không bị chặn dưới hoặc S = ∅ (Phần b Mệnh đề 1.2). Để minh họa phương pháp giải (LFP) dựa trên phép biến đổi Charnes - Cooper ta xét hai ví dụ sau. Ví dụ 1.1 Giải quy hoạch phân tuyến tính: f (x) = p(x) 3x1 + 6x2 + 6 = −→ min q(x) 2x1 + 5x2 + 5 Với các điều kiện x1 − 3x2 ≤ 2, −x1 + 2x2 ≤ 8, 4x1 + x2 ≥ 4, x1 ≥ 0, x2 ≥ 0. Có thể thấy rằng mẫu số q(x) = 2x1 + 5x2 + 5 > 0 trên toàn miền chấp nhận được của bài toán (do có x1 ≥ 0, x2 ≥ 0). Ta giải bài toán 15 này theo phương pháp Charnes - Cooper. Bài toán quy hoạch tuyến tính tương đương có dạng 3y1 + 6y2 + 6t −→ min với các điều kiện y1 − 3y2 − 2y ≤ 0, −y1 + 2y2 − 8t ≤ 0, 4y1 + y2 − 4t ≥ 0, 2y1 + 5y2 + 5t = 1, y1 ≥ 0, y2 ≥ 0, t ≥ 0. Có thể kiểm tra lại rằng y1 = 0; y2 = 0, 16; t = 0, 04 > 0 là một nghiệm tối ưu của bài toán quy hoạch tuyến tính trên. Do đó theo Mệnh đề 1.2, phương án tối ưu của bài toán quy hoạch phân tuyến tính ban y2 y1 = 0, x2 = = 4 và giá trị nhỏ nhất của hàm mục tiêu đầu là x1 = t t là fmin = 1, 2. Hình 1.1. Tập ràng buộc S của bài toán ở Ví dụ 1.1 Ví dụ 1.2 Bài toán quy hoạch phân tuyến tính có nghiệm tối ưu tiệm cận: −3x1 + 2x2 + 5 −→ min f (x) = x1 + 4x2 + 3 16 Với các điều kiện −2x1 + x2 ≤ 4, x1 + x2 ≥ 2, x1 ≥ 0, x2 ≥ 0. Mẫu số q(x) = x1 + x2 + 4 > 0 trên toàn miền chấp nhận được của bài toán (do có x1 ≥ 0, x2 ≥ 0). Bài toán quy hoạch tuyến tính tương đương có dạng −3y1 + 2y2 + 5t −→ min, với các điều kiện −2y1 + y2 − 4t ≤ 0, y1 + y2 − 2t ≥ 0, y1 + 4y2 + 3t = 1, y1 ≥ 0, y2 ≥ 0, t ≥ 0. Giải bài toán này theo thuật toán đơn hình, ta nhận được nghiệm tối ưu duy nhất y1 = 1; y2 = 0; t = 0. Do đó theo Mệnh đề 1.3, bài toán quy hoạch phân tuyến tính ban đầu có nghiệm tối ưu tiệm cận với inf f (x) = lim f (x1 , 0) = −3. x∈S x1 →∞ Hình 1.2. Tập ràng buộc S của bài toán ở Ví dụ 1.2