Giáo trình Quy hoạch và quản lý nguồn nước part 6

1. Các khái niệm và nội dung cơ bản về quy hoạch và quản lý nguồn nước 2. Đặc điểm Tài nguyên nước và vấn đề quy hoạch quản lý nguồn nước của Việt Nam 3. Phân tích kinh tế trong quy hoạch và phát triển nguồn nước 4. Kỹ thuật phân tích hệ thống ứng dụng trong quy hoạch và quản lý nguồn nước 5. Áp dụng phương pháp tối ưu hoá trong quy hoạch và quản lý nguồn nước 6. Hệ thống hỗ trợ ra quyết định trong quy hoạch quản lý nguồn nước...
Nội dung trích xuất từ tài liệu:
Giáo trình Quy hoạch và quản lý nguồn nước part 6 96 Quy ho¹ch vµ qu¶n lý nguån n­íc Bµi to¸n t×m cùc ®¹i (5- 21) cã d¹ng: F(X ) c1 x1 + c2 x 2 + ... + c i x i + ... + c n x n ® max (5-36) Víi ci lµ h»ng sè víi biÕn thø i. Víi rµng buéc lµ: g j (X ) = a j1 x1 + a j2 x 2 + ... + a jn x n = b j ; j = 1, m (5-37) vµ xi ³ 0 víi i=1, 2,..., n; ®­îc ®­a vÒ d¹ng chÝnh t¾c víi hµm môc tiªu: max F(X) = min(-F(X)) tøc lµ: F1 (X ) = - F(X ) = - c1 x1 - c 2 x 2 - ... - c i x i - ... - c n x n ® min VÝ dô: T×m X = (x1,, x2, x3, x4) sao cho hµm môc tiªu: Z = x1+ 2x2 - 3x3+ 4x4 ® max Víi c¸c rµng buéc: ìx1 - x 2 + 7x 3 + x 4 = 100 ï í2 x1 + 3x 2 - x3 + 10x 4 = 800 ïx ³ 0; i = 1 ¸ 4 îi §­îc ®­a vÒ d¹ng chÝnh t¾c nh­ sau: T×m X = (x1, , x2, x3, x4) sao cho hµm môc tiªu: Z = -x1 - 2x2 + 3x5 - 4x4 ® min Víi c¸c rµng buéc: ìx1 - x 2 + 7x 3 + x 4 = 100 ï í2 x1 + 3x 2 - x3 + 10x 4 = 800 ïx ³ 0; i = 1 ¸ 4 îi 5.4.2.2. D¹ng chuÈn t¾c D¹ng chuÈn t¾c lµ d¹ng mµ rµng buéc lµ bÊt ®¼ng thøc, tøc lµ: g (X) = a x + a x + ... + a x + ... + a x £ b ; j = 1, m (5- 38) j j1 1 j2 2 ji i jn n j vµ xi ³ 0 víi i =1, 2,..., n. 97 Ch­¬ng 5- Kü thuËt ph©n tÝch hÖ thèng... 5.4.2.3. §-a bµi to¸n QHTT vÒ d¹ng chuÈn t¾c vµ d¹ng chÝnh t¾c + NÕu rµng buéc cã d¹ng gj(X) ³ bj: Nh©n 2 vÕ cña biÓu thøc rµng buéc víi (- 1), ®­a bµi to¸n vÒ d¹ng chuÈn víi rµng buéc d¹ng (5- 21). + §­a bµi to¸n chuÈn t¾c vÒ d¹ng chÝnh t¾c: Bµi to¸n d¹ng chuÈn cã thÓ ®­a vÒ d¹ng chÝnh t¾c b»ng c¸ch thªm c¸c biÕn phô vµo vÕ tr¸i cña c¸c bÊt ®¼ng thøc. Cã m rµng buéc bÊt ®¼ng thøc sÏ cã m biÕn phô. Do ®ã d¹ng chÝnh t¾c míi sÏ cã n + m nghiÖm. Ta cã: g (X) + x = 0 ; j = 1, m (5-39) j n+j trong ®ã: x lµ biÕn phô; n+j vµ xi ³ 0 víi i=1, 2,..., n. 5.4.3. §Þnh lý c¬ b¶n vµ c¸c ®Þnh nghÜa vÒ quy ho¹ch tuyÕn tÝnh 5.4.3.1. §Þnh lý c¬ b¶n cña quy ho¹ch tuyÕn tÝnh §Þnh lý (ph¸t biÓu cho d¹ng chÝnh t¾c): Ph­¬ng ¸n tèi ­u cña quy ho¹ch tuyÕn tÝnh chøa mét sè biÕn d­¬ng ®óng b»ng sè c¸c rµng buéc d¹ng ®¼ng thøc ®éc lËp , c¸c biÕn cßn l¹i cã gi¸ trÞ “0”. VÝ dô bµi to¸n QHTT cã 5 biÕn vµ 3 rµng buéc nh­ sau: F(X ) c1 x1 + c2 x 2 + ... + c i x i + ... + c5 x 5 ® min víi n = 5 víi c¸c rµng buéc ®¼ng thøc: a11x1 + a12x2 + … + a15x5 = b1 a21x1 + a22x2 + … + a25x5 = b2 a31x1 + a32x2 + … + a35x5 = b3 ® Sè rµng buéc m = 3 Do ®ã nghiÖm tèi ­u cã 3 biÕn kh¸c kh«ng, hai biÕn cßn l¹i cã gi¸ trÞ kh«ng. * Ch¼ng h¹n nghiÖm lµ: X = (*, *, 0, 0, *) . NÕu bµi to¸n tèi ­u tuyÕn tÝnh d¹ng chÝnh t¾c cã nghiÖm th× nghiÖm cña bµi to¸n sÏ n»m ë c¸c ®iÓm cùc biªn: c¸c ®Ønh tam gi¸c (®èi víi bµi to¸n ph¼ng) vµ ®Ønh c¸c ®a gi¸c (®èi víi bµi to¸n 3 chiÒu) v.v... C¸c ph­¬ng ph¸p t×m nghiÖm cña bµi to¸n th­êng lµ c¸c phÐp thö dÇn t¹i c¸c ®iÓm cùc biªn. Gi¶ sö ®· dß t×m ë tÊt c¶ nh÷ng ®iÓm cùc biªn mµ kh«ng t×m ®­îc mét tr­êng hîp nµo cã xi ³ 0 víi mäi i th× bµi to¸n lµ v« nghiÖm. 98 Quy ho¹ch vµ qu¶n lý nguån n­íc 5.4.3.2. Kh¸i niÖm vÒ ph-¬ng ¸n c¬ së chÊp nhËn ®-îc a. BiÕn c¬ së (BCS) vµ biÕn tù do (BTD) Gi¶ sö ta xÐt mét bµi to¸n tèi ­u chÝnh t¾c cã n biÕn sè, víi sè ph­¬ng tr×nh rµng buéc ®¼ng thøc lµ m. Ta gäi: TËp hîp c¸c biÕn ®­îc chän tuú ý víi gi¶ thiÕt lµ xi ³ o, víi i=1® m, · trong ®ã m lµ sè c¸c ph­¬ng tr×nh rµng buéc ®­îc gäi c¸c biÕn c¬ së. TËp hîp c¸c biÕn cßn l¹i xj víi j ¹ i, j = (n-m)® n ®­îc gäi lµ biÕn tù do. · b. Ph-¬ng ¸n c¬ së Lµ ph­¬ng ¸n mµ c¸c biÕn tù do ®­îc chän b»ng kh«ng, tøc lµ ta gi¶ ®Þnh x j = 0 víi mäi j thuéc biÕn tù do. Gi¸ trÞ cña c¸c biÕn c¬ së ®­îc x¸c ®Þnh theo thñ tôc sau: - Chän biÕn c¬ së cña bµi to¸n - Gi¶ ®Þnh c¸c gi¸ trÞ cña biÕn tù do b»ng kh«ng xj =0 víi mäi j thuéc biÕn tù do. - X¸c ®Þnh gi¸ trÞ cña biÕn c¬ së b»ng c¸ch gi¶i hÖ c¸c ph­¬ng tr×nh rµng buéc sau khi thay c¸c gi¸ trÞ b»ng kh«ng cña biÕn tù do vµo ph­¬ng tr×nh. c. Ph-¬ng ¸n c¬ së chÊp nhËn ®-îc Lµ ph­¬ng ¸n c¬ së cã c¸c biÕn c¬ së nhËn c¸c gi¸ trÞ d­¬ng. d. VÝ dô XÐt bµi to¸n QHTT Z = 6x1 + 2 x 2 - 5x3 + x 4 + 4 x5 - 3x 6 + 12 x 7 ® min Víi c¸c rµng buéc: x1 + x2 + x 3 + x4 = 4 x1 + x5 =2 x3 + x6 =3 (5-40) 3x2 + x3 + x7 =6 xi ³ 0, j = 1, 2,..., 7 Chän biÕn c¬ së: Ph-¬ng ¸n 1: - Chän c¸c biÕn x 4, x5, x6 , x7 lµ biÕn c¬ së, tøc lµ X = (0, 0, 0, x 4, x5, x6, x7 ). - Thay c¸c gi¸ trÞ cña X vµo hÖ ph­¬ng tr×nh rµng buéc (5-40) t×m ®­îc gi¸ trÞ c¸c biÕn lµ X = (0, 0, 0, 4, 2, 3, 6). 99 Ch­¬ng 5- Kü thuËt ph©n tÝch hÖ thèng... C¸c biÕn c¬ së ®Òu nhËn gi¸ trÞ d­¬ng vËy ph­¬ng ¸n 1 lµ ph­¬ng ¸n c¬ së chÊp nhËn ®­îc. Ph-¬ng ¸n 2: - Chän c¸c biÕn x 2, x5, x6, x7 lµ biÕn c¬ së, tøc lµ X = (0, x2, 0, 0,, x5, x6, x7). - Thay c¸c gi¸ trÞ cña X vµo hÖ ph­¬ng tr×nh rµng buéc (5-40) t×m ®­îc gi¸ trÞ c¸c biÕn lµ X = (0, 4, 0, 0, 2, 3, - 6). Trong c¸c biÕn c¬ së cã mét biÕn ...