CH NG IƯƠ
BÀI TOÁN QUY HO CH TUY N TÍNHẠ Ế
1.1/ M T S VÍ D D N Đ N BÀI TOÁN QUY HO CH TUY N TÍNH: Ộ Ố Ụ Ẫ Ế Ạ Ế
1.1.1. Bài toán v n chuy n:ậ ể
T i sân bay Tân S n Nh t có nhu c u v n chuy n 1200 hành khách và 120 t nạ ơ ấ ầ ậ ể ấ
hàng b ng máy bay. Gi s có 2 lo i máy bay có th s d ng v i kh năng v n chuy nằ ả ử ạ ể ử ụ ớ ả ậ ể
c a m i lo i nh sau: ủ ỗ ạ ư
Máy bay lo i A: 01 máy bay có th ch 150 hành khách và 20 t n hàng v i chi phíạ ể ở ấ ớ
t ng ng 240 tri u đ ng.ươ ứ ệ ồ
Máy bay lo i B: 01 máy bay ch có th ch 180 hành khách và 16 t n hàng v i chiạ ở ể ở ấ ớ
phí t ng ng là 220 tri u đ ng.ươ ứ ệ ồ
Hãy l p mô hình tìm ph ng án s d ng s máy bay m i lo i sao cho ph i th aậ ươ ử ụ ố ỗ ạ ả ỏ
mãn yêu c u v n chuy n v i t ng chi phí ít nh t.ầ ậ ể ớ ổ ấ
L p mô hình: ậ
G i xọ1 là s l ng máy bay lo i Aố ượ ạ
G i xọ2 là s l ng máy bay lo i Bố ượ ạ
T ng chi phí (tri u đ ng): ổ ệ ồ Z = 240 x1 + 220x2
Đ m b o v hành khách: ả ả ề 150 x1 + 180x2 = 1200
Đ m b o v hàng hóa: ả ả ề 20 x1 + 16 x2 = 120
Đ m b o th c t :ả ả ự ế x1,x2 ≥ 0
Gi i bài toán:ả
Z = 240 x1 + 220x2
→
min (*)
( )
1 2
1 2
150 180 1200
20 16 120
0; 1, 2
j
x x
x x
x j
+ =
+ =
≥ =
Gi i h ph ng trình trên ả ệ ươ x1 = 2, x2 = 5 thay x1 và x2 vào (* )
→
Z = 1580
1.1.2/ Bài toán kh u ph n th c ănẩ ầ ứ :
Đ nuôi m t lo i gia súc ng i ta s d ng 3 lo i th c ăn A, B, C. T l % theoể ộ ạ ườ ử ụ ạ ứ ỷ ệ
kh i l ng các ch t dinh d ng Pố ượ ấ ưỡ 1, P2 có trong các lo i th c ăn nh sauạ ứ ư :
Th c ănứCh tấ dinh d ngưỡ
P1P2
A 20 10
B 10 10
C 10 20
Yêu c u trong kh u ph n th c ăn c a lo i gia súc này:ầ ẩ ầ ứ ủ ạ
- Ch t dinh d ng Pấ ưỡ 1 ph i có ít nh t là 70g và nhi u nh t là 80gả ấ ề ấ
- Ch t dinh d ng Pấ ưỡ 2 có ít nh t là 90gấ
- Giá 1kg th c ăn A,B,C t ng ng là 2.000đ, 1.000đ, 2.000đứ ươ ứ
Yêu c uầ : Hãy l p mô hình bài toán xác đ nh khậ ị ối l ng th c ăn c n mua saoượ ứ ầ
cho t ng chi phí ít nh t.ổ ấ
L p mô hình bài toánậ :
G i xọ1, x2, x3 t ng ng là s g th c ăn A, B, C c n muaươ ứ ố ứ ầ
- T ng chi phí Z = 2xổ1 + x2 + 2x3
- Hàm l ng các ch t dinh d ng ượ ấ ưỡ
P1: 0,2x1 + 0,1x2 + 0,1x3 thu c [ 70,80] (g)ộ
P2: 0,1 x1 + 0,1x2 + 0,2 x3 ≥ 90 (g)
( )
0 1, 2,3
j
x j≥ =
Bài toán: Tìm xj (j= 1,2,3) sao cho
Z = 2x1+ x2 + 2x3
→
min
≥
≥+
≤++
≥++
0,,
9002
8002
70022
321
321
321
321
xxx
xxx
xxx
xxx
1.1.3/ Bài toán th i gian thi công ng n nh t:ờ ắ ấ
Đ đ m b o hoàn thành k ho ch, đ n v s a ch a và b o d ng đ ng nh a Aể ả ả ế ạ ơ ị ử ữ ả ưỡ ườ ự
c n g p rút hoàn thành 50km s n v ch m t đ ng, trong đó s km đ ng đ c s n kầ ấ ơ ạ ặ ườ ố ườ ượ ơ ẻ
v ch c a đ ng c p I không nh h n 20% t ng chi u dài đ c s n k v ch c aạ ủ ườ ấ ỏ ơ ổ ề ượ ơ ẻ ạ ủ
đ ng c p II và c p III.ườ ấ ấ
Đ n v A ch có 1 dây chuy n ( ng i, máy) đ làm vi c này. Trong khi đ th iơ ị ỉ ề ườ ể ệ ể ờ
gian hoàn thành 1km đ ng c p I, II, III t ng ng là 12 ngày, 8 ngày và 6 ngày.ườ ấ ươ ứ
Đ nh m c ti n s n cho 1km đ ng c p I, II, III t ng ng là 30, 20 và 15 tri uị ứ ề ơ ườ ấ ươ ứ ệ
đ ng, trong khi kinh phí dành cho công vi c này trong th i gian t i ch còn 120 (tri uồ ệ ờ ớ ỉ ệ
đ ng).ồ
Hãy l p mô hình xác đ nh chi u dài s n k v ch cho m i c p đ ng sao cho t ngậ ị ề ơ ẻ ạ ỗ ấ ườ ổ
th i gian th c hi n là ng n nh t, đ ng th i đ m b o v kinh phí mua s n.ờ ự ệ ắ ấ ồ ờ ả ả ề ơ
L p mô hình:ậ
G i xọ1, x2, x3 là chi u dài (km) d đ nh th c hi n trong t ng ng c p đ ng lo iề ự ị ự ệ ươ ứ ấ ườ ạ
I, II, III khi đó.
M c tiêu th i gian: Z =ụ ờ
Yêu c u kh i l ng: ầ ố ượ
Yêu c u ch ng lo i:ầ ủ ạ
Yêu c u kinh phíầ
Đi u ki n t t y u: xề ệ ấ ế 1, x2, x3
0≥
Bài toán:
1.2/ Đ NH NGHĨA VÀ CÁC D NG BÀI TOÁN QUY HO CH TUY N TÍNH Ị Ạ Ạ Ế
1.2.1/ Đ nh nghĩa: ị
Bài toán quy ho ch tuy n tính d ng t ng quát: tìm (xạ ế ạ ổ 1, x2, …, xn) sao cho
f (x) = c1x1+ c2x2 + cnxn =
∑
=
n
j
jj xc
1
min→
(max) (1)
V i đi u ki n ớ ề ệ
1
( 1, 2,.., )(2)
0
0 (1, 2,..., )(3)
n
ij j i
j
j
a x b i m
x j n
Tùyý
=
≤
= =
≥
≥
≤ =
∑
+ Các bi g i là các h s t do ọ ệ ố ự
+ Các cj g i là h s hàm m c tiêu ( h s )ọ ệ ố ụ ệ ố
+ aij g i là h s các ràng bu c chungọ ệ ố ộ
+ f(x) g i là hàm m c tiêuọ ụ
+ H (*) g i là h ràng bu cệ ọ ệ ộ
(2) g i là ràng bu c chung (có m ràng bu c) ọ ộ ộ
(3) g i là ràng bu c bi n (có n ràng bu c)ọ ộ ế ộ
Vector x = (x1, x2, … xn) g i là ph ng án (P.A) n u x th a (*) t p h p t t c cácọ ươ ế ỏ ậ ợ ấ ả
ph ng án g i là mi n ràng bu c kí hi u là Dươ ọ ề ộ ệ
-M t ph ng án làm cho hàm m c tiêu đ t c c ti u ( ng v i bài toán tìm min c aộ ươ ụ ạ ự ể ứ ớ ủ
f (min f) ho c c c đ i (max f) g i là ph ng án t i u đ c ký hi u là xặ ự ạ ọ ươ ố ư ượ ệ opt
Nghĩa là:
BT min:
x
∈
D : f (x)
≥
f (xopt)
BT max:
x
∈
D : f (x)
≤
f (xopt)
Gi i bài toán quy ho ch tuy n tính là tìm các ph n t t i u (n u có)ả ạ ế ầ ử ố ư ế
+ Hai bài toán quy ho ch tuy n tính g i là t ng đ ng nhau n u chúng có chungạ ế ọ ươ ươ ế
ph n t t i u.ầ ử ố ư
M nh đ : ệ ề Quan h gi a max f và min fệ ữ
∈
⇒
Dx
xf max)(
⇔
( ) ( ) ming x f x
x D
= − ⇒
∈
1.2.2/ Bi u di n bài toán quy ho ch tuy n tính d i d ng ma tr n:ể ễ ạ ế ướ ạ ậ
G iọ
11 12 1
21
1
...
...
n
m mn
a a a
a
A
a a
=
là ma tr n ậc p m*n các h s các ấ ệ ố ràng bu c chung ộ
x1
X = … , CT = (c1, c2, …,cn)
xn
b1
B =
….
bm
Lúc đó bài toán quy ho ch tuy n tính đ c phát bi u ạ ế ượ ể
Tìm x = ( x1, x2, …, xn) sao cho
f(x) = CT x
→
min (max)
th a mãn:ỏ
A.X B
≥
X ≥ 0 ; trong ≤
=
1.2.3/ Các d ng c a bài toán quy ho ch tuy n tính và các quy t c bi n đ i.ạ ủ ạ ế ắ ế ổ
1.2.3.1: D ng chính t c ạ ắ
( )
( )
1
1
( ) min max
( 1, 2..., )
0 1, 2,...,
n
j j
j
n
ij j i
j
j
f x c x
a x b i m
x j n
=
=
= →
= =
≥ =
∑
∑
Ta nh n xét r ng, b t kỳ bài toán quy ho ch tuy n tính nào cũng có th đ a vậ ằ ấ ạ ế ể ư ề
d ng chính t c nh các quy t c bi n đ i sau:ạ ắ ờ ắ ế ổ
•N u ràng bu c có d ng : ế ộ ạ
i
n
j
jij
bxa
≥
∑
=
1
thì ta đ a v d ng t ng đ ng :ư ề ạ ươ ươ
i
n
j
njij
bxxa
=−
∑
=+
1
1
v i ớ
1
0
n
x
+
≥
là n ph )ẩ ụ
• N u ràng bu c có d ng : ế ộ ạ
1
n
ij j i
j
a x b
=
≤
∑
thì ta đ a v d ng t ng đ ng ư ề ạ ươ ươ
∑
=+
=+
n
j
injij
bxxa
1
1
v i ớ
1
0
n
x
+
≥
là n ph )ẩ ụ
Chú ý:
- H s c a n ph trong hàm m c tiêu f(x) là 0.ệ ố ủ ẩ ụ ụ
- N u bi n xế ế j ≤ 0 thì ta thay b ng xằj’ : xj’ = - xj (xj’ ≥ 0)
- N u bi n xế ế j không ràng bu c v d u ta thay b ng hi u c a 2 bi n không, t c làộ ề ấ ằ ệ ủ ế ứ
đ t ặ
xj = xj’ - xj’’ v i xớj’ ≥ 0, xj’’ ≥ 0
Chú ý r ng:ằ Đây không ph i là bi n ph nên ph i tính l i hàm m c tiêu theo cácả ế ụ ả ạ ụ
bi n m i.ế ớ
Các ví d : đ a các bài toán QHTT sau v d ng chính t c ụ ư ề ạ ắ
1/ f(x) = -2x1 +3x2 - 2x3
→
min
≥
−=+
=−+
0,,
33
222
321
31
321
xxx
xx
xxx
Ví d 1 này là d ng chính t c vì x y ra d u = và xụ ạ ắ ả ấ 1, x2, x3 ≥ 0