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

K y u công trình khoa h c 2015 – Ph n I<br /> <br /> BÀI TOÁN TỐI ƯU HAI CẤP VÀ ỨNG DỤNG<br /> GS. TS. Trần Vũ Thiệu<br /> Khoa Toán – Tin, Đại học Thăng Long<br /> Email: trvuthieu@gmail.com<br /> Tóm tắt. Báo cáo đề cập tới bài toán tối ưu hai cấp có dạng:<br /> (BPP) min {F(x, y) | x ∈ X, G(x, y) ≤ 0, y ∈ argmin {f(x, y) | y ∈ Y, g(x, y) ≤ 0}}, trong đó<br /> 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óm<br /> biế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ứ<br /> 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ác<br /> 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. Bài này trình<br /> 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<br /> 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<br /> 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<br /> kế mạng vận tải và trong thị trường năng lượng.<br /> 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, qui<br /> hoạch toán học, trò chơi Stackelberg.<br /> 1. Bài toán tối ưu hai cấp<br /> 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<br /> ứ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ên<br /> 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<br /> 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<br /> 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)<br /> 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<br /> 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.<br /> Để 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<br /> 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à<br /> đườ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ự<br /> 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<br /> thu đượ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ành<br /> 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<br /> 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<br /> 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ừ<br /> 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.<br /> 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<br /> và mức thu bao nhiêu là có lợi nhất (thu về được nhiều tiền nhất)?<br /> 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.<br /> • Bài toán tối ưu hai cấp một mục tiêu:<br /> Trư ng Đ i h c Thăng Long<br /> <br /> 112<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br />  G ( x , y) ≤ 0, x ∈ X,<br /> <br /> min f ( x , y)<br /> min F(x, y) với điều kiện <br /> ,<br /> y nghiêm đúng  y<br /> x ,y<br /> <br />  g( x , y) ≤ 0, y ∈ Y.<br /> <br /> <br /> (BPP)<br /> <br /> 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<br /> (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.<br /> 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.<br /> • 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 hai<br /> cấp (Bilevel Linear Programming Problem, viết tắt là BLPP) hay trò chơi Stackelberg tuyến tính<br /> (Linear Stackelberg Game).<br /> • Khi F và f là các véctơ hàm (hàm giá trị véctơ), tức là<br /> F : »n×»m → »p và f : »n×»m → »q,<br /> ta có bài toán tối ưu đa mục tiêu hai cấp (Bilevel Multi-Objective Programming Problem,<br /> viết tắt là BMOPP).<br /> 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)) đã<br /> đượ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<br /> (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<br /> 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<br /> đượ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ó<br /> khăn nhất định trong tìm kiếm và xác định các nghiệm tối ưu.<br /> 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<br /> đị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<br /> 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.<br /> 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<br /> 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ứ<br /> 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.<br /> 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<br /> toá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ả.<br /> 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 cho<br /> <br /> min F(x, y) = x - 2y<br /> x ,y<br /> <br /> với điều kiện<br /> - x + 3y - 4 ≤ 0 và với mỗi x ∈ »<br /> y là nghiệm cực tiểu của bài toán<br /> <br /> min {f(x, y) = x + y : x - y ≤ 0, - x - y ≤ 0}.<br /> y<br /> <br /> Tậ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ới<br /> S(x) = {y ∈ » : x - y ≤ 0, - x - y ≤ 0} = {y ∈ » : y ≥ |x|}.<br /> Trư ng Đ i h c Thăng Long<br /> <br /> 113<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> 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<br /> P(x) = {y : y ∈ argmin {x + y : y ∈ S(x)}} = {y : y = |x|}<br /> Bài toán tối ưu hai cấp được viết lại thành<br /> <br /> min {x - 2y : - x + 3y - 4 ≤ 0, y ∈ P(x)}.<br /> x ,y<br /> <br /> Tập chấp nhận được<br /> M = {(x, y) : - x + 3y - 4 ≤ 0, y ∈ P(x)}<br /> của bài toán hai cấp được gọi là miền cảm sinh.<br /> Nói chung, miền này thường không lồi, đôi khi không liên thông và thậm chí có thể rỗng.<br /> Ở ví dụ này, miền cảm sinh của bài toán hai cấp không lồi, nhưng liên thông. Đó là tập<br /> M = {(x, y) : - x + 3y - 4 ≤ 0, y ∈ P(x)} = {(x, y) : - x + 3y - 4 ≤ 0, y = |x|} =<br /> {(x, y) : y = - x, - 1 ≤ x ≤ 0} ∪ {(x, y) : y = x, 0 ≤ x ≤ 2}.<br /> Nếu như ràng buộc của bài toán hai cấp nêu trên được đổi thành<br /> - x + 3y - 4 ≤ 0, - y + 0,5 ≤ 0<br /> thì miền cảm sinh của bài toán đó trở thành tập không lồi và không liên thông:<br /> M = {(x, y) : y = - x, - 1 ≤ x ≤ - 0,5} ∪ {(x, y) : y = x, 0,5 ≤ x ≤ 2}.<br /> Trong cả hai trường hợp, bài toán hai cấp có hai điểm cực tiểu địa phương (- 1, 1) và (2,<br /> 2), trong đó điểm (- 1, 1) là cực tiểu toàn cục của bài toán với Fmin= F(- 1, 1) = - 3.<br /> <br /> 2. Nguồn gốc bài toán tối ưu hai cấp<br /> A. Xuất phát từ lý thuyết qui hoạch toán học<br /> 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: "Bracken J. and<br /> McGill J., Mathematical Programs with Optimization Problems in the Constraints, Operations<br /> Research 21 (1973), 37 - 44", 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<br /> lần đầu trong báo cáo: "Candler W. and Norton R., Multilevel Programming, Tech. Rep. 20,<br /> World Bank Development Research Center,Washington D.C., 1977". Tuy nhiên, mãi sau thập kỷ<br /> 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ự<br /> phát triển.<br /> B. Xuất phát từ lý thuyết trò chơi<br /> Được thúc đẩy bởi lý thuyết trò chơi Stackelberg (Stackelberg H., The Theory of the<br /> Market Economy, Oxford University Press, 1952), một số tác giả đã đẩy mạnh nghiên cứu tối ưu<br /> 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<br /> 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<br /> 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, ...<br /> 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<br /> 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<br /> 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<br /> Trư ng Đ i h c Thăng Long<br /> <br /> 114<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> 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<br /> 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<br /> (công bố chiến lược chơi) cùng một luc. Hai người chơi độc lập và không hợp tác với nhau.<br /> 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ủ.<br /> 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<br /> 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<br /> 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<br /> 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 đó.<br /> 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<br /> 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ọ,<br /> được gọi là nghiệm cân bằng Nash (Nash equili-brium).<br /> 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<br /> 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)<br /> 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<br /> 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.<br /> 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,<br /> 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<br /> 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<br /> 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<br /> 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<br /> doanh nhỏ hơn trong thị trường đó.<br /> 3. Tính chất bài toán tối ưu hai cấp<br /> Lý thuyết tối ưu hai cấp nghiên cứu sự tồn tại nghiệm và các tính chất nghiệm của bài<br /> toán, các điều kiện cần tối ưu, các thuật toán tìm nghiệm và về độ phức tạp của bài toán. Người ta<br /> đã chứng minh được rằng ngay cả bài toán tối ưu tuyến tính hai cấp, trong đó mọi hàm là tuyến<br /> tính, là một bài toán NP-cực khó, theo nghĩa nếu bài toán này có thể giải được bằng một thuật<br /> toán thời gian đa thức thì nhiều bài toán khó khác cũng sẽ giải được bằng các thuật toán thời gia<br /> đa thức. Cũng có thể dễ dàng xây dựng các bài toán tối ưu hai cấp tuyến tính có số điểm cực tiểu<br /> địa phương tăng theo cấp hàm mũ theo số biến của bài toán. Nhiều kết quả lý thuyết đáng chú ý<br /> khác cũng đã được chứng minh về mối liên hệ giữa tối ưu hai cấp với các lĩnh vực khác của qui<br /> hoạch toán học. Chẳng hạn, có thể chỉ ra rằng các bài toán minimax, bài toán qui hoạch tuyến<br /> tinh, qui hoạch nguyên, qui hoạch song tuyến tính và qui hoạch toàn phương đều là các trường<br /> hợp riêng của bài toán tối ưu hai cấp. Các lớp bài toán khác như bài toán tối ưu đa mục tiêu, bài<br /> toán Stackelberg tĩnh cũng có quan hệ mật thiết vối bài toán tối ưu hai cấp.<br /> Có các thuật toán điểm cực biên cho bài toán hai cấp tuyến tính, thuật toán nhánh cận và<br /> thuật toán xoay vần bù tìm cực tiểu toàn cục cho bài toán với cấp trên tuyến tính, cấp dưới tuyến<br /> tính hoặc lồi toàn phương, phương pháp hướng giảm và phương pháp phạt tìm cực tiểu địa<br /> phương cho bài toán hai cấp phi tuyến.<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 115<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> Ta có bài toán tối ưu hai cấp nguyên khi các biến x, y hoặc cả hai bị hạn chế nhận các giá<br /> trị nguyên. Nếu thay bài toán ở cấp dưới bằng bài toán bất đẳng thức biến phân, ta có bài toán tối<br /> ưu hai cấp suy rộng, thường gọi là bài toán tối ưu với ràng buộc cân bằng.<br /> • Về sự tồn tại nghiệm:<br /> + Bài toán tối ưu hai cấp không chắc có nghiệm. Ví dụ 2 nêu dưới đây cho thấy điều<br /> này.<br /> + Với các hàm mục tiêu F, f và các hàm ràng buộc G, g liên tục, bị chặn cũng không<br /> đảm bảo bài toán có nghiệm.<br /> Ví dụ 2 (Bard, 1998). Xét bàu toán tơi ưu hai cấp (BPP) với dữ liệu<br /> <br /> min {F(x, y) = (2y1 + 3y2)x1 + (4y1 + y2)x2}<br /> x ,y<br /> <br /> với các điều kiện<br /> x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0,<br /> với mỗi x thỏa mãn các điều kiện trên, y là nghiệm tối ưu của bài toán<br /> <br /> min {f(x, y) = - (x1 + 3x2)y1 - (4x1 + 2x2)y2 : y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0}.<br /> y<br /> <br /> ˆ<br /> Nghiệm tối ưu y của bài toán tối ưu cấp dưới là một hàm của biến x có dạng<br /> <br /> khi x 1 + 3x 2 > 4 x 1 + 2 x 2 hay x 1 < 1 ,<br /> (1, 0)<br /> 4<br /> <br /> 1<br /> ˆ<br /> y (x) =  y1 + y 2 = 1 khi x 1 = 4 ,<br />  (0, 1)<br /> khi x 1> 1 .<br /> 4<br /> <br /> Thay các giá trị này vào hàm mục tiêu của bài toán cấp trên ta nhận được<br /> <br /> ; x1 < 1<br />  2 x1 + 4x 2<br /> 4<br /> <br /> 3<br /> min F =  2 y1 + 2 (0 ≤ y1 ≤ 1) ; x 1 = 1<br /> 4<br /> x<br /> 3x + X<br /> ; x 1> 1<br /> 2<br />  1<br /> 4<br /> với điều kiện<br /> <br /> x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0.<br /> <br /> Hình 1. Không gian nghiệm của cấp trên<br /> <br /> Tính toán cho thấy tại x = ( 1 ,<br /> 4<br /> <br /> 3<br /> 4<br /> <br /> Hình 2. Nghiệm tối ưu của cấp trên<br /> <br /> ) giá trị mục tiêu của cấp dưới là f = - 2,5 và đạt tại một<br /> <br /> điểm bất kỳ trên đoạn thẳng y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0. Giá trị tối ưu tương ứng của cấp trên bằng<br /> Trư ng Đ i h c Thăng Long<br /> <br /> 116<br /> <br />