多目標(biāo)規(guī)劃培訓(xùn)教材-課件

MATLAB求解多目標(biāo)規(guī)劃江西師范大學(xué)數(shù)信學(xué)院吳根秀MATLAB求解多目標(biāo)規(guī)劃江西師范大學(xué)數(shù)信學(xué)院吳根秀一、0-1規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINf’xS.T.Ax<=bAeqx=beqx=0,1命令格式：x=bintprog(f)x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)x=bintprog(f,A,b,Aeq,beq,x0)x=bintprog(f,A,b,Aeq,beq,x0,options)[x,fval]=bintprog(...)[x,fval,exitflag]=bintprog(...)[x,fval,exitflag,output]=bintprog(...)一、0-1規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINf’x數(shù)學(xué)模型：MINlambdaS.T.F(x)-weight*lambda<=goal(達(dá)到目標(biāo)）Ax<=b（線性不等式約束）Aeqx=beq（線性等式約束）C(x)<=0（非線性不等式約束）Ceq(x)=0（非線性等式約束）lb<=x<=ubF=[f1(x),f2(x),…]為多目標(biāo)的目標(biāo)函數(shù)；F與[C(x),Ceq(x)]都是通過function來定義；命令格式：x=fgoalattain(fun,x0,goal,weight)x=fgoalattain(fun,x0,goal,weight,A,b)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)二、多目標(biāo)規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINlambda二、多目標(biāo)規(guī)劃的MATLAB求命令格式：x=fgoalattain(fun,x0,goal,weight)x=fgoalattain(fun,x0,goal,weight,A,b)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,...lb,ub,nonlcon,options)[x,fval]=fgoalattain(...)[x,fval,attainfactor]=fgoalattain(...)[x,fval,attainfactor,exitflag]=fgoalattain(...)[x,fval,attainfactor,exitflag,output]=fgoalattain(...)[x,fval,attainfactor,exitflag,output,lambda]=fgoalattain(...)二、多目標(biāo)規(guī)劃的MATLAB求解命令格式：二、多目標(biāo)規(guī)劃的MATLAB求解x=fgoalattain(@myfun,x0,goal,weight,A,b,Aeq,beq,...lb,ub,@mycon)wheremyconisaMATLABfunctionsuchasfunction[c,ceq]=mycon(x)c=...%computenonlinearinequalitiesatx.ceq=...%computenonlinearequalitiesat二、多目標(biāo)規(guī)劃的MATLAB求解x=fgoalattain(@myfun,x0,goal,weight)wheremyfunisaMATLABfunctionsuchasfunctionF=myfun(x)F=...%Computefunctionvaluesatx.x=fgoalattain(@myfun,x0,goal有關(guān)優(yōu)化參數(shù)設(shè)置：options=optimset(‘GradObj’,‘on’)目標(biāo)函數(shù)的梯度方向參數(shù)設(shè)置為‘on’時(shí)，用下列函數(shù)定義：function[F,G]=myfun(x)F=...%Computethefunctionvaluesatxifnargout>1%TwooutputargumentsG=...%GradientsevaluatedatxEndThegradientconsistsofthepartialderivativedF/dxofeachFatthepointx.二、多目標(biāo)規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：二、多目標(biāo)規(guī)劃的MATLAB求解二、多目標(biāo)規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：options=optimset(‘GradConstr’,‘on’）約束條件的梯度方向參數(shù)設(shè)置為‘on’時(shí)，用下列函數(shù)定義：function[c,ceq,GC,GCeq]=mycon(x)c=...%Nonlinearinequalitiesatxceq=...%Nonlinearequalitiesatxifnargout>2%Nonlconcalledwith4outputsGC=...%GradientsoftheinequalitiesGCeq=...%GradientsoftheequalitiesEnd注意：一般weight=abs(goal)二、多目標(biāo)規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：模型：x’=(A+BKC)x+Bu，設(shè)計(jì)K滿足目標(biāo)：Y=Cx1）循環(huán)系統(tǒng)的特征值（由命令eig(A+B*K*C)確定）的目標(biāo)為goal=[-5,-3,-1]2）K中元素均在[-4,4]中;設(shè)特征值的weight=abs(goal),定義目標(biāo)函數(shù)F如下：functionF=eigfun(K,A,B,C)F=sort(eig(A+B*K*C));%Evaluateobjectives，由小到大排列優(yōu)化程序?yàn)椋篈=[-0.500;0-210;01-2];B=[10;-22;01];C=[100;001];K0=[-1-1;-1-1];%Initializecontrollermatrixgoal=[-5-3-1];%Setgoalvaluesfortheeigenvaluesweight=abs(goal)%Setweightforsamepercentagelb=-4*ones(size(K0));%Setlowerboundsonthecontrollerub=4*ones(size(K0));%Setupperboundsonthecontrolleroptions=optimset('Display','iter');%Setdisplayparameter[K,fval,attainfactor]=fgoalattain(@(K)eigfun(K,A,B,C)...goal,weight,[],[],[],[],lb,ub,[],options)二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題模型：x’=(A+BKC)x+Bu，設(shè)計(jì)K滿足目標(biāo)：二、舉例運(yùn)行結(jié)果如下Activeconstraints:124910K=-4.0000-0.2564-4.0000-4.0000fval=-6.9313-4.1588-1.4099attainfactor=-0.3863二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題運(yùn)行結(jié)果如下二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標(biāo)精確匹配，設(shè)置‘GoalsExactAchieve’參數(shù)值為3options=optimset('GoalsExactAchieve',3);[K,fval,attainfactor]=fgoalattain(...@(K)eigfun(K,A,B,C),K0,goal,weight,[],[],[],[],lb,ub,[],...options)Afteraboutseveniterations,asolutionisK=-1.59541.2040-0.4201-2.9046fval=-5.0000-3.0000-1.0000attainfactor=1.0859e-20表明目標(biāo)已完全匹配二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標(biāo)精確匹配，設(shè)置‘GoalsEx謝謝！謝謝！

初等模型舉例多目標(biāo)規(guī)劃培訓(xùn)教材-課件

常見類型定性模型經(jīng)驗(yàn)公式（擬合、插值）量綱分析比例模型常見類型定性模型§2.1

崖高的估算假如你站在崖頂且身上帶著一只具有跑表功能的計(jì)算器，你也許會(huì)出于好奇心想用扔下一塊石頭聽回聲的方法來估計(jì)山崖的高度，假定你能準(zhǔn)確地測(cè)定時(shí)間，你又怎樣來推算山崖的高度呢，請(qǐng)你分析一下這一問題。我有一只具有跑表功能的計(jì)算器?！?.1崖高的估算假如你站在崖頂且身上方法一假定空氣阻力不計(jì)，可以直接利用自由落體運(yùn)動(dòng)的公式來計(jì)算。例如，設(shè)t=4秒，g=9.81米/秒2，則可求得h≈78.5米。

我學(xué)過微積分，我可以做得更好，呵呵。

方法一假定空氣阻力不計(jì)，可以直接利用自由落體運(yùn)動(dòng)的公式我學(xué)除去地球吸引力外，對(duì)石塊下落影響最大的當(dāng)屬空氣阻力。根據(jù)流體力學(xué)知識(shí)，此時(shí)可設(shè)空氣阻力正比于石塊下落的速度，阻力系數(shù)K為常數(shù)，因而，由牛頓第二定律可得：

令k=K/m，解得

代入初始條件v(0)=0，得c=－g/k，故有

再積分一次，得：

除去地球吸引力外，對(duì)石塊下落影響最大的當(dāng)屬空氣阻力。根若設(shè)k=0.05并仍設(shè)t=4秒，則可求得h≈73.6米。

聽到回聲再按跑表，計(jì)算得到的時(shí)間中包含了反應(yīng)時(shí)間

進(jìn)一步深入考慮不妨設(shè)平均反應(yīng)時(shí)間為0.1秒，假如仍設(shè)t=4秒，扣除反應(yīng)時(shí)間后應(yīng)為3.9秒，代入式①，求得h≈69.9米。

①多測(cè)幾次，取平均值再一步深入考慮代入初始條件h(0)=0，得到計(jì)算山崖高度的公式：

將e-kt用泰勒公式展開并令k→0+

，即可得出前面不考慮空氣阻力時(shí)的結(jié)果。若設(shè)k=0.05并仍設(shè)t=4秒，則可求得h≈73.6米。還應(yīng)考慮回聲傳回來所需要的時(shí)間。為此，令石塊下落的真正時(shí)間為t1，聲音傳回來的時(shí)間記為t2，還得解一個(gè)方程組：這一方程組是非線性的，求解不太容易，為了估算崖高竟要去解一個(gè)非線性主程組似乎不合情理

相對(duì)于石塊速度，聲音速度要快得多，我們可用方法二先求一次

h，令t2=h/340，校正t，求石塊下落時(shí)間t1≈t-t2將t1代入式①再算一次，得出崖高的近似值。例如，若h=69.9米，則t2≈0.21秒，故t1≈3.69秒，求得h≈62.3米。還應(yīng)考慮回聲傳回來所需要的時(shí)間。為此，令石塊下落的真§2.2

錄像帶還能錄多長(zhǎng)時(shí)間錄像機(jī)上有一個(gè)四位計(jì)數(shù)器，一盤180分鐘的錄像帶在開始計(jì)數(shù)時(shí)為0000，到結(jié)束時(shí)計(jì)數(shù)為1849，實(shí)際走時(shí)為185分20秒。我們從0084觀察到0147共用時(shí)間3分21秒。若錄像機(jī)目前的計(jì)數(shù)為1428，問是否還能錄下一個(gè)60分鐘的節(jié)目？§2.2錄像帶還能錄多長(zhǎng)時(shí)間錄像機(jī)上有一個(gè)四位計(jì)數(shù)器，一rθRl由得到又因和得

積分得到即從而有我們希望建立一個(gè)錄像帶已錄像時(shí)間t與計(jì)數(shù)器計(jì)數(shù)n之間的函數(shù)關(guān)系。為建立一個(gè)正確的模型，首先必須搞清哪些量是常量，哪些量是變量。首先，錄像帶的厚度W是常量，它被繞在一個(gè)半徑為r的園盤上，見圖。磁帶轉(zhuǎn)動(dòng)中線速度v顯然也是常數(shù)，否則圖象聲音必然會(huì)失真。此外，計(jì)數(shù)器的讀數(shù)n與轉(zhuǎn)過的圈數(shù)有關(guān)，從而與轉(zhuǎn)過的角度θ成正比。rθRl由得到又rθRl

此式中的三個(gè)參數(shù)W、v和r均不易精確測(cè)得，雖然我們可以從上式解出t與n的函數(shù)關(guān)系，但效果不佳，故令則可將上式簡(jiǎn)化為：故令上式又可化簡(jiǎn)記成t=an2+bn

rθRl此式中的三個(gè)參數(shù)W、v和r均不易精確測(cè)得，雖然我們t=an2+bn

rθRl上式以a、b為參數(shù)顯然是一個(gè)十分明智的做法，它為公式的最終確立即參數(shù)求解提供了方便。將已知條件代入，得方程組：從后兩式中消去t1，解得a=0.0000291,b=0.04646,故t=0.0000291n2+0.04646n，令n=1428，得到t=125.69（分）由于一盒錄像帶實(shí)際可錄像時(shí)間為185.33分，故尚可錄像時(shí)間為59.64分，已不能再錄下一個(gè)60分鐘的節(jié)目了。

t=an2+bnrθRl上式以a、b為參數(shù)顯然是一個(gè)十分在解決實(shí)際問題時(shí)，注意觀察和善于想象是十分重要的，觀察與想象不僅能發(fā)現(xiàn)問題隱含的某些屬性，有時(shí)還能順理成章地找到解決實(shí)際問題的鑰匙。本節(jié)的幾個(gè)例子說明，猜測(cè)也是一種想象力。沒有合理而又大膽的猜測(cè)，很難做出具有創(chuàng)新性的結(jié)果。開普勒的三大定律（尤其是后兩條）并非一眼就能看出的，它們隱含在行星運(yùn)動(dòng)的軌跡之中，隱含在第谷記錄下來的一大堆數(shù)據(jù)之中。歷史上這樣的例子實(shí)在太多了。在獲得了一定數(shù)量的資料數(shù)據(jù)后，人們常常會(huì)先去猜測(cè)某些結(jié)果，然后試圖去證明它。猜測(cè)一經(jīng)證明就成了定理，而定理一旦插上想象的翅膀，又常常會(huì)被推廣出許多更為廣泛的結(jié)果。即使猜測(cè)被證明是錯(cuò)誤的，結(jié)果也決不是一無所獲的失敗而常常是對(duì)問題的更為深入的了解?！?.3最短路徑與最速方案問題在解決實(shí)際問題時(shí)，注意觀察和善于想象是十分重要的，觀察與想象例5（最短路徑問題）設(shè)有一個(gè)半徑為r的圓形湖，圓心為O。A、B

位于湖的兩側(cè)，AB連線過O，見圖。現(xiàn)擬從A點(diǎn)步行到B點(diǎn)，在不得進(jìn)入湖中的限制下，問怎樣的路徑最近。

ABOr將湖想象成凸出地面的木樁，在AB間拉一根軟線，當(dāng)線被拉緊時(shí)將得到最短路徑。根據(jù)這樣的想象，猜測(cè)可以如下得到最短路徑：過A作圓的切線切圓于E，過B作圓的切線切圓于F。最短路徑為由線段AE、弧EF和線段FB連接而成的連續(xù)曲線（根據(jù)對(duì)稱性，AE′，弧E′F′，F(xiàn)′B連接而成的連續(xù)曲線也是）。EFE′F′例5（最短路徑問題）設(shè)有一個(gè)半徑為r的圓形湖，圓心為以上只是一種猜測(cè)，現(xiàn)在來證明這一猜測(cè)是正確的。為此，先介紹一下凸集與凸集的性質(zhì)。定義2.1（凸集）稱集合R為凸集，若x1、x2∈R及λ∈[0，1]，總有λx1+（1+λ）x2∈R。即若x1、x2∈R，則x1、x2的連線必整個(gè)地落在R中。定理2.2（分離定理）對(duì)平面中的凸集R與R外的一點(diǎn)K，存在直線l,l

分離R與K，即R與K分別位于l的兩側(cè)（注：對(duì)一般的凸集R與R外的一點(diǎn)K，則存在超平面分離R與K），見圖。klR下面證明猜想以上只是一種猜測(cè)，現(xiàn)在來證明這一猜測(cè)是正確的。為此，先介紹一猜測(cè)證明如下：（方法一）顯然，由AE、EF、FB及AE′，E′F′，F(xiàn)′B圍成的區(qū)域R是一凸集。利用分離定理易證最短徑不可能經(jīng)過R外的點(diǎn)，若不然，設(shè)Γ為最短路徑，Γ過R外的一點(diǎn)M，則必存在直線l分離M與R，由于路徑Γ是連續(xù)曲線，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。這樣，直線段M1M2的長(zhǎng)度必小于路徑M1MM2的長(zhǎng)度，與Γ是A到B的最短路徑矛盾，至此，我們已證明最短路徑必在凸集R內(nèi)。不妨設(shè)路徑經(jīng)湖的上方到達(dá)B點(diǎn)，則弧EF必在路徑F上，又直線段AE是由A至E的最短路徑，直線FB是由F到B的最短路徑，猜測(cè)得證。ABOrEFE′F′M1M2MΓl猜測(cè)證明如下：（方法一）顯然，由AE、EF、FB及AE′，還可用微積分方法求弧長(zhǎng)，根據(jù)計(jì)算證明滿足限止條件的其他連續(xù)曲線必具有更大的長(zhǎng)度；此外，本猜測(cè)也可用平面幾何知識(shí)加以證明等。根據(jù)猜測(cè)不難看出，例5中的條件可以大大放松，可以不必設(shè)AB過圓心，甚至可不必設(shè)湖是圓形的。例如對(duì)下圖，我們可斷定由A至B的最短路徑必為l1與l2之一，其證明也不難類似給出。ABl1l2D到此為止，我們的研討還只局限于平面之中，其實(shí)上述猜測(cè)可十分自然地推廣到一般空間中去。1973年，J.W.Craggs證明了以上結(jié)果：若可行區(qū)域的邊界是光滑曲面。則最短路徑必由下列弧組成，它們或者是空間中的自然最短曲線，或者是可行區(qū)域的邊界弧。而且，組成最短路徑的各段弧在連接點(diǎn)處必定相切。還可用微積分方法求弧長(zhǎng)，根據(jù)計(jì)算證明滿足限止條件的其他連續(xù)曲例6

一輛汽車停于A處并垂直于AB方向，此汽車可轉(zhuǎn)的最小圓半徑為R，求不倒車而由A到B的最短路徑。解（情況1）若|AB|>2R，最短路徑由弧AC與切線BC組成（見圖①

）。（情況2）若|AB|<2R，則最短路徑必居于圖②（a）、（b）兩曲線之中。可以證明，（b）中的曲線ABC更短。AR2RBRC①②ABoC（a）CABo1o2（b）例6一輛汽車停于A處并垂直于AB方向，此解（情況1）若例7

駕駛一輛停于A處與AB成θ1角度的汽車到B處去，已知B處要求的停車方向必須與AB成θ2角，試找出最短路徑（除可轉(zhuǎn)的最小圓半徑為R外，不受其他限止）。解根據(jù)Craggs定理并稍加分析可知，最短路徑應(yīng)在l1與l2中，見圖，比較l1與l2的長(zhǎng)度，即可得到最短路徑。Al1l2Bθ2θ1例7駕駛一輛停于A處與AB成θ1角度的汽解根據(jù)Cra最速方案問題例8

將一輛急待修理的汽車由靜止開始沿一直線方向推至相隔S米的修車處，設(shè)阻力不計(jì)，推車人能使車得到的推力f滿足:-B≤f≤A,f>0為推力，f<0為拉力。問怎樣推車可使車最快停于修車處。

設(shè)該車的運(yùn)動(dòng)速度為υ=υ(t)，根據(jù)題意，υ(0)=υ(T)=0，其中T為推車所花的全部時(shí)間。由于-B≤f≤A，且f=mυ′，可知-b≤υ′≤a（其中m為汽車質(zhì)量，a=A/m,b=B/m）。據(jù)此不難將本例歸納為如下的數(shù)學(xué)模型：

minT

υ(0)=υ(T)=0最速方案問題例8將一輛急待修理的汽車由靜止開始沿一此問題為一泛函極值問題，求解十分困難，為得出一個(gè)最速方案。我們作如下猜測(cè)：猜測(cè)最速方案為以最大推力將車推到某處，然后以最大拉力拉之，使之恰好停于修車處，其中轉(zhuǎn)換點(diǎn)應(yīng)計(jì)算求出證明設(shè)υ=υ(t)為在最速推車方案下汽車的速度，則有。設(shè)此方案不同于我們的猜測(cè)。現(xiàn)從O點(diǎn)出發(fā)，作射線y=at；從（t,0）出發(fā)，作直線y=-b(t-T)交y=at于A，由于，曲線υ=υ(t)必位于三角形區(qū)域DAT的內(nèi)部，從而有ΔOAT的面積大于S。在O到T之間任取一點(diǎn)T′

，過T′作AT的平行線交OA于A′

。顯然ΔOA′T′的面積S（T′）是T′的連續(xù)函數(shù)，當(dāng)T′=0時(shí)S（0）=0，當(dāng)T′=T時(shí)，S（T）>S，故由連續(xù)函數(shù)的性質(zhì)存在某T′<T，S（T′）=S但這一結(jié)果與υ=υ(t)是最優(yōu)方案下的車速的假設(shè)矛盾，因?yàn)橛梦覀儾聹y(cè)的推車方法推車，只需T′時(shí)間即可將車推到修車處，而T′<T。oυtAT′TA′Sy=aty=-b(t-T)此問題為一泛函極值問題，求解十分困難，為得出一個(gè)最速方案。我邏輯模型多目標(biāo)規(guī)劃培訓(xùn)教材-課件例1

擬將一批尺寸為1×2×4的的商品裝入尺寸為6×6×6的正方體包裝箱中，問是否存在一種裝法，使裝入的該商品正好充滿包裝箱。解

將正方體剖分成27個(gè)2×2×2的小正方體，并按下圖所示黑白相間地染色。再將每一2×2×2的小正方體剖分成1×1×1的小正方體。易見，27個(gè)2×2×2的正方體中，有14個(gè)是黑的，13個(gè)是白的（或13黑14白），故經(jīng)兩次剖分，共計(jì)有112個(gè)1×1×1的黑色小正方體和104個(gè)1×1×1的白色小正方體。雖然包裝箱的體積恰好是商品體積的27倍，但容易看到，不論將商品放置在何處，它都將占據(jù)4個(gè)黑色和4個(gè)白色的1×1×1小正方體的位置，故商品不可能充滿包裝箱。例1擬將一批尺寸為1×2×4的的商品裝入尺寸為6×6

德國著名的藝術(shù)家AlbrechtDürer(1471-1521)于1514年曾鑄造了一枚名為“MelencotiaI”的銅幣。令人奇怪的是在這枚銅幣的畫面上充滿了數(shù)學(xué)符號(hào)、數(shù)字及幾何圖形。這里，我們僅研究銅幣右上角的數(shù)字問題

例2.Dürer魔方（或幻方）問題德國著名的藝術(shù)家AlbrechtDürer(147所謂的魔方是指由1~n2這n2個(gè)正整數(shù)按一定規(guī)則排列成的一個(gè)n行n列的正方形。n稱為此魔方的階。Dürer魔方：4階，每一行之和為34，每一列之和為34，對(duì)角線（或反對(duì)角線）之和是34，每個(gè)小方塊中的數(shù)字之和是34，四個(gè)角上的數(shù)字加起來也是34什么是Dürer魔方多么奇妙的魔方！銅幣鑄造時(shí)間：1514年

所謂的魔方是指由1~n2這n2個(gè)正整數(shù)按一定規(guī)則排列成的一個(gè)

構(gòu)造魔方是一個(gè)古老的數(shù)學(xué)游戲，起初它還和神靈聯(lián)系在一起，帶有深厚的迷信色彩。傳說三千二百多年前（公元前2200年），因治水出名皇帝大禹就構(gòu)造了三階魔方（被人們稱“洛書”），至今還有人把它當(dāng)作符咒用于某些迷信活動(dòng)，大約在十五世紀(jì)時(shí)，魔方傳到了西方，著名的科尼利厄斯·阿格里帕（1486-1535）先后構(gòu)造出了3~9階的魔方。構(gòu)造魔方是一個(gè)古老的數(shù)學(xué)游戲，起初它還和神靈聯(lián)系在如何構(gòu)造魔方奇數(shù)（不妨n=5）階的情況Step1:在第一行中間寫1Step2:每次向右上方移一格依次填按由小到大排列的下一個(gè)數(shù)，向上移出界時(shí)填下一列最后一行的小方格；向右移出界時(shí)填第一列上一行的小方格。若下面想填的格已填過數(shù)或已達(dá)到魔方的右上角時(shí)，改填剛才填的格子正下方的小方格，繼續(xù)Step2直到填完12345678910111213141516171819202122232425偶數(shù)階的情況

偶數(shù)階的魔方可以利用奇數(shù)階魔方拼接而成，拉爾夫·斯特雷奇給出了一種拼接的方法，這里不作詳細(xì)介紹如何構(gòu)造魔方奇數(shù)（不妨n=5）階的情況Step1:在第五階沒人知道有多少個(gè)?。?！三階1個(gè)反射和中心旋轉(zhuǎn)生成8個(gè)四階880個(gè)反射和中心旋轉(zhuǎn)生成7040個(gè)魔方數(shù)量隨階數(shù)n增長(zhǎng)的速度實(shí)在是太驚人了！同階魔方的個(gè)數(shù)五階沒人知道有多少個(gè)?。?！三階允許構(gòu)成魔方的數(shù)取任意實(shí)數(shù)允許取實(shí)數(shù)

n階魔方A、B，任意實(shí)數(shù)α、βαA+βB是n階魔方具有指定性質(zhì)的魔方全體構(gòu)成一個(gè)線性空間問題已發(fā)生了實(shí)質(zhì)性變化注：刻畫一個(gè)線性空間只需指出它的維數(shù)并求出此線性空間的一組基底松馳問題的討論允許構(gòu)成魔方的數(shù)取任意實(shí)數(shù)允許取實(shí)數(shù)n階魔方A、

1在第一行中共有4種取法，為保持上述性質(zhì)的成立，第二行中的1還有兩種取法。當(dāng)?shù)诙械?也取定后，第三行與第四行的1就完全定位了，故一共可作出8個(gè)不同的最簡(jiǎn)方陣，稱之為基本魔方并記之為Q1，…，Q8

仍以4階方陣為例。令R為行和，C為列和，D為對(duì)角線和，S為小方塊和定義0-方：R=C=D=S=0定義1-方：R=C=D=S=4R=C=D=S=1的方陣構(gòu)成的線性空間具有什么樣的性質(zhì)？類似于構(gòu)造n維歐氏空間的標(biāo)準(zhǔn)基，利用0和1我們來構(gòu)造一些R=C=D=S=1的最簡(jiǎn)單的方陣。1在第一行中共有4種取法，為保持上述性質(zhì)的

顯然，Dürer空間（簡(jiǎn)稱D空間）中任何一個(gè)元素都可以用Q1，Q2，…，Q8來線性表示，但它們能否構(gòu)成D空間的一組基呢？

顯然，Dürer空間（簡(jiǎn)稱D空間）中任何一容易看出：Q1，…，Q8這8個(gè)基本方是線性相關(guān)的，即至少存在一個(gè)Qj，可以通過其它7個(gè)基本方的線性組合得到。這8個(gè)基本方的地位是等同的，故可不妨設(shè)j=8。下面驗(yàn)證Q1，Q2，…，Q7是否線性相關(guān)。

令：，即=容易看出：Q1，…，Q8這8個(gè)基本方是線性相關(guān)的，即至少存在等號(hào)兩邊對(duì)應(yīng)元素相比較，得r1=r2=…=r7=0，所以是線性無關(guān)是D空間的最小生成集。

令D

即解方程組：

=

解得

D=研究AlbrechtDürer鑄造的銅幣等號(hào)兩邊對(duì)應(yīng)元素相比較，得r1=r2=…=r7=0，是D空間2004年浙江大學(xué)數(shù)學(xué)建模競(jìng)賽（B題）通訊衛(wèi)星上的開關(guān)設(shè)置

地面上存在著n個(gè)接收站與n個(gè)發(fā)送站，而在通訊衛(wèi)星上則設(shè)置了若干種開關(guān)模式。開關(guān)模式可用矩陣P=(pij)來表示，若衛(wèi)星可接收發(fā)送站i發(fā)射的信息并將信息傳送回地面的接收站j時(shí)，矩陣中的元素pij=1，否則pij=0。通訊衛(wèi)星上的接收發(fā)送任務(wù)也可以用一個(gè)矩陣T=（tij）來表示，其元素tij為需經(jīng)通訊衛(wèi)星傳遞的由i發(fā)點(diǎn)發(fā)送到j(luò)接收點(diǎn)的信息量的傳送時(shí)間長(zhǎng)度。由于技術(shù)上的原因，當(dāng)發(fā)送站i在發(fā)送給接收站j信息時(shí)，它不能同時(shí)發(fā)送給別的接收站信息；同樣，當(dāng)接收站j在接收發(fā)送站i的信息時(shí)，也不能同時(shí)接收其他發(fā)送站發(fā)送的信息。你的任務(wù)是：2004年浙江大學(xué)數(shù)學(xué)建模競(jìng)賽

設(shè)計(jì)一組開關(guān)模式，k=1,…,r（注：r應(yīng)當(dāng)盡可能?。?，使得對(duì)任意給定的任務(wù)矩陣T，衛(wèi)星開關(guān)設(shè)置均能完成要求的發(fā)接收任務(wù)。設(shè)計(jì)一個(gè)算法，在發(fā)接收任務(wù)T給出后，可根據(jù)你設(shè)計(jì)的開關(guān)模式（k=1,…,r）求出各開關(guān)的使用時(shí)間λk，使得在完成預(yù)定傳送任務(wù)的前提下使用各開關(guān)模式的總時(shí)間最短。同樣由于技術(shù)上的原因，開關(guān)模式的總數(shù)r有一個(gè)上限。當(dāng)需要傳送的任務(wù)數(shù)數(shù)量較大時(shí)，仍無法分派任務(wù)。請(qǐng)你想一些辦法來解決這一困難，（當(dāng)然，這時(shí)你可能要作出一些犧牲，即傳送時(shí)間可能會(huì)增加一些）。

設(shè)計(jì)一組開關(guān)模式，k=1,…,r（注：r應(yīng)當(dāng)盡可能?。﹩栴}及模型問題的標(biāo)準(zhǔn)形式為：在地面上存在著n個(gè)收站與n個(gè)發(fā)戰(zhàn)，而在通訊衛(wèi)星上則設(shè)置了若干種開關(guān)模式。開關(guān)模式可用矩陣P=(pij)來表示，若衛(wèi)星可接收發(fā)射站i發(fā)射的信息并將信息傳送回地面的接收站j時(shí)，矩陣元素pij=1，否則pij=0。通訊衛(wèi)星的接發(fā)任務(wù)也可用一矩陣T=（tij）來表示，其元素tij為需經(jīng)通訊衛(wèi)星傳遞的由i發(fā)點(diǎn)發(fā)送到j(luò)接受點(diǎn)的信息量的傳送時(shí)間長(zhǎng)度。問題要求求r并設(shè)計(jì)一組開關(guān)模式Pk，k=1,…,r及模式Pk的使用時(shí)間λk，使得在完成預(yù)定傳送任務(wù)的前提下各開關(guān)模式使用的總時(shí)間最短，即要求求解下面的問題：?jiǎn)栴}及模型問題的標(biāo)準(zhǔn)形式為：在地面上存在著n個(gè)收站與n個(gè)發(fā)戰(zhàn)例1

設(shè)

這是一個(gè)有3個(gè)發(fā)送站與3個(gè)接收站的實(shí)例，tij在矩陣中已給出，例如由發(fā)站1傳送到收站1的通訊量為3單位時(shí)間等。分析

容易看出，三個(gè)發(fā)站需傳送的時(shí)間分別為6、5、5；而三個(gè)收站需接收的時(shí)間分別為6、3、7。為完成全部傳送任務(wù)，通訊衛(wèi)星總傳送時(shí)間至少應(yīng)為7單位時(shí)間，即的下界為7。由于技術(shù)上的原因，當(dāng)發(fā)站i在發(fā)送給收站j信息時(shí)，它不能同時(shí)發(fā)送給別的收站信息；同樣，當(dāng)收站j在接收發(fā)站i的信息時(shí)，也不能同時(shí)接收其他發(fā)站發(fā)送的信息。這一要求說明，任一開關(guān)模式Pk應(yīng)具有以下性質(zhì)：（1）Pk的每一行中有且只有一個(gè)1，每一列中也有且只有一個(gè)1；（2）所有的1均位于不同的行列中。滿足（1）、（2）的矩陣被稱為置換矩陣，n階置換矩陣Pk共有n!個(gè)，當(dāng)n較大時(shí)，我們不可能在通訊衛(wèi)星上設(shè)置這么多種不同的開關(guān)模式。因而，為了設(shè)計(jì)出切實(shí)可行的開關(guān)模式，我們還得另想辦法。例1設(shè)這是一個(gè)有3個(gè)發(fā)送站與3個(gè)接收站的實(shí)例，tij在（設(shè)計(jì)方法1）注意到Pk每行（或列）元素之和均為1，故不管如何指派開關(guān)的使用時(shí)間（即不論如何取λk），矩陣均具有某些特殊的性質(zhì)，例如其行和（及列和）均為同一常數(shù)。這樣的矩陣構(gòu)成一個(gè)線性空間（參見邏輯模型第一節(jié)Dürer魔方），為減少開關(guān)模式的種類，可取此空間的一組基底作為開關(guān)模式。在使用這種開關(guān)模式時(shí)，無論T的元素tij怎么取，通訊衛(wèi)星對(duì)每一發(fā)（收）點(diǎn)的開通時(shí)間總和是恒定的。在這種開關(guān)模式下，可按如下方式指派各開關(guān)模式的使用時(shí)間：步1先將T改變?yōu)?，滿足：（1）≥T（2）記，步2用Pk表示，即將分解為（r為空間的維數(shù)）（設(shè)計(jì)方法1）注意到Pk每行（或列）元素之和均為1，故不管如將T化為的方法一般有無窮多種，如可如下化法：令事實(shí)上，，（即通訊衛(wèi)星傳送總時(shí)間的下界）。令其中用這種方法化例中的T，得到的任一行（或列）中元素之和均為7。將T化為的方法一般有無窮多種，如可如下化法：令定義1稱行和、列%%和均相等的矩陣為雙隨機(jī)矩陣（Doublystochasticmatrix）定理1

（Birkhoff定理，1944）任一n階雙隨機(jī)矩陣均可寫成至多（n－1）2+1個(gè)置換矩陣的非線性組合。的分解可如下進(jìn)行：步1選取由Pij>0可推出>0的置換矩陣P步2確定

步3取，用－代替步4若=0，停；否則，返回步1。例2.

為方便起見，我們來分解一個(gè)元素均為非負(fù)整數(shù)的3階雙隨機(jī)矩陣，（由Birkhoff定理，r≤5）定義1定理1（Birkhoff定理，1944）任一n階雙隨解：取，λ=min{1,3,3}=1分解成，再取

因min{5,5,3}=3，又有，取

解：取于是又有易得分解結(jié)果為：于是又有易得分解結(jié)果為：尚需解決的問題是如何求P，使得Pij>0必有。讀者不難發(fā)現(xiàn)，此問題可以通過求解一個(gè)兩分圖上的最大流（或最大匹配）來實(shí)現(xiàn)，計(jì)算量為O(n4)，是多項(xiàng)式時(shí)間可解的。具體方法為：作一兩分圖，若，則作邊（i,j），令邊容量為1，這樣，可作出P的充要條件是該最大流問題的最大流量為n。對(duì)例9.33，n=3。由于所有，先取

，－P1為

相應(yīng)的兩分圖為：于是又可求得尚需解決的問題是如何求P，使得Pij>0必有，相應(yīng)的兩分圖為：又可得，…，如此下去，直到作不出P為至，由于的特殊性質(zhì)及Birkhoff定理，上述分解必能在不超過r=(n－1)2+1步內(nèi)終止。上述開關(guān)設(shè)計(jì)方法要求在通訊衛(wèi)星上設(shè)置(n－1)2+1種不同的開關(guān)模式（即Pk），當(dāng)n稍大時(shí)，(n－1)2+1仍顯得太大而使得使用時(shí)不便。例如，當(dāng)n=41時(shí)，(n－1)2+1=|60|。為實(shí)用方便，人們研究了限止開關(guān)模式個(gè)數(shù)的相應(yīng)問題。，相應(yīng)的兩分圖為：又可得若要求r≤n，即要求通訊衛(wèi)星上至多設(shè)置n種開關(guān)模式，則問題化為令r≤n，求不超過n個(gè)置換矩陣Pk及λk，使之滿足：minS.t

為了使任意一對(duì)發(fā)射法與接收站之間的傳送均為可能實(shí)現(xiàn)的，自然應(yīng)要求Pk滿足（5.1）

（5.2）

（右面的矩陣有n2個(gè)值為1的分量，每一Pk

恰有n個(gè)1分量）故r=n。容易看出，（5.1）隱含著T的每一元素只能被唯一的P復(fù)蓋，即T的元素在分解中是不可分割的，這當(dāng)然是一個(gè)好性質(zhì)，使實(shí)際操作時(shí)較為方便，但可惜的是對(duì)一般的雙隨機(jī)矩陣，分解很可能無解。若要求r≤n，即要求通訊衛(wèi)星上至多設(shè)置n種開關(guān)模式，則問題化例3

若取，

，

（注意：T已是雙隨機(jī)矩陣，行和列和均為10）則min

S.t

的解為λ1=3，λ2=4，λ3=5。例3若取，，（注意：T已是雙隨機(jī)矩陣，行和列和均為1（大于10）而但等號(hào)經(jīng)常并不成立。1985年，F(xiàn)·Rendel證明，在給定滿足（5.2）的置換矩陣P1,…,Pn后，求解問題（5.1）是NP難的，從而不可能存在多項(xiàng)式時(shí)間算法，除非P=NP?，F(xiàn)要求r≤2n一種自然而方便的開關(guān)設(shè)置為引入兩組各有n個(gè)開關(guān)模式的置換矩陣P1,…,Pn，Q1,…,Qn，滿足下面的（5.3)式：例如，當(dāng)n=3時(shí)，可令：（大于10）而但等號(hào)經(jīng)常并不成立。1985年，F(xiàn)·Rend（注：這種設(shè)置方法保持了其內(nèi)在的對(duì)稱性，不失為一種明智的做法。）現(xiàn)在，我們來分解例9.33中的雙隨機(jī)矩陣，令=，得方程組（注：這種設(shè)置方法保持了其內(nèi)在的對(duì)稱性，不失為一種明智的做法求出各對(duì)角線與反對(duì)角線上的三個(gè)元素之和，并作一些簡(jiǎn)單的消去運(yùn)算；將矩陣的所有元素相加，可得下面的方程組：注意到（5.3），易證空間的維數(shù)為5，故之一可任取，（稍加注意即可保持非負(fù)性），例如，令μ3=0，求得，故有求出各對(duì)角線與反對(duì)角線上的三個(gè)元素之和，并作一些簡(jiǎn)單的消去運(yùn)讀者不難驗(yàn)證，上述方法可推廣到n是奇數(shù)的一般情況。事實(shí)，由各對(duì)角線元素之和可導(dǎo)出n－1個(gè)方程，由各反對(duì)角線元素之和又可導(dǎo)出n－1個(gè)方程，加上矩陣所有元素之和導(dǎo)出的等式，共計(jì)可導(dǎo)出2n－1個(gè)方程，并易知它們是獨(dú)立的。另一方面空間的維數(shù)恰為2n－1，故之一可任取，而通過方程組解得所有的，（只須注意保持其非負(fù)性即可）但當(dāng)n為偶數(shù)時(shí)，情況就不大相同了。讓我們先來觀察一下n=4的情況。當(dāng)n=4時(shí)，讀者不難驗(yàn)證，上述方法可推廣到n是奇數(shù)的一般情況。事實(shí)，由各易見，具有非常特殊的結(jié)構(gòu)，一般的偶數(shù)階雙隨機(jī)矩陣，即使其元素是非負(fù)整數(shù)，也無法用Pk、Qk來分解。當(dāng)具有上述結(jié)構(gòu)時(shí)，能否用Pk和Qk來分解呢？易見，由各對(duì)角線元素之和可導(dǎo)出：易見，另外，由反對(duì)角線元素之和又可導(dǎo)出上述方程中只有6個(gè)是獨(dú)立的，且已不可能再得出新的獨(dú)立方程，（讀者可自行分析之）故可選取其中2個(gè)的值，進(jìn)而可解出其余。例如，若令

4=3=0，可得2=1，1=0，進(jìn)而可求得1=2，4=3，3=3及2=4，

已達(dá)到下界。易見，P1+P3=Q2+Q4，P2+P4=Q1+Q3，故空間的維數(shù)為6，與上面的分析是一致的。讀者可將上述討論推廣到n為一般偶數(shù)的情況，分析方法是完全類似的。另外，由反對(duì)角線元素之和又可導(dǎo)出上述方程中只有6個(gè)是獨(dú)立的，當(dāng)n是偶數(shù)時(shí)，我們雖無法將一般的雙隨機(jī)矩陣分解為Pk

、Qk的非負(fù)組合，但上述討論仍然是十分有意義的。首先，要求完成的任務(wù)矩陣是T，在將T轉(zhuǎn)換成時(shí)我們可盡量使具有上述的特殊結(jié)構(gòu)（有興趣的讀者可自行研究這一問題），只要能做到這一點(diǎn)，即可給出一個(gè)達(dá)到下界的開關(guān)模式的指派方式。其次，即使這樣的努力沒有成功，也容易給出一個(gè)具有上述特殊結(jié)構(gòu)矩陣，并使盡可能地小，即給出一種開關(guān)指派的近似最佳方法，由此可設(shè)計(jì)出效果較好的近似算法。由于技術(shù)水平的提高，目前通訊衛(wèi)星傳送信息已允許一個(gè)發(fā)射站同時(shí)向多個(gè)接收站發(fā)送信息，當(dāng)然，同時(shí)發(fā)送的信息條數(shù)具有某一上限，例如上限為v。1987年，J.L.Lewandowski和C.L.Liu研究了如下更一般的問題：當(dāng)n是偶數(shù)時(shí)，我們雖無法將一般的雙隨機(jī)矩陣分解為Pk、Qk給定一正整數(shù)v，（v為通訊衛(wèi)星傳送容量的總限止），求開關(guān)模式M：=：={;(0,1)|,i=1,…,m;,i=1,…,n,}的設(shè)計(jì)，要求所用的開關(guān)模式總數(shù)量r盡可能小，并使有解，其中T為信息傳送量矩陣（需滿足一定要求），ak為開關(guān)模式Mk的使用時(shí)間。他們?cè)O(shè)計(jì)了一個(gè)求解此問題的O(n5)算法，有興趣的讀者可直接閱讀他們的論文。

TheEnd給定一正整數(shù)v，（v為通訊衛(wèi)星傳送容量的總限止），求開關(guān)模式MATLAB求解多目標(biāo)規(guī)劃江西師范大學(xué)數(shù)信學(xué)院吳根秀MATLAB求解多目標(biāo)規(guī)劃江西師范大學(xué)數(shù)信學(xué)院吳根秀一、0-1規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINf’xS.T.Ax<=bAeqx=beqx=0,1命令格式：x=bintprog(f)x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)x=bintprog(f,A,b,Aeq,beq,x0)x=bintprog(f,A,b,Aeq,beq,x0,options)[x,fval]=bintprog(...)[x,fval,exitflag]=bintprog(...)[x,fval,exitflag,output]=bintprog(...)一、0-1規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINf’x數(shù)學(xué)模型：MINlambdaS.T.F(x)-weight*lambda<=goal(達(dá)到目標(biāo)）Ax<=b（線性不等式約束）Aeqx=beq（線性等式約束）C(x)<=0（非線性不等式約束）Ceq(x)=0（非線性等式約束）lb<=x<=ubF=[f1(x),f2(x),…]為多目標(biāo)的目標(biāo)函數(shù)；F與[C(x),Ceq(x)]都是通過function來定義；命令格式：x=fgoalattain(fun,x0,goal,weight)x=fgoalattain(fun,x0,goal,weight,A,b)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)二、多目標(biāo)規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINlambda二、多目標(biāo)規(guī)劃的MATLAB求命令格式：x=fgoalattain(fun,x0,goal,weight)x=fgoalattain(fun,x0,goal,weight,A,b)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,...lb,ub,nonlcon,options)[x,fval]=fgoalattain(...)[x,fval,attainfactor]=fgoalattain(...)[x,fval,attainfactor,exitflag]=fgoalattain(...)[x,fval,attainfactor,exitflag,output]=fgoalattain(...)[x,fval,attainfactor,exitflag,output,lambda]=fgoalattain(...)二、多目標(biāo)規(guī)劃的MATLAB求解命令格式：二、多目標(biāo)規(guī)劃的MATLAB求解x=fgoalattain(@myfun,x0,goal,weight,A,b,Aeq,beq,...lb,ub,@mycon)wheremyconisaMATLABfunctionsuchasfunction[c,ceq]=mycon(x)c=...%computenonlinearinequalitiesatx.ceq=...%computenonlinearequalitiesat二、多目標(biāo)規(guī)劃的MATLAB求解x=fgoalattain(@myfun,x0,goal,weight)wheremyfunisaMATLABfunctionsuchasfunctionF=myfun(x)F=...%Computefunctionvaluesatx.x=fgoalattain(@myfun,x0,goal有關(guān)優(yōu)化參數(shù)設(shè)置：options=optimset(‘GradObj’,‘on’)目標(biāo)函數(shù)的梯度方向參數(shù)設(shè)置為‘on’時(shí)，用下列函數(shù)定義：function[F,G]=myfun(x)F=...%Computethefunctionvaluesatxifnargout>1%TwooutputargumentsG=...%GradientsevaluatedatxEndThegradientconsistsofthepartialderivativedF/dxofeachFatthepointx.二、多目標(biāo)規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：二、多目標(biāo)規(guī)劃的MATLAB求解二、多目標(biāo)規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：options=optimset(‘GradConstr’,‘on’）約束條件的梯度方向參數(shù)設(shè)置為‘on’時(shí)，用下列函數(shù)定義：function[c,ceq,GC,GCeq]=mycon(x)c=...%Nonlinearinequalitiesatxceq=...%Nonlinearequalitiesatxifnargout>2%Nonlconcalledwith4outputsGC=...%GradientsoftheinequalitiesGCeq=...%GradientsoftheequalitiesEnd注意：一般weight=abs(goal)二、多目標(biāo)規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：模型：x’=(A+BKC)x+Bu，設(shè)計(jì)K滿足目標(biāo)：Y=Cx1）循環(huán)系統(tǒng)的特征值（由命令eig(A+B*K*C)確定）的目標(biāo)為goal=[-5,-3,-1]2）K中元素均在[-4,4]中;設(shè)特征值的weight=abs(goal),定義目標(biāo)函數(shù)F如下：functionF=eigfun(K,A,B,C)F=sort(eig(A+B*K*C));%Evaluateobjectives，由小到大排列優(yōu)化程序?yàn)椋篈=[-0.500;0-210;01-2];B=[10;-22;01];C=[100;001];K0=[-1-1;-1-1];%Initializecontrollermatrixgoal=[-5-3-1];%Setgoalvaluesfortheeigenvaluesweight=abs(goal)%Setweightforsamepercentagelb=-4*ones(size(K0));%Setlowerboundsonthecontrollerub=4*ones(size(K0));%Setupperboundsonthecontrolleroptions=optimset('Display','iter');%Setdisplayparameter[K,fval,attainfactor]=fgoalattain(@(K)eigfun(K,A,B,C)...goal,weight,[],[],[],[],lb,ub,[],options)二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題模型：x’=(A+BKC)x+Bu，設(shè)計(jì)K滿足目標(biāo)：二、舉例運(yùn)行結(jié)果如下Activeconstraints:124910K=-4.0000-0.2564-4.0000-4.0000fval=-6.9313-4.1588-1.4099attainfactor=-0.3863二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題運(yùn)行結(jié)果如下二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標(biāo)精確匹配，設(shè)置‘GoalsExactAchieve’參數(shù)值為3options=optimset('GoalsExactAchieve',3);[K,fval,attainfactor]=fgoalattain(...@(K)eigfun(K,A,B,C),K0,goal,weight,[],[],[],[],lb,ub,[],...options)Afteraboutseveniterations,asolutionisK=-1.59541.2040-0.4201-2.9046fval=-5.0000-3.0000-1.0000attainfactor=1.0859e-20表明目標(biāo)已完全匹配二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標(biāo)精確匹配，設(shè)置‘GoalsEx謝謝！謝謝！

初等模型舉例多目標(biāo)規(guī)劃培訓(xùn)教材-課件

常見類型定性模型經(jīng)驗(yàn)公式（擬合、插值）量綱分析比例模型常見類型定性模型§2.1

崖高的估算假如你站在崖頂且身上帶著一只具有跑表功能的計(jì)算器，你也許會(huì)出于好奇心想用扔下一塊石頭聽回聲的方法來估計(jì)山崖的高度，假定你能準(zhǔn)確地測(cè)定時(shí)間，你又怎樣來推算山崖的高度呢，請(qǐng)你分析一下這一問題。我有一只具有跑表功能的計(jì)算器?！?.1崖高的估算假如你站在崖頂且身上方法一假定空氣阻力不計(jì)，可以直接利用自由落體運(yùn)動(dòng)的公式來計(jì)算。例如，設(shè)t=4秒，g=9.81米/秒2，則可求得h≈78.5米。

我學(xué)過微積分，我可以做得更好，呵呵。

方法一假定空氣阻力不計(jì)，可以直接利用自由落體運(yùn)動(dòng)的公式我學(xué)除去地球吸引力外，對(duì)石塊下落影響最大的當(dāng)屬空氣阻力。根據(jù)流體力學(xué)知識(shí)，此時(shí)可設(shè)空氣阻力正比于石塊下落的速度，阻力系數(shù)K為常數(shù)，因而，由牛頓第二定律可得：

令k=K/m，解得

代入初始條件v(0)=0，得c=－g/k，故有

再積分一次，得：

除去地球吸引力外，對(duì)石塊下落影響最大的當(dāng)屬空氣阻力。根若設(shè)k=0.05并仍設(shè)t=4秒，則可求得h≈73.6米。

聽到回聲再按跑表，計(jì)算得到的時(shí)間中包含了反應(yīng)時(shí)間

進(jìn)一步深入考慮不妨設(shè)平均反應(yīng)時(shí)間為0.1秒，假如仍設(shè)t=4秒，扣除反應(yīng)時(shí)間后應(yīng)為3.9秒，代入式①，求得h≈69.9米。

①多測(cè)幾次，取平均值再一步深入考慮代入初始條件h(0)=0，得到計(jì)算山崖高度的公式：

將e-kt用泰勒公式展開并令k→0+

，即可得出前面不考慮空氣阻力時(shí)的結(jié)果。若設(shè)k=0.05并仍設(shè)t=4秒，則可求得h≈73.6米。還應(yīng)考慮回聲傳回來所需要的時(shí)間。為此，令石塊下落的真正時(shí)間為t1，聲音傳回來的時(shí)間記為t2，還得解一個(gè)方程組：這一方程組是非線性的，求解不太容易，為了估算崖高竟要去解一個(gè)非線性主程組似乎不合情理

相對(duì)于石塊速度，聲音速度要快得多，我們可用方法二先求一次

h，令t2=h/340，校正t，求石塊下落時(shí)間t1≈t-t2將t1代入式①再算一次，得出崖高的近似值。例如，若h=69.9米，則t2≈0.21秒，故t1≈3.69秒，求得h≈62.3米。還應(yīng)考慮回聲傳回來所需要的時(shí)間。為此，令石塊下落的真§2.2

錄像帶還能錄多長(zhǎng)時(shí)間錄像機(jī)上有一個(gè)四位計(jì)數(shù)器，一盤180分鐘的錄像帶在開始計(jì)數(shù)時(shí)為0000，到結(jié)束時(shí)計(jì)數(shù)為1849，實(shí)際走時(shí)為185分20秒。我們從0084觀察到0147共用時(shí)間3分21秒。若錄像機(jī)目前的計(jì)數(shù)為1428，問是否還能錄下一個(gè)60分鐘的節(jié)目？§2.2錄像帶還能錄多長(zhǎng)時(shí)間錄像機(jī)上有一個(gè)四位計(jì)數(shù)器，一rθRl由得到又因和得

積分得到即從而有我們希望建立一個(gè)錄像帶已錄像時(shí)間t與計(jì)數(shù)器計(jì)數(shù)n之間的函數(shù)關(guān)系。為建立一個(gè)正確的模型，首先必須搞清哪些量是常量，哪些量是變量。首先，錄像帶的厚度W是常量，它被繞在一個(gè)半徑為r的園盤上，見圖。磁帶轉(zhuǎn)動(dòng)中線速度v顯然也是常數(shù)，否則圖象聲音必然會(huì)失真。此外，計(jì)數(shù)器的讀數(shù)n與轉(zhuǎn)過的圈數(shù)有關(guān)，從而與轉(zhuǎn)過的角度θ成正比。rθRl由得到又rθRl

此式中的三個(gè)參數(shù)W、v和r均不易精確測(cè)得，雖然我們可以從上式解出t與n的函數(shù)關(guān)系，但效果不佳，故令則可將上式簡(jiǎn)化為：故令上式又可化簡(jiǎn)記成t=an2+bn

rθRl此式中的三個(gè)參數(shù)W、v和r均不易精確測(cè)得，雖然我們t=an2+bn

rθRl上式以a、b為參數(shù)顯然是一個(gè)十分明智的做法，它為公式的最終確立即參數(shù)求解提供了方便。將已知條件代入，得方程組：從后兩式中消去t1，解得a=0.0000291,b=0.04646,故t=0.0000291n2+0.04646n，令n=1428，得到t=125.69（分）由于一盒錄像帶實(shí)際可錄像時(shí)間為185.33分，故尚可錄像時(shí)間為59.64分，已不能再錄下一個(gè)60分鐘的節(jié)目了。

t=an2+bnrθRl上式以a、b為參數(shù)顯然是一個(gè)十分在解決實(shí)際問題時(shí)，注意觀察和善于想象是十分重要的，觀察與想象不僅能發(fā)現(xiàn)問題隱含的某些屬性，有時(shí)還能順理成章地找到解決實(shí)際問題的鑰匙。本節(jié)的幾個(gè)例子說明，猜測(cè)也是一種想象力。沒有合理而又大膽的猜測(cè)，很難做出具有創(chuàng)新性的結(jié)果。開普勒的三大定律（尤其是后兩條）并非一眼就能看出的，它們隱含在行星運(yùn)動(dòng)的軌跡之中，隱含在第谷記錄下來的一大堆數(shù)據(jù)之中。歷史上這樣的例子實(shí)在太多了。在獲得了一定數(shù)量的資料數(shù)據(jù)后，人們常常會(huì)先去猜測(cè)某些結(jié)果，然后試圖去證明它。猜測(cè)一經(jīng)證明就成了定理，而定理一旦插上想象的翅膀，又常常會(huì)被推廣出許多更為廣泛的結(jié)果。即使猜測(cè)被證明是錯(cuò)誤的，結(jié)果也決不是一無所獲的失敗而常常是對(duì)問題的更為深入的了解?！?.3最短路徑與最速方案問題在解決實(shí)際問題時(shí)，注意觀察和善于想象是十分重要的，觀察與想象例5（最短路徑問題）設(shè)有一個(gè)半徑為r的圓形湖，圓心為O。A、B

位于湖的兩側(cè)，AB連線過O，見圖。現(xiàn)擬從A點(diǎn)步行到B點(diǎn)，在不得進(jìn)入湖中的限制下，問怎樣的路徑最近。

ABOr將湖想象成凸出地面的木樁，在AB間拉一根軟線，當(dāng)線被拉緊時(shí)將得到最短路徑。根據(jù)這樣的想象，猜測(cè)可以如下得到最短路徑：過A作圓的切線切圓于E，過B作圓的切線切圓于F。最短路徑為由線段AE、弧EF和線段FB連接而成的連續(xù)曲線（根據(jù)對(duì)稱性，AE′，弧E′F′，F(xiàn)′B連接而成的連續(xù)曲線也是）。EFE′F′例5（最短路徑問題）設(shè)有一個(gè)半徑為r的圓形湖，圓心為以上只是一種猜測(cè)，現(xiàn)在來證明這一猜測(cè)是正確的。為此，先介紹一下凸集與凸集的性質(zhì)。定義2.1（凸集）稱集合R為凸集，若x1、x2∈R及λ∈[0，1]，總有λx1+（1+λ）x2∈R。即若x1、x2∈R，則x1、x2的連線必整個(gè)地落在R中。定理2.2（分離定理）對(duì)平面中的凸集R與R外的一點(diǎn)K，存在直線l,l

分離R與K，即R與K分別位于l的兩側(cè)（注：對(duì)一般的凸集R與R外的一點(diǎn)K，則存在超平面分離R與K），見圖。klR下面證明猜想以上只是一種猜測(cè)，現(xiàn)在來證明這一猜測(cè)是正確的。為此，先介紹一猜測(cè)證明如下：（方法一）顯然，由AE、EF、FB及AE′，E′F′，F(xiàn)′B圍成的區(qū)域R是一凸集。利用分離定理易證最短徑不可能經(jīng)過R外的點(diǎn)，若不然，設(shè)Γ為最短路徑，Γ過R外的一點(diǎn)M，則必存在直線l分離M與R，由于路徑Γ是連續(xù)曲線，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。這樣，直線段M1M2的長(zhǎng)度必小于路徑M1MM2的長(zhǎng)度，與Γ是A到B的最短路徑矛盾，至此，我們已證明最短路徑必在凸集R內(nèi)。不妨設(shè)路徑經(jīng)湖的上方到達(dá)B點(diǎn)，則弧EF必在路徑F上，又直線段AE是由A至E的最短路徑，直線FB是由F到B的最短路徑，猜測(cè)得證。ABOrEFE′F′M1M2MΓl猜測(cè)證明如下：（方法一）顯然，由AE、EF、FB及AE′，還可用微積分方法求弧長(zhǎng)，根據(jù)計(jì)算證明滿足限止條件的其他連續(xù)曲線必具有更大的長(zhǎng)度；此外，本猜測(cè)也可用平面幾何知識(shí)加以證明等。根據(jù)猜測(cè)不難看出，例5中的條件可以大大放松，可以不必設(shè)AB過圓心，甚至可不必設(shè)湖是圓形的。例如對(duì)下圖，我們可斷定由A至B的最短路徑必為l1與l2之一，其證明也不難類似給出。ABl1l2D到此為止，我們的研討還只局限于平面之中，其實(shí)上述猜測(cè)可十分自然地推廣到一般空間中去。1973年，J.W.Craggs證明了以上結(jié)果：若可行區(qū)域的邊界是光滑曲面。則最短路徑必由下列弧組成，它們或者是空間中的自然最短曲線，或者是可行區(qū)域的邊界弧。而且，組成最短路徑的各段弧在連接點(diǎn)處必定相切。還可用微積分方法求弧長(zhǎng)，根據(jù)計(jì)算證明滿足限止條件的其他連續(xù)曲例6

一輛汽車停于A處并垂直于AB方向，此汽車可轉(zhuǎn)的最小圓半徑為R，求不倒車而由A到B的最短路徑。解（情況1）若|AB|>2R，最短路徑由弧AC與切線BC