1. Trang Chủ
  2. Môi trường
  3. 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

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ướ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 4 øng dông quy ho¹ch p

Thể loại Tài liệu miễn phí Môi trường

Số trang 57

Ngày tạo 8/29/2018 11:44:00 PM +00:00

Loại tệp PDF

Kích thước 2.34 M

Tên tệp

Tải Kỹ thuật và quản lý hệ thống nguồn nước ( Đại học ... (.pdf)

Xem mẫu

  1. 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 129
  2. 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ù 130
  3. ¸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
  4. 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 132
  5. 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
  6. 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
  7. 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 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 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
  8. 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
  9. 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
  10. ~ 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. l­îng c¸c ®iÓm l­íi lµm t¨ng thêi gian tÝnh to¸n vµ nhu cÇu l­u 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
  20. §Ó 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
nguon tai.lieu . vn
Toán học Môi trường Vật lý Sinh học Địa Lý Hoá học Nông - Lâm - Ngư Cơ khí - Chế tạo máy Tiếng Anh phổ thông Khoa học ứng dụng Nông - Lâm Kiến thức tổng hợp Giáo dục học Xã hội học