Ứng dụng quy hoạch phi tuyến và quy hoạch đông trong hê thống nguồn nước

129 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¹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 ch­¬ng tr×nh riªng cho tõng øng dô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 ch­a ®­îc phæ biÕn mÆc dï hÇu hÕt c¸c bµi to¸n yªu cÇu lê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ña nh÷ng kü thuËt quy ho¹ch phi tuyÕn míi vµ c¸c ®o¹n ch­¬ng tr×nh quy ho¹ch phi tuyÕn s½n cã ®· l«i cuèn nh÷ng øng dông míi cña quy ho¹ch phi tuyÕ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­¬ng nµy tr×nh bµy nh÷ng c¬ së cña quy ho¹ch ®éng. Sau ®ã, tr×nh bµy c¸c b­íc tÝ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 ­u hã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¸n quyÕt ®Þnh nèi tiÕp hay nhiÒu giai ®o¹n cã thÓ cã nhiÒu biÕn quyÕt ®Þnh liªn quan víi nhau thµnh mét chuçi nh÷ng bµi to¸n tõng giai ®o¹n ®¬n lÎ, mçi bµ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çi N bµi to¸n con quyÕt ®Þnh riªng lÎ nh­ng cã liªn quan víi nhau. Sù ph©n t¸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¹p b»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¬n 130 vµ 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êi gi¶i cña m« h×nh tæng thÓ. Lý do sö dông sù ph©n t¸ch nµy nh»m ®Ó gi¶i mé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Ýnh to¸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 nh­ng 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 quy ho¹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¸n ph©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ù ¸n gåm cã nh÷ng ph­¬ng ¸n x©y dùng kh¸c nhau mµ ®ßi hái nh÷ng møc cÊp vè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Êt nhiª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îp nghiÖm kh«ng kh¶ thi. Trong quy ho¹ch ®éng mçi ph­¬ng ¸n cho mçi dù ¸n ®­îc xem xÐt riªng mµ kh«ng bá qua sù phô thuéc lÉn nhau gi÷a c¸c dù ¸n th«ng qua tæ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 cho mç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ù ¸n cß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«ng biÕ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Ën tè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÷a víi bÊt cø l­îng vèn nµo ®­îc ph©n bæ cho dù ¸n A, nh÷ng sù ph©n bæ cho dù ¸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 sau khi ®· ph©n bæ cho dù ¸n A. §Ó t×m ®­îc sù ph©n bæ tèi ­u cho dù ¸n B ta t×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èi ­u 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ù 131 ¸n B vµ C, nh­ mét hµm cña c¸c l­îng vèn cßn l¹i sau khi ph©n bæ cho dù ¸n A. Trong thùc tÕ, nh÷ng l­îng vèn ®­îc ph©n bæ ®ång thêi cho c¶ ba dù ¸n nµy. Sù ph©n bæ theo mét chuçi thø tù lµ mét ®éng t¸c vÒ mÆt to¸n häc cho phÐp ta tiÕn hµnh c¸c quyÕt ®Þnh kÕ tiÕp nhau. Quy ho¹ch ®éng cã thÓ kh¾c phôc ®­îc nh÷ng h¹n chÕ cña ph­¬ng ph¸p liÖt kª ®Çy ®ñ b»ng viÖc sö dông c¸c kh¸i niÖm sau: 1. Bµi to¸n ®­îc t¸ch ra thµnh c¸c bµi to¸n con vµ ph­¬ng ¸n tèi ­u ®­îc lùa chän cho mçi bµi to¸n con theo mét chuçi tr×nh tù ®Ó kh«ng bao giê cÇn liÖt kª tÊt c¶ nh÷ng ph­¬ng ¸n vÒ tr­íc cña bµi to¸n. 2. Bëi v× tèi ­u hãa ®­îc ¸p dông cho tõng bµi to¸n con, nh÷ng ph­¬ng ¸n kh«ng tèi ­u sÏ tù ®éng bÞ lo¹i bá. 3. C¸c bµi to¸n con cÇn ®­îc kÕt nèi víi nhau theo mét c¸ch nhÊt ®Þnh ®Ó kh«ng bao giê cã thÓ tèi ­u hãa trªn nh÷ng ph­¬ng ¸n kh«ng kh¶ thi. 4.1.1. C¸c thµnh phÇn cña m« h×nh quy ho¹ch ®éng. VÝ dô ph©n bæ l­îng vèn cho dù ¸n n­íc võa ®­îc m« t¶ cã thÓ ®­îc m« h×nh hãa b»ng to¸n häc lµ: 1 1 iMN ij ij i j Max r x    (4.1.1a) víi gi¶ thiÕt lµ: 1 1 iMN ij ij i j c x F    (4.1.1b) 1 1, 1,2,3,... iM ij j x i N    víi (4.1.1c) TÊt c¶ xij = 0 hoÆc 1 (4.1.1d) Trong ®ã ijr lµ lîi nhuËn cã thÓ sinh ra tõ ph­¬ng ¸n j cña dù ¸n i, ijc lµ yªu cÇu cÊp vèn cho ph­¬ng ¸n j cña dù ¸n i, ijx lµ mét biÕn quyÕt ®Þnh mµ cã thÓ lÊy hoÆc b»ng 0 hoÆc b»ng 1, b»ng 0 khi ph­¬ng ¸n j cña dù ¸n i kh«ng ®­îc lùa chän vµ b»ng 1 khi ph­¬ng ph­¬ng ¸n j cña dù ¸n i ®­îc lùa chän. F lµ tæng l­îng vèn giµnh cho dù ¸n nµy, N lµ tæng sè l­îng c¸c dù ¸n ®­îc xem xÐt, vµ Mi lµ tæng sè c¸c ph­¬ng ¸n cña dù ¸n i. TËp hîp thø hai vÒ c¸c rµng buéc biÓu thÞ r»ng kh«ng ph¶i tÊt c¶ c¸c dù ¸n xÐt ®Õn ph¶i ®­îc cÊp vèn. H¬n n÷a, c¸c ph­¬ng ¸n cña mçi dù ¸n lµ xung kh¾c víi nhau, tøc lµ chØ mét ph­¬ng ¸n trong mçi dù ¸n cã thÓ ®­îc chän. 132 H×nh 4.1.1 BiÓu thÞ thø tù cña chuçi c¸c bµi to¸n quy ho¹ch ®éng. Theo th¶o luËn chung vÒ h­íng tiÕp cËn gi¶i quyÕt quy ho¹ch ®éng, m« h×nh quy ho¹ch to¸n häc trªn cã thÓ ®­îc m« t¶ nh­ trong h×nh 4.1.1. Theo h×nh 4.1.1, c¸c phÇn tö vµ c¸c ng«n tõ c¬ b¶n trong sù thiÕt lËp c¸c bµi to¸n quy ho¹ch ®éng nh­ sau: 1. C¸c giai ®o¹n (n) lµ c¸c ®iÓm cña bµi to¸n mµ c¸c quyÕt ®Þnh ®­îc lùa chän. Trong vÝ dô ph©n bæ l­îng vèn, mçi dù ¸n ®Æc tr­ng cho mét giai ®o¹n trong m« h×nh quy ho¹ch ®éng. NÕu mét bµi to¸n ra quyÕt ®Þnh cã thÓ ®­îc ph©n t¸ch thµnh N bµi to¸n con, khi chuyÓn sang bµi to¸n quy ho¹ch ®éng sÏ cã N giai ®o¹n. 2. C¸c biÕn quyÕt ®Þnh (dn) lµ c¸c tæ hîp hµnh ®éng ®­îc tiÕn hµnh trong mçi giai ®o¹n. QuyÕt ®Þnh trong vÝ dô ph©n bæ l­îng vèn dù ¸n lµ ph­¬ng ¸n ®­îc lùa chän trong dù ¸n. Sè c¸c biÕn quyÕt ®Þnh, dn, trong mçi giai ®o¹n kh«ng nhÊt thiÕt b»ng 1. 3. C¸c biÕn tr¹ng th¸i (Sn) lµ c¸c biÕn diÔn t¶ tr¹ng th¸i cña mét hÖ thèng t¹i giai ®o¹n n bÊt kú. Mét biÕn tr¹ng th¸i cã thÓ lµ rêi r¹c hoÆc liªn tôc, h¹n ®Þnh hoÆc kh«ng h¹n ®Þnh. Trong h×nh 4.1.1, ë giai ®o¹n n bÊt kú, cã c¸c tr¹ng th¸i ®Çu vµo, Sn, vµ c¸c tr¹ng th¸i ®Çu ra, Sn+1. C¸c biÕn tr¹ng th¸i cña hÖ thèng trong mét m« h×nh quy ho¹ch ®éng cã chøc n¨ng liªn kÕt c¸c giai ®o¹n kÕ tiÕp sao cho khi mçi giai ®o¹n ®­îc tèi ­u hãa riªng biÖt quyÕt ®Þnh thu ®­îc tù ®éng kh¶ thi cho toµn bé bµi to¸n. H¬n n÷a, nã cho phÐp ta ra nh÷ng quyÕt ®Þnh tèi ­u cho c¸c giai ®o¹n cßn l¹i mµ kh«ng cÇn ph¶i kiÓm tra ¶nh h­ëng cña c¸c quyÕt ®Þnh trong t­¬ng lai tíi c¸c quyÕt ®Þnh ®· ra tr­íc ®Êy. 4. Lîi nhuËn giai ®o¹n (rn) lµ mét chØ sè ®o tÝnh hiÖu qu¶ cña quyÕt ®Þnh lµm trong mçi giai ®o¹n. Nã lµ mét hµm cña tr¹ng th¸i ®Çu vµo, tr¹ng th¸i ®Çu ra vµ c¸c biÕn quyÕt ®Þnh cña mét giai ®o¹n nhÊt ®Þnh. Tøc lµ: rn=r(Sn, Sn+1, dn). 5. PhÐp biÕn ®æi tr¹ng th¸i hay phÐp biÕn ®æi giai ®o¹n (tn) lµ mét phÐp biÕn ®æi ®¬n trÞ biÓu thÞ mèi quan hÖ gi÷a tr¹ng th¸i ®Çu vµo, tr¹ng th¸i ®Çu ra, vµ quyÕt ®Þnh. Nãi chung, th«ng qua phÐp biÕn ®æi tr¹ng th¸i nµy, ®Çu ra t¹i mét 133 B¶ng 4.1.1 Chi phÝ vµ lîi nhuËn cña c¸c ph­¬ng ¸n trong VÝ dô 4.1.1 Dù ¸n A Dù ¸n B Dù ¸n C Ph­¬ng ¸n Chi phÝ cA (triÖu ®«) Lîi nhuËn rA (triÖu ®«) Chi phÝ cA (triÖu ®«) Lîi nhuËn rA (triÖu ®«) Chi phÝ cA (triÖu ®«) Lîi nhuËn rA (triÖu ®«) 1 2 3 1 2 3 5 6 8 2 3 4 8 9 12 1 3 - 3 5 - giai ®o¹n n bÊt kú cã thÓ ®­îc biÓu thÞ b»ng mét hµm cña tr¹ng th¸i ®Çu vµo vµ biÕn quyÕt ®Þnh nh­ sau: Sn+1=tn(Sn, dn) (4.1.2) §Ó minh häa thuËt gi¶i ®¹i sè cña h­íng tiÕp cËn quy ho¹ch ®éng trong tèi ­u hãa mét bµi to¸n, bµi to¸n ph©n bæ vèn dù ¸n ®­îc gi¶i trong vÝ dô sau. VÝ dô 4.1.1. B¶ng 4.1.1. gåm vèn cÇn thiÕt (triÖu ®« la) cho mçi ph­¬ng ¸n vµ ri biÓu thÞ lîi nhuËn (triÖu ®« la) mµ cã thÓ ®­îc sinh ra do mçi dù ¸n. Tæng ng©n s¸ch x©y dùng lµ 7 triÖu ®« la. Gi¶ sö r»ng tÊt c¶ c¸c dù ¸n ®ang xÐt ph¶i ®­îc thùc thi. X¸c ®Þnh tæ hîp tèi ­u c¸c ph­¬ng ¸n ®Ó tèi ®a hãa lîi nhuËn tæng céng. Lêi gi¶i. C¸c yÕu tè c¬ b¶n cho m« h×nh quy ho¹ch ®éng ®­îc ®Þnh nghÜa nh­ sau: 1. Giai ®o¹n (n): mçi dù ¸n biÓu thÞ mét giai ®o¹n víi n = A, B vµ C. 2. BiÕn tr¹ng th¸i (Sn): biÕn tr¹ng th¸i t¹i mçi giai ®o¹n lµ tËp hîp c¸c ph­¬ng ¸n ®­îc xÐt. 3. BiÕn quyÕt ®Þnh (dn): biÕn quyÕt ®Þnh lµ ph­¬ng ¸n ®­îc chän cho mçi giai ®o¹n (dù ¸n). 4. Lîi nhuËn giai ®o¹n (rn): lîi nhuËn ®­îc sinh ra tõ ph­¬ng ¸n ®· chän. 5. Hµm chuyÓn ®æi tr¹ng th¸i (tn): Sn = dn víi n = C vµ Sn+1 = dn víi n = A vµ B. Theo d¹ng gi¶n ®å, bµi to¸n nµy cã thÓ ®­îc miªu t¶ nh­ trong h×nh 4.1.2a d­íi d¹ng mét bµi to¸n chuçi quyÕt ®Þnh. Mét c¸ch râ rµng h¬n, hÖ thèng nµy cã thÓ ®­îc H×nh 4.1.2a Sù biÓu thÞ thµnh chuçi cña bµi to¸n vÝ dô ph©n bæ ng©n s¸ch. 134 H×nh 4.1.2b BiÓu thÞ m¹ng l­íi cña vÝ dô ph©n bæ ng©n s¸ch sö dông c¸c ph­¬ng ¸n nh­ lµ c¸c biÕn tr¹ng th¸i. më réng cho mét sù biÓu thÞ m¹ng l­íi nh­ ®­îc chØ ra trong h×nh 4.1.2b khi chØ ra tr¹ng th¸i kh¶ thi (c¸c ph­¬ng ¸n) trong mçi giai ®o¹n (dù ¸n). Gi¶ sö r»ng chuçi c¸c quyÕt ®Þnh theo thø tù dù ¸n ®­îc chØ ra trong h×nh 4.1.2a; ph©n tÝch nµy cã thÓ ®­îc tiÕn hµnh theo tr×nh tù ng­îc l¹i b»ng viÖc b¾t ®Çu víi dù ¸n cuèi cïng (tøc lµ dù ¸n C). Thø tù cña c¸c dù ¸n lµ kh«ng quan träng trong vÝ dô nµy. ThuËt to¸n ®Ö quy b¾t ®Çu víi giai ®o¹n n = C, cã hai tr¹ng th¸i (hay ph­¬ng ¸n) kh¶ thi nh­ ®­îc chØ ra trong h×nh 4.1.2b. V× ®©y lµ tr¹ng th¸i cuèi cïng, kh«ng liªn quan ®Õn sù tèi ­u hãa nµo. Nãi c¸ch kh¸c, quyÕt ®Þnh tèi ­u cho dù ¸n C lµ ** CC Sd  bëi v× sù tèi ­u hãa t­¬ng øng cã thÓ ®­îc ph¸t biÓu lµ Max fC(SC) = rC(dC = SC) ë d¹ng b¶ng, c¸c tÝnh to¸n cho giai ®o¹n nµy ®­îc chØ ra trong B¶ng 4.1.2(a). Lïi l¹i mét giai ®o¹n ®Ó xem xÐt dù ¸n B. Víi mçi tr¹ng th¸i kh¶ thi ë giai ®o¹n n = B, môc ®Ých lµ ®Ó x¸c ®Þnh sù kÕt nèi tèt nhÊt (d­íi d¹ng lîi nhuËn ®­îc tÝch lòy cho tíi dù ¸n B) cho tÊt c¶ c¸c tr¹ng th¸i kh¶ thi trong c¸c giai ®o¹n ngay sau (chØ cã giai ®o¹n C ë thêi ®iÓm hiÖn t¹i). Bµi to¸n tèi ­u hãa lµ Max    *( )B B B B C Bf S r S f d  Nh÷ng tÝnh to¸n ®Ó x¸c ®Þnh c¸c kÕt nèi tèi ­u cho mçi tr¹ng th¸i kh¶ thi trong dù ¸n B ®­îc ®­a ra trong B¶ng 4.1.2(b). Chó ý r»ng bµi to¸n nµy lµ mét chuçi lùa chän c¸c ph­¬ng ¸n víi rµng buéc vÒ ng©n s¸ch. CÇn ph¶i theo dâi vµ kiÓm tra c¸c phÝ tæn tÝch lòy khi qu¸ tr×nh tèi ­u hãa chuyÓn tõ mét giai ®o¹n nµy sang giai ®o¹n kÕ tiÕp. Trong B¶ng 4.1.2(b) víi mçi tr¹ng th¸i kh¶ thi cña dù ¸n B, ®ã lµ, SB = (ph­¬ng ¸n 1, ph­¬ng ¸n 2, ph­¬ng ¸n 3), ®iÒu ®ã t­¬ng øng hai quyÕt ®Þnh cã thÓ víi c¸c tr¹ng th¸i trong giai ®o¹n kÕ tiÕp (dù ¸n C), dC = SC = (ph­¬ng ¸n 1, ph­¬ng ¸n 2). §Ó gi¶i thÝch nh÷ng tÝnh to¸n cã liªn quan trong B¶ng 4.1.2(b) xÐt dßng cuèi cïng t­¬ng øng víi SB = ph­¬ng ¸n 3. Lîi nhuËn tÝch lòy g¾n liÒn víi dC = ph­¬ng ¸n 1 lµ 12 triÖu ®« la + 3 triÖu ®« la = 15 triÖu ®« la trong ®ã sè ®Çu tiªn (12 triÖu ®« la) lµ lîi nhuËn sinh ra tõ sù lùa chän ph­¬ng ¸n 3 cho dù ¸n B vµ sè thø hai (3 triÖu ®« la) do sù lùa chän ph­¬ng ¸n 1 cho dù ¸n C nh­ ®· ®­îc chØ ra trong B¶ng 4.1.2(a). Chi phÝ tÝch lòy t­¬ng øng víi sù kÕt nèi c¸c tr¹ng th¸i gi÷a c¸c dù ¸n B vµ C nµy (tøc lµ, SB = ph­¬ng ¸n 3 vµ SC = ph­¬ng ¸n 1) lµ 4 triÖu ®« + 1 triÖu ®« = 5 triÖu ®«, lµ kh¶ thi trong vßng h¹n chÕ ng©n s¸ch lµ 7 triÖu ®«. Víi chó ý tíi SB = ph­¬ng ¸n 3 vµ dB = SC = ph­¬ng ¸n 2, lîi nhuËn tÝch lòy lµ 17 triÖu ®«, lín h¬n quyÕt ®Þnh ban ®Çu lµ 15 triÖu ®«; tuy nhiªn, chi phÝ tÝch lòy lµ 7 triÖu ®« sö dông hÕt toµn bé ng©n s¸ch vµ kh«ng cßn kinh phÝ cho dù ¸n A. §iÒu nµy vi ph¹m rµng buéc yªu cÇu r»ng tÊt c¶ c¸c dù ¸n ph¶i ®­îc thùc thi. V× vËy, quyÕt ®Þnh dB = SC = ph­¬ng ¸n 2 lµ kh«ng kh¶ thi vµ cÇn ph¶i lo¹i bá. Hai cét cuèi cïng cña B¶ng 4.1.2(b) ghi vµo lîi nhuËn tÝch lòy tèi ­u vµ quyÕt ®Þnh tèi ­u øng víi mçi tr¹ng th¸i kh¶ thi cho dù ¸n B. Nh÷ng sù nèi kÕt tèi ­u cho mçi tr¹ng th¸i kh¶ thi trong tõng giai ®o¹n tíi giai ®o¹n kÕ tiÕp ®­îc ®¸nh dÊu bëi c¸c khung ch÷ nhËt trong B¶ng 4.1.2b. 135 Khi ®· kÕt thóc ph©n bæ dù ¸n B, ph©n tÝch ®­îc tiÕn hµnh theo chiÓu ng­îc l¹i ®Ó xem xÐt dù ¸n A. Gi¶i ph¸p tèi ­u cho dù ¸n A lµ ph­¬ng ¸n 3, cã lîi nhuËn tæng céng lµ 21 triÖu ®« la cho ba dù ¸n nµy. Sö dông cïng mét qu¸ tr×nh tÝnh nh­ ®· dïng cho dù ¸n B, b¶ng tÝnh to¸n cho dù ¸n A ®­îc chØ ra trong B¶ng 4.1.2(c). KiÓm tra cét cuèi cïng trong B¶ng 4.1.2(c) t­¬ng øng víi quyÕt ®Þnh tèi ­u * Ad , ng­êi ta thÊy r»ng tæng l­îng vèn b»ng 7 triÖu ®« ®­îc sö dông hÕt khi thùc hiÖn gi¶i ph¸p tèi ­u. B­íc cuèi cïng cña kü thuËt quy ho¹ch ®éng lµ “b­íc t×m ng­îc” qua ba giai ®o¹n theo thø tù ng­îc l¹i, tøc lµ A  B  C dïng b¶ng tÝnh to¸n t­¬ng øng. Chó ý r»ng, tõ B¶ng 4.1.2(c), tæng lîi nhuËn cã thÓ ®¹t ®­îc lín nhÊt lµ 21 triÖu ®« øng víi SA = ph­¬ng ¸n 2. Víi SA = ph­¬ng ¸n 2, quyÕt ®Þnh tèi ­u lµ * A Bd S = ph­¬ng ¸n 3 nh­ ®· ®­îc khoanh trßn. TiÕp tôc t×m ng­îc trong B¶ng 4.1.2(b), víi SB = ph­¬ng ¸n 3, quyÕt ®Þnh tèi ­u t­¬ng øng lµ * B Cd S = ph­¬ng ¸n 1. §Õn ®©y th× hoµn thµnh b­íc t×m ng­îc chØ ra sù lùa chän tèi ­u cña c¸c ph­¬ng ¸n lµ * * * A B C( d ,d ,d )  ( ph­¬ng ¸n 2, ph­¬ng ¸n 3, ph­¬ng ¸n 1) vµ tæng lîi nhuËn tèi ­u (lín nhÊt) lµ 21 triÖu ®« la. B­íc t×m ng­îc ®­îc minh häa trong h×nh 4.1.2b chØ ra bëi c¸c ®­êng nÐt ®Ëm. Bµi to¸n nµy còng cã thÓ ®­îc gi¶i b»ng viÖc x¸c ®Þnh biÕn tr¹ng th¸i lµ l­îng ng©n s¸ch s½n cã (Bµi to¸n 4.1.2). 4.1.2. C¸c ®Æc tr­ng vÒ thuËt gi¶i cña quy ho¹ch ®éng Tõ vÝ dô 4.1.1, c¸c ®Æc tÝnh c¬ b¶n ®Æc tr­ng cho tÊt c¶ c¸c bµi to¸n quy ho¹ch ®éng lµ nh­ sau: 1. Bµi to¸n ®­îc chia ra thµnh c¸c giai ®o¹n, víi c¸c biÕn quyÕt ®Þnh t¹i mçi giai ®o¹n. 2. Mçi giai ®o¹n cã mét sè tr¹ng th¸i g¾n liÒn víi nã. 3. ¶nh h­ëng cña quyÕt ®Þnh ®­îc lùa chän t¹i mçi giai ®o¹n lµ ®Ó t¹o ra mét lîi nhuËn, dùa trªn hµm lîi nhuËn cña giai ®o¹n ®ã, vµ ®Ó biÕn ®æi biÕn tr¹ng th¸i hiÖn t¹i thµnh biÕn tr¹ng th¸i cho giai ®o¹n kÕ tiÕp, th«ng qua hµm chuyÓn ®æi tr¹ng th¸i. 4. Víi tr¹ng th¸i hiÖn t¹i, mét chÝnh s¸ch tèi ­u cho c¸c giai ®o¹n cßn l¹i lµ ®éc lËp víi chÝnh s¸ch ®· ®­îc chÊp nhËn trong c¸c giai ®o¹n tr­íc. §©y gäi lµ nguyªn lý Bellman vÒ tÝnh tèi ­u, ®­îc xem nh­ lµ cèt lâi cña quy ho¹ch ®éng. 5. Lêi gi¶i b¾t ®Çu b»ng viÖc t×m quyÕt ®Þnh tèi ­u cho mçi tr¹ng th¸i cã thÓ trong B¶ng 4.1.2(a) TÝnh to¸n quy ho¹ch ®éng cho dù ¸n C SC Lîi nhuËn tèi ­u * Cf (triÖu ®« la) QuyÕt ®Þnh tèi ­u * Cd Ph­¬ng ¸n 1 3 (1)+ Ph­¬ng ¸n 1 (chi phÝ = 1 triÖu ®« la) Ph­¬ng ¸n 2 5 (3) Ph­¬ng ¸n 2 (chi phÝ = 3 triÖu ®« la) DÊu + trong () lµ chi phÝ tÝch lòy cho c¸c dù ¸n C. 136 B¶ng 4.1.2(b) TÝnh to¸n quy ho¹ch ®éng cho dù ¸n B * B B B B B C Bf (S ,d ) = r (S )+ f (d ) dB = SC SB Ph­¬ng ¸n 1 Ph­¬ng ¸n 2 * Bf () * Bd Ph­¬ng ¸n 1 8+3=11 (2+1=3)+ 8+5=13 (2+3=5) 13 PA - 2 ($5) Ph­¬ng ¸n 2 9+3=12 (3+1=4) 9+5=14 (3+3=6) 14 PA - 2 ($6) Ph­¬ng ¸n 3 12+3=15 (4+1=5) 12+5=17 (4+3=7, kh«ng kh¶ thi)# 15 DÊu + trong () lµ chi phÝ tÝch lòy cho c¸c dù ¸n C #kh«ng kh¶ thi, quyÕt ®Þnh nµy sö dông tÊt c¶ $7 triÖu ng©n s¸ch kh«ng dù tr÷ cho dù ¸n A. giai ®o¹n cuèi cïng (gäi lµ ®Ö quy lïi) hay trong giai ®o¹n ®Çu tiªn (gäi lµ ®Ö quy tiÕn). Mét thuËt gi¶i tiÕn b¾t ®Çu tÝnh to¸n tõ giai ®o¹n ®Çu tiªn cho tíi giai ®o¹n cuèi cïng cßn mét thuËt gi¶i lïi b¾t ®Çu tÝnh to¸n tõ giai ®o¹n cuèi cïng tíi giai ®o¹n ®Çu tiªn. 6. Mét mèi quan hÖ ®Ö quy x¸c ®Þnh chÝnh s¸ch tèi ­u cho mçi tr¹ng th¸i ë giai ®o¹n n bÊt kú cã thÓ ®­îc x©y dùng khi cho tr­íc chÝnh s¸ch tèi ­u cho mçi tr¹ng th¸i ë giai ®o¹n tiÕp theo, n+1. Ph­¬ng tr×nh ®Ö quy lïi nµy, theo h×nh 4.1.1, cã thÓ ®­îc viÕt lµ:     * * 1 1 * 1 ( ) . ( . ) ( ) . ( . ) [ ( , )] n n n n n n n n n d n n n n n nn d f S opt r S d f S opt r S d f t S d      o o (4.1.3) trong ®ã obiÓu thÞ mét to¸n tö ®¹i sè mµ cã thÓ lµ +, -,  , hoÆc bÊt kú miÔn lµ phï hîp víi bµi to¸n. Ph­¬ng tr×nh ®Ö quy cho mét thuËt gi¶i tiÕn ®­îc ph¸t biÓu lµ:  * * 1 1( ) . ( , ) ( ) n n n n n n n n d f S opt r S d f S  o (4.1.4) Chó ý r»ng, trong vÝ dô nµy, nh÷ng tÝnh to¸n cho giai ®o¹n 3 (dù ¸n C) kh«ng liªn quan ®Õn sè h¹ng fn+1(Sn+1) trong ph­¬ng tr×nh ®Ö quy 4.1.3. Nãi chung ®©y sÏ lµ tr­êng hîp sö dông tèi ­u hãa quy ho¹ch ®éng lïi. Do ®ã, ph­¬ng tr×nh ®Ö quy cho kü thuËt quy ho¹ch ®éng lïi cã thÓ ®­îc viÕt lµ: * * 1 1 .[ ( , )], ( ) .[ ( , ) ( )], n n n n n d n n n n n n n d opt r S d S opt r S d f S f         o víi = (4.1.5 ) víi = 1 ®Õn - 1 (4.1.5 ) n N a n N b B¶ng 4.1.2(c) TÝnh to¸n quy ho¹ch ®éng cho dù ¸n A SA * A A A A A B Af (S ,d ) = r (S )+ f (d ) * Af () * Ad PA-1 ($5) 137 dA = SB Ph­¬ng ¸n 1 Ph­¬ng ¸n 2 Ph­¬ng ¸n 3 PA - 1 5+13=8 (1+5=6)+ 5+14=19 (1+6=7) 5+15=20 (1+5=6) 20 PA - 3 ($6) PA - 2 6+13=19 (2+5=7) 6+14=20 (2+6=8, kh«ng kh¶ thi) 6+15=21 (2+5=7) 21 PA - 3 ($7) PA - 3 8+13=21 (3+5=8, kh«ng kh¶ thi) 8+14=22 (3+6=9, kh«ng kh¶ thi) *+15+23 (3+5=8, kh«ng kh¶ thi) - - - DÊu + trong () lµ chi phÝ tÝch lòy cho c¸c dù ¸n A, B vµ C. VÝ dô 4.1.2. X¸c ®Þnh c¸c ph­¬ng tr×nh ®Ö quy lïi cho VÝ dô 4.1.1. Lêi gi¶i. Víi giai ®o¹n thø ba (n=3)    *3 3 C C d f S Max r ; víi giai ®o¹n thø hai    *2 2 B B C d f S Max r f  ; vµ víi giai ®o¹n 1    *1 1 A A B d f S Max r f  . VÝ dô 4.1.3. C¸c dßng ch¶y tíi mét hå cã tæng dung tÝch b»ng 4 ®¬n vÞ n­íc lµ 2, 1, 2 vµ 1 ®¬n vÞ t­¬ng øng víi bèn mïa trong n¨m. §Ó tiÖn lîi, l­îng n­íc chØ ®­îc tÝnh b»ng c¸c ®¬n vÞ nguyªn. Do ®ã, l­îng x¶ ra tõ hå ®Ó cung cÊp cho mét thµnh phè vµ n«ng nghiÖp ®­îc b¸n víi gi¸ lµ $2000 cho ®¬n vÞ ®Çu tiªn, $1500 cho ®¬n vÞ thø hai, $1000 cho ®¬n vÞ thø ba, vµ $500 cho ®¬n vÞ thø t­. Khi hå chøa ®Çy n­íc vµ x¶ trµn 1 ®¬n vÞ n­íc, mét trËn lò nhá sÏ dÉn tíi thiÖt h¹i $1500, Khi x¶ trµn lªn tíi 2 ®¬n vÞ, mét trËn lò lín sÏ g©y thiÖt h¹i $4000, X¸c ®Þnh chÝnh s¸ch vËn hµnh ®Ó lîi nhuËn hµng n¨m lín nhÊt b»ng quy ho¹ch ®éng sö dông thuËt gi¶i lïi, xÐt víi bÊt kú l­îng dù tr÷ nµo ë thêi ®iÓm cuèi n¨m. Lêi gi¶i. B­íc ®Çu tiªn lµ gi¶i thÝch hµm lîi nhuËn. Mét ®¬n vÞ x¶ ra tõ hå cã lîi nhuËn lµ $2000; 2 ®¬n vÞ x¶ cã lîi nhuËn lµ $2000+ $1500 = $3500; 3 ®¬n vÞ x¶ cã lîi nhuËn lµ $3500 + $1000 = $4500; 4 ®¬n vÞ x¶ cã lîi nhuËn lµ $4500 + $500 = $5000; 5 ®¬n vÞ x¶ (khi mµ hå chøa chØ cã dung tÝch lµ 4 ®¬n vÞ th× ®iÒu nµy cã nghÜa lµ hå chøa bÞ ®Çy vµ 1 ®¬n vÞ ph¶i x¶ trµn); lîi nhuËn sÏ lµ $5000 (4 ®¬n vÞ cÊp n­íc) - $1500 (1 ®¬n vÞ x¶ trµn) = $3500; vµ 6 ®¬n vÞ x¶ th× lîi nhuËn sÏ lµ $5000 -$4000 (2 ®¬n vÞ x¶ trµn) = $1000, Mçi mïa thÓ hiÖn mét giai ®o¹n nh­ trªn h×nh 4.1.3. BiÕn tr¹ng th¸i cho bµi to¸n vËn hµnh hå chøa nµy chÝnh lµ l­îng tr÷ trong hå, lµ l­îng tr÷ ban ®Çu hay ®Çu mïa Sn = STn vµ l­îng tr÷ kÕt thóc hay cuèi mïa 1 ~  nn STS ®èi víi mïa thø n. L­îng x¶ tõ hå chøa lµ biÕn quyÕt ®Þnh ®­îc ký hiÖu lµ dn = Rn ®èi víi mïa thø n. Hµm chuyÓn ®æi ®¬n gi¶n chÝnh lµ ph­¬ng tr×nh liªn tôc liªn hÖ l­îng tr÷ ®Çu thêi ®o¹n víi l­îng tr÷ cuèi thêi ®o¹n cña giai ®o¹n n: nnnn RQFSS  ~ trong ®ã QFn lµ dßng ch¶y ®Õn cho giai ®o¹n n. L­îng tr÷ cuèi cña mét giai ®o¹n (mïa) nµo ®ã sÏ lµ l­îng tr÷ ban ®Çu cho tr¹ng th¸i kÕ tiÕp, nghÜa lµ 1 ~  nn SS Ph­¬ng tr×nh ®Ö quy lïi quy ho¹ch ®éng cho vÝ dô nµy lµ:      [ * )],([ Max nnnn dSrMaxf C¸c b­íc tÝnh to¸n quy ho¹ch ®éng ®­îc tr×nh bµy ë c¸c b¶ng 4.1.3(a)-(d). Xem b¶ng 4.1.3(a) ®Ó theo dâi c¸c b­íc tÝnh to¸n cho giai ®o¹n 4. Cét ®Çu tiªn thÓ hiÖn l­îng tr÷ (tr¹ng th¸i) ban ®Çu cña mïa (giai ®o¹n) 4. Cét thø hai lµ gi¸ trÞ l­îng tr÷ ban ®Çu céng víi l­îng dßng ch¶y tíi hå QF4 = 1. N¨m cét tiÕp theo lµ linh hån cña tÝnh to¸n quy ho¹ch ®éng mµ ë ®ã c¸c ph­¬ng tr×nh ®Ö quy ®­îc 138 gi¶i. Mçi cét dµnh cho c¸c gi¸ trÞ cã thÓ cña l­îng tr÷ cuèi thêi ®o¹n 4 ~ S = 0, 1, 2, vµ 4. §èi víi giai ®o¹n 4, c¸c tÝnh to¸n lµ kh«ng cÇn thiÕt v× ph­¬ng tr×nh ®Ö quy lµ ),()( 4444 * 4 dSrSf  . VÝ dô nh­ nÕu l­îng tr÷ ban ®Çu S4 = 0 vµ l­îng tr÷ cuèi 04 ~ S cho ta l­îng x¶ R4 = 1. L­îng x¶ nµy ®­îc x¸c ®Þnh tõ viÖc gi¶i hµm chuyÓn ®æi tr¹ng th¸i cho R4 10104 ~ 444  SQFSR Víi l­îng x¶ lµ 1 ®¬n vÞ th× lîi nhuËn lµ $2000 do ®ã f4(S4)=r4(S4=0, d4=R4=1) = $2000, Mét c¸ch t­¬ng tù cho S4 = 1 vµ 04 ~ S , R4 = 1 + 1 - 0 = 2 vµ khi ®ã f4(S4)=r4(S4=1, d4=R4=2) = $3500, C¸c cét lîi nhuËn tèi ®a )( 4 * 4 Sf ®Þnh nghÜa c¸c gi¸ trÞ lîi nhuËn cùc ®¹i cho mçi l­îng tr÷ ban ®Çu cã xÐt ®Õn l­îng tr÷ cuèi. §iÒu nµy gièng nh­ viÖc xÐt mçi l­îng x¶ (quyÕt ®Þnh) cã thÓ ®èi víi l­îng tr÷ ban ®Çu. L­îng x¶ tèi ­u cho mçi l­îng tr÷ ban ®Çu ®­îc liÖt kª trong cét kÕ tiÕp vµ l­îng tr÷ cuçi tèi ­u ®­îc liÖt kª ë cét cuèi cïng. B¶ng 4.1.3(b) tr×nh bµy c¸c tÝnh to¸n quy ho¹ch ®éng cho giai ®o¹n (mïa) thø 3 víi l­îng dßng ch¶y tíi hå lµ 2 ®¬n vÞ. §Ó minh ho¹ quy tr×nh tÝnh to¸n xÐt tr­êng hîp S3= 0 vµ 03 ~ S . L­îng x¶ ®­îc thÓ hiÖn th«ng qua tæ hîp gi÷a l­îng tr÷ ban ®Çu vµ l­îng tr÷ cuèi lµ 20203 ~ 343  SQFSR , do vËy lîi nhuËn lµ r3(S3=0, d3=R3=2) = $3500, Tõ b¶ng 4.1.3(a) lîi nhuËn luü tÝch tèi ­u cho giai ®o¹n 4 lµ 2000$)0( 4 * 4 Sf ®èi víi 4 ~ 3 SS  . C¸c b­íc tÝnh to¸n ®­îc lÆp theo chiÒu ng­îc l¹i cho giai ®o¹n 2 (mïa 2) råi giai ®o¹n (mïa) 1 nh­ ®­îc tr×nh bµy lÇn l­ît t¹i c¸c b¶ng 4.1.3(c) vµ (d). 139 H×nh 4.1.3 Kh«ng gian tr¹ng th¸i vµ c¸c giai ®o¹n cho VÝ dô 4.1.3. Khi c¸c tÝnh to¸n quy ho¹ch ®éng cho giai ®o¹n 1 kÕt thóc, b­íc t×m ng­îc ®­îc tiÕn hµnh ®Ó t×m ra tËp hîp c¸c l­îng x¶ tèi ­u. XÐt c¸c tÝnh to¸n quy ho¹ch ®éng cho giai ®o¹n 1 ë b¶ng 4.1.3(d), lîi nhuËn lín nhÊt thu ®­îc tõ mçi l­îng tr÷ S1 lµ: $11000 víi S1 = 0, $12500 víi S1 = 1, $14000 víi S1 = 2, $15000 víi S1 = 3, vµ $16000 víi S1 = 4. Lîi nhuËn lín nhÊt nh­ vËy lµ $16000, Mét phÐp t×m ng­îc ®­îc tiÕn hµnh cho mçi l­îng tr÷ ban ®Çu. Víi môc ®Ých minh ho¹, phÐp t×m ng­îc ®­îc tiÕn hµnh ®èi víi tr­êng hîp lîi nhuËn cùc ®¹i b»ng $16000 t­¬ng øng víi S1 = 4. Trong tr­êng hîp nµy l­îng x¶ tèi ­u 2*1 d hoÆc 3 ®¬n vÞ vµ t­¬ng øng víi chóng lµ l­îng tr÷ cuèi thêi ®o¹n 41 ~ S hoÆc 3. XÐt trong b¶ng 4.1.3(c) víi 4 ~ 12  SS hoÆc 3 th× l­îng x¶ tèi ­u víi S2 = 3 lµ 2*2 d hoÆc 3 ®èi víi c¸c l­îng tr÷ cuèi cïng t­¬ng øng cña giai ®o¹n 2 22 ~ S hoÆc 1. §èi víi S2 = 4, l­îng x¶ tèi ­u 2 * 2 d hoÆc 3 t­¬ng øng víi l­îng tr÷ cuèi thêi ®o¹n 32 ~ S hoÆc 2. Do vËy 1 ~ 23  SS , 2 hoÆc 3. B©y giê ®i xÐt b¶ng 4.1.3(b) cho giai ®o¹n 3, c¸c l­îng x¶ tèi ­u lµ: víi S3 = 1, d2 = 2 vµ 1 * 3 ~ S ; víi S3 = 2, 2 * 3 d hoÆc 3 vµ 2 * 3 ~ S hoÆc 3; vµ víi S3 = 3, 3*3 d vµ 2 * 3 ~ S . C¸c l­îng tr÷ cuèi tèi ­u cña giai ®o¹n 3 lµ 1 * 3 ~ S hoÆc 2. Qu¸ tr×nh t×m ng­îc l¹i ®­îc tiÕp tôc ®Õn giai ®o¹n 4 trong b¶ng 4.1.3(a). Víi 1* 4 ~ 4  SS hoÆc 2 th× c¸c quyÕt ®Þnh tèi ­u t­¬ng øng 2*4 d hoÆc 3 ®Ó cho 0 * 4 S trong c¶ hai tr­êng hîp. Tãm l¹i: lîi nhuËn lín nhÊt trong bµi to¸n nµy cã thÓ b¾t ®Çu víi hå chøa lµ ®Çy n­íc vµo thêi ®iÓm b¾t ®Çu cña n¨m vµ x¶ hÕt vµo thêi ®iÓm cuèi n¨m. §iÒu nµy lµ hiÓn nhi