Chương 2
LÝ THUYẾT ĐỐI NGẪU
20/6/2012 1MaMH: 501014 Chương 1: Bài toán Quy hoạch tuyến tính
NỘI DUNG
1. Bài toán đối ngẫu quy hoạch tuyến tính
1.1 Xây dựng bài toán đối ngẫu
1.2
Các
định
lý
đối
ngẫu
1.2
Các
định
lý
đối
ngẫu
2. Phương pháp đơn hình đối ngẫu
20/6/2012 2MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
Bài toán đối ngẫu QHTT
1. Xây dựng bài toán đối ngẫu QHTT
Xét bài toán
( ) nmi
n
j
j
cf x x
= →
∑
20/6/2012 3MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1
1
, 1,
( )
0, 1, .
j
j
n
iij j
j
j
j
b
a x i m
P
x j n
=
≥ =
≥ =
∑
∑
Bài toán đối ngẫu QHTT
Bài toán đối ngẫucủa bài toán trên là
1
( ) xma
m
i
i
i
bg y y
=
= →
∑
∑
20/6/2012 4MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
1
, 1,
( )
0, 1, .
jij i
i
i
c
a y j n
D
y i m
=
≤ =
≥ =
∑
Bài toán đối ngẫu QHTT
Nhận xét:
•Cảhai bài toán đềuở dạng chuẩn tắc;
•
Một
bài
toán
min
,
một
bài
toán
max;
•
Một
bài
toán
min
,
một
bài
toán
max;
•Sốbiến của bài toán này là sốràng buộc của bài
toán kia và ngược lại;
•và đổi vai trò cho nhau.
20/6/2012 5MaMH: 501014 Chương 2: Lý thuyết đối ngẫu
j
c
i
b