1
BÀI TOÁN ĐỐI NGẪU
1
Chương 2
NỘI DUNG CHƯƠNG
2.1 Ý nghĩa và cách lập bài toán đối ngẫu
2.2 Giải bài toán đối ngẫu
2.3 Ứng dụng của bài toán đối ngẫu
2
2
2.1 Ý nghĩa và cách lập bài toán đối ngẫu
 Xét bài toán sảnxuấttối ưu:
Có một đốitácđặtvấn đề mua toàn bộ nguyên
liệucủactyA.Hãylập bài toán định giá mua
ng/liệurẻ nhất.
12 3
123
123
12 3
234 max
2 3 10000
2 3 3 50000 (2.1.1)
2 3 4 30000
0, 1,2,3
j
Zxx x
xxx
xxx
xx x
xj





4
3
Lập bài toán đối ngẫu
Bài toán xuất phát(ĐNgẫu) Bài toán đối ngẫu (X.phát)
5
11
max
nn
Zcx cx 
11
min
mm
Zby by

 
1
,( 1, )
n
ij j i
j
ax b i m







0
0,( 1,)
tuøy yù
i
y
im






RBD ngược dấu RBC
RBC cùng dấu RBD x
j
Lập bài toán đối ngẫu
Ví dụ 2.1.1a Xét bài toán QHTT
6
12 3
123
123
12 3
28max
7 4 2 28
3 3 10
2 3 15
0, 1,3
j
Zxxx
xxx

4
Lập bài toán đối ngẫu
b)
7
123
12 3
123
12
13
12
23 min
2 2 2
4 3
2 4
2 5
, 0
Zx x x
xx x
xxx
xx
xx
xx
  

 
 


1234
123 4

đối ngẫu sau:
9
1123
2123
3123
123 1
12 3 3
0 7 3 2 2
0 4 3 1
0 2 3 8
742 28 0
23 15 0
xyyy
xyyy
xyyy
xxx y
xx x y
 
 
  
 

Các định lý đối ngẫu
Định lý đốingẫuyếu:
Nếu x*là phươngántùyýcủabàitoángốc(P)
và y*làphươngántùyýcủabàitoánđốingẫu
(D) thì Z(x*) ≤ Z’(y*).
Hệ quả 1:
Nếumột trong hai bài toán (củacặpbàitoánđối
ngẫu) có phương án tối ưu thì bài toán còn lại



Các định lý đối ngẫu
Định lý đối ngẫu mạnh:
12
Nếu x
*
là PATƯ của (P)
y
*
là PATƯ của (D)
*
() (*)
Z
xZy





7
Các định lý đối ngẫu
Định lý độ lệch bù yếu:
Điềukiệncầnvàđủ để PA x
0
của bài toán (P) và
PA y
0
của bài toán (D) là là 2 PA tối ưulà:
13






Các định lý đối ngẫu
Hoặc phát biểutương đương:
Đkcầnvàđủ để x
0
và y
0
là PATƯ của bài toán (P)
và (D) tương ứng là trong từng cặpràngbuộc đối
ngẫucủacặpbàitoánđó: nếumộtràngbuộc(của
bài toán này) thỏamãnvớidấubất đẳng thứcthực
sự (thỏa mãn lỏng) thì ràng buộc còn lại(củabài
toán kia) phảithỏamãnvớidấu đẳng thức(thỏa
mãn chặt), i.e.,
14
8
Các định lý đối ngẫu
.
15
00 0 0
11
- Neáu 0 hay 0 thì
jjjmjmj
x
xayayc 
00 0

-Giải hệ này tìm nghiệm y
0
.
Bước 3: Kết luận lời giải cho bt (D)
-Nếu y
0
thỏa các Rb còn lại của (D) thì
nó là PATƯ cần tìm của (D).
16
9
2.2 Giải BTĐN khi biết PATƯ BT gốc
Vi dụ 2.2.1:
Có phương án tối ưu la x
0
=(7,0,-9) . Hãy lập và
giải bài toán đối ngẫu của bài toán trên?
17
123
123
123
123
12 3
34 min
32415
2 5 8
4 2 2 10 (2.2.1)
, 0; 0
 
  
 

1
2
3
y
y
y











12 3
15 8 10 maxZyyy


123
3243yyy


123
2 2 4yyy


123




1
2
3
1/5
0
9/10
y
y
y








max
12Z


2.3 Ứng dụng của bài toán đối ngẫu
2.3.1 Giải bt QHTT bằng bài toán đối ngẫu.
2.3.2 Kiểm chứng tính tối ưu của một PA.
2.3.3 Tìm tập PATƯ của một bài toán QHTT
20
11

1
min,( 0)
,( 0),( 1, ) (P2.3.1)
0,( 1, )
n
jj j
j
n
ij j i i
j
j
Zcx c
ax b b i m
xjn


 




2.3.1 Giải bt QHTT bằng bài toán đối ngẫu
Giải (Q2.3.1) bằng cách thêm vào n biếnphụ
y
m+k
, (k=1, ,n) và dùng PP đơn hình.
Nếu(Q2.3.1)tối ưuthìcáchệ sốướclượng trong
bảng đơnhìnhtối ưu(
m+1
, , 

2.3.1 Giải bt QHTT bằng bài toán đối ngẫu
Ví dụ 2.3.1 Giải bt QHTT sau:
Chỉ cần thêm vào 3 biến phụ y
4
,y
5
,y
6
ta sẽ có bt
dạng chuẩn.
25
123
123
12 3
123
12 27 6 min
2 3 2 12
(P3.1) 3 6
6 9 2 24
0, 1,3
j
Zx xx
xx x
xx x
xxx
xj


 


vào cơ sở, y
4
ra khỏi cơ sở, phần tử trụ a
13
=6
26
CS c
B
PA y
1
y
2
y
3
y
4
y
5
y
6

j
126240 0 0
y
4
0122 1 6 10 02
y
5
02733901 03
y

6

j
12 6 24 0 0 0
y
3
24 2 1/3 1/6 1 1/6 0 0 6
y
5
0 9 0 3/2 0-3/21 0-
y
6
024/3 2/3 0 -1/3 0 1 3/2

i
48 -4 -2 0 4 0 0
27
2.3.1 Giải bt QHTT bằng bài toán đối ngẫu
Bảng 3
Do 
i
 0, i nên PA đã tối ưu.
CS c
B
PA y
1
y
2
y
3

=(3, 0, 3) thỏa các RB củabt(P3.1)nên
nó là PATƯ của bài toán và Z
min
=54.
29
123
123
2
23212
692 24
0
xx x
xxx
x








1
2
3
3
0
3
x
x

n
. Hỏi x
0
có
phải là PATƯ của (P) không?
Lời giải:
Bước 1: Kiểm tra x
0
có là PA của (P) không.
Nếu phảiBước 2
Bước 2: Lập btđn (Q) của (P). Giả sử x
0
là
PATƯ của (P).
Bước 3: Lập hệ PT tối ưu theo biến bt (Q).
31
2.3.2 Kiểm chứng tính tối ưu của một PA.
Giảihệ pt tối ưu tìm nghiệm:
-Nếuhệ vô nghiệm x
0
không là PATƯ
-Nếuhệ có nghiệmy
0
∈R
m
Bước4
Bước4:
-Nếuy
0
không thỏacácRBcònlạicủa(Q)

3 + 2 4 (P2.3.2)
4
, , , 0
    


 

Zxxxx
xxx
xx
xx x
xx xx
2.3.2 Kiểm chứng tính tối ưu của một PA.
Ta thấyx
0
thỏacácRBcủa (P2.3.2) nên nó là PA
của (P2.3.2).
BTĐNcủa (P2.3.2) là:
34
123
12
3
13
123
2
644 max
3 2
2
2 4 (Q2.3.2)

12
13
0
3 2
2 4
y
yy
yy



 




1
2
3
2
0
0
y
y
y






37
12
12
12
12
1
2 3 min
2 2
2 (P3.3)
2 3 12
1






Zxx
xx
xx
xx
x
2.3.3 Tìm tập PATƯ của một bài toán QHTT
BTĐN của (P3.3) là:
Do x
*
=(-9/4, -5/2) là PATƯ của (P3.3) nên theo đlý
đ.l.b.y ta có hệ
38
12 34





20
2.3.3 Tìm tập PATƯ của một bài toán QHTT
y
*
=(0,0,1,0) thỏa các RB của(Q3.3)nênnólà
PATƯ cùa (Q3.3). Theo đlý đ.l.b.y ta có hệ:
Tập nghiệm pt:
Để  là tậpPATƯ của(P3.3)thì phảithỏahệ
39

12
23 12xx


{( 6 3 / 2, )/ }



 
2( 6 3 / 2) 2
14 5
63/2 2
32
63/21

 