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

MATLAB求解多目標規(guī)劃江西師范大學(xué)數(shù)信學(xué)院吳根秀MATLAB求解多目標規(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(達到目標）Ax<=b（線性不等式約束）Aeqx=beq（線性等式約束）C(x)<=0（非線性不等式約束）Ceq(x)=0（非線性等式約束）lb<=x<=ubF=[f1(x),f2(x),…]為多目標的目標函數(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)二、多目標規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINlambda二、多目標規(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(...)二、多目標規(guī)劃的MATLAB求解命令格式：二、多目標規(guī)劃的MATLAB求解x=fgoalattain(@myfun,x0,goal,weight,A,b,Aeq,beq,...lb,ub,@mycon)wheremyconisaMATLABfunctionsuchasfunction[c,ceq]=mycon(x)c=...%computenonlinearinequalitiesatx.ceq=...%computenonlinearequalitiesat二、多目標規(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’)目標函數(shù)的梯度方向參數(shù)設(shè)置為‘on’時，用下列函數(shù)定義：function[F,G]=myfun(x)F=...%Computethefunctionvaluesatxifnargout>1%TwooutputargumentsG=...%GradientsevaluatedatxEndThegradientconsistsofthepartialderivativedF/dxofeachFatthepointx.二、多目標規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：二、多目標規(guī)劃的MATLAB求解二、多目標規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：options=optimset(‘GradConstr’,‘on’）約束條件的梯度方向參數(shù)設(shè)置為‘on’時，用下列函數(shù)定義：function[c,ceq,GC,GCeq]=mycon(x)c=...%Nonlinearinequalitiesatxceq=...%Nonlinearequalitiesatxifnargout>2%Nonlconcalledwith4outputsGC=...%GradientsoftheinequalitiesGCeq=...%GradientsoftheequalitiesEnd注意：一般weight=abs(goal)二、多目標規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：模型：x’=(A+BKC)x+Bu，設(shè)計K滿足目標：Y=Cx1）循環(huán)系統(tǒng)的特征值（由命令eig(A+B*K*C)確定）的目標為goal=[-5,-3,-1]2）K中元素均在[-4,4]中;設(shè)特征值的weight=abs(goal),定義目標函數(shù)F如下：functionF=eigfun(K,A,B,C)F=sort(eig(A+B*K*C));%Evaluateobjectives，由小到大排列優(yōu)化程序為：A=[-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è)計K滿足目標：二、舉例運行結(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)化問題運行結(jié)果如下二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標精確匹配，設(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表明目標已完全匹配二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標精確匹配，設(shè)置‘GoalsEx謝謝！謝謝！

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

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

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

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

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

令k=K/m，解得

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

再積分一次，得：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

）。（情況2）若|AB|<2R，則最短路徑必居于圖②（a）、（b）兩曲線之中?？梢宰C明，（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的長度，即可得到最短路徑。Al1l2Bθ2θ1例7駕駛一輛停于A處與AB成θ1角度的汽解根據(jù)Cra最速方案問題例8

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

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

minT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

令D

即解方程組：

=

解得

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

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

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

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

設(shè)

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

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

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

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

為方便起見，我們來分解一個元素均為非負整數(shù)的3階雙隨機矩陣，（由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)，此問題可以通過求解一個兩分圖上的最大流（或最大匹配）來實現(xiàn)，計算量為O(n4)，是多項式時間可解的。具體方法為：作一兩分圖，若，則作邊（i,j），令邊容量為1，這樣，可作出P的充要條件是該最大流問題的最大流量為n。對例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è)計方法要求在通訊衛(wèi)星上設(shè)置(n－1)2+1種不同的開關(guān)模式（即Pk），當n稍大時，(n－1)2+1仍顯得太大而使得使用時不便。例如，當n=41時，(n－1)2+1=|60|。為實用方便，人們研究了限止開關(guān)模式個數(shù)的相應(yīng)問題。，相應(yīng)的兩分圖為：又可得若要求r≤n，即要求通訊衛(wèi)星上至多設(shè)置n種開關(guān)模式，則問題化為令r≤n，求不超過n個置換矩陣Pk及λk，使之滿足：minS.t

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

（5.2）

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

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

若取，

，

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

S.t

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

4=3=0，可得2=1，1=0，進而可求得1=2，4=3，3=3及2=4，

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

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

TheEnd給定一正整數(shù)v，（v為通訊衛(wèi)星傳送容量的總限止），求開關(guān)模式MATLAB求解多目標規(guī)劃江西師范大學(xué)數(shù)信學(xué)院吳根秀MATLAB求解多目標規(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(達到目標）Ax<=b（線性不等式約束）Aeqx=beq（線性等式約束）C(x)<=0（非線性不等式約束）Ceq(x)=0（非線性等式約束）lb<=x<=ubF=[f1(x),f2(x),…]為多目標的目標函數(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)二、多目標規(guī)劃的MATLAB求解數(shù)學(xué)模型：MINlambda二、多目標規(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(...)二、多目標規(guī)劃的MATLAB求解命令格式：二、多目標規(guī)劃的MATLAB求解x=fgoalattain(@myfun,x0,goal,weight,A,b,Aeq,beq,...lb,ub,@mycon)wheremyconisaMATLABfunctionsuchasfunction[c,ceq]=mycon(x)c=...%computenonlinearinequalitiesatx.ceq=...%computenonlinearequalitiesat二、多目標規(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’)目標函數(shù)的梯度方向參數(shù)設(shè)置為‘on’時，用下列函數(shù)定義：function[F,G]=myfun(x)F=...%Computethefunctionvaluesatxifnargout>1%TwooutputargumentsG=...%GradientsevaluatedatxEndThegradientconsistsofthepartialderivativedF/dxofeachFatthepointx.二、多目標規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：二、多目標規(guī)劃的MATLAB求解二、多目標規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：options=optimset(‘GradConstr’,‘on’）約束條件的梯度方向參數(shù)設(shè)置為‘on’時，用下列函數(shù)定義：function[c,ceq,GC,GCeq]=mycon(x)c=...%Nonlinearinequalitiesatxceq=...%Nonlinearequalitiesatxifnargout>2%Nonlconcalledwith4outputsGC=...%GradientsoftheinequalitiesGCeq=...%GradientsoftheequalitiesEnd注意：一般weight=abs(goal)二、多目標規(guī)劃的MATLAB求解有關(guān)優(yōu)化參數(shù)設(shè)置：模型：x’=(A+BKC)x+Bu，設(shè)計K滿足目標：Y=Cx1）循環(huán)系統(tǒng)的特征值（由命令eig(A+B*K*C)確定）的目標為goal=[-5,-3,-1]2）K中元素均在[-4,4]中;設(shè)特征值的weight=abs(goal),定義目標函數(shù)F如下：functionF=eigfun(K,A,B,C)F=sort(eig(A+B*K*C));%Evaluateobjectives，由小到大排列優(yōu)化程序為：A=[-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è)計K滿足目標：二、舉例運行結(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)化問題運行結(jié)果如下二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標精確匹配，設(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表明目標已完全匹配二、舉例---有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證38.63%的目標精確匹配，設(shè)置‘GoalsEx謝謝！謝謝！

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

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

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

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

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

令k=K/m，解得

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

再積分一次，得：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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