TR NG Đ I H C KINH T K THU T CÔNG NGHI P ƯỜ Ạ Ọ Ế Ỹ Ậ Ệ
B MÔN KHOA H C C B NỘ Ọ Ơ Ả
BÀI GI NGẢ
QUY HO CH TUY N TÍNHẠ Ế
Ch ng ươ I: BÀI TOÁN QUY HO CH TUY N Ạ Ế
TÍNH
Ch ng ươ II: BÀI TOÁN V N T IẬ Ả
Ch ng ươ III: MÔ HÌNH S Đ M NG L IƠ Ồ Ạ ƯỚ
CH NG I:ƯƠ
BÀI TOÁN QUY HO CH TUY N TÍNHẠ Ế
1.1. Bài toán quy ho ch tuy n tính t ng quátạ ế ổ
1.2. Bài toán d ng chính t cạ ắ
1.3. Bài toán d ng chu nạ ẩ
1.4. Các tính ch t chungấ
1.5. Ph ng pháp đ n hìnhươ ơ
1.6. Ph ng pháp đ n hình đ i ng uươ ơ ố ẫ
1.1. Bài toán quy ho ch tuy n tính t ng quátạ ế ổ
Hàm f(x) g i là hàm m c tiêuọ ụ
M i ph ng trình ho c b t ph ng trình trong h đi u ỗ ươ ặ ấ ươ ệ ề
ki n g i là m t ràng bu c. ệ ọ ộ ộ
( )
( )
( ) ( )
∈≤≥
∈=
→=
∑
∑
∑
=
=
=
2
n
1j
ijij
1i
n
1j
jij
n
1j
jj
Ii bxa
Ii bxa
(max)min xcxf
■ M t s khái ni m :ộ ố ệ
Ph ng ánươ
Ph ng ánươ :
: Vect x = (xơ
Vect x = (xơ1
1, x
, x2
2,..., x
,..., xn
n) tho mãn m i đi u ả ọ ề
) tho mãn m i đi u ả ọ ề
ki n ràng bu c c a bài toán g i là m t ph ng ánệ ộ ủ ọ ộ ươ
ki n ràng bu c c a bài toán g i là m t ph ng ánệ ộ ủ ọ ộ ươ .
.
-N u thì ràng bu c i g i là “ch t” đ i v i ế ộ ọ ặ ố ớ
ph ng án x, ho c ph ng án x tho mãn ch t ràng bu c i.ươ ặ ươ ả ặ ộ
∑
=
=
n
1j
ijij
bxa
-N u thì ràng bu c i g i là “l ng” đ i v i ế ộ ọ ỏ ố ớ
ph ng án x, ho c ph ng án x tho mãn l ng ràng bu c i.ươ ặ ươ ả ỏ ộ
∑
=
<>
n
1j
ijij
)b(xa
Ph ng án t i uươ ố ư : M t ph ng án mà t i đó tr s hàm ộ ươ ạ ị ố
m c tiêu đ t c c ti u (ho c c c đ i) g i là ph ng án t i ụ ạ ự ể ặ ự ạ ọ ươ ố
u.ư
Ph ng án c c biênươ ự : M t ph ng án th a mãn ch t n ộ ươ ỏ ặ
ràng bu c đ c l p tuy n tính g i là ph ng án c c biên.ộ ộ ậ ế ọ ươ ự