第五章最優(yōu)化方法在國民經(jīng)濟(jì)各部門和科學(xué)技術(shù)的各個領(lǐng)域中普遍存在著最優(yōu)化問題(如工業(yè)設(shè)計中的參數(shù)選擇,資源合理分配等等).最優(yōu)化問題的解就是從所有可能的方案中選出最合理的,以達(dá)到最優(yōu)目標(biāo)的方案--最優(yōu)方案.搜尋最優(yōu)方案的方法就是最優(yōu)化方法.隨著計算機(jī)科學(xué)的發(fā)展和廣泛應(yīng)用,應(yīng)用最優(yōu)化方法解決問題的領(lǐng)域不斷擴(kuò)大,解決問題的深度不斷深化,最優(yōu)化的理論和方法也不斷得到普及和發(fā)展.近幾年的大學(xué)生數(shù)學(xué)建模競賽題目很多都與最優(yōu)化問題有關(guān)(如飛行管理問題(95A),最優(yōu)捕魚策略(96A),節(jié)水洗衣機(jī)(96B),零件參數(shù)設(shè)計(97A),投資的收益和風(fēng)險(98A),鋼管訂購和運(yùn)輸(2000B)).這里,我們主要介紹最典型的優(yōu)化模型及應(yīng)用背景、相關(guān)的優(yōu)化理論和最常用的優(yōu)化算法.建立最優(yōu)化問題的數(shù)學(xué)模型,首先要確定問題的決策變量,用n維向量表示x二(x,x,x)t,然后構(gòu)造模型的目標(biāo)函數(shù)f(X)和決策變TOC\o"1-5"\h\z1 2 n量的允許取值范圍，稱可行域,常用一組不等式g(x)<0(i二1,2,…,m)來i界定，稱為約束條件.一般地，這類模型可表述成如下形式：min(max)z=f(x) (0.1)xS.t.g(x)<0,i=1,2,…,m (0.2)i只滿足(0.2)的解x稱可行解，同時滿足(0.1)、(0.2)的解x=x*

稱為最優(yōu)解.1線性規(guī)劃如果(0.1)(0.2)中的目標(biāo)函數(shù)f(x)和約束條件g(x)都是線性函數(shù),該模型稱為線性規(guī)劃.模型為LP)(1)minf(x)=cxs.t.Ax<b,x>0LP)(1)1．1線性規(guī)劃模型的標(biāo)準(zhǔn)型:minf=cx(2)其中A=(a) ,x=(x,x,x)t,b=(b,b,b)t,c=(c,c,c)ijmxn 1 2 n 1 2 m 1 2 n線性規(guī)劃的其他形式可通過形式變換和添加松弛變量而化為標(biāo)準(zhǔn)型1.2求解方法:單純形方法是通過迭代來求問題(LP)的最優(yōu)解,在一個基本可行解非最優(yōu)時，確定一個更優(yōu)的基本可行解，形成一個使目標(biāo)函數(shù)單調(diào)減的基本可行解序列X(1),X(2),…，經(jīng)有限步即可求得最優(yōu)解1.3模型示例:例1.1運(yùn)輸問題:設(shè)有m個生產(chǎn)地點(diǎn)a,A，…,A可供應(yīng)物資,TOC\o"1-5"\h\z1 2m其供應(yīng)量(產(chǎn)量)分別為a,a，…,a.有n個銷售地點(diǎn)B,B,B,1 2m 1 2n其需求量分別為b,b，…,b，假設(shè)供需平衡既遲a=Xb?用c表1 2n i i iji=1 i=1示由A到B運(yùn)輸單位物資的運(yùn)價，如何確定一種調(diào)運(yùn)方案才能ii使總運(yùn)輸費(fèi)用I最小.用x表示由A到B調(diào)運(yùn)物資的數(shù)量,則運(yùn)輸問題的數(shù)學(xué)模ijii型為:minI二埜exijiji=1j=1工x=a,i=1,2,…,mijij=1S.t.區(qū)x=b,j=1,2,…，nijii=1x>0ij1．4利用MATLAB優(yōu)化工具箱解線性規(guī)劃Matlab求解線性規(guī)劃的命令為x=linprog(c,A,b,Aeq,beq)x=linprog(c,A,b,Aeq,beq,vlb,vub)x=linprog(c,A,b,Aeq,beq,vlb,vub,x0);x0表示初始點(diǎn)八、、x=lp(c,A,b,Aeq,beq,vlb,vub,x0,options);x0表示初始點(diǎn)其中1)用于求解模型minZ=ex亠Ax<bs.t.Aeqx=beq2)、3)、4)用于求解minZ=exAx<bS.t.Aeqx-beqvlb<x<vub例1求解線性規(guī)劃問題maxz=cxS.t.Ax<bx>0其中c=[-0.4,-0.28,-0.32,-0.72,-0.64,-0.6]A=[0.010.010.010.030.030.030.020 00.050 000.02 000.050000.03000.08]b=[850;700;100;900]vlb=[0;0;0;0;0;0]vub=[]解用命令2)l11.mc=[-0.4,-0.28,-0.32,-0.72,-0.64,-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];vlb=[0;0;0;0;0;0];vub=[];x=linprog(c,A,b,[],[],vlb,vub)f=c*x例2求解線性規(guī)劃問題minz=6x+3x+4x123s.t.x+x+x=120123x>30,10<x<502x>203解用命令3)l12.mc=[6,3,4];A=[1,1,1;0,1,0];b=[120;50];vlb=[30,0,20];vub=[];x0=[0;0;0];Aeq=[1,1,1];Beq=120;x=lp(c,A,b,Aeq,beq,vlb,vub,x0)z=c*x§2整數(shù)線性規(guī)劃在某些線性規(guī)劃問題中,決策變量只能取整數(shù)（如人數(shù)、機(jī)器的數(shù)量）,這時約束條件中還需添加變量取整的限制,這就是整數(shù)線性規(guī)劃,模型的一般形式為minz=cxAx=b (ILP)x為非負(fù)整數(shù)(j二1,2,…,n)j如果其中只有部分變量取整數(shù),稱為混合整數(shù)規(guī)劃.決策變量只能取整數(shù)0或1的稱為0-1規(guī)劃2．1整數(shù)線性規(guī)劃的求解方法2．1.1割平面法—用于求解純整數(shù)規(guī)劃2．1.2分枝定界法—用于求解混合整數(shù)規(guī)劃.2．1．3窮舉法-用于規(guī)模不大的整數(shù)問題的求解2．2建模示例例2.1背包問題：有一只背包(泛指倉庫、船艙、衛(wèi)星倉等)，最大裝載重量為w單位?，F(xiàn)有k種物品，每種的數(shù)量無限。第i種物品每件重量為w，價值v。每種物品各取多少裝入背包，使其中的物ii品總價值最高。設(shè)取第i種物品x件,則iminz=vx+vxH Fvx1122kk,wx+wxH Fwx<ws.t.1122kkx>0,且為整數(shù),i二1,2,…,ki§3無約束優(yōu)化無約束優(yōu)化的模型為minf(x)xeR?它的最優(yōu)解都是局部最優(yōu)解,全局最優(yōu)解只能從局部最優(yōu)解的比較中得到3．1最優(yōu)解條件Vf(x)二(?,?，…,?)T(稱為梯度),V2f(x)二(f2f) (Hessian矩陣)oxox ox oxoxnxn1 2n ij必要條件：若x*為f(x)的極小點(diǎn)，則Vf(x*)=0充分條件:若Vf(x*)=0,V2f(x*)正定，則x*是極小點(diǎn)3．2求解方法：搜索算法(數(shù)值迭代)數(shù)值迭代的基本思路是在迭代的每一步,確定一個搜索方向和一個步長,使沿此方向和此步長走一步到達(dá)下一點(diǎn)時,函數(shù)f(X)的值下降.基本步驟為1)選初始點(diǎn)x2)對于第k次迭代解x,確定搜0k索方向dGRn并在此方向確定搜索步長九GR，令x二x+九dS.t.k k k+1 kkkf(x)<f(x)3)若x符合給定的迭代終止原則，停止迭代,k+1 k k+1x*=xk+1否則轉(zhuǎn)2).不同的算法在于方向和步長的選擇，目的是使f下降更快.3．2．1步長的選擇:搜索方向d確定后,求步長實際上是一個k一維優(yōu)化問題:minf(x+九d)九 kk稱為一維搜索,有很多方法,如成功-失敗法、黃金分割法(0.618法)、Fibonacci法、拋物線插值法和三次插值法等等3．2.2方向的選擇3. 2.2.1最速下降法(梯度法)：取d二-Vf(x)kk3. 2.2.2牛頓法：取d=-(V2f(x))-1Vf(x)k k k3. 2.2.3擬牛頓法:選d滿足d=-HVf(x)k k k k

其中H由BFGS迭代公式或DEP公式迭代得出k=H7-1TOC\o"1-5"\h\z\o"CurrentDocument"-Hyy TH +=H7-1i-ri-r/-1 /-1丁yth yssT7-17-1y Ts7-1 7-1=ssT7-17-1y Ts7-1 7-1=Hi-1-Hi-iy「iy「Hi_iyi-1THi-1yi-1ssTi—1i-1yTsi-1 i-1+wwTi-1i-13.3用MATLAB優(yōu)化工具箱解無約束最優(yōu)化問題3．3.1命令fminuncx=fminunc(‘fun',x0)x=fminunc(‘fun',x0,options)其中1)、2)用于求解多元函數(shù)的無約束極小化問題,x0為迭代的初值fun為函數(shù)形式的M-文件(fun.m)的文件名，fminunc的求解方法由options(6)(方向)和options(7)(步長)指定(options(6)=0擬牛頓法(BFGS公式)options(6)=1擬牛頓法(DFP公式)options(6)=2最速下降法;options(7)=0混合的二次和三次多項式插值options(7)=1三次多項式插值)例1求f二2e-xsinx在(0,8)上的最大值和最小值.L21.mf='2*exp(-x)*sin(x)';fplot(f,[0,8]);xmin=fminbnd(f,0,8);x=xmin;ymin=eval(f);f1='-2*exp(-x)*sin(x)';xmax=fminbnd(f1,0,8);x=xmax;ymax=eval(f)例2求f(x)=(4x2+2x2+4xx+2x+10]12122編寫函數(shù)M-文件FUN32.Mfunctionf=fun32(x)f二exp(x(l))*(4*x(l廠2+2*x(2廠2+4*x(l)*x(2)+2*x(2)+l);鍵入命令l22.mx0=[-1,1];x=fminunc('fun32',x0);y=fun32(x)例3Rosenbrock函數(shù)f(x,x)=100(x一x2)2+(1一x)212211它的極小值點(diǎn)為x*=(1,1),極小值f(x*)=0.試用不同的算法求數(shù)值最優(yōu)解,初始點(diǎn)選為x=(-1.2,2).0建立函數(shù)M-文件fun33.mfunctionf=fun33(x)f=100*(x(2)-x(l廠2廠2+(l-x(l)廠2;用fminunc命令l232.moptions(6)=1;options(7)=0;[x,options]=fminu('fun33',[-1.2,2],options)y=options(8)n=options(10)options(6)=1;options(7)=1;[x,options]=fminu('fun33',[-1.2,2],options)y=options(8)n=options(10)options(6)=2;options(7)=1;[x,options]=fminu('fun33',[-1.2,2],options)y=options(8)n=options(10)options(6)=0;options(7)=1;[x,options]=fminu('fun33',[-1.2,2],options)y=options(8)n=options(10)畫圖[x,y]=meshgrid(-2:0.1:2,-1:0.1:3);z=100*(y-x.八2).八2+(l-x).八2;mesh(x,y,z)contour(x,y,z,20)drawnowholdonplot(-1.2,2,'o')text(-1.2,2,'startpoint')plot(1,1,'o')text(1,1,'solution')3．4模型示例例3.4.1選址問題:某市燃?xì)夤居媱澮ㄒ粋€煤氣供應(yīng)站,該站向城市中有固定位置的m個用戶供貨.對于選定的坐標(biāo)系，已知第i個用戶的位置為(a,b),i1,2,,m,如果只考慮直線距離，如何確定ii煤氣站的位置,才能使總的運(yùn)輸距離最短?設(shè)煤氣站的位置為(x,x)則問題的數(shù)學(xué)模型為12minf（x,x）=￡ （x一a）2+（x一b）21 2 * 1i 2ii=1§4非線性規(guī)劃(0.1)(0.2)中至少有一個是非線性函數(shù)的最優(yōu)化問題稱為非線性規(guī)劃問題,其數(shù)學(xué)模型為TOC\o"1-5"\h\zminf(x) (4.1)s.t.g(x)n°，i=12…,m (4.2)h(x)=0,j=1,2,…,lj其中x=(x,x，…,x),f,g,h:RntR1 2 n ij求目標(biāo)函數(shù)的最大值或約束條件小于等于零的情形,可通過取其相反數(shù),而化為上述形式.4．1非線性規(guī)劃問題的求解方法4．1．1罰函數(shù)法基本思想是通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題.這種方法稱為序列無約束最小化方法，簡稱SUMT.4.1.1.1SUMT外點(diǎn)法構(gòu)造罰函數(shù)T(x,M)如下：T(x,M)=f(x)+M區(qū)[min(0,g(x)]2+M工[h(x)]2 (4.3)iji=1 j=1將求解非線性規(guī)劃問題(4.1)(4.2)轉(zhuǎn)化為求解無約束問題

minT(x,M) (4.4)若對某個確定的M,(4.4)的解x(M)eD,則x(M)是(4.1)(4.2)的解4.1.1.2SUMT內(nèi)點(diǎn)法對具有不等式約束的非線性規(guī)劃問題(4.5)minf(x)(4.5)s.t.g(x)>0,i二1,2,…,mi構(gòu)造障礙函數(shù)I(x,r)如下：kr遲kir遲ki=1,或I(X,r)=f(x)-

k區(qū)Ing(x)ii=1(4.6)將(4.5)轉(zhuǎn)化為求解(4.6)minI(x,r)k其中r>r>…>r>…>0,limr=01 2 k kT8k若x是(4.6)的解,則x*=limx是(4.5)的解kk4.2用MATLAB優(yōu)化工具箱解約束最優(yōu)化(非線性規(guī)劃)問題4.2.1求解二次規(guī)劃問題minf(minf(x)=1—xtHx+cxs.t.Ax<b,x>0(vlb<x<vub)其中H為n階對稱半正定矩陣.MATLAB命令為1)x二qp(H,c,A,b);2)x二qp(H,c,A,b,vlb,vub);x=qp(H,c,A,b,vlb,vub,x0);x=qp(H,c,A,b,vlb,vub,x0)x=qp(H,c,A,b,vlb,vub,x0,N)例4.1求二次規(guī)劃minminf(x,x)=一2x一6x+x2一2xx+2x212121122s.t.x+x<212一x+2x<212x>0,x>012寫成標(biāo)準(zhǔn)形式minf(x)=xTHx+minf(x)=xTHx+cx2,c=(一2,一6),A=(1-1,vlb=鍵入命令141H=[2,-2;-2,4];c=[-2;-6];A=[1,1;-1,2];b=[2;2],vlb=[0;0];vub=[];x=qp(H,c,A,b,vlb,vub)z=0.5*x'*H*x+c'*x4．2．2求解非線性規(guī)劃問題minF(x)fG(x)<0s.t.<[vlb<x<vub的MATLAB命令為1)x=constr(‘fun',x0)2)x=constr(‘fun',x0,options)x=constr(‘fun',x0,options,vlb,vub)

例4.2求解min例4.2求解1X222s.t2x+1X22212x+4x<512x,x>012建立函數(shù)M-文件FUN42function[f,g]=fun42(x)f=-x(l)-2*x(2)+l/2*x(l廠2+l/2*x(2廠2;g=[2*x(1)+3*x(2)-6;x(1)+4*x(2)-5];鍵入命令x0=[1;1];vlb=[0;0];vub=[];options=[];x=constr('fun42',x0,options,vlb,vub)fun42(x)例4.3求解minf(x)=ex](4x2+2x2+4xx+2x+1)12122s.t.x+x=0121.5+xx一x一x<01212—xx—10<012建立函數(shù)文件FUN43.Mfunction[f,g]=fun43(x)f二exp(x(l))*(4*x(l廠2+2*x(2廠2+4*x(l)*x(2)+2*x(2)+l);g=[x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];鍵入命令x0=[-1;1];options(13)=1;[x,options]=constr('fun43',x0,options);options(8)4．3.建模示例例4．3.1資金使用問題設(shè)有400萬元資金，要求4年內(nèi)使用完，若在一年內(nèi)使用資金x萬元，則可得效益質(zhì)萬元（效益不能再使用），當(dāng)年不用的資金可存入銀行，年利率為10%.試制定出資金的使用計劃，以使4年效益之和為最大設(shè)變量x表示第i年所使用的資金數(shù)，則有imaxz=x+x+x+「x' 1 * 2中3片4s.t.x<40011.1x+x<440121.21x+1.1x+x<4841 2 31.331x+1.21x+1.1x+x<532.41 2 3 4x>0,i=1,2,3,4i建立函數(shù)文件FUN44.Mfunction[f，g]=fun44(x)f=-(sqrt(x(1))+sqrt(x(2))+sqrt(x(3))+sqrt(x(4)));g(1)=x(1)-400;g(2)=1.1*x(1)+x(2)-440;g(3)=1.21*x(1)+1.1*x(2)+x(3)-484;g(4)=1.331*x(1)+1.21*x(2)+1.1*x(3)+x(4)-532.4;鍵入命令x0=[1;1;1;1];vlb=[0;0;0;0];vub=[];options=[];x=constr('fun44',x0,options,vlb,vub)fun44(x)得至寸x=86.2,x=104.2,x=126.2,x=152.8Z=43.1 2 3 4§5動態(tài)規(guī)劃動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種數(shù)學(xué)方法.它在工程技術(shù)、管理、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事及現(xiàn)代控制工程等方面都有廣泛的應(yīng)用。構(gòu)造動態(tài)規(guī)劃模型的步驟為1)將實際問題恰當(dāng)?shù)貏澐譃槿舾呻A段;2)正確選擇狀態(tài)變量x;3)確定決策變量u及每段的允kk許決策集合D(x)二{u}；4)正確選擇狀態(tài)轉(zhuǎn)移方程x=f(x,u)；kk k k+1 kkk正確列出指標(biāo)函數(shù)v并要求滿足遞推性。k,n根據(jù)Bellman的最優(yōu)化原理(對最優(yōu)策略來說，無論過去狀態(tài)和決策如何，由前面諸決策所形成的狀態(tài)出發(fā)，相應(yīng)的剩余決策序列構(gòu)成最優(yōu)子策略)，利用逆推(初始狀態(tài)給定)和順推方法(終止?fàn)顟B(tài)給定)可求出最優(yōu)決策和最優(yōu)值。下面我們將就幾個典型的多階段決策過程最優(yōu)化問題，利用動態(tài)規(guī)劃方法給出他們的求解算法。5.1投資問題:設(shè)有某種資源(或資金)M個單位(M為正整數(shù)),欲分配用于N個生產(chǎn)項目.已知第k個生產(chǎn)項目獲得u(k)個單位(u(k)為非負(fù)整數(shù),稱為決策變量)這種資源后可創(chuàng)利潤L((u(k)),k).L(u(k)),K)是u(k)的不減函數(shù).如何分配這些資源可使所獲利潤I二藝l(u(k),k)最大.k=1把資源分配過程分為N個階段.第k階段是向第k個生產(chǎn)項目分配資源.用x(k+1)表示分配完1,2,…,k個生產(chǎn)項目后剩余的資源數(shù)量(稱為狀態(tài)變量,x(1)=M).用v(x(k+1),k+1)表示把剩余的資源x(k+1)分配給第k+1,k+2,…,N個生產(chǎn)項目能獲得的最大利潤(稱為最優(yōu)值函數(shù)).根據(jù)動態(tài)規(guī)劃方法,利用動態(tài)規(guī)劃基本方程V(x(k),k)=max{L(u(k),k)+V(x(k+1),k+l))},k=N-1,—,2,1u(k)eU(x(k))V(x(N),N)=L(x(N),N)和狀態(tài)轉(zhuǎn)移方程x(k+1)=x(k)-u(k)逆向遞推可求得最優(yōu)決策序列(u*(1),u*(2),…,u*(N))和總利潤的最大值I*=V(x(1),1).其中U(x(k))={0,1,…,x(k)}.求解程序TZ.Mfunction[u,I]=tz(M,N,L)fori=1:M+1V(i,N)=L(i,N);W(i,N)=i-1;endfork=N-1:-1:2fori=1:M+1V(i,k)=0;W(i,k)=i-1;forj=1:iifV(i,k)<L(j,k)+V(i+1-j,k+1)V(i,k)=L(j,k)+V(i+1-j,k+1);W(i,k)=j-1;endendendendV(M+1,1)=0;W(M+1,1)=M;forj=1:M+1ifV(M+1,1)<L(j,1)+V(M+2-j,2)V(M+1,1)=L(j,1)+V(M+2-j,2);W(M+1,1)=j-1;endendI=V(M+1,1);u(1)=W(M+1,1); s二M-u(l);fori=2:Nu(i)=W(s+1,i);s=s-u(i);end應(yīng)用實例:某公司新購置了某種設(shè)備6臺,欲分配給下屬的4個企業(yè).已知各企業(yè)獲得這種設(shè)備后年創(chuàng)利潤如表,問如何分配這些設(shè)備能使年創(chuàng)總利潤最大,最大利潤為多少?M=6;N=4;L=[0,0,0,0;4,2,3,4;6,4,5,5;7,6,7,6;7,8,8,6;7,9,8,6;7,10,8,6];[u,I]=tz(M,N,L)§6多目標(biāo)規(guī)劃在日常生產(chǎn)、管理、經(jīng)營等活動中,經(jīng)常會遇到多目標(biāo)決策問題,如在一個生產(chǎn)過程中,人們總是期望高產(chǎn)出、少用料、省工時等等,在風(fēng)險投資中,希望收益大、風(fēng)險小.多目標(biāo)規(guī)劃的一般模型為minf(x)s.t.g(x)>0 (vp)h(x)二0其中f(x)二(fi(X)，f2(X)，…,f(x))，g(x)二(gi(X)，…,gm(x))，h(x)二(hi(X)，…,h(x))有效解和弱有效解a<=boa<bii設(shè)x*GD,如果對VxGD,f(x*)<=f(x則稱x*為(vp)的絕對最優(yōu)解.6.L3設(shè)x*GD,如果不存在xGD,使得f(x)<=(<)f(x*)則稱x*為(vp)的(弱)有效解或pareto最優(yōu)解.求解多目標(biāo)函數(shù)的評價函數(shù)方法評價函數(shù)法是求對目標(biāo)規(guī)劃有效解的最基本方法.它的基本思想是:借助于幾何和應(yīng)用中的直觀背景,構(gòu)造所謂的評價函數(shù),從而將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題.然后利用單目標(biāo)優(yōu)化問題的求解方法求出最優(yōu)解,并把這種最優(yōu)解當(dāng)作多目標(biāo)規(guī)劃問題的最優(yōu)解.所謂的評價函數(shù)是利用(vp)的目標(biāo)函數(shù)f(x),構(gòu)造一個復(fù)合函數(shù)申(f(x)),然后在(vp)的約束集上極小化申(f(x)).(P的構(gòu)造必須保證在一定條件下，min*(f(x))的最優(yōu)解是(vp)的(弱)有效解.xeD理想點(diǎn)法在(vp)中,先求解p個單目標(biāo)問題minf(x),j二1,2,…,p,設(shè)xeDj其最優(yōu)值為f*,稱f*二(f*,f*,.?.,f*)為一個理想值點(diǎn)，一般很難達(dá)到j(luò) 1 2 p它，我們期望在某種度量下，尋求距f*最近的f作為近似值.一種直接的想法是構(gòu)造評價函數(shù)I*(z)二咗(z-f*)2iiIi=1然后極小化min*(f(x))并將它的最優(yōu)解x*作為(vp)在這種意義下的xeD最優(yōu)解.線性加權(quán)和法構(gòu)造評價函數(shù)*(z)=另九ziii*(z)=另九ziii=1iii=1求解min*(f(x))二九Tf(x),將它的最優(yōu)解x*最為(vp)在該意義下的xeD最優(yōu)解.九為權(quán).一般相對重要的指標(biāo)給予較大的權(quán)系數(shù).i極大極小法在決策時,采取保守策略是穩(wěn)妥的.既在最壞的情況下,尋求最好的結(jié)果.按照這種想法,可以構(gòu)造評價函數(shù)申(z)=maxz1<i<p‘然后求解min申(f(x))=minmaxf(x),并將它的最優(yōu)解作為(vp)在xeD xeD1<ip1這種意義下的最優(yōu)解.還有很多其他形式的評價函數(shù).不一一列舉建模示例用直徑為1的圓木制作截面為矩形的梁,為使重量最輕而強(qiáng)度最大,問截面的長與寬應(yīng)取何尺寸?設(shè)矩形截面的長與寬分別為x,x,這時梁的面積為xx,它決定121重量，而梁的強(qiáng)度取決于截面矩1xx2，故得到模型為612minxx121maxxx2612s.t.x2+x2=112x,x>012§7組合最優(yōu)化問題組合最優(yōu)化(combinatorialoptimization)是通過對數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，是運(yùn)籌學(xué)中的一個經(jīng)典且重要的分支，所研究的問題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通訊網(wǎng)絡(luò)等諸多領(lǐng)域。該問題可用數(shù)學(xué)模型描述為minf(x)s.t.g(x)>0xGD其中，f(X)為目標(biāo)函數(shù)，g(x)為約束條件，x為決策變量,D表示有限個點(diǎn)組成的集合。一個組合優(yōu)化問題可用三參數(shù)(D，F(xiàn),f)表示，其中D表示決策變量的定義域，F(xiàn)表示可行解區(qū)域F={xIxgD,g(x)>0},F中的任何一個元素稱為該問題的可行解，f表示目標(biāo)函數(shù).滿足f(x*)二min{f(x)IxgF}的可行解x*稱為該問題的最優(yōu)解?組合最優(yōu)化問題的特點(diǎn)是可行解集合為有限點(diǎn)集.由直觀可知,只要將D中有限個點(diǎn)逐