intTypePromotion=1
ADSENSE

Toán chuyên ngành - Quy hoạch tuyến tính

Chia sẻ: Lê Quang Hùng | Ngày: | Loại File: DOC | Số trang:99

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

Chuyên ngành quy hoạch tuyến tính được các nhà Toán học trên thế giới nghiên cứu và phát triển kể từ sau đại chiến thế giới lần thứ hai. Người tiên phong trong lĩnh vực này là G.B.Dantzig. Có nhiều bài toán thực tế thuộc các lĩnh vực khác nhau có thẻ mô tả toán học bằng quy hoạch tuyến tính

Chủ đề:
Lưu

Nội dung Text: Toán chuyên ngành - Quy hoạch tuyến tính

  1. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh CHƯƠNG I: BAI TOAN QUY HOACH TUYÊN TINH ̀ ́ ̣ ́ ́ §1 MÔT SỐ VÍ DỤ DÂN ĐÊN BAI TOAN QUY HOACH ̣ ̃ ́ ̀ ́ ̣ ́ ́ TUYÊN TINH I. Bai toan lâp kế hoach san xuât trong điêu kiên tai nguyên han chê: ̀ ́ ̣ ̣ ̉ ́ ̀ ̣ ̀ ̣ ́ Ví du: ̣ Nhân dip têt trung thu, 1 xí nghiêp muôn san xuât 3 loai banh: Đâu xanh, ̣ ́ ̣ ́ ̉ ́ ̣ ́ ̣ thâp câm, banh deo nhân đâu xanh. Để san xuât 3 loai banh nay, xí nghiêp ̣ ̉ ́ ̉ ̣ ̉ ́ ̣ ́ ̀ ̣ phai có đường, đâu, bôt, trứng, mứt, lap xưởng…Gia sử số đường có thể ̉ ̣ ̣ ̣ ̉ chuân bị được là 500kg, đâu là 300kg, cac nguyên liêu khac muôn có bao ̉ ̣ ́ ̣ ́ ́ nhiêu cung được. Lượng đường, đâu và số tiên lai khi ban 1 chiêc banh môi ̃ ̣ ̀ ̃ ́ ́ ́ ̃ ̣ loai cho trong bang: ̉ ́ Banh Banh đâu xanh ́ ̣ ́ Banh thâp câm ̣ ̉ ́ Banh deo ̉ Nguyên liêu ̣ Đường: 500kg 0.06kg 0.04kg 0.07kg Đâu: 300kg̣ 0.08kg 0 0.04kg Lai: ̃ 2 ngan ̀ 1.7 ngan ̀ 1.8 ngan ̀ Cân lâp kế hoach san xuât môi loai banh bao nhiêu cai để không bị đông về ̀ ̣ ̣ ̉ ́ ̃ ̣ ́ ́ ̣ đường, đâu và tông số lai thu được là lớn nhât( nêu san suât ra bao nhiêu ̣ ̉ ̃ ́ ́ ̉ ́ ̃ cung ban hêt) ́ ́ GIAI: ̉ Phân tich: ́ Goi x1; x2 ; x3 lân lượt là số lượng banh đâu xanh, thâp câm, banh deo cân ̣ ̀ ́ ̣ ̣ ̉ ́ ̉ ̀ ̉ san xuât ́ 1. Điêu kiên cua ân: xi ≥ 0, i = 1,3 . ̀ ̣ ̉ ̉ 2. Tông số đường: 0.06 x1 + 0.04 x2 + 0.07 x3 ̉ Tông số đâu: 0.08 x1 + 0.x2 + 0.04 x3 ̉ ̣ Tông tiên lai: 2 x1 + 1.7 x2 + 1.8 x3 ̉ ̀ ̃ Ta có mô hinh toan hoc cua bai toan: ̀ ́ ̣ ̉ ̀ ́ (1) f ( x ) = 2 x1 + 1.7 x2 + 1.8 x3 → max 0.06 x1 + 0.04 x2 + 0.07 x3 ≤ 500 ( 2)   0.08 x1 + 0.x2 + 0.04 x3 ≤ 300 ( 3) x j ≥ 0, j = 1.3 Mô hinh toan hoc dưới dang ma trân: ̀ ́ ̣ ̣ ̣ ̣ ̀ ̣ Ma trân rang buôc: -1-
  2. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh 0.06 0.04 0.07  A= 0.08 0 0.04  500 B=  vec tơ số hang tự do. ́ ̣ 300  x = ( x1; x2 ; x3 ) là vec tơ ân sô. ́ ̉ ́ Môt vec tơ x = ( x1; x2 ; x3 ) thoa (2) va(3) goi là 1 phương an cua bai toan. ̣ ́ ̉ ̀ ̣ ́ ̉ ̀ ́ Môt phương an x = ( x1; x2 ; x3 ) thoa (1) goi là 1 phương an tôi ưu cua bai ̣ ́ ̉ ̣ ́ ́ ̉ ̀ toan.́ II. Bai toan đâu tư vôn nhỏ nhât: ̀ ́ ̀ ́ ́ Ví du: ̣ Có 3 xí nghiêp may cung có thể san xuât ao vet và quân. Do trinh độ công ̣ ̀ ̉ ́ ́ ́ ̀ ̀ nhân, tai tổ chức, mức trang bị kỹ thuât…khac nhau, nên hiêu quả cua đông ̀ ̣ ́ ̣ ̉ ̀ vôn ở cac xí nghiêp cung khac nhau. Gia sử đâu tư 1000$ vao môi xí nghiêp ́ ́ ̣ ̃ ́ ̉ ̀ ̀ ̃ ̣ thì cuôi kỳ ta có kêt quả ́ ́ Xí nghiêp 1: 35 ao 45 quân. ̣ ́ ̀ Xí nghiêp 2: 40 ao 42 quân. ̣ ́ ̀ Xí nghiêp 3: 43 ao 30 quân. ̣ ́ ̀ Lượng vai và số giờ công cân thiêt để san xuât 1 ao hoăc 1 quân ( goi là ̉ ̀ ́ ̉ ́ ́ ̣ ̀ ̣ suât tiêu hao nguyên liêu và lao đông) được cho ở bang sau: ́ ̣ ̣ ̉ XN 1 2 3 ̉ San phâm ̉ ́ Ao vet ́ 3.5m 20h 4m 16h 3.8m 18h Quân ̀ 2.8m 10h 2.6m 12h 2.5m 15h Tông số vai và giờ công lao đông có thể huy đông được cho cả 3 xí nghiêp ̉ ̉ ̣ ̣ ̣ là 10.000m và 52.000 giờ công. Theo hợp đông kinh doanh thì cuôi kỳ phai có tôi thiêu 1500 bộ quân ao. Do ̀ ́ ̉ ́ ̉ ̀ ́ đăc điêm hang hoa, nêu lẻ bộ chỉ có quân là dễ ban. ̣ ̉ ̀ ́ ́ ̀ ́ Hay lâp kế hoach đâu tư vao môi xí nghiêp bao nhiêu vôn để : ̃ ̣ ̣ ̀ ̀ ̃ ̣ ́ - Hoan thanh kế hoach san phâm. ̀ ̀ ̣ ̉ ̉ - Không khó khăn về tiêu thu. ̣ - Không bị đông về vai và tiêu thu. ̣ ̉ ̣ - Tông số vôn đâu tư nhỏ nhât là điêu nôi bât cân quan tâm. ̉ ́ ̀ ́ ̀ ̉ ̣ ̀ Phân tich: ́ 1)Goi x1; x2 ; x3 lân lượt là số đơn vị vôn đâu tư ( 1000$) vao môi xí nghiêp. ̣ ̀ ́ ̀ ̀ ̃ ̣ ́ Ta co: x j ≥0, j =1,3 2)Tông số ao cua 3 XN: 35 x1 + 40 x2 + 43 x3 , ̉ ́ ̉ -2-
  3. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh 3)Tông số quân cua 3 XN: 45 x1 + 42 x2 + 30 x3 , ̉ ̀ ̉ Để không khó khăn về tiêu thụ thi: ̀ 45 x1 + 42 x2 + 30 x3 ≥ 35 x1 + 40 x2 + 43 x3 ⇔ 10 x1 + 2 x2 − 13 x3 ≥ 0 4)Tông số bộ quân ao= Tông số ao cua 3 XN: 35 x1 + 40 x2 + 43 x3 , ̉ ̀ ́ ̉ ́ ̉ 5) Tông số met vai cua 3 xí nghiêp ( dung để may ao và quân ): ̉ ́ ̉ ̉ ̣ ̀ ́ ̀ 3.5 × 35 x1 + 4 × 40 x2 + 3.8 × 43 x3 + 2.8 × 45 x1 + 2.6 × 42 x2 + 2.5 × 30 x3 248.5 x1 + 269.2 x2 + 238.4 x3 6) Tông số giờ công cua 3 xí nghiêp: ̉ ̉ ̣ 20 × 35 x1 + 16 × 40 x2 + 18 × 43 x3 + 10 × 45 x1 + 12 × 42 x2 + 15 × 30 x3 1150 x1 + 1144 x2 + 1224 x3 7) Tông số vôn đâu tư( đơn vi: 1000$): x1 + x2 + x3 ̉ ́ ̉ ̣ ̀ Mô hinh toan hoc ́ ̣ (1) f ( x ) = x1 + x2 + x3 → min  10 x1 + 2 x2 − 13 x3 ≥ 0  35 x1 + 40 x2 + 43 x3 ≥ 1500 ( 2)   248.5 x1 + 269.2 x2 + 238.4 x3 ≤ 10000  1150 x1 + 1144 x2 + 1224 x3 ≤ 52000  ( 3) x j ≥ 0, j = 1,3 Mô hinh toan hoc dưới dang ma trân: ̀ ́ ̣ ̣ ̣  10 2 − 13   0   35 40 43   1500  A= , B =   248.5 269.2 238.4 10000       1150 1144 1224  52000  ̀ ́ III. Bai toan vân tai ̣ ̉ Ví du: ̣ Ta cân vân tai vât liêu từ 2 kho: K1 và K2 , đên 3 công trường xây dựng: C1, ̀ ̣ ̉ ̣ ̣ ́ C2, C3 . Tông số vât liêu có ở môi kho, tông số vât liêu yêu câu cua môi ̉ ̣ ̣ ̃ ̉ ̣ ̣ ̀ ̉ ̃ -3-
  4. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh công trường, khoang cach từ môi kho đên môi công trường được cho ở ̉ ́ ̃ ́ ̃ ̉ bang sau: CT C1 C2 C3 km 15T 20T 25T Kho 5km 7km 2km K1 20T x11 x12 x13 4km 3km 6km K2 40T x21 x22 x23 Hay lâp kế hoach vân chuyên thế nao đê: ̃ ̣ ̣ ̣ ̉ ̀ ̉ ́ ̉ ́ - Cac kho giai phong hêt vât liêu. ́ ̣ ̣ - Cac công trường nhân đủ vât liêu cân thiêt. ́ ̣ ̣ ̣ ̀ ́ - Tông số T × km phai thực hiên là it nhât. ̉ ̉ ̣ ́ ́ GIAI ̉ Phân tich: ́ 1. Goi xij ( i = 1,2; j = 1,2,3) ̣ lân lượt là số tân vât liêu vân chuyên từ kho ̀ ́ ̣ ̣ ̣ ̉ Ki → C j ∀xij ≥ 0 2. Số tân vât liêu từ kho K1 đên 3 công trường: ́ ̣ ̣ ́ x11 + x12 + x13 3. Số tân vât liêu từ kho K2 đên 3 công trường: ́ ̣ ̣ ́ x21 + x22 + x23 4. Số tân vât liêu công trường C1 nhân được từ 3 kho: ́ ̣ ̣ ̣ x11 + x21 5. Số tân vât liêu công trường C2 nhân được từ 3 kho: ́ ̣ ̣ ̣ x12 + x22 6. Số tân vât liêu công trường C3 nhân được từ 3 kho: ́ ̣ ̣ ̣ x13 + x23 7. Tông số T × km : ̉ 5 x11 + 7 x12 + 2 x13 + 4 x21 + 3x22 + 6 x23 ̀ Mô hinh toan hoc: ́ ̣ -4-
  5. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh (1) f ( x ) = 5 x11 + 7 x12 + 2 x13 + 4 x21 + 3x22 + 6 x23 → min  x11 + x12 + x13 = 20  x + x + x = 40  21  22 23 ( 2)  x11 + x21 = 15  x + x = 20  12 22  x13 + x23 = 25  ( 3) xij ≥ 0 ( i = 1,2; j = 1,2,3) -5-
  6. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh ́ ̣ ̀ ́ ̣ ́ ́ §2 CAC DANG BAI TOAN QUY HOACH TUYÊN TINH ̣ ̉ ́ I. Dang tông quat: n (1) f ( x ) = ∑ c j x j → min ( max ) j =1  n  ∑ aij x j = bi  j =1  n ( 2)  ∑ aij x j ≤ bi   j =1  n  ∑ aij x j ≥ bi  j =1  ( 3) x j ≥ 0 ( j ∈ J1 ); x j ≤ 0 ( j ∈ J 2 ); x j tu  y y ′ ( j ∈ J 3 ) ; J1 ∪ J 2 ∪ J 3 = {1;2; ; n} - Vector x = ( x1; x2 ; ; xn ) thoa (2);(3) goi là 1 phương an cua bai toan. ̉ ̣ ́ ̉ ̀ ́ - Nêu phương an thoa (1) tức là ham muc tiêu đat cực đai( hay cực ́ ́ ̉ ̀ ̣ ̣ ̣ tiêu) thì goi là phương an tôi ưu. ̉ ̣ ́ ́ - Giai 1 bai toan QHTT là đi tim phương an tôi ưu hoăc chỉ ra bai toan ̉ ̀ ́ ̀ ́ ́ ̣ ̀ ́ không có phương an tôi ưu. ́ ́ Ví du: ̣ Bai toan sau đây có dang tông quat: ̀ ́ ̣ ̉ ́ (1) f ( x ) = 3x1 − x2 + 2 x3 + x4 + 5 x5 → max 2 x1 − x2 + x3 + 2 x4 + x5 ≤ 17  4 x1 − 2 x2 + x3 = 20 ( 2)    x1 − x2 + 2 x3 + x5 ≥ −18  x1 + x2 + 2 x3 + x4 ≤ 100  ( 3) x1; x4 ≥ 0; x2 ; x5 ≤ 0; x3 tu  y y′ ̣ ́ II. Dang chinh tăc: ́ n (1) f ( x ) = ∑ c j x j → min ( max ) j =1 n ( 2) ∑ aij x j = bi (i = 1, m) j =1 ( 3) x j ≥ 0 ( j = 1, n ) -6-
  7. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh Ví du: ̣ Bai toan sau đây có dang chinh tăc: ̀ ́ ̣ ́ ́ (1) f ( x ) = 3x1 − x2 + x3 − 3x4 + x5 → min  2 x1 + x2 − x3 + 3x4 = 0 ( 2)  x2 − x3 − x4 + x5 = −18   x + 2 x − x = 17  3 4 5 ( 3) x j ≥ 0; j = 1,5 ̣ ̉ III. Dang chuân: n (1) f ( x ) = ∑ c j x j → min ( max ) j =1  x1 + a1( m +1) xm +1 +  a1n xn = b1  x2 + a2( m +1) xm +1 +  a2n xn = b2 ( 2)     .......... .......... .......... ..........   xm + am( m +1) xm +1 +  amn xn = bm ( 3) x j ≥ 0 ( j = 1, n ); bi ≥ 0(i = 1, m ) x1 x2 xm xm +1 xn  1 0 ...... 0 a1( m +1) ... a1n    A=  0 1 ...... 0 a2( m +1) ... a2n             0 0 ...... 1 am( m +1) ... amn    Nhân xet: ̣ ́ Ta thây bai toan dang chuân là bai toan dang chinh tăc thêm 2 điêu kiên: ́ ̀ ́ ̣ ̉ ̀ ́ ̣ ́ ́ ̀ ̣  Cac số hang tự do không âm: bi ≥ 0 i = 1, m . ́ ̣ ( )  Ma trân cac hệ số rang buôc A chứa 1 ma trân đơn vị câp m. ̣ ́ ̀ ̣ ̣ ́ ̣ Đinh nghia: ̃ 1) ân cơ ban: Cac ân ứng với vec tơ côt đơn vị trong ma trân A goi là ân cơ ̉ ̉ ́ ̉ ́ ̣ ̣ ̣ ̉ ban, trên ma trân A ta có x1; x2 ; ; xm là cac ân cơ ban. ̉ ̣ ́ ̉ ̉ - ân cơ ban ứng với vec tơ côt đơn vị thứ i goi là ân cơ ban thứ i. Cac ân ̉ ̉ ́ ̣ ̣ ̉ ̉ ́ ̉ con lai là không cơ ban. ̀ ̣ ̉ 2) Phương an cơ ban: 1 phương an mà cac ân không cơ ban đêu băng 0 goi ́ ̉ ́ ́ ̉ ̉ ̀ ̀ ̣ là phương an cơ ban. ́ ̉ Nhân xet: ̣ ́ -7-
  8. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh Với bai toan dang chuân ta luôn có phương an cơ ban ban đâu : ̀ ́ ̣ ̉ ́ ̉ ̀ ( x1; x2 ;; xm ; xm +1;; xn ) = ( b1; b2 ;; bm ;0; ;0) bi ≥ 0, ∀i = 1, m Ví du: Bai toan sau có dang chuân ̣ ̀ ́ ̣ ̉ (1) f ( x ) = 3x1 − x2 + x3 − 3x4 + x5 → min  2 x1 + 2 x4 + x5 = 20 ( 2) − 3x1 + 4 x2 − 4 x4 + x6 = 0   x + 2 x + x + 3 x = 28  1 2 3 4 ( 3) x j ≥ 0; j = 1,6 x1 x2 x3 x4 x5 x6  2 0 0 2 1 0   A = − 3 4 0 − 4 0 1  1 2 1 3 0 0   Ta có x5 là ân cơ ban thứ nhât, x6 là ân cơ ban thứ hai, x3 là ân cơ ban thứ ̉ ̉ ́ ̉ ̉ ̉ ̉ ba Phương an cơ ban ban đâu: ( x1, x2 , x3, x4 , x5 , x6, ) = ( 0,0,28,0,20,0) ́ ̉ ̀ -8-
  9. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh ́ ̉ ̣ ̉ ̀ ́ ̣ ́ §3 BIÊN ĐÔI DANG CUA BAI TOAN QUY HOACH TUYÊN TINH́ I. Đưa dang tông quat về dang chinh tăc: ̣ ̉ ́ ̣ ́ ́ n ́ ̣ ̀ ̣ ̣ 1) Nêu găp rang buôc dang: ∑ aij x j ≤ bi ta công thêm vao vế trai 1 ân phụ ̣ ̀ ́ ̉ j =1 ( Slack variable) không âm xi +1 ≥ 0 để biên về dang phương trinh: ́ ̣ ̀ n ∑ aij x j + xn +1 = bi j =1 n ́ ̣ ̀ ̣ ̣ 2) Nêu găp rang buôc dang: ∑ aij x j ≥ bi ta công thêm vao vế trai 1 ân phụ ̣ ̀ ́ ̉ j =1 ( Slack variable) không âm xi +1 ≥ 0 , với hệ số -1 để biên về dang phương ́ ̣ ̀ trinh: n ∑ aij x j − xn +1 = bi j =1 Chú y: Cac ân phụ chỉ là những số giup ta biên bât phương trinh thanh ́ ́ ̉ ́ ́ ́ ̀ ̀ phương trinh, chứ không đong vai trò gì về kinh tê, nên nó không anh ̀ ́ ́ ̉ hưởng đên ham muc tiêu. Vì vây hệ số cua nó trong ham muc băng 0. ́ ̀ ̣ ̣ ̉ ̀ ̣ ̀ 3) Nêu găp ân x j ≤ 0 ta thay x j = −t j , t j ≥ 0 ́ ̣ ̉ 4) Nêu găp ân x j tu  y y ′ ta thay x j = x′j − x′′ , x′j , x′′ ≥ 0 ́ ̣ ̉ j j Ví du: ̣ Đưa bai toan sau về dang chinh tăc: ̀ ́ ̣ ́ ́ (1) f ( x ) = 2 x1 − x2 + 2 x3 + x4 − 2 x5 → min  x1 − 2 x2 + x3 + 2 x4 + x5 ≤ 7  x1 − 2 x2 + x3 + 2 x4 + x5 ≤ 7( a )  x2 + 2 x3 + x4 ≥ −1  − x2 − 2 x3 − x4 ≤ 1( b )   ( 2)  ⇔  2 x3 + x4 + 3x5 ≥ 10  2 x3 + x4 + 3x5 ≥ 10( c )  x1 + x2 − 2 x3 + x4 = 20   x1 + x2 − 2 x3 + x4 = 20( d )  ( 3) x1; x5 ≥ 0; x4 ≤ 0; x2 ; x3 tu  y y′ GIAI ̉  Công vao (a) ân phụ x6 ≥ 0 . ̣ ̀ ̉  Công vao (b) ân phụ x7 ≥ 0 . ̣ ̀ ̉  Công vao (c) ân phụ x8 ≥ 0 .với hệ số -1 ̣ ̀ ̉  Thay x4 = −t 4 ; t4 ≥ 0 -9-
  10. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh  ′ Thay x2 = x2 − x2 ; ′′ ′ ′′ x2 ≥ 0 x2 ≥ 0  Thay x3 = x3 − x3 ;′ ′′ ′ ′′ x3 ≥ 0 x3 ≥ 0 Bai toan đưa về dang chinh tăc như sau: ̀ ́ ̣ ́ ́ (1) f ( x ) = 2 x1 − ( x2 − x′2 ) + 2( x3 − x3 ) − t4 − 2 x5 + 0.x6 + 0 x7 + 0 x8 → min ′ ′ ′ ′′  x1 − 2( x2 − x′′ ) + ( x3 − x3 ) − 2t 4 + x5 + x6 = 7( a ) ′ 2 ′ ′′  − ( x2 − x2 ) − 2( x3 − x3 ) + t 4 + x7 = 1( b ) ′ ′′ ′ ′′ ( 2)    2( x3 − x3 ) − t 4 + 3x5 − x8 = 10( c ) ′ ′′   x1 + ( x2 − x2 ) − 2( x3 − x3 ) − t 4 = 20( d ) ′ ′′ ′ ′′ ( 3) x1; x5 ≥ 0; t4 ≥ 0; x2 ; x2 ; x3 ; x3 ; x6 ; x7 ; x8 ≥ 0 ′ ′′ ′ ′′ chú y: ́ ́ ( ) Nêu x1 , x20 , x20 , x30 , x30 , t 4 , x5 , x6 , x7 , x8 là phương an tôi ưu cua bai 0 ′ ′′ ′ ′′ 0 0 0 0 0 ́ ́ ̉ ̀ toan mới thì ́ ( 0 0 0 0 0 x1 , x2 , x3 , x4 , x5 with) x2 = x20 − x20 , x3 = x30 − x30 , x4 = −t 4 là 0 ′ ′′ 0 ′ ′′ 0 0 phương an tôi ưu cua bai toan gôc. ́ ́ ̉ ̀ ́ ́ II. Đưa dang chinh tăc về dang chuân: ̣ ́ ́ ̣ ̉ 1) Mô tả phương phap: ́ Giả sử bai toan đã có dang chinh tăc: (Gia sử bi ≥ 0, i = 1, m ) ̀ ́ ̣ ́ ́ ̉ n (1) f ( x ) = ∑ c j x j → min ( max ) j =1 a11 x1 +  + a1n x n = b1 a x +  + a x = b ( 2)  11 1  11 1 2    a11 x1 +  + a11 x1 = bm  ( 3) x j ≥ 0 ( j = 1, n )  Ta thêm vao môi phương trinh môt ân giả không âm xn +i ≥ 0 với ̀ ̃ ̀ ̣ ̉ ̣ hệ số 1  Trong ham muc tiêu f ( x ) → min , ân giả có hệ số M( M>0, M lớn ̀ ̣ ̉ hơn số nao ân so sanh) ̀ ̀ ́  Trong ham muc tiêu f ( x ) → max , ân giả có hệ số –M ̀ ̣ ̉ Ta có bai toan mới goi là bai toan mở rông cua bai toan xuât phat. ̀ ́ ̣ ̀ ́ ̣ ̉ ̀ ́ ́ ́ - 10 -
  11. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh n m (1) f ( x ) = ∑ c j x j ± M ∑ xn + i → min ( max ) j =1 i =1  a11x1 +  + a1n x n + xn +1 = b1 a x +  + a x + xn + 2 = b2 ( 2)  21 1  2n n   +  am1x1 +  + amn xn +  xn + m = bm ( 3) x j ≥ 0 ( j = 1, n + m )  a11 x1  a1n xn 1 0  0  a x  a2 n xn 0 1  0  A =  21 1            am1x1  amn xn 0 0  1  ́ ̣ ̉ ̉ ̉ ( ) Ta thây bai toan đã có dang chuân với ân cơ ban thứ i là xn + i i = 1, m là cac ́ ̀ ́ ̉ ân gia. ̉ Ví du: ̣ (1) f ( x ) = 2 x1 + x2 + x3 − x4 → max  x1 + 5 x2 + 5 x4 = 25 ( 2) − 4 x2 − x3 + 6 x4 = 18   3 x + 8 x = 28  2 4 ( 3) x j ≥ 0; j = 1,4 1 5 0 5 A= 0 − 4 − 1 6    0 3  0 8  Ta thây con thiêu vector côt đơn vị thứ 2 và thứ 3 nên phai thêm ân giả vao ́ ̀ ́ ̣ ̉ ̉ ̀ phương trinh thứ 2 và thứ 3. Bai toan đưa về dang chuân. ̀ ̀ ́ ̣ ̉ - 11 -
  12. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh (1) f ( x ) = 2 x1 + x2 + x3 − x4 − Mx5 − Mx6 → max  x1 + 5 x2 + 5 x4 = 25 ( 2) − 4 x2 − x3 + 6 x4 + x5 = 18   3 x + 8 x + x = 28  2 4 6 ( 3) x j ≥ 0; j = 1,6 1 5 0 5 0 0 A = 0 − 4 − 1 6 1 0    0 3  0 8 0 1  2) Quan hệ giữa bai toan xuât phat và bai toan mở rông ̀ ́ ́ ́ ̀ ́ ̣ ̣ NHÂN XET ́ a) Nêu x = ( x1, x2 , , xn ) là phương an cua bai toan xuât phat thì ́ ́ ̉ ̀ ́ ́ ́ x = ( x1 , x2 ,..., xn ,0,...,0 ) là phương an cua bai toan mở rông. ́ ̉ ̀ ́ ̣ ́ 0 0 0 ( 0 ) b) Nêu x = x1 , x2 , , xn là phương an tôi ưu cua bai toan xuât phat ́ ́ ̉ ̀ ́ ́ ́ ( ) thì x 0 = x1 , x2 , , xn ,0...,0 là phương an tôi ưu cua bai toan mở 0 0 0 ́ ́ ̉ ̀ ́ ̣ rông. Từ đó nêu bai mở rông không có phương an tôi ưu thì bai toan xuât phat ́ ̀ ̣ ́ ́ ̀ ́ ́ ́ cung không có phương an tôi ưu. ̃ ́ ́ 1 2 ( ) c) Nêu x 0 = x 0 , x 0 , , xn ,0...,0 là phương an tôi ưu cua bai toan mở ́ 0 ́ ́ ̉ ̀ ́ ̣ 0 0 ( 0 ) rông thì x 0 = x1 , x2 , , xn là phương an tôi ưu cua bai toan xuât ́ ́ ̉ ̀ ́ ́ phat.́ d) Nêu bai toan mở rông có phương an tôi ưu trong đó có 1 ân giả nhân ́ ̀ ́ ̣ ́ ́ ̉ ̣ giá trị dương thì bai toan xuât phat không có phương an. ̀ ́ ́ ́ ́ BAI TÂP CHƯƠNG I ̀ ̣ ̣ ̀ Lâp mô hinh toan hoc ́ ̣ 1) Công ty bao bì dược cân san xuât 3 loai hôp giây đựng thuôc B1, Cao sao ̀ ̉ ́ ̣ ̣ ́ ́ vang và đựng “Quy sâm đai bổ hoan”. ̀ ̣ ̀ Để san xuât ra cac hôp nay công ty dung cac tâm bia có kich thước ̉ ́ ́ ̣ ̀ ̀ ́ ́ ̀ ́ giông nhau. Môi tâm bia có 5 cach căt khac nhau ́ ̃ ́ ̀ ́ ́ ́ Cach ́ Hôp B1 ̣ ̣ Hôp cao sao ̣ Hôp quy sâm ̀ vang 1 2 0 2 2 0 7 4 - 12 -
  13. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh 3 8 0 3 4 1 6 2 5 9 2 0 Theo kế hoach số hôp B1 phai có là 1500, số hôp quy sâm là 2000, số hôp ̣ ̣ ̉ ̣ ̣ cao sao vang tôi thiêu là 1000. Cân phương an căt sao cho tông số tâm ̀ ́ ̉ ̀ ́ ́ ̉ ́ bia phai dung là it nhât. Hay lâp mô hinh bai toan. ̀ ̉ ̀ ́ ́ ̃ ̣ ̀ ̀ ́ 2) Xí nghiêp cơ khí An Phú cân căt 1000 đoan thep dai 0.55m; 800 đoan dai ̣ ̀ ́ ̣ ́ ̀ ̣ ̀ 0.8m và 1120 đoan dai 0.45m lam chuông ga. Để có cac đoan thep nay, xí ̣ ̀ ̀ ̀ ̀ ́ ̣ ́ ̀ nghiêp phai dung 3 loai thanh thep: loai 1 dai 1.2m; loai 2 dai 1.5m và loai 3 ̣ ̉ ̀ ̣ ́ ̣ ̀ ̣ ̀ ̣ dai 1.8m. Cac cach căt được cho trong bang dưới ̀ ́ ́ ́ ̉ ̣ Loai thep ́ ́ Cach căt ́ 0.55m 0.8m 0.45m Thừa I: 1.2m 1 1 0 1 0.2 2 2 0 0 0.1 3 0 0 2 0.3 II: 1.5m 1 1 1 0 0.15 2 1 0 2 0.05 3 0 1 1 0.25 4 0 0 3 0.15 III: 1.8m 1 1 1 1 0 2 0 1 2 0.1 3 0 2 0 0.2 4 0 0 4 0 Cân tim phương an căt sao cho tông số mâu thep thừa là it nhât. Lâp mô ̀ ̀ ́ ́ ̉ ̃ ́ ́ ́ ̣ ̀ ̀ hinh bai toan. ́ Nhân dang và đôi dang ̣ ̣ ̉ ̣ Trong cac bai toan từ 1 đên 5 dưới đây: ́ ̀ ́ ́ 1) (1) f ( x ) → min  2 x1 + x2 + 3x3 + 4 x5 = 17 ( 2)  4 x1 + 2 x3 + x4 + 5 x5 = 20 ( 3) x j ≥ 0( j = 1,5) 2) - 13 -
  14. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh (1) f ( x ) → max  x1 + x2 − 2 x3 + x4 + x5 = 32 ( 2)   x2 + x3 − 2 x4 = 16  x + x − 2 x + x = 32  1 2 3 4 ( 3) x1, x3 ≤ 0; x2 ≥ 0; x4 , x5 tu  y y′ 3) (1) f ( x ) → min  2 x1 + x2 + 3x3 + 4 x5 = 17 ( 2) 4 x1 + 2 x3 + x4 + 5 x5 = 20   − 2x + 4x + x = 6  1 5 6 ( 3) x j ≥ 0 ( j = 1,6) 4) (1) f ( x ) → max  x1 − x2 − 2 x3 ≤ 5 ( 2)  x1 + 2 x2 + x3 + x4 = 15   2 x + x + 3x ≥ 8  1 2 3 ( 3) x j ≥ 0 ( j = 1,4) 5) (1) f ( x ) → min  x1 − 2 x2 − 2 x3 = −7 ( 2)  x2 + 2 x3 + x4 ≤ 15   2 x + 3x + x ≥ 8  1 3 4 ( 3) x j ≥ 0 ( j = 1,4) a) Những bai toan nao đã có dang chinh tăc. ̀ ́ ̀ ̣ ́ ́ b) Những bai toan nao đã có dang chuân? Ân cơ ban là những ân nao? ̀ ́ ̀ ̣ ̉ ̉ ̉ ̉ ̀ Thứ tự cua nó thế nao?Hay tim phương an cơ ban ban đâu cua no. ̉ ̀ ̃ ̀ ́ ̉ ̀ ̉ ́ c) Những bai toan nao chưa có dang chuân hay đưa về dang chuân sau ̀ ́ ̀ ̣ ̉ ̃ ̣ ̉ đó cho biêt ân nao là ân cơ ban, ân cơ ban ây là ân gi?( ân chinh , ân ́ ̉ ̀ ̉ ̉ ̉ ̉ ́ ̉ ̀ ̉ ́ ̉ phu, ân gia) thứ tự cua nó thế nao? Phương an cơ ban ban đâu cua ̣ ̉ ̉ ̉ ̀ ́ ̉ ̀ ̉ bai toan dang chuân nay thế nao. ̀ ́ ̣ ̉ ̀ ̀ - 14 -
  15. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh CHƯƠNG II: PHƯƠNG PHAP ĐƠN HINH ́ ̀ §1 THUÂT TOAN ĐƠN HINH ̣ ́ ̀ I. Trường hợp f ( x ) → min ( gôm 5 bước) ̀ Bước 1: Lâp bang ban đâu ̣ ̉ ̀ ̉ Ân Phươn c1 c2 cr cm cm +1  cv  cn Hệ cơ g λi ̉ số ban an ́ x1 x2 xr xm xm +1  xv  xn c1 x1 b1 1 0  0  0 a1( m +1)  a1v  a1n λ1 c2 x2 b2 0 1  0  0 a2( m +1)  a 2v  a2 n λ2 cr xr br 0 0  1  0 a3( m +1)  arv  arn λr cm xm bm 0 0  0  1 am( m +1)  amv  amn f ( x) f0 ∆1 ∆2 ∆r ∆ m ∆ m +1  ∆ v  ∆ n m m Trong đó f 0 = ∑ ci bi & ∆ j = ∑ ci aij − c j i =1 i =1 Bước 2: Kiêm tra tinh tôi ưu ̉ ́ ́ a) Nêu ∆ j ≤ 0 ́ ∀j thì phương an đang xet là tôi ưu và giá trị ham ́ ́ ́ ̀ muc tiêu tương ứng là f ( x ) = f 0 ̣ b) Nêu ∃∆ j > 0 ́ ( ) ma  aij ≤ 0 i = 1, m thì bai toan không có phương ̀ ́ an tôi ưu ́ ́ Nêu cả 2 trường hợp trên không xay ra thì chuyên sang bước 3 ́ ̉ ̉ Bước 3: Tim ân đưa vao: ̀ ̉ ̀ ∆ = max ∆ j thi xv Nêu v ́ j được chon đưa vao. ̣ ̀ Bước 4: Tim ân đưa ra: ̀ ̉ b λi = i with aiv > 0 aiv If λr = min λi then xr out i - 15 -
  16. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh Bước 5:Biên đôi bang(dung phương phap khử Gauss-Jordan) ́ ̉ ̉ ̀ ́ 1. Thay xr băng xv . Cac ân cơ ban khac và cac hệ số tương ứng giữ ̀ ́ ̉ ̉ ́ ́ nguyên. 2. hang chuân=hang đưa ra( xr )/ arv . ̀ ̉ ̀ 3. hang i(mới)= − aiv × hang chuân+ hang i(cu). ̀ ̀ ̉ ̀ ̃ 4. hang cuôi (mới)= − ∆ v × hang chuân+ hang cuôi(cu). ̀ ́ ̀ ̉ ̀ ́ ̃ II. Trường hợp f ( x ) → max Đăt g ( x ) = − f ( x ) → min . Vây ta đã chuyên về bai toan Ham muc tiêu cực ̣ ̣ ̉ ̀ ́ ̀ ̣ tiêu và do đó ta hoan toan có thể ap dung kêt quả cua bai toan min. ̉ ̀ ̀ ́ ̣ ́ ̉ ̀ ́ Ví du: ̣ ̉ ̀ Giai bai toan QHTT:́ (1) f ( x ) = 2 x1 + 5 x2 + 4 x3 + x4 − x5 → min  x1 − 6 x2 − 2 x4 − 9 x5 = 32  ( 2) 2 x2 + x3 + 1 x4 + 3 x5 = 30  2 2  3x2 + x5 ≤ 36 ( 3) x j ≥ 0; j = 1,5 → s tan dard form (1) f ( x ) = 2 x1 + 5 x2 + 4 x3 + x4 − x5 + 0.x6 → min  x1 − 6 x2 − 2 x4 − 9 x5 = 32  ( 2) 2 x2 + x3 + 1 x4 + 3 x5 = 30  2 2  3x2 + x5 + x6 = 36 ( 3) x j ≥ 0; j = 1,6 1 − 6 0 − 2 − 9 0  1 3  A = 0 2 1 0 2 2 0 3 0 0 1 1   - 16 -
  17. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh Bang đơn hinh: ̉ ̀ Hệ số Ân cơ Phươn ̉ 2 5 4 1 -5 0 ban̉ ́ g an x1 x2 x3 x4 x5 x6 2 x1 32 1 -6 0 -2 -9 0 4 x3 30 0 2 1 ½ 3/2 0 0 x6 36 0 3 0 0 1 1 f ( x) 184 0 -9 0 -3 -7 0 ∆ j ≤ 0, ∀j ⇒ phương an tôi ưu là ( x1 , x2 , x3 , x4 , x5 ) = ( 32,0,30,0,0 ) ́ ́ Ví du: ̣ (1) f ( x ) = 6 x1 + x2 + x3 + 3x4 + x5 − 7 x6 + 7 → min  − x1 + x2 − x4 + x6 = 15 ( 2)  2 x1 − x3 + 2 x6 = −9  4 x + 2 x + x − 3 x = 2  1 4 5 6 ( 3) x j ≥ 0; j = 1,6 → s tan dard form (1) f ( x ) = 6 x1 + x2 + x3 + 3x4 + x5 − 7 x6 + 7 → min  − x1 + x2 − x4 + x6 = 15 ( 2)  − 2 x1 + x3 − 2 x6 = 9  4 x + 2 x + x − 3 x = 2  1 4 5 6 ( 3) x j ≥ 0; j = 1,6 −1 1 0 −1 0 1  A = − 2 0 1 0 0 − 2     4 0 0 2 1 − 3   - 17 -
  18. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh Bang đơn hinh: ̉ ̀ Hệ số Ân cơ Phươn ̉ 6 1 1 3 1 -7 ban̉ ́ g an x1 x2 x3 x4 x5 x6 1 x2 15 -1 1 0 -1 0 (1) 1 x3 9 -2 0 1 0 0 -2 1 x5 2 4 0 0 2 1 -3 f ( x) 26+7 ∆1 ∆2 ∆3 ∆4 ∆5 ∆6 -5 0 0 -2 0 (3) -7 x6 15 -1 1 0 -1 0 1 1 x3 39 -4 2 1 -2 0 0 1 x5 47 1 3 0 -1 1 0 f ( x) -19+7 -2 -3 0 (1) 0 0 Ở phương an cơ ban ban đâu: ́ ̉ ̀ max ∆ j = ∆ 6 = 3 ⇒ x6 ( in ) arv = 1 ⇒ x2 ( out ) Ở phương an thứ 2 ́ max ∆ j = ∆ 4 = 1but ai 4 < 0, { − 1,−2,−1} ⇒ bai toan không có phương an tôi ̀ ́ ́ ́ ưu. - 18 -
  19. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh Ví du: ̣ (1) f ( x ) = −2 x1 + 6 x2 + 4 x3 − 2 x4 + 3x5 → max  x1 + 2 x2 + x3 = 52 ( 2) 4 x2 + 2 x3 + x4 = 60   3x + x = 36  2 5 ( 3) x j ≥ 0; j = 1,5 → s tan dard form (1) g ( x) = − f ( x ) = 2 x1 − 6 x2 − 4 x3 + 2 x4 − 3x5 → min  x1 + 2 x2 + 4 x3 = 52 ( 2) 4 x2 + 2 x3 + x4 = 60   3x + x = 36  2 5 ( 3) x j ≥ 0; j = 1,5 1 2 4 0 0  A = 0 4 2 1 0    0 3 0 0 1    Bang đơn hinh: ̉ ̀ Hệ số Ân cơ Phươn ̉ 2 -6 -4 2 -3 ban̉ ́ g an x1 x2 x3 x4 x5 2 x1 52 1 2 (4) 0 0 2 x4 60 0 4 2 1 0 -3 x5 36 0 3 0 0 1 g ( x) 116 ∆1 ∆2 ∆3 ∆4 ∆5 0 9 (16) 0 0 x3 13 1/4 1/2 1 0 0 x4 34 -1/2 (3) 0 1 0 x5 36 0 3 0 0 1 g ( x) -92 -4 (1) 0 0 0 x3 22/3 1/3 0 1 -1/6 0 x2 34/3 -1/6 1 0 1/3 0 x5 2 1/2 0 0 -1 1 - 19 -
  20. ́ ̀ Toan chuyên nganh ̣ ́ ́ Quy hoach tuyên tinh g ( x) -310/3 -23/6 0 0 -1/3 0 Ở phương an cơ ban ban đâu: ́ ̉ ̀ max ∆ j = ∆3 =16 ⇒ x3 ( in ) 52 min λi = λ = 1 =13 4 arv = 4 ⇒ x1 ( out ) Ở phương an thứ 2 ́ max ∆ j = ∆ 2 = 1 ⇒ x2 ( in ) 34 min λi = λ2 = 3 arv = 3 ⇒ x4 ( out ) Phương an cuôi cung: ∆ j ≤ 0, ∀j ⇒ ta có phương an tôi ưu la: ́ ́ ̀ ́ ́ ̀ ( x1, x2 , x3 , x4 , x5 ) =  0, 34 , 22 ,0,2     3 3  310 Giá trị cua phương an: f 0 = − g 0 = ̉ ́ 3 - 20 -
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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