Bài toán tối ưu hai cấp và ứng dụng

Bài viết 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 đáng chú ý 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. Cuối cùng, báo cáo nêu một số hướng ứng dụng của tối ưu hai cấp trong kinh tế, phân bổ nguồn lực, trong thiết kế mạng vận tải và trong thị trường năng lượng.
Nội dung trích xuất từ tài liệu:
Bài toán tối ưu hai cấp và ứng dụngK y u công trình khoa h c 2015 – Ph n IBÀI TOÁN TỐI ƯU HAI CẤP VÀ ỨNG DỤNGGS. TS. Trần Vũ ThiệuKhoa Toán – Tin, Đại học Thăng LongEmail: trvuthieu@gmail.comTóm tắt. Báo cáo đề cập tới bài toán tối ưu hai cấp có dạng:(BPP) min {F(x, y) | x ∈ X, G(x, y) ≤ 0, y ∈ argmin {f(x, y) | y ∈ Y, g(x, y) ≤ 0}}, trong đóX ⊆ »n, Y ⊆ »m, F, G, f, g : »n+m → ». Đây là một bài toán qui hoạch toán học theo hai nhómbiến x ∈ »n, y ∈ »m 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à vectơ tham số). Bài toán tối ưu hai cấp hiện đang được nhiều tácgiả 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. Bài này trìnhbà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 đáng chú ý của bài toán, đặcbiệ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. Cuối cùng, báocáo nêu một số hướng ứng dụng của tối ưu hai cấp trong kinh tế, phân bổ nguồn lực, trong thiếtkế mạng vận tải và trong thị trường năng lượng.Từ khóa Tối ưu hai cấp, bài toán tối ưu tuyến tính hai cấp, bài toán nhiều mục tiêu, quihoạch toán học, trò chơi Stackelberg.1. Bài toán tối ưu hai cấpBà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, v.v ... Tối ưu hai cấp xuất hiện trênsá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àitoá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ệmcủ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ủamỗ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.Để 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ạnggiao 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ềnthu được. Với mỗi mức thu phí đề ra, người tham gia giao thông (cấp dưới) sẽ đáp lại và tìm hànhtrì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 quannhư 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 thamgia 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àovà mức thu bao nhiêu là có lợi nhất (thu về được nhiều tiền nhất)?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:Trư ng Đ i h c Thăng Long112K y u công trình khoa h c 2015 – Ph n I G ( x , y) ≤ 0, x ∈ X,min f ( x , y)min F(x, y) với điều kiện ,y nghiêm đúng  yx ,y g( x , y) ≤ 0, y ∈ Y.(BPP)trong đó X ⊂ »n, Y ⊂ »m, F, f : X×Y → » 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 : X×Y → » là các hàm ràng buộc.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.• Khi F, f và 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 haicấp (Bilevel Linear Programming Problem, viết tắt là BLPP) hay trò chơi Stackelberg tuyến tính(Linear Stackelberg Game).• Khi F và f là các véctơ hàm (hàm giá trị véctơ), tức làF : »n×»m → »p và f : »n×»m → »q,ta có bài toán tối ưu đa mục tiêu hai cấp (Bilevel Multi-Objective Programming Problem,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 (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ể. Tuynhiê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, tuynhiê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ậptrung 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àitoán hai cấp thường là không lồi, thuộc lớp bài toán NP-khó và thiếu các thuật toán giải hiệu quả.Ví dụ 1. Sau đây là một ví dụ đơn giản về bài toán tối ưu hai cấp: Tìm x, y ∈ » sao chomin F(x, y) = x - 2yx ,yvới điều kiện- x + 3y - 4 ≤ 0 và với mỗi x ∈ »y là nghiệm cực tiểu của bài toánmin {f(x, y) = x + y : x - y ≤ 0, - x - y ≤ 0}.yTập chấp nhận được của bài toán cấp dưới phụ thuộc x, ký hiệu S(x) vớiS(x) = {y ∈ » : x - y ≤ 0, - x - y ≤ 0} = {y ∈ » : y ≥ |x|}.Trư ng Đ i h c Thăng Long113K y u công trình khoa h c 2015 – Ph n ITậ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ởiP(x) = {y : y ∈ argmin {x + y : y ∈ S(x)}} = {y : y = |x|}Bài toán tối ưu hai cấp được viết lại thànhmin {x - 2y : - x + 3y - 4 ≤ 0, y ∈ P(x)}.x ,yTập chấp nhận đượcM = {(x, y) : - x + 3y - 4 ≤ 0, y ∈ P(x)}của bài toán hai cấp được gọi là miền cảm sinh.Nói chung, ...