Tháng 3 - 2008
Tháng 3 - 2008
LÊ HU NH TUY T ANHỲ Ế
LÊ HU NH TUY T ANHỲ Ế
QUY HO CH TUY N TÍNHẠ Ế
QUY HO CH TUY N TÍNHẠ Ế
PHÁT BI U BÀI TOÁN QUY HO CH TUY N TÍNHỂ Ạ Ế
ymax = max c1x1 + c2x2 + ... + cnxn
ymin = min c1x1 + c2x2 + ... + cnxn
Ràng bu cộ
a x + a x + ... + a x (≤, =, ≥) b
Bài toán quy ho ch tuy n tính thu c lo i bài ạ ế ộ ạ
toán t i u ố ư th c đ nhự ị
I U KI N BÀI TOÁN T I U THU C D NG Đ Ề Ệ ĐỂ Ố Ư Ộ Ạ
I U KI N BÀI TOÁN T I U THU C D NG Đ Ề Ệ ĐỂ Ố Ư Ộ Ạ
BÀI TOÁN QUY HO CH TUY N TÍNHẠ Ế
BÀI TOÁN QUY HO CH TUY N TÍNHẠ Ế
HÀM M C TIÊUỤ là hàm b c nh t đ i v i các bi nậ ấ ố ớ ế
CÁC ĐI U KI N RÀNG BU CỀ Ệ Ộ
ph i đ c th hi n qua ả ượ ể ệ
các hàm toán h c b c nh t tuy n tínhọ ậ ấ ế
PH NG PHÁP THƯƠ ĐỒ Ị
PH NG PHÁP THƯƠ ĐỒ Ị
Th i gian làm vi c ờ ệ
Th i gian làm vi c ờ ệ Đ t sétấ
Đ t sétấ Doanh thu
Doanh thu
S n ph mả ẩ
S n ph mả ẩ (gi /đ n v )ờ ơ ị
(gi /đ n v )ờ ơ ị (kg/đ n v )ơ ị
(kg/đ n v )ơ ị (1000$/đ n v )ơ ị
(1000$/đ n v )ơ ị
Tô
Tô 1
1 4
4 40
40
Bình
Bình 2
2 3
3 50
50
Trong m t x ng m i ngàyộ ưở ỗ
Trong m t x ng m i ngàyộ ưở ỗ ,
,
có t i đa 40 gi làm vi c và 120 kg ố ờ ệ
có t i đa 40 gi làm vi c và 120 kg ố ờ ệ
đ t sét đ s n xu t tô và bình. ấ ể ả ấ
đ t sét đ s n xu t tô và bình. ấ ể ả ấ
V iớ
V iớ
x
x1
1 = s tô đ c s n xu t trong ngàyố ượ ả ấ
= s tô đ c s n xu t trong ngàyố ượ ả ấ
x
x2
2 = s bình đ c s n xu t trong ngàyố ượ ả ấ
= s bình đ c s n xu t trong ngàyố ượ ả ấ
BÀI TOÁN
BÀI TOÁN
PHÁT BI U BÀI TOÁN T I UỂ Ố Ư
PHÁT BI U BÀI TOÁN T I UỂ Ố Ư
y
y
max
max
= Max 40
= Max 40 x
x
1
1
+ 50
+ 50 x
x
2
2
Đi u ki n ràng bu cề ệ ộ
Đi u ki n ràng bu cề ệ ộ
x
x1
1+
+2
2x
x2
2≤
≤ 40
40 (ràng bu c v gi làm ộ ề ờ
(ràng bu c v gi làm ộ ề ờ
vi c)ệ
vi c)ệ
4
4x
x1
1+
+3
3x
x2
2≤
≤ 120
120 (ràng bu c v đ t sét)ộ ề ấ
(ràng bu c v đ t sét)ộ ề ấ
x
x1
1 ,
, x
x2
2 ≥
≥ 0
0