Bài giảng Quy hoạch tuyến tính - Chương II: Lý thuyết đối ngẫu - Bài 1: Bài toán đối ngẫu và một số tính chất

ện dấu hiệu tối ưu. 
P/án tối ưu tìm được có cơ sở liên kết 
{A1,A2,,Am}. Khi đó phương án tối ưu 
của bài toán đối ngẫu được tính theo công 
thức 
x
1y cB
trong đó : c=(c1,c2,,cm) tương ứng với 
 B=[A1,A2,,Am] 
x
Ví dụ 1: Xét lại bài toán QHTT 
1 2 3 4
1 2 4
2 3 4
( ) 2 2 0 min
4 6
( )
2 5 8
0, 1,4j
f x x x x x
x x x
P
x x x
x j
    
  

  
 
Bài toán (P) có p/án tối ưu (2,4,0,0)x 
Cơ sở liên kết là {A1,A2}. Vậy p/án tối ưu 
của bài toán đối ngẫu là : 
   
1
1
1 1 1 0.5 3
1, 2 1, 2 1,
0 2 0 0.5 2
y cB


     
          
    
Ví dụ 2: Xét bài tập 11 ở bài 4 chương 1 
  1 2 3
1 2 3
1 2 3
1 2 3
min
6 2 20
7 3 25
3 8 30
0, 1,2,3.j
f x x x x
x x x
x x x
x x x
x j
   
  

  
   
 
Đối ngẫu của bài toán này là bài toán 
1 2 3
1 2 3
1 2 3
1 2 3
( ) 20 25 30 max
6 3 1
2 7 1
3 8 1
0, 1,3i
g y y y y
y y y
y y y
y y y
y i
   
  

  
   
 
 20 25 30 0 0 0 
----------------------------------------------------------------------------- 
Co So CJ Ph.An y1 y2 y3 y4 y5 y6 
------------------------------------------------ ----------------------------- 
 A4 0 1 6 1 3 1 0 0 
 A5 0 1 2 7 1 0 1 0 
 A6 0 1 1 3 8 0 0 1 
----------------------------------------------------------------------------- 
 -20 -25 -30 0 0 0 
----------------------------------------------------------------------------- 
 A4 0 5/8 45/8 -1/8 0 1 0 -3/8 
 A5 0 7/8 15/8 53/8 0 0 1 -1/8 
 A3 30 1/8 1/8 3/8 1 0 0 1/8 
----------------------------------------------------------------------------- 
 -65/4 -55/4 0 0 0 15/4 
----------------------------------------------------------------------------- 
 A1 20 1/9 1 -1/45 0 8/45 0 -1/15 
 A5 0 2/3 0 20/3 0 -1/3 1 0 
 A3 30 1/9 0 17/45 1 -1/45 0 2/15 
----------------------------------------------------------------------------- 
 0 -127/9 0 26/9 0 8/3 
----------------------------------------------------------------------------- 
 A1 20 17/150 1 0 0 53/300 1/300 -1/15 
 A2 25 1/10 0 1 0 -1/20 3/20 0 
 A3 30 11/150 0 0 1 -1/300 -17/300 2/15 
----------------------------------------------------------------------------- 
 0 0 0 131/60 127/60 8/3 
----------------------------------------------------------------------------- 
P/án tối ưu là : 
17 1 11
, , ,0,0,0
150 10 150
y
 
  
 
 P/án tối ưu của bài toán gốc : 1x cB
 
1
6 1 3
131 127 8
20,25,30 2 7 1 , ,
60 60 3
1 3 8
x

 
  
       
 
Giá trị tối ưu :   209
30
g y 
Nếu giải bài toán gốc trước sẽ tính toán 
nhiều hơn 
2.7 Mệnh đề: Giả sử là cơ 
sở đơn vị liên kết của phương án cực 
biên xất phát của bài toán gốc dạng chính 
tắc. Khi đó phương án tối ưu của bài toán 
đối ngẫu có thể tính theo công thức: 
1 2, ,..., m
jj j
A A A
 
1 1 2 2
, , ..,
m mj j j j j j
y c c c      
Trong đó là các ước lượng ứng 
với các cột xuất hiện ở bảng 
đơn hình cuối cùng và là các hệ 
số của . 
1 2
, , ..,
mj j j
  
1 2, ,.., m
jj j
A A A
1 2
, , ..,
mj j j
c c c
1 2
, , ..,
mj j j
x x x
Ví dụ: Xét lại bài toán trên 
1 2 3 4
1 2 4
2 3 4
( ) 2 2 0 min
4 6
( )
2 5 8
0, 1,2,3,4;j
f x x x x x
x x x
P
x x x
x j
    
  

   
 
Ta có bảng đơn hình là: 
 1 -2 2 0 
------------------------------------------------------------------ 
Co So CJ Ph.An x1 x2 x3 x4 
------------------------------------------------------------------ 
 A1 1 6 1 1 0 4 
 A3 2 8 0 2 1 5 
------------------------------------------------------------------ 
 0 7 0 14 
------------------------------------------------------------------ 
 A4 0 3/2 1/4 1/4 0 1 
 A3 2 1/2 -5/4 3/4 1 0 
------------------------------------------------------------------ 
 -7/2 7/2 0 0 
------------------------------------------------------------------ 
 A4 0 4/3 2/3 0 -1/3 1 
 A2 -2 2/3 -5/3 1 4/3 0 
------------------------------------------------------------------ 
 7/3 0 -14/3 0 
------------------------------------------------------------------ 
 A1 1 2 1 0 -1/2 3/2 
 A2 -2 4 0 1 1/2 5/2 
------------------------------------------------------------------ 
 0 0 -7/2 -7/2 
Ta có cơ sở đơn vị liên kết của phương án 
cực biên xuất phát trong bảng đơn hình đầu 
là 1 21 1 3 21 0,
0 1
j jA A E A A E
   
        
   
Hệ số đứng trước là 1 3,x x
1 21 3
1, 2j jc c c c   
Các ước lượng ở bảng đơn hình cuối là : 
j
1 21 3
7
0,
2
j j

       
Vậy ph. Án tối ưu của bài toán đối ngẫu là: 
 
1 1 2 2
7 3
, , .., 0 1, 2 1,
2 2m m
j j j j j jy c c c
    
             
   
Ví dụ: Ta xét bài tập 11 ở bài 4 chương 1 
1 2 3
1 2 3
1 2 3
1 2 3
min
6 2 20
7 3 25
3 8 30
0, 1,2,3.j
f x x x
x x x
x x x
x x x
x j
   
  

  
   
 
Đối ngẫu của bài toán này là bài toán 
1 2 3
1 2 3
1 2 3
1 2 3
( ) 20 25 30 max
6 3 1
2 7 1
3 8 1
0, 1,3i
g y y y y
y y y
y y y
y y y
y i
   
  

  
   
 
 20 25 30 0 0 0 
----------------------------------------------------------------------------- 
Co So CJ Ph.An y1 y2 y3 y4 y5 y6 
------------------------------------------------ ----------------------------- 
 A4 0 1 6 1 3 1 0 0 
 A5 0 1 2 7 1 0 1 0 
 A6 0 1 1 3 8 0 0 1 
----------------------------------------------------------------------------- 
 -20 -25 -30 0 0 0 
----------------------------------------------------------------------------- 
 A4 0 5/8 45/8 -1/8 0 1 0 -3/8 
 A5 0 7/8 15/8 53/8 0 0 1 -1/8 
 A3 30 1/8 1/8 3/8 1 0 0 1/8 
----------------------------------------------------------------------------- 
 -65/4 -55/4 0 0 0 15/4 
----------------------------------------------------------------------------- 
 A1 20 1/9 1 -1/45 0 8/45 0 -1/15 
 A5 0 2/3 0 20/3 0 -1/3 1 0 
 A3 30 1/9 0 17/45 1 -1/45 0 2/15 
----------------------------------------------------------------------------- 
 0 -127/9 0 26/9 0 8/3 
----------------------------------------------------------------------------- 
 A1 20 17/150 1 0 0 53/300 1/300 -1/15 
 A2 25 1/10 0 1 0 -1/20 3/20 0 
 A3 30 11/150 0 0 1 -1/300 -17/300 2/15 
----------------------------------------------------------------------------- 
 0 0 0 131/60 127/60 8/3 
----------------------------------------------------------------------------- 
Phương án tối ưu là 
= ( 17/150, 1/10, 11/150, 0, 0, 0,) 
Giá trị tối ưu g = 209/30. 
y
từ đây ta suy ra ph. Án tối ưu của bài toán 
gốc như sau 
 
1 1 2 2
, , ..,
m mj j j j j j
x c c c      
Ta có cơ sở liên kết của phương án cực biên 
xuất phát trong bảng đơn hình đầu là 
4 5 6, ,A A A
31 24 1 5 2 6 3, ,
jj j
A A E A A E A A E     
Ba hệ số đứng trước 
4 5 6, ,x x x
1 2 34 5 6
0, 0, 0j j jc c c c c c     
Các ước lượng ở bảng đơn hình cuối là: 
j
1 24 5 3 6
131/60, 127/60, 8/3j j j           
Vậy ta có phương án tối ưu của bài toán 
gốc là  
 
1 1 2 2
, , ..,
131/60+0,127/60+0,8/3+0
m mj j j j j j
x c c c      

 131/60, 127/60, 8/3x
Tóm lại, giữa bài toán gốc và đối ngẫu ta có 
các kết qủa sau: 
i) Nếu bài toán gốc (đối ngẫu) có phương 
án tối ưu thì bài toán đối ngẫu (gốc) cũng 
có phương án tối ưu. Phương án tối ưu có 
thể tìm bằng ba phương pháp. Giá trị tối ưu 
của hai bài toán là bằng nhau 
ii) Nếu cả hai bài toán gốc và đối ngẫu 
đều có tập phương án không rỗng thì cả 
hai bài toán đều có phương án tối ưu và 
giá trị tối ưu của các hàm mục tiêu là 
bằng nhau. (Định lý 2 ) 
iii) Từ đó nếu bài toán gốc (hoặc đối 
ngẫu) có tập phương án khác rỗng và hàm 
mục tiêu không bị chặn (không bị chặn 
dưới nếu là bài toán min, không bị chặn 
trên nếu là bài toán max) thì bài toán còn 
lại có tập phương án bằng rỗng. 
Nếu bài toán gốc (hoặc đối ngẫu) có tập 
phương án bằng rỗng thì bài toán đối ngẫu 
(hoặc gốc) có tập phương án bằng rỗng, 
hoặc có hàm mục tiêu không bị chặn. 
Bài tập 1: Chứng minh bài toán sau 
không có phương án tối ưu. 
1 2 3 4
1 2 3 4
1 2 3 4
( ) 7 2 6 max
3 10
2 5 4 15
0, 1,4 .j
f x x x x x
x x x x
x x x x
x j
    
   

   
 
1 2 3 4
1 2 3 4
1 2 3 4
( ) 7 2 6 max
3 10
2 5 4 15
0, 1,4 .j
f x x x x x
x x x x
x x x x
x j
    
   

   
 
Giải: 
Bài tập 2: Cho bài toán (P) 
1 2 3 4
1 2 3 4
1 2 3 4
( ) 4 6 5 3 min
3 3 2 9
4 2 7
0; 1,4.j
f x x x x x
x x x x
x x x x
x j
    
   

   
 
a)Phát biểu bài toán đối ngẫu (Q) của bài 
toán (P). 
b) Giải bài toán Q và suy ra phương án tối 
ưu của bài toán (P) bằng ba cách. 
1 2 3 4
1 2 3 4
1 2 3 4
( ) 4 6 5 3 min
3 3 2 9
4 2 7
0; 1,4.j
f x x x x x
x x x x
x x x x
x j
    
   

   
 
 9 7 0 0 0 0 
----------------------------------------------------------------------------- 
Co So CJ Ph.An A1 A2 A3 A4 A5 A6 
----------------------------------------------------------------------------- 
 A3 0 4 1 1 1 0 0 0 
 A4 0 6 3 4 0 1 0 0 
 A5 0 5 3 2 0 0 1 0 
 A6 0 3 2 1 0 0 0 1 
----------------------------------------------------------------------------- 
 - 9 - 7 0 0 0 0 
----------------------------------------------------------------------------- 
 A3 0 5/2 0 1/2 1 0 0 -1/2 
 A4 0 3/2 0 5/2 0 1 0 -3/2 
 A5 0 1/2 0 1/2 0 0 1 -3/2 
 A1 9 3/2 1 1/2 0 0 0 1/2 
----------------------------------------------------------------------------- 
 0 -5/2 0 0 0 9/2 
----------------------------------------------------------------------------- 
 A3 0 11/5 0 0 1 -1/5 0 -1/5 
 A2 7 3/5 0 1 0 2/5 0 -3/5 
 A5 0 1/5 0 0 0 -1/5 1 -6/5 
 A1 9 6/5 1 0 0 -1/5 0 4/5 
----------------------------------------------------------------------------- 
 0 0 0 1 0 3 
   
1
1
1 1 0 1
0 4 0 3
0,7,0,9 0,1,0,3
0 2 1 3
0 1 0 2
x cB


 
 
  
 
 
 