BÀI 3
1. Cach thiêt lâp bai toan đôi ngâu:
( )
1 1
... max
n n
f x c x c x
= + +
( )
1 1
... min
m m
f y b y b y
= + +
%
1 1
... , 1,...,
i in n i
a x a x b i m
��
��
+ + =
��
��
=
��
0
0 , 1,...,
tuy y
i
y i m
� �
� �
=
� �
� �
� �
0
0 , 1,...,
tuy y
j
x j n
� �
� �
=
� �
� �
� �
1
... , 1,...,
ij mj m j
a y a y c j n
��
��
+ + =
��
��
=
��
( )
P
%
( )
P
* Nguyên tăc thiêt lâp bai toan đôi ngâu:
1) Nêu f(x) min (max) thi max (min)
2) Sô rang buôc chinh trong bai toan nay băng sô biên
sô trong bai toan kia
3) Hê sô trong ham muc tiêu cua bai toan nay la hê sô t ư
do cua hê rang buôc trong bai toan kia.
4) Ma trân điêu kiên cua hai bai toan la chuyên vi cua
nhau.
5) Rang buôc vê biên cua bai toan nay t ng ng v i ươ ư ơ
rang buôc vê dâu cua bai toan kia.
6) Biên không co rang buôc vê dâu trong bai toan nay thi
rang buôc t ng ng trong bai toan kia co dâu “=” ươ ư
7) Rang buôc bât đăng th c trong h ràng bu c chính ư ệ ộ
c a bai toan min cung chiêu v i rang buôc dâu trong bai ủ ơ
toan max
8) Rang buôc bât đăng th c trong h ràng bu c chính ư ệ ộ
c a bai toan max ng c chiêu v i rang buôc dâu trong ủ ươ ơ
bai toan min.
( )
f y
%
Vi du 1: vi t bài toán đ i ng u c a bài toán QHTT sau: ế ố ẫ ủ
( )
( )
( )
( )
( )
( )
4
4
1
2
3
2 3 4 min
1 2 3 4
2 3
1 2 3 4
3 7 7
1 2 3
2 4 18
1 2 3
6
20
32 1
2
0 3
0 4
0 5
f x x x x x
x x x x
x x x x
x x x x
x
x
x
= +
+ +
− + +
+ + +
− −
− =
−
( )
( )
( )
( )
( )
: 20 32 18 max
1 2 3
y 3 2 2 6
1 2 3
2y 4 3 7
1 2 3
3y 7 4 8
1 2 3
y 7 6
1 2 3
tuy y
1
P f y y y y
y y
y y
y y
y y
y
= + +
− +
− + −
+ +
− + + = −
%
%
( )
( )
y 0 9
2
y 0 10
3