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

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