Về một lược đồ đối ngẫu trong tối ưu dạng phân thức tuyến tính - Huỳnh Khoa

TAÏP CHÍ KHOA HOÏC ÑAÏI HOÏC SAØI GOØN Soá 23 (48) - Thaùng 12/2016 155 Về một lược đồ đối ngẫu trong tối ưu dạng phân thức tuyến tính A note on duality in linear fractional programming ThS. Huỳnh Khoa Trường THPT Nguyễn Thị Diệu Huynh Khoa, M.Sc. Nguyen Thi Dieu High School Tóm tắt Trong bài báo này, chúng tôi quan tâm đến một lược đồ đối ngẫu của bài toán tối ưu dạng phân thức tuyến tính do Seshan [12] đề xuất. Điểm đặc biệt của lược đồ đối ngẫu này là bài toán gốc và bài toán đối ngẫu có cùng hàm mục tiêu. Mặc dù lược đồ này đã thu hút sự quan tâm và được khảo cứu lại trong các tài liệu, nhưng các bước để dẫn đến sự hình thành lược đồ dường như chưa được làm rõ. Mục đích của bài báo này là chỉ rõ rằng, lược đồ đối ngẫu ấy có thể nhận được từ các phép biến đổi Charnes- Cooper và phép biến đổi của Dinkelbach. Ví dụ minh họa được giới thiệu. Từ khóa: đối ngẫu Seshan, phương pháp Charnes - Cooper, phương pháp Dinkelbach. Abstract We are interested in the duality scheme of a linear fractional programming problem proposed by Seshan. The specification of the duality scheme is that the dual problem and the primal problem have the same objective functions. Despite having academic attentions and having been studied in literature, the motivation for the scheme is not clear. The aim of this paper is to show that the duality scheme can be obtained based on the Charnes-Cooper and Dinkelbach transformations. An example is given. Keywords: Seshan’s duality, Charnes – Cooper method, Dinkelbach method. 1. Phần giới thiệu Bài toán tối ưu dạng phân thức tuyến tính được nhiều nhà toán học quan tâm từ rất sớm [14], [8], [7], [5]. Như là một sự mở rộng tự nhiên của bài toán tối ưu dạng tuyến tính, người ta quan tâm dạng bài toán tối ưu phân thức tuyến tính sau đây (P)Max 0 0 ( ) T T c x c F x d x d    (1.1) Đ.k. ,Ax b (1.2) 0,x  (1.3) trong đó 1 2 n c c c c             , 1 2 n d d d d             là các vectơ cột gồm n thành phần; 1 2 m b b b b             là vectơ cột gồm m thành phần; 0 0,c d là những hằng số, A là ma trận cấp m n 156 ( m n , hạng của A bằng m). Từ bài toán (P), nếu mẫu thức là hằng số, ta có bài toán quy hoạch tuyến tính thông thường. Tuy nhiên nếu mẫu thức không là hàm số thì hàm mục tiêu thường là không là lồi. Điều đó có nghĩa, bài toán tối ưu dạng phân thức tuyến tính là bài toán tối ưu không lồi. Có nhiều phương pháp giải bài toán này đã được tổng hợp và giới thiệu trong tài liệu [3], [11]. Hơn thế nữa nhiều lược đồ đối ngẫu cho bài toán tối ưu dạng phân thức tuyến tính đã được thiết lập [1], [13], [6], [7], [2], [12]. Chúng ta đã biết rõ rằng: trong tối ưu tuyến tính, đối ngẫu của bài toán tối ưu tuyến tính cũng có dạng bài toán tối ưu tuyến tính. Câu hỏi này được đặt ra cho bài toán (P) nêu trên: Có hay không một lược đồ đối ngẫu của bài toán tối ưu dạng phân thức tuyến tính mà bài toán đối ngẫu cũng là dạng phân thức tuyến tính? Theo sự hiểu biết của chúng tôi, trong tất cả các lược đồ đối ngẫu áp dụng cho bài toán phân thức tuyến tính, chỉ có lược đồ đối ngẫu Seshan [12] đưa ra vào năm 1980 là trả lời được câu hỏi nêu trên. Từ bài toán (P), trong bài báo [12], năm 1980, Seshan đã giới thiệu một bài toán đối ngẫu của (P) như sau: (D) Min 0 0 ( , ) T T c u c I u v d u d    (1.4) Đ.k.     0 0 ,T T Tc d u d c u A v c d d c    (1.5) 0 0 0, T T Tc d u d c u b v   (1.6) 0, 0.u v  (1.7) Với bài toán này, các định lý đối ngẫu yếu và đối ngẫu mạnh cho bài toán (P) đã được thiết lập. Năm 2006, T.Q. Sơn trong bài báo [2] đã quan tâm đến lược đồ này. Bằng cách điều chỉnh miền chấp nhận được của bài toán (P) một cách thích hợp, thông qua một lược đồ đối ngẫu cải biên, các định lí về đối ngẫu yếu và đối ngẫu mạnh được thiết lập. Hơn thế nữa, đặc trưng tập nghiệm của (P) đã được giới thiệu. Lược đồ đối ngẫu nói trên đã được tổng hợp và giới thiệu trong tài liệu [3]. Mặc dù lược đồ đối ngẫu Seshan thu hút được quan tâm, nhưng các bước tiến hành xây dựng bài toán đối ngẫu Seshan dường như vẫn chưa được làm rõ và câu hỏi về cơ sở để hình thành được bài toán đối ngẫu Seshan vẫn còn bỏ ngỏ trong nhiều năm. Năm 2010, trong bài báo số [4], các tác giả đã làm rõ một số lược đồ đối ngẫu tương đương của bài toán (P). Đặc biệt tác giả chỉ ra lược đồ đối ngẫu của (P) do Gol'stein đề nghị trong bài báo số [9] có thể dẫn tới đối ngẫu Seshan thông qua một hàm Lagrange thích hợp dạng phân thức và phép biến đổi của Charnes-Coopper. Mục đích của nghiên cứu này là đưa ra lời giải thích về sự hình thành bài toán đối ngẫu mà Seshan đã giới thiệu trong [12]. Bằng cách tiếp cận bài toán đối ngẫu theo kiểu biến đổi của Charnes - Cooper [10] và theo kiểu biến đổi Dinkelbach [3], chúng tôi đã đưa ra được các giải thích hợp lý cho việc hình thành lược đồ đối ngẫu của Seshan. Chú ý rằng, mặc dù sử dụng biến đổi Charnes-Cooper để đi đến lược đồ đối ngẫu Seshan, nhưng cách tiếp cận của chúng tôi là không trùng lặp với hướng tiếp cận của Gol'strein mà bài báo [4] đã bình luận. Trong các phần còn lại của bài báo này, phần tiếp theo được dành cho một số kết quả cơ bản đã biết để phục vụ cho các chứng minh trong bài báo. Trong phần cuối cùng, cũng là phần chính của bài báo, chúng tôi nêu ra hai cách tiếp cận để giải thích sự hình thành bài toán đối ngẫu đã giới thiệu trong [12]. Một ví dụ cũng 157 được giới thiệu để minh họa cho kết quả nghiên cứu. 2. Các kí hiệu và kiến thức cơ bản Kí hiệu  , 0nX x Ax b x    là tập chấp nhận được của bài toán (P). Giả sử 0 0 Td x d  với mọi x X , tập X là bị chặn và hàm mục tiêu F của bài toán (P) không phải là hàm hằng trên X . Kí hiệu Y là tập chấp nhận được của bài toán (D) và giả sử 0 0 Td u d  với mọi  ,u v Y . Từ bài toán (P), bằng cách sử dụng phép đổi biến của Charnes – Cooper [3], đặt 0 1 T t d x d   và y tx ta thu được bài toán quy hoạch tuyến tính có dạng (L1) Max   0, TG y t c y c t  (2.8) Đ. k. 0,Ay bt  (2.9) 0 1 , Td y d t  (2.10) 0, 0.y t  (2.11) Kí hiệu 1F là tập chấp nhận được của (L1). Bằng cách đặt 1 0 n c h c c             , 1 n y z y t             , 1 0 n d k d d             , [ ]A A b  là ma trận cấp  1m n  với cột thứ  1n  là b , bài toán (L1) được viết gọn lại như sau : Max Th z Đ. k. 0,Az  1 ,Tk z   10 0 .nz z   Theo quy tắc đối ngẫu của bài toán quy hoạch tuyến tính thông thường, ta thu được bài toán đối ngẫu của (L1) có dạng: (DL1) Min   TH g  Đ. k. 0, 1, ,i i m   1 ,m   T TB h  , trong đó 1 1 m m                  , 0 0 1 g             có  1m  thành phần, 0 B T bA dd        là ma trận cấp    1 1m n   . Với bài toán phân thức tuyến tính (P), giả sử 0 0 Td x d  với mọi x X . Đặt    0 0, T Tf x c x c g x d x d    . Chúng tôi quan tâm bổ đề sau đây : Bổ đề 2.1 Hàm      max , x X E f x g x         là hàm giảm. Chứng minh. Lấy 1 2,  sao cho 2 1  . Ta có                     2 2 2 2 2 2 1 2 1 1 max max x X x X E f x g x f x g x f x g x f x g x E                      Vậy  E  là hàm giảm. Định lí sau đây thiết lập sự mối liên hệ giữa bài toán phân thức tuyến tính và bài toán quy hoạch tuyến tính tham số. Định lí 2.1 ([3], trang 88) Với 158    0 0, T Tf x c x c g x d x d    , giả sử X   và   0g x  với mọi x X . Khi đó 0x X là nghiệm tối ưu của (P) nếu và chỉ nếu      0 0max 0, x X f x g x E        trong đó     0 0 0 f x g x   . Do  E  là hàm giảm, áp dụng định lí 2.1 nghiệm tối ưu của (P) tìm được dựa vào thuật toán sau đây (xem [3], trang 88): Bước 1: Với 1 0   , tìm 1x là nghiệm của bài toán    1 max x X E f x   . Đặt     1 2 1 f x g x   . Bước 2: Tìm 2x là nghiệm của bài toán      2 2max x X E f x g x       . Đặt     2 3 2 f x g x   . Bước 3: Tương tự như Bước 2 và tiếp tục. Dừng lại nếu   0kE   . Khi đó ta tìm được 1kx  là nghiệm của (P) và k là giá trị tối ưu của (P). Ví dụ 2.1 Xét bài toán (P1) Max 1 2 1 2 ( ) 1 x x F x x x     Đ.k. 1 2 1,x x  1 2, 0.x x  Kí hiệu X là tập chấp nhận được của (P1).    1 2 1 2max 1 x X E x x x x          Bước 1: 1 0   , chọn được 1 0 1 X        là một nghiệm của bài toán      1 1 20 max x X E E x x     . Khi đó  1 1E   . Đặt     1 2 1 1 2 f X g X    Bước 2 :       2 1 2 1 2 1 2 1 1 max 1 2 2 1 1 max 2 2 0. x X x X E E x x x x x x                              Do đó 2 1 2   là giá trị tối ưu của (P1) và 1 0 1 X        là nghiệm của (P1). 3. Nội dung chính 3.1. Đối ngẫu Seshan nhận được từ biến đổi của Charnes – Cooper Theo phương pháp đổi biến của Charnes – Cooper, bài toán (P) và (L1) là tương đương. Bổ đề 3.1 Giả sử 0 0 Td x d  với mọi x X . Khi đó, bài toán (P) có nghiệm khi và chỉ khi bài toán (L1) có nghiệm và chúng có chung giá trị tối ưu. Chứng minh. Lấy *x là nghiệm của (P). Đặt * * 0 1 T t d x d   và * * *y t x . Khi đó  * * 1,y t F . Thật vậy  * * * * * * * 0,Ay bt t Ax bt t Ax b       * * * * * * *0 0 0 1,T T Td y d t d t x d t t d x d      * *0, 0y t  . Ta có  * ** * * * * 00 0 * * * 0 0 0 TT T T T T t c x cc y c t c t x c t d x d d x d d x d        .(3.12) Vì *x là nghiệm tối ưu của (P) nên * 0 0 * 0 0 T T T T c x c c x c d x d d x d      với mọi x X . (3.13) 159 Với mọi   1,y t F thì 0t  (do 0 0 Td x d  với mọi x X ). Đặt y x t  . Khi đó x X . Thật vậy, do   1,y t F nên 0 0 y Ay bt A b Ax b t        và 0x  . Từ (3.12), (3.13), ta có     * * *0 0 1* 0 , , T T T c y c t t c y c t y t F d x d       hay  * *0 0 1, , T Tc y c t c y c t y t F     . Suy ra  * *,y t là nghiệm tối ưu của (L1) và     * * * * * * * * *0 0 0 * 0 , T T T T c x c G y t c y c t c t x c t F x d x d         . Ngược lại, lấy  ,y t là nghiệm của (L1), tức là  0 0 1, , T Tc y d t c y d t y t F     . Giả sử y x t  không là nghiệm của (P). Khi đó tồn tại 0x X sao cho 0 0 0 0 0 0 T T T T c x c c x c d x d d x d      . Do 0 0 0 T T T c x c c y c t d x d     , Nên 0 0 0 0 0 T T T c x c c y c t d x d     . Đặt 0 0 0 1 T t d x d   và 0 0 0y t x . Khi đó  0 0 0 0 0 0 0 1 0 0 , , T T T c x c c y c t y t F d x d      . Do đó 0 0 0 0 T Tc y c t c y c t   (mâu thuẩn vì  ,y t là nghiệm của (L1) ). Như vậy nếu  ,y t là nghiệm của (L1) thì y x t  là nghiệm của (P) và    0 0 0 0 , T T T T c x c F x c t x c t c y c t G y t d x d         . Chú ý rằng với quy tắc đối ngẫu của bài toán quy hoạch tuyến tính thông thường, ta thu được bài toán đối ngẫu của (L1) như sau: (DL1) Min   TH g  Đ. k. 0, 1, ,i i m   1 ,m   T TB h  , trong đó 1 1 m m                  , 0 0 1 g             có  1m  thành phần, 0 B T bA dd        là ma trận cấp    1 1m n   . Từ bài toán (DL1), gọi ia là vectơ cột thứ i của ma trận A, 1, n . Đặt 1 m               và 1m   . Khi đó:  1 1 0,..., ,T T T Tn nB a d a d b d           . Như vậy T T TB h A d c      và 0 0 Tb d c    . Mặt khác, 1 T mg    . Bài toán (DL1) chính là bài toán sau đây: ( Q ) Min  (3.14) Đ. k. ,TA c d   (3.15) 0 0c 0, Tb d    (3.16) 160 0, m   . (3.17) Ta sẽ chỉ ra rằng, bài toán ( Q ) có thể biến đổi thành bài toán đối ngẫu Seshan. Thật vậy, với 0 0 Td u d  với mọi 0u  và đặt 0 0 T T c u c d u d     , 0( ) Tv d u d   . Ta có :                               0 0 0 0 0 0 . T T T T T T T T T T T T T T T T T T T T A c d A d c A v d c d u d d u c c u d A v d u c c u d c d d u d d u c c u d A v d u c c u d d u c d c c u c d d u c c u d A v c d d c                                       Nhận xét 3.1: Ràng buộc (1.5) là tương đương ràng buộc (3.15) Hơn thế nữa, ta cũng có       0 0 0 0 0 0 0 0 0 c 0 0 0 T T T T T T T T b d d u d b c d u d d c u c b v c d u d c u                  Nhận xét 3.2: Ràng buộc (1.6) là tương đương ràng buộc (3.16) Nhận xét 3.3: Ngoài ra, do cách đặt 1 m               nên 0  và do 0( ) Tv d u d   nên 0v  . Nhận xét 3.4: Do các Nhận xét 3.1, 3.2, 3.3 và với cách đặt 0 0 T T c u c d u d     , bài toán ( Q ) là tương đương với bài toán (D). Tóm lại, từ Bổ đề 3.1, kết hợp với các nhận xét 3.1, 3.2 và 3.3 và với cách đặt 0 0 T T c u c d u d     , ta thấy rằng bài toán đối ngẫu Seshan là tương đương với một bài toán mà bài toán ấy lại có thể nhận được từ bài toán (P) bằng cách kết hợp phép đổi biến Charnes-Cooper với phép lấy đối ngẫu của bài toán quy hoạch tuyến tính. 3.2. Đối ngẫu Seshan nhận được từ biến đổi Dinkelbach Dựa vào định lí 2.1, bài toán (P) tương đương với bài toán (L2) Max   0 0T Tc x c d x d   Đ. k. ,Ax b 0x  . trong đó  là giá trị tối ưu của (P) và giá trị tối ưu của (L2) bằng 0. Chú ý rằng nếu sắp xếp lại hàm mục tiêu của bài toán thì (L2) viết lại như sau: 0 0Max {(c- ) } Td x c d   Đ.k. Ax b, 0x  . Giả sử x là nghiệm tối ưu của (L2). Bài toán (L2) là bài toán dạng quy hoạch tuyến tính. Theo quy tắc đối ngẫu của bài toán quy hoạch tuyến tính, ta xác định được bài toán đối ngẫu của (L2) có dạng: (DL2)  0 0Min Tb c d   Đ.k. ,TA c d   0, m   . Giả sử rằng v là nghiệm tối ưu của (DL2). Kí hiệu 2F là tập chấp nhận được của (DL2). Bổ đề 3.2: Hàm số ( )R  =  0 0 | , 0,T T mMin b c d A c d           là một hàm giảm. Chứng minh. Giả sử 2 1.  . Ta có: R( 2 ) =  0 2 0 2Min | , 0,T T mb c d A c d           = 0 2 0 Tb v c d  . Khi đó, theo quy tắc đối ngẫu giữa (L2) và (DL2) ta cũng có: 22 0 2 0 ( ) ax{( ) | , 0}TR M c d x c d Ax b x        161 = 2 0 2 0( ) Tc d x c d    1 0 1 0( ) Tc d x c d     1 0 1 0Max{( ) | , 0} Tc d x c d Ax b x        0 1 0 1Min | , 0,T T mb c d A c d            = 1( )R  . Do đó ( )R  là hàm giảm. Bổ đề 3.3: Giả sử  là giá trị tối ưu của (P). Khi đó v là nghiệm của (DL2) nếu và chỉ nếu ( v , ) là nghiệm của (Q ). Chứng minh. Lấy v là nghiệm của (DL2). Khi đó: 0 0 0 Tb v c d   , TA v c d  và 0.v  Do đó ( ) 0R   và 2( , ) Fv   . Với mọi   2, F   thì ( ) 0R   ( ) R( )R    .   Vậy  là giá trị tối ưu của (Q ), tức là ( v , ) là nghiệm của ( Q ). Ngược lại, lấy ( v , ) là nghiệm của (Q ), ta có: 0 0 0, Tb v c d   TA v c d  và 0.v  Vì  là giá trị tối ưu của (P) nên   2 0min 0. T o F b c d        Mặt khác,   2 0 0 0min 0. T T o F b v c d b c d            Do đó 0 0 0. Tb v c d   Như vậy v là nghiệm tối ưu của (DL2). Nhận xét 3.5: Bài toán (DL2) là tương đương với bài toán (Q ) Tóm lại: từ Bổ đề 3.3, kết hợp với các Nhận xét 3.4 và 3.5 ta thấy rằng bài toán đối ngẫu Seshan có thể nhận được từ bài toán (P) bằng cách kết hợp phép đổi biến Dinkelbach với phép lấy đối ngẫu của bài toán quy hoạch tuyến tính. Ví dụ 3.1. Xét bài toán (P1) Max 1 2 1 2 F(x)= 1 x x x x    Đ.k. 1 2 1x x  , 1 2, 0.x x  Ký hiệu 1 1 2 1 2 2 | 1, , 0 x X x x x x x x                là tập chấp nhận được của (P1). Giá trị tối ưu của (P1) là 1 2 và 1 1 2 1 2 2 Sol(P1) | 1, , 0 x x x x x x               . Bài toán đối ngẫu Seshan của (P1) có dạng: (D1) Min 1 2 1 2 ( , ) 1 u u I u v u u     Đ.k. 1,v  1 2 0,u u v    1 2, , v 0.u u  Ký hiệu Y =  1 2 1 2( , ) | u 0, 1, ( , ) 0,u v u v v u u u v        là tập chấp nhận được của (D1). Giá trị tối ưu của (D1) là 1 2 và Sol (D1) =  1 2 1 2( ,1) | ( , ) 0, 1 .u u u u u u    Theo hướng tiếp cận Charnes – Cooper, (P1) được đưa về dạng bài toán quy hoạch tuyến tính thông thường như sau, ký hiệu (L3): 162 Max 1 2( , )G y t y y  Đ.k. 1 2 0,y y t   1 2 1,y y t   1 2, , 0.y y t  Sol (L3) = 1 2 1 2 1 2 1 1 ( , , ) | , , 0 . 2 2 y y y y y y         Theo quy tắc đối ngẫu thông thường, ta xác định được bài toán đối ngẫu của (L3), ký hiệu (DL3): Min 2( ) TH l l g l  Đ.k. 1 0,l  1 2 0,l l   1 2 1.l l  trong đó 1 2 0 , . 1 l l g l             Bằng cách đặt 2l  và 1l  , ta thấy (DL3) có dạng bài toán tham số (K ) Min  Đ.k. 0,   1 ,   0.  Giá trị tối ưu của (K ) là 1 2 và Sol (K ) = 1 1 , . 2 2          Đặt 1 2 1 2 1 u u u u      với 1 2, 0.u u  và 1 2( 1)v u u    . Khi đó 1 2 0 0; 1 1; u u v v                0 0.v    Do đó (K ) được viết lại giống bài toán đối ngẫu (D1). Theo hướng tiếp cận Dinkelbach, (P1) được đưa về bài toán quy hoạch tuyến tính tham số (L4) Max  1 2 1 2( 1)x x x x    Đ.k. 1 2 1;x x  1 2, 0x x  . trong đó  là giá trị tối ưu của (P1). Ta tìm được giá trị tối ưu của (P1) là 1 2   (xem ví dụ 2.1) nên (L4) Max 1 2 1 1 ( ) 2 2 x x        Đ.k. 1 2 1;x x  1 2, 0x x  . Bài toán đối ngẫu của (L4) có dạng: (DL4) Min 1 2        Đ.k. 1 , 2    . Giá trị tối ưu của (DL4) là 0 và Sol(DL4)= 1 . 2       Theo bổ đề 3.3, (DL4) đưa về dạng bài toán tham số  K Min  Đ.k. 0,   Giá trị tối ưu của  K là 1 2 và Sol  K = 1 1 ; . 2 2          Bằng cách đặt 1 2 1 2 1 u u u u      với 1 2, 0.u u  và 1 2( 1)v u u    , thì  K được viết lại giống bài toán đối ngẫu (D1). Để kết thúc bài báo này chúng tôi giới thiệu sơ đồ hình thành lược đồ đối ngẫu Seshan. 1 , 0.       163 Hình 1: Lược đồ thiết lập bài toán đối ngẫu Seshan TÀI LIỆU THAM KHẢO 1. B. D. Craven, B. Mond (1973), The dual of a fractional linear program, Journal of mathematical analysis and appications, 42, 507-512. 2. Ta Quang Son (2006), On a duality scheme in linear fractional programming, Nonlinear analysis forum, 42, 137-145. 3. I. M. Stancu - Minasian (1997), Fractional Programming, Kluwer Academic Publishers, U.S.A. 4. S. Jahan and M.A. Islam (2010), Equivalence of duals in linear fractional programming, Dhaka Univ. Journal of Sciences, 58, 73-78. 5. K. Swarup (1965), Linear fractional functionals programming, Oper. Research, 13, 1029 - 1036. 6. S.F. Tantawy (2008), A new procedure for solving linear fractional programming problems, Mathematical and computer modelling, 48, 969-973. 7. G. R. Bitran, T. L. Magnanti (1976), Duality and sensitivity analysis for fractional programs, Oper. Research, 24, 675-699. 8. E. G. Gol'stein (1967), Dual problems of convex and fractionally-convex programming in functional spaces, Soviet Math. Dokl, 8, 212-216. 9. E. G. Gol'stein (1971), Duality Theory in Mathematical Programming, Nauka, Mosow. 10. A. Chanes and W.W. Cooper (1962), Programming with Linear Fractional Functionals, Naval Research Quarterly, 8, 181-186. 11. S. Schaible (1976), Fractional programming. I, Duality, Management Science, 22, 858-867. 12. C. R. Seshan (1980), On duality in linear fractional programming, Proc. Indian Acad. Sci. (Math. Sci.), 89, 35-42. 13. K. Swarup (1965), Linear fractional functionals programming, per.Research, 13, 1029-1036. 14. T. Weir (1991), Symmetric dual multiobective fractional programming, J. Austral. Math. Soc. (Series A), 50, 67-74. Ngày nhận bài: 05/10/2016 Biên tập xong: 15/12/2016 Duyệt đăng: 20/12/2016