Đối ngẫu liên hợp cho bài toán tối ưu và ứng dụng - Trần Văn Thắng

Trần Văn Thắng Tạp chí KHOA HỌC & CÔNG NGHỆ 128(14): 55 - 59 55 ĐỐI NGẪU LIÊN HỢP CHO BÀI TOÁN TỐI ƯU VÀ ỨNG DỤNG Trần Văn Thắng* Trường Đại học Điện lực TÓM TẮT Trong bài báo này, chúng tôi đưa ra đối ngẫu liên hợp cho các bài toán tối ưu tựa lõm với hàm mục tiêu là các hàm sản xuất Cobb-Douglas. Sau đó, chúng tôi ứng dụng kết quả đối ngẫu đạt được để nghiên cứu một số bài toán trong kinh tế. Từ khoá: Hàm sản xuất Cobb-Douglas, Đối ngẫu liên hợp GIỚI THIỆU* Gần đây, lý thuyết đối ngẫu mà được xây dựng dựa trên phép biến đổi tựa liên hợp của hàm : nf   dạng * 1( ) [sup{ ( ) | 1, 0}] T np f x p xf x p      bởi TS. P. T. Thạch đã được ứng dụng cho một số bài toán tối ưu trong kinh tế và thu được những kết quả đáng chú ý ([5], [7], [8], [9]). Mục đích của bài báo này là mở rộng đối ngẫu liên hợp cho bài toán tối ưu vô hướng và tối ưu đa mục tiêu với hàm mục tiêu là các hàm sản xuất Cobb-Douglas. Sau đó, chúng tôi ứng dụng kết quả đối ngẫu để nghiên cứu tìm phương án sản xuất cho một số bài toán trong kinh tế như: Bài toán với một ràng buộc phân bố nguồn lực, bài toán với nhiều ràng buộc phân bố nguồn lực và bài toán tối ưu với các ràng buộc phân bố nguồn lực. ĐỐI NGẪU LIÊN HỢP Cho ( )f x là hàm số không âm, nhận giá trị hữu hạn trên n  . Định nghĩa 1.1 (xem [5]). Hàm *f được gọi là tựa liên hợp của f nếu * 1( ) [sup{ ( ) | 1, 0}] T np f x p xf x p      (quy ước 1/ 0  ). Cho các hàm sản xuất Cobb-Douglas   1 21 2( ) ... n nf x x x x và   1 21 2( ) ... n ng p p p p , với 1 20 , ... 1i ni         . Mệnh đề 1.2 (xem [7]). Hàm f và g liên hợp với nhau theo nghĩa: 1 2 1 1 2( ) ... [sup{ ( ) : 1, 0}] n T ng p f x p x x        , * Tel: 1 2 1 1 2( ) ... [sup{ ( ) : 1, 0}] n T nf x g p p x p        . Cho X là tập lồi, đóng, bị chặn có thứ nguyên đầy đủ trong Rn+ và thoả mãn điều kiện bỏ đi được: ',0x X x x   ' .x X  Định nghĩa P là liên hợp dưới của X:  : 1, .n TP p p x x X     Dễ thấy P cũng là tập lồi, đóng, bị chặn có thứ nguyên đầy đủ trong Rn+ và thoả mãn điều kiện bỏ đi được. Ngoài ra, chúng ta có Bổ đề 1.3 (xem [7]). X là liên hợp dưới của P :  : 1, .n TX x p x p P     Sau đây, chúng ta quan tâm đến bài toán tối ưu: max ( ), f x v.đ.k x X (1) và bài toán đối ngẫu: max ( ),g p v.đ.k p P . (2) Vì X và P là liên hợp dưới với nhau, f và g liên hợp với nhau, do đó, cặp bài toán (1) và (2) là đối hợp. Mệnh đề 1.4. (xem [8]) Cho *x X và *p P . Nếu 1 2* * 1 2( ) ( ) ... n nf x g p     , thì *x là nghiệm của (1) và *p là nghiệm của (2). Đặt 1( ) [ ( ) ]Tf x f x x    , 1( ) [ ( ) ]Tg p g p p    Chúng ta có định lý đối ngẫu sau. Định lý 1.5. (xem [8]) Nếu *x là nghiệm của (1) thì * *( )p f x là nghiệm của (2). Đảo lại, Nếu *p là nghiệm của (2) thì * *( )x f p là nghiệm của (1). Tiếp theo, chúng ta sẽ mở rộng đối ngẫu liên hợp cho bài toán tối ưu đa mục tiêu. Trần Văn Thắng Tạp chí KHOA HỌC & CÔNG NGHỆ 128(14): 55 - 59 56 Với mỗi 1 2 , ,...,r k , ta lấy véctơ  r sao cho 1 20 1         , ... r r r r j nj và đặt 1 2 1 2  ( ) ... rr r n r n f x x x x , 1 2 1 2  ( ) ... rr r n r n g x p p p . Xét bài toán tối ưu: 1 2max ( ( ), ( ),..., ( )) kf x f x f x , x X (3) và bài toán đối ngẫu: 1 2max (g ( ), ( ),..., ( )) kp g p g p , p P (4) Bổ đề 1.6 (xem [8]). *x X là nghiệm hữu hiệu Pareto của (3) nếu và chỉ nếu tồn tại   k sao cho *x là nghiệm tối ưu của bài toán 1 2 1 2max{ ( ) ( )... ( ) | } k kf x f x f x x X    (5) Tương tự, *p P là nghiệm hữu hiệu Pareto của (4) nếu và chỉ nếu tồn tại   k sao cho *p là nghiệm tối ưu của bài toán 1 2 1 2max{ ( ) ( )... ( ) | p } k kg p g p g p P    . (6) Cho *x là nghiệm hữu hiệu Pareto của (3) và *p là nghiệm hữu hiệu Pareto của (4). Khi đó, * *( , )x p được gọi là cặp nghiệm hữu hiệu Pareto gốc-đối ngẫu nếu tồn tại   k sao cho *x là nghiệm hữu hiệu Pareto của (5) và *p là nghiệm hữu hiệu Pareto của (6). Đặt  là tập gồm tất cả các véctơ:              1 21 2 ...| ,n kk       1 2 .. , 1. 0,k r r . Chúng ta có đối ngẫu cho cặp bài toán tối ưu đa mục tiêu bởi định lý sau. Định lý 1.7. Cho *x X và *p P . Nếu tồn tại   sao cho * *j j jx p  với mọi 1,2,...,j n thì * *( , )x p là cặp nghiệm hữu hiệu Pareto gốc-đối ngẫu. Chứng minh. Vì * *j j jx p  với mọi 1,2,...,j n ta có 1 2* * 1 2( ) ( ) ... n nf x g p     , theo Mệnh đề 1.4, *x là nghiệm của bài toán (1). Mặt khác, do   nên tồn tại   k sao cho    12 21 1 21 2( ) . ( ) (.. )... ( ) kn n kf x f x ff x x x xx Điều này suy ra *x là nghiệm của (5). Tương tự, ta cũng chỉ ra *p là nghiệm tối ưu của bài toán (6). Vậy, * *( , )x p được là cặp nghiệm hữu hiệu Pareto gốc-đối ngẫu. ỨNG DỤNG Bài toán với một ràng buộc phân bố nguồn lực Cho m véctơ i na  và n  thỏa mãn 0j  với mọi ,j 1 2 ... 1n      . Chúng ta xét hệ phi tuyến sau:       1 1 1 0, ,, m mi i i mi i x a m (7)    0, 1,2,..., , 1, 1,2,...,T ijp j n p a i m (8)  , 1,2,...,j j jp x a j n (9) Bài toán này có thể gặp trong việc lập kế hoạch hoạt động của một công ty có m nhà máy để sản xuất n hàng hoá khác nhau. Để sản xuất các hàng hoá này, một nguồn lực nhất định có tổng bằng 1 được phân bố cho các nhà máy. Giả sử i na  là véctơ đặc trưng cho năng lực của nhà máy thứ i , nghĩa là nhà máy thứ i chạy hết công suất có thể sản xuất được ija đơn vị hàng hóa thứ j , 1,2,...,j n . Số jp biểu thị phần nguồn lực được phân bố cho việc sản xuất một đơn vị hàng hóa thứ j và jx là tổng lượng hàng hóa thứ j cần sản xuất bởi cả công ty. Khi đó, j jp x là tổng nguồn lực được phân bố cho việc sản xuất hàng hóa thứ j , tức là giá vốn sản xuất lượng hàng hóa thứ j . Để đảm bảo khả năng cạnh tranh trên thị trường, cần thiết rằng   1,2,...,j j jp x a j n . Bài toán đặt ra là tìm một phương án hoạt động khả thi, tức là tìm một véctơ ( , ) n nx p    thỏa mãn hệ (7)-(9). Véctơ  được gọi là véctơ phân bố nguồn lực. Ký hiệu X là tập các véctơ  n x , thỏa mãn (7) và X là tập các véctơ thỏa mãn (8). Bổ đề 2.1.1 (xem [8]). Chúng ta có 0 1    { | }TP p p x x X Trần Văn Thắng Tạp chí KHOA HỌC & CÔNG NGHỆ 128(14): 55 - 59 57 { 0 | 1 }TX x p x p P      trong đó : { : , 0}X y x X x y      . Định lý 2.1.2. Nếu * *( , )x p là nghiệm của hệ (7)-(9), thì *x là nghiệm của (1) và *p là nghiệm của (2). Đảo lại, nếu *x là nghiệm của (1), thì * *( , )x p với * *( )p f x là nghiệm của hệ hệ (7)-(9); nếu *p là nghiệm của (2), thì * *( , )x p với * *( )x g p là nghiệm của hệ (7)-(9). Chứng minh. Cho * *( , )x p là nghiệm của hệ (7)-(9). Ta có * * 1,2,...j j jx p j n   , theo Mệnh đề 1.4, *x là nghiệm của bài toán (1) và *p là nghiệm của (2). Đảo lại, nếu *x là nghiệm của (1) và * *( )p f x thì *p thỏa mãn (8) và *p là nghiệm của (2). Do đó, * *( , )x p với là nghiệm của hệ hệ (7)-(9). Tương tự, nếu *p là nghiệm của (2), thì * *( , )x p với * *( )x g p là nghiệm của hệ hệ (7)-(9). Dễ thấy các bài toán (1) và (2) tương ứng tương đương với các bài toán cực đại hàm lõm sau: max{ln( ( )) : },f x x X (10) max{ln( ( )) : }.g p p P (11) Các hàm ln( ( ))f x và ln( ( ))g p là lõm chặt trên n nên nghiệm của các bài toán (10) và (11) là tồn tại duy nhất. Do đó, từ Định lý 2.1.2 chúng ta khẳng định nghiệm của hệ (7)- (9) là tồn tại và duy nhất, đồng thời nghiệm này có được bằng cách giải bài toán (10) hoặc (11). Chú ý rằng các bài toán (10) và (11) tương đương với các bài toán tối ưu lồi, nên việc giải các bài toán này đơn giản hơn việc giải hệ phi tuyến (7)-(9). Bài toán với nhiều ràng buộc phân bố nguồn lực Trong phần này, chúng ta xét bài toán mở rộng của (7)-(9) khi công ty có 1k nguồn lực được sử dụng để sản xuất n sản phẩm trong m nhà máy, với r là giá trị của nguồn lực thứ , 1,2,..,r r k . Không mất tính tổng quát ta có thể giả thiết rằng    1 1. k rr Giả sử  rj là phần nguồn lực thứ r được phân bố cho việc sản xuất sản phẩm thứ j và toàn bộ các nguồn lực được sử dụng hết, khi đó ta có 0 1rj  , 1 1 1, , .j r j n r k     Véctơ      1( , , ) n n với      1 k r j r j r (tổng giá trị các nguồn lực được sử dụng để sản xuất sản phẩm thứ j ),  1, , ,j n được gọi là véctơ phân bố các nguồn lực. Vậy  là tập gồm tất cả các véctơ phân bố các nguồn lực. Ứng với mỗi véctơ phân bố các nguồn lực   , véctơ nx  thỏa mãn (7)-(9) sẽ được gọi là một phương án sản xuất. Véctơ 1 ( , , )np p p với jp là tổng giá trị các nguồn lực được sử dụng để sản xuất một đơn vị hàng hóa thứ j (tức là giá vốn sản xuất của đơn vị hàng hóa thứ j ) sẽ được gọi là véctơ chi phí sản xuất đơn vị. Bài toán đặt ra là tìm phương án sản xuất nx  và véctơ chi phí sản xuất đơn vị  n p thỏa mãn 1 1( , , )n np x p x  . Điều đó có nghĩa là chúng ta cần giải hệ sau:       1 1 1 0, ,, m mi i i mi i x a m (12)    0 1,2,..., , 1 1,2,...,T ijp j n p a i m (13)   1,2,...,j j jp x j n (14)   . (15) Định lý 2.2.1. Giả sử * *( , )x p là cặp nghiệm hữu hiệu Pareto gốc-đối ngẫu. Khi đó, * *( , )x p là nghiệm của hệ (12)-(15). Chứng minh. Cho * *( , )x p là cặp nghiệm hữu hiệu Pareto gốc-đối ngẫu, nghĩa là tồn tại Trần Văn Thắng Tạp chí KHOA HỌC & CÔNG NGHỆ 128(14): 55 - 59 58 véctơ   k sao cho *x là nghiệm hữu hiệu Pareto của (5) và *p là nghiệm hữu hiệu Pareto của (6). Bằng cách chứng minh tương tự như ở Định lý 2.3 ta có *x là nghiệm của (1), *p là nghiệm của (2), trong đó 1 2 1 2 ... k k         . Theo Định lý 2.1.2, * *( , )x p là nghiệm của hệ (7)-(9). Từ Định lý 2.3 và Định lý 2.2.1 ta chỉ ra rằng bài toán với nhiều ràng buộc phân bố nguồn lực tương đương với bài toán tối ưu đa mục tiêu (3) hoặc (4). Tối ưu với các ràng buộc phân bố nguồn lực Xét bài toán max ( )q x (16)       1 1 1 0, ,, m mi i i mi i x a m , (17)    0, 1,2,..., , 1, 1,2,..., ,T iip i n p a i m (18)  , 1,2,...,i i ip x i n (19)   , (20) trong đó ( )q x là hàm lõm liên tục trên  n sao cho ( ) 0 x>0q x   . Nếu ( )q x là hàm biểu diễn lợi ích của công ty tại phương án sản xuất  n x thì (16) - (20) trở thành bài toán tìm phương án sản xuất sao cho lợi ích của công ty là lớn nhất. Ký hiệu EX là tập gồm các phương án sản xuất, lúc này bài toán (16)-(20) được viết lại như sau: max ( ) }{ | Eq x x X (21) Theo Định lý 2.3 và Định lý 2.2.1, EX cũng chính là tập nghiệm hữu hiệu Pareto của bài toán tối ưu đa mục tiêu (3). Do đó, (21) là bài toán tối ưu trên tập nghiệm hữu hiệu Pareto của bài toán tối ưu đa mục tiêu. Đối với bài toán dạng này đã có nhiều phương pháp giải được đưa ra (xem [3], [6]). Sau đây, chúng tôi sẽ sử dụng phương pháp được đưa ra trong các bài báo [5] để biến đổi (21) về bài toán cực đại hàm tựa lồi trên một tập lồi compắc trong không gian k chiều. Do đó, bài toán sau khi biến đổi có thể được giải bằng phương pháp xấp xỉ ngoài như ở [6]. Bằng cách đổi thang đơn vị nếu cần thiết, không mất tính tổng quát chúng ta có thể giả thiết rằng 1, ,min 2 i j n ja   với mọi 1,2,...,i m . Điều này dẫn đến 1, , min 2 .j n jx x X     Đặt  1 221| max ( ) ( )... ( ) 3rn x X rM f fx x xf        1 221 3    ( ) max ( ) | ( ) ( )... ( ) ,rrh q x x x xf f xf X .n   (quy ước max 0  ). Dễ thấy tập M là tập lồi compắc. Ngoài ra, ta có bổ đề sau: Bổ đề 2.3.1 (xem [8]). Hàm h là nửa liên tục trên và tựa lồi ở trên . k  Xét bài toán:   max ( ) | h M (22) Định lý 2.3.2. Giá trị tối ưu của các bài toán (21) và (22) là bằng nhau: * *.q h Ngoài ra, nếu * là nghiệm tối ưu của (22) thì điểm cực đại *x của hàm 1 2 1 2   ** * ( ) ( )... ( )kkf fx fx x trên X là nghiệm tối ưu của (21). Chứng minh. Cho *x là nghiệm tối ưu của (21), nghĩa là  * * *, ( ) .Ex X q x q Vì * Ex X , nên tồn tại véctơ k  sao cho *x là nghiệm tối ưu của (5). Ta khẳng định rằng tồn tại 0  sao cho 1 2* * * 1 2( ) ( )... ( ) 3. k kf x x xf f    Thực vậy, đặt 1 2* * * 1 2( ) ( )... ( ). k kf x f x f x    Vì * 2, 1, ,jx j n   , do đó ln( ) 0.  Lấy 1ln(3)ln ( )  ta có ln( ) ln(3)   . Bây giờ, đặt .  Dễ thấy 1 2 1 2max ( ) ( )... ( ) 3, k x X kf x f x f x     điều này suy ra .M Do vậy, * *( )q q x  1 21 2sup ( ) | ( ) ( )... ( ) 3,kkq x f x f x f x x X    *( )h h  . Điều này dẫn đến * 0h  . Đảo lại, giả sử * là nghiệm tối ưu của (22), nghĩa là * M  và * *( ) .h h  Giả sử *x là một điểm Trần Văn Thắng Tạp chí KHOA HỌC & CÔNG NGHỆ 128(14): 55 - 59 59 cực đại của hàm ** * 1 2 1 2( ) ( )... ( ) k kf fx x f x   trên .X Theo Bổ đề (1.6), *x là nghiệm hữu hiệu Pareto của (5) và do đó, * .Ex X Vì * M  , nên ta có ** * 1 2* * * 1 2( ) ( )... ( ) k kx x xf f f   ** * 1 2* * * 1 2sup{ ( ) ( )... ( ) : x X} 3. k kf fx xf x     Nếu ** * 1 2* * * 1 2( ) ( )... ( ) 3 k kx x xf f f    thì   ** * 1 2* 1 2( ) sup ( ) | ( ) ( )... ( ) 3, k kh q x f x f x f x x X      *sup 0 h    điều này là vô lý. Do đó, ** * 1 2* * * 1 2( ) ( )... ( ) 3 k kx x xf f f    và hơn nữa, * *( )h h    ** * 1 2 1 2sup ( ) | ( ) ( )... ( ) 3, k kq x f x f x f x x X     * *( )q x q  . Hệ quả là * *q h và do đó, *x là nghiệm tối ưu của (21). TÀI LIỆU THAM KHẢO 1. A. V. Fiacco, (1983), Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Academic Press, New York. 2. D. G. Luenberger, (1995), Microeconomic Theory, McGraw-Hill, Inc., New York. 3. L. D. Muu, (2000), A Convex-concave Programming Method for Optimizing over the Efficient Set, Acta Math. Vietnam, 25, 67-85. 4. P. T. Thach, (1993), Global Optimality Criterion and Duality with Zero Gap in Nonconvex Optimization, SIAM J. Math. Anal., 24, 1537-1556. 5. P. T. Thach, (2004), Dual preference in Leontief production problem and its extension, Vietnam J. Math., 32, 209-218. 6. P. T. Thach, H. Konno, and D. Yokota, (1996), Dual Approach to Minimization on the Set of Pareto-optimal Solutions, J. Optim. Theory Appl., 88, 689-707. 7. P. T. Thach and T. V. Thang, (2011), Conjugate duality for vector-maximization problems, J. Math. Anal. Appl., 1, 94-102. 8. P. T. Thach and T. V. Thang, (2014), Problems with resource allocation constraints and optimization over the efficient set, J. Glob. Optim., 58, 481-495. 9. T. V. Thang, (2014), Conjugate duality in nonconvex optimization problems and optimization over the weakly efficient set (Preprint). 10 H. Tuy, (2000), Monotonnic Optimization: Problem and Solution Approaches, SIAM Journal of Optimization, 11, 464-494. 11. H. Tuy, A. Migdalas and N.T. Hoai-Phuong, (2007), A novel approach to Bilevel nonlinear programming, J. Glol. Optim., 38, 527-554. SUMMARY CONJUAGATE DUALITY FOR OPTIMIZATION PROBLEMS AND APPLICATIONS Tran Van Thang* University of Electric Power In this paper, we present the conjugate duality for a class of quasiconcave optimization problems with objective functions are Cobb-Douglas production functions. Then, we apply the conjugate duality to study some optimization problems in Economics. Key word: cobb-douglas function, conjuagate duality Ngày nhận bài:17/9/2014; Ngày phản biện:02/10/2014; Ngày duyệt đăng: 25/11/2014 Phản biện khoa học: PGS.TS Hà Trần Phương – Trường Đại học Sư phạm - ĐHTN * Tel: