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

Nội dung text: Bài toán tối ưu hai cấp và ứng dụng

1. Kỷ yếu công trình khoa học 2015 – Phần I BÀI TOÁN TỐI ƯU HAI CẤP VÀ ỨNG DỤNG GS. TS. Trần Vũ Thiệu Khoa Toán – Tin, Đại học Thăng Long Email: trvuthieu@gmail.com Tóm tắt. Báo cáo cp ti bài toán ti u hai cp có dng: (BPP) min {F(x, y) | x ∈ X, G(x, y) 0, y ∈ argmin {f(x, y) | y ∈ Y, g(x, y) 0}}, trong ó n m n+m X ⊆ » , Y ⊆ » , F, G, f, g : » ». ây là mt bài toán qui hoch toán hc theo hai nhóm n m bin x ∈ » , y ∈ » và trong ràng buc ca bài toán này, y là nghim ca bài toán ti u th hai (vi y là véctơ bin và x là vectơ tham s). Bài toán ti u hai cp hin ang c nhiu tác gi quan tâm nghiên cu, do ý ngha khoa hc và kh nng ng dng ca bài toán. Bài này trình bày ni dung, ngun gc ca bài toán ti u hai cp, các tính cht áng chú ý ca bài toán, c bit lu ý ti trng hp riêng quan trng là bài toán ti u hai cp tuyn tính. Cui cùng, báo cáo nêu mt s hng ng dng ca ti u hai cp trong kinh t, phân b ngun lc, trong thit k mng vn ti và trong th trng nng lng. 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 hoạch toán học, trò chơi Stackelberg. 1. Bài toán tối ưu hai cấp 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, v.v 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. Để 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 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)? 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 ti u hai cp mt mc tiêu: Trường Đại học Thăng Long 112
2. Kỷ 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 , (BPP) y,x y nghiêm đ úng   g(x,y)≤ 0,y ∈ Y. n m trong đó X ⊂ » , Y ⊂ » , F, f : X×Y → » lần lượt là hàm mc 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 buc. 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 ti u tuyn tính hai cp (Bilevel Linear Programming Problem, viết tắt là BLPP) hay trò chơi Stackelberg tuyn 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à n m p n m q F : » ×» → » và f : » ×» → » , ta có bài toán ti u a mc tiêu hai cp (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ể. 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à 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 cho min F(x, y) = x - 2y y,x vớ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án min {f(x, y) = x + y : x - y ≤ 0, - x - y ≤ 0}. y 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 S(x) = {y ∈ » : x - y ≤ 0, - x - y ≤ 0} = {y ∈ » : y ≥ |x|}. Trường Đại học Thăng Long 113
3. Kỷ yếu công trình khoa học 2015 – Phần I 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 ∈ 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ành min {x - 2y : - x + 3y - 4 ≤ 0, y P(x)}. y,x ∈ Tập chấp nhận được M = {(x, y) : - x + 3y - 4 ≤ 0, y ∈ P(x)} của bài toán hai cấp được gọi là min cm sinh. 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. Ở 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 M = {(x, y) : - x + 3y - 4 ≤ 0, y ∈ P(x)} = {(x, y) : - x + 3y - 4 ≤ 0, y = |x|} = {(x, y) : y = - x, - 1 ≤ x ≤ 0} ∪ {(x, y) : y = x, 0 ≤ x ≤ 2}. Nếu như ràng buộc của bài toán hai cấp nêu trên được đổi thành - x + 3y - 4 ≤ 0, - y + 0,5 ≤ 0 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: M = {(x, y) : y = - x, - 1 ≤ x ≤ - 0,5} ∪ {(x, y) : y = x, 0,5 ≤ x ≤ 2}. 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, 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.  2. Nguồn gốc bài toán tối ưu hai cấp A. Xuất phát từ lý thuyết qui hoạch toán học 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 McGill J., Mathematical Programs with Optimization Problems in the Constraints, Operations 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 lần đầu trong báo cáo: "Candler W. and Norton R., Multilevel Programming, Tech. Rep. 20, World Bank Development Research Center,Washington D.C., 1977". 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. Xuất phát từ lý thuyết trò chơi Được thúc đẩy bởi lý thuyết trò chơi Stackelberg (Stackelberg H., The Theory of the Market Economy, Oxford University Press, 1952), 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, 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 chin lc chơi và sẽ phải nộp (hay nhận) s tin tr tương ứng với cách chơi đó. Đơn giản nhất là trò chơi hai ngi vi tng 0 hay còn gọi là trò chơi đối kháng. Trong trò chơi này, số tiền Trường Đại học Thăng Long 114
4. Kỷ yếu công trình khoa học 2015 – Phần I 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 luc. 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 trn 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à nghim cân bng 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à ngi chơi th cp (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 đó. 3. Tính chất bài toán tối ưu hai cấp 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 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 đã 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 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 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 đ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 đị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ú ý 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 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 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 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 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. 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à 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 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 phương cho bài toán hai cấp phi tuyến. Trường Đại học Thăng Long 115
5. Kỷ yếu công trình khoa học 2015 – Phần I 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á 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 ư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. • Về sự tồn tại nghiệm: + 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 này. + 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 đảm bảo bài toán có nghiệm. Ví dụ 2 (Bard, 1998). Xét bàu toán tơi ưu hai cấp (BPP) với dữ liệu min {F(x, y) = (2y1 + 3y2)x1 + (4y1 + y2)x2} y,x với các điều kiện x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0, 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 min {f(x, y) = - (x1 + 3x2)y1 - (4x1 + 2x2)y2 : y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0}. y 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 1 (1,0) khix1+ 3x 2 > 4x 1 + 2x 2 hayx 1 4 . 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 1  2x1+ 4x 2 ; x 1 4 với điều kiện x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0. Hình 1. Không gian nghiệm của cấp trên Hình 2. Nghiệm tối ưu của cấp trên 1 3 Tính toán cho thấy tại x = ( 4 , 4 ) giá trị mục tiêu của cấp dưới là f = - 2,5 và đạt tại một đ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 Trường Đại học Thăng Long 116
6. Kỷ yếu công trình khoa học 2015 – Phần I 3 3 7 F = 2y1 + 2 , do đó F ∈ [ 2 , 2 ] (do 0 ≤ y1 ≤ 1). Vì thế, cấp trên không có cách nào đảm bảo cho họ đạt được số tiền trả cực tiểu. Cho nên trong trường hợp này bài toán vô nghiệm.  • Thứ tự ra quyết định: + Thứ tự ai ra quyết định trước, ai ra quyết định sau là rất quan trọng. + Vai trò của cấp trên và cấp dưới không đổi cho nhau được (bài toán không đối xứng). Ví dụ 3 (đảo lại thứ tự bài toán so với Ví dụ 2) cho thấy bài toán có nghiệm. min {f(x, y) = - (x1 + 3x2)y1 - (4x1 + 2x2)y2} y,x với các điều kiện y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0, với mỗi y thỏa mãn các điều kiện trên, x là nghiệm tối ưu của bài toán min {F(x, y) = (2y1 + 3y2)x1 + (4y1 + y2)x2 : x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0}. y Nghiệm tối ưu xˆ của bài toán tối ưu cấp dưới là một hàm của biến y có dạng 1 (1,0) khi2y1+ 3y 2 2 ,  1 xˆ (y) = x1+ x 2 = 1 khi y 1 = 2 ,  1  (0, 1) khi y1 2  1 min f = −(3 − 2x)y1 1 − (2x 1 + 2)y 2 ;y 1 = 2 y  1  −3y1 − 2y 2 ; y 1 < 2 với điều kiện y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0. Hình 3. Không gian nghiệm của cấp trên Hình 4. Nghiệm tối ưu của cấp trên 1 1 Tại y* = ( 2 , 2 ) giá trị tối ưu của bài toán cấp dưới là F = 2,5 đạt tại một điểm bất kỳ trên đoạn thẳng x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0. Trường Đại học Thăng Long 117
7. Kỷ yếu công trình khoa học 2015 – Phần I Bảng 1. So sánh nghiệm ở hai Ví dụ 2 và 3 Ví dụ Ví dụ 3 Điểm cân 2 bằng Nghiệ 1 x1 + x2 1 3 ( 4 , ( 4 , 4 ) m x = 1 3 4 ) Chi phí 1,5 2,5 2,5 F Nghiệ (0, 1) 1 1 1 ( 2 , ( 2 , 2 ) m y 1 2 ) Chi - 2,5 - 2,5 - 2,5 phiis f Tóm lại, bài toán tối ưu hai cấp (BPP) có các tính chất đáng chú ý sau. • Nói chung, tối ưu hai cấp là một bài toán tối ưu không lồi và có thể không liên thông. • Bài toán hai cấp có thể không có nghiệm tối ưu hay nghiệm Pareto khi có nhiều mục tiêu. • Bài toán cấp trên và cấp dưới không thể đổi chỗ cho nhau, nghĩa là thứ tự theo đó các quyết định được đưa ra là rất quan trọng. • Trường hợp tuyến tính vẫn là bài toán NP-khó, nhưng có nhiều cách diễn tả và cách giải. • Các tính chất trên có thể còn đúng cho bài toán với các hàm liên tục và bị chặn. 4. Bài toán tối ưu tuyến tính hai cấp Bài toán tối ưu tuyến tính hai cấp có dang: (BLPP) min F(x, y) = c1x + d1y y,x với các điều kiện  A1 x+ B 1 y ≤ b 1 , x ∈ X,  2 2  minf(x,y)= cx + dy , y nghiêm đ úng  y    A2 x+ B 2 y ≤ b 2 , y ∈ Y. n m 1 2 n 1 2 m trong đó X ⊂ » , Y ⊂ » , x, c , c ∈ » , y, d , d ∈ » , A1, A2, B1, B2 và b1, b2 là các ma trận và véctơ có kích thước thích hợp. Ta nêu một số định nghĩa: • Min ràng buc của bài toán (BLPP): S = {(x, y) : x ∈ X, y ∈ Y, A1x + B1y ≤ b1, A2x + B2y ≤ b2}. • Tp chp nhn c của bài toán cấp dưới với mỗi x ∈ X cố định: S(x) = {y ∈ Y : B2y ≤ b2 - A2x}. • Tp nghim ti u (còn gọi là tp phn ng có lý trí) của bài toán cấp dưới: P(x) = {y ∈ Y : y ∈ argmin{f(x, y) : y ∈ S(x)}}. • Tp chp nhn c (còn gọi là min cm sinh) của bài toán (BLPP): Trường Đại học Thăng Long 118
8. Kỷ yếu công trình khoa học 2015 – Phần I M = {(x, y) ∈ S : y ∈ P(x)}. Khi S và P(x) khác rỗng, bài toán (BLPP) có thể viết lại thành bài toán ti u mt cp thông thường: min {F(x, y) : (x, y) ∈ S, y ∈ P(x)} = min {F(x, y) : (x, y) ∈ M}. Các khái niệm trên đây được minh họa qua ví dụ bằng số sau đây. Ví dụ 4. Xét bài toán tối ưu hai cấp min F(x, y) = x - 4y x≥ 0 với điều kiện min {f(y) = y : - x - y ≤ - 3, - 2x + y ≤ 0, 2x + y ≤ 12, - 3x + 2y ≤ - 4}. y≥ 0 Với bài toán này tập S, S(x), P(x) và miền cảm sinh M được vẽ ở Hình 5. Hình 5. Minh họa các tập S, S(x), P(x) và M trong Ví dụ 4 • Người ta chứng minh được rằng (xem Bard J. F., Practical Bilevel Optimization: Applica-tions and Algorithms, Kluwer Academic Press, 1998) Định lý 1. Tp chp nhn c M ca bài toán (BLPP) là tp nghim ca mt ràng buc ng thc tuyn tính tng khúc và to nên bi giao ca S vơi mt s siêu phng ta ca S. Định lý 2. Nghim ti u (x*, y*) ca bài toán (BLPP) t ti mt nh ca tp S. Các định lý này được sử dụng trong thuật toán liệt kê đỉnh của Candler và Townsley đăng trên tạp chí Computers and Operations Research, 9 (1982). Ngoài ra, cách tiêp cận dựa trên phương pháp đơn hình và nhiều phương pháp phạt khác nhau cũng được đề xuất. • Sau đây nêu cách tiếp cận sử dụng điều kiện Karush-Kuhn-Tucker (điều kiện KKT). Cách tiếp cận này thay bài toán tối ưu cấp dưới bằng điều kiện KKT: Cố định x = xˆ , điều kiện KKT cho điểm tối ưu địa phương y* của bài toán Trường Đại học Thăng Long 119
9. Kỷ yếu công trình khoa học 2015 – Phần I min {f( xˆ , y) : g( xˆ , y) ≤ 0} y là Τ ∇yf( xˆ , y*) - µ ∇yg( xˆ , y*) = 0, µΤg( xˆ , y*) = 0, µ ≥ 0. Bài toán cấp dưới 2 2 min {f(x, y) = c x + d y : A2x + B2y ≤ b2, y ≥ 0} = y∈ Y 2 2 min {f(x, y) = c x + d y : b2 - A2x - B2y ≥ 0, y ≥ 0} y∈ Y được thay bằng điều kiện KKT (các biến đối ngẫu u, v là các véctơ hàng): 2 d + uB2 - v = 0, u(b2 - A2x - B2y) + vy = 0, u, v ≥ 0. Khi đó có thể viết lại bài toán (BLPP) thành (theo các biến x, y, u, v) min {F(x, y) = c1x + d1y} x∈ X với các điều kiện A1x + B1y ≤ b1, 2 uB2 - v = - d , u(b2 - A2x - B2y) + vy = 0, A2x + B2y ≤ b2, x ≥ 0, y ≥ 0, u ≥ 0, v ≥ 0. • Còn có một cách diễn đạt khác cho bài toán (BLPP): Thay tập nghiệm của bài toán cấp dưới bằng cách mô tả nó thông qua hàm giá trị tối ưu. Tuy nhận được bài toán tương đương, nhưng hàm giá trị tối ưu thường không trơn, kể cả khi các hàm trong bài toán là tuyến tính afin. min {F(x, y) : G(x, y) ≤ 0, g(x, y) ≤ 0, f(x, y) - ϕ (x) ≤ 0}, x∈ X, y trong đó ϕ(x) := min {f(x, y) : g(x, y) ≤ 0}. y Để hàm giá trị tối ưu được xác định, bài toán cấp dưới phải có nghiệm với mỗi x có thể. 5. Một số hướng ứng dụng Mô hình bài toán tối ưu hai cấp thường được áp dụng vào các hệ thống có cấu trúc phân cấp, trong đó quyết định của cấp trên có ảnh hưởng tới quyết định của cấp dưới mà không cần can thiệp trực tiếp vào hoạt động của cấp dưới và hàm mục tiêu của bộ phận này phụ thuộc một phần vào các biến bị điều khiển bởi bộ phận khác, hoạt động ở cấp cao hơn hay cấp thấp hơn. Tối ưu hai cấp còn có thể được áp dụng trong công tác lập kế hoạch phát triển kinh tế, xã hội cho một vùng lãnh thổ hay một quốc gia: cấp trên là nhà nước nắm quyền điều khiển các biến chính sách như biểu thuế, tỉ giá, côta nhập khẩu, nhằm mục tiêu tạo ra nhiều việc làm, cực tiểu Trường Đại học Thăng Long 120
10. Kỷ yếu công trình khoa học 2015 – Phần I nguồn lực sử dụng, v.v Cấp dưới là các công ty với mục tiêu tối đa hóa thu nhập ròng với các ràng buộc về kinh tế và quản lý của cấp trên. Cũng có thể áp dụng tối ưu hai cấp trong phân bổ nguồn lực (Resource Allocation) ở một hãng hay công ty có phân cấp quản lý. Cấp trên giữ vai trò của trung tâm cung cấp nguồn lực (vốn, vật tư, lao động) nhằm đạt cực đại lợi nhuận của toàn công ty. Cấp dưới là các nhà máy sản xuất sản phẩm ở các địa điểm khác nhau, quyết định tỉ lệ, sản lượng sản xuất riêng nhằm tối đa hóa hiệu suất của đơn vị mình. Cuối cùng, tối ưu hai cấp cũng được áp dụng trong thiết kế mạng hệ thống vận tải (Trans- portation System Network Design) và trong các thị trường năng lượng (Energy Markets). Sau đây là một mô hình đơn giản về bài toán tối ưu hai cấp trong thị trường điện năng. Giả sử có n nhà máy cùng tham gia vào thị trường sản xuất điện năng, trong đó có một nhà máy (đánh số 1) có sản lượng lớn nhất và giữ vai trò chủ đạo (chủ cái), các nhà máy còn lại đánh số 2, 3, , n. Gọi xi là sản lượng điện cần sản xuất của nhà máy thứ i, i = 1, 2, , n và fi(xi) là chi phí sản xuất của nhà máy i. Giá bán điện p sẽ phụ thuộc vào tổng lượng điện do các nhà máy sản xuất ra. Nhà máy 1 công bố mức sản lượng của mình trước và các nhà máy khác sẽ phản ứng lại đối với số lượng này. Mỗi nhà máy đều mong muốn tối đa hóa lợi nhuận thu được (số tiền bán điện sau khi trừ chi phí sản xuất). Khi đó, bài toán tối ưu hai cấp đặt ra là n max {x1p( ∑ xi ) - f1(x1)} x1 i= 1 với điều kiện n xi ∈ arg max {xip( ∑ xi ) - fi(xi)}, i = 2, , n. xi i= 1 6. Kết luận Trên đây chúng tôi đã trình bày ngắn gọn một số kiến thức cơ bản về bài toán tối ưu hai cấp, một trong những lớp bài toán qui hoạch toán học đang thu hút sự quan tâm của nhiều nhà nghiên cứu trong và ngoài nước. Phân tích nội dung, nguồn gốc của bài toán và các tính chất cần biết của bài toán, nhằm giúp việc tìm hiểu, học tập và 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. Đáng chú ý và được nghiên cứu nhiều hơn cả là các bài toán tối ưu hai cấp tuyến tính, một hay nhiều hàm muc tiêu. Tuy nhiên, khả năng ứng dụng của tối ưu hai cấp hiện nay còn bị hạn chế, do thiếu các thuật toán giải hiệu quả. Hy vọng trong tương lai sẽ có những bài nghiên cứu hoặc tổng quan sâu sắc hơn về bài toán quan trọng này, đặc biệt là các kỹ thuật xử lý bài toán và các ứng dụng cụ thể của bài toán. 7. Tài liệu tham khảo [1]. Ansari E., Zhiani Rezai H. (2011), Solving Multi-objective Linear Bilevel Multi- follower Programming Problem. Int. J. Industrial Mathematics, Vol. 3, No. 4, 303 - 316. [2]. Bard J. F. (1991), Some properties of the bilevel programming problem, Journal of Optimization: Theory and Applications 68, 371 - 378. [3]. Colson B., Marcotte P. and Savard G. (2005), Bilevel Programming: A Servey. A Quarterly Journal of Operations Research, 3, 87 - 107, Springer -Verlag. Trường Đại học Thăng Long 121
11. Kỷ yếu công trình khoa học 2015 – Phần I [4]. Eichfelder G. (2008), Multiobjective Bilevel Optimization, Mathematical Programming, o Vol. 123, N .2, pp. 419 - 449. [5]. Fricke C., An Introduction to Bilevel Programming, Department of Mathe-matics and Statistics, University of Melbourne. [6]. Pieume C. O. et al. (2013), Generating Efficient Solutions in Bilevel Multi-Objective Programming Problems, American Journal of Operations Research 3, 289 - 298. THE BILEVEL PROGRAMMING PROBLEM AND APPLICATIONS Tran Vu Thieu Dept of Math, Thang Long University Abstract: In this report we address the bilevel programming problem of the form (BP) min {F(x, y) | x ∈ X, G(x, y) 0, y ∈ argmin {f(x, y) | y ∈ Y, g(x, y) 0}}, n m n+m where X ⊆ » , Y ⊆ » , F, G, f, g : » ». This is a mathematical program involving two group of n m variables x ∈ » , y ∈ » that contains an optimization problem in its constraints: y solves the second optimization problem with x being parameters. The bilevel problem attracts attention of many researchers because of its scientific meaning and abilities to apply into practice. We present the formulation and the origins of the bilevel programs, some their interesting properties, in particular pay attention to a special case of the linear bilevel programming problem. Finally we describe some applications in economics, resource allocation, transportation network design and to energy markets. Keywords: Bilevel Programming, Bilevel Linear Programming Problem, Multiple Objective Problem, Mathematical Programming, Stackelberg Game. Trường Đại học Thăng Long 122