Luận văn Thạc sĩ Toán học: Một số tính chất của bài toán tối ưu hai cấp

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

Thêm vào BST

Báo xấu

23
lượt xem 5
download

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

Luận văn là trình bày nội dung, nguồn gốc của bài toán tối ưu hai cấp, các dạng bài toán tối ưu hai cấp và các tính chất cần biết của bài toán, đặc biệt lưu ý trường hợp riêng quan trọng là bài toán tối ưu hai cấp tuyến tính, nhằm giúp việc học tập, nghiên cứu bài toán tối ưu hai cấp được thuận lợi và dễ dàng hơn. 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: Một số tính chất của bài toán tối ưu hai cấp

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRỊNH MINH THƯỜNG MỘT SỐ TÍNH CHẤT CỦA BÀI TOÁN TỐI ƯU HAI CẤP 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 TRỊNH MINH THƯỜNG MỘT SỐ TÍNH CHẤT CỦA BÀI TOÁN TỐI ƯU HAI CẤP Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 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 - 2016
i Mục lục Danh mục các hình vẽ . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1 Kiến thức chuẩn bị 4 1.1 Tập lồi và tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Bài toán tối ưu tuyến tính đa mục tiêu . . . . . . . . . . . . . . . . 7 1.3 Tính chất tập nghiệm hữu hiệu của bài toán . . . . . . . . . . . . . 10 Chương 2 Bài toán tối ưu hai cấp 12 2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Đưa về bài toán tối ưu một cấp . . . . . . . . . . . . . . . . . . . . 16 2.3 Tính chất bài toán tối ưu hai cấp . . . . . . . . . . . . . . . . . . . 18 2.4 Bài toán tối ưu hai cấp tuyến tính . . . . . . . . . . . . . . . . . . . 22 2.5 Một số hướng ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . 25 Chương 3 Tối ưu hai cấp tuyến tính và tối ưu đa mục tiêu 27 3.1 Nội dung vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Quan hệ với tối ưu đa mục tiêu . . . . . . . . . . . . . . . . . . . . 29 3.3 Quan hệ với tối ưu trên tập nghiệm hữu hiệu . . . . . . . . . . . . . 31 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
ii Danh mục các hình vẽ Bảng 2.1 So sánh nghiệm của hai Ví dụ 2.3 và 2.2 Hình 2.1 Minh họa Ví dụ 2.1 Hình 2.2 Không gian ngiệm của cấp trên (Ví dụ 2.1) Hình 2.3 Nghiệm tối ưu của cấp trên (Ví dụ 2.2) Hình 2.4 Không gian ngiệm của cấp trên (Ví dụ 2.3) Hình 2.5 Nghiệm tối ưu của cấp trên (Ví dụ 2.3) Hình 2.6 Minh họa các tập S, S(x), P (x) và M trong Ví dụ 2.4
1 Mở đầu Luận văn đề cập tới bài toán tối ưu hai cấp (viết tắt là BPP) có dạng: min {F (x, y) | x ∈ X, G(x, y) ≤ 0, y ∈ arg min {f (x, y) | y ∈ Y, g(x, y) ≤ 0}}, trong đó X ⊆ Rn , Y ⊆ Rm , F, G, f, g : Rm+n → R. Đây là một bài toán qui hoạch toán học theo hai nhóm biến x ∈ Rn , y ∈ Rm và trong ràng buộc của bài toán này, y là nghiệm của bài toán tối ưu thứ hai (với y là véctơ biến và x là véctơ tham số). Như vậy có thể hiểu đơn giản tối ưu hai cấp là bài toán tối ưu mà trong ràng buộc của nó lại là một bài toán tối ưu khác. Bài toán tối ưu hai cấp xuất hiện trên sách báo, tạp chí có liên quan tới các hệ thống có sự phân cấp, trong thực tế tối ưu hai cấp nảy sinh từ nhiều ứng dụng đa dạng trong hoạt động vận tải, kinh tế, sinh thái học, kỹ thuật, . . . Bài toán tối ưu hai cấp hiện đang được nhiều tác giả quan tâm nghiên cứu, do ý nghĩa khoa học và khả năng ứng dụng của bài toán. Tối ưu hai cấp được phân ra thành: các bài toán hai cấp một mục tiêu (được nghiên cứu và ứng dụng nhiều hơn) và bài toán hai cấp nhiều mục tiêu (khó ứng dụng hơn do ít có thuật toán hiệu quả). Khi các hàm mục tiêu và các hàm ràng buộc trong bài toán là các hàm tuyến tính, thì ta có bài toán tối ưu hai cấp tuyến tính. Tối ưu hai cấp là một bài toán NP - khó và thuộc lớp các bài toán tối ưu toàn cục, nói chung rất phức tạp và khó giải. Nói riêng nó bao hàm bài toán tối ưu trên tập nghiệm hữu hiệu (tập điểm Pareto) như một trường hợp cụ thể. Nhiều phương pháp xử lý đã được đề xuất, tuy nhiên hiệu quả không cao và chủ yếu đối với các bài toán hai cấp tuyến tính với một hay nhiều mục tiêu. Đề tài luận văn "Một số tính chất của bài toán tối ưu hai cấp"
2 có mục đích tìm hiểu và trình bày nội dung, nguồn gốc của bài toán tối ưu hai cấp, các dạng bài toán tối ưu hai cấp và các tính chất cần biết của bài toán, đặc biệt lưu ý trường hợp riêng quan trọng là bài toán tối ưu hai cấp tuyến tính, nhằm giúp việc học tập, nghiên cứu bài toán tối ưu hai cấp được thuận lợi và dễ dàng hơn. Cuối cùng, luận văn giới thiệu một số hướng ứng dụng của tối ưu hai cấp trong thực tế. Nội dung luận văn gồm ba chương: Chương 1. "Kiến thức chuẩn bị” nhắc lại một số kiến thức về tập lồi đa diện, khái niệm nghiệm hữu hiệu (điểm tối ưu Pareto) của bài toán tối ưu đa mục tiêu và tính chất đặc trưng đối với đỉnh và cạnh hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu. Chương 2. "Bài toán tối ưu hai cấp" giới thiệu khái quát nội dung, xuất xứ của bài toán tối ưu hai cấp, các tính chất cần biết của bài toán, đặc biệt lưu ý tới trường hợp riêng quan trọng là bài toán tối ưu hai cấp tuyến tính một mục tiêu. Cuối chương, đề cập tới một số hướng ứng dụng của tối ưu hai cấp trong thực tế. Chương 3. "Tối ưu hai cấp tuyến tính và tối ưu đa mục tiêu" xét mối liên hệ giữa bài toán tối ưu hai cấp tuyến tính và bài toán tối ưu tuyến tính trên tập nghiệm hữu hiệu. Có thể mô tả bài toán này dưới dạng bài toán kia, và ngược lại, Từ đó suy ra hệ quả là bài toán tối ưu tuyến tính trên tập nghiệm hữu hiệu là NP - khó. Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên dưới sự giúp đỡ và hướng dẫn tận tình của GS.TS. Trần Vũ Thiệu. Qua đây tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới Thầy, người đã dành nhiều thời gian và tâm huyết để hướng dẫn và tạo điều kiện cho tác giả trong suốt thời gian 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 lợi trong quá trình tác giả học tập và nghiên cứu. Tác giả xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo, Khoa Toán - Tin trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả
3 trong suốt thời gian học tập tại trường. Cuối cùng tác giả xin gửi lời cảm ơn đến gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Thái Nguyên, tháng 06 năm 2016 Học viên Trịnh Minh Thường
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 về tập lồi và tập đa diện, khái niệm nghiệm hữu hiệu (điểm tối ưu Pareto) của bài toán tối ưu tuyến tính đa mục tiêu và nêu lại các tính chất đặc trưng của đỉnh và cạnh hữu hiệu của bài toán. Nội dung của chương được tham khảo từ các tài liệu [1], [7] và [9]. 1.1 Tập lồi và tập lồi đa diện Trước hết ta nhắc lại khái niệm tập lồi trong Rn và các khái niệm có liên quan. Định nghĩa 1.1. Tập C ⊆ Rn được gọi là một tập lồi nếu λa + (1 − λ)b ∈ C ∀a, b ∈ C, ∀λ ∈ [0, 1], tức là C chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó. • Ta chú ý tới một số tập lồi đặc biệt sau: 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 có dạng H = {x ∈ Rn : aT x = α}, a ∈ Rn , a 6= 0 và α ∈ Rn . c) Các nửa không gian đóng H + = {x ∈ Rn : aT x ≥ α}, H − = {x ∈ Rn : aT x ≤ α}. • Từ định nghĩa tập lồi trực tiếp suy ra một số tính chất đơn giản sau:
5 a) Giao của một họ bất kỳ các tập lồi là một tập lồi: C, D lồi thì C ∩ D lồi. b) Nếu C, D ⊂ Rn là tập lồi thì C ± D = {x ± y : x ∈ C, y ∈ D} là các tập lồi. c) Nếu C ∈ Rm , D ∈ Rn thì tích C × D = {(x, y) : x ∈ C, y ∈ D} là một tập lồi trong Rm+n . (Có thể mở rộng cho nhiều tập lồi). Đị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 là aff 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 là conv E. Đị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 dim C, là thứ nguyên hay số chiều của bao afin aff C 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 con lồi F của tập lồi C được gọi là một diện của C nếu x, y ∈ C mà (1 − λ)x + λy ∈ F, 0 < λ < 1 thì [x, y] ⊂ F , tức nếu một đoạn thẳng bất kỳ thuộc C có một điểm trong thuộc F thì cả đoạn thẳng ấy phải nằm trong F . Một diện có số chiều 0 gọi là một điểm cực biên của C. Nói một cách khác, đó là một điểm thuộc C mà nó không thể là một điểm trong của một đoạn thẳng bất kỳ nào với hai đầu mút khác nhau thuộc C. Một diện có số chiều 1 gọi là một cạnh của C: cạnh là hữu hạn nếu diện đó là một đoạn thẳng, cạnh là vô hạn nếu diện đó là một nửa hay cả đường thẳng. Một diện của C, khác ∅ và khác C, gọi là một diện thực sự của C. Ví dụ: các diện thực sự của một hình lập phương trong R3 là 8 đỉnh, 12 cạnh và 6 mặt của nó. Định nghĩa 1.6. 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, ký hiệu là D. Nói cách khác, D là tập nghiệm của một hệ
6 hữu hạn các phương trình và (hoặc) bất phương trình tuyến tính. Một tập lồi đa diện có thể bị chặn hoặc không bị chặn (không giới nội). 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. Các đa giác lồi theo nghĩa thông thường trong mặt phẳng hai chiều (tam giác, hình vuông, hình tròn,...) là những ví dụ cụ thể về đa diện lồi trong R2 . Tập lồi đa diện mà đồng thời là một nón, còn được gọi là một nón lồi đa diện. Mỗi điểm cực biên của tập lồi đa diện được gọi là một đỉnh của tập đa diện đó. Định nghĩa 1.7. Đoạn thẳng [x1 , x2 ], x1 6= x2 , được gọi là một cạnh hữu hạn của D nếu x1 , x2 là các đỉnh của D và rank {ai : ai , x1 = ai , x2 = bi } = n − 1. Định nghĩa 1.8. Tia Γ = {x0 + λd : λ ≥ 0} ⊆ D, trong đó x0 ∈ D, d ∈ Rn , được gọi là một cạnh vô hạn của D nếu rank {ai : ai , x = bi , ∀x ∈ Γ} = n − 1. Để hiểu rõ hơn về tập lồi đa diện ta cũng cần biết một số khái niệm sau đây. Trong các bài toán tối ưu, ta thường gặp tập lồi đa diện có dạng D = {x ∈ Rn : Ax ≤ b, x ≥ 0} với A ∈ Rm×n , b ∈ Rm }, tức D là tập nghiệm không âm của một hệ (hữu hạn) bất phương trình tuyến tính. Tập này không chứa đường thẳng nào (do x ≥ 0) nên D có đỉnh. Từ các định nghĩa nêu trên cho thấy: a) Điểm x0 ∈ D là một đỉnh của D khi và chỉ khi hệ véctơ {ak : ak , x0 = bk } ∪ {ek : x0k = 0} có hạng bằng n. b) Các hướng cực biên (chuẩn hóa) của D là các nghiệm cơ sở của hệ Ay ≤ 0, eT y = 1, y ≥ 0, trong đó eT = (1, . . . , 1).
7 c) Giả sử tia Γ = {x0 + λd : λ ≥ 0}, trong đó x0 là một đỉnh và d là một hướng cực biên của D. Khi đó Γ là một cạnh vô hạn của D khi và chỉ khi rank ({ak : ak , x = bk , ∀x ∈ Γ} ∪ {ek : xk = 0, ∀x ∈ Γ}) = n − 1. Bây giờ cho tập lồi đa diện D 6= ∅ xác định bởi hệ bất phương trình tuyến tính ai , x ≥ bi , i = 1, 2, . . . , m. Với x ∈ D, ký hiệu I(x) = {i : ai , x = bi } là tập chỉ số những ràng buộc mà x thỏa mãn chặt. Đặt I0 = {i : ai , x = bi , ∀x ∈ D}. Tính chất đặc trưng của các diện (nói riêng, các đỉnh và cạnh) của D được cho trong định lý sau. Định lí 1.1 (Diện của tập lồi đa diện). Một tập con lồi khác rỗng F ⊂ D là một diện thực sự của D khi và chỉ khi F = {x : ai , x = bi , i ∈ I, ai , x ≥ bi , i 6∈ I} với I là tập chỉ số sao cho I0 ⊂ I ⊂ {1, . . . , m} (I gọi là tập chỉ số xác định diện F ). Hơn nữa, ta có dim F = n − rank {ai : i ∈ I} và dim P = n − rank {ai : i ∈ I0 }. Hệ quả 1.1. Cho D là tập lồi đa diện xác định bởi hệ ai , x ≥ bi , i = 1, . . . , m: a) Điểm x0 ∈ D là một đỉnh của D khi và chỉ khi rank {ai : i ∈ I(x0 )} = n, nghĩa là x0 thỏa mãn chặt n ràng buộc độc lập tuyến tính của D; b) Nếu một đoạn thẳng (nửa đường thẳng hay cả đường thẳng) Γ ⊂ D là một cạnh của D thì Γ được xác định bởi một tập chỉ số I sao cho rank {ai : i ∈ I} = n − 1. 1.2 Bài toán tối ưu tuyến tính đa mục tiêu Xét bài toán tối ưu đa mục tiêu có dạng: V min h(x) = [h1 (x), . . . , hp(x)] với x ∈ U, (MOPP)
8 với h : Rn → Rp là véctơ hàm mục tiêu, U ⊆ Rn là tập ràng buộc của bài toán. Để giải (MOPP), ta cần phải so sánh các véctơ hàm mục tiêu [h1 (x), . . . , hp (x)] đối với các x ∈ U khác nhau. Vì thế, ta cần xác định một quan hệ thứ tự trên h(U ), dùng để so sánh. Vì với p ≥ 2, trong Rp không có thứ tự toàn phần như trong R1 nên ta chỉ có thể xác định một thứ tự bộ phận trên h(U ). Giả sử K là một nón tùy ý sao cho K ⊂ Rp , một quan hệ nhị nguyên (hai ngôi) theo nón K, ký hiệu ≤K , được xác định bởi a ≤K b khi và chỉ khi (b − a) ∈ K. Quan hệ thứ tự bộ phận tạo ra bởi các nón lồi, đóng và nhọn hay được sử dụng nhất. Do không thể tìm được một nghiệm mà là tối ưu đồng thời cho mọi hàm mục tiêu, nên ta dùng một khái niệm yếu hơn, đó là khái niệm điểm không bị vượt trội. Định nghĩa 1.9. Điểm y 0 ∈ h(U ) gọi là điểm không bị vượt trội (non-dominated point) theo nón K nếu không tồn tại điểm y ∈ h(U ), y 6= y 0 sao cho y ≤K y 0 . Nếu y ∗ ∈ h(U ) là điểm không bị vượt trội theo nón K thì x∗ ∈ U sao cho y ∗ = h(x∗ ) gọi là điểm tối ưu Pareto (Pareto-optimal point) theo nón K. Định nghĩa sau đây về các điểm hữu hiệu hay được sử dụng trên thực tế. Định nghĩa 1.10. Điểm x∗ ∈ U gọi là điểm tối ưu Pareto hay nghiệm hữu hiệu (efficiant solution) của bài toán (MOPP) nếu không tồn tại x ∈ U sao cho [h1 (x), . . . , hp (x)] ≤ [h1 (x∗ ), . . . , hp (x∗ )] và [h1 (x), . . . , hp (x)] 6= [h1 (x∗ ), . . . , hp (x∗ )]. Nếu x∗ là một điểm tối ưu Pareto thì h(x∗ ) gọi là một điểm không bị vượt trội (theo nón K ≡ Rp+ \ {0p }). Khi đó các nghiệm hữu hiệu, hay nghiệm tối ưu Pareto, là những nghiệm mà không thể cải tiến theo một mục tiêu nào đó mà lại không làm thiệt hại ít nhất một mục tiêu khác. Ta nhận xét là Định nghĩa 1.10 là một trường hợp đặc biệt của Định nghĩa 1.9 với nón được sử dụng là Rp+ \ {0p }.
9 Giải một bài toán tối ưu đa mục tiêu có nghĩa là tìm một phần hay toàn bộ tập nghiệm hữu hiệu và đệ trình nó cho người ra quyết định xem xét, đánh giá và lựa chọn. Khi đó, nghiệm do người ra quyết định lựa chọn (chẳng hạn theo một tiêu chuẩn nào đó) được xem là nghiệm tối ưu của bài toán tối ưu đa mục tiêu đã cho. • Khi h(x) là một ánh xạ tuyến tính và U là một tập lồi đa diện thì ta có bài toán tối ưu tuyến tính đa mục tiêu, ký hiệu là (MOLP). Có thể phát biểu như sau: V min{Cx : x ∈ D} (MOLP) với C là ma trận cấp p × n và D ⊆ Rn là một tập lồi đa diện được xác định bởi hệ ai , x ≥ bi , i = 1, 2, . . . , m. với ai ∈ Rn và bi ∈ R (i = 1, . . . , m) cho trước. Sau đây là một số khái niệm về nghiệm của bài toán (MOLP). Định nghĩa 1.11. Ta nói x0 ∈ D là một nghiệm hữu hiệu của (MOLP) nếu không tồn tại x ∈ D với Cx0 ≥ Cx và Cx0 6= Cx. Nếu mọi điểm thuộc diện F ⊆ D là nghiệm hữu hiệu thì ta nói F là một diện nghiệm hữu hiệu hay đơn giản, diện hữu hiệu. Nếu diện hữu hiệu F là một đỉnh (hay cạnh) của D thì để đơn giản, ta nói F là một đỉnh hữu hiệu (hay cạnh hữu hiệu) của (MOLP). Định nghĩa 1.12. Ta nói x0 ∈ D là một nghiệm hữu hiệu yếu của (MOLP) nếu không có x ∈ D với Cx0 > Cx. Ta còn nói x0 ∈ D là một nghiệm hữu hiệu lý tưởng nếu Cx0 ≤ Cx với mọi x ∈ D.
10 Hình 1.1 minh họa tập nghiệm hữu hiệu trong R2 khi C = I2 (ma trận đơn vị). Rõ ràng một nghiệm hữu hiệu cũng là nghiệm hữu hiệu yếu, nhưng điều ngược lại không chắc đúng. 1.3 Tính chất tập nghiệm hữu hiệu của bài toán Ta nêu lại bài toán (MOLP): V min{Cx : x ∈ D} với C ∈ Rp×n và D = {x ∈ Rn : ai , x ≥ bi , i = 1, 2, . . . , m}, trong đó ai ∈ Rn , bi ∈ R(i = 1, . . . , m) cho trước. Giả thiết D 6= ∅. Mục này quan tâm chủ yếu tới các nghiệm hữu hiệu của bài toán (MOLP). Ký hiệu E(D) là tập các nghiệm hữu hiệu của bài toán (MOLP). Ta chú ý tới một số tính chất sau đây của tập nghiệm hữu hiệu của (MOLP). Mệnh đề 1.1. Điểm x0 ∈ D là một nghiệm hữu hiệu của (MOLP) khi và chỉ khi tồn tại véctơ dương λ ∈ Rp (λ > 0) sao cho x0 là nghiệm cực tiểu của hàm tuyến tính f (x) = λT Cx trên D. Mệnh đề 1.2. Nếu tập D bị chặn thì (MOLP) chắc chắn có nghiệm hữu hiệu. Mệnh đề 1.3. Tập nghiệm hữu hiệu của (MOLP) là liên thông đường gấp khúc, theo nghĩa với bất kỳ hai nghiệm hữu hiệu x, y ∈ D, tồn tại hữu hạn nghiệm hữu hiệu x1 , . . . , xk sao cho x1 = x, xk = y và mọi đoạn [xi , xi+1 ], i = 1, . . . , k − 1, là hữu hiệu. Với mỗi x0 ∈ D, đặt tương ứng bài toán qui hoạch tuyến tính theo biến x: max {eT C(x0 − y) | Cx0 ≥ Cx, x ∈ D}, (LP0 ) trong đó e là véctơ p chiều với mọi phần tử bằng 1 (p - số mục tiêu trong (MOLP)). Kết quả sau chỉ ra lược đồ hay được dùng để kiểm tra một điểm chấp nhận được x0 là nghiệm hữu hiệu (dr tối ưu Pareto) của bài toán (MOLP1 ).
11 Mệnh đề 1.4. x0 ∈ E(D) khi và chỉ khi giá trị tối ưu của (LP0 ) bằng 0. Hơn nữa, mỗi nghiệm tối ưu của (LP0 ) là một nghiệm hữu hiệu, tức là thuộc E(D), bất kể x0 có là nghiệm hữu hiệu của (MOLP) hay không. Kết luận, chương này đã đề cập tới bài toán tối ưu đa mục tiêu và trường hợp riêng là bài toán tối ưu tuyến tính đa mục tiêu, nhắc lại một số khái niệm có liên quan đến bài toán như: tập lồi đa diện và các đỉnh, cạnh, diện của tập lồi đa diện, khái niệm điểm tối ưu Pareto hay nghiệm hữu hiệu của bài toán đa mục tiêu và giới thiệu tóm tắt tính chất đặc trưng của các đỉnh và cạnh hữu hiệu của bài toán tối ưu tuyến tính đa mục tiêu.
12 Chương 2 Bài toán tối ưu hai cấp Chương này trình bày nội dung, nguồn gốc của bài toán tối ưu hai cấp, các tính chất của bài toán, đặc biệt lưu ý tới trường hợp riêng quan trọng là bài toán tối ưu hai cấp tuyến tính một mục tiêu. Cuối chương, đề cập tới một số hướng ứng dụng của tối ưu hai cấp trong thực tế. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [2] - [8] và [10]. 2.1 Nội dung bài toán Bài toán tối ưu hai cấp (Bilevel Programming Problem, viết tắt là BPP) nảy sinh từ nhiều ứng dụng khác nhau trong vận tải, kinh tế, sinh học, kỹ thuật,... Tối ưu hai cấp xuất hiện trên sách báo, tạp chí thường có liên quan đến các hệ thống phân cấp. Tối ưu hai cấp bao gồm hai bài toán tối ưu, trong đó một phần dữ liệu của bài toán thứ nhất được xác định ẩn thông qua nghiệm của bài toán thứ hai. Người ra quyết định ở mỗi cấp cố gắng tối ưu hóa (cực tiểu hay cực đại) hàm mục tiêu riêng của cấp mình mà không để ý tới mục tiêu của cấp kia, nhưng quyết định của mỗi cấp lại ảnh hưởng tới giá trị mục tiêu của cả hai cấp và tới không gian quyết định nói chung. • Ví dụ thực tế: Bài toán thu lệ phí giao thông Để làm ví dụ, ta xét tình huống thực tế sau đây trong lĩnh vực giao thông đường bộ: Mạng giao thông đường bộ của một vùng nào đó (miền Bắc chẳng hạn), gồm nhiều đường quốc lộ và đường liên tỉnh, liên kết với nhau và nối liền nhiều tỉnh, thành phố. Cơ quan quản lý (cấp trên) dự tính thu lệ phí một số tuyến đường trong hệ thống và mục tiêu mong muốn là tối đa hóa số tiền thu được. Với mỗi mức thu
13 phí đề ra, người tham gia giao thông (cấp dưới) sẽ đáp lại và tìm hành trình đi lại sao cho làm cực tiểu tổng chi phí bỏ ra, có tính toán, cân nhắc các yếu tố có liên quan như thời gian, khoảng cách, hao phí xăng xe, lệ phí... và lựa chọn hành trình đi tối ưu, khi tham gia giao thông trong hệ thống. Nếu cấp trên đặt lệ phí quá cao, người tham gia giao thông sẽ từ chối chọn các tuyến đường có chi phí đắt và hệ quả là cơ quan quản lý thu được ít kinh phí hơn. Vậy bài toán đặt ra cho cơ quan quản lý (cấp trên) là đặt mức lệ phí trên những tuyến đường nào và mức thu bao nhiêu là có lợi nhất (thu về được nhiều tiền nhất). • Mô hình toán học Sau đây là phát biểu toán học của một số dạng bài toán tối ưu hai cấp. Bài toán tối ưu hai cấp một mục tiêu: Tìm min F (x, y) với điều kiện G(x, y) ≤ 0. (BPP) x,y trong đó với mỗi giá trị x, y là nghiệm tối ưu của bài toán thứ hai: Tìm min f (x, y) với điều kiện g(x, y) ≤ 0. y với x ∈ X ⊆ Rn , y ∈ Y ⊆ Rm , F, f : Rn × Rm → R lần lượt là hàm mục tiêu của bài toán ngoài (bài toán cấp trên) và bài toán trong (bài toán cấp dưới), G, g : Rn × Rm → R là các hàm ràng buộc của các bài toán tương ứng. Ta thấy (BPP) là một bài toán qui hoạch toán học có chưa bài toán tối ưu ở các ràng buộc của nó. • Trường hợp riêng: Khi X, Y là các tập đa diện và F, f, G, g là các hàm tuyến tính afin, (BPP) gọi là bài toán tối ưu tuyến tính hai cấp (viết tắt là BLPP) hay trò chơi Stackelberg tuyến tính). • Tối ưu hai cấp đa mục tiêu Khi F và f là các véctơ hàm, tức là F : Rn × Rm → Rp và f : Rn × Rm → Rq , ta có bài toán tối ưu đa mục tiêu hai cấp (viết tắt là BMOPP). Các bài toán tối ưu hai cấp, trong đó mỗi cấp chỉ có một hàm mục tiêu (bài toán
14 (BPP)) đã được nhiều người nghiên cứu. Với các bài toán mà mục tiêu và các ràng buộc là hàm tuyến tính (bài toán (BLPP)), đã có một số kết quả lý thuyết, ứng dụng và phương pháp giải cụ thể. Tuy nhiên, các bài toán tối ưu hai cấp, trong đó mỗi cấp có nhiều hàm mục tiêu (bài toán (BMOPP)) ít được đề cập tới trong các tài liệu. Sự thiếu vắng các nghiên cứu như thế có lẽ là do có những khó khăn nhất định trong tìm kiếm và xác định các nghiệm tối ưu. Trong bài toán hai cấp, mỗi cấp được quyền điều khiển (chọn giá trị) một số biến quyết định của cấp mình. Mỗi cấp đề ra quyết định nhằm tối ưu hóa mục tiêu riêng của cấp mình, tuy nhiên giá trị hàm mục tiêu đó thường phụ thuộc một phần các biến do cấp kia điều khiển. Sự tương tác giữa hai cấp phản ánh tình huống xây dựng quyết định theo kiểu phi tập trung hóa, nghĩa là cấp cao hơn (cấp trên, lãnh đạo hay chủ cái) chỉ có thể gây ảnh hưởng chứ không ra lệnh hay ép buộc cấp dưới (người dưới quyền hay người cùng chơi) lựa chọn. Khả năng ứng dụng của tối ưu hai cấp bị hạn chế bởi nhiều khó khăn về tính toán do bài toán hai cấp thường là bài toán không lồi và không liên thông, thuộc lớp bài toán NP-khó và do thiếu các thuật toán giải hiệu quả. • Nguồn gốc bài toán tối ưu hai cấp Tối ưu hai cấp bắt nguồn từ qui hoạch toán học và lý thuyết trò chơi. A. Phát biểu đầu tiên về bài toán tối ưu hai cấp xuất hiện trong bài báo của Bracken J. và McGill J. [5], mặc dù tên gọi tối ưu hai cấp và nhiều cấp chính thức được sử dụng lần đầu trong báo cáo của Candler W. và Norton R. [6]. Tuy nhiên, mãi sau thập kỷ 80 thế kỷ 20, các bài toán tối ưu hai cấp và nhiều cấp mới bắt đầu nhận được sự chú ý và thực sự phát triển. B. Được thúc đẩy bởi lý thuyết trò chơi Stackelberg [10], một số tác giả đã đẩy mạnh nghiên cứu tối ưu hai cấp và qua đó đã thúc đẩy sự phát triển của tối ưu hai cấp trong cộng đồng qui hoạch toán học. Một số khái niệm trong tối ưu hai cấp hay nhiều cấp bắt nguồn từ các thuật ngữ dùng trong lý thuyết trò chơi như chủ cái, người cùng chơi, chiến lược, xung đột, cạnh tranh, cân bằng,...
15 Mỗi trò chơi thường bao gồm nhiều người chơi, mỗi người chơi có một số cách chơi hay chiến lược chơi và sẽ phải nộp (hay nhận) số tiền trả tương ứng với cách chơi đó. Đơn giản nhất là trò chơi hai người với tổng 0 hay còn gọi là trò chơi đối kháng. Trong trò chơi này, số tiền thắng của người này bằng số tiền thua của người kia và lập nên một ma trận trả tiền. Mỗi người chơi đều biết thông tin về cách chơi của người kia và số tiền trả tương ứng. Cả hai ra quyết định (công bố chiến lược chơi) cùng một lúc. Hai người chơi độc lập và không hợp tác với nhau. Các trò chơi dân gian như trò chơi tung đồng xu, trò chơi gieo xúc sắc và trò chơi "Giấy - Búa - Kéo" (hay trò chơi "One - Two - Three") thuộc loại trò chơi đối kháng, hai đấu thủ. Tiếp theo là trò chơi song ma trận với hai người chơi, trong đó số tiền thắng của người này khác số tiền thua của người kia, mỗi người chơi trả tiền theo một ma trận riêng. Hai người chơi ra quyết định theo thứ tự qui định (người trước, kẻ sau). Mục đích của mỗi người chơi là tìm chiến lược chơi đem lại lợí ích cao nhất (hay chi phí thấp nhất) cho người chơi đó. Trạng thái của trò chơi mà không người chơi nào được lợi hơn nếu người đó đơn phương thay đổi chiến lược chơi của mình, trong khi đối phương giữ nguyên chiến lược chơi của họ, được gọi là nghiệm cân bằng Nash (Nash equili-brium). Phát triển tiếp là trò chơi Stackelberg với qui tắc chơi hơi khác. Người chơi giữ quyền ra quyết định trước gọi là chủ cái (leader). Những người chơi sau đáp trả lại quyết định (chiến lược) của chủ cái gọi là người chơi thứ cấp (followers). Hành động của người chơi này tác động đến hàm mục tiêu (lợi ích hay chi phí) và sự lựa chọn quyết định của người kia, và ngược lại. Theo quan điểm qui hoạch toán học, trò chơi Stackelberg là một bài toán tối ưu hai cấp, theo nghĩa có một bài toán mức trên (chủ cái hành động trước, cố gắng tối ưu hóa mục tiêu của mình) và một bài toán mức dưới (những người chơi thứ cấp hành động sau chủ cái, tìm cực tiểu chi phí hay cực đại lợi ích riêng của họ). Trong thực tế, thường chủ cái có thể là một hãng lớn nổi trội trong một thị trường cạnh tranh nào đó và những người chơi còn lại là những hãng kinh doanh nhỏ hơn trong thị trường
16 đó. 2.2 Đưa về bài toán tối ưu một cấp Xét bài toán tối ưu hai cấp (BPP). Tập ràng buộc của bài toán cấp dưới phụ thuộc x, ký hiệu S(x) với S(x) = {y ∈ Rm : g(x, y) ≤ 0, y ∈ Y }. Tập nghiệm cực tiểu của bài toán cấp dưới, ký hiệu P (x), được xác định bởi P (x) = {y : y ∈ arg min {f (x, y) : y ∈ S(x)}}. Bài toán tối ưu hai cấp (BPP) ban đầu được viết lại thành min {F (x, y) : G(x, y) ≤ 0, x ∈ X, y ∈ P (x)} x,y với tập ràng buộc (còn gọi là miền cảm sinh) của bài toán bây giờ là M = {(x, y) ∈ Rn+m : G(x, y) ≤ 0, x ∈ X, y ∈ P (x)}. Tập này nói chung không lồi, đôi khi không liên thông, thậm chí có thể rỗng. Ví dụ 2.1. Xét một ví dụ đơn giản về bài toán tối ưu hai cấp: Tìm x, y ∈ R đạt min F (x, y) = x − 2y x,y với điều kiện  −x + 3y − 4 ≤ 0 và với mỗi x ∈ R       y là nghiệm cực tiểu của bài toán     min {f (x, y) = x + y : x − y ≤ 0, −x − y ≤ 0}.  y Tập ràng buộc của bài toán cấp dưới phụ thuộc x, ký hiệu S(x) với S(x) = {y ∈ R : x − y ≤ 0, −x − y ≤ 0} = {y ∈ R : y ≥ |x|}.