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<br /> Th.s. nguyÔn m¹nh hïng<br /> Tr­êng §¹i häc Thuû lîi, Email: hungmath1976@yahoo.com<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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ö<br /> 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<br /> ­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.<br /> 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<br /> 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<br /> 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è<br /> 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<br /> th­êng gÆp trong thùc tÕ lµ bµi to¸n tèi ­u ph©n tuyÕn rêi r¹c.<br /> Bµi to¸n tèi ­u rêi r¹c ph©n tuyÕn cã thÓ ph¸t biÓu nh­ sau:<br /> (F): max{ f(x)/g(x) : xX } (1)<br /> trong ®ã g(x) >0 xX, f(x) >0 víi mét sè x X,<br /> 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Ý (<br /> 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<br /> r¹c ph©n tuyÕn lµ t×m : Max { f(x)/g(x), xX} trong ®ã X {0,1}p.<br /> 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.<br /> CÆp (*, x*)R  X lµ nghiÖm tèi ­u cña bµi to¸n G nÕu vµ chØ nÕu:<br /> f(x)-*g(x)  0= f(x*)-*g(x*) víi mçi xX.<br /> §iÒu nµy t­¬ng ®­¬ng víi : f(x)/g(x)  *= f(x*)/g(x*) víi mçi xX,<br /> 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<br /> vµ G lµ t­¬ng ®­¬ng.<br /> 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.<br /> 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().<br /> 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µ<br /> 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<br /> bµi to¸n F: ( Z) : T×m R tho¶ m·n h() =0<br /> <br /> <br /> 1<br /> trong ®ã h() =max { f(x) - g(x) x X } (2)<br /> 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<br /> 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<br /> cña mét sè h÷u h¹n c¸c hµm tuyÕn tÝnh gi¶m.<br /> (i) Hµm h lµ liªn tôc trªn (-, +) vµ gi¶m ngÆt tõ + tíi -.<br /> (ii) h(0) >0 (§­îc suy ra tõ gi¶ sö f(x) > 0 víi mét sè x  X nµo ®ã)<br /> (iii) Hµm h cã chÝnh x¸c mét nghiÖm * vµ * > 0.<br /> (iv) NÕu 1< 2 0 ) then<br /> 6) d[u]:= d[v] +a(v, u) ; predecessor[u]:=v ; seen[u]:= true<br /> 7) Let P=(v1, v2,. .., vk ) where v1=1, vk =n, and vi= predecessor[vi+1] for i=1,2,..,k-1<br /> <br /> 3<br /> 8) return d[n] and path P.<br /> 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)<br /> sÏ tr¶ l¹i gi¸ trÞ 0 vµ mét ®­êng ®i P lµ tèi ­u cho bµi to¸n MaxRatioPath .<br /> 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µ<br /> 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<br /> 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 :<br /> 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:<br /> WeightedMaxCost(n,E,c,w)<br /> 1) d[1]:=0 ; seen[1]:=true<br /> 2) for v=2 to n do seen[v]:=false<br /> 3) for v=1 to n-1 do<br /> 4) for each u such that (v, u )E do<br /> 5) let s and t be the number such that<br /> s-*t =d[v] + c(v,u)-*w(v,u) -d[u]<br /> 6) if t # 0 then<br /> 7) x:=the number returned by MaxCost(n,E,c-(s/t)w)<br /> 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<br /> ph¸p Newton gi¶i h()=0 )<br /> <br /> 4<br />  f(xi)-g(xi)<br /> <br /> <br /> f(xi+1)-g(xi+1)<br /> <br /> <br /> hi<br /> hi+1<br /> i i+1  <br /> <br /> Qu¸ tr×nh tÝnh to¸n b¾t ®Çu víi 1=0.<br /> 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)<br /> vµ gi= g(xi), víi mçi 1  i < t+1. Tõ qu¸ tr×nh m« t¶ trªn ta cã :<br /> hi= fi- igi víi mçi 1  i < t+1,<br /> i+1 =fi / gi, víi mçi 1  i h2 >. ..>ht-1 > ht =0,<br /> (B) 0 = 1 < 2 ...>gt-1 >gt.<br /> KÕt qu¶ 2.<br /> hi 1 gi 1<br /> Víi mçi i=1,2,..., t-1, th×   1.<br /> hi gi<br /> KÕt qu¶ 3. Ph­¬ng ph¸p Newton gi¶i bµi to¸n F víi nhiÒu nhÊt<br /> log(MAXf )+log(MAXg)-log(MINg)-log(GAP) +2 b­íc lÆp.<br /> KÕt qu¶ 4.Víi bµi to¸n tèi ­u rêi r¹c ph©n tuyÕn tÝnh FL tho¶ m·n tÊt c¶ c¸c ai, bi, 1  i p, lµ<br /> nguyªn vµ kh«ng lín h¬n U th× ph­¬ng ph¸p Newton ch¹y trong O(log(pU)) b­íc lÆp.<br /> KÕt qu¶ 5.Gäi c=(c1,c2,...,cp) lµ mét vÐc t¬ p-chiÒu víi c¸c thµnh phÇn thùc kh«ng ©m,vµ gäi y1,<br /> y2,...,yp lµ vÐc t¬ thuéc {-1,0,1}p. NÕu víi tÊt c¶ i=1,2,..,q-1<br /> 1<br /> 0