陳 剛

(南通職業(yè)大學(xué)基礎(chǔ)部，江蘇南通226007)

尋求三元函數(shù)F(x,y,t)在有界閉區(qū)域Ω上的最小值，經(jīng)典的微分法已解決理論定位[1]：找出區(qū)域Ω內(nèi)部的駐點和邊界上的疑似極值點，比較它們的函數(shù)值，即可確定全區(qū)域的最小值.

但理論定位還遠未完全解決現(xiàn)實的最小值認定.在實際問題中，一方面內(nèi)部駐點和邊界極值點通常沒有解析表達，難以比較函數(shù)值；另一方面雖然計算機程序可提供足夠精度的數(shù)值計算，但函數(shù)F(x,y,t)中往往含有大量的參數(shù)，這些參數(shù)未給定具體數(shù)值前或處于變動時無法實施數(shù)值搜索.此外，經(jīng)典微分法著眼于整體處置，缺少個性特點，運算量比較大.

為了解決上述困難，本文考慮運用逐次極值法，并結(jié)合典型案例，說明逐次極值法的實際分析操作.

1 逐次極值法原理與算法

1.1 逐次極值法的原理

定理1設(shè)F(x,y,t)的可行域為Ω，對于每一個固定的t∈{t|(x,y,t)∈Ω}，二元函數(shù)F(x,y,t)取得最小值φ(t).若函數(shù)φ(t)在t=t*時取得最小值φ(t*)，則φ(t*)必為三元函數(shù)F(x,y,t)在區(qū)域Ω中的最小值.

證根據(jù)最小值的可達性知，存在(x*,y*,t*)∈Ω使φ(t*)=F(x*,y*,t*).再根據(jù)φ(t)的定義知，對于任意(x,y,t)∈Ω，

F(x,y,t)≥φ(t)≥φ(t*)=F(x*,y*,t*).

定理1給出了求最優(yōu)解的逐次遞推方法：對于固定的t，可得到低維區(qū)域Dt?Ω，求出Dt中的最小值點x=x(t)，y=y(t)，則φ(t)=F(x(t),y(t),t)，然后設(shè)法求出φ(t)的最小值.

這里的x=x(t)，y=y(t)是區(qū)域Ω中的曲線，稱之為優(yōu)勢曲線，φ(t)稱為優(yōu)勢函數(shù)，最小值點(x(t*),y(t*),t*)也叫最優(yōu)點.最優(yōu)點的位置往往隨函數(shù)中的參數(shù)而變，分析優(yōu)勢曲線和優(yōu)勢函數(shù)，可以獲得各個可能極值點成為最優(yōu)點的充分必要條件，進而完成最優(yōu)性的理論定位.

1.2 逐次極值法的算法

對于固定的t，尋求二元函數(shù)F(x,y,t)的最小值，也可用逐次極值法，比如固定y，求出關(guān)于x的最小值，得到區(qū)域Dt中的優(yōu)勢曲線，分析該優(yōu)勢曲線即可確定優(yōu)勢函數(shù)φ(t).

在尋求優(yōu)勢曲線時，可以用微分法.例如對于二維問題

minf(x,y)，

s.t.a≤x≤b，c(x)≤y≤d(x)，

先固定x，令f′y(x,y)=0，求出駐點y=y0(x)(可能不止一個解)，比較函數(shù)值

f(x,y0(x))，f(x,c(x))，f(x,d(x))，

其中最小者對應(yīng)的y值y=u(x)(u(x)等于y0(x)或c(x)或d(x))，便給出了優(yōu)勢曲線.然后代入目標(biāo)函數(shù)，得到優(yōu)勢函數(shù)φ(x)=f(x,u(x))，化簡后令φ′(x)=0，解得駐點x=x0. 再比較函數(shù)值φ(x0)，φ(a)和φ(b)，就可得到目標(biāo)函數(shù)f(x,y)的最小值.

顯然，這個算法對于開放的無界區(qū)域也適用，比如約束區(qū)域為D：a≤x<+∞，c(x)≤y≤d(x)，這時優(yōu)勢函數(shù)φ(x)的最優(yōu)值可以通過比較φ(x0)，φ(a)和φ(+∞)φ(x)加以認定.目標(biāo)函數(shù)f(x,y)在無界區(qū)域未必有最優(yōu)值，判斷最優(yōu)性的難度增大，而逐次極值法在低維度下進行最優(yōu)性判斷相對比較容易.

如果目標(biāo)函數(shù)f(x,y)的約束區(qū)域為D：a(y)≤x≤b(y)，c≤y≤d，則先固定y，令f′x(x,y)=0，求出x的駐點. 經(jīng)比較函數(shù)值可得優(yōu)勢曲線x=v(y)，優(yōu)勢函數(shù)為φ(y)=f(v(y),y)，化簡后令φ′(y)=0，解得駐點y=y0.再與端點y=c，y=d比較，即可得到目標(biāo)函數(shù)f(x,y)的最小值.

如果目標(biāo)函數(shù)f(x,y)的可微性較好，沒有病態(tài)特征，那么上述判別最優(yōu)性的函數(shù)值比較過程可以省略，利用唯一駐點或唯一極值點就是最優(yōu)點的原理，直接認定優(yōu)勢曲線.

對于比較簡單的目標(biāo)函數(shù)，尋求優(yōu)勢曲線還可以用初等方法.常見的初等方法是利用算術(shù)平均與幾何平均的關(guān)系.初等方法的好處是省卻了最優(yōu)性判斷，在獲得駐點的同時便已完成最優(yōu)性的證明.

逐次極值法是對各個變量逐次尋優(yōu)，顯然可推廣到更多元的函數(shù)，當(dāng)然也適用于求函數(shù)的最大值.定理1并未限定Ω為有界閉區(qū)域，其應(yīng)用性相當(dāng)廣泛.

逐次極值法的基本算法為：針對多元函數(shù)，選定其中一個變量選優(yōu)，其余變量固定為常數(shù)；完成單元函數(shù)選優(yōu)后，將目標(biāo)函數(shù)化為低一維的函數(shù)；重復(fù)這一選優(yōu)過程，直至降維到一元優(yōu)勢函數(shù)；對此一元優(yōu)勢函數(shù)尋優(yōu)，便得到原目標(biāo)函數(shù)的最優(yōu)值.

2 逐次極值法的應(yīng)用案例

2.1 用初等方法求優(yōu)勢曲線

初等方法除了前面提到的算術(shù)平均不小于幾何平均外，還有二次函數(shù)極值法和幾何直線最短法等.

圖1 管線鋪設(shè)示意圖

例1[2]油管鋪設(shè)問題.如圖1所示，鐵路線(x軸)同側(cè)有兩個煉油廠A(0,a)和B(c,b)，a≤b，長度單位為km.現(xiàn)欲在鐵路線上增建一個車站P(x,0)，用來運送成品油，希望管線建設(shè)費用最少.管線鋪設(shè)費用為r萬元/km；若安排共用管線，則其費用為p萬元/km (r≤p<2r).

解方案設(shè)計的關(guān)鍵決策點是交匯點Q(x,y).點到直線的距離垂線最短，故共用管線PQ垂直于x軸；又兩點間直線最短，所以鋪設(shè)的管線由直線段AQ,BQ,PQ構(gòu)成.于是需要最小化的總費用w可用二元函數(shù)表示為

可行域為有界閉區(qū)域D：0≤x≤c，0≤y≤a.

先固定y，用幾何方法求|AQ|+|BQ|的最小值：作平行于x軸、高度為y的直線，如圖1中虛線所示，在y軸上作點A關(guān)于該直線的對稱點A1(0,2y-a)，則直線A1B給出|AQ|+|BQ|的最小值.利用圖中兩個直角三角形的比例關(guān)系，容易求得點Q的橫坐標(biāo)為

此方程給出優(yōu)勢曲線，因為兩點間直線最短，所以其最優(yōu)性不必另行判定.將優(yōu)勢曲線方程代入目標(biāo)函數(shù)f(x,y)，或者直接求出直線A1B的長度，可得優(yōu)勢函數(shù)

將y*的表達式回代到優(yōu)勢曲線方程，可得最優(yōu)點Q的橫坐標(biāo)為

若需對最優(yōu)性作嚴(yán)格認定，則可將導(dǎo)數(shù)作通分、有理化變形為

再討論φ′(y)的符號.

2.2 優(yōu)勢曲線有尖點的情形

優(yōu)勢曲線y=u(x)通過比較函數(shù)值獲得，u(x)可能等于駐點y0(x)，也可能等于端點c(x)或d(x). 如果對于不同的x，u(x)的取值對象不同，那么優(yōu)勢曲線就會分段給出，形成尖點.在這種情況下，要關(guān)注適當(dāng)?shù)挠懻?

例2求解二維問題

maxf(x,y)=x3-10x2+4xy-2y2+13x+6，

s.t. 0≤x≤7，0≤y≤3.

解先固定x，則f(x,y)是y的二次函數(shù).當(dāng)0≤x≤3時，在駐點y=x處取得最大值；當(dāng)3

將此y代入f(x,y)，得到優(yōu)勢函數(shù)

對于0≤x≤3，令φ′(x)=3x2-16x+13=0，得[0,3]內(nèi)的駐點x=1；對于3

φ(0)=6，φ(1)=12，φ(3)=0，φ(5)=-12，φ(7)=16.

其中φ(7)=16最大，對應(yīng)的最優(yōu)點為x*=7，y*=3，最大值為maxf(x,y)=f(7,3)=16.

若按經(jīng)典的二元函數(shù)極值法，令f′x(x,y)=f′y(x,y)=0，得到可行域內(nèi)的唯一駐點x=y=1，但f(1,1)=12并非最大值，還需在4條邊界x=0，x=7，y=0，y=3處，分別求函數(shù)

f(0,y)=-2y2+6，

f(7,y)=-50+28y-2y2，

f(x,0)=x3-10x2+13x+6,

f(x,3)=x3-10x2+25x-12

的最大值再作比較，求后兩個函數(shù)最大值的計算量較大，最后也得到maxf(x,y)=f(7,3)=16.

2.3 逐次選優(yōu)過程中的靈活應(yīng)變

當(dāng)變量個數(shù)較多時，逐次極值法面對多個選優(yōu)過程，這些過程相對獨立，從而可針對個性化特征，采用不同的方法靈活處置.

圖2 場地圍墻示意圖

例3建筑材料問題.一塊場地由矩形和等腰梯形拼接而成，如圖2所示，場地的面積為S=4280m2；四周的圍墻寬度有額定要求：CP和DQ段為δ=0.2m，PQ段為aδ，AB段為bδ，AC和BD段為cδ. 這里的a,b,c是圍墻的寬度比，其中c≥1.為了節(jié)省墻體材料，需要確定各段墻的長度，使得用料最少，前提是保持場地面積不變，各段墻的寬度不變.

場地面積的計算公式為S=2HR+y(1+x)R2.在面積公式中解出H代入目標(biāo)函數(shù)，并去掉與最小化無關(guān)的公因子δ，得到三元優(yōu)化問題

運用逐次極值法，先將x,y看作常數(shù)，記

則

當(dāng)且僅當(dāng)左端兩項相等，即

繼續(xù)運用逐次極值法，將x看作常數(shù)，求f(x,y)的最小值即可.令

得到駐點

求出二階導(dǎo)數(shù)，不難發(fā)現(xiàn)f″yy(x,y)>0，因而f′y(x,y)在駐點兩側(cè)左負右正，所以f(x,y)在該駐點處取得最小值，即上述方程給出優(yōu)勢曲線.回代到f(x,y)即得優(yōu)勢函數(shù)

求優(yōu)勢函數(shù)φ(x)的最小值難以用微分法，因為方程φ′(x)=0整理后是一個關(guān)于x的4次方程.于是轉(zhuǎn)而用數(shù)值搜索的方法，取定一組墻寬的比值a=0.8,b=0.9,c=1.1.對x∈[0,1]，計算φ(x)的值，從中找出最小值，這是一維搜索，可在Excel表中完成.數(shù)值搜索的結(jié)果是：當(dāng)x=0.6794時，優(yōu)勢函數(shù)取得最小值minφ(x)=3.27853486.回代到前面的優(yōu)勢曲線(曲面)方程可得y=0.3789，R=36.1312. 代入面積約束公式可算得H的值，進而計算圍墻各段的長度

2R*=72.26 m， 2r*=49.10 m，h*=13.69 m，H*=47.73 m.

3 逐次極值法的優(yōu)點

從以上案例可以看出，逐次極值法相對于經(jīng)典方法有以下優(yōu)點：

(i)逐次極值法每次選優(yōu)都針對一元函數(shù)，原理簡單，方法多樣，微分方法、初等方法可以靈活處置，對已知參數(shù)的討論也比較方便(參看例1)；

(ii)一元函數(shù)的最優(yōu)性認定方法豐富、成熟、有效，如導(dǎo)數(shù)的符號，不等式的現(xiàn)成結(jié)論等，所以逐次極值法對于最優(yōu)性的論證可以做得很充分；

(iii)逐次極值法的每一步都可利用優(yōu)勢曲線(曲面)將目標(biāo)函數(shù)降維并化簡，為后繼尋優(yōu)帶來很大便利，還能像例2那樣，省去許多不必要的計算；

(iv)有許多極值問題沒有解析解，如例3，令三個偏導(dǎo)數(shù)等于零，難以整體推演，需要作多維數(shù)值搜索，而逐次極值法能夠?qū)㈦y點后移，只需作一維搜索，并且求解的脈絡(luò)清晰.

[參 考 文 獻]

[1] 菲赫金戈爾茲 ГМ.微積分學(xué)教程(一卷二分冊)[M].葉彥謙譯.北京：高等教育出版社，1959：376-431.

[2] 全國大學(xué)生數(shù)學(xué)建模競賽組委會.2010高教社杯全國大學(xué)生數(shù)學(xué)建模競賽(CUMCM)題目C題[EB/OL].[2010-09-09] http:∥www.mcm.edu.cn/