Luận văn Thạc sĩ Toán học: Cực đại hàm tuyến tính trên tập hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu

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

Thêm vào BST

Báo xấu

23
lượt xem 4
download

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

Luận văn tìm hiểu và giới thiệu một thuật toán mới, dựa trên quy hoạch song tuyến tính, nêu ở tài liệu tham khảo để giải bài toán tối ưu tuyến tính trên tập điểm hữu hiệ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: Cực đại hàm tuyến tính trên tập hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————o0o————— LÊ NHƯ QUỲNH CỰC ĐẠI HÀM TUYẾN TÍNH TRÊN TẬP HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU TUYẾN TÍNH ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————o0o————— LÊ NHƯ QUỲNH CỰC ĐẠI HÀM TUYẾN TÍNH TRÊN TẬP HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU TUYẾN TÍNH ĐA 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 - 2017
i Mục lục Danh mục các ký hiệu i Danh mục các hình vẽ iii Mở đầu 1 Chương 1. Kiến thức chuẩn bị 4 1.1 Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Bài toán quy hoạch song tuyến tính . . . . . . . . . . . . . . . . . 7 1.3 Bài toán tối ưu tuyến tính đa mục tiêu . . . . . . . . . . . . . . . 15 1.4 Bài toán tối ưu tuyến tính hai cấp . . . . . . . . . . . . . . . . . . 19 Chương 2. Thuật toán giải bài toán cực đại hàm tuyến tính trên tập điểm hữu hiệu 25 2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Cơ sở lý thuyết của thuật toán . . . . . . . . . . . . . . . . . . . 27 2.3 Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . 30 2.4 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Kết luận 40 Tài liệu tham khảo 42 Một số thuật ngữ thường sử dụng 44
i Danh mục các ký hiệu Rn Không gian Euclide n-chiều Rn+ Góc không âm trong Rn Rn++ Góc dương trong Rn e Véc tơ với mọi thành phần bằng 1 (e = (1, . . . , 1) ∈ R p ) 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 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 ∅ Tập hợp rỗng (tập không có phần tử nào) D Ký hiệu tập lồi đa diện F Ký hiệu diện của tập lồi đa diện 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 A là tập hợp con của B A⊆B A là tập hợp con (có thể bằng) của B conv S Bao lồi của tập S ⊂ Rn dim S Thứ nguyên (hay số chiều) của tập S ⊂ Rn ∃x Tồn tại x ∀x Với mọi x (P) Ký hiệu bài toán tối ưu tuyến tính đa mục tiêu (Q) Ký hiệu bài toán cực đại hàm tuyến tính trên tập E P
ii (BP) Ký hiệu bài toán quy hoạch song tuyến tính EP Tập các điểm hữu hiệu của bài toán (P) EdP Tập các diện hữu hiệu của bài toán (P)
iii Danh mục các hình vẽ Chương 1 Hình 1.1. Tập lồi đa diện, đa diện lồi và nón lồi đa diện Chương 2 Hình 2.2. Sơ đồ khối thuật toán giải bài toán (Q) Hình 2.3. Tập chấp nhận được D của bài toán (P)
1 Mở đầu Bài toán tối ưu hóa hàm tuyến tính, trên tập điểm hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu, phục vụ cho nhiều mục đích trong việc đề ra quyết định, liên quan tới nhiều mục tiêu khác nhau. Tuy nhiên, đó thường là một bài toán tối ưu toàn cục không dễ giải, bởi vì miền chấp nhận được của bài toán, trong trường hợp tổng quát, là một tập không lồi. Mặt khác, có thể xem nó như một bài toán tối ưu hai cấp, hiện đang được nhiều người quan tâm nghiên cứu, đặc biệt về mặt phương pháp giải bài toán. Luận văn đề cập tới bài toán tối ưu sau đây: (Q) max{d T x : x ∈ E p } trong đó d ∈ Rn và E P là tập điểm hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu: (P) V max{cT1 x, . . . , cTp x}, c1 , . . . , c p ∈ Rn với điều kiện: Ax = b, x ≥ 0 (A ∈ Rm×n , b ∈ Rm ). Có nhiều thuật toán khác nhau để giải bài toán (Q). Luận văn tìm hiểu và giới thiệu một thuật toán mới, dựa trên quy hoạch song tuyến tính, nêu ở tài liệu tham khảo [5] để giải bài toán tối ưu tuyến tính trên tập điểm hữu hiệ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] - [7] hiện có và gồm hai chương: Chương 1 “Kiến thức chuẩn bị”. Chương này nhắc lại một số kiến thức cơ sở về tập lồi đa diện, bài toán quy hoạch song tuyến tính, bài toán tối ưu tuyến tính đa mục tiêu và bài toán tối ưu hai cấp. Nội dung của chương được tham khảo chủ yếu
2 từ các tài liệu [1] - [4], [7], và bao gồm các tiểu mục sau: 1.1. Tập lồi đa diện và khái niệm có liên quan (xác định diện của tập lồi đa diện qua tập mô tả cực đại của nó). 1.2. Bài toán quy hoạch song tuyến tính: Nội dung bài toán, tính chất nghiệm của bài toán và thuật toán giải. 1.3. Bài toán tuyến tính đa mục tiêu: Nội dung bài toán và tính chất của điểm và diện hữu hiệu. 1.4. Bài toán tối ưu tuyến tính hai cấp: Nội dung bài toán và tính chất (đặc biệt là tính chất tối ưu tuyến tính hai cấp là bài toán NP - khó). Chương 2 “Thuật toán giải bài toán cực đại hàm tuyến tính trên tập điểm hữu hiệu”. Chương này đề cập tới bài toán tối ưu hóa hàm tuyến tính trên tập điểm hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu và trình bày thuật toán song tuyến tính, được nêu ra ở tài liệu tham khảo [5], để giải bài toán. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [5] - [7] và bao gồm các tiểu mục sau: 2.1. Nội dung bài toán: liên hệ với tối ưu toàn cục và tối ưu hai cấp. 2.2. Cơ sở lý thuyết của thuật toán: các định lý đưa bài toán về quy hoạch song tuyến tính. 2.3. Thuật toán và sự hội tụ: các bước của thuật toán và sự hội tụ hữu hạn tới nghiệm tối ưu toàn cục chính xác. 2.4. Ví dụ minh họa: Xét ví dụ số trong R3 . 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 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. 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
3 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 2017 Tác giả luận văn Lê Như Quỳnh
4 Chương 1 Kiến thức chuẩn bị Chương này nhắc lại một số kiến thức cơ bản về tập lồi đa diện, bài toán quy hoạch song tuyến tính, bài toán tối ưu tuyến tính đa mục tiêu và bài toán tối ưu hai cấp. Các kiến thức này sẽ cần đến cho thuật toán trình bày ở chương sau. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1] - [4], [7]. 1.1 Tập lồi đa diện Tập lồi là một khái niệm cơ bản trong lý thuyết tối ưu và tập lồi đa diện là một dạng tập lồi đơn giản và rất hay gặp trong lý thuyết tối ưu tuyến tính. Ta nhắc lại ở đây các khái niệm cơ bản này và các kiến thức liên quan. Định nghĩa 1.1. Tập C ⊆ Rn được gọi là một tập lồi (convex set) nếu với bất kỳ x, y ∈ C và bất kỳ số thực λ ∈ [0, 1] thì phải có λ x + (1 − λ )y ∈ C. Theo định nghĩa này, tập ∅, tập chỉ có một phần tử và Rn là các tập lồi. • Ta để ý tới một số dạng tập lồi đặc biệt sau đây: a) Tập afin là tập chứa trọn đường thẳng đi qua hai điểm bất kỳ thuộc nó. b) Siêu phẳng là tập lồi dạng H = {x ∈ Rn : aT x = α}, a ∈ Rn \ {0}, α ∈ R. c) Các nửa không gian đóng H + = {x ∈ Rn : aT x ≥ α}, H − = {x ∈ Rn : aT x ≤ α}.
5 d) Các nửa không gian mở K + = {x ∈ Rn : aT x > α}, K − = {x ∈ Rn : aT x < α}. Định nghĩa 1.2. Cho E là một tập hợp bất kỳ trong Rn . a) Giao của tất cả các tập afin chứa E gọi là bao afin của E, ký hiệu a f f E. b) Giao của tất cả các tập lồi chứa E gọi là bao lồi của E, ký hiệu convE. Định nghĩa 1.3. a) Thứ nguyên (hay số chiều) của một tập afin M, ký hiệu dim M, là thứ nguyên (số chiều) của không gian con song song với nó. b) Thứ nguyên (hay số chiều) của một tập lồi C, ký hiệu dimC, là thứ nguyên hay số chiều của bao afin a f fC của nó. Định nghĩa 1.4. Tập lồi K ∈ Rn được gọi là một nón lồi nếu K có thêm tính chất λ x ∈ K với mọi x ∈ K và mọi λ > 0. Định nghĩa 1.5. Một tập lồi mà là giao của một số hữu hạn các nửa không gian đóng gọi là một tập lồi đa diện (convex polyhedron set). Một tập lồi đa diện có thể không bị chặn (không giới nội). Một tập lồi đa diện mà đồng thời là một nón lồi (tương ứng với trường hợp b = 0) gọi là một nón lồi đa diện. Một tập lồi đa diện bị chặn còn được gọi là một đa diện lồi (polytop). Các đa giác lồi theo nghĩa thông thường trong R2 là những ví dụ cụ thể về đa diện lồi. Các khái niệm này được minh họa ở Hình 1.1. Hình 1.1: Tập lồi đa diện, đa diện lồi và nón lồi đa diện
6 Trong tối ưu tuyến tính người ta thường hay xét các tập lồi đa diện có dạng: X = {x ∈ Rn : Ax = b, x ≥ 0}, (1.1) trong đó A = (A1 , . . . , An ) với A1 , . . . , An , b ∈ Rm cho trước. Ta tìm hiểu các khái niệm diện, đỉnh và cạnh của tập lồi đa diện. Định nghĩa 1.6. Cho F ⊆ X là một tập con lồi của tập lồi đa diện X. Ta nói F là một diện (face) của X nếu mỗi đoạn thẳng bất kỳ thuộc X có một điểm trong thuộc F thì cả đoạn thẳng ấy phải thuộc F, tức là nếu x, y ∈ X, x 6= y và λ x+(1−λ )y ∈ F với 0 < λ < 1 thì [x, y] ⊆ F. Nếu dim F = 0 thì diện F gọi là một đỉnh (vertex), nếu dim F = 1 thì diện F gọi là một cạnh (edge) của tập đa diện X. Các đỉnh, cạnh, mặt của hình hộp chữ nhật X ⊂ R3 đều là các diện của X. • Để hiểu thuật toán trình bày ở Chương 2, ta cần một số cách nhận biết một diện bất kỳ của một tập lồi đa diện. Có nhiều tính chất đặc trưng khác nhau cho các diện của tập lồi đa diện. Sau đây là đặc trưng do Jorge đưa ra năm 2003. Giả sử J 0 ⊆ J = {1, . . . , n}. Định nghĩa 1.7. Ta nói tập con J 0 ⊆ J là tập mô tả (descriptor set) của diện F ⊆ X (X cho bởi (1.1)) khi và chỉ khi F = F(J 0 ), trong đó F(J 0 ) = {x ∈ X : x j = 0, ∀ j ∈ J 0 }. Có thể chứng minh rằng mọi diện F của X có thể được mô tả (không nhất thiết duy nhất) thông qua tập mô tả của diện đó. Như thường lệ, ta dùng các ký hiệu quen thuộc R+ n n n n = {x ∈ R : x ≥ 0} và R++ = {x ∈ R : x > 0}. Như vậy, có thể thấy 0 F(J 0 ) = {x ∈ Rn : AJ−J xJ−J 0 = b, xJ 0 = 0},
7 0 trong đó AJ−J = {A j , j ∈ J − J 0 }, xJ−J 0 = {x j , j ∈ J − J 0 } và xJ 0 = {x j , j ∈ J 0 }. Dễ kiểm tra lại rằng nói chung tập mô tả càng lớn (nhiều phần tử) thì diện được mô tả càng nhỏ. Một yếu điểm của cách đặc trưng này là một diện bất kỳ có thể có một vài tập mô tả khác nhau gắn với nó. Điều này dẫn tới định nghĩa một khái niệm mới cho phép khắc phục được khó khăn này. Định nghĩa 1.8. Ta nói J 0 ⊆ J là tập mô tả cực đại (maximal descriptor set) nếu và chỉ nếu không tồn tại tập con J” ⊆ J sao cho J” chứa J 0 như tập con thực sự và F(J”) = F(J 0 ). Tầm quan trọng của khái niệm trên là ở chỗ có thể thiết lập tương ứng một-một giữa diện và tập mô tả cực đại của nó, như chỉ ra ở định lý sau. Định lí 1.1. (Jorge, 2003) Mỗi diện khác rỗng F của X tương ứng duy nhất với một tập mô tả cực đại. 1.2 Bài toán quy hoạch song tuyến tính 1.2.1 Nội dung bài toán Quy hoạch song tuyến tính (Bilinear Programming, viết tắt là BP) là sự mở rộng trực tiếp của quy hoạch tuyến tính và có thể xem như một lớp con của quy hoạch toàn phương. Quy hoạch song tuyến tính nghiên cứu các bài toán tìm cực tiểu (hay cực đại) của một hàm song tuyến tính với các ràng buộc tuyến tính. Định nghĩa 1.9. Hàm f(x, y) được gọi là một hàm song tuyến tính (bilinear fun- cyion) nếu nó là hàm tuyến tính khi cố định véctơ x hay véctơ y ở một giá trị cụ thể. Tổng quát, hàm song tuyến tính có dạng: f (x, y) = cT x + yT Qx + d T y, 0 trong đó c, x ∈ Rn , d, y ∈ Rn và Q là ma trận cấp n0 × n.
8 Nhận xét 1.1. Khi n0 = 0 (n = 0) thì f (x, y) trở thành hàm tuyến tính theo biến x (biến y). Còn khi Q = 0 thì f (x, y) là hàm tuyến tính theo cả biến x và biến y. Cũng có thể xem hàm song tuyến tính f (x, y) như một trường hợp riêng của hàm toàn phương theo cả hai biến x và y. Thật vậy, nếu đặt ! ! ! ! 1 0 QT c 0 x C= , p= , q= , và z = , 2 Q 0 0 d y thì hàm toàn phương q(z) = pT z + zT Cz + qT z = cT x + yT Qx + d T y = f (x, y). Ví dụ 1.1. Hàm số f (x, y) = x1 + 2y2 + x1 y1 + 3x1 y2 − 2x2 y1 − 4x2 y2 là một hàm song tuyến tính với n = n0 = 2 và ! ! ! 1 0 1 −2 c= , d= , Q= . 0 2 3 −4 Quy hoạch song tuyến tính có nhiều ứng dụng đa dạng trong lý thuyết trò chơi ma trận có ràng buộc, bài toán bù tuyến tính và bài toán phân việc 3 - chiều Markovian. Nhiều bài toán nguyên 0 - 1 có thể phát biểu như các bài toán song tuyến tính. Bài toán quy hoạch lõm tuyến tính từng khúc và bài toán luồng trên mạng với phụ phí cố định (rất quen thuộc trong quản lý các chuỗi cung ứng) cũng có thể giải nhờ dùng cách diễn đạt song tuyến tính. Gần đây có ứng dụng trong công nghiệp hóa chất, thị giác máy điện toán, quá trình Máccốp, v.v... Có nhiều dạng bài toán quy hoạch song tuyến tính. Luận văn này chú ý tới dạng đơn giản và hay gặp trong nhiều ứng dụng, đó là bài toán quy hoạch song tuyến tính với miền ràng buộc rời nhau (disjoint feasible re-gion), ký hiệu bài toán (BP): (BP) min f (x, y) = cT x + yT Qx + d T y, x∈X,y∈Y
9 trong đó X, Y là các tập lồi đa diện khác rỗng cho trước và độc lập nhau. Thông thường các tập X và Y được cho dưới dạng: X = {x ∈ Rn : Ax ≤ a, x ≥ 0}, Y = {y ∈ Rm : By ≤ b, y ≥ 0}, trong đó A là ma trận cấp m × n, B là ma trận cấp m0 × n0 , Q là ma trận cấp n0 × n và a, b, c, d là các véctơ tương ứng với m, m0 , n, n0 thành phần. Không giảm tổng quát ta có thể giả thiết rằng X và Y khác rỗng và n ≤ n0 . 1.2.2 Bài toán quy hoạch lõm tương đương Ta giả thiết rằng min f (x, y) (1.2) y∈Y tồn tại với mọi x ∈ X và Y có ít nhất một đỉnh (chẳng hạn có giả thiết này nếu Y khác rỗng và bị chặn). Khi đó ta có Định lí 1.2. Bài toán (1.2) có thể diễn đạt như một bài toán cực tiểu hàm lõm tuyến tính từng khúc với ràng buộc tuyến tính. Chứng minh. Ký hiệu Y¨ là tập đỉnh của Y . Từ lý thuyết quy hoạch tuyến tính suy ra rằng nghiệm tối ưu của bài toán (1.2) đạt tại ít nhất một đỉnh của Y . Bài toán (BP) có thể phát biểu lại thành min f (x, y) = min min f (x, y) = min min f (x, y) = min g(x), x∈X, y∈Y x∈X y∈Y x∈X y∈Y¨ x∈X trong đó g(x) = min f (x, y) = min f (x, y). y∈Y¨ y∈Y
10 Như vậy, bài toán (BP) tương đương với bài toán min g(x). (1.3) x∈X Để ý rằng tập Y¨ gồm hữu hạn phần tử và với mỗi y ∈ Y¨ thì f (x, y) là hàm afin theo x, do đó g(x) là hàm lõm tuyến tính từng khúc theo x, nghĩa là (1.3) là bài toán cực tiểu hàm lõm tuyến tính từng khúc với các ràng buộc tuyến tính. Nhận xét 1.2. Nếu bài toán quy hoạch song tuyến tính phát biểu dưới dạng max f (x, y) (1.4) x∈X, y∈Y thì với các giả thiết như trước, bài toán (1.4) tương đương với bài toán max g(x), (1.5) x∈X trong đó g(x) = max f (x, y) = max f (x, y). y∈Y¨ y∈Y là hàm lồi của x. Bài toán cực đại hàm lồi (1.5) tương đương với một bài toán cực tiểu hàm lõm. Hơn nữa, có thể đưa bất kỳ bài toán cực tiểu hàm lõm toàn phương về bài toán quy hoạch song tuyến tính. Nói riêng, xét bài toán tối ưu sau đây: min q(x) = 2cT x + xT Qx, (1.6) x∈X trong đó Q là một ma trận đối xứng, nửa xác định âm. Xây dựng bài toán quy hoạch song tuyến tính như sau: min f (x, y) = cT x + yT Qx + cT y, (1.7) x∈X, y∈Y trong đó Y = X. Ta có
11 Định lí 1.3. Nếu x∗ là một nghiệm tối ưu của bài toán (1.6) thì (x∗ , x∗ ) là một nghiệm tối ưu của bài toán (1.7). Ngược lại, nếu (b x, yb) là một nghiệm tối ưu của bài toán (1.7) thì xb và yb là các nghiệm tối ưu của bài toán (1.6). 1.2.3 Tính chất nghiệm bài toán (BP) Mục trước cho thấy rằng (BP) tương đương với bài toán cực tiểu hàm lõm tuyến tính từng khúc. Mặt khác, ta lại biết rằng cực tiểu của hàm lõm trên một tập lồi đa diện luôn đạt tại một đỉnh. Định lý sau được suy ra từ nhận xét này. Định lí 1.4. Nếu X và Y bị chặn thì tồn tại một nghiệm tối ưu (x∗ , y∗ ) của (BP) sao cho x∗ ∈ X¨ và y∗ ∈ Y¨ , trong đó X, ¨ Y¨ lần lượt là tập đỉnh của X, Y . Giả sử (x∗ , y∗ ) là một nghiệm tối ưu của (BP). Khi cố định x = x∗ , (BP) trở thành bài toán tuyến tính theo biến y và y∗ là một nghiệm tối ưu của bài toán đó. Từ tính đối xứng của bài toán (BP), kết quả tương tự cũng đúng khi cố định y = y∗ . Định lý sau là một điều kiện cần của tối ưu và là hệ quả trực tiếp của những điều bàn luận trên. Định lí 1.5. Nếu (x∗ , y∗ ) là một nghiệm tối ưu của bài toán (BP) thì min f (x, y∗ ) = f (x∗ , y∗ ) = min f (x∗ , y). (1.8) x∈X y∈y Tuy nhiên (1.8) không là điều kiện đủ. Thực ra chỉ có thể đảm bảo (x∗ , y∗ ) là nghiệm tối ưu địa phương nếu có thêm một số điều kiện. Cụ thể, y∗ phải là nghiệm tối ưu duy nhất của bài toán miny∈Y f (x∗ , y). Từ đó suy ra rằng f (x∗ , y∗ ) < f (x∗ , y), ∀y ∈ Y¨ , y 6= y∗ . Do hàm f (x, y) liên tục nên với mọi y ∈ Y¨ , y 6= y∗, f (x∗ , y∗ ) < f (x, y) trong lân cận Uy đủ nhỏ của điểm x∗ . Đặt \ U= Uy . y∈Y¨ , y6=Y ∗ Khi đó f (x∗ , y∗ ) < f (x, y), ∀x ∈ U, y ∈ Y¨ , y 6= y∗ . Cuối cùng, để ý rằng Y là một đa diện lồi và mỗi điểm của Y có thể biểu diễn dưới dạng một tổ hợp lồi của
12 các đỉnh của Y . Từ đó suy ra f (x∗ , y∗ ) ≤ f (x, y), ∀x ∈ U, y ∈ Y , điều này chứng minh cho định lý sau. Định lí 1.6. Nếu (x∗ , y∗ ) thỏa mãn (1.8) và y∗ là nghiệm duy nhất của bài toán miny∈Y f (x∗ , y) thì (x∗ , y∗ ) là nghiệm tối ưu địa phương của (BP). Nhớ rằng (BP) tương đương với bài toán cực tiểu hàm lõm, tuyến tính từng khúc (1.3). Vì thế, với các giả thiết của định lý 1.6 có thể chỉ ra rằng x∗ cũng là cực tiểu địa phương của hàm g(x) trên X. 1.2.4 Thuật toán giải (BP) Như vậy bài toán (BP) tương đương với bài toán quy hoạch lõm: (CP) min{g(x) : x ∈ X}, trong đó g(x) = min f (x, y) = cT x + min(d + Qx)T y, (1.9) y∈Y y∈Y X = {x ∈ Rn : Ai x ≤ ai , , i = 1, . . . , m, x j ≥ 0, j = 1, . . . , n} với Ai là hàng thứ i của ma trận ràng buộc A, ai là tọa độ thứ i của a. Để thuận tiện, ta giả thiết các tập lồi đa diện X và Y khác rỗng (có thể không bị chặn). Để giải (BP) ta giải (CP) theo phương pháp xấp xỉ ngoài. Nội dung thuật toán như sau; Bước 0. Đặt S0 = Rn+ . Giả sử U0 là tập đỉnh và V0 là tập các hướng cực biên của S0 . Rõ ràng, U0 = {0}, V0 = {e1 , . . . , en }, trong đó e j là véctơ đơn vị thứ j trong Rn , ( j = 1, . . . , n). Đặt I0 = ∅ (tập chỉ số ràng buộc xác định S0 ) và k = 0. Vòng lặp k = 0, 1, 2, . . . , m. Ở vòng lặp k ta có tập lồi đa diện Sk sao cho Rn+ ⊃ Sk ⊃ X, cùng với tập đỉnh Uk , tập hướng cực biên Vk của Sk và tập chỉ số Ik các ràng buộc đã thêm vào S0 để xác định Sk . Đặt Jk = {1, . . . , m} \ Ik .
13 Bước 1 (Kiểm tra hàm g(x) bị chặn dưới theo hướng cực biên vk ). Tính γ(vk ) = min{(Qvk )T y : y ∈ Y }, ∀k ∈ Vk . (1.10) Nếu có γ(vk ) < 0 với vk nào đó thuộc Vk thì tính λ = max{Ai vk : i ∈ Jk }. (a) Nếu λ ≤ 0, tức là Ai vk ≤ 0 với mọi i = 1, . . . , m thì dừng: bài toán (CP) không có nghiệm tối ưu hữu hạn và g(x) không bị chặn dưới trên tia bất kỳ trong X song song với vk . Trong trường hợp này, bài toán quy hoạch song tuyến tính (BP) vô nghiệm (không có nghiệm tối ưu hữu hạn). (b) λ > 0, chọn ik ∈ arg max{Ai vk : i ∈ Jk } và chuyển sang Bước 3. Bước 2. Nếu γ(v) ≥ 0 với mọi v ∈ Vk (g(x) bị chặn dưới trên Sk ) thì chọn xk = arg min{g(x) : x ∈ Uk } (với mỗi x ∈ Uk , giá trị g(x) được tính nhờ giải quy hoạch tuyến tính (1.9)). Tính µ = max{Ai xk − ai : i ∈ Jk }. (a) Nếu µ ≤ 0, tức là Ai xk ≤ ai với mọi i = 1, . . . , m thì dừng: xk là nghiệm tối ưu của bài toán (CP). Giải quy hoạch tuyến tính (1.9) với x = xk . Nếu yk là một nghiệm tối ưu của bài toán đó, thì (xk , yk ) là một nghiệm tối ưu của (BP). (b) Nếu µ > 0 thì chọn ik ∈ arg max{Ai xk − ai : i ∈ Jk } và chuyển sang Bước 3.
14 Bước 3. Xây dựng tập lồi đa diện mới và tập chỉ số ràng buộc tương ứng Sk+1 = Sk ∩ {x : Aik x ≤ aik }, Ik+1 = Ik ∪ {ik }. Xác định tập đỉnh Uk+1 và tập phương cực biên Vk+1 của Sk+1 (dùng kỹ thuật sinh đỉnh trong quy hoạch lõm) và chuyển sang vòng lặp k + 1 (trở lại Bước 2 nếu ở vòng lặp trước đó thuật toán đã chạy qua Bước 2, xem Nhận xét 1.4). Vì ở mỗi vòng lặp tập lồi đa diện hiện có nhận được từ tập trước đó bằng cách thêm vào một ràng buộc mới lấy ra từ hệ Ax ≤ b, cho nên thuật toán phải dừng sau không quá m vòng lặp (m là số ràng buộc xác định X, không kể ràng buộc về dấu). Sau đây nêu một số chú ý khi thực thi thuật toán. Nhận xét 1.3. Việc tính giá trị hàm mục tiêu g(x) tại các đỉnh của Sk và việc kiểm tra g(x) bị chặn dưới trên các tia cực biên của Sk được thực hiện bằng cách giải các quy hoạch tuyến tính dạng (1.9) và (1.10). Các bài toán tuyến tính này đều có cùng tập ràng buộc Y và chỉ khác nhau ở các hệ số hàm mục tiêu. Do đó, có thể sử dụng kỹ thuật tái tối ưu hóa để giảm bớt số phép lặp đơn hình cần thực hiện trong quá trình giải các bài toán tuyến tính này. Nhận xét 1.4. Nếu Bước 2 xảy ra ở một vòng lặp k nào đó thì có nghĩa là hàm g(x) bị chặn dưới trên mọi tia cực biên của Sk và do đó của Sh với h > k, bởi vì Sh ⊂ Sk với mọi h > k. Vì thế, từ đó Bước 1 sẽ không cần thực hiện nữa. Nhận xét 1.5. Thuật toán không nhất thiết phải bắt đầu từ S0 = Rn+ mà có thể từ tập lồi đa diện bất kỳ S0 ⊃ D, miễn là các đỉnh và các hướng cực biên của S0 đã biết (hoặc có thể tính được dễ dàng). Chẳng hạn, để làm S0 ta có thể chọn một nón có đỉnh tại một điểm cực biên của X và sinh bởi các cạnh của X kề với điểm đó (trong trường hợp này đỉnh duy nhất và các hướng cực biên của S0 được tính bằng kỹ thuật quen thuộc trong quy hoạch tuyến tính). Nhận xét 1.6. Nhằm mục đích đơn giản cách trình bày, chúng ta đã hạn chế chỉ xét các bài toán có tập chấp nhận được cho bởi các ràng buộc bất đẳng thức tuyến tính. Tuy nhiên bằng một số thay đổi nhỏ, thuật toán nêu trên cũng có thể áp dụng cho trường hợp bài toán có các ràng buộc đẳng thức tuyến tính.