Xem mẫu
- ðH Công nghi p Tp.HCM 23/12/2010
Chương I xí nghi p có là 8, 24, 12. S lư ng các
nguyên li u c n ñ s n xu t m t ñơn v s n
BÀI TOÁN QUY HO CH TUY N TÍNH
ph m A, B ñư c cho b ng sau ñây.
Bài 1. M T S BÀI TOÁN D N ð N
BÀI TOÁN QHTT. I (
- ðH Công nghi p Tp.HCM 23/12/2010
Có ba xí nghi p may I, II, III cùng có XN I II III
th s n xu t áo vét và qu n.
N u ñ u tư 1000 USD vào XN I thì
S.P
cu i kỳ s cho 35 áo vét và 45 qu n
Áo vét 3.5 m v i 4m v i 3.8 m v i
N u ñ u tư 1000 USD vào XN II thì cu i 20 gi công 16 gi công 18 gi công
kỳ s cho 40 áo vét và 42 qu n
N u ñ u tư 1000 USD vào XN III thì cu i Qu n 2.8 m v i 2.6 m v i 2.5 m v i
kỳ s cho 43 áo vét và 30 qu n 10 gi công 12 gi công 15 gi công
Lư ng v i và s gi công ñ sx m t áo
ho c m t qu n cho b ng sau.
4. T ng s v n ñ u tư nh nh t .
T ng s v i và gi công mà công ty có
th có là 10 000m và 52 000 gi công . L p k ho ch.
Theo h p ñ ng thì cu i kỳ ph i có t i thi u Gi s xj (ñơn v là 1000 USD) là s
1500 b qu n áo, n u l b thì qu n d bán v n ñ u tư vào các XN I, II, III.
hơn. a) S áo vét thu ñư c ba XN là
Hãy l p m t k ho ch ñ u tư vào m i 35x1+40x2+43x3
XN bao nhiêu v n ñ : b) S qu n thu ñư c ba XN là
1. Hoàn thành k ho ch s n ph m.
45x1+42x2+30x3
2. Không khó khăn v tiêu th . c) T ng s v i c n ñ may áo vét là
3.Không thi u v i và gi công lao ñ ng
20 × 35 x1 + 16 × 40 x2 + 18 × 43 x3 +
3.5m × 35 x1 + 4m × 40 x2 + 3.8m × 43x3
d) T ng s v i c n ñ may qu n là
10 × 45 x1 + 12 × 42 x2 + 15 × 30 x3 =
2.8m× 45x1 + 2.6m× 42x2 + 2.5m×30x3
= 1150 x1 + 1144 x2 + 1224 x3
e) T ng s v i mà XN ph i dùng là
Ta có bài toán như sau
3.5m× 35x1 + 4m× 40x2 + 3.8m× 43x3 +
2.8m× 45x1 + 2.6m× 42x2 + 2.5m× 30x3 =
= 248.5x1 + 269.2x2 + 238.4x3 (m)
f) Tương t như trên t ng s gi công lao
ñ ng mà XN ph i dùng là
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 2
- ðH Công nghi p Tp.HCM 23/12/2010
( ) Có th vi t l i bài toán trên như sau
min x + x + x
123
f = x + x + x → min
248.5 x1 + 269.2 x2 + 238.4 x3 ≤ 10 000 (1) 123
248.5 x + 269.2 x + 238.4 x ≤ 10 000 (1)
1150 x1 + 1144 x2 + 1224 x3 ≤ 52 000 (2) 1 2 3
1150 x1 + 1144 x2 + 1224 x3 ≤ 52 000 (2)
45 x1 + 42 x2 + 30 x3 ≥ 35 x1 + 40 x2 + 43x3 (3)
35 x + 40 x + 43x ≥ 1500 10 x1 + 2 x2 − 13 x3 ≥ 0 (3)
(4)
1
2 3
35 x1 + 40 x2 + 43x3 ≥ 1 500 (4)
(1) ñi u ki n v lư ng v i. (2) ñi u ki n v
x j ≥ 0, ∀j = 1, 2,3
gi công lao ñ ng. (3) s qu n nhi u hơn s (5)
áo. (4) s b qu n áo t i thi u.
2. Bài toán v n t i (D ng t ng quát là bài T1 T2 T3
tóan phân ph i). 35 t n 25 t n 45 t n
hàng hàng hàng
Bài tóan 1:
Có m t lo i hàng c n ñư c chuyên ch P1 5 2 3
30 t n
t hai kho (tr m phát) P1 và P2 t i ba nơi
hàng
tiêu th (tr m thu) T1, T2, T3 .
Lư ng hàng có hai kho và lư ng P2 2 1 1
hàng c n ba nơi tiêu th cũng như s ti n 75 t n
hàng
v n chuy n m t ñơn v hàng t m i kho
ñ n các nơi tiêu th ñư c cho b ng sau.
Bài toán ñ t ra là, hãy tìm m t T ng chi phí
f = 5 x11 + 2 x12 + 3 x13 + 2 x21 + x22 + x23
phương án v n chuy n th a yêu c u v thu
phát sao cho chi phí v n chuy n bé nh t. Ma tr n phương án x x1 3
x1 2
11
L p phương án.
x 21 x 22 x 23
G i xij là lư ng hàng v n chuy n t kho Pi
x11 + x12 + x13 = 3 0
ñ n nơi nh n Tj .
x 21 + x 22 + x 23 = 7 5
Ta có ma tr n chi phí v n chuy n là
x11 + x 21 = 3 5
5 x11 3 x13
2 x12
x12 + x 22 = 2 5
2 x21 x22 x23
x13 + x 23 = 4 5
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 3
- ðH Công nghi p Tp.HCM 23/12/2010
Tóm l i ta có bài toán Bài tóan 2:
M t nhà máy ch bi n th t, s n xu t ba lo i
f = 5 x11 + 2 x12 + 3x13 + 2 x21 + x22 + x23 → min
th t: bò, l n, c u, v i t ng lư ng m i ngày
x11 + x12 + x13 = 30 là 480 t n bò; 400 t n l n; 230 t n c u.
x + x + x = 75
M i lo i ñ u có th bán ñư c d ng tươi
21 22 23
x11 + x21 = 35 ho c n u chín. T ng lư ng các lo i th t n u
chín ñ bán trong gi làm vi c là 420 t n.
x12 + x22 = 25 Ngoài ra n u thêm ngoài gi 250 t n (v i
x13 + x23 = 45
giá cao hơn). L i nhu n thu ñư c trên m t
xij ≥ 0 ∀i, j t n ñư c cho b ng b ng sau: (v i ñơn v là
tri u ñ ng)
M c ñích c a nhà máy là tìm phương án
Tươi N u chín N u chín
s n xu t ñ làm c c ñ i l i nhu n. Hãy
ngoài gi
phát bi u mô hình bài toán.
8 11 14
Bò Gi i: Có th tóm t t l i bài toán như sau
Tươi N u chín N u chín ngoài
4 7 12
Ln 440 gi
420
(t n) (t n) 250 (t n)
8 11 14
Bò (480)
4 9 13
Cu
4 7 12
L n (400)
4 9 13
C u (230)
ðây là m t d ng c a bài toán v n t i, V i các ràng bu c sau ñây:
x11 + x12 + x13 = 480
nhưng ta tìm phương án ñ có “cư c phí”
v n chuy n l n nh t.
x21 + x22 + x23 = 400
Ký hi u xij , i = 1,3; j = 1,3 theo th t là x31 + x32 + x33 = 230
lư ng th t Bò, L n, C u dư i d ng Tươi,
x11 + x21 + x31 = 440
N u chín, N u chín ngoài gi mà nhà máy x + x + x = 420
12 22 32
s s n xu t trong ngày. Ta có bài toán :
x13 + x23 + x33 = 250
f = 8 x11 + 11 x12 + 14 x13 + 4 x21 + 7 x22 + 12 x23 xij ≥ 0, ∀i , j
4 x31 + 9 x32 + 13 x33 → max
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 4
- ðH Công nghi p Tp.HCM 23/12/2010
Bài tóan 3: Máy l ai I Máy l ai II Máy l ai III
(1 máy) (2 máy) (2 máy)
M t phân xư ng có 2 công nhân n và
3 công nhân nam. Phân xư ng cũng có 1
Nam 10 8 7
máy ti n l ai I, 2 máy ti n l ai II và 2 máy (3)
ti n l ai III. Năng su t (chi ti t / ngày) c a
các công nhân ñ i v i m i l ai máy ti n
N 8 9 11
ñư c cho trong b ng sau:
(2)
Chương I
1) Hãy l p mô hình bài tóan.
BÀI TOÁN QUY HO CH TUY N TÍNH
2) V i bài tóan v a l p ra, b n hãy cho m t
Bài 2. BÀI TOÁN QHTT VÀ Ý NGHĨA
phương án phân ph i các công nhân ñ ng
HÌNH H C .
các máy và tính s chi ti t làm ra ñư c
trong m t ngày. 1.D ng t ng quát c a bài toán Quy
ho ch tuy n tính.
3) Li t kê t t c các phương án c a bài tóan
Bài toán Quy ho ch tuy n tính t ng
và xác ñ nh phương án t i ưu.
quát có d ng sau ñây
Tìm giá tr l n nh t hay nh nh t c a hàm
Ví d 2.1: f ( x ) = 4 x1 + x2 − x3 + x4 → min
f ( x) = c1 x1 + c2 x2 + .. + cn xn
2 x1 + x2 ≤1
x
v i các ràng bu c: − x3 − 4 x4 ≤ −2
1
ai1x1 + ai2 x2 + .. + ain xn ≤ bi ; i ∈ I1 (1) x1 + x2 + x3 ≥0
x1 + 4 x2 − 5 x3 + 5 x4 = 17
ai1x1 + ai2 x2 + .. + ain xn ≥ bi ; i ∈ I2 (2)
x1 ; x3 ≥ 0
a x + a x + .. + a x = b ; i ∈ I (3)
i1 1 i2 2 x2 ∈ R
in n i 3
x j ≥ 0 ; j ∈ J1, x j ≤ 0 ; j ∈ J 2 , x j ∈ R ; j ∈ J3. x4 ≤ 0.
ñây là bài toán Quy ho ch tuy n tính
Trong ñó I1 , I 2 , I 3 r i nhau và I1 ∪ I2 ∪ I3 = {1,2,.., m} d ng t ng quát, và
, J1 , J 2 , J 3 r i nhau và J1 ∪ J 2 ∪ J 3 = {1, 2,.., n} .
I1 = {1,2} , I2 = {3} , I3 = {4} , J1 = {1,3} , J2 = {4} , J3 = {2}
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 5
- ðH Công nghi p Tp.HCM 23/12/2010
Ví d 2.2: f ( x) = 4 x1 + x2 − x3 + x4 → max 2. M t s khái ni m c a bài toán Quy
2 x1 + x2 + 6 x5 ≤ 1 ho ch tuy n tính:
x − x3 − 4 x4 − 4 x5 ≥ −2
Hàm m c tiêu: Là hàm
1
x1 + x2 + x3 + 16 x5 ≤ 2
n
x + 4 x − 5 x + 5 x + x = 17
∑
f (x) = = 〈c, x〉
cjx
1 2 3 4 5
j
9 x1 + x2 + 5 x3 + 2 x4 ≥ 11 j =1
x1 ; x5 ≥ 0, x2 ; x3 ∈ R, x4 ≤ 0.
Phương án: Véctơ x = ( x1 , x2 ,.., xn )
ñây là bài toán Quy ho ch tuy n tính
d ng t ng quát, và th a t t c các ràng bu c g i là m t
I1 = {1,3} , I2 = {2,5} , I3 = {4} , J1 = {1,5} , J2 = {4} , J3 = {2,3} phương án.
3. D ng chính t c c a bài toán Quy
T p phương án:
ho ch tuy n tính:
T p h p t t c các véctơ x th a các ràng
Bài toán Quy ho ch tuy n tính có
bu c g i là t p phương án.
d ng sau ñây, g i là d ng chính t c
Phương án t i ưu: n
f ( x) = ∑ c j x j = 〈c, x〉 → max (min)
Phương án x làm cho giá tr hàm m c j =1
tiêu ñ t giá tr nh nh t (n u là bài toán n
∑a x = bi i = 1, m
ij j
j =1
min), ho c hàm m c tiêu l n nh t (n u là
xj ≥ 0 j = 1, n.
bài toán max) ñư c g i là phương án t i ưu
f ( x ) = 〈 c, x〉 → max (min)
c a bài toán QHTT. Ax = b
x≥0
Trong ñó A = ( aij )ij==1,1,mn là m t ma tr n c p Nh n xét: M i bài tóan QHTT ñ u có
m×n ,
th ñưa v bài tóan QHTT d ng chính t c.
a11 ... a1n
a12
Ví d 2.3: ðưa các bài toán sau v d ng
a a22 ... a2 n
A = 21 chính t c: f ( x) = 4 x + x + 5x → max
1 2 3
... ... ...
... 4 x1 + x2 + 5 x3 ≤ 4
4 x1 + x2 + 5 x3 ≥ 3
am1 am 2 ... amn
x j ≥ 0, j = 1, 2,3.
x1 b1 a1 j
x2 b2 a2 j
x = , b= Aj =
f ( x ) = 4 x1 + 7 x2 + 5 x3 → min
...
.. ..
amj x1 + x2 + x3 = 4
xn bm
x1 + 2 x2 + 5 x3 = 3
Ax = x1 A1 + x2 A2 + .. + xn An x1 ≥ 0, x2 ≤ 0, x3 ∈ R
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 6
- ðH Công nghi p Tp.HCM 23/12/2010
4.Ý nghĩa hình h c và phương pháp ñ
th : A
Xét bài toán Quy ho ch tuy n tính B
f ( x) = 4 x1 + x2 → max
x1 + x2 ≤ 5
2 x1 + 3x2 ≤ 12 O
x1 ; x2 ≥ 0. C
Bi u di n t p phương án trên m t ph ng O(0,0); A(0,4); B(3,2); C(5,0). Hàm m c tiêu có d ng
x0y, ta ñư c t giác OABC. c a m t ñư ng th ng: f=4x1 + x2. Cho f=0 ta có ñư ng
th ng ñi qua g c t a ñ .
T nh ti n ñư ng th ng (d) theo m t hư ng Bài t p. B ng phương pháp hình h c,
nào ñó s làm cho giá tr hàm m c tiêu gi i các bài toán sau
f ( x) = −4x1 + 3x2 → min
tăng, ngư c l i s làm hàm m c tiêu gi m. 1)
x1 + x 2 ≤ 6
bài toán này ta c n làm cho hàm m c tiêu
2 x1 + 3 x2 ≥ 6
tăng. Rõ ràng ñi theo hư ng mũi tên s làm x − x ≤ 2
1
cho hàm m c tiêu tăng. 2
x j ≥ 0, j = 1, 2
f (O ) = f (0; 0) = 0; f ( A) = f (0; 4) = 4;
2) f ( x) = 3 x1 + 3 x2 → max
f ( B ) = f (3; 2) = 14; f (C ) = f (5; 0) = 20
x1 + x2 ≤ 6
Hàm m c tiêu ñ t giá tr max là 20 t i
3 x1 + x2 ≥ 3
ñi m C(5;0).
x1 , x2 ≥ 0
3) M t công ty s n xu t hai lo i sơn n i Giá bán m t t n sơn n i th t là 2000 USD,
th t và sơn ngoài tr i. Nguyên li u ñ s n giá bán m t t n sơn ngoài tr i là 3000
xu t g m hai lo i A, B v i tr lư ng là 6 USD. H i c n s n xu t m i lo i sơn bao
t n và 8 t n tương ng. ð s n xu t m t t n nhiêu t n ñ có doanh thu l n nh t ?
sơn n i th t c n 2 t n nguyên li u A và 1
t n nguyên li u B. ð s n xu t m t t n sơn
ngoài tr i c n 1 t n nguyên li u A và 2 t n
nguyên li u B. Qua ñi u tra th trư ng công
ty bi t r ng nhu c u sơn n i th t không hơn
sơn ngoài tr i quá 1 t n, nhu c u c c ñ i
c a sơn n i th t là 2 t n.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 7
- ðH Công nghi p Tp.HCM 23/12/2010
Chương I 1. ð nh nghĩa t p h p l i: T p L ⊆ Rn
ñư c g i là t p l i, n u:
BÀI TOÁN
∀x, y ∈ L ⇒ λ x + (1− λ) y ∈ L, ∀λ ; 0 ≤ λ ≤ 1
QUY HO CH TUY N TÍNH
Bài 3. Nói cách khác, t p L là t p l i, n u
ño n th ng n i hai ñi m trong L n m g n
TÍNH CH T C A T P PHƯƠNG ÁN
trong L.
VÀ T P PHƯƠNG ÁN T I ƯU
C A BÀI TOÁN
QUY HO CH TUY N TÍNH
Hình nh v hai t p l i trong R 2 , R 3
x0 = λ x1 + (1 − λ ) x 2 , x1 ; x 2 ∈ L ⇒ x0 = x1 = x 2
Ví d 3.1: Trong m t ph ng, ño n th ng,
0 < λ < 1.
ñư ng th ng, tia, toàn b m t ph ng, n a
Ví d 3.2:Trong R, cho ño n [1, 4]. Hai
m t ph ng, ña giác l i, tam giác, hình tròn,
ñi m 1; 4 là hai ñi m c c biên.
hình elip ñ u là các t p l i.
Gi i: Gi s
Trong không gian, ño n th ng,
1 = λ x + (1 − λ ) y , x, y ∈ [1; 4], 0 < λ < 1.
ñư ng th ng, m t ph ng, ña di n l i, hình
Ta s ch ng minh x=y=1.
c u… là các t p l i.
Th t v y, t : x, y ≥ 1 λ ,1 − λ > 0
2. ði m c c biên c a m t t p l i:
⇒ λ x + (1 − λ ) y ≥ λ1 + (1 − λ )1 = 1
ði m x0 ñư c g i là ñi m c c biên c a
D u b ng x y ra khi x=y=1.
t p l i L, n u:
Ch ng h n ch ng minh ñi m B(4,1) là
Ví d 3.3: Trong m t ph ng Oxy ta xét tam
ñi m c c biên
giác OAB, v i O(0;0), A(4;1), B(1,4). Khi
B = λ X + (1 − λ )Y , X , Y ∈ ∆OAB, 0 < λ < 1.
ñó các ñi m O, A, B là các ñi m c c biên.
(4,1) = λ ( x1 , y1 ) + (1 − λ )( x2 , y2 )
Gi i: Có th th y phương trình các c nh
OA, AB, BC l n lư t là: Trong ñó ( x1 , y1 ), ( x2 , y2 ) th a h phương trình
4 x − y = 0, x − 4 y = 0, x + y − 5 = 0 trên. T trên ta có:
Mi n trong c a tam giác OAB là t p các 4 = λ x1 + (1 − λ ) x2
ñi m (x,y) th a h b t phương trình:
1 = λ y1 + (1 − λ ) y2
4x − y ≥ 0
Có th ch ng minh ñư c
x − 4y ≤ 0 ( x1 , y1 ) = ( x2 , y2 ) = (4,1)
x + y ≤ 5
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 8
- ðH Công nghi p Tp.HCM 23/12/2010
Ví d 3.5: B ng phương pháp hình h c, tìm
Ví d 3.4: Hình ña giác l i; ña di n l i,
t p phương án và phương án t i ưu c a bài
thì các ñ nh là các ñi m c c biên.
toán f ( x) = 3x1 + 3x2 → max
3. Tính ch t c a bài toán Quy ho ch
x1 + x2 ≤ 6
tuy n tính:
3x1 + x2 ≥ 3
a) ð nh lý 1: T p h p các phương án c a x1 , x2 ≥ 0
bài toán Quy ho ch tuy n tính là m t t p
l i.
b) ð nh lý 2: T p h p các phương án t i
ưu c a bài toán Quy ho ch tuy n tính là
m t t p l i.
4. Tính ch t c a bài toán Quy ho ch a) ð nh nghĩa 1: Gi s
tuy n tính d ng chính t c: x 0 = ( x1 0 , x 20 , .., x n 0 )
Xét bài toán Quy ho ch tuy n tính
là m t phương án c a bài toán Quy ho ch
d ng chính t c:
f ( x) → min tuy n tính d ng chính t c. Khi ñó
Ax = b x10 A1 + x 20 A 2 + .. + x n 0 A n = b
ng v i nh ng x j 0 > 0 h véctơ { A j }
x ≥ 0,
Trong ñó A là ma tr n c p m × n và
ñư c g i là h véctơ liên k t v i x0.
x1 A1 + x2 A2 + .. + xn An = b
Ta có: x 0 = , , 0 là m t phương án c a
71
Ví d 3.5: Xét bài toán Quy ho ch tuy n
3 3
tính bài toán
f = 4 x − x − x → min
5
1 2 3
và ta có 7 . A1 + 1 . A2 + 0. A3 = b =
2 x1 + x2 − x3 = 5
2
3 3
x1 − x2 + 4 x3 = 2
V y h véctơ liên k t c a x0 là: A1 , A2
x j ≥ 0, j = 1,3.
trong ñó
x1 A1 + x2 A2 + x3 A3 = b
Ta có: 22 7
x1 = 0, , là m t phương án c a
3 3
−1 bài toán
2 1 5
A1 = , A2 = , A3 = , b = 5
22 2 7 3
0. A1 + .A + .A = b =
−1
1 4 2 2
3 3
V y h véctơ liên k t c a x1 là: A2 , A3
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 9
- ðH Công nghi p Tp.HCM 23/12/2010
b) ð nh lý 3: Gi s x 0 = ( x10 , x20 ,.., xn 0 ) c) H qu 1: S phương án c c biên c a
bài toán Quy ho ch tuy n tính d ng chính
là m t phương án khác không c a bài
t c là h u h n.
toán Quy ho ch tuy n tính d ng chính
d) ð nh nghĩa 2: M t phương án c c biên
t c.
c a bài toán Quy ho ch tuy n tính d ng
Khi ñó n u x0 là phương án c c
chính t c ñư c g i là không suy bi n n u
biên c a t p phương án thì h véctơ liên
s thành ph n dương c a nó b ng m.
k t v i nó ñ c l p tuy n tính.
Ngư c l i, n u x0 là m t phương án N u s thành ph n dương ít hơn m thì
có h véctơ liên k t v i nó ñ c l p tuy n phương án c c biên này g i là suy bi n.
tính thì x0 là m t phương án c c biên.
Ví d 3.6: Xét bài toán Quy ho ch tuy n x1 = (5, 0, 0)
là m t phương án c c biên c a
f = 4 x1 + x2 + x3 → min
tính bài toán, vì h véctơ liên k t v i nó là
x1 + 2 x2 − x3 = 5 1
A = h m t véctơ này ñ c l p tuy n tính.
1
1
x1 − x2 + 2 x3 = 5 Nhưng ñây không ph i là phương án
x j ≥ 0, j = 1,3. c c biên không suy bi n vì s thành ph n
dương c a nó là 1.
Ta có x 0 = (0,5,5) là m t phương án c c
x 2 = (1, 4, 4) là m t phương án c a bài toán.
biên c a bài toán, vì h véctơ liên k t
v i nó là A = 21 ; A = −1 hai véctơ này Nhưng không ph i là phương án c c
2 3
−
2
biên, vì h véctơ liên k t v i nó là
ñ c l p tuy n tính
−1 Các ñ nh lý trên ñây ñã ch ra cho chúng ta
1 2
A1 = ; A2 = ; A3 =
−1 cách thành l p m t phương án c c biên c a
1 2
bài toán Quy ho ch tuy n tính d ng chính
h véctơ này ph thu c tuy n tính.
t c là:
e) H qu 2: S thành ph n dương c a
- Xác ñ nh các h g m m véctơ ñ c l p
m t phương án c c biên c a bài toán Quy
tuy n tính, c a h các véctơ c t c a A. H
ho ch tuy n tính d ng chính t c t i ña là
này h u h n và t i ña là C = m!(nn−m)! h con.
!
m
b ng m (m là s dòng c a matr n A). n
- Bi u di n véctơ b theo các h con
f) ð nh lý 4: N u bài toán Quy ho ch tuy n
trên, ta ñư c các h s bi u di n. Thành
tính d ng chính t c có t p phương án khác
l p véctơ x có các thành ph n là h s
r ng thì nó có ít nh t m t phương án c c
bi u di n. Khi ñó x là m t phương án.
biên.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 10
- ðH Công nghi p Tp.HCM 23/12/2010
- Lo i ñi nh ng véctơ x có thành ph n Gi i: Có t t c 4 véctơ c t c a A là
âm, các véctơ còn l i là các phương án 1 0 1 1
A1 = , A2 = , A3 = , A4 =
−1
c c biên. 0 1 2
T ñó l y ñư c 6 h con ñ c l p tuy n
Ví d 3.7: Tìm t t c các phương án c c
tính là
biên c a t p phương án c a bài toán
{A ; A 2 }, {A ; A 3 }, {A },
1 1 1 4
;A
f = 2 x1 + x3 + 5 x4 → min
{A }, { A }, { A }
x1 + x3 + x4 = 5 2 3 2 4 3 4
;A ;A ;A
x2 − x3 + 2 x4 = 1 5
Bi u di n véctơ b = theo các h ñ c
x j ≥ 0, j = 1, 4 .
l p tuy n tính này, ta có
1
9 1
x1 = (5,1, 0, 0)
9114 x 3 = , 0, 0,
b = 5 A1 + A2 b = 6 A1 − A3 b= A+ A 2 2
2 2
x 4 = (0, 6, 5, 0) x 6 = (0, 0,3, 2)
b = 6 A2 + 5 A3 b = − 9 A2 + 5 A 4 b = 3 A3 + 2 A4
g) ð nh lý 5: N u bài toán Quy ho ch
tuy n tính d ng chính t c có phương án t i
T ñây ta có các véctơ th a h phương
ưu thì nó s có ít nh t m t phương án c c
trình trên là
9 1
x1 = (5,1, 0, 0) x 2 = (6, 0, −1, 0) x = , 0, 0, biên là phương án t i ưu.
3
2 2
h) ð nh lý 6: N u t p phương án c a bài
x = (0, 6,5, 0) x = (0, −9, 0,5) x = (0, 0, 3, 2)
6
5
4
toán Quy ho ch tuy n tính không r ng và
là m t ña di n l i thì bài toán s có ít nh t
Lo i b các véctơ có thành ph n âm ta
m t phương án t i ưu là phương án c c
ñư c 4 phương án c c biên là
biên.
i) ð nh lý 7: ði u ki n c n và ñ ñ bài - Ki m ch ng t p phương án không r ng
toán Quy ho ch tuy n tính có phương án và hàm m c tiêu b ch n.
t i ưu là t p phương án không r ng và hàm
- Tìm các phương án c c biên.
m c tiêu b ch n dư i (n u là bài toán min)
- L n lư t th các phương án c c biên ta
ho c b ch n trên ( n u là bài toán max).
suy ra phương án t i ưu và giá tr t i ưu
j) Ghi chú: T các ñ nh lý 7, ñ nh lý 5, c a hàm m c tiêu.
ñ nh lý 3 ta có th gi i ñư c bài toán QHTT Ví d 3.8: Gi i bài toán QHTT
f = 2 x1 + x3 + 5 x4 → min
d ng chính t c như sau:
x1 + x3 + x4 = 5
x2 − x3 + 2 x4 = 1
x j ≥ 0, j = 1, 4 .
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 11
- ðH Công nghi p Tp.HCM 23/12/2010
9 1
x 3 = , 0, 0, x 4 = (0, 6,5, 0) x 6 = (0, 0,3, 2)
x1 = (5,1, 0, 0)
Gi i: Ví d này ta ñã xét trên. 2 2
- T p phương án không r ng là hi n nhiên. f (x1) = f (5,1,0,0) = 2.5 +1.0 + 5.0 =10
- Hàm m c tiêu b ch n dư i b i 0, vì 9 1 9 1 23
f ( x 3 ) = f , 0, 0, = 2. + 1.0 + 5. =
f = 2 x1 + x3 + 5 x4 > 0 2
2 2 22
f ( x 4 ) = 2.0 + 5 + 5.0 = 5
Theo ñ nh lý 7 bài toán có phương án
t i ưu. Theo ñ nh lý 5 bài toán có phương
f ( x 6 ) = 3 + 5.2 = 13
án c c biên là phương án t i ưu.
V y x4 là phương án t i ưu c a bài toán,
Theo ví d trên có t t c các phương án
và giá tr t i ưu là 5.
c c biên là:
Bài t p. 2) Tương t bài 1) v i các bài toán:
a) f (x) = 3x1 + 4x 2 + 5x 3 → min
f ( x ) = 4 x1 + x 2 → m a x
1) Cho bài toán (P)
6x1 + 3x 2 + 2x 3 ≥ 18
x1 + x 2 ≤ 5
2x1 + 6x 2 + 3x 3 ≥ 23
2 x1 + 3 x 2 ≤ 1 2
x j ≥ 0; j = 1, 3.
x1 ; x 2 ≥ 0 .
a) ðưa bài toán (P) v d ng chính t c; ta
f ( x) = 5 x1 − x2 → max
b)
g i bài toán này là (Q).
3x1 + x2 ≥ 3
b) Li t kê t t c các phương án c c biên x1 + x2 ≥ 2
3x + 4 x ≥ 7
c a (Q). 1 2
x j ≥ 0; j = 1, 2.
c) Tìm phương án t i ưu c a (Q).
Chương I Ho c vi t dư i d ng:
f ( x) = 〈 c, x〉 → min (max)
BÀI TOÁN QUY HO CH TUY N TÍNH
Bài 4. PHƯƠNG PHÁP ðƠN HÌNH Ax = b
x≥0
1. Gi i thi u chung: Ta xét bài toán
Trong ñó:
QHTT d ng chính t c:
A = ( aij )i =1, m
n
f ( x) = ∑ c j x j = 〈 c, x〉 → min (max)
j =1, n
j =1
x = ( x1 , x2 ,.., xn )T , b = (b1 , b2 ,.., bm )T
n
∑a x = bi i = 1, m
ij j
j =1
c = (c1 , c2 ,.., cn )
xj ≥ 0 j = 1, n.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 12
- ðH Công nghi p Tp.HCM 23/12/2010
Ký hi u : x j = ( x1 j ; x2 j ;..; xmj )
Gi s bài toán ñang xét ta ñã bi t
m t phương án c c biên d ng : N u mà ta ñã bi t ñư c x là phương án t i
x = ( x10 ; x20 ;..; xm 0 ;0;0;..;0) ưu nh m t cách nào ñó thì m c ñích c a ta ñã
xong.
trong ñó xj0 >0, j =1,m cơ s liên k t c a
N u x không ph i là phương án t i ưu thì ta
x là A1 , A2 ,..., Am tìm phương án c c biên khác t t hơn t c là
x10 A1 + x20 A2 + .. + xm0 Am = b phương án làm cho giá tr hàm m c tiêu nh
Giá tr hàm m c tiêu là: hơn.
f ( x ) = c1 x10 + c2 x20 + .. + cm xm 0
Mu n v y ta ph i xây d ng m t cơ s m i,
V i m i j = 1, 2, .., n
ñơn gi n nh t là thay th m t véctơ trong cơ s
x1 j A + x2 j A + .. + xmj A = A
1 2 m j
cũ b ng m t véctơ n m ngoài cơ s cũ.
T hai véctơ: x = ( x10 ; x 20 ;..; x m 0 ; 0; 0;..; 0) 2. ð nh lý 1.( D u hi u t i ưu)
N u x = ( x10 ; x20 ;..; xm 0 ; 0;0;..;0) là m t
x = ( x1 j ; x 2 j ;..; x mj )
j
ð t: phương án c c biên c a bài toán Quy
m
∑cx
zj = = 〈 c , x j 〉 , j = 1, n ho ch tuy n tính d ng chính t c sao cho :
i ij
i =1
∆ = zj − cj
∆ j ≤ 0, ∀j = 1, n
j
Tóm l i, chúng ta v a xây d ng ñư c:
thì x là phương án t i ưu, và ngư c l i.
∆ j = 〈c, x j 〉 − c j
g i là ư c lư ng th j c a phương án x.
Giá tr này ñóng vai trò vô cùng quan tr ng
trong vi c ñánh giá tính t i ưu c a m t p.án.
Ví d 4.1: Xét bài toán QHTT
3. ð nh lý 2: N u t n t i véctơ A j ngoài
f ( x) = x1 + 6 x2 + 9 x3 → min
cơ s liên k t c a phương án c c biên x1 + 2 x3 = 6
x = ( x10 ; x20 ;..; xm0 ;0;0;..;0)
+ x2 + x3 = 8
sao cho ∆ j > 0 và x j ≤ 0 thì bài toán Quy x j ≥ 0, j = 1, 2,3.
ho ch tuy n tính d ng chính t c không có v i phương án c c biên x=(6,8,0).
phương án t i ưu. Rõ hơn là hàm m c tiêu Xét xem x có ph i là phương án t i ưu hay
không b ch n dư i trên t p phương án. không ?
Gi i: Véctơ x có cơ s liên k t là:
1 0
A1 = , A2 =
0 1
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 13
- ðH Công nghi p Tp.HCM 23/12/2010
Ta xác ñ nh các véctơ xj : ∆1 = z1 − c1 = 〈 c, x1 〉 − c1 = 〈(1, 6), (1,0)〉 − 1
= 1.1 + 6.0 − 1 = 0
A j = x1 j A1 + x2 j A2 + .. + xmj Am
∆ 2 = z2 − c2 = 〈c, x 〉 − c2 = 〈(1, 6), (0,1)〉 − 6
2
x j = ( x1 j ; x2 j ;..; xmj )
= 1.0 + 6.1 − 6 = 0
A1 = x11 A1 + x21 A2 = 1. A1 + 0. A2 ⇒ x1 = (1, 0)
∆ 3 = z3 − c3 = 〈 c, x 3 〉 − c3 = 〈 (1, 6), (2,1)〉 − 9
A2 = x12 A1 + x22 A2 = 0. A1 + 1. A2 ⇒ x 2 = (0,1)
= 1.2 + 6.1 − 9 = −1
A3 = x13 A1 + x23 A2 = 2. A1 + 1. A2 ⇒ x 3 = (2,1)
Ta th y t t c các ∆ j ≤ 0 v i m i j. V y x
m
∆ j = z j − c j = ∑ ci xij − c j = 〈c, x j 〉 − c j
là phương án t i ưu và giá tr t i ưu là:
i =1
L n lư t thay j=1,2,3 ta có : f(x)=1.6+6.8+9.0=54.
ð d th y ta s p x p các phép toán lên Ví d 4.2: Xét bài toán QHTT
f ( x ) = 7 x1 − 26 x2 + 9 x3 → min
b ng sau:
x1 − 2 x2 =5
Cơ s Hs P. án 1 6 9
− x2 + x3 = 7
x1 x2 x3
x j ≥ 0, j = 1, 2,3.
A1 1 6 1 0 2
v i phương án c c biên x=(5,0,7).
A2 6 8 0 1 1
∆1 = 0 ∆ 2 = 0 ∆ 3 = −1 Xét xem x có ph i là phương án t i ưu hay
f(x) 54
không ?
B ng g m 3 dòng, 6 c t. C t m t ghi cơ Gi i: Véctơ x có cơ s liên k t là:
liên k t c a p. án x, c t hai ghi h s liên
1 0
A1 = , A3 =
k t c a x, c t 3 ghi p. án x, c t 4; 5; 6
0 1
dòng hai ghi toàn b ma tr n A…..
Ta xác ñ nh các véctơ xj :
∆1 = z1 − c1 = 〈 c, x1 〉 − c1 = 〈 (7,9), (1, 0)〉 − 7 = 0
A = x11 A + x31 A = 1. A + 0. A ⇒ x = (1, 0)
1 1 3 1 3 1
∆ 2 = z2 − c2 = 〈c, x 2 〉 − c2 =
A = x12 A + x32 A = −2 A − 1. A ⇒ x = (−2, −1)
2 1 3 1 3 2
= 〈(7,9), ( −2, −1)〉 − (−26) = 3
A = x13 A + x23 A = 0. A + 1. A ⇒ x = (0,1)
3 1 2 1 2 3
∆ 3 = z3 − c3 = 〈 c, x 3 〉 − c3 = 〈 (7, 9), (0,1)〉 − 9 = 0
∆ j = 〈 c, x j 〉 − c j
Ta th y ∆ 2 > 0 và x 2 = (−2, −1) ≤ 0 .V y bài
toán không có phương án t i ưu. Rõ hơn
L n lư t thay j=1,2,3 ta có :
là hàm m c tiêu không b ch n dư i trên
t p phương án.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 14
- ðH Công nghi p Tp.HCM 23/12/2010
Lưu ý: Vi c tính toán mà s p x p trên b ng
Cơ s Hs P. án 7 -26 9
ñơn hình ch th c hi n ñư c khi phương án
x1 x2 x3
c c biên có h véc tơ liên k t là ñơn v .
A1 7 5 1 -2 0
A3 9 7 0 -1 1 Trư ng h p h véc tơ liên k t không ph i là
∆3 = 0
∆1 = 0 ∆2 = 3 h ñơn v thì ph i tính tr c ti p t công
th c ñã bi t.
B ng g m 3 dòng, 6 c t. C t m t ghi cơ
Ch ng h n ví d sau.
liên k t c a p. án x, c t hai ghi h s liên
k t c a x, c t 3 ghi p. án x, c t 4; 5; 6
dòng hai ghi toàn b ma tr n A…..
D th y ñây là h ñ c l p tuy n tính nên là
Ví d 4.3: Cho bài toán
phương án c c biên.
f ( x ) = −4 x1 + 3 x2 + 7 x3 + 8 x4 → min
3 x1 + 3 x2 + 4 x3 + 5 x4 = 21 3 3 4
−1 1 = − 131 ≠ 0
7
7 x1 − x2 + x3 + 6 x4 = 8 −1
2 5
2 x − x + 5 x + 2 x = 15
x1 = (1, 0, 0), x 2 = (0,1, 0), x 3 = (0, 0,1)
1 2 3 4
x j ≥ 0, j = 1, 4. 120 73 19
x 4 = B −1 A 4 = , ,
Ch ng minh x = (1, 2,3, 0 ) là phương án c c 131 131 131
∆1 = ∆ 2 = ∆ 3 = 0
biên, t i ưu c a bài tóan ñã cho.
− 1 176
∆ 4 = c, x 4 − c4 = 0
sao cho ∆ j > 0 , và v i m i j mà ∆ j > 0 ta
l n nh t. Gi s ñó là Ak.
luôn tìm ñư c ít nh t m t xij > 0 , thì khi
Véctơ b thay ra là As, v i cách xác ñ nh
ñó ta có th tìm ñư c m t phương án c c
As như sau: θ = min xi 0 : xik > 0 = xs 0
biên m i t t hơn x, nghĩa là phương án
xik xsk
này làm cho hàm m c tiêu nh hơn
Trong ñó xik là h s bi u di n c a
phương án x.
Ak theo cơ s liên k t c a p. án x.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 15
- ðH Công nghi p Tp.HCM 23/12/2010
Và khi ñó phương án m i x’ ñư c Ví d 4.4: Xét bài toán QHTT
xác ñ nh theo công th c: f ( x ) = x1 − 2 x2 + 2 x3 + 0 x4 → min
x1 + x2 + 4 x4 = 6
x′ = ( x10 − θ x1 j ; x20 − θ x2 j ;..; xm 0 − θ xmj ;..;θ ; 0;..; 0)
+ 2 x2 + x3 + 5 x4 = 8
Ho c có th bi u di n véctơ b theo cơ x j ≥ 0, j = 1, 2,3, 4.
s m i này ta có p. án m i x’ . V i p. án x=(6,0,8,0) cơ s liên k t là:
Phương án x’ t t hơn x. 1 0
A1 = , A3 =
0 1
ð n ñây ta xem x’ như x và ki m tra x’
có th a ñ nh lý 1, hay ñ nh lý 2 không.
Trư c tiên ta xem x có ph i p. án t i
N u không ta l i xây d ng m t phương ưu hay không.
án m i t t hơn …
ð thu n ti n ta s p x p các ph n t lên Véctơ ñưa vào thay th ñó là A4 .
b ng và tính toán các ∆ j ta có: 6 8 3 x
xi 0 x x
: xi 4 > 0 = min 10 , 30 = min , = = 10
θ = min
4 5 2 x14
xi 4 x14 x34
Cơ Hs P. án 1 -2 2 0
s 1 b thay ra.
Vy A
x1 x2 x3 x4
A1 1 6 1 1 0 4
P. Án m i x’ ñư c xác ñ nh như sau:
A3 2 8 0 2 1 5
6
b=
Cơ s m i là A3, A4 . Bi u th véctơ
f(x) 22 0 7 0 14
8
theo cơ s này ta ñư c
Ta th y p. án này chưa t i ưu, và trong
s các ∆ j > 0 ,các xj ñ u có h s dương. 6 1 0 3 4
b = = +
Do ñó có th tìm p. án m i t t hơn.
8 2 1 2 5
Ta xác ñ nh các véctơ xj :
T ñó ta có p. án m i là:
−5 3 1 4 −5 1
1 3 A1 = x31 A3 + x41 A4 = . A + . A ⇒ x1 = ,
x′ = 0, 0, ,
4 4
4 4
2 2
3 1
3314
A2 = x32 A3 + x42 A4 = A + A ⇒ x 2 = ,
Giá tr hàm m c tiêu lúc này là:
4 4
4 4
1 3 1
f ( x′) = f 0, 0, , = 0 − 2.0 + 2. = 1 A3 = x33 A3 + x43 A4 = 1. A3 + 0. A4 ⇒ x3 = (1, 0)
2 2 2
A4 = x34 A3 + x44 A4 = 0. A3 + 1. A4 ⇒ x 3 = (0,1)
Rõ ràng p. án này t t hơn x.
∆ j = 〈 c, x j 〉 − c j
Bây gi xem x’ như x. Ta ki m tra xem x’
L n lư t thay j=1, 2, 3, 4 ta có :
có ph i là p. án t i ưu không.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 16
- ðH Công nghi p Tp.HCM 23/12/2010
ð ti n theo dõi ta s p x p lên b ng:
−5 1 −7
∆1 = z1 − c1 = 〈c, x1 〉 − c1 = 〈 (2, 0), , 〉 − 1 =
4 4 2 Cơ Hs P. án 1 -2 2 0
s x1 x2 x3 x4
3 1 7
∆ 2 = z2 − c2 = 〈 c, x 2 〉 − c2 = 〈 (2, 0), , 〉 − (−2) =
4 4 2 A4 0 3/2 1/4 1/4 0 1
A3 2 1/2 -5/4 3/4 1 0
∆ 3 = z3 − c3 = 〈c, x3 〉 − c3 = 〈(2, 0), (1, 0)〉 − 2 = 0 f(x) 1 -7/2 7/2 0 0
∆ 4 = 〈 c, x 4 〉 − c4 = 〈 (2, 0), (0,1)〉 − 0 = 0 Ta liên h hai b ng này v i nhau:
P. Án này v n chưa t i ưu.
5. Phương pháp ñơn hình cho bài toán
B ng 1
chính t c có s n ma tr n ñơn v :
Cơ Hs P. án 1 -2 2 0
s x1 x2 x3 x4
Xét bài toán chính t c:
A1 1 6 1 1 0 4
f ( x ) = 〈c, x〉 → min
A3 2 8 0 2 1 5
Ax = b
f(x) 22 0 7 0 14
x≥0
B ng 2
A4 0 3/2 1/4 1/4 0 1 Trong ñó A có s n m t ma tr n ñơn v c p
A3 2 1/2 -5/4 3/4 1 0
m. Không m t tính t ng quát có th gi s
f(x) 1 -7/2 7/2 0 0
ñó là m c t ñ u A1 , A2 ,.., Am , và phương
án c c biên x trong bư c l p ñ u tiên là:
x = (b1 , b2 ,.., bm , 0, 0,.., 0) ≥ 0 Cơ H. Ph c1 c2 … cm cm+1 … ck cn
s s án
Khi ñó các xj d dàng bi u di n qua các x1 x2 xm xm+1 xk xn
cj
véctơ cơ s trên. A1 c1 b1 1 0 0 x x1k x1n
1m+1
A2 c2 b2 0 1 0 x x2k x2n
ð thu n ti n cho vi c tính toán ta s p 2m+1
.. .. .. .. .. .. .. ..
x p các d li u lên b ng sau mà ta g i là …
As cs bs 0 0 0 xsk xsn
x
b ng ñơn hình.
sm+1
.. .. .. .. .. .. .. ..
xmn
Am xmk
cm x
bm 0 0 1 mm+1
∆n
∆k
∆ m +1
f(x) f0 0 0 0
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 17
- ðH Công nghi p Tp.HCM 23/12/2010
Trong ñó f 0 = c1 x1 + c2 x2 + .. + cm xm N u không th a bư c 1 ta sang bư c 2.
m
∆ j = ∑ ci xij − c j , j = 1, n Bư c 2:
i =1
i) Xác ñ nh ∆ k = max {∆ j / ∆ j > 0} ,véctơ Ak
∆ j = 0 , j = 1, m
ñưa vào thay th .
Thu t toán ñơn hình ñư c th c hi n m t s
ii) Xác ñ nh véctơ As ñưa ra kh i cơ s
như sau: min xi 0 : xik > 0 = xs 0
bư c như sau:
Bư c 1: N u ∆ j ≤ 0 , ∀j = 1, n thì phương án
xik xsk
ñang xét là t i ưu. Bư c 3:
Bi n ñ i b ng ñơn hình m i: Dùng
N u ∆ j > 0 mà ng v i j này xij ≤ 0, ∀i = 1, m
phép bi n ñ i như sơ c p trên ma tr n, bi n
thì bài toán không có phương án t i ưu. ñ i c t k tr thành véctơ ñơn v th s.
Bư c 4: Tính toán các ph n t trên dòng -5 -4 0 0 2
cu i cùng và quay l i bư c 1.
Cơ H Ph. x1 x2 x3 x4 x5
Ví d 4.5: Gi i bài toán s s cj án
A1 -5 10 1 0 0 2 1
f ( x ) = −5 x1 − 4 x2 + 0 x3 + 0 x4 + 2 x5 → min
A2 -4 12 0 1 0 1 3
+ 2 x4 + x5 = 10
x1 A3 0 15 0 0 1 3 1
+ x4 + 3x5 = 12
x2
f(x) -98 0 0 0 -14 -19
+ x3 + 3x4 + x5 = 15
x j ≥ 0, j = 1,5. Bài toán ñã có d u hi u t i ưu, phương
án t i ưu là x = (10,12,15, 0, 0) , giá tr t i ưu
Gi i: ðây là bài toán QHTT d ng chính
-98.
t c mà ma tr n A có s n ma tr n ñơn v .
Ví d 4.6: Gi i bài toán -2 -4 1 -1 0 0
f ( x) = −2 x1 − 4 x2 + x3 − x4 + 0 x5 + 0 x6 → min cs Hs Pa x1 x2 x3 x4 x5 x6
A5 0 4 1 3 0 0 1 0
x1 + 3x2 + x5 = 4
A6 0 3 2 1 -1 0 0 1
2 x1 + x2 − x3 + x6 = 3
A4 -1 3 0 1 4 1 0 0
x2 + 4 x3 + x4 =3 f(x) -3 2 3 -5 0 0 0
A2 -4 4/3 1/3 1 0 0 1/3 0
x j ≥ 0, j = 1, 6. A6 0 5/3 5/3 0 -1 0 -1/3 1
A4 -1 5/3 -1/3 0 4 1 -1/3 0
Gi i:ðây là bài toán QHTT d ng chính f(x) -7 1 0 -5 0 -1 0
t c mà ma tr n A có s n ma tr n ñơn v . A2 -4 1 0 1 1/5 0 2/5 -1/5
A1 -2 1 1 0 -3/5 0 -1/5 3/5
Ma tr n ñơn v này không theo th t mà A4 -1 2 0 0 19/5 1 -2/5 1/5
ñó là A5, A6, A4 . f(x) -8 0 0 -22/5 0 -4/5 -3/5
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 18
- ðH Công nghi p Tp.HCM 23/12/2010
f ( x ) = −2 x1 + 3 x2 − x3 + 0 x4 + 0 x5 + 0 x6 → min
Ví d 4.7: Gi i bài toán
f ( x) = −2 x1 + 3 x2 − x3 → min x1 − 5 x2 + x3 + x4 = 15
x1 − 5 x2 + x3 ≤ 15 3 x1 + 2 x2 − 2 x3 + x5 = 20
4 x
3 x1 + 2 x2 − 2 x3 ≤ 20 + x3 + x6 = 10
1
4 x + x3 ≤ 10 x j ≥ 0, j = 1, 6.
1
x j ≥ 0, j = 1,3. Lúc này ma tr n A ñã có s n m t ma tr n
ñơn v , cho nên s p x p các các ph n t
Gi i: ðây không ph i là bài toán chính t c,
lên b ng ñơn hình và tính toán ta có b ng
ta s ñưa v bài toán chính t c b ng cách
thêm vào các n ph x4 , x5 , x6 ≥ 0 , bài sau:
toán tr thành
ð i v i bài toán max ta có các k t q a sau:
-2 3 -1 0 0 0
cs Hs Pa x1 x2 x3 x4 x5 x6
ð nh lý 1’.( D u hi u t i ưu)
A4 0 15 1 -5 1 1 0 0
N u x = ( x ; x ;..; x ; 0; 0;..; 0) là m t phương án
A5 0 20 3 2 -2 0 1 0 10 20 m0
A6 0 10 4 0 1 0 0 1
c c biên c a bài toán Quy ho ch tuy n tính
f(x) 0 2 -3 1 0 0 0
d ng chính t c
A4 0 25/2 0 -5 3/4 1 0 -1/4
f ( x) → max
A5 0 25/2 0 2 -11/4 0 1 -3/4
Ax = b
A1 -2 5/2 1 0 1/4 0 0 1/4
x≥0
f(x) -5 0 -3 1/2 0 0 -1/2
A4 0 5 -3 -5 0 1 0 -1
thì x là phương án t i
sao cho ∆ j ≥ 0, ∀j = 1, n
A5 0 40 11 2 0 0 1 2
A3 -1 10 4 0 1 0 0 1
ưu.
f(x) -10 -2 -3 0 0 0 -1
ð nh lý 2’: N u t n t i véctơ Aj ngoài cơ s ð nh lý 3’ :N u t n t i véctơ Aj ngoài cơ
liên k t c a phương án c c biên s liên k t c a phương án c c biên
x=(x10,x20,…,xm0,0,0,..0) sao cho ∆j < 0 và x = ( x10 ; x20 ;..; xm 0 ;0;0;..; 0) sao cho ∆ < 0 , và
j
x j ≤ 0 thì bài toán Quy ho ch tuy n tính v i m i j mà ∆ j < 0 ta luôn tìm ñư c ít
nh t m t xij > 0 , thì khi ñó ta có th tìm
d ng chính t c không có phương án t i ưu.
Rõ hơn là hàm m c tiêu không b ch n trên, ñư c m t phương án c c biên m i t t
trên t p phương án. hơn x, nghĩa là phương án này làm cho
hàm m c tiêu l n hơn phương án x.
Khi ch n véctơ cơ s ñưa vào ta
ch n ∆ = min {∆ / ∆ < 0} , ch n véctơ ñưa ra
k j j
như trư ng h p min.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 19
- ðH Công nghi p Tp.HCM 23/12/2010
f ( x ) = 2 x1 + 3x2 + x3 → max
Ví d 4.8: Gi i bài toán
x1 − 5 x2 + x3 =6
f ( x) = 2 x1 + 3 x2 + x3 → max
2 x1 + 2 x2 + x4 = 7
x1 − 5 x2 + x3 = 6
− x + 2 x
+ x5 = 5
2 x1 + 2 x2 ≤7 1 2
− x + 2 x x j ≥ 0, j = 1,5.
≤5
1 2
x j ≥ 0, j = 1,3. Lúc này ma tr n A ñã có s n m t ma tr n
Gi i: ðây không ph i là bài toán chính t c, ñơn v , cho nên s p x p các các ph n t lên
ta s ñưa v bài toán chính t c b ng cách b ng ñơn hình và tính toán ta có b ng sau:
thêm vào các n ph x4 , x5 ≥ 0 vào các b t
phương trình th hai và th ba, bài toán tr
thành
Ví d 4.9: Cho bài tóan Quy h ach tuy n
2 3 1 0 0
cs Hs Pa x1 x2 x3 x4 x5
tính mà ta g i là bài tóan (P)
f ( x ) = 5 x1 + 2 x2 − 7 x3 − 8 x4 → max
A3 1 6 1 -5 1 0 0
2 x1 + 3 x2 + 4 x3 + 5 x4 = 20
A4 0 7 2 2 0 1 0
8 x1 − x2 + x3 + 6 x4 = 9
A5 0 5 -1 2 0 0 1
2 x − x + 5 x + 2 x = 15
f(x) 6 -1 -8 0 0 0 1 2 3 4
x j ≥ 0, j = 1, 4.
A3 1 37/2 -3/2 0 1 0 5/2
61 163 73
A4 0 2 3 0 0 1 -1
Ch ng minh x = 0, 60 , 60 , 60 là phương án
A2 3 5/2 -1/2 1 0 0 1/2
c c biên, nhưng không ph i là phương án
f(x) 26 -5 0 0 0 4
t i ưu c a bài tóan (P). Hãy xây d ng m t
A3 1 39/2 0 0 1 1/2 2
A1 2 2/3 1 0 0 1/3 -1/3
phương án c c biên m i t t hơn phương án
A2 3 17/6 0 1 0 1/6 1/3
x nói trên, và ki m tra tính t i ưu c a
f(x) 88/3 0 0 0 5/3 7/3
phương án này.
6. Thu t toán ñơn hình cho bài toán Gi s ma tr n A còn thi u m véctơ ñơn v .
chính t c không có s n ma tr n ñơn v : Ta thêm vào m n gi xm+1, xm+2,..,xm+n .
Gi s bài toán chính t c Khi ñó bài toán có d ng như sau:
f ( x) → min
f ( x ) + Mxn +1 + Mxn + 2 + .. + Mxn + m → min
Ax = b (*)
Bx = b (M )
x≥0
trong ñó A không có ma tr n ñơn v . Ch ng x≥0
Trong ñó B là ma tr n c p mx(m+n) v i n
h n bài toán sau ñây
f ( x) = −3 x1 + x2 + 3 x3 − x4 → min c t ñ u là ma tr n A, m c t sau là m véctơ
x1 + 2 x2 − x3 + x4 = 2
ñơn v . x là véctơ có n+m thành ph n . M là
2 x1 − 6 x2 + 3 x3 + 3 x4 = 9
m t s dương r t l n; l n hơn b t kỳ s nào
x − x + x − x = 6
1 2 3 4
c n so sánh. Ta có các k t q a sau.
x j ≥ 0, j = 1, 4.
Quy ho ch tuy n tính ð i h c
& Cao ñ ng 20
nguon tai.lieu . vn
