Một số thuật toán giải bài toán tối ưu phân thức và ứng dụng - ThS. Nguyễn Mạnh Hùng

Mời các bạn cùng tham khảo nội dung bài viết "Một số thuật toán giải bài toán tối ưu phân thức và ứng dụng" dưới đây để nắm bắt được nội dung bài toán tìm đường đi có tỷ số lớn nhất trong đồ thị không có chu trình, phương pháp Newton,... Với các bạn chuyên ngành Toán học thì đây là tài liệu tham khảo hữu ích.
Nội dung trích xuất từ tài liệu:
Một số thuật toán giải bài toán tối ưu phân thức và ứng dụng - ThS. Nguyễn Mạnh Hùng mét sè thuËt to¸n gi¶i bµi to¸n tèi ­u ph©n thøc vµ øng dông Th.s. nguyÔn m¹nh hïng Tr­êng §¹i häc Thuû lîi, Email: hungmath1976@yahoo.com Tãm t¾t: HÖ thèng nguån n­íc t¹o ra nhiÒu vÊn ®Ò ®Æc biÖt, vÝ dô, trong sö dông tèi ­u nguån n­íc, viÖc cùc ®¹i hiÖu qu¶ kinh tÕ, chÊt l­îng m«i tr­êng, kh¶ n¨ng ®iÒu tiÕt lò...vv khi øng dông c¸c ph­¬ng ph¸p tèi ­u ho¸ vµ c¸c m« h×nh To¸n häc gÆp kh¸ nhiÒu khã kh¨n v× c¸c ®Æc tr­ng kh¸c nhau cña hÖ thèng liªn quan ®Õn bµi to¸n qui ho¹ch rêi r¹c. §Æc ®iÓm kh¸c biÖt cña tèi ­u rêi r¹c, tèi ­u tæ hîp lµ c¸c biÕn thuéc miÒn rêi r¹c vµ nã ®· ph¸t triÓn nhanh chãng v× viÖc sö dông réng kh¾p vÒ m¸y tÝnh vµ c«ng nghÖ th«ng tin. Mét sè kü thuËt cña tèi ­u rêi r¹c d­íi ®©y lµ lêi gi¶i vÒ c¸c thuËt to¸n , c¸c ®Þnh lý héi tô cho bµi to¸n tèi ­u ph©n tuyÕn .Sö dông ph­¬ng ph¸p Newton liªn hÖ víi ®é phøc t¹p tÝnh to¸n cña thuËt to¸n trong ®ã nghiÖm tèi ­u ®­îc xÊp xÜ vµ thuËt to¸n ®a thøc dõng sau mét sè h÷u h¹n b­íc lÆp. I. Giíi thiÖu. Bµi to¸n t×m cùc ®¹i hoÆc cùc tiÓu cña th­¬ng hai hµm thùc trªn tËp D cña kh«ng gian Rn ®­îc gäi lµ bµi to¸n tèi ­u ph©n tuyÕn. Bµi to¸n tèi ­u ph©n tuyÕn t×m ®­îc nhiÒu øng dông trong thùc tÕ, ch¼ng h¹n ®Ó ®o hiÖu qu¶ cña mét sè hÖ thèng ®­îc thÓ hiÖn nh­ lµ tû sè gi÷a lîi nhuËn /thêi gian, phÝ tæn /thêi gian,.. . Mét trong nh÷ng líp bµi to¸n tèi ­u ph©n tuyÕn th­êng gÆp trong thùc tÕ lµ bµi to¸n tèi ­u ph©n tuyÕn rêi r¹c. Bµi to¸n tèi ­u rêi r¹c ph©n tuyÕn cã thÓ ph¸t biÓu nh­ sau: (F): max{ f(x)/g(x) : xX } (1) trong ®ã g(x) >0 xX, f(x) >0 víi mét sè x X, C¸c phÇn tö cña tËp rêi r¹c X ®­îc gäi lµ c¸c cÊu tróc, f(x) th­êng ®­îc gäi lµ hµm chi phÝ ( cost), g(x) th­êng ®­îc gäi lµ hµm träng l­îng (weight). Mét vÝ dô vÒ bµi to¸n qui ho¹ch rêi r¹c ph©n tuyÕn lµ t×m : Max { f(x)/g(x), xX} trong ®ã X {0,1}p. Cïng víi bµi to¸n F ta xÐt bµi to¸n sau: (G): Min R víi f(x)-g(x) 0 x X. CÆp (*, x*)R  X lµ nghiÖm tèi ­u cña bµi to¸n G nÕu vµ chØ nÕu: f(x)-*g(x)  0= f(x*)-*g(x*) víi mçi xX. §iÒu nµy t­¬ng ®­¬ng víi : f(x)/g(x)  *= f(x*)/g(x*) víi mçi xX, cã nghÜa lµ * lµ gi¸ trÞ môc tiªu tèi ­u vµ x* lµ nghiÖm tèi ­u cña bµi to¸n F. V× vËy bµi to¸n F vµ G lµ t­¬ng ®­¬ng. Gäi P() lµ bµi to¸n bæ trî tham sè t­¬ng øng cña F: P() : Max f(x)-g(x), víi x X. Ký hiÖu h() vµ x* lµ gi¸ trÞ môc tiªu tèi ­u vµ nghiÖm tèi ­u cña bµi to¸n P(). Ta cã h() =0 nÕu vµ chØ nÕu (, x* ) lµ nghiÖm tèi ­u cña G, tøc lµ, nÕu vµ chØ nÕu  vµ x* lµ gi¸ trÞ môc tiªu tèi ­u vµ nghiÖm tèi ­u cña bµi to¸n F. V× vËy ta cã d¹ng t­¬ng ®­¬ng kh¸c cña bµi to¸n F: ( Z) : T×m R tho¶ m·n h() =0 1 trong ®ã h() =max { f(x) - g(x) x X } (2) ChÝnh d¹ng nµy gîi ra c¸ch thiÕt kÕ thuËt to¸n cho bµi to¸n F b»ng c¸ch ¸p dông c¸c ph­¬ng ph¸p cæ ®iÓn t×m nghiÖm cña hµm. C¸c tÝnh chÊt sau cña hµm h ®­îc suy ra víi h lµ maximum cña mét sè h÷u h¹n c¸c hµm tuyÕn tÝnh gi¶m. (i) Hµm h lµ liªn tôc trªn (-, +) vµ gi¶m ngÆt tõ + tíi -. (ii) h(0) >0 (§­îc suy ra tõ gi¶ sö f(x) > 0 víi mét sè x  X nµo ®ã) (iii) Hµm h cã chÝnh x¸c mét nghiÖm * vµ * > 0. (iv) NÕu 1< 2 0 ) then 6) d[u]:= d[v] +a(v, u) ; predecessor[u]:=v ; seen[u]:= true 7) Let P=(v1, v2,. .., vk ) where v1=1, vk =n, and vi= predecessor[vi+1] for i=1,2,..,k-1 3 8) return d[n] and path P. Nh­ vËy nÕu * lµ gi¸ trÞ tèi ­u cña MaxPath() th× ta ch¹y thuËt to¸n víi ®Çu vµo lµ (n,E,c-*w) sÏ tr¶ l¹i gi¸ trÞ 0 vµ mét ®­êng ®i P lµ tèi ­u cho bµi to¸n MaxRatioPath . B©y giê, ta thö ch¹y MaxCost víi ®Çu vµo lµ (n,E, c-*w) nh­ng kh«ng biÕt gi¸ trÞ *. §©y lµ c¸ch t×m kiÕm tham sè theo ph­¬ng ph¸p Megiddo[2]. Tõ dßng 5) trong thuËt to¸n MaxCost trªn ta cã: d[v] + (c(v,u)-*w(v,u))-d[u] > 0 tøc cã d¹ng : s-*t >0 cã ba kh¶ n¨ng : s/t < *, s/t > * hoÆc s/t= *. V× vËy ta cã thuËt to¸n cho bµi to¸n MaxRatioPath nh­ sau: WeightedMaxCost(n,E,c,w) 1) d[1]:=0 ; seen[1]:=true 2) for v=2 to n do seen[v]:=false 3) for v=1 to n-1 do 4) for each u such that (v, u )E do 5) let s and t be the number such that s-*t =d[v] + c(v,u)-*w(v,u) -d[u] 6) if t # 0 then 7) x:=the number returned by MaxCost(n,E,c-(s/t)w) 8) if (not seen[u]) or (t=0 and s>0) or (tx 0) vµ chóng ta xö lý b­íc lÆp tiÕp theo. (H×nh minh ho¹ ph­¬ng ph¸p Newton gi¶i h()=0 ) 4  f(xi)-g(xi) f(xi+1)-g(xi+1) hi hi+1 i i+1   Qu¸ tr×nh tÝnh to¸n b¾t ®Çu víi 1=0. Gäi t lµ chØ sè cña b­íc lÆp cuèi cïng vµ t=+ nÕu qu¸ tr×nh tÝnh to¸n kh«ng dõng. §Æt fi=f(xi) vµ gi= ...