Quy hoạch và quản lý nguồn nước phần 6

Tham khảo tài liệu quy hoạch và quản lý nguồn nước phần 6, khoa học tự nhiên, công nghệ môi trường phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Quy hoạch và quản lý nguồn nước phần 696 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 îi5.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. 97Ch¬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Ýnh5.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ÕntÝ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¸nsÏ 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 ®agi¸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ênglµ 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Ómcù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íc5.4.3.2. Kh¸i niÖm vÒ ph-¬ng ¸n c¬ së chÊp nhËn ®-îca. 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µngbué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 = 0ví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 + ...