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

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:57

Thêm vào BST

Báo xấu

112
lượt xem 17
download

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

ứ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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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¹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 cha ®î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Î nhng 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 129
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 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 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ù 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©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µ: Mi N Max rij xij (4.1.1a) i 1 j 1 víi gi¶ thiÕt lµ: N Mi  cij xij  F (4.1.1b) i 1 j 1 Mi  xij  1, (4.1.1c) víi i  1, 2,3,...N j 1 TÊt c¶ xij = 0 hoÆc 1 (4.1.1d) Trong ®ã rij lµ lîi nhuËn cã thÓ sinh ra tõ ph¬ng ¸n j cña dù ¸n i, cij lµ yªu cÇu cÊp vèn cho ph¬ng ¸n j cña dù ¸n i, xij 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. 131
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 trng 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 132
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 Chi phÝ Lîi nhuËn C hi phÝ Lîi nhuËn Chi phÝ Lîi nhuËn Ph¬ng ¸n cA rA cA rA cA rA (triÖu ®«) (triÖu ®«) ( triÖu ®«) (triÖu ®«) (triÖu ®«) (triÖu ®«) 1 1 5 2 8 1 3 2 2 6 3 9 3 5 3 3 8 4 12 - - 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. 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. 5. 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. 133
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µ d C  S C 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 f B ( S B )  rB  S B   fC  d B  * 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. 134
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 d * , 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 A 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µ d *  S B = ph¬ng ¸n 3 nh ®· ®îc khoanh trßn. TiÕp tôc t×m ngîc trong A d *  S C = ph¬ng ¸n 1. §Õn B¶ng 4.1.2(b), víi SB = ph¬ng ¸n 3, quyÕt ®Þnh tèi u t¬ng øng lµ B ®©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µ ( d * ,d B ,dC )  ( * * A 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 trng 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 trng 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 Lîi nhuËn tèi u QuyÕt ®Þnh tèi u SC * * fC (triÖu ®« la) dC 3 Ph¬ng ¸n 1 P h¬ng ¸n 1 (chi phÝ = 1 triÖu ®« la) ( 1)+ 5 Ph¬ng ¸n 2 Ph¬ng ¸n 2 (chi phÝ = 3 triÖu ®« la) (3) DÊu + trong () lµ chi phÝ tÝch lòy cho c¸c dù ¸n C. 135
B¶ng 4.1.2(b) TÝnh to¸n quy ho¹ch ®éng cho dù ¸n B * f B (S B ,d B ) = rB (S B )+ f C (d B ) dB = S C * d* f B () P h¬ng ¸n 1 Ph¬ng ¸n 2 SB B Ph¬ng ¸n 1 PA - 2 8+3=11 8+5=13 ($5) 13 (2+1=3)+ (2+3=5) Ph¬ng ¸n 2 PA - 2 9+3=12 9+5=14 ($6) 14 (3+1=4) (3+3=6) Ph¬ng ¸n 3 PA-1 12+3=15 12+5=17 15 ($5) (4+3=7, kh«ng kh¶ thi)# ( 4+1=5) 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µ: f n* ( Sn )  opt .rn ( Sn .d n ) o f n*1 (Sn1 ) dn (4.1.3)  opt .rn (Sn .dn ) o f n*1[tn ( Sn , dn )] dn 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µ: f n* ( Sn )  opt .rn ( Sn , d n ) o f n*1 ( Sn1 ) (4.1.4) dn 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µ: opt .[rn (S n , d n )], víi n = N (4.1.5a)  dn * f ( Sn )   n * opt .[rn (S n , d n ) o f n 1 ( S n 1 )], víi n = 1 ®Õn N - 1 (4.1.5b)  dn B ¶ng 4.1.2(c) TÝnh to¸n quy ho¹ch ®éng cho dù ¸n A * * d* f A (S A ,d A ) = rA (S A )+ f B (d A ) f A () SA A 136
dA = S B P h¬ng ¸n 1 Ph¬ng ¸n 2 Ph¬ng ¸n 3 5+13=8 5+14=19 20 PA - 3 5+15=20 PA - 1 (1+5=6)+ (1+6=7) ($6) ( 1+5=6) 6+13=19 6+14=20 21 PA - 3 6+15=21 PA - 2 (2+5=7) (2+6=8, kh«ng kh¶ ($7) ( 2+5=7) thi) * 8+13=21 8+14=22 +15+23 - - PA - 3 (3+5=8, kh«ng kh¶ (3+6=9, kh«ng kh¶ (3+5=8, kh«ng kh¶ - thi) thi) 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. f3*  S 3   Max  rC  ; víi giai ®o¹n thø hai Lêi gi¶i. Víi giai ®o¹n thø ba (n=3) dC   ; vµ víi giai ®o¹n 1 f  S   Max  r  *  f B* . f 2  S 2   Max rB  f C 1 1 A dB dA 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 S n  STn 1 ®è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: ~ S n  S n  QFn  Rn 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µ ~ S n  S n1 Ph¬ng tr×nh ®Ö quy lïi quy ho¹ch ®éng cho vÝ dô nµy lµ:   * f n  Max[rn ( S n , d n )]   Max[ 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 137
~ S 4 = 0, 1, 2, vµ 4. §èi víi 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 * giai ®o¹n 4, c¸c tÝnh to¸n lµ kh«ng cÇn thiÕt v× ph¬ng tr×nh ®Ö quy lµ f 4 ( S 4 )  r4 ( S 4 , d 4 ) . VÝ ~ S4  0 dô nh nÕu lîng tr÷ ban ®Çu S4 = 0 vµ lîng tr÷ cuèi 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 ~ R4  S 4  QF4  S 4  0  1  0  1 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 ~ S 4  0 , R4 = 1 + 1 - 0 = 2 vµ khi ®ã f4(S4)=r4(S4=1, d4=R4=2) = $3500, t¬ng tù cho S4 = 1 vµ * C¸c cét lîi nhuËn tèi ®a f 4 ( S 4 ) ®Þ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 ~ S3  0 . Lî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µ 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µ ~ R3  S 4  QF3  S 3  0  2  0  2 , do vËy lîi nhuËn lµ r3(S3=0, d3=R3=2) = $3500, Tõ b¶ng ~ * S3  S 4 . C¸c 4.1.3(a) lîi nhuËn luü tÝch tèi u cho giai ®o¹n 4 lµ f 4 ( S 4  0)  $2000 ®èi víi 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). 138
H×nh 4.1.3 K h«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 d1  2 hoÆc 3 ®¬n vÞ vµ t¬ng øng víi chóng lµ lîng tr÷ cuèi thêi ~ ~ S1  4 hoÆc 3. XÐt trong b¶ng 4.1.3(c) víi S 2  S1  4 hoÆc 3 th× lîng x¶ tèi u víi S2 = ®o¹n ~ * S2  2 3 lµ d 2  2 hoÆc 3 ®èi víi c¸c lîng tr÷ cuèi cïng t¬ng øng cña giai ®o¹n 2 hoÆc 1. §èi ~ * S2  3 víi S2 = 4, lîng x¶ tèi u d 2  2 hoÆc 3 t¬ng øng víi lîng tr÷ cuèi thêi ®o¹n hoÆc 2. ~ Do vËy S 3  S 2  1 , 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µ S 3  1 ; víi S3 = 2, d 3  2 hoÆc 3 vµ S 3  2 hoÆc 3; vµ víi S3 = 3, ~* ~* * d 3  3 vµ S 3  2 . C¸c lîng tr÷ cuèi tèi u cña giai ®o¹n 3 lµ S 3  1 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 S 4  S *  1 hoÆc 2 th× c¸c quyÕt 4 * * ®Þnh tèi u t¬ng øng d 4  2 hoÆc 3 ®Ó cho S 4  0 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ªn trong vÝ dô ta ®ang xÐt. Tuy nhiªn nÕu xÐt theo quan ®iÓm vËn hµnh mét hå chøa thùc tÕ, chÝnh s¸ch vËn hµnh nµy kh«ng thÓ thùc thi. Qu¸ tr×nh t×m ngîc tèi u ®îc minh ho¹ cô thÓ h¬n trong h×nh 4.1.4 cïng víi c¸c lîng x¶ tèi u. MÆc dï quy ho¹ch ®éng mang nhiÒu u ®iÓm trong viÖc gi¶i c¸c bµi to¸n nguån níc, ®Æc biÖt lµ ®èi víi c¸c bµi to¸n ph©n tÝch c¸c qu¸ tr×nh nhiÒu giai ®o¹n, nã cã hai h¹n chÕ lµ yªu cÇu vÒ bé nhí m¸y tÝnh vµ thêi gian tÝnh to¸n lín. Hai h¹n chÕ nµy cã thÓ lµ kh¸ nghiªm träng trong hai trêng hîp: (1) khi sè c¸c biÕn tr¹ng th¸i lµ lín; vµ (2) khi quy ho¹ch ®éng ®îc ¸p dông theo ph¬ng ph¸p rêi r¹c ®Ó tÝnh to¸n cho mét kh«ng gian tr¹ng th¸i liªn tôc. VÊn ®Ò liªn quan ®Õn trêng hîp 2 lµ tån t¹i nhiÒu khã kh¨n trong viÖc t×m kiÕm nghiÖm tèi u thùc nÕu kh«ng t¨ng mét c¸ch ®¸ng kÓ sè c¸c kho¶ng rêi r¹c ho¸ trong kh«ng gian tr¹ng th¸i. Cïng víi nh÷ng tiÕn bé vÒ c«ng nghÖ m¸y tÝnh, nh÷ng nhîc ®iÓm nµy dÇn trë nªn Ýt nghiªm träng. Mét gia sè c¸c rêi r¹c ho¸ hay sè c¸c biÕn tr¹ng th¸i cã thÓ lµm t¨ng theo hµm mò sè c¸c tÝnh to¸n c¸c c«ng thøc ®Ö quy vµ bé nhí cho mçi giai ®o¹n. VÊn ®Ò t¨ng nhanh yªu cÇu vÒ bé nhí vµ thêi gian tÝnh g¾n víi c¸c bµi to¸n quy ho¹ch ®éng ®a biÕn tr¹ng th¸i nµy thêng ®îc ®Ò cËp tíi víi tªn gäi lêi nguyÒn cña sè chiÒu (vÊn ®Ò t¨ng theo quy luËt hµm mò khi t¨ng sè chiÒu trªn kh«ng gian tÝnh). 139
B ¶ng 4.1.3(a) TÝnh to¸n quy ho¹ch ®éng cho giai ®o¹n 4 cña VÝ dô 4.1.3 (a) Giai ®o¹n 4 - Mïa 4 Tæng Lîi nhuËn QuyÕt Lîng Lîi nhuËn f4(S4)=r4(S4,d4) Lîng lîng lín nhÊt ®Þnh (X¶) tr÷ cuèi tr÷ ban Lîng tr÷ cuèi S 4 tr÷ f 4*  S4  * * d 4 = R4 S4 ®Çu S4 S4 + QF4 0 1 2 3 4 0 1 2000 0 - - - 2000 1 0 1 2 3500 2000 0 - - 3500 2 0 2 3 4500 3500 2000 0 - 4500 3 0 3 4 5000 4500 3500 2000 0 5000 4 0 4 5 3500 5000 4500 3500 2000 5000 4 1 Nh×n tõ khÝa c¹nh gi¶i quyÕt vÊn ®Ò, vÊn ®Ò vÒ yªu cÇu bé nhí lµ nghiªm träng h¬n vÊn ®Ò vÒ thêi gian tÝnh to¸n. NÕu bé nhí t¹m bÞ chiÕm chç vît qu¸ kh¶ n¨ng cña mét bé nhí m¸y tÝnh th× bµi to¸n sÏ kh«ng gi¶i ®îc. MÆt kh¸c, mét sù gia t¨ng vÒ thêi gian tÝnh to¸n chØ yªu cÇu ta cã thªm chót kiªn nhÉn ®Ó cã ®îc kÕt qu¶. ChÝnh v× vËy mµ vÊn ®Ò t¨ng nhanh vÒ yªu cÇu bé nhí g¾n víi c¸c bµi to¸n quy ho¹ch ®éng ®a biÕn tr¹ng th¸i cã thÓ ph©n biÖt c¸c bµi to¸n gi¶i ®îc vµ c¸c bµi to¸n kh«ng thÓ gi¶i ®îc. 140
B¶ng 4.1.3(b) TÝnh to¸n quy ho¹ch ®éng cho giai ®o¹n 3 cña VÝ dô 4.1.3 (b) Giai ®o¹n 3 – Mïa 3 QuyÕt f 3  S 3  = r3  S 3 ,d 3  + f 4*  S 4  Lîng tr÷ Lîi nhuËn Lîi nhuËn Lîng tr÷ Tæng ®Þnh cuèi cïng lín nhÊt ban ®Çu lîng tr÷ (X¶) S 3 = S4 Lîng tr÷ cuèi * f 3*  S 3  S3 S3 + QF3 S 3 = S4 d 3 = R* 0 1 2 3 4 3 3500 + 2000 2000 + 3500 0 + 4500 0 2 - - 5500 2,1 0,1 = = = 5500 5500 4500 4500 + 2000 3500 + 3500 2000 + 4500 0 + 5000 = 1 3 - 7000 2 1 = = = 5000 6500 7000 6500 5000 + 2000 4500 + 3500 3500 + 4500 2000 + 5000 0 + 5000 = 2 4 8000 3,2 1,2 = = = = 5000 7000 8000 8000 7000 3500 + 2000 5000 + 3500 4500 + 4500 3500 + 5000 2000 + 5000 3 5 9000 3 2, = = = = = 7000 5500 8500 9000 8500 1000 + 2000 3500 + 3500 5000 + 4500 4500 + 5000 3500 + 5000 4 6 = = = = 9500 4,3 2,3 = 8500 3000 7000 9500 9500
B¶ng 4.1.3(c) TÝnh to¸n quy ho¹ch ®éng cho giai ®o¹n 2 cña VÝ dô 4.1.3 (c) Giai ®o¹n 2 – Mïa 2 f 2 S 2   r2 S 2 , d 2   f 3* S 3  Lîi nhuËn Lîng tr÷ Lîng tr÷ Tæng lîng Lîi nhuËn QuyÕt ®Þnh S 2  S3 Lîng tr÷ cuèi cuèi cïng ban ®Çu tr÷ lín nhÊt (X¶) * S 2  * * f d2  R S 2  S3 S2 S2+QF2 0 1 2 3 4 2 2 0 1 2000+5500= 0+7000= _ _ _ 7500 1 0 7500 7000 1 2 3500+5500= 2000+7000= 0+8000= _ _ 9000 2,1 0,1 9000 9000 8000 2 3 4500+5500= 3500+7000= 2000+8000= 0+9000= _ 10500 2 1 10000 10500 10000 9000 3 4 5000+5500= 4500+7000= 3500+8000= 2000+9000= 0+9500= 11500 3,2 1,2 10500 11500 11500 11000 9500 4 5 3500+5500= 5000+7000= 4500+8000= 3500+9000= 2000+9500= 12500 3,2 2,3 9000 12000 12500 12500 11500
B¶ng 4.1.3(d) TÝnh to¸n quy ho¹ch ®éng cho giai ®o¹n 1 cña VÝ dô 4.1.3 (d) Giai ®o¹n 1 – Mïa 1 f1 S1   r1 S1 , d1   f 2* S 2  Lîi nhuËn Lîng tr÷ Lîng tr÷ Tæng Lîi nhuËn QuyÕt ®Þnh S1  S2 Lîng tr÷ cuèi cuèi cïng ban ®Çu lîng tr÷ lín nhÊt (X¶) * S1  * * f d1  R S1  S2 S1 S1+QF1 0 1 2 3 4 1 1 0 2 3500+7500= 2000+9000= 0+10500= _ _ 11000 2,1 0,1 11000 11000 10500 1 3 4500+7500= 3500+9000= 2000+10500= 0+11500= _ 12500 2,1 1,2 12000 12500 12500 11500 2 4 5000+7500= 4500+9000= 3500+10500= 2000+11500= 0+12500= 14000 2 2 12500 13500 14000 13500 12500 3 5 3500+7500= 5000+9000= 4500+10500= 3500+11500= 2000+12500= 15000 3,2 2,3 11000 14000 15000 15000 14500 4 6 1000+7500= 3500+9000= 5000+10500= 4500+11500= 3500+12500= 16000 3,2 3,4 8500 12500 15500 16000 16000
H×nh 4.1.4 B íc t×m ngîc cho vÝ dô 4.1.3. 4.2. Quy ho¹ch ®éng sai ph©n rêi r¹c Quy ho¹ch ®éng sai ph©n rêi r¹c (DDDP-Discrete Differential Dynamic Programming) lµ mét thñ tôc quy ho¹ch ®éng lÆp, ®îc ®Æc biÖt thiÕt kÕ ®Ó kh¾c phôc mét sè khã kh¨n cña c¸ch tiÕp cËn quy ho¹ch ®éng ®· ®îc ®Ò cËp ®Õn ë tríc. Quy ho¹ch ®éng sai ph©n rêi r¹c sö dông ph¬ng tr×nh ®Ö quy gièng nh quy ho¹ch ®éng ®Ó t×m kiÕm trong sè c¸c tr¹ng th¸i rêi r¹c thuéc miÒn giai ®o¹n-tr¹ng th¸i. Thay b»ng viÖc t×m kiÕm nghiÖm tèi u trªn toµn miÒn giai ®o¹n-tr¹ng th¸i nh trong trêng hîp quy ho¹ch ®éng, quy ho¹ch ®éng sai ph©n rêi r¹c chØ kiÓm tra mét phÇn cña miÒn giai ®o¹n-tr¹ng th¸i vµ do ®ã tiÕt kiÖm thêi gian vµ bé nhí m¸y tÝnh (Chow et al., 1975). Quy tr×nh tèi u hãa nµy ®îc gi¶i th«ng qua c¸c bíc lÆp cña c¸c tr¹ng th¸i vµ c¸c quyÕt ®Þnh thö nghiÖm ®Ó t×m kiÕm sù tèi u cho mét hÖ thèng víi nh÷ng rµng buéc lµ c¸c tr¹ng th¸i vµ c¸c quyÕt ®Þnh thö nghiÖm ph¶i n»m trong miÒn kh¶ thi t¬ng øng, ®ã lµ, kh¶ thi trong trong c¸c kh«ng gian tr¹ng th¸i vµ quyÕt ®Þnh. Trong quy ho¹ch ®éng sai ph©n rêi r¹c, bíc ®Çu tiªn lµ gi¶ thiÕt mét chuçi thö nghiÖm cña c¸c quyÕt ®Þnh cã thÓ chÊp nhËn ®îc gäi lµ chÝnh s¸ch thö nghiÖm vµ c¸c vector tr¹ng th¸i cña mçi giai ®o¹n ®îc tÝnh t¬ng øng. Chuçi c¸c tr¹ng th¸i n»m trong miÒn tr¹ng th¸i kh¶ thi cho c¸c giai ®o¹n kh¸c nhau ®îc gäi lµ quü ®¹o thö nghiÖm. Mét quy tr×nh kh¸c víi thñ tôc trªn lµ ®Çu tiªn ®i gi¶ sö mét quü ®¹o thö nghiÖm vµ sau ®ã sö dông nã ®Ó tÝnh ra chÝnh s¸ch thö nghiÖm. Mét vµi tr¹ng th¸i ë l©n cËn mét quü ®¹o thö nghiÖm, cã thÓ ®îc ®a vµo h×nh thµnh mét d¶i ®îc gäi lµ hµnh lang quü ®¹o thö nghiÖm (Xem h×nh 4.2.1). 118
H×nh 4.2.1 Sù thiÕt lËp hµnh lang quanh quü ®¹o thö nghiÖm cho mét bµi to¸n ba giai ®o¹n. Trong thùc hµnh th«ng thêng kh«ng gian tr¹ng th¸i ®îc rêi r¹c ho¸ thµnh c¸c sè gia ®Òu nhau, gäi lµ c¸c sè gia tr¹ng th¸i, trong ®ã tæng sè c¸c rêi r¹c hãa, ®îc xem lµ c¸c ®iÓm líi hay c¸c ®iÓm m¾t c¸o, cho mçi biÕn tr¹ng th¸i lµ nh nhau. Do ®ã, c¸c quyÕt ®Þnh ph¶i ®îc lùa chän t¬ng øng víi ph¬ng ph¸p rêi r¹c hãa c¸c biÕn tr¹ng th¸i. Kho¶ng sè gia cña biÕn quyÕt ®Þnh phô thuéc vµo kho¶ng sè gia cña biÕn tr¹ng th¸i t¬ng øng. Híng tiÕp cËn quy ho¹ch ®éng truyÒn thèng ®îc ¸p dông trong mét bµi to¸n quy ho¹ch ®éng sai ph©n rêi r¹c cho c¸c tr¹ng th¸i trong hµnh lang ®ã sö dông mèi quan hÖ ®Ö quy ®Ó t×m ra mét quü ®¹o tèt h¬n. Quü ®¹o nµy x¸c ®Þnh mét chÝnh s¸ch hay tËp hîp cña c¸c quyÕt ®Þnh trong hµnh lang ®· ®îc ®a ra. Quü ®¹o thö nghiÖm nµy sau ®ã ®îc sö dông nh mét quü ®¹o míi ®Ó t¹o ra mét hµnh lang míi. Qu¸ tr×nh h×nh thµnh vµ tèi u hµnh lang nµy xÐt tíi c¸c tr¹ng th¸i n»m trong hµnh lang ®ã vµ qua tr×nh t×m ngîc trë l¹i ®Ó nhËn ®îc mét quü ®¹o tèt h¬n cho toµn bé hÖ thèng ®îc gäi lµ mét bíc lÆp. Quü ®¹o míi, ®Þnh nghÜa hÖ thèng th«ng qua sù tèi u cña hµnh lang thö nghiÖm, sau ®ã ®îc sö dông nh quü ®¹o thö nghiÖm míi ®Ó thiÕt lËp hµnh lang tèt h¬n cho bíc lÆp tiÕp theo. Thñ tôc nµy ®îc lÆp tíi qu¸ mét bíc lÆp thø k nµo ®ã mµ ë ®ã cho ra mét hµnh lang. Hµnh lang nµy cung cÊp mét lîi nhuËn cña hÖ thèng fk sao cho c¸c bíc lÆp tiÕp theo víi cïng kÝch thíc cña hµnh lang nµy sÏ t¹o ra mét chªnh lÖch trong lîi nhuËn hÖ thèng, fk-fk-1 nhá h¬n mét dung sai x¸c ®Þnh. T¹i ®iÓm nµy trong thñ tôc tèi u hãa, kÝch thíc cña sè gia tr¹ng th¸i cã thÓ ®îc gi¶m xuèng ®Ó thiÕt lËp mét hµnh lang míi mµ trong ®ã c¸c tr¹ng th¸i hay c¸c ®iÓm líi xÝt nhau h¬n. Mét hµnh lang nhá h¬n ®îc h×nh thµnh quanh quü ®¹o ®· ®îc c¶i thiÖn tõ bíc lÆp cuèi cïng. 119
C¸c bíc lÆp tiÕp tôc gi¶m kÝch thíc cña sè gia tr¹ng th¸i th«ng qua hÖ thèng cho ®Õn khi ®¹t tíi mét kÝch thíc hµnh lang nhá nhÊt x¸c ®Þnh. Tiªu chuÈn ®îc sö dông ®Ó x¸c ®Þnh khi nµo kÝch thíc sè gia tr¹ng th¸i cÇn ®îc gi¶m lµ dùa trªn sù thay ®æi t¬ng ®èi cña gi¸ trÞ hµm môc tiªu tèi u cña bíc lÆp tríc, ®ã lµ: (4.2.1) f k  f k 1 / f k 1   trong ®ã  lµ møc dung sai x¸c ®Þnh. h×nh 4.2.2 lµ mét s¬ ®å khèi thÓ hiÖn thuËt gi¶i chung cña thñ tôc quy ho¹ch ®éng sai ph©n rêi r¹c. MÆc dï viÖc sö dông quy ho¹ch ®éng sai ph©n rêi r¹c phÇn nµo kh¾c phôc vÊn ®Ò liªn quan tíi lêi nguyÒn cña sè chiÒu cña quy ho¹ch ®éng th«ng thêng, nã l¹i g©y ra mét sè vÊn ®Ò cÇn quan t©m kh¸c liªn quan ®Õn viÖc lùa chän quü ®¹o ban ®Çu, viÖc thay ®æi ®iÓm líi hay kh«ng gian tr¹ng th¸i, vµ sù héi tô tíi mét tèi u ®Þa ph¬ng thay v× mét tèi u toµn côc. C¸c nh©n tè chÝnh ¶nh hëng tíi viÖc thùc hiÖn quy ho¹ch ®éng sai ph©n rêi r¹c gåm cã: 1. Sè c¸c ®iÓm líi; 2. Sè gia tr¹ng th¸i ban ®Çu cïng víi sè ®iÓm líi x¸c ®Þnh ®é réng hµnh lang; 3. Quü ®¹o thö nghiÖm ban ®Çu ®îc sö dông ®Ó thiÕt lËp vÞ trÝ cña c¸c hµnh lang bªn trong kh«ng gian tr¹ng th¸i cho bíc lÆp ®Çu tiªn; 4. Tèc ®é gi¶m cña kÝch thíc sè gia tr¹ng th¸i mµ x¸c ®Þnh ®é réng hµnh lang cho c¸c bíc lÆp kh¸c nhau. Nh÷ng nh©n tè nµy ®«i khi phô thuéc lÉn nhau trong viÖc sö dông thÝch hîp vµ hiÖu qu¶ quy ho¹ch ®éng sai ph©n rêi r¹c cho c¸c bµi to¸n tµi nguyªn níc. Sù lùa chän quü ®¹o thö nghiÖm ban ®Çu vµ ®é réng hµnh lang ban ®Çu lµ phô thuéc lÉn nhau. VÝ dô, nÕu mét ®é réng hµnh lang nhá ®îc chän cïng víi mét quü ®¹o thö nghiÖm ban ®Çu c¸ch xa vïng tèi u, c¸c bíc lÆp kh«ng cÇn thiÕt ®îc ®ßi hái ®Ó di chuyÓn quü ®¹o ®ã vµo trong vïng tèi u hoÆc gÇn tèi u. Cã thÓ trong mét sè trêng hîp bµi to¸n quy ho¹ch ®éng sai ph©n rêi r¹c sÏ héi tô tíi mét nghiÖm kh¸ xa nghiÖm tèi u. Sè c¸c ®iÓm líi vµ sè gia tr¹ng th¸i ban ®Çu cïng x¸c ®Þnh ®é réng cña hµnh lang ban ®Çu. Sö dông mét sù kÕt hîp mét sè lîng nhá c¸c ®iÓm líi vµ mét sè gia tr¹ng th¸i ban ®Çu nhá còng cã thÓ dÉn tíi nh÷ng lêi gi¶i tèi u ®Þa ph¬ng c¸ch xa nghiÖm tèi u. ¶nh hëng cña viÖc chän mét quü ®¹o ban ®Çu kh«ng tèt cã thÓ ®îc gi¶m ®i nÕu mét sè lîng lín c¸c ®iÓm líi vµ/hoÆc c¸c sè gia tr¹ng th¸i ban ®Çu lín ®îc sö dông. Thùc chÊt, quü ®¹o ban ®Çu cµng tèt th× yªu cÇu sè c¸c ®iÓm líi vµ c¸c sè gia tr¹ng th¸i ban ®Çu cµng nhá, hoÆc ®¬n gi¶n, cµng cã thÓ sö dông ®é réng hµnh lang ban ®Çu nhá. Sè gia tr¹ng th¸i rÊt nhá víi c¸c ®iÓm líi nhiÒu h¬n còng cã thÓ ®îc sö dông ®Ó thiÕt lËp mét ®é réng hµnh lang nhá. §iÒu nµy cã thÓ dÉn tíi sù héi tô tèt h¬n; tuy nhiªn, viÖc t¨ng sè 120
lîng c¸c ®iÓm líi lµm t¨ng thêi gian tÝnh to¸n vµ nhu cÇu lu tr÷. Thêi gian tÝnh to¸n cã thÓ ®îc c¶i thiÖn b»ng viÖc gia t¨ng tèc ®é gi¶m cña sè gia tr¹ng th¸i t¹i mçi bíc lÆp; tuy nhiªn, tèc ®é suy gi¶m cña sè gia tr¹ng th¸i qu¸ lín cã thÓ bá qua khu vùc tèi u v× vËy kh«ng cung cÊp lêi gi¶i tèi u. ViÖc lùa chän mét sè gia tr¹ng th¸i ban ®Çu lín vµ mét tèc ®é suy gi¶m kÝch thíc sè gia tr¹ng th¸i lín cã thÓ lµ cã lîi. Tuy nhiªn, khi sè gia tr¹ng th¸i ban ®Çu qu¸ lín, dÉn tíi c¸c ®é réng hµnh lang lín, nh÷ng sù tÝnh to¸n kh«ng cÇn thiÕt ®îc thùc hiÖn ë c¸c khu vùc kh«ng gian tr¹ng th¸i c¸ch xa vïng tèi u. H×NH 4.2.2 ThuËt gi¶i tæng qu¸t cho quy ho¹ch ®éng sai ph©n rêi r¹c 4.3. §¹i sè ma trËn cho quy ho¹ch phi tuyÕn 121
§Ó gi¶i thÝch c¸c kh¸i niÖm cña qui ho¹ch phi tuyÕn, nhiÒu kü thuËt vÒ ®¹i sè ma trËn vµ ®¹i sè tuyÕn tÝnh ®îc sö dông. Trong môc nµy giíi thiÖu tãm t¾t mét sè kh¸i niÖm ®ã. Mét ®êng lµ mét tËp hîp c¸c ®iÓm x=x0+  d (4.3.1) H×nh 4.3.1 X ¸c ®Þnh mét ®êng th¼ng trong kh«ng gian hai chiÒu. trong ®ã x0 lµ mét ®iÓm x¸c ®Þnh trªn ®êng th¼ng,  lµ mét kÝch thíc bíc (bËc) v« híng, vµ d lµ híng cña ®êng th¼ng. h×nh 4.3.1 biÓu thÞ mét ®êng th¼ng trong kh«ng gian hai chiÒu trong ®ã x0 lµ ®iÓm (1,1) vµ d lµ vector chØ híng (2,1)T ®îc biÓu thÞ b»ng mòi tªn trong ®ã ch÷ T ë trªn biÓu thÞ chuyÓn vÞ cña mét vector hay mét ma trËn. Mét hµm nhiÒu biÕn f(x) t¹i ®iÓm x còng lµ mét kh¸i niÖm quan träng. Víi mét hµm mµ lµ liªn tôc vµ ®¹o hµm liªn tôc, cã mét vector cña ®¹o hµm bËc nhÊt ®îc gäi lµ gradient hay vector gradient. T  f   f f f  f  x       (4.3.2) , ,....,   x   x1 x2 xn  T trong ®ã  lµ vector cña to¸n tö gradient   / x1,...,  / xn  . VÒ mÆt h×nh häc, vector gradient t¹i mét ®iÓm cho tríc biÓu thÞ híng mµ theo ®ã tèc ®é gia t¨ng lín nhÊt trong gi¸ trÞ hµm sÏ diÔn ra. Víi f(x) cã ®¹o hµm liªn tôc bËc hai tån t¹i mét ma trËn ®¹o hµm bËc hai ®îc gäi lµ ma trËn Hessian hay Hessian.  2 f 2 f 2 f  ...   x2 x1x2 x1xn   2 1 2 2 f f f  ... H ( x)   2 f  x    x x (4.3.3) x12  2 x2  ... 1 2 ...  ... ... 2 2 f  f  ... ... 2  xnx1 xn    122