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 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 đề 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óm 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ứ 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 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 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. 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 tối ưu hai cấp một mục tiêu: Trường Đại học Thăng Long 112 Kỷ yếu công trình khoa học 2015 – Phần I y,x min F(x, y) với điều kiện         ∈≤ ∈≤ .Yy,0)y,x(g )y,x(fmin đúng nghiêm y ,Xx,0)y,x(G 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 hai cấ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ể. 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 y,x min F(x, y) = x - 2y 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 y min {f(x, y) = x + y : x - y ≤ 0, - x - y ≤ 0}. 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 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 y,x min {x - 2y : - x + 3y - 4 ≤ 0, y ∈ P(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à miền cảm 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 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 Trường Đại học Thăng Long 114 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 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 đó. 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 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 y,x min {F(x, y) = (2y1 + 3y2)x1 + (4y1 + y2)x2} 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 y min {f(x, y) = - (x1 + 3x2)y1 - (4x1 + 2x2)y2 : y1 + y2 = 1, y1 ≥ 0, y2 ≥ 0}. 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 yˆ (x) =      > ==+ + .xkhi)1,0( ,xkhi1yy ,xhayx2x4x3xkhi)0,1( 4 1 1 4 1 121 4 1 12121 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 x min F =      >+ =≤≤+ <+ 4 1 121 4 1 112 3 1 4 1 121 x;Xx3 x;)1y0(y2 x;x4x2 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 Tính toán cho thấy tại x = ( 41 , 43 ) 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 Kỷ yếu công trình khoa học 2015 – Phần I F = 2y1 + 23 , do đó F ∈ [ 23 , 27 ] (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. y,x min {f(x, y) = - (x1 + 3x2)y1 - (4x1 + 2x2)y2} 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 y min {F(x, y) = (2y1 + 3y2)x1 + (4y1 + y2)x2 : x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0}. 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 xˆ (y) =      < ==+ >+<+ .ykhi)1,0( ,ykhi1xx ,yhayyy4y3y2khi)0,1( 2 1 1 2 1 121 2 1 12121 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 y min f =      <−− =+−−− >−− 2 1 121 2 1 12111 2 1 121 y;y2y3 y;y)2x2(y)x23( y;y4y 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 Tại y* = ( 21 , 21 ) 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 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ụ 2 Ví dụ 3 Điểm cân bằng Nghiệ m x ( 41 , 4 3 ) x1 + x2 = 1 ( 41 , 43 ) Chi phí F 1,5 2,5 2,5 Nghiệ m y (0, 1) ( 21 , 2 1 ) ( 21 , 21 ) Chi phiis f - 2,5 - 2,5 - 2,5 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) y,x min F(x, y) = c1x + d1y với các điều kiện          ∈≤+ += ∈≤+ .Yy,byBxA ydxc)y,x(fmin đúng nghiêm y ,Xx,byBxA 222 22 y 111 , trong đó X ⊂ n, Y ⊂ m, x, c1, c2 ∈ n, y, d1, d2 ∈ m, 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: • Miền ràng buộc của bài toán (BLPP): S = {(x, y) : x ∈ X, y ∈ Y, A1x + B1y ≤ b1, A2x + B2y ≤ b2}. • Tập chấp nhận đượ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}. • Tập nghiệm tối ưu (còn gọi là tập phản ứ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)}}. • Tập chấp nhận được (còn gọi là miền cảm sinh) của bài toán (BLPP): Trường Đại học Thăng Long 118 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 tối ưu một cấp 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 0x min ≥ F(x, y) = x - 4y với điều kiện 0y min ≥ {f(y) = y : - x - y ≤ - 3, - 2x + y ≤ 0, 2x + y ≤ 12, - 3x + 2y ≤ - 4}. 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. Tập chấp nhận được M của bài toán (BLPP) là tập nghiệm của một ràng buộc đẳng thức tuyến tính từng khúc và tạo nên bởi giao của S vơi một số siêu phẳng tựa của S. Định lý 2. Nghiệm tối ưu (x*, y*) của bài toán (BLPP) đạt tại một đỉnh của tập 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 Kỷ yếu công trình khoa học 2015 – Phần I y min {f( xˆ , y) : g( xˆ , y) ≤ 0} là ∇yf( xˆ , y*) - µΤ∇yg( xˆ , y*) = 0, µΤg( xˆ , y*) = 0, µ ≥ 0. Bài toán cấp dưới Yy min ∈ {f(x, y) = c2x + d2y : A2x + B2y ≤ b2, y ≥ 0} = Yy min ∈ {f(x, y) = c2x + d2y : b2 - A2x - B2y ≥ 0, y ≥ 0} đượ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): d2 + 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) Xx min ∈ {F(x, y) = c1x + d1y} với các điều kiện A1x + B1y ≤ b1, uB2 - v = - d2, 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. y,Xx min ∈ {F(x, y) : G(x, y) ≤ 0, g(x, y) ≤ 0, f(x, y) - ϕ (x) ≤ 0}, trong đó ϕ(x) := y min {f(x, y) : g(x, y) ≤ 0}. Để 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 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à 1x max {x1p(∑ = n 1i ix ) - f1(x1)} với điều kiện xi ∈ ix maxarg {xip(∑ = n 1i ix ) - fi(xi)}, i = 2, ... , n. 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 Kỷ yếu công trình khoa học 2015 – Phần I [4]. Eichfelder G. (2008), Multiobjective Bilevel Optimization, Mathematical Programming, Vol. 123, No.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}}, where X ⊆ n, Y ⊆ m, F, G, f, g : n+m → . This is a mathematical program involving two group of variables x ∈ n, y ∈ m 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