Giáo trình Quy hoạch tuyến tính - Chương 3: Bài toán đối ngẫu

 tương ứng của (P và 
(D). 
 Chúng minh 
- Nếu x không là phương án tối ưu của bài toán (P) thì tồn tại một phương án 
x sao cho : 
 )x(z)x(z < 
 ⇒ )x(z)y(w < : điều này mâu thuẩn với định lý 1. 
- Nếu y không là phương án tối ưu của bài toán (D) thì tồn tại một phương án 
y sao cho : 
 )y(w)y(w < 
 ⇒ )x(z)y(w < : điều này mâu thuẩn với định lý 1. 
 Vậy x và y lần lượt là phương án tối ưu của (P) và (D). 
BÀI TOÁN ĐỐI NGẪU 
77 
 c- Định lý 3 
Xét hai bài toán đối ngẫu : 
⎪⎪⎩
⎪⎪⎨
⎧
≥
=
=
 0x
 b Ax
x cz(x)max 
 )P(
T
⎪⎪⎩
⎪⎪⎨
⎧
≥
=
 tùy ý y 
 cyA
yb w(y) min
 )D( T
T
Nếu x* là phương án tối ưu của bài toán (P) đối với cơ sở B thì phương án tối 
ưu y* của bài toán (D) được tính bởi công thức : 
 ( ) 1TBT Bc*y −=
 Chứng minh 
 Do x* là phương án tối ưu của (P) với cơ sở B nên thoả dấu hiệu tối ưu 
 0AB.cc 1TB
T ≤− −
 ⇒ T1TB cA.Bc ≥−
 ⇒ ( ) TT cA*y ≥
 ⇒ y* là một phương án của (D) 
Mặt khác x* được tính bởi công thức : 
 ⎥⎥⎦
⎤
⎢⎢⎣
⎡
=
==
−
0x
bBx
x
*
N
1*
B*
 và giá trị mục tiêu tối ưu của (P) là : 
 z(x*) = cTx* = *B
T
B xc
 Ta có : 
)x(zxcxcb)(Bc 
b)Bc()Bc(b*yb)y(w
**
B
T
B
*
B
T
B
1-T
B
1T
B
T1T
B
TT*
====
=== −−
 Theo định lý 2 thì y* là phương án tối ưu của (D). 
 Định lý này cho phép tìm phương án tối ưu của bài toán quy hoạch tuyến tính 
đối ngẫu từ bài toán gốc. Trong đó : 
- được xác định trong bảng đơn hình tối ưu của (P). TBc
- B-1 gồm m cột tương ứng với m cột của ma trận cơ sở ban đầu lấy từ 
bảng đơn hình tối ưu của bài toán gốc. 
BÀI TOÁN ĐỐI NGẪU 
78 
 d- Định lý 4 ( sự đối ngẫu) 
 Xét hai bài toán đối ngẫu 
⎪⎪⎩
⎪⎪⎨
⎧
≥
=
=
 0x
 b Ax
x cz(x)max 
 )P(
T
⎪⎪⎩
⎪⎪⎨
⎧
≥
=
 tùy ý y 
 cyA
yb w(y) min
 )D( T
T
- Nếu (P) và (D) đều có phương án khả thi thì chúng có phương án tối ưu và 
giá trị của hàm mục tiêu tương ứng là bằng nhau. 
 - Nếu một trong hai bài toán có phương án tối ưu không giới nội thì bài toán 
còn lại không có phương án khả thi. 
 Chứng minh 
 - Đây là kết quả của định lý 3 . 
 - Giả sử rằng phương án tối ưu của (D) không giới nội, tức là tồn tại một 
phương án khả thi y của (D) sao cho w(y)= bTy nhỏ tuỳ ý. Điều này cũng có nghĩa là : 
với mọi M>0 lớn tuỳ ý luôn tìm được một phương án khả thi y của (D) sao cho : 
 M ybT −≤ 
 Nếu (P) có phương án khả thi là x thì theo định lý 1 ta có : 
 M yb)y(wxc)x(z TT −<=≤= 
 Điều này dẫn đến mâu thuẩn 
 e- Định lý 5 (tính bổ sung ) 
 Xét hai bài toán đối ngẫu 
⎪⎪⎩
⎪⎪⎨
⎧
≥
=
=
 0x
 b Ax
x cz(x)max 
 )P(
T
⎪⎪⎩
⎪⎪⎨
⎧
≥
=
 tùy ý y 
 cyA
yb w(y) min
 )D( T
T
 y , x là phương án khả thi tương ứng của (P) và (D). 
 Điều kiện cần và đủ để y , x cũng là phương án tối ưu là : 
 0)cyA(x TT
T =− 
 Chứng minh 
 - Do x là phương án khả thi của (P) nên : 
BÀI TOÁN ĐỐI NGẪU 
79 
 (*) xc-yb)cyA(x 
)xcc x( xc-ybcxyAx 
ybyAx 
 bAx 
b)x(A 
bxA 
TTTT
TTTTTTT
TTT
TTT
TT
=−⇒
==−⇒
=⇒
=⇒
=⇒
=
 - Theo kết quả (*) : 
 . Nếu y , x là phương án tối ưu của (P) và (D) thì theo định lý 4 
 0)cyA(x 
0ybxc 
ybxc 
TT
TT
TT
=−⇒
=−⇒
=
 . Nếu xcyb0xcyb0)cyA(x TTTTT
T =⇒=−⇒=− 
 Theo định lý 2 thì y , x là phương án tối ưu . 
II- GIẢI THUẬT ĐỐI NGẪU 
 Xét hai bài toán đối ngẫu : 
 (P) và (D) 
⎩⎨
⎧
≥
=
=
0x
bAx
xcz(x) max T
⎩⎨
⎧ ≥
=
y tuy y
cyA
ybw(y) min
T
T
 Chúng ta sẽ xét xem giải thuật đơn hình cơ bản đã biết trong chương trước 
được áp dụng như thế nào đối với bài toán đối ngẫu. 
 Giả sử rằng B là một cơ sở của bài toán (P) thoả : 
 và 1TBBcy
−= NT cyN ≥
 Nếu B cũng là một cơ sở khả thi của bài toán gốc, tức là 
⎥⎥⎦
⎤
⎢⎢⎣
⎡
=
≥===
−
0x
0bbBx
x
N
1
B , thì (theo định lý đối ngẫu) y, x lần lượt là phương án tối 
ưu của bài toán đối ngẫu và bài toán gốc. Nếu không thì không là phương 
án của bài toán gốc vì 
⎥⎦
⎤⎢⎣
⎡=
N
B
x
x
x
bBbx 1B
−== không thể ≥ 0. 
 Để tiện việc trình bày ta xét (m=3 , n=5) : 
BÀI TOÁN ĐỐI NGẪU 
80 
 (P) 
0x,x,x,x,x
bxaxaxaxaxa
bxaxaxaxaxa
bxaxaxaxaxa
xcxcxcxcxcz(x) max
54321
3535434333232131
2525424323222121
1515414313212111
5544332211
≥
⎪⎩
⎪⎨
⎧
=++++
=++++
=++++
++++=
 Các dữ liệu của (P) đuợc trình bày trong bảng sau : 
x1 x2 x3 x4 x5 
c1 c2 c3 c4 c5 
a11 a12 a13 a14 a15 b1
a21 a22 a23 a24 a25 b2
a31 a32 a33 a34 a35 b3
 và bài toán đối ngẫu 
 (D) 
tuy y y,y,y
cyayaya
cyayaya
cyayaya
cyayaya
cyayaya
ybybybw(y) min
321
5335225115
4434224114
3333223113
2332222112
1331221111
332211
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
≥++
≥++
≥++
≥++
≥++
++=
 Người ta đưa (D) về dạng chính tắc bằng cách thêm các biến phụ y4 y5, y6, y7, 
y8 ≥ 0. Chúng không ảnh hưởng đến hàm mục tiêu. 
 0y,y ,y,y,y -tuy y y,y,y
cyyayaya
cyyayaya
cyyayaya
cyyayaya
cyyayaya
y.0y.0y.0y.0y.0ybybybw(y) min
87654321
58335225115
47434224114
36333223113
25332222112
14331221111
87654332211
≥
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
=−++
=−++
=−++
=−++
=−++
+++++++=
Các dữ liệu của (D) được trình bày trong bảng sau : 
BÀI TOÁN ĐỐI NGẪU 
81 
y1 y2 y3 y4 y5 y6 y7 y8 
b1 b2 b3 0 0 0 0 0 
a11 a21 a31 -1 0 0 0 0 c1
a12 a22 a32 0 -1 0 0 0 c2
a13 a23 a33 0 0 -1 0 0 c3
a14 a24 a34 0 0 0 -1 0 c4
a15 a25 a35 0 0 0 0 -1 c5
Giả sử rằng m cột đầu tiên của A là một cơ sở B của (P) thì hai bảng trên được 
trình bày rút gọn như sau : 
T
Bx 
T
Nx 
T
Bc 
T
Nc 
B N b 
Bảng (P) 
yT y4....y8 
bT 0 
BT -Im 0 cB
NT 0 -In-m cN
Bảng (D) 
 Để đưa bài toán đối ngẫu về dạng chuẩn người ta nhân (bên trái) bảng (D) với 
bảng sau đây : 
( )T1B − 0 
( )T1NB − -In-m
 Khi đó người ta được bảng kết quả có dạng : 
BÀI TOÁN ĐỐI NGẪU 
82 
 m m n-m 
 Ty y4y5y6 y7y8 
 0 bBb 1−= 0 
m Im ( )T1B −− 0 ( )T1TBBc − 
n-m 0 ( ) ( )T1T NBN −−=− In-m ( )T1TBTNN NBccc −−−=− 
 Bảng này cho ta một quy hoạch tuyến tính dạng chuẩn với ma trận đơn vị (cơ 
sở) tương ứng với các cột y1 y2 y3 y7 y8 . 
 Áp dụng giải thuật đơn hình cơ bản vào kết quả này cho ta quy tắc đổi cơ sở 
như sau : 
 Tính : 0bBb 1 ≥= − 
 a- Nếu 0b ≥ thì giải thuật kết thúc, khi đó : 
 là phương án tối ưu của bài toán đối ngẫu . 1TBBcy
−=
 ⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡=
0
b
x
x
x
N
B là phương án tối ưu của bài toán gốc . 
 b- Nếu tồn tại r sao cho 0b , bb rr <∈ thì xảy ra một trong hai trường hợp 
sau : 
 - Nếu trong dòng r của N có thành phần < 0 thì người ta tính : 
0N : j 
N
c
 min
N
c
ij
rj
j
rs
s
<∀
⎭⎬
⎫
⎩⎨
⎧=
 Như vậy : đối với bài toán đối ngẫu thì biến yr đi vào cơ sở và biến ys ra khỏi 
cơ sở, trong khi đó đối với bài toán gốc thì biến xs đi vào cơ sở và biến xr ra khỏi cơ 
sở. 
 - Nếu mọi thành phần trong dòng r của N đều > 0 thì phương án 
tối ưu của bài toán đối ngẫu là không giới nội, điều này (theo định lý đối ngẫu) dẫn 
đến bài toán gốc không có phương án. 
 Ví dụ : Xét bài toán 
BÀI TOÁN ĐỐI NGẪU 
83 
 (D) 
1,2,3,4)(j 0x
2xx3x
1xx2x
xxw(x) min
j
421
321
31
=≥
⎩⎨
⎧
=++
=+−
−=
Bài toán đối ngẫu của (D) là : 
 (P) 
⎪⎪⎩
⎪⎪⎨
⎧
≤
−≤
≤+−
≤+
+=
0y
1y
0y3y2
1yy
y2yz(y) max
2
1
21
21
21
y1, y2 là tùy ý 
Ta có thể chọn bài toán (D) hoặc (P) để giải tìm phương án tối ưu bằng phương pháp 
đơn hình, từ đó suy ra phương án tối ưu của bài toán còn lại theo kết quả trên. Trong 
ví dụ này ta chọn bài toán (D) để giải vì có chứa sẵn ma trận đơn vị. 
 Giải bài toán (D) bằng phương pháp đơn hình cải tiến ta được : 
0B
c 
0B
i 1x 2x 3x 4x 0b 
-1 3 1 -2 1 0 1 
0 4 1 3 0 1 2 
Tc 1 0 -1 0 w(x0) 
T
0c 2 -2 0 0 -1 
1B
c 
1B
i 1x 2x 3x 4x 1b 
-1 3 
3
5 0 1 
3
2 
3
7 
0 2 
3
1 1 0 
3
1 
3
2 
Tc 1 0 -1 0 w(x1) 
T
1c 3
8 0 0 
3
2 
3
7− 
 Giải thuật dừng vì thoả dấu hiệu tối ưu của bài toán min. 
 Phương án tối ưu của bài toán (D) là : 
⎪⎪⎩
⎪⎪⎨
⎧
−==
====
3
7
)x(w)x(w
0x 
3
7
x 
3
2
x 0x
1
4321
BÀI TOÁN ĐỐI NGẪU 
84 
Suy ra phương án tối ưu của (P) là : 
[ ] [ ]
[ ]
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
−=⎥⎥⎦
⎤
⎢⎢⎣
⎡
−
−
==
⎥⎦
⎤⎢⎣
⎡ −−=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=== −
3
7
3
2
1
 21yb)y(z
3
2
1
3
1
0
3
2
1
 01Bcyyy
T
1T
B21
T
BÀI TOÁN ĐỐI NGẪU 
85 
CÂU HỎI CHƯƠNG 3 
1- Bạn hiểu như thế nào về khái niệm đối ngẫu ? 
2- Quy hoạch tuyến tính đối ngẫu của một quy hoach tuyến tính chính tắc có dạng như 
thế nào ? 
3- Bạn hãy nêu ra các quy tắc đối ngẫu. Cho ví dụ . 
4- Giá trị hàm mục tiêu của hai quy hoạch tuyến tính đối ngẫu thì như thế nào ? . 
Chứng minh 
BÀI TOÁN ĐỐI NGẪU 
86 
BÀI TẬP CHƯƠNG 3 
1- Xét bài toán quy hoạch tuyến tính 
 max z = 7x1 + 5x2 
 2x1 + 3x2 ≤ 19 
 (P) 2x1 + x2 ≤ 13 
 3x2 ≤ 15 
 3x1 ≤ 18 
 x1 , x2 ≥ 0 
a- Tìm bài toán đối ngẫu (D) từ bài toán (P) 
b- Tìm phương án tối ưu cho bài toán (P) 
c- Từ bảng đơn hình tối ưu của (P). Hãy tìm phương án tối ưu cho bài toán (D) 
2- Xét bài toán quy hoạch tuyến tính 
min w= x1 + x2 
 x1 - 2x3 + x4 = 2 
(D) x2 - x3 + 2x4 = 1 
 x3 - x4 + x5 = 5 
xi ≥ 0, ∀i = 1→5 
a- Tìm bài toán đối ngẫu của bài toán (D) 
 b- Tìm phương án tối ưu của bài toán (D) 
c- Từ bảng đơn hình tối ưu của bài toán (D). Hãy tìm phương án tối ưu cho bài 
toán đối ngẫu ở câu a. 
3- Xét bài toán quy hoạch tuyến tính 
 min w = -2x1 - x4
 x1 + x2 + 5x3 = 20 
 (D) x2 + 2x4 ≥ 5 
 x1 + x2 - x3 ≥ 8 
 xi tùy ý (i=1→ 4) 
Tìm bài toán đối ngẫu (P) của bài toán (D). Từ bài toán (P) hãy chỉ ra rằng (P) 
không tồn tại phương án tối ưu do đó (D) cũng tồn tại phương án tối ưu. 
4- Cho bài toán quy hoạch tuyến tính 
BÀI TOÁN ĐỐI NGẪU 
87 
 (D) 
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
→=≥
≤++
≤−−
≤++
+++=
4)1(j 0x
3xx4x4
3x2x5
1xx3x
xxx42xz max
j
432
42
421
4321
 1- Tìm bài toán đối ngẫu của bài toán đã cho. 
 2- Giải bài toán đã cho rồi suy ra kết quả của bài toán đối ngẫu. 
5- Cho bài toán quy hoạch tuyến tính 
 (D) 
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
≤
−≤−+
≤−+−
≤++
++=
 0x ý, tuúx 31 x,
2x4x2x
4x2xx2
2xx2x
x18x5027xz max
2
321
321
321
321
 a- Tìm bài toán đối ngẫu của bài toán đã cho. 
 b- Giải bài toán đối ngẫu rồi suy ra kết quả của bài toán đã cho.