intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Chương 1: Bài toán quy hoạch tuyến tính

Chia sẻ: Nguyen Doan Minh Tri | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST
Báo xấu
202
lượt xem 39
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một xí nghiệp dự định sản xuất hai loại sản phẩm A và B. Các sản phẩm này được chế tạo từ ba nguyên liệu I, II và III mà xí có là 8,24,12 số lượng các nguyên liệu cần để sản xuất một đơn vị snar phẩm A,B được cho ở bảng sau đây:

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Chương 1: Bài toán quy hoạch tuyến tính

  1. ð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 (
  2. ð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
  3. ð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
  4. ð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
  5. ð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
  6. ð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
  7. ð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
  8. ð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
  9. ð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
  10. ð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
  11. ð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
  12. ð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
  13. ð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
  14. ð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
  15. ð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
  16. ð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
  17. ð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
  18. ð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
  19. ð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
  20. ð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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2