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

Quy hoạch tuyến tính - ĐH Sư Phạm Đồng Tháp

Chia sẻ: Nguyen Lan | Ngày: | Loại File: PDF | Số trang:82

165
lượt xem
34
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong toán học, quy hoạch tuyến tính (QHTT) (tiếng Anh: linear programming - LP) là bài toán tối ưu hóa, trong đó hàm mục tiêu (objective function) và các điều kiện ràng buộc đều là tuyến tính.

Chủ đề:
Lưu

Nội dung Text: Quy hoạch tuyến tính - ĐH Sư Phạm Đồng Tháp

  1. Quy hoạch tuyến tính
  2. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp M cl c Chương 1. Bài toán quy ho ch tuy n tính 3 1.1. M t vài bài toán th c t . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Bài toán l p k ho ch s n xu t . . . . . . . . . . . . . . . . 3 1.1.2 Bài toán v n t i . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Bài toán quy ho ch tuy n tính . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 D ng t ng quát . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 D ng chính t c và d ng chu n t c . . . . . . . . . . . . . . . 6 1.3. ý nghĩa hình h c và phương pháp đ th . . . . . . . . . . . . . . . 8 1.4. Bài t p chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chương 2. Tính ch t c a t p phương án và t p phương án t i ưu c a bài toán quy ho ch tuy n tính 14 2.1. T p h p l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. Tính ch t c a t p phương án và t p phương án t i ưu c a bài toán quy ho ch tuy n tính . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3. Tính ch t c a quy ho ch tuy n tính d ng chính t c . . . . . . . . . 16 2.4. Bài t p chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Chương 3. Phương pháp đơn hình và các thu t toán c a nó 21 3.1. Cơ s lí lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2. Thu t toán đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.1 Thu t toán đơn hình . . . . . . . . . . . . . . . . . . . . . . 24 3.2.2 B ng đơn hình . . . . . . . . . . . . . . . . . . . . . . . . . 24 1
  3. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 3.2.4 Trư ng h p bài toán suy bi n . . . . . . . . . . . . . . . . . 27 3.2.5 Tìm phương án c c biên và cơ s ban đ u . . . . . . . . . . 27 3.3. Bài t p chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Chương 4. Bài toán quy ho ch tuy n tính đ i ng u và thu t toán đơn hình đ i ng u 42 4.1. Bài toán quy ho ch tuy n tính đ i ng u . . . . . . . . . . . . . . . 42 4.2. Thu t toán đơn hình đ i ng u . . . . . . . . . . . . . . . . . . . . . 47 4.2.1 Cơ s lí lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.5 Thu t toán đơn hình đ i ng u . . . . . . . . . . . . . . . . . 49 4.3. V n đ tìm phương án c c biên xu t phát c a bài toán đ i ng u . . 54 4.4. V n đ h u t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.5. Bài t p chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Chương 5. Bài toán v n t i và thu t toán th v 68 5.1. Bài toán v n t i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2. Các Tính ch t c a bài toán v n t i . . . . . . . . . . . . . . . . . . 69 5.2.1 Chu trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3. V n đ tính các ư c lư ng . . . . . . . . . . . . . . . . . . . . . . . 70 5.4. M t s phương pháp xây d ng phương án c c biên ban đ u . . . . 73 5.5. Thu t toán th v . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6. Tiêu chu n t i ưu. Bài toán đ i ng u c a bài toán v n t i . . . . . 77 5.6.1 Tiêu chu n t i ưu . . . . . . . . . . . . . . . . . . . . . . . . 77 5.6.2 Bài toán đ i ng u c a bài toán v n t i . . . . . . . . . . . . 78 2
  4. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Chương 1. BÀI TOÁN QUY HO CH TUY N TÍNH 1.1. M t vài bài toán th c t 1.1.1 Bài toán l p k ho ch s n xu t Bài toán: M t cơ s s n xu t d đ nh s n xu t hai lo i s n ph m A và B. Các s n ph m đư c ch t o t ba lo i nguyên li u I, II và III. S lư ng d tr c a t ng lo i và s lư ng t ng lo i nguyên li u c n dùng đ s n xu t ra m t s n ph m đư c cho b ng b ng sau: Lo i Nguyên li u Nguyên li u c n dùng đ s n xu t m t đơn v s n ph m Nguyên li u d tr A B I 18 2 3 II 30 5 4 III 25 1 6 Hãy l p quy ho ch s n su t đ thu đư c ti n lãi là l n nh t, bi t r ng ti n lãi thu đư c khi bán m t s n ph m A là 3 tri u đ ng, m t s n ph m B là 2 tri u đ ng. Ta xây d ng mô hình toán h c cho bài toán trên: G i x, y theo th t là s s n ph m A, B c n s n xu t theo k ho ch. Khi đó, ti n lãi thu đư c là: Z = 3x + 2y (tri u đ ng ) 3
  5. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Nh ng ràng bu c v nguyên li u d tr , đó là: 2x + 3y ≤ 18 (Ràng bu c v nguyên liêu I) 5x + 4y ≤ 30 (Ràng bu c v nguyên liêu II) x + 6y ≤ 25 (Ràng bu c v nguyên liêu III) Ngoài ra, còn các ràng bu c t nhiên là x, y ≥ 0. Vì s đơn v s n ph m không th âm. Như v y, b ng ngôn ng toán h c, bài toán có th phát bi u như sau: Tìm x và y sao cho t i đó bi u th c Z = 3x + 2y đ t giá tr l n nh t, v i các ràng bu c:   2x + 3y  18       5x + 4y  30 (1.1.1) x + 6 y   25       x 0, y 0 Bài toán t ng quát c a bài toán trên là: Hãy tìm véc tơ x = (x1 , x2 , . . . , xn ) n sao cho hàm f (x) = cj xj → max v i các ràng bu c : j=1 n      aij xj bi , i = 1...m j=1    xj  0, j = 1..n 1.1.2 Bài toán v n t i Bài toán. C n v n chuy n hàng t hai kho (tr m phát) P1 và P2 t i ba nơi tiêu th (tr m thu) T1 , T2 , và T3 . B ng dư i đây cho bi t cho bi t s lư ng hàng v n chuy n cùng v i cư c phí v n chuy n m t đơn v hàng t m i kho t i m i nơi tiêu th tương ng. Hãy l p l p k ho ch v n chuy n th a mãn yêu c u bài toán sao cho chi phí v n chuy n là nh nh t. 4
  6. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Ta xây d ng mô hình toán h c cho bài toán trên. G i xij là lư ng hàng hóa c n v n chuy n t Pi đ n Tj , (i = 1..2vj = 1..3) thì ta có mô hình toán h c bài toán là: Tìm X = (xij ) sao cho: f = 5x11 + 2x12 + 3x13 + 2x21 + x22 + x23 −→ min v i các ràng bu c:   x  11 +x12 +x13 = 30     x21 +x22 +x23 = 75         x11  +x21 = 35 (1.1.2)    x12 +x22 = 25        x13 +x23 = 45    x  0, i = 1..2, j = 1..3 ij Bài toán t ng quát c a bài toán v n t i. Bài toán có m tr m phát, lư ng phát là ai , i = 1, ..., m, n tr m thu, lương thu tương ng là bj , j = 1, ..., n; cij là cư c phí, xij là lư ng hàng v n chuy n t tr m phát th i đ n tr m thu j. Khi đó, bài toán có mô hình toán h c như sau: Tìm m n x = (xij ) sao cho f = cij xij → min v i các ràng bu c: i=1 j=1  n    xij = ai , i = 1, ..., m   j=1 m  xij = bj , j = 1, ..., n (1.1.3) i=1       xij 0, i = 1, ..., m, j = 1, ..., n 1.2. Bài toán quy ho ch tuy n tính 1.2.1 D ng t ng quát Bài toán quy ho ch tuy n tính là bài toán tìm bi n (ho c phương án) th a mãn các ràng bu c sao cho làm hàm m c tiêu đ t c c đ i ho c c c ti u. V i c hàm m c tiêu và các ràng bu c đ u tuy n tính theo bi n. Nh n xét, max(z) = − min(−z). Do đó, quy ho ch tuy n tính là: 5
  7. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Tìm x = (x1 , · · · , xn ) sao cho n f (x) = cj xj → min (1) j=1       n         aij   bi , i ∈ Ik , k = 1, 2, 3 (2) (1.2.4)        j=1   =          0, j ∈ Nl , l = 1, 2 (3)  x   j    Trong đó, véc tơ x th a các ràng bu c (2) và (3) đư c g i là phương án. Phương án là hàm m c tiêu f (x) đ t giá tr c c tr theo yêu c u đư c g i là phương án t i ưu. Gi i quy ho ch tuy n tính là tìm phương án t i ưu c a bài toán. 1.2.2 D ng chính t c và d ng chu n t c • Quy ho ch tuy n tính d ng chính t c là quy ho ch tuy n tính d ng n f (x) = cj xj → min (1) j=1 n      aij = bi , i = 1, · · · , m (2) j=1    xj 0, j = 1, 2 , · · · ,n (3)  • D ng ma tr n c a quy ho ch tuy n tính d ng chính t c f (x) = cT x → min (1) Ax = b (2) x 0 (3) Trong đó, c, x là véc tơ c t c a Rn , b là véc tơ c t c a Rm . A là ma tr n c p n×m • Nh n xét: M i quy ho ch tuy n tính đ u đưa đư c v d ng chính t c. Th t v y, n u Ai x ≥ bi (ho c Ai x ≤ bi ) thì ta ch n bi n bù xn+i đưa v d ng Ai x − xn+i = bi (ho c Ai x + xn+i = bi ). 6
  8. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Khi xj ≤ 0 (ho c xj ∈ R) thì ta thay xj = −xj (ho c xj = x+ x− ) mà j j xj , x+ , x− là các bi n không âm. j j Ví d 1. Đưa bài toán sau v d ng chính t c f (x) = 5x1 + 2x2 − 4x3 → max   4x1 +7x2   +x3 3    1 x 2 −x 3 −2x −1    2x1 +3x2 +6x3  = 11 x1 0, x2 0 Bài gi i Ta ch n bi n bù x4 , x5 cho cho ràng bu c th nh t, th hai. Ch n n ph x+ , x− và thay x3 = x+ − x− cho s không mang d u c a x3 . 3 3 3 3 T đó, ta đưa bài toán sau v d ng chính t c như sau: −f (x) = −5x1 − 2x2 + 4x3 → min   4x1 +7x2    +x3 −x4 = 3   1 x 2 3−x −2x +x5 = −1    2x1 +3x2 +6x3  = 11 xj 0, j = 1, 2, 4, 5; x∗ 3 0, ∗ = +, − • D ng ma tr n c a quy ho ch tuy n tính d ng chu n t c : f (x) = cT x → min (1) Ax b (2) x 0 (3) • Khi đưa t d ng chu n t c v chính t c ta ch c n thêm bi n bù cho các ràng bu c. 7
  9. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 1.3. ý nghĩa hình h c và phương pháp đ th Xét quy ho ch tuy n tính hai n f (x) = −2x1 + x2 → min   x  1 +2x2 2 (1)      2x1 −3x2   6 (2)    4x 1 +5x2 20 (3)    x1   0 (4)      x2 0 (5) Sau đây ta đây ta đưa ra cách gi i hình h c bài toán (phương pháp đ th ). Trư c h t ta bi u di n hình h c t p phương án (Hình 1). Trên m t ph ng t a đ 0x1 x2 , các ràng bu c đư c bi u di n b i các n a m t ph ng . Giao c a chúng là t p phương án c a bài toán. T p phương án bài toán là ngũ giác ABCDE. T p các đi m (x1 , x2 ) sao cho hàm m c tiêu nh n giá tr m : −2x1 + x2 = m, là đư ng th ng, đư c g i là đư ng m c (v i m c là m). Khi m thay đ i cho ta h đư ng th ng song song, có véc tơ pháp tuy n v = (−2, 1). Khi cho m gi m d n ta th y đi m cu i cùng mà đư ng m c (m) còn c t t p phương án là đ nh A. A là giao đi m c a đư ng th ng (2) và (3) nên A = (45/11, 8/11). 8
  10. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp 45 8 V y, x∗ = , là phương án t i ưu và fmin = f (x∗) = 82/11. 11 11 Nhân xét + Trong trư ng h p t p phương án khác r ng mà không có v trí gi i h n thì bài toán có hàm m c tiêu không b ch n + Phương pháp đ th có th áp d ng cho trư ng h p nhi u bi n nhưng ch có hai ràng bu c cư ng b c. 1.4. Bài t p chương 1 Bài 1.1. M t cơ s s n xu t có th làm đư c hai lo i hàng I và hàng II, t nguyên li u A và B. Tr lư ng các nguyên li u A và B hàng ngày có đư c theo th t là 6 và 8 đơn v . Đ s n xu t m t đơn v hàng I c n 2 đơn v nguyên li u lo i A và 3 đơn v nguyên li u lo i B; s n xu t m t đơn v hàng II c n 1 đơn v nguyên li u lo i A và 4 đơn v nguyên li u lo i B. Giá bán m t đơn v hàng I và hàng II theo th t là 7 và 5 đơn v ti n t . Qua ti p th đư c bi t, trong m t ngày nhu c u tiêu th hàng II không quá 2 đơn v ; nhu c u hàng I hơn hàng II không quá 1 đơn v . V n đ đ t ra là c n s n xu t m i ngày bao nhiêu đơn v hàng m i lo i đ doanh thu l n nh t. Hãy thi t l p mô hình toán h c cho bài toán đó? Bài 1.2. M t máy bay có tr ng t i M . Có n lo i hàng hóa c n x p lên máy bay đó. M i đơn v lo i j có kh i lư ng là aj và giá cư c phí là bj , (j = 1n). C n x p lên máy bay m i lo i hàng bao nhiêu đơn v đ t ng cư c phí thu đư c là nhi u nh t. Hãy thi t l p mô hình toán h c cho bài toán đó? Bài 1.3. Gi s m t nhà máy c n phân công cho m phân xư ng cùng s n xu t m t lo i máy có n chi ti t khác nhau, trong đó m i máy c n kj chi ti t th j (j = 1, . . . , n).aij là s chi ti t th j mà phân xư ng th i có th s n xu t trong m t đơn v th i gian. 9
  11. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Hãy l p mô hình toán h c bài toán xác đ nh s đơn v th i gian c n dành s n xu t chi ti t j c a phân xư ng i trong m t đơn v th i gian? Bài 1.4. Dùng đ nh nghĩa, ch ng t x∗ là phương án t i ưu c a các bài toán sau (a) f (x) = 84x1 + x3 → min  2x1 + x2 + x3 5      x1 − x2 + x3 1   4x1 − x3 −3   x1 0 x∗ = (0, 2, 3) (b) f (x) =x2 +x4 → min   −x1   +2x2 +x3 +x4 = 1    −2x1 +x2 +x3 +x4 = 2   3x2 + 2x4 = 3   x1 0 x∗ = (0, −1, 0, 3) (c) f (x) = x1 +x4 → max   x1 +x2 +x3 +x4 =1      1 x 2 +x 3 4 +3x +2x 4    −x1 +x2 +9x3 +4x4 = 16  x1 0 x∗ = (0, 1, 3, −3) Bài 1.5. Ch ng t r ng các bài toán sau có t p phương án khác r ng nhưng hàm m c tiêu không b ch n. 10
  12. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp f (x) = 3x1 −x2 → max      x1 +x2 2   −x1 +x2 2 (a)    x −2x  1 2 2 x1 0, x2 0 f (x) = x1 −x2 → min   2x −x −2    1 2   2x1 +x2 2 (b)   x1 −3x2   3 x1 0, x2 0 Bài 1.6. Tìm phương án t i ưu c a bài toán sau: f (x) = −x1 − 2x2 − 2x3 +6x4 → min   −2x +2x =5   1 2     −x1 +2x2   −x3 +x4 10    1−x −2x2 +3x4 = −2    2x1 +x3 −5x4 −13      −2x3   2x2 =5 Bài 1.7. Ch ng t r ng, đ i v i các bài toán sau, m i phương án đ u là phương án t i ưu: f (x) = −3x2 +2x3 −x4 → min   −5x1 +4x2 −x3 +3x4 = −7 (a)  −4x −7x +6x 1 2 3 −x4 =8 11
  13. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp f (x) = 100x1 + 70x2 − 30x3 → max   x1    −8x2 −9x3 −19  (b) x −3x −4x = −13  1  2 3   2x1 +5x2 +3x3 = −15  x1 0 Bài 1.8. Gi i b ng phương pháp đ th các bài toán sau: f (x) = −x1 + x2 → min   −2x1   +x2 2   x1 −2x2 2 (a)    x1 +x2 5   x1 0, x2 0 f (x) = x1 − 3x2 → max   4x1   +3x2 12   (b) 1−x 2 +x 5     x1 +5x2  6 x1 0, Bài 1.9. Đưa bài toán v d ng chính t c: f (x) = x1 + x2 → max   2x + x  1 1 2 (a)  x1 − x2  0 x1 0, x2 0 f (x) = x1 + x2 → min  (b)  0  x1 3  x2 −5  12
  14. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Bài 1.10. Cho bài toán f (x) = x1 + x2 → min   2x + x  1 3 2  λx1 + x2  2 x1 0, x2 0 Tìm t t c giá tr c a sao sao cho (a) T p phương án là r ng. (b) T p phương án khác r ng nhưng hàm m c tiêu không b ch n. (c) Bài toán có phương án t i ưu duy nh t . (d) Bài toán có vô s phương án t i ưu. Bài 1.11. Cho quy ho ch tuy n tính f (x) = 4x1 + 8x2 + x3 − 6x4 → min   2x1 +2x2 +3x3 +3x4   50    1 4x 2 +8x +2x3 +3x4 = 80    4x1 +4x2  +x3 +2x4 = 40 xj 0, j = 1..4 (a) Ch ng minh m i phương án c a bài toán đ u có x1 = x4 = 0. (b) Xác đ nh t p phương án. T đó tìm phương án t i ưu c a bài toán đã cho. 13
  15. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Chương 2. TÍNH CH T C A T P PHƯƠNG ÁN VÀ T P PHƯƠNG ÁN T I ƯU C A BÀI TOÁN QUY HO CH TUY N TÍNH 2.1. T ph pl i Đ nh nghĩa 2.1.1 (T h p l i). Gi s x1 , x2 , . . . , xm là các đi m c a Rn . Đi m m x đư c g i là t h p l i c a các đi m y n u t n t i λi 0, i = 1, .., m, λi = i=1 m 1 sao cho x = λi xi i=1 Trong trư ng h p x là t h p l i c a hai đi m x1 , x2 ta thư ng vi t x = λx1 + (1 − λ)x2 , 0 λ 1 T p h p các đi m là t h p l i c a hai đi m x1 , x2 đư c g i là đo n th ng n i hai đi m y. Khi đó, hai đi m x1 , x2 g i là đ u mút, các đi m còn l i c a đo n th ng g i là đi m trong c a đo n th ng y. Đ nh lý 2.1.2 (Tính ch t b c c u c a t h p l i). Đi m x là t h p l i c a các đi m xj , j = 1, .., m và m i đi m xj là t h p l i c a các đi m y i , i = 1, .., k. Khi đó x là t h p l i c a các đi m y i , i = 1, .., k. Đ nh nghĩa 2.1.3 (T p l i). T p L ⊂ Rn đư c g i là t p l i n u L ch a hai đi m nào đó thì nó ch a c đo n th ng n i hai đi m đó. T p r ng và t p đơn t đư c coi như t p l i. 14
  16. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Đ nh lý 2.1.4 (Tính ch t t p l i). (a) Giao c a các t p l i là t p l i. (b) N u L là t p l i thì nó ch a m i t h p l i c a h u h n đi m c a t p đó. Đ nh nghĩa 2.1.5 (Đi m c c biên c a t p l i). Đi m x0 c a t p l i L đư c g i là đi m c c biên c a t p l i y n u nó không là đi m trong c a đo n th ng n i hai đi m phân bi t trong L, t c là không t n t i trong L hai đi m phân bi t x1 , x2 sao cho x0 = λx1 + (1 − λ)x2 , 0 < λ < 1. Đ nh nghĩa 2.1.6 (Đa di n l i và t p l i đa di n). (a) T p L g m các đi m là t h p l i c a các đi m xi , i = 1, .., m cho trư c đư c g i là đa di n l i sinh b i h đi m đó xi . (b) Giao c a m t s h u h n các n a không gian trong Rn đư c g i là t p l i đa di n. Ngư i ta ch ng minh đư c r ng, m t t p l i đa di n không r ng và gi i n i là m t đa di n l i. 2.2. Tính ch t c a t p phương án và t p phương án t i ưu c a bài toán quy ho ch tuy n tính Đ nh lý 2.2.1 (Tính l i c a t p phương án). (a) T p các phương án c a bài toán quy ho ch tuy n tính là t p l i. (b) T p các phương án t i ưu c a bài toán quy ho ch tuy n tính là t p l i. Đ nh lý 2.2.2 (Phương án c c biên). (a) N u t p phương án c a bài toán quy ho ch tuy n tính không r ng và là đa di n l i thì bài toán đó có ít nh t m t phương án c c biên là phương án t i ưu. 15
  17. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp (b) Gi s x là m t đi m c a P = {x ∈ Rn : Ai x bi , i = 1, . . . , m}, trong đó Ai là ma tr n dòng th i c a ma tr n A c n × m. Khi đó, x là đi m c c biên c a P khi và ch khi th a mãn v i d u b ng đ i v i n b t phương trình đ c l p tuy n tính trong m b t phưng trình Ai x bi , i = 1..m. 2.3. Tính ch t c a quy ho ch tuy n tính d ng chính t c Đ nh lý 2.3.1 (Đi u ki n c a phương án c c biên). Gi s x0 = (x10 , x20 , . . . , xn0 ) là phương án khác 0 c a bài toán quy ho ch tuy n tính d ng chính t c, v i t p phưng án P = x ∈ Rn : x1 A1 + x2 A2 + ... + xn An = b; x 0 . Khi đó, x0 là phương án c c biên c a t p P khi và ch khi h véc tơ liên k t v i nó, t c là h H(x0 ) = Aj : xj0 > 0 đ c l p tuy n tính. H qu 2.3.2 (Tính h u h n c a phương án c c biên). 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 t c là h u h n. Đ nh lý 2.3.3 (Phương án c c biên t i ưu). 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 ưu thì nó có ít nh t m t phương án c c biên t i ưu. Đ nh lý 2.3.4 (Đi u ki n có phương án t i ưu). Đi u ki n c n và đ đ bài toán quy ho ch tuy n tính có phương án t i ưu là t p phương án khác r ng và hàm m c tiêu b ch n. 2.4. Bài t p chương 2 Bài 2.1. Ch ng minh các bài toán sau có phương án t i ưu (a) f (x) = 3x1 + 2x2 + x3 → max 16
  18. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp   x1 + x2 + x3 = 1  x −x +x =1 1 2 3 xj 0, j = 1, . . . , 3 (b) g(x) = x1 + x2 + x3 → min   −x1 + x2 + x3   1    1 −x − x − x 2 3 1    −x1 − x2 + x3  1 (c) ϕ(x) = 3x1 − x2 → min   2x1 + 5x2 10      1 2x + x 2 6    x1 + 2x2  2 x1 0, x2 0 Bài 2.2. Ch ng minh r ng hình tròn trong R2 là m t t p l i. Bài 2.3. Gi s x là đi m c a t p l i L. Ch ng minh r ng x là đi m c c biên c a L khi và ch khi L \ {x} là t p l i. Bài 2.4. Trên R2 , cho hai đi m A(2, 1) và B(3, 4) và h b t phương trình v i m-tham s   2x − y m−2      x − 3y m+3    x+y 2 − 3m  Tìm t t c các giá tr c a m sao cho m i đi m thu c đo n th ng AB đ u là nghi m c a h đã cho. Bài 2.5. Cho hai t p l i đa di n X = {x ∈ Rn : Ax b, x 0} , trong đó A là ma tr n c n × m và Y = {(x, y) : x ∈ Rn , y ∈ Rm , Ax − y = b, x 0, y 0}. Ch ng minh r ng x là đi m c c biên c a X thì (x, y) là đi m c c biên c a Y , đó y = Ax − b và ngư c l i. 17
  19. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Bài 2.6. Tìm t t c các đi m c c biên c a các t p l i cho b i h sau   x +x 2    1 2    x1 − 3x2 3  (a)  −3x + x 6    1 2    x  0, x 0 1 2   2x + x + 3x + 2x + 4x 10    1 2 3 4 5  (b) x1 + 3x2 + 2x3 + x4 + 3x5 = 5    xj 0, j = 1, .., 5   Bài 2.7. Trên R2 cho các đi m O(0, 0), A(0, 2), B(1, 3), C(2, 0). (a) Vi t h ràng bu c cho quy ho ch tuy n tính nh n t giác OABC làm t p phưng án. (b) V i giá tr nào c a tham s λ thì B là phương án t i ưu c a bài toán quy ho ch tuy n tính có t p phương án là OABC và hàm m c tiêu f (x) = x − 2y −→ min (c) Tìm mi n giá tr c a hàm s g(x) = x − 2y trên OABC. Bài 2.8. Cho quy ho ch tuy n tính f (x) = 2x1 + λx2 → max   −x1 + x2   3   x + 2x  1 2 12    3x1 − x2  15 x1 0, x2 0 (a) Đ i v i m i giá tr c a λ hãy tìm phương án t i ưu c a bài toán đã cho. (b) V i giá tr nào c a λ thì giá tr t i ưu hàm m c tiêu nh nh t. Bài 2.9. Tìm t t c các đi m c c biên c a các t p l i đư c xác đ nh b i các h sau   2x1 − 3x2   6   (a) 4x1 + 5x2 20    x1 0   18
  20. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp      x1 −x3 +2x4 = 1  (b) x1 +x2 +4x3 −2x4 = 2    x1 0 j = 1, ..., 4   Bài 2.10. Ch ng t các bài toán sau có phương án c c biên nhưng hàm m c tiêu không b ch n. f (x) = −x1 − 2x2 − 2x3 + 6x4 → max     −2x1 + 2x2 = 5     −x1 + 2x2 − x3 + x4  10 (a)     −x1 − 2x2 + 3x4 = −2   2x1 + x3 − 5x4 −13       2x2 − 2x3 = 5   f (x) = −4x1 + x2 − x3 + 5x4 → min   2x =4    1  (b)   6x1 −2x2  6     x3 −7   x3 +5x4 = −12   Bài 2.11. Cho quy ho ch tuy n tính f (x) = x1 + x2 → max   ax + bx  1 2 1  x  1 0, x2 0 Tìm t t c các giá tr tham s a, b sao cho (a) T p phương án khác r ng. (b) Bài toán đã cho có phương án t i ưu. (c) Hàm m c tiêu không b ch n. Bài 2.12. Đ i v i m i bài toán sau, ch ng t r ng, x∗ là phương án c c biên t i ưu. 19
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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