Quy hoạch tuyến tính - ĐH Sư Phạm Đồng Tháp
lượt xem 35
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Quy hoạch tuyến tính - ĐH Sư Phạm Đồng Tháp
- Quy hoạch tuyến tính
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Quy hoạch tuyến tính
110 p | 1070 | 384
-
Giáo trình Quy hoạch tuyến tính: Phần 1 - TS. Võ Văn Tuấn Dũng
63 p | 423 | 141
-
Toán chuyên ngành - Quy hoạch tuyến tính
99 p | 304 | 78
-
Giáo trình Quy hoạch tuyến tính: Phần 2 - TS. Võ Văn Tuấn Dũng
79 p | 194 | 77
-
Giáo trình Quy hoạch tuyến tính: Phần 1
100 p | 167 | 46
-
Giáo trình Quy hoạch tuyến tính - Lê Đức Thắng
131 p | 165 | 17
-
Bài giảng Quy hoạch tuyến tính: Chương 3 - ThS. Nguyễn Văn Phong (2016 - BT)
17 p | 218 | 15
-
Đề cương chi tiết học phần Quy hoạch tuyến tính
5 p | 212 | 12
-
Kỹ thuật Quy hoạch tuyến tính
81 p | 97 | 11
-
Bài giảng Quy hoạch tuyến tính: Chương 1 - ThS. Nguyễn Văn Phong (2016)
11 p | 147 | 11
-
quy hoạch tuyến tính
82 p | 131 | 11
-
quy hoạch tuyến tính - trường Đhsp Đồng tháp
81 p | 110 | 10
-
Bài giảng Quy hoạch tuyến tính: Chương 1 - ThS. Nguyễn Văn Phong
14 p | 125 | 7
-
Bài giảng Lý thuyết cơ bản về Quy hoạch tuyến tính - Chương 3: Bài toán đối ngẫu
18 p | 122 | 5
-
Bài giảng Lý thuyết cơ bản về Quy hoạch tuyến tính - Chương 1: Lý thuyết cơ bản về Quy hoạch tuyến tính
28 p | 126 | 5
-
Bài giảng Tối ưu hóa và quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính
86 p | 32 | 5
-
Bài giảng Quy hoạch tuyến tính - ThS. Nguyễn Hải Đăng
67 p | 40 | 3
-
Xây dựng thuật toán quy hoạch tuyến tính dựa trên gia lượng ngẫu nhiên
6 p | 78 | 2
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