Ch ng Iươ
BÀI TOÁN QUY HO CH TUY N TÍNHẠ Ế
Bài 2. BÀI TOÁN QHTT VÀ Ý NGHĨA
HÌNH H C .Ọ
1. D ng t ng quát c a bài toán Quy ạ ổ ủ
ho ch tuy n tính.ạ ế
Bài toán Quy ho ch tuy n tính t ng ạ ế ổ
quát có d ng sau đâyạ
Tìm giá tr l n nh t hay nh nh t c a hàm ị ớ ấ ỏ ấ ủ
1 1 2 2
( ) ..
n n
f x c x c x c x= + + +
v i các ràng bu c:ớ ộ
i1 1 i2 2 in 1
i1 1 i2 2 in 2
i1 1 i2 2 in 3
1 2 3
.. ; (1)
.. ; (2)
.. ; (3)
0 ; , 0 ; , ; .
n i
n i
n i
j j j
a x a x a x b i I
a x a x a x b i I
a x a x a x b i I
x j J x j J x R j J
+ + +
+ + +
+ + + =
� ���
Trong đó r i nhau và ờ
, r i nhau và .ờ
1 2 3
, ,I I I
{ }
1 2 3
1,2,..,I I I m
=� �
1 2 3
, ,J J J
{ }
1 2 3
1,2,..,J J J n
=� �
Ví d 1:ụ
1 2 3 4
1 2
1 3 4
1 2 3
1 2 3 4
1 3
2
4
( ) 4 min
2 1
4 2
0
4 5 5 17
; 0
0.
f x x x x x
x x
x x x
x x x
x x x x
x x
x R
x
= + − +
+
− − −
+ +
+ − + =
{ } { } { } { } { } { }
1 2 3 1 2 3
1,2 , 3 , 4 , 1,3 , 4 , 2I I I J J J
= = = = = =
đây là bài toán Quy ho ch tuy n tính Ở ạ ế
d ng t ng quát, vàạ ổ
Ví d ụ
2:
1 2 3 4
1 2 5
1 3 4 5
1 2 3 5
1 2 3 4 5
1 2 3 4
1 5 2 3 4
( ) 4 max
2 6 1
4 4 2
16 2
4 5 5 17
9 5 2 11
; 0, ; , 0.
f x x x x x
x x x
x x x x
x x x x
x x x x x
x x x x
x x x x R x
= + − +
+ +
− − − −
+ + +
+ − + + =
+ + +
Σ�
{ } { } { } { } { } { }
1 2 3 1 2 3
1,3 , 2,5 , 4 , 1,5 , 4 , 2,3I I I J J J
= = = = = =
đây là bài toán Quy ho ch tuy n tính Ở ạ ế
d ng t ng quát, vàạ ổ
2. M t s khái ni m c a bài toán Quy ộ ố ệ ủ
ho ch tuy n tính:ạ ế
Hàm m c tiêu: Là hàm ụ
1
( ) ,
n
j j
j
f x c x c x
=
= =��
Ph ng án: ươ
1 2
( , ,.., )
n
x x x x
=
Véctơ
th a t t c các ỏ ấ ả ràng bu cộ g i là m t ọ ộ
ph ng án. ươ