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.1 Ý nghĩa và cách lập bài toán đối ngẫu
Xét bài toán sản xuất tối ưu:
Có một đối tác đặt vấn đề mua toàn bộ nguyên
liệu của cty A. Hãy lập bài toán định giá mua
ng/liệu rẻ nhất.
1 2 3
1 2 3
1 2 3
1 2 3
2 3 4 max
10 20 30 10000
20 30 30 50000 (2.1.1)
20 30 40 30000
0, 1, 2,3
j
Z x x x
x x x
x x x
x x x
xj

3
Ý nghĩa và cách lập bài toán đối ngẫu
Gọi yi, i=1,2,3 là giá mua 1 đ/vị nguyên liệu
đường, sữa, bột tương ứng.
Bài toán (2.1.1)’ gọi là BTĐN của (2.1.1).
1 2 3
1 2 3
1 2 3
1 2 3
10000 50000 30000 min
10 20 20 2
20 30 30 3 (2.1.1)
30 30 40 4
0, 1, 2,3
i
Z y y y
y y y
y y y
y y y
yi

4
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
Z c x c x
11 min
mm
Z b y b y
1
,( 1, )
n
ij j i
j
a x b i m





0
0 ,( 1, )
tù ý
j
x j n
y





1
,( 1, )
m
ij i j
i
a y c j n





0
0 ,( 1, )
tùy ý
i
y i m





RBD ngược dấu RBC
RBC cùng dấu RBD xj