Một số thuật toán giải bài toán tối ưu phân thức và ứng dụng

 1 
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 
 2 
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 <...< q lµ ký hiÖu tÊt c¶ c¸c gi¸ trÞ cña  mµ trong ®ã hai ®­êng trong {f(x)-
g(x) x X} giao nhau th× hµm h lµ tuyÕn tÝnh trªn tõng ®o¹n [- , 1], [i, i+1] víi i=1,2,..,q-1, 
vµ [q, + ]. 
(v) Hµm h lµ låi. 
Chóng ta sö dông c¸c tham sè sau : 
MAXf = max{ f(x) : x X }, MAXg = max{ g(x) :x X }, MINg = min{ g(x) : x X },GAP = 
min { f(x,)/g(x,)-f(x,,)/g(x,,) : x,, x,, X, vµ f(x,)/g(x,) f(x,,)/g(x,,)}. 
C¸c gi¶ thiÕt vÒ hµm f(x) vµ g(x) ë bµi to¸n F chØ ra r»ng gi¸ trÞ môc tiªu tèi ­u cña bµi to¸n F 
lµ n»m trong kho¶ng (0, MAXf / MINg ). Tham sè GAP lµ sù kh¸c biÖt nhá nhÊt gi÷a hai tû sè 
chi phÝ-träng l­îng kh¸c nhau. 
Trong phÇn tiÕp theo, ta xÐt mét sè bµi to¸n tèi ­u rêi r¹c ph©n thøc tuyÕn tÝnh d¹ng : 
 FL : max 
pp
pp
xbxbxb
xaxaxa
...
...
2211
2211
 víi (x1,x2,. ..,xp ) X. 
II. Bµi to¸n t×m ®­êng ®i cã tû sè lín nhÊt trong ®å thÞ kh«ng cã chu tr×nh. 
Mét vÝ dô cho bµi to¸n qui ho¹ch rêi r¹c ph©n tuyÕn lµ bµi to¸n ®­êng ®i cã tû sè lín nhÊt 
(MaxRatioPath) nh­ sau: 
Cho ®å thÞ cã h­íng n ®Ønh víi tËp c¹nh E. C¸c hµm chi phÝ trªn c¹nh: 
c : E R vµ hµm träng l­îng c¹nh w: E R. 
Gi¶ sö víi (v,u) E th× v < u vµ mäi ®Ønh ®Òu cã thÓ ®Õn ®­îc tõ ®Ønh 1. 
Cho ®­êng ®i P vµ gäi f(P)= 
 Puv
uvc
),(
),( , g(P)= 
 Puv
uvw
),(
),( , f(P)/g(P) lÇn l­ît lµ chi phÝ, träng 
l­îng vµ chi phÝ-träng l­îng trung b×nh. YÒu cÇu cña bµi to¸n lµ t×m ®­êng ®i tõ ®Ønh 1 tíi ®Ønh 
n ®Ó chi phÝ-träng l­îng trung b×nh lín nhÊt: 
 MaxRatioPath: Max 
)(
)(
Pg
Pf
trªn tÊt c¶ ®­êng ®i P E tõ ®Ønh 1 tíi ®Ønh n. VÐc t¬ x X cã d¹ng x {0,1}E sÏ t­¬ng øng víi 
c¸c ®­êng ®i tõ ®Ønh 1 tíi ®Ønh n. 
Bµi to¸n tham sè t­¬ng øng cña MaxRatioPath lµ: 
 3 
 MaxPath() : Max f(P)-g(P) víi tÊt c¶ PE tõ ®Ønh 1 tíi ®Ønh n. 
Víi mçi  R vµ ®­êng ®i P cè ®Þnh, f(P)-g(P)= Pe ewec ))()((  , v× vËy gi¸ trÞ tèi ­u cña 
MaxPath() lµ gi¸ trÞ lín nhÊt cña mét ®­êng ®i tõ ®Ønh 1 tíi ®Ønh n theo hµm chi phÝ trªn c¹nh 
c -w. 
VÝ dô : XÐt ®å thÞ cã h­íng minh ho¹ trªn h×nh vÏ. 
C¸c ®­êng th¼ng 9-6, 8-4, 6-2, vµ 4- t­¬ng øng víi 4 ®­êng tõ ®Ønh 1 tíi ®Ønh 4. §­êng ®i 
tèi ­u lµ 1-3-4. 
ThuËt to¸n MaxCost d­íi ®©y tÝnh to¸n gi¸ trÞ lín nhÊt cña mét ®­êng ®i tõ ®Ønh 1 tíi ®Ønh n 
cña tËp c¸c c¹nh E vµ mét hµm chi phÝ trªn c¹nh a bÊt kú b»ng c¸ch xÐt trong c¸c ®Ønh tõ 1 tíi 
n-1. Trong khi xÐt ®Ønh v, thuËt to¸n kiÓm tra tÊt c¶ c¸c c¹nh ®i ra tõ v.Trong qu¸ tr×nh tÝnh to¸n, 
biÕn boolean seen[u] chØ ra ®Ønh u ®· ®­îc th¨m hay ch­a. C¸c phÇn tö cña m¶ng d[v] víi 
v=1,2,...,n lµ b»ng gi¸ trÞ lín nhÊt cña ®­êng ®i tõ ®Ønh 1 tíi ®Ønh v sau mét lÇn tÝnh. BiÕn 
predecessor trá tíi d¹ng mét c©y chøa "®­êng ®i dµi nhÊt" cã gèc lµ ®Ønh 1. 
C¸c thuËt to¸n tr×nh bµy d­íi d¹ng ng«n ng÷ tùa C. 
ThuËt to¸n MaxCost. 
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) if (not seen[u]) or (d[v] +a(v, u)-d[u] >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 
   
  path1-2-3-4) 
path1-2-3-4) 
  path1-2-4) 
path1-2-3-4) 
  path1-4) 
path1-2-3-4) 
  path1-3-4) 
path1-2-3-4) 
h 
 4 
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 * 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) then 
9) d[u]:= d[v] + c(v,u)-*w(v,u); 
10) predecessor[u]:=v ; seen[u]:= true 
11) Let P=(v1, v2,. .., vk ) where v1=1, vk =n, and vi= predecessor[vi+1] for i=1,2,..,k-1 
12) return path P. 
 III. Ph­¬ng ph¸p Newton. 
Ph­¬ng ph¸p Newton cho bµi to¸n tèi ­u rêi r¹c ph©n tuyÕn lµ mét øng dông cña ph­¬ng ph¸p 
Newton cæ ®iÓn cho bµi to¸n t×m nghiÖm cña hµm h() ®Þnh nghÜa ë (2). §Ó sö dông ph­¬ng 
ph¸p nµy ta gäi Amax lµ thuËt to¸n tÝnh to¸n h() vµ x X tho¶ f(x)-g(x) =h() víi  ®· cho. 
(Tøc lµ gi¶i quyÕt bµi to¸n P() b»ng ph­¬ng ph¸p cña quy ho¹ch tham sè, xem [3]). 
Ph­¬ng ph¸p Newton cho bµi to¸n F lµ t¹o ra qu¸ tr×nh lÆp trong ®ã mçi b­íc lÆp sinh ra mét 
xÊp xØ míi gÇn gi¸ trÞ môc tiªu tèi ­u * h¬n. T¹i b­íc lÆp thø i, ­íc l­îng  * lu«n ®­îc xem 
xÐt vµ qu¸ tr×nh tÝnh to¸n nh­ sau: 
Tr­íc hÕt, ch¹y thuËt to¸n Amax cho =i thu ®­îc hi= h(i) vµ xi X tho¶ m·n: f(xi)-ig(xi)=hi. 
 NÕu hi=0 th× i=
* lµ nghiÖm tèi ­u cña bµi to¸n F vµ qu¸ tr×nh tÝnh to¸n dõng l¹i. 
Ng­îc l¹i ta thu ®­îc ­íc l­îng míi i+1:=f(xi)/g(xi) 
 (NhËn xÐt i
 < i+1 
* v× hi > 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 ) 
 5 
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= g(xi), víi mçi 1 i < t+1. Tõ qu¸ tr×nh m« t¶ trªn ta cã : 
 hi= fi- igi víi mçi 1 i < t+1, 
 i+1 =fi / gi, víi mçi 1 i <t. 
C¸c kÕt qu¶ sau ®· ®­îc chøng minh trong[1],[4], rÊt cã ý nghÜa trong c¸c vÊn ®Ò vÒ ®é phøc t¹p 
tÝnh to¸n(computational complexity) trong to¸n häc vµ tin häc: 
 KÕt qu¶ 1. Ph­¬ng ph¸p Newton dõng sau mét sè h÷u h¹n b­íc lÆp vµ : 
(A) h1 >h2 >. ..>ht-1 > ht =0, 
(B) 0 = 1 < 2 <...< t-1 <t = 
*, 
(C) g1 > g2 >...>gt-1 >gt. 
KÕt qu¶ 2. 
Víi mçi i=1,2,..., t-1, th× 111 
i
ii
g
g
hi
h
. 
KÕt qu¶ 3. Ph­¬ng ph¸p Newton gi¶i bµi to¸n F víi nhiÒu nhÊt 
 log(MAXf )+log(MAXg)-log(MINg)-log(GAP) +2 b­íc lÆp. 
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µ 
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. 
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, 
y2,...,yp lµ vÐc t¬ thuéc {-1,0,1}
p. NÕu víi tÊt c¶ i=1,2,..,q-1 
 0 <yi+1c 
2
1
yic th× q=O(plogp). 
VËy suy ra: Gäi c=(c1,c2,...,cp) vµ y1, y2,...,yp lµ c¸c vÐc t¬ thuéc {0, 1}
p. 
 i 
hi 
i+1 
hi+1 
 
f(xi)-g(xi) 
f(xi+1)-g(xi+1) 
 6 
 NÕu 0 <yi+1 c 
2
1
yic víi mäi i=1,2,.., q-1 th× q=O(plogp). 
KÕt qu¶ 6.Ph­¬ng ph¸p Newton gi¶i bµi to¸n qui ho¹ch rêi r¹c ph©n tuyÕn tÝnh FL trong 
O(p3logp) b­íc. 
KÕt qu¶ 7. Cã nhiÒu nhÊt O(plogp) b­íc lÆp k tho¶ m·n : gk+1 (2/3)gk. 
KÕt qu¶ 8. Cã nhiÒu nhÊt O(plogp) b­íc lÆp liªn tiÕp k tho¶ m·n : gk+1 (2/3)gk. 
Tõ hai kÕt qu¶ 7 vµ 8 ta suy ra nhËn xÐt: Ph­¬ng ph¸p Newton gi¶i bµi to¸n qui ho¹ch rêi r¹c 
ph©n tuyÕn tÝnh FL trong O(p
2log2p) b­íc lÆp. 
Trë l¹i bµi to¸n MaxRatioPath, nÕu c¸c träng l­îng lµ kh«ng ©m th× ph­¬ng ph¸p Newton l¹i 
chØ yªu cÇu O(nlogn) b­íc lÆp. §iÒu nµy ®­îc kh¼ng ®Þnh nhê kÕt qu¶ sau: 
KÕt qu¶ 9. Ph­¬ng ph¸p Newton gi¶i bµi to¸n MaxRatioPath trong O(nlogn) b­íc lÆp vµ thêi 
gian tÝnh O(n2logn) nÕu c¸c träng l­îng cña c¸c c¹nh lµ kh«ng ©m. 
Tµi liÖu tham kh¶o 
 1.NguyÔn M¹nh Hïng, Mét sè bµi to¸n tèi ­u trªn tËp rêi r¹c víi hµm môc tiªu ph©n tuyÕn, 
LuËn v¨n Th¹c sÜ – ViÖn To¸n häc –2001. 
 [2]. N.Megiddo. "Combinatorial optimization with rational object 
functions". Mathematics of Operation Reseach 4 -1979. 
[3]. Bïi ThÕ T©m-TrÇn Vò ThiÖu, "C¸c ph­¬ng ph¸p tèi ­u ho¸", Nhµ xuÊt b¶n Giao th«ng vËn 
t¶i, Hµ néi, 1998. 
 [4]. C.H.Papadimitriou and K.Steiglitz, Combinatorial Optimization : Algorithms and 
Complexity. Pren-tice-Hall, Englewood Cliffwood, 1982. 
Algorithms for Fractional Programming and application 
Abstract: Water resources systems create many special problems, for example, in water 
resources planning, one wants to maximize economic efficiency, environmental quality, flood 
control capabilities...,which make the application of optimization methodologies and 
mathematical models quite difficult from different characteristics of these systems in relation 
with combinatorial optimization. The distinguishing feature of discrete, combinatorial 
optimization is that some of the variables are required to belong to a discrete set and it has been 
developing rapidly because of the widespread use of computer and information technology. 
Some techniques are viewed here as solutions of our algorithms and convergence theorems for 
Fractional Programming problems. We present a version of Newton's method deals with 
computational complexity and the optimal solution is approximated by Polynomial –Time 
Algorithms that stop for some finite iteration index. 
 7 
 8