Kỹ thuật và quản lý hệ thống nguồn nước ( Đại học Quốc gia Hà Nội ) - Chương 4

ứng dụng quy hoạch phi tuyến và quy hoạch động trong hệ thống nguồn nướcNhững ứng dụng ban đầu các kỹ thuật vận trù học vào các bài toán hệ thống nguồn nước chủ yếu dựa vào việc sử dụng các kỹ thuật quy hoạch tuyến tính và quy hoạch động. Việc sử dụng những kỹ thuật này để giải các bài toán hệ thống nguồn nước đã được ghi lại trong khá nhiều các tài liệu. Các đoạn chương trình quy hoạch tuyến tính được phổ biến rộng rãi, tuy nhiên quy hoạch động đòi hỏi mỗi đoạn...
Nội dung trích xuất từ tài liệu:
Kỹ thuật và quản lý hệ thống nguồn nước ( Đại học Quốc gia Hà Nội ) - Chương 4 CH¦¥NG 4 øng dông quy ho¹ch phi tuyÕn vµ quy ho¹ch ®éng trong hÖ thèng nguån níc Nh÷ng øng dông ban ®Çu c¸c kü thuËt vËn trï häc vµo c¸c bµi to¸n hÖthèng nguån níc chñ yÕu dùa vµo viÖc sö dông c¸c kü thuËt quy ho¹chtuyÕn tÝnh vµ quy ho¹ch ®éng. ViÖc sö dông nh÷ng kü thuËt nµy ®Ó gi¶i c¸cbµi to¸n hÖ thèng nguån níc ®· ®îc ghi l¹i trong kh¸ nhiÒu c¸c tµi liÖu.C¸c ®o¹n ch¬ng tr×nh quy ho¹ch tuyÕn tÝnh ®îc phæ biÕn réng r·i, tuynhiªn quy ho¹ch ®éng ®ßi hái mçi ®o¹n ch¬ng tr×nh riªng cho tõng øngdông. ViÖc sö dông quy ho¹ch phi tuyÕn trong gi¶i quyÕt c¸c bµi to¸n hÖthèng nguån níc cha ®îc phæ biÕn mÆc dï hÇu hÕt c¸c bµi to¸n yªu cÇulêi gi¶i trong thùc tÕ lµ nh÷ng bµi to¸n phi tuyÕn. Sù ph¸t triÓn gÇn ®©y cñanh÷ng kü thuËt quy ho¹ch phi tuyÕn míi vµ c¸c ®o¹n ch¬ng tr×nh quyho¹ch phi tuyÕn s½n cã ®· l«i cuèn nh÷ng øng dông míi cña quy ho¹ch phituyÕn vµo c¸c bµi to¸n hÖ thèng nguån níc. Hai phÇn ®Çu tiªn cña ch¬ngnµy tr×nh bµy nh÷ng c¬ së cña quy ho¹ch ®éng. Sau ®ã, tr×nh bµy c¸c bíctÝnh to¸n tèi u hãa phi tuyÕn kh«ng rµng buéc vµ c¸c bíc tÝnh to¸n tèi uhãa phi tuyÕn cã rµng buéc.4.1. Quy ho¹ch ®éng Quy ho¹ch ®éng (DP-Dynamic Programming) biÕn ®æi mét bµi to¸nquyÕt ®Þnh nèi tiÕp hay nhiÒu giai ®o¹n cã thÓ cã nhiÒu biÕn quyÕt ®Þnh liªnquan víi nhau thµnh mét chuçi nh÷ng bµi to¸n tõng giai ®o¹n ®¬n lÎ, mçibµi to¸n con ®¬n lÎ nµy chØ chøa mét hoÆc mét vµi biÕn. Nãi c¸ch kh¸c, küthuËt quy ho¹ch ®éng ph©n t¸ch mét bµi to¸n N quyÕt ®Þnh thµnh mét chuçiN bµi to¸n con quyÕt ®Þnh riªng lÎ nhng cã liªn quan víi nhau. Sù ph©nt¸ch nµy lµ rÊt h÷u dông trong viÖc gi¶i quyÕt nh÷ng bµi to¸n lín, phøc t¹pb»ng viÖc ph©n t¸ch mét bµi to¸n thµnh mét chuçi c¸c bµi to¸n con nhá h¬n129vµ sau ®ã kÕt hîp c¸c lêi gi¶i cña c¸c bµi to¸n nhá h¬n ®Ó nhËn ®îc lêigi¶i cña m« h×nh tæng thÓ. Lý do sö dông sù ph©n t¸ch nµy nh»m ®Ó gi¶imét bµi to¸n cã hiÖu qu¶ h¬n mµ cã thÓ tiÕt kiÖm ®¸ng kÓ khèi lîng tÝnhto¸n. Theo kinh nghiÖm, khèi lîng tÝnh to¸n t¨ng theo hµm mò cïng víi sèbiÕn nhng chØ t¨ng tuyÕn tÝnh theo sè c¸c bµi to¸n con. Ch¬ng nµy chñyÕu chØ ®Ò cËp ®Õn quy ho¹ch ®éng. Nh÷ng cuèn s¸ch ®Ò cËp ®Õn quyho¹ch ®éng lµ Dreyfus and Law (1977), Cooper and Cooper (1981) vµDenardo (1982). §Ó diÔn t¶ triÕt lý chung vÒ kü thuËt quy ho¹ch ®éng, xem xÐt bµi to¸nph©n bæ tµi nguyªn sau. Gi¶ sö r»ng c¸c nguån vèn ®îc ph©n bæ cho ba dù¸n thuû lîi A, B vµ C, nh»m tèi ®a hãa tæng thu nhËp dù tÝnh. Mçi dù ¸ngåm cã nh÷ng ph¬ng ¸n x©y dùng kh¸c nhau mµ ®ßi hái nh÷ng møc cÊpvèn kh¸c nhau vµ mang l¹i nh÷ng lîi nhuËn kh¸c nhau. Do sù h¹n chÕ vÒng©n s¸ch, tæng lîng vèn s½n cã cho toµn bé c¸c dù ¸n lµ kh«ng ®æi (®· Ên®Þnh). NÕu sè ph¬ng ¸n cho mçi dù ¸n lµ kh«ng qu¸ lín, th× cã thÓ liÖt kª®Çy ®ñ tÊt c¶ nh÷ng sù kÕt hîp cã thÓ nh÷ng ph¬ng ¸n cña dù ¸n ®Ó x¸c®Þnh sù kÕt hîp c¸c ph¬ng ¸n tèi u cho sù ph¸t triÓn dù ¸n tæng thÓ. TÊtnhiªn, híng tiÕp cËn liÖt kª ®Çy ®ñ nµy cã ba nhîc ®iÓm chÝnh: (1) nã sÏtrë nªn kh«ng kh¶ thi nÕu sè lîng nh÷ng sù kÕt hîp c¸c ph¬ng ¸n lµ lín;(2) kh«ng thÓ kiÓm ®Þnh ®îc tæ hîp hµnh ®éng tèi u cho tíi khi tÊt c¶ph¬ng ¸n kÕt hîp ®îc kiÓm tra, thËm chÝ tæ hîp nµy b¾t gÆp ngay tõnh÷ng tÝnh to¸n ban ®Çu; vµ (3) kh«ng thÓ lo¹i trõ ngay tõ ®Çu nh÷ng tæ hîpnghiÖm kh«ng kh¶ thi. Trong quy ho¹ch ®éng mçi ph¬ng ¸n cho mçi dù ¸n ®îc xem xÐtriªng mµ kh«ng bá qua sù phô thuéc lÉn nhau gi÷a c¸c dù ¸n th«ng quatæng ng©n s¸ch hiÖn cã. V× tæng lîng vèn bÞ h¹n chÕ, lîng vèn dµnh chomçi dù ¸n phô thuéc vµo sù ph©n bæ cho c¸c dù ¸n cßn l¹i. Víi bÊt kúnh÷ng lîng vèn ®îc Ên ®Þnh cho c¸c dù ¸n A vµ B, sù ph©n bæ cho dù ¸ncßn l¹i, C, ph¶i ®îc tiÕn hµnh ®Ó tèi u hãa lîi nhuËn cña nã ®èi víi kh¶n¨ng vèn cßn l¹i ®ã. Nãi c¸ch kh¸c, sù ph©n bæ tèi u cho dù ¸n C phôthuéc vµo lîng vèn dµnh cho C sau khi ®· ph©n bæ cho A vµ B. V× kh«ngbiÕt nh÷ng sù ph©n bæ tèi u cho c¸c dù ¸n A vµ B, sù ph©n bæ vµ lîi nhuËntèi u tõ dù ¸n C ph¶i ®îc x¸c ®Þnh cho tÊt c¶ c¸c lîng vèn cßn l¹i cã thÓ,sau khi nh÷ng sù ph©n bæ cho c¸c dù ¸n A vµ B ®îc tiÕn hµnh. H¬n n÷avíi bÊt cø lîng vèn nµo ®îc ph©n bæ cho dù ¸n A, nh÷ng sù ph©n bæ chodù ¸n B vµ C ph¶i ®îc lµm mét c¸ch tèi u ®èi víi lîng vèn cßn l¹i saukhi ®· ph©n bæ cho dù ¸n A. §Ó t×m ®îc sù ph©n bæ tèi u cho dù ¸n B tat×m sù ph©n bæ lµm tèi ®a hãa lîi nhuËn tõ dù ¸n B cïng víi lîi nhuËn tèiu tõ dù ¸n C. Sù ph©n bæ nµy lµ mét hµm cña c¸c lîng vèn cßn l¹i tõ sùph©n bæ cho dù ¸n B. Cuèi cïng, sù ph©n bæ tèi u cho dù ¸n A ®îc x¸c®Þnh ®Ó tèi ®a lîi nhuËn tõ dù ¸n A céng víi lîi nhuËn tèi u kÕt hîp cña dù 130¸n B vµ C, nh mét hµm cña c¸c lîng vèn cßn l¹i sau khi ph ...