Tính đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằng

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

Thêm vào BST

Báo xấu

34
lượt xem 2
download

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

Bài viết xây dựng và nghiên cứu một mô hình đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằng. Đầu tiên chúng đề xuất mô hình đối ngẫu dạng Wolfe và cung cấp một ví dụ để minh họa cho mô hình đối ngẫu. Thứ hai, chúng tôi thiết lập các định lí về tính đối ngẫu mạnh và tính đối ngẫu yếu cho cặp bài toán gốc (LOPEC) và bài toán đối ngẫu dạng Wolfe (DWLOPEC).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tính đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằng

UED Journal of Social Sciences, Humanities & Education – ISSN 1859 - 4603 TẠP CHÍ KHOA HỌC XÃ HỘI, NHÂN VĂN VÀ GIÁO DỤC TÍNH ĐỐI NGẪU DẠNG WOLFE CHO BÀI TOÁN TỐI ƯU TUYẾN TÍNH VỚI RÀNG BUỘC CÂN BẰNG Nhận bài: 15 – 10 – 2018 Trần Văn Sựa*, Lê Xuân Hòab Chấp nhận đăng: 25 – 12 – 2018 Tóm tắt: Đối ngẫu có vai trò quan trọng trong nghiên cứu các bài toán quy hoạch toán học vì tính đối http://jshe.ued.udn.vn/ ngẫu yếu cung cấp một chặn dưới đối với hàm mục tiêu của bài toán ban đầu (hay bài toán gốc). Trong bài báo này chúng tôi xây dựng và nghiên cứu một mô hình đối ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với ràng buộc cân bằng. Đầu tiên chúng đề xuất mô hình đối ngẫu dạng Wolfe và cung cấp một ví dụ để minh họa cho mô hình đối ngẫu. Thứ hai, chúng tôi thiết lập các định lí về tính đối ngẫu mạnh và tính đối ngẫu yếu cho cặp bài toán gốc (LOPEC) và bài toán đối ngẫu dạng Wolfe (DWLOPEC). Cuối cùng chúng tôi trình bày một ví dụ để mô tả kết quả về tính đối ngẫu mạnh trong giấy. Từ khóa: bài toán tối ưu tuyến tính với ràng buộc cân bằng; đối ngẫu dạng Wolfe; định lí đối ngẫu mạnh; định lí đối ngẫu yếu; ánh xạ tuyến tính. bài toán đối ngẫu “max”. Ma trận ràng buộc bài toán 1. Giới thiệu gốc “min” được chuyển thành ma trận chuyển vị của Đối ngẫu là một chủ đề quan trọng trong nghiên cứu bài toán đối ngẫu “max” và ngược lại. Tuy nhiên, mô các bài toán quy hoạch toán học, chẳng hạn tính đối hình đối ngẫu trên lại không phù hợp với lớp bài toán ngẫu yếu cung cấp giá trị chặn dưới cho hàm mục tiêu. tối ưu tuyến tính với ràng buộc cân bằng. Đối với mô Tương tự như trong bài toán quy hoạch tuyến tính tổng hình đối ngẫu dạng Wolfe (xem Wolfe [4]), tính đối quát, khi thiết lập một mô hình đối ngẫu cho bài toán ngẫu giữa các biến không xảy ra, đây là vấn đề thuận ban đầu (hay còn gọi là bài toán gốc), các định lí về tính lợi để xây dựng các thuật toán với thời gian chạy đối ngẫu yếu và tính đối ngẫu mạnh cho cặp bài toán gốc chương trình nhanh hơn. và bài toán đối ngẫu luôn giữ một vai trò chủ đạo và Gần đây, thông qua các tài liệu trình bày về mô thường được nghiên cứu trước tiên, xem, chẳng hạn [1, hình đối ngẫu dạng Wolfe (xem [1,2,3,4,5]), ta thấy 2, 3, 4, 5]. rằng khi xây dựng một mô hình đối ngẫu dạng Wolfe Trong bài toán quy hoạch tuyến tính tổng quát, cần công cụ là các đạo hàm theo hướng và dưới vi phân tính đối ngẫu được thiết lập phụ thuộc vào biến và dấu, phù hợp để thiết lập mô hình đối ngẫu cũng như các nghĩa là bài toán gốc chọn biến x, bài toán đối ngẫu định lí đối ngẫu mạnh và yếu. Tuy nhiên đối với các chọn biến y, dấu của y phụ thuộc vào ràng buộc đẳng hàm tuyến tính, đạo hàm theo hướng đạt được ngay tại thức hay bất đẳng thức của bài toán gốc và ngược lại. phương lấy đạo hàm. Do đó, chúng ta không cần sử Các hệ số của hàm mục tiêu của bài toán gốc được lấy dụng một công cụ đạo hàm nào hay dạng dưới vi phần làm chặn trên của bài toán đối ngẫu “max” và chặn nào áp đặt lên bài toán đối ngẫu dạng Wolfe, mà có thể dưới của bài toán gốc “min” được chọn làm hệ số của xây dựng trực tiếp mô hình đối ngẫu dạng Wolfe như trong bài toán quy hoạch tuyến tính tổng quát. aTrường Đại học Quảng Nam Mục đích của chúng tôi trong bài báo này là đề bTrường Đại học Kiến trúc Đà Nẵng xuất mô hình đối ngẫu dạng Wolfe cho bài toán tối ưu * Tác giả liên hệ Trần Văn Sự tuyến tính với ràng buộc cân bằng. Tiếp theo chúng tôi Email: tranuu63@gmail.com Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 8, số 4 (2018), 27-33 | 27
Trần Văn Sự, Lê Xuân Hòa nghiên cứu các định lí về tính đối ngẫu mạnh và về tính Chúng ta xét bài toán bài toán tối ưu tuyến tính với đối ngẫu yếu của cặp bài toán gốc và bài toán đối ngẫu ràng buộc cân bằng: dạng Wolfe. Kết quả thu được của chúng tôi trong bài ( LOPEC ) : min f ( x) xC báo này là mới và chưa từng được nghiên cứu trước đây, và trong tương lai chúng có thể được xem xét mở g ( x)  0, h( x) = 0, rộng để nghiên cứu cho lớp bài toán quy hoạch phi G( x)  0, H ( x)  0, tuyến với ràng buộc cân bằng.  G( x), H ( x) = 0. Trong đó: f : ¡ q →¡ , g:¡ q → ¡ m, 2. Cơ sở lí thuyết 2.1. Các kí hiệu h: ¡ q → ¡ n, G : ¡ q → ¡ p, H : ¡ q →¡ p Kí hiệu là các hàm tuyến tính. Tập chấp nhận được của ¥ : Tập các số tự nhiên; (LOPEC) là K với ¡ : Tập các số thực;  x  C : g ( x)  0, h( x) = 0,     x, y = x y với mọi x, y  ¡ , trong đó s là số T s K :=  G( x)  0, H ( x)  0, .   G( x), H ( x) = 0  tự nhiên, ở đây xT là ma trận cột của vectơ dòng x,   X, Y: Không gian Banach thực, Ở đây C là tập con khác rỗng trong ¡ q , các hàm . : Chuẩn trong không gian Banach thực. ràng buộc được mô tả ở dạng g = ( g1 ,..., gm ) : ¡ q → ¡ m, 2.2. Các định nghĩa Định nghĩa 2.2.1. Một ánh xạ f : X → Y được h = (h1 ,..., hn ) : ¡ q → ¡ n, gọi là tuyến tính nếu G = (G1 ,..., G p ) : ¡ q → ¡ p, f (ax + by ) = af ( x) + bf ( y) H = ( H1 ,..., H p ) : ¡ q → ¡ p. x, y  X , a, b  ¡ . Chú ý các thành phần bên trong mỗi hàm số là một Định nghĩa 2.2.2. Xét bài toán gốc (P): hàm vô hướng trên ¡ q . Cho trước một vectơ chấp min f ( x) với x  K  X . nhận được x  K , ta kí hiệu các tập chỉ số: Ta nói rằng: a) Vectơ x  K là một nghiệm tối ưu toàn cục của  I g = I g ( x) = i = 1...m : gi ( x) = 0 ;  bài toán gốc (P) nếu   A = A( x) = i = 1... p : Gi ( x) = 0, H i ( x)  0 ; f ( x)  f ( x) x  K. B = B( x) = i = 1... p : G ( x) = 0, H ( x) = 0 ; i i b) Vectơ x  K là một nghiệm tối ưu địa phương C = C ( x) = i = 1.. p : G ( x)  0, H ( x) = 0. i i của bài toán gốc (P) nếu Bài toán đối ngẫu dạng Wolfe cho bài toán gốc  f ( x)  f ( x) x  K  y  X : y − x   với  số (LOPEC), kí hiệu (DWLOPEC) và xác định như sau dương  nào đấy. (xem [1, 4]) :  (  jh −  hj ) h j (u)  n Chú ý 1: Bài toán “max” được định nghĩa một cách tương tự.   i g g i (u ) +  ( DWLOPEC ) :m ax  g  iI j =1 u,     + f (u ) −  ( iG Gi (u ) + iH H i (u ) )  p Chú ý 2: Mỗi vectơ x  K được gọi là điểm chấp nhận được cho bài toán gốc (P).  i =1  sao cho 3. Mô hình đối ngẫu dạng Wolfe 28
ISSN 1859 - 4603 - Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 8, số 4 (2018), 27-33 5v1 − 3v2 + 1g ( v1 − v2 ) f (v) +  ig gi (v) +  (  jh −  hj ) h j (v) n iI g j =1 + ( 1h − 1h ) ( v1 + v2 ) − 1G v2   −   ( iG Gi (v) + iH H i (v) )  p − 1H v1  0  ( v1 , v2 )  C − ( u1 , u2 ) ;  i =1  1g  0, 1h  0,  0 v  C − u ; 1h  0, 1G  0, 1H  0,   0 i  I g ;  ,   0 j = 1, 2,..., n; i g h j h j − 1  ui  1, i = 1, 2. iG , iH , iG , iH  0 i = 1, 2,..., p; Kí hiệu các tập chỉ số CG = AH = CG =  AH = 0, A+ = i  A : iG  0 ; i  B, iG = iH = 0, u  C , CG = ( cG ) , AH = ( aH ) , C+ = i  C : iH  0 ; cC a A CG = ( cG )cC ,  AH = ( aH )aA , BG = i  B : iH = 0, iG  0 ;  = (h , G ,  H )  ¡ n+2 p , BH = i  B : iG = 0, iH  0 .  = ( g ,  h , G ,  H )  ¡ m+n+2 p . Một định lí đối ngẫu yếu cho bài toán gốc (LOPEC) và bài toán đối ngẫu dạng Wolfe Mô hình đối ngẫu dạng Wolfe (DWLOPEC) trên (DWLOPEC) sẽ được phát biểu: được mô tả bằng một ví dụ số sau: Định lí 3.1 (Đối ngẫu yếu). Cho x là chấp nhận Ví dụ 1. Cho q = 2, C = [ − 1, 1]  −1, 1 , m = n = p = 1. Xét bài toán tối ưu tuyến tính với ràng được cho bài toán gốc (LOPEC) và ( u,  ) là chấp nhận được cho bài toán đối ngẫu dạng Wolfe buộc cân bằng (LOPEC) trên không gian ¡ 2 và được (DWLOPEC). Khi đó, nếu BG  BH  A+  C+ =  mô tả như sau: thì với mọi vectơ chấp nhận được x của bài toán gốc ( LOPEC ) : min f ( x) = 5 x1 − 3 x2 ( x1 , x2 ) C (LOPEC), ta có g ( x) = x1 − x2  0, f ( x)  f (u ) +  ig gi (u ) +  (  jh −  hj ) h j (u ) n h( x) = x1 + x2 = 0, iI g j =1 G ( x) = x2  0, −  ( iG Gi (u ) + iH H i (u ) ) p H ( x) = x1  0, i =1  G ( x), H ( x) = x1 x2 = 0. Chứng minh: Vì f là hàm tuyến tính nên Khi đó tập chấp nhận được K = (0, 0). Chọn f ( x − u ) = f ( x) − f (u ). (3.1) vectơ chấp nhận được x = (0,0) và ta có Do g, h, G, H là các hàm tuyến tính nên các thành I g = 1 , A = C =  , B = 1. Khi đó mô hình đối phần bên trong là các hàm vô hướng tuyến tính. Do đó, ta có ngẫu dạng Wolfe của bài toán gốc (LOPEC) là bài toán (DWLOPEC) có dạng: gi ( x − u) = gi ( x) − gi (u ) i  I g . (3.2) 5u1 − 3u2 + 1g ( u1 − u2 )  h j ( x − u) = h j ( x) − h j (u)   m ax  + ( 1h − 1h ) ( u1 + u2 )  j = 1,2,.., n. (3.3) u1 ,u2 , 1g , 1h , 1G , 1H    − 1G u2 − 1H u1  (−hj )( x − u) = (−h j )( x) − (−h j )(u) sao cho (3.4) j = 1,2,.., n. 29
Trần Văn Sự, Lê Xuân Hòa (−Gi )( x − u) = (−Gi )( x) − (−Gi )(u) Từ các điều kiện (3.7)-(3.8) dẫn đến i  A  B. (3.5) f ( x) − f (u ) +  ig g i ( x) −  ig g i (u ) iI g iI g (− Hi )( x − u) = (− Hi )( x) − (− Hi )(u) +  j =1...n h j h j ( x) −  j =1...n h j h j (u ) (3.6) i  C  B. +   hj (−h j )( x) −   hj (−h j )(u ) (3.9) j =1...n j =1...n Theo giả thiết BG  BH  A+  C+ =  , ta nhân p p +  iG ( −Gi ) ( x) − iG ( −Gi ) (u ) lần lượt từng phương trình (3.2), (3.3), (3.4), (3.5) và i =1 i =1 (3.6) cho các vô hướng p p +  iH ( − H i ) ( x) − iH ( − H i ) (u )  0.   0 i  I g ;   0 i = 1, 2,..., n; i g i h i =1 i =1   0 i = 1, 2,..., n;   0 i  A  B; i h i G Do x là chấp nhận được của bài toán (LOPEC) nên   0 i  B  C , và sau đó cộng dồn chúng lại với H các bất đẳng thức sau xảy ra: i nhau, ta nhận được kết quả gi ( x)  0 i  I g ( x), (3.10) f ( x) − f (u ) +  ig g i ( x) −  ig g i (u ) h j ( x) = 0 j = 1, 2,..., n, (3.11) iI g iI g Gi ( x)  0 i = 1, 2,..., p, (3.12) +  h j h j ( x) −  h j h j (u ) j =1...n j =1...n H i ( x)  0 i = 1, 2,..., p. (3.13) +  j =1...n  (−h j )( x) − h j  j =1...n  (−h j )(u ) h j Kết hợp các điều kiện (3.10), (3.11), (3.12) và (3.13) ta nhận được bất đẳng thức đúng sau: p p +  iG ( −Gi ) ( x) − iG ( −Gi ) (u )  iI g i g gi ( x) +  j =1...n h j h j ( x) i =1 i =1 +  p p +  h (−h j )( x) ( − H i ) ( x) −  ( − H i ) (u ) H H j j =1...n i i i =1 i =1 p (3.14) +  iG ( −Gi ) ( x) = f (u − x) +  ig gi ( x − u ) i =1 iI g p +  iH ( − H i ) ( x)  0. + (  −  ) h ( x − u) n h h (3.7) i =1 i i i i =1 p p Kết hợp điều kiện có trong (3.9) và (3.14), sau khi +  iG ( −Gi ) ( x − u ) +  iH ( − H i ) ( x − u ). nhân vế trái của (3.14) với (-1), bất đẳng thức đổi i =1 i =1 chiều, ta suy ra được kết quả như sau: Theo giả thiết ( u,  ) là vectơ chấp nhận được cho f ( x)  f (u ) +  ig gi (u ) bài toán đối ngẫu dạng Wolfe (DWLOPEC) và ngoài ra iI g x − u  C − u , ta có đánh giá sau: +  j =1...n h j h j (u ) +  j =1...n  hj (−h j )(u ) f (u − x) +  ig g i ( x − u ) p p iI g +  iG ( −Gi ) (u ) +  iH ( − H i ) (u ) i =1 i =1 +  ( ih − ih ) hi ( x − u ) n  i =1 (3.8) −   ig gi ( x) +   jh h j ( x) p  iI g j =1...n +  iG ( −Gi ) ( x − u ) i =1 p p +  iH ( − H i ) ( x − u )  0. +  j =1...n h j (−h j )( x) +  iG ( −Gi ) ( x) i =1 i =1 30
ISSN 1859 - 4603 - Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 8, số 4 (2018), 27-33 p   f (v )  0 +  iH ( − H i ) ( x)     gi (v)  0 i  I g , i =1  f (u ) +  ig gi (u )  iI g (−Gi )(v)  0 i  A  B, (− H )(v)  0 i  B  C , +  h j h j (u ) +   hj (−h j )(u )  i j =1...n j =1...n  v  C − x. p p +  iG ( −Gi ) (u ) +  iH ( − H i ) (u ) i =1 i =1 Áp dụng Định lí 2.12 trong Giáo trình của Rockafeller [6], khi đó tồn tại các vectơ chấp nhận = f (u ) +  ig gi (u ) +  (  jh −  hj ) h j (u ) n iI g j =1 được ( , ,  )  ¡ 1+ m+ 4 p , trong đó  ¡ +, −  ( iG Gi (u ) + iH H i (u ) ). p i =1  = ( g , G ,  H )  ¡ m+2 p , Vậy, bất đẳng thức cuối cùng nhận được là  = ( G ,  H )  ¡ 2p , f ( x)  f (u ) +  ig gi (u ) +  (  jh −  hj ) h j (u ) n và chúng không đồng thời bằng 0, thỏa mãn bất đẳng iI g j =1 thức sau đây : −  ( iG Gi (u ) + iH H i (u ) ). p  f (v) +  ig gi (v) i =1 iI g Điều này kết thúc chứng minh. p +  iG ( −Gi ) (v) (3.15) Tiếp theo chúng tôi phát biểu một định lí đối ngẫu i =1 mạnh cho bài toán gốc (LOPEC) trong trường hợp bỏ p +  iH ( − H i ) (v)  0 v  C − x. ràng buộc đẳng thức h( x) = 0 . i =1 Định lí 3.2 (Đối ngẫu mạnh). Cho x  K là Mặt khác, theo giả thiết ban đầu tồn tại vectơ nghiệm tối ưu địa phương cho bài toán gốc (LOPEC). v  C − x thỏa mãn h  0, vC − x gi (v)  0 i  I g , Giả sử và tồn tại sao cho (3.16) gi (v)  0 i  I g , (−Gi )(v)  0 i  A  B và (− H i )(v)  0 i  B  C. Khi đó, nếu điều kiện (−Gi )(v)  0 i  A  B , (3.17) B  B  A  C =  G H + + thì tồn tại một vectơ (− H i )(v)  0 i  B  C. )¡ và (3.18) ( =  , , g G H m+2 p sao cho ( x,  ) là nghiệm Kết hợp các điều kiện (3.15), (3.16), (3.17) và tối ưu của bài toán đối ngẫu dạng Wolfe (DWLOPEC) và (3.18) ta nhận được   0. Không mất tính tổng quát giá trị hàm mục tiêu của chúng tương ứng bằng nhau. của bài toán ta chọn các giá trị vô hướng  = 1 và Chứng minh: Do x  K là nghiệm tối ưu địa  =  . Áp dụng Định lí 3.1, với mọi vectơ ( u,  ) là phương của bài toán gốc (LOPEC) nên hệ bất đẳng nghiệm chấp nhận được của bài toán đối ngẫu dạng thức sau không xảy ra: Wolfe (DWLOPEC), bất đẳng thức dưới đây đúng: 31
Trần Văn Sự, Lê Xuân Hòa f ( x)  f (u ) +  ig gi (u )  1 chọn vectơ v =  2,   C , lúc này các bất đẳng thức iI g  2 p +  iG ( −Gi ) (u ) (3.19) (3.16), (3.17) và (3.18) đúng. Do đó tất cả các giả thiết i =1 trong Định lí 3.2 được thỏa mãn. Lúc này một mô hình p đối ngẫu dạng Wolfe cho bài toán gốc (LOPEC là bài +  iH ( − H i ) (u )  0. i =1 toán đối ngẫu (DWLOPEC) có dạng: Mặt khác, không khó kiểm tra được kết quả: u1 + 1g ( u2 − u1 )    f ( x) = f ( x) +  ig gi ( x) ( DWLOPEC) : m ax  +u2 − 1G ( 3u2 − u1 )  1g , 1G , 1H   u1 , u2 , iI g (3.20)  − 1H u1  p p +  iG ( −Gi ) ( x) +  iH ( − H i ) ( x). sao cho i =1 i =1 v1 + v2 + 1g ( v2 − v1 ) Kết hợp (3.19) và (3.20) ta thu được − 1G ( 3v2 − v1 ) − 1H v1 f ( x) +  ig gi ( x) iI g  0  ( v1 , v2 )  C − ( u1 , u2 ) ; 1g  0, 1G  0, 1H  0, p p +  iG ( −Gi ) ( x) +  iH ( − H i ) ( x) i =1 i =1 0  ui  3, i = 1, 2.  f (u ) +   gi (u ) i g iI g   H = 0, 1G  0 p p Giả sử không xảy ra  1G , +  iG ( −Gi ) (u ) +  iH ( − H i ) (u ).  1 = 0, 1  0 H i =1 i =1 nghĩa là ( ) Vậy x,  là nghiệm tối ưu của bài toán đối ngẫu BG  BH  A+  C+ = . dạng Wolfe (DWLOPEC), và giá trị hàm mục tiêu của chúng tương ứng bằng nhau. Khi đó, áp dụng Định lí 3.2, tồn tại vectơ Cuối cùng chúng tôi cung cấp một ví dụ để minh ( g =  , , G H )¡ 3 ( sao cho x,  ) là nghiệm tối họa kết quả đạt được bên trên như sau: ưu của bài toán đối ngẫu dạng Wolfe (DWLOPEC) và Ví dụ 2. Cho q = 2, C = 0, 3 , m = p = 1. Xét 2 giá trị hàm mục tiêu của chúng tương ứng bằng nhau. bài toán tối ưu tuyến tính với ràng buộc cân bằng Thật vậy, chúng ta thử lại kết quả trực tiếp như sau. Ta (LOPEC) trên ¡ 2 sau: có x = (0,0) là nghiệm tối ưu của bài toán gốc ( LOPEC ) : min f ( x) = x1 + x2 (LOPEC) và giá trị hàm mục tiêu f ( x) = 0. Tiếp theo, ( x1 , x2 )  C g ( x) = x2 − x1  0, bằng phương pháp giải trực tiếp bài toán đối ngẫu dạng Wolfe (DWLOPEC), chúng ta cũng tìm được một G ( x) = 3x2 − x1  0, nghiệm tối ưu cho bài toán đối ngẫu dạng Wolfe là H ( x) = x1  0,  G ( x), H ( x) = ( 3x2 − x1 ) x1 = 0. (u,  ) = ( 0, 0, 2,1, 0) Tập chấp nhận được cho bài toán (LOPEC) là và giá trị hàm mục tiêu K = ( 3a, a )  ¡ : 0  a  1. Quan sát hàm mục tiêu 2 f (u ) +   i gi (u ) g iI g f ( x) = 3 x1 + x2 ta dễ dàng thấy rằng nghiệm tối ưu của ( ) p −  Gi (u ) +  i H i (u ) = 0. G H bài toán gốc (LOPEC) là x = (0,0) . Kiểm tra khái i i =1 niệm các tập chỉ số ta nhận được Vậy định lí 3.2 được kiểm tra. I g = 1 , A = C =  , B = 1. Vì x = (0,0) nên ta 32
ISSN 1859 - 4603 - Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 8, số 4 (2018), 27-33 Nhận xét 3.1. Trong trường hợp C = ¡ q + (nón toàn mới và trong tương lai các kết quả này có thể orthant không âm) và H = 0 hoặc G = 0 thì bài toán được áp dụng để xây dựng thuật toán số giải các bài toán tối ưu tuyến tuyến với ràng buộc cân bằng (LOPEC) trở thành bài toán quy hoạch tuyến tính tổng (LOPEC) và bài toán đối ngẫu của nó dạng Wolfe quát dạng “min” sau (xem [7, tr.14]): (DWLOPEC). ( LOPEC ) : min f ( x) g ( x)  0, Tài liệu tham khảo G ( x)  0 ( H ( x)  0), [1] R. I. Bot, S. -M. Grad (2010). Wolfe duality and h( x) = 0, Mond-Weir duality via perturbations. Nonlinear Anal. Theory Methods Appl., 73(2), 374-384. x  0. [2] S. Dempe, A. B. Zemkoho (2012). Bilevel road Do đó, kết quả thu được bên trên có thể áp dụng pricing: Theoretical analysis and optimality conditions. Ann. Oper. Research, 196, 223-240. trực tiếp cho bài toán quy hoạch tuyến tính tổng quát [3] Z. Q. Luo, J. S. Pang, D. Ralph (1996). dạng “min” và thậm chí là cả bài toán vận tải và bài Mathematical problems with equilibrium constraints. toán bán hàng và nhiều bài toán thực tế khác với điều Cambridge University Press, Cambridge. kiện cả hàm mục tiêu và các hàm ràng buộc đều là các [4] P. Wolfe (1961). A duality theorem for nonlinear hàm tuyến tính. programming. Q. J. Appl. Math, 19, 239-244. [5] J. J. Ye (2005). Necessary and sufficient 4. Kết luận optimality conditions for mathematical program with equilibrium constraints. J. Math. Anal. Appl., Bài báo đã xây dựng một cách đầy đủ mô hình đối 307, 350-369. ngẫu dạng Wolfe cho bài toán tối ưu tuyến tính với [6] R. T. Rockafellar (1970). Convex Analysis. ràng buộc cân bằng (LOPEC). Chứng minh hai định lí Princeton Univ. Press, Princeton. về tính đối ngẫu yếu và tính đối ngẫu mạnh cho bài [7] Phí Mạnh Ban (2015). Quy hoạch tuyến tính, toán gốc (LOPEC) và bài toán đối ngẫu dạng Wolfe NXB Đại học Sư phạm. (DWLOPEC). Kết quả đạt được trong bài báo là hoàn WOLFE TYPE DUALITY FOR LINEAR OPTIMIZATION PROBLEMS WITH EQUILIBRIUM CONSTRAINTS Abstract: Duality has an important role in the study of mathematical programming problems , since the weak duality provides a lower bound to the objective function of the primal problem (or the original problem). In this article, we formulate and investigate a Wolfe type duality model for linear optimization problems with equilibrium constraints. Firstly, we propose the Wolfe type duality model and give an example to illustrate the given dual model. Secondly, we establish the weak duality and strong duality theorems for a pair of the primal problem (LOPEC) and the Wolfe type dual problem (DWLOPEC). Finally, we present an example to illustrate the strong duality result in the paper. Key words: linear optimization problem with equilibrium constraints; wolfe type duality; strong duality theorem; weak duality theorem; linear mappings. 33