BÀI 3
1) Muc đich : Giai bai toan QHTT co ân gia. Bai toan
nay xuât hiên khi chuyên bai toan dang chinh tăc vê
bai toan dang chuân băng cach đ a vao ân gia đê tao ư
ma trân đ n vi. ơ
- T bai toan xuât phat dang chinh tăc:ư
1
( )
n
j
f x c x
j j
=
=
Min (Max)
ij
, 1,...,
j i
a x b i m= =
0; 1,...,x j n
j =
Ta chuyên vê bai toan:
- Bai toan dang chuân v i biên gia (bai toan m rông hay ơ ơ
bai toan M).
( )
( )
, min
1 1
, max
1 1
n m
g g
g x x c x M x
i j j i
i i
n m
g g
g x x c x M x
i j j i
i i
= +
� �
= =
= −
� �
= =
� �
� �
� �
( )
, 1,...,
1
0, 0 1,..., ; 1,...,
ng
a x x b i m
ij j i i
j
x x i m j n
j i
+ = =
=
= =
Vi du 1:
( )
8 6 2 min
1 2 3
4 4 3 18
1 2 3
4 3 4 16
1 2 3
0, 1,2,3
f x x x x
x x x
x x x
x j
j
= − + +
+ − =
+ + =
=
Suy ra ta co bai toan dang chuân v i biên gia: ơ
( )
( )
8 6 2 min
5
1 2 3 4
4 4 3 18
1 2 3 4
4 3 4 16
5
1 2 3
0, 1,2,3,4,5
g x x x x M x x
x x x x
x x x x
x j
j
= − + + + +
+ − + =
+ + + =
=
2) Quan hê gi a bai toan xuât phat va bai toan m rông: ư ơ
Gia s (x*, x ư ig) la ph ng an cua bai toan m rông, ta co: ươ ơ
Nêu x la PA cua bai toan xuât phat thi (x*, x ig) = (x, 0)
la ph ng an cua bai toan m rông. Ng c ươ ơ ươ
lai ph ng an cua bai toan m rông la (x*, x ươ ơ ig) = (x, 0) thi
x la ph ng an cua bai toan xuât phat. ươ
x la ph ng an c ban cua bai toan xuât phat ươ ơ (x, 0)
la PACB cua bai toan m rông. ơ
( )
0,
g
i
x i
= ∀