Quy hoạch Tuyến tính

Chia sẻ: Nguyễn Văn Cường | Ngày: | Loại File: PDF | Số trang:81

2
1.546
lượt xem
315
download

Quy hoạch Tuyến tính

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ự tí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,III.

Chủ đề:
Lưu

Nội dung Text: Quy hoạch Tuyến tính

  1. 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
  2. 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
  3. 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
  4. 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 cj xj → max v i các ràng bu c : sao cho hàm f (x) = 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
  5. 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 cij xij → min v i các ràng bu c: x = (xij ) sao cho f = i=1 j =1 n  xij = ai , i = 1, ..., m    j =1   m  (1.1.3) xij = bj , j = 1, ..., n 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
  6. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp Tìm x = (x1 , · · · , xn ) sao cho n cj xj → min (1) f (x) = j =1      n         bi , i ∈ Ik , k = 1, 2, 3 (2) aij   (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 cj xj → min (1) f (x) = j =1 n   aij = bi , i = 1, · · · , m (2)    j =1   0, j = 1, 2 , · · · ,n (3)  xj  • 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
  7. 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à jj 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     −x −2x −1 x 1 2 3    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  −x4 = 3  4x1 +7x2 +x3     −x −2x +x5 = −1 x 1 2 3    2x1 +3x2 +6x3 = 11  0, j = 1, 2, 4, 5; x∗ 0, ∗ = +, − xj 3 • 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
  8. 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 +5x2 20 (3) 1     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
  9. 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
  10. 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     x +x +3x +2x 4 1 2 3 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
  11. 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  2 1 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     −x −2x2 = −2 +3x4 1    −5x4 −13  2x1 +x3      −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 3 −x4 =8 1 2 11
  12. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp f (x) = 100x1 + 70x2 − 30x3 → max  −8x2 −9x3 −19  x1     (b) −3x −4x = −13 x 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     −2x2 x1 2 (a)    x1 +x2 5   x1 0, x2 0 f (x) = x1 − 3x2 → max   4x1 +3x2 12     (b) −x +x 5 1 2     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  −5  x2  12
  13. 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 3 1 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     4x +8x +2x3 +3x4 = 80 1 2     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
  14. 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. Tph 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 λi xi 1 sao cho x = 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
  15. 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
  16. 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 : bi , i = 1, . . . , m}, trong đó Ai x 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 : xj 0 > 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
  17. 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     −x − x − x 1 1 2 3     −x1 − x2 + x3 1  (c) ϕ(x) = 3x1 − x2 → min   2x1 + 5x2 10     2x + x 6 1 2     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    2 − 3m  x+y  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 0} , trong đó A là b, x ma tr n c n × m và Y = {(x, y ) : x ∈ Rn , y ∈ Rm , Ax − y = b, x 0}. 0, y 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
  18. 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     x1 + 3x2 + 2x3 + x4 + 3x5 = 5 (b)    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 12 1 2    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
  19. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp  −x3 x1 +2x4 = 1      (b) −2x4 = 2 x1 +x2 +4x3    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  −7 x3       x3 +5x4 = −12   Bài 2.11. Cho quy ho ch tuy n tính f (x) = x1 + x2 → max   ax + bx 1 1 2  x 0, x2 0 1 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
  20. Quy ho ch tuy n tính Trư ng ĐHSP Đ ng Tháp (a) (x) = 4x1 −6x2 +3x3 → min f  −2x +4x −x3 0 1 2       3x1 −5x2 +2x3 1     −x1 −2x3 −2    −3x2 +x3 2       −x2 −2  x1  x∗ = (2, 1, 0) f (x) = x2 +2x3 −2x4 −2x5 → max  −2x1 +3x2 +x3 x5 = 4       (b)  4x1 −5x2  +3x4 −x5 = −6  x1 +2x2 +2x3 −x4 = 3        xj 0 , j = 1, .., 5   x∗ = (1, 2, 0, 0, 0) Bài 2.13. Cho quy ho ch tuy n tính f (x) = x1 +x2 → max   2x1 −2x2 −1       x2 0   −1 x1 +2x2        −x1 +4x2 3   2 1 71 Trong các đi m x1 = (−1, 0), x2 = − , − , x3 = (−7, −1), x4 = − , − , 3 6 99 đi m nào là phương án c c biên, phương án t i ưu c a bài toán đã cho? 20

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản