最優(yōu)化方法模擬試題二

最優(yōu)化方法》模擬試題二一、填空題：1．最優(yōu)化問題的數(shù)學(xué)模型一般為：，其中稱為目標(biāo)函數(shù)，稱為約束函數(shù)，可行域D可以表示為，若，稱x*為問題的局部最優(yōu)解，若，稱x*為問題的全局最優(yōu)解。2?設(shè)f(x)=x2+2xx-10x+5x,則其梯度為，海色矩陣11212，令x二(1,0)T,d二(1,-1)T,則f(x)在x處沿方向d的一階方向?qū)?shù)為，幾何意義為,二階方向?qū)?shù)為，幾何意義為3．設(shè)嚴(yán)格凸二次規(guī)劃形式為：minf(x)=x2+x2一2x一x1212s.t.x+x<112x>01x>02則其對偶規(guī)劃為4.求解無約束最優(yōu)化問題：minf（x）,xgRn，設(shè)xk是不滿足最優(yōu)性條件的第k步迭代點，則：用最速下降法求解時，搜索方向dk=用Newton法求解時，搜索方向dk=用共軛梯度法求解時，搜索方向dk=二．（10分）簡答題：試敘述求解無約束優(yōu)化問題的優(yōu)化方法及其優(yōu)缺點。（200字左右）三．（25分）計算題1．（10分）用一階必要和充分條件求解如下無約束優(yōu)化問題的最優(yōu)解：minf（x）=2x3一3x2一6xx（x一x一1）.1112122．（15分）用約束問題局部解的一階必要條件和二階充分條件求解約束問題：minf(x)=Xxpii=1st.c(x)=Xx-a=0ii=1其中p>1,a>0.四．證明題(共33分)1．(10分)設(shè)f(X)=2xtGx+rTx+6是正定二次函數(shù)，證明一維問題2min9(a)=f(xk+adk)的最優(yōu)步長為a:(Xk)Tdk.kdkTGdk2．(23分)考慮如下規(guī)劃問題minf(x),xeRns.t.c(x)<0,i二1,2,…，m.i其中f(x),c(x)(i二1,…,n)是凸函數(shù)，證明：i(1)(7分)上述規(guī)劃為凸規(guī)劃；(8分)上述規(guī)劃的最優(yōu)解集R*為凸集；(8分)設(shè)f(x),c(x)(i二1,2,…,n)有連續(xù)的一階偏導(dǎo)數(shù)，若x*是KT點,i則x*是上述凸規(guī)劃問題的全局解。4)5)6)練習(xí)題一1、建立優(yōu)化模型應(yīng)考慮哪些要素?答：決策變量、目標(biāo)函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準(zhǔn)則。minf(x)答:針對一般優(yōu)化模型s.tg(x)n0,i=12…m，討論解的可行域D,若存在一點X*eD,h(x)=0,j=1,…,p對于VXeD均有f(X*)<f(X)則稱X*為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭代所得到的序列X⑴,X⑵，…,X&)???，滿足f(X(K+i))<f(X(K))，則迭代法收斂；收斂的停止準(zhǔn)則有||X(k+1)-X(停止準(zhǔn)則有||X(k+1)-X(k)||<￡,X(k+1)-X(k)<￡，<￡，X(k)<￡練習(xí)題二1、某公司看中了例中廠家所擁有的3種資源R]、R2、和R3,欲出價收購(可能用于生產(chǎn)附加值更高的產(chǎn)品)。如果你是該公司的決策者，對這3種資源的收購報價是多少？(該問題稱為例的對偶問題)。解：確定決策變量對3種資源報價y,y解：確定決策變量對3種資源報價y,y,y作為本問題的決策變量。123問題的目標(biāo)很清楚——“收購價最小”。資源的報價至少應(yīng)該高于原生產(chǎn)產(chǎn)品的利潤，這樣原廠家才可能賣。確定目標(biāo)函數(shù)確定約束條件因此有如下線性規(guī)劃問題：minw=170y+100y+150y1233y+2y+y>10123s.t<2y+3y+5y>18123y,y,y>0123*2、研究線性規(guī)劃的對偶理論和方法(包括對偶規(guī)劃模型形式、對偶理論和對偶單純形法)答：略。3、用單純形法求解下列線性規(guī)劃問題：minz=X]-x?+x3X]+x2-2x3<22X[+x2+x3<3—X[+x3<4X],x2,x3>0解：(1)引入松弛變量x4，x5，x6minz=X-X+X+0*X+0*X+0*X1234561)s.t2)minz=4-x2+x3X]-2x2+x3X。-2Xq+X.s.t.f234X2+X3+X5X.>0(i=1,2,,5)ix+x-2x+x=21x+x-2x+x=212342x+x+x+x5=3s.t<123-x1+x3+x6=4x1,x2,x3,x4,x5,x6>0-1cb基bx42x53x64x1-1[1]x3-2-1因檢驗數(shù)O2v0,故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量x作為換出的基變量。Cjf1-11000CB基bx1x4x3x4x5x6-1x2211-21000x5110[3]-1100x64-10100120-1100因檢驗數(shù)O3v0,故確定x3為換入非基變量，以x3的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的匕1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/317/3032/31/30因檢驗數(shù)o.>0，表明已求得最優(yōu)解：X*二(0,8/3,1/3,0,0,11/3)，去除添加的松弛變量，原為基變量：問題的最優(yōu)解為：X*=(0,8/3,1/3)。為基變量：(2)根據(jù)題意選取x1，x4，x5，minz=4-x?+x3TOC\o"1-5"\h\zx】-2x2+x3=2x^-2x^+xA-2s.t.<234x2+x§+x§-5x.>0(i-1,2,,5)iCL0-1100CB基bx1x2x3x4x5

0x121-21000x420[1]-2100x5501101c-zj0-1100因檢驗數(shù)o2<0最小，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量x4作為換出的基變量。匕0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x5300[3]-11Cj-zj00-110因檢驗數(shù)O3v0最小，故確定x3為換入非基變量，以X1的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對匸0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31x31001-1/31/3cj-勺0002/31/3因檢驗數(shù)片>0，表明已求得最優(yōu)解：X*二(9,4,1,0,0)。4、分別用大M法、兩階段法和4、分別用大M法、兩階段法和Matlab軟件求解下列線性規(guī)劃問題:minz=4x】+x23X]+x2=39X]+3x2>6X]+2x2<3X],x2>0（1）s.t.<⑵s.t」maxz=10x】+15x?+12x35x】+3x2+兀3<9-5x】+6x2+15x3<152x[+x2+x3>5

x1,x2,x3>0解：(1)大M法根據(jù)題意約束條件1和2可以合并為1,引入松弛變量x3,x4,構(gòu)造新問題。minz=4x+x+Mx+0*x3x+x+x123TOC\o"1-5"\h\z13x+x+x1232st<x+2x12x,???x>0V14cb基cb基bxiX4Mx3300x43120100x431201jj4-3M1-M4x111/31/30x420[5/3]-1/31jj0-1/3M-4/304x13/52/5-1/51x26/5-1/53/50M-7/51/5因檢驗數(shù)o>0,表明已求得最優(yōu)解：X*=⑶5,6/5）。Matlab調(diào)用代碼：f=[4;1];A=[-9,-3;1,2];b=[-6;3];Aeq=[3,1];beq=3;lb=[0;0];[x,fval]=linprog(f,A,b,Aeq,beq,lb)輸出結(jié)果：Optimizationterminated.x=fval=（2）大M法引入松弛變量x4，x5，x6，x7構(gòu)造新問題max=10x+15x+12x+0x+0x+0x—Mx125x+3x+x+x1234—5x+6x+15x+xS.t<12352x+x+x123x，…，x>0J17=9=15—x+x=567單純形表計算略；當(dāng)所有非基變量為負(fù)數(shù)’人工變量x7=0?5,所以原問題無可行解。請同學(xué)們自己求解。Matlab調(diào)用代碼：f=[-10;-15;-12];A=[5,3,1;-5,6,15;-2,-1,-1];x=1x=1b=[9;15;-5];lb=[0;0;0];x=linprog(f,A,b,[],[],lb)輸出結(jié)果：原題無可行解。5、用內(nèi)點法和Matlab軟件求解下列線性規(guī)劃問題:minz=2x】+x2+x§X]+2x2+2X3=6

s.t.f2X]+x2=5解：用內(nèi)點法的過程自己書寫，參考答案：最優(yōu)解X=[4/37/30]；最優(yōu)值5Matlab調(diào)用代碼：f=[2;];]];Aeq=[],2,2;2,],0];beq=[6;5];lb=[0;0;0];[x,fval]=linprog(f,[],[],Aeq,beq,lb)輸出結(jié)果：Optimizationterminated.x=fval=6、用分支定界法求解下列問題：2)maxz=7x】+9x2-x】+3x2<2)maxz=7x】+9x2-x】+3x2<6s.t.<7X]+x2<35x],x2>0且x】為整數(shù)(1)s.t.<5x】+9x2<45、x】,x2>0且均為整數(shù)解：(1)調(diào)用matlab編譯程序bbmethodf=[-5;-8];G=[】】;59];h=[6;45][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[];]],])x=33y=-39最優(yōu)解[33]；最優(yōu)值39(2)調(diào)用matlab編譯程序bbmethod

f=[-7;-9];G=[-13;71];h=[6;35][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;0],1)x=50y=-35最優(yōu)解[50]；最優(yōu)值357、用隱枚舉法和Matlab軟件求解下列問題:1）minz=4x】1）minz=4x】+3x丄+2x32X]—5x2+3X3<44X]+x2+3x3>3x2+兀彳>1xj=0或1(j=1,2,3)s.t.<；（2）maxz=3x】+2x?—5x3—2x4+3x§x]+x2+x3+2x4+x5<47x]+3x3—4x4+3x5<811x]—6x2+3x4—3x5>1xy二0或1(j二1,2,,5)s.t.<解：隱枚舉法：（1）將（0，0，0）（0，0，1）（0，1，0）（1，0，0）（0，1，1）（1，0，1）（1，1，0）（1，1，1）分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是（0，0，1），目標(biāo)函數(shù)最優(yōu)值2.（2）將（0,0,0,0,0）（0,0,0,0,1）（0,0,0,1,0）（0,0,1,0,0）....（1,1,1，1，1）分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是（1，1，0，0，0），目標(biāo)函數(shù)最優(yōu)值-5。Matlab軟件求解：（1）調(diào)用代碼：f=[4;3;2];A=[2,-5,3;-4,-1,-3;0,-1,-1];b=[4;-3;-1];[x,fval]=bintprog(f.A,b,[],[]);%價值向量f%不等式約束系數(shù)矩陣A,□中的分號“；”％為行分隔符%不等式約束右端常數(shù)向量b%調(diào)用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。輸出結(jié)果x=001fval=22）調(diào)用代碼f=[-3;-2;5;2;3];%價值向量fA=[1,1丄2,1;7,0,3,-4,3;-11,6,0,-3,3];%不等式約束系數(shù)矩陣A,□中的分號“；”％為行分隔符b=[4;8;-1];[x,fval]=bintprog(f,A,b,[],[]);%不等式約束右端常數(shù)向量b%調(diào)用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。輸出結(jié)果

000fval=-5最優(yōu)值5。8、某地區(qū)有A、B、C三個化肥廠，供應(yīng)本地甲、乙、丙、丁四個產(chǎn)糧區(qū)。已知各化肥廠可供應(yīng)化肥的數(shù)量和各產(chǎn)糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運價如表2-28所示。試制定一個使總運費最少的化肥調(diào)撥方案。表2-1運價/\產(chǎn)糧化肥廠甲乙丙丁各廠供應(yīng)量/萬噸A,58737A,491078A384293各區(qū)需要量/萬噸6633解：設(shè)A、B、C三個化肥廠為A.A2、A3，甲、乙、丙、丁四個產(chǎn)糧區(qū)為B「B2、B3、B4；Cj為由Ai運化肥至Bj的運價，單位是元/噸；Xjj為由Ai運往Bj的化肥數(shù)量（i=l,2,3;j=l,2,3,4）單位是噸；z表示總運費，單位為元，依題意問題的數(shù)學(xué)模型為：34minz二乙乙cxijiji=1j=1x+x+x=6112131x+x+x=6122232x+x+x=3132333x+x+x=3142434x+x+x+x=711121314x+x+x+x=821222324x+x+x+x=731323334該題可以用單純形法或matlab自帶工具箱命令（1inprog）求解。*9、求解下列不平衡運輸問題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價格c..，框外右側(cè)的一列數(shù)ij為各發(fā)點的供應(yīng)量a.，框底下一行數(shù)是各收點的需求量叩：108015108015要求收點3的需求必須正好滿足。752050200575205020055要求收點1的需求必須由發(fā)點4供應(yīng)。10、一公司經(jīng)理要分派4位推銷員去4個地區(qū)推銷某種商品。推銷員各有不同的經(jīng)驗和能力，因而他們在不同地區(qū)能獲得的利潤不同，其獲利估計值如表2-29所示。公司經(jīng)理應(yīng)怎樣分派才使總利潤最大？'35272837'M—C..'35272837'M—C..(513123、,28342940126110,35243233M=40>51687,,.24322528,.1681512,解：用求極大值的“匈牙利法”求解。效率矩陣表示為：行約簡/2109.12611..0113.807212(0)810611(0)6(0)、80*0*2所畫()0兀素少于n(n44丿表2-2地區(qū)推銷員、1234135272837228342940335243233424322528=4),未得到最優(yōu)解，需要繼續(xù)變換矩陣(求能覆蓋所有0元素的最少數(shù)直線集合):<2106(0)、1268()*(°、[[n*(0)110*28(0)44j8(0)44丿VVV

未被直線覆蓋的最小元素為Cj=2，在未被直線覆蓋處減去2,在直線交叉處加上2。'(0)840*(08401(0)10460標(biāo)號1046011040*11(0)48046J18(0)46J?r100000011?得最優(yōu)解：0010i0100J???使總利潤為最大的分配任務(wù)方案為：1—1，2—4，3—3，4—2此時總利潤W=35+40+32+32=139練習(xí)題三min申(t)=13一2t+1min申(t)=13一2t+1t>0的近似最優(yōu)解，已知)(t)的單谷區(qū)間為［0,3］，要求最后區(qū)間精度=0.5o答:t=0.8115；最小值-0.0886.(調(diào)用golds.m函數(shù))2、求無約束非線性規(guī)劃問題minf(x,x,x)=x2+4x2+x2一2x123123的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點：則由Vf(x)二0得1,f二2x-2，更二8x,dx1dx212再用充分條件進行檢驗：d2f二2竺dx2dx212廠2即V2f=062fdx230\dx3d2f

dxdx12二0，空dxdx13x=0，x=023二0，江dxdx230為正定矩陣得極小點為x*=(1，0,0)2JT，最優(yōu)值為-1。解二：目標(biāo)函數(shù)改寫成minf(x,x,x)=(x一1)2+4x2+x2一1123123易知最優(yōu)解為(1,0,0)，最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。minf(X)=x一x+2x2+2xx+x221122其中X=(xi,X2)T，給定初始點X0二(o,o)T。解一：目標(biāo)函數(shù)f(x)的梯度V解一：目標(biāo)函數(shù)f(x)的梯度Vf(x)=1+4x+2x12—1+2x+2x12Vf(X(0))二1令搜索方向d(D=—Vf(X(o))=—11再從X(0)出發(fā)，沿d(1)方向作一維尋優(yōu),0+X—1—X0+X—1—X01令9'(九)=2九—2=0可得九110—1—1+=011求出X(1)點之后，與上「-1「丁類似地，進行第二次迭代：Vf(X(1))=—1令d⑵=—Vf(X(1))=1X⑴=X(0)+九d(1)=1令步長變量為為，最優(yōu)步長為為2,則有步長變量為為，最優(yōu)步長為為1，則有X(0)+竭(1)二故f(x)二f(X(0)+九d(1))二(—九)—九+2(—九)2+2(—九)九+九2二九2—2九=9(九)1—11九—11九+1故f(x)=f(X(1)+九d⑵)二(九一1)—(X+1)+2(X—1)2+2(九一1)(九+1)+(九+1)2=5九2—2九一1=9(九)2Vf(X(2)Vf(X(2))=0.2—0.2此時所達到的精度IV(X(2))卜0.28281「-1「1丁「-0.8「X=—X(2)=X(1)+Xd(2)=+一=252151_1.2_令9'(X)=10X—2=0可得2本題最優(yōu)解X*=，f(X*)=—1,25解二：利用matlab程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件functionf=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);functiong=gfun(x)g=[1+4*x(1)+2*x(2),-1+2*x(1)+2*x(2)];調(diào)用文件

x0=[0,0];[x,val,k]=grad('fun','gfun',x0)結(jié)果x=[-1.0000,]val=k=33即迭代33次的到最優(yōu)解x=[-1.0000,]；最優(yōu)值val=。4、試用Newton法求解第3題。其逆矩陣為G-1=解一：其逆矩陣為G-1=1+4x+2x2—1+2x+2x0.5—0.50.5—0.5—0.51X⑴二X(0)—G-1Vf(X(0))J0,0]t—I—0.55-；半,—dJ—1,10計算||Vf(Xd》||=0。本題最優(yōu)解X*=15,f(X*)=—1,25解二：除了第3題建立兩個M文件外，還需建立Hesse矩陣的M文件利用matlab程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件functionf=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);functiong=gfun(x)g=[1+4*x(1)+2*x(2),-1+2*x(1)+2*x(2)];functionh=hess(x)g=[42;22];調(diào)用newton.m文件x0=[0,0];[x,val,k]=newton('fun','gfun','hess',x0)結(jié)果x=[-1.0000,]val=k=15、用Fletcher—Reeves法求解問題minf(X)=x2+25x212其中X=(x,x)t，要求選取初始點X0=(2,2)t,￡=10-6。12解一：f(x)二2(X1,叮_20_f(x)二2(X1,叮_20_x-20_1,G=050x1-2J_050_r=Yf(x)=(2x,50x)t.12第一次迭代:令p=-r=(一4,-100)t,00r4(4,100)100r201r-41(-4,-100)050-100rrra=—0_0—0prGp00150即，X(I)=X(0)+ap=(1.92,0)T00第二次迭代：r=(3.84,0)r,1IIrII231=,p=—r+BIIrII220001-0p=(—3.846,—0.15)t100(3.84,0)「3.84-一0(-3.846,-0.15)r201「-3.846050」l_-0」5_rrra=—1_1—=1prGp11=0.4802X⑵=X(1)+ap=(0.0732,-0.072)r1第三次迭代：r=(0.1464,-3.6)r(建議同學(xué)們自己做下去，注意判別||r<￡k解二：利用matlab程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件functionf=fun(x)f=x(1)人2+25*x(2)*x(2);functiong=gfun(x)g=[2*x(1),50*x(2)];調(diào)用frcg.m文件x0=[2,2]';epsilon=1e-6;[x,val,k]=frcg('fun','gfun',x0,epsilon)結(jié)果x=1.0e-006*[,]k=616、試用外點法(二次罰函數(shù)方法)求解非線性規(guī)劃問題Jminf(X)=(x-2)2+x2Ist.g(X)=x-1>0i2其中X=(x,x)gR212解：設(shè)計罰函數(shù)P(x,M)=f(X)+M*[g(X)]A2采用Matlab編程計算，結(jié)果x=[10]；最優(yōu)結(jié)果為1。(調(diào)用)7、用內(nèi)點法(內(nèi)點障礙罰函數(shù)法)求解非線性規(guī)劃問題：X2(i+VT73)X2(i+VT73)i/2、(建議同學(xué)自己編程序計算)|minf(X)二x2+x2h(X)二x+x—2二0112解：建立乘子法的增廣目標(biāo)函數(shù)：屮(x,九Q)入(x+x一2)+—(x+x一2)八21212212令：劉(x,八,b)=2x—九+b(x+x—2)=01128、用乘子法求解下列問題當(dāng)乘子九取2時，或發(fā)參數(shù)b趨于無窮時，得到X=1]=x*即最優(yōu)解。min(x+1)3+x2s.tx—1>01x>0解：容易看出此問題最優(yōu)解為x=[10]；最優(yōu)值為8.給出罰函數(shù)為P(x,r)=(x+1)3+x+r(1/(x一1)+1/x)1212令=3(x+i)2—^_=0；=1—二=0x1(x—1)2xx211/2、2從而當(dāng)rT0+時，x從而當(dāng)rT0+時，x(r)二Tdx1。屮(x,九Q)2「一,2、0=2x一九+b(x+x—2)=0ax21271解上述關(guān)于x的二元一次方程組得到穩(wěn)定點2b+九]2b+2I2b+XI2b+2I(建議同學(xué)自己編程序計算)練習(xí)題四1、石油輸送管道鋪設(shè)最優(yōu)方案的選擇問題：考察網(wǎng)絡(luò)圖4-6,設(shè)A為出發(fā)地，F(xiàn)為目的地，B，C，D，E分別為四個必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設(shè)的位置，線段旁的數(shù)字表示鋪設(shè)這些管線所需的費用。問如何鋪設(shè)管道才能使總費用最?。繄D4-1解：第五階段：E1—F4；E2—F3；

第四階段：DI—El—F7；D2—E2—F5；D3—El—F5；第三階段：C1—D1—E1—F12；C2—D2—E2—F10；C3—D2—E2—F8；C4—D3—E1—F9第二階段：Bl—C2—D2—E2—Fl3；B2—C3—D2—E2—Fl5；第一階段：A—Bl—C2—D2—E2—Fl7；最優(yōu)解：A—Bl—C2—D2—E2—F最優(yōu)值：l7maxx+x+xmaxx+x+x=27￡123x,x,x>0

123解:xi二9,x2二9,x3二9，最優(yōu)值為9。3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃rmaxz=7x2+6x+5x212stx+2x<10￡12x一3x<912x,x>012解：用順序算法階段：分成兩個階段’且階段-2分別對應(yīng)x1，x2。決策變量：x1,x2狀態(tài)變量：v,w分別為第j階段第一、第二約束條件可供分配的右段數(shù)值。iif1*(v1,w1)=0<x1<v10<x11<w11max{7f1*(v1,w1)=0<x1<v10<x11<w11x*=min{v,w}11f*(v,w)=max{5x2+f*(v一2x,w+3x)}222122220<x2<5=max{5x2+min{7(v一2x)2+6(v一2x),7(w+3x)2+6(w+3x)}}222222220<x<52由于丁10,w2=9,f*(v,w)=f*(10,9)=max{min{33x2-292x+760,68x2+396x+621}22220<x2<52222可解的x1=96x2=0.2，最優(yōu)值為獨92。4、設(shè)四個城市之間的公路網(wǎng)如圖4-7。兩點連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應(yīng)的最短距離。

圖4-2城市公路網(wǎng)解：城市1到城市4路線——1-3-4距離10；城市2到城市4路線——2-4距離8；城市3到城市4路線——3-4距離4。5、某公司打算在3個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設(shè)置不同數(shù)量的銷售點每月可得到的利潤如表4-19所示。試問在各地區(qū)如何設(shè)置銷售點可使每月總利潤最大。表4-1地區(qū)銷售點01234101625303220121721223010141617解：將問題分為3個階段，k=1,2,3；決策變量xk表示分配給第k個地區(qū)的銷售點數(shù);狀態(tài)變量為sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù);狀態(tài)轉(zhuǎn)移方程：$￡+]=$￡—Xp，其中S]=4；允許決策集合：Dk(sk)={xkIOWxkWsk}kkkkk階段指標(biāo)函數(shù)：gk(xk)表示xk個銷售點分配給第k個地區(qū)所獲得的利潤;最優(yōu)指標(biāo)函數(shù)fk(sk)表示將數(shù)量為sk的銷售點分配給第k個至第3個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃基本方程為：f(s)二max[g(X)+f(s-x)]k二3,2,1kk—,kkk+1kkovxk<skf(s)=o44k=3時，f(s)=max[g(x)]333X3=S3

g3(和f(s)丿33x*3012340000110101214142316163417174k=2時，f(s)=max[g(x)+f(s-x)]22甘/22322何=m：x[gw+何=m：x[gw+小-xi)]，代)=+f2(4-xi)]g2(X2)+f3(丁—x)2f(s)丿22x*201234000010+1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312,3k=1時,gi(xiM0ixi)0123440+3116-2725-2230-1232-0472最優(yōu)解為：X]*=2,%2*=1，工3*=1,介(4)=47，即在第1個地區(qū)設(shè)置2個銷售點，第2個地區(qū)設(shè)置1個銷售點，第3個地區(qū)設(shè)置1個銷售點，每月可獲利潤47。6、設(shè)某廠計劃全年生產(chǎn)某種產(chǎn)品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產(chǎn)產(chǎn)品A的生產(chǎn)費用與產(chǎn)品的平方成正比，系數(shù)為。廠內(nèi)有倉庫可存放產(chǎn)品，存儲費為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。解：四個季度為四個階段，采用階段編號與季度順序一致。設(shè)sk為第k季初的庫存量，則邊界條件為S1=S5=0設(shè)xk為第k季的生產(chǎn)量，設(shè)yk為第k季的訂貨量；sk，xk，，yk都取實數(shù)，狀態(tài)轉(zhuǎn)移方程為sk+1=sk+xk-yk仍采用反向遞推，但注意階段編號是正向的目標(biāo)函數(shù)為：f(x)=mm￡(0.005x2+s)iiX1,X2,X3,X4i=1第一步：(第四季度)總效果f4(s4,x4)=0.005x42+s4由邊界條件有：S5=S4+X4-『4=0，解得：％4*=120074將X4*代入74($4，工4)得：f4*(s4)=0.005(1200—s4)2+s4=7200-11s4+0.005s42第二步：(第三、四季度)總效果f3(s3，x3)=0.005x32+s3+f4*(s4)將s4=s3+x3-500代入f3(s3，x3)得：f(s,x)=0.005x2+s+7200-11(x+s-500)TOC\o"1-5"\h\z333333+0.005(x+s-500)233=0.01x2+0.01xs-16x+0.005s2-15s+1395033333fs3,x3)=0.02x+0.01s-16=0dx333解得x*=800-0.5s,代入f(s,x)得33333f*(s)=7550-7s+0.0025s23333第三步：(第二、三、四季度)總效果f2(s2，x2)=0.005x22+s2+f3*(s3)將s3=s2+x2-700代入f2(s2，x2)得：f(s，x)=0.005x2+s+7550-7(x+s-700)222222+0.0025(x+s-700)222號(s2,x2)=0.015x+0.005(s-700)-7=0dx222解得x*=700-(1⑶s,代入f(s,x)得2222f*(s)=10000-6s+(0.005.3)s222■2第四步：(第一、二、三、四季度)總效果f1(s1，x1)=0.005x12+s1+f2*(s2)將s2=s1+x1-600=x1-600代入f1(s1，x1)得：

f(s,x)=0.005x2+s+10000-6(x-600)TOC\o"1-5"\h\ziiiiii+(0.005.⑶(x-600)2顯=(0.043)x-8=0dxii解得x*=600,代入f(s,x)得iiiif*(s)=ii800i2由此回溯：得最優(yōu)生產(chǎn)-庫存方案xi*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。7、某種機器可在高低兩種不同的負(fù)荷下進行生產(chǎn)。設(shè)機器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g=8ui，其中ui為投入生產(chǎn)的機器數(shù)量，年完好率a在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為h=5y,其中y為投入生產(chǎn)的機器數(shù)量，年完好率為b。假定開始生產(chǎn)時完好機器的數(shù)量S]=I000。試問每年如何安排機器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：構(gòu)造這個問題的動態(tài)規(guī)劃模型：設(shè)階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機器數(shù)量，同時也是第k-1年度末時的完好機器數(shù)量。決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機器數(shù)量，于是sk-uk為該年度中分配在低負(fù)荷下生產(chǎn)的機器數(shù)量。這里sk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如sk，就表示一臺機器在k年度中正常工作時間只占6/I0；uk，就表示一臺機器在該年度只有3/I0的時間能在高負(fù)荷下工作。狀態(tài)轉(zhuǎn)移方程為：s=au+b(s-u)=0.7u+0.9(s-u),k=i,2,..?,5k+ikkkkkkk段允許決策集合為：D(s)={u|0<u<s}kkkkk設(shè)v(s,u)為第k年度的產(chǎn)量，則v=8u+5(s一u)kkkkkkk故指標(biāo)函數(shù)為：V=丈v(s,u)i,5kkkk=i令最優(yōu)值函數(shù)fk(sk)表示由資源量sk出發(fā)，從第k年開始到第5年結(jié)束時所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆推關(guān)系式：f(s)=066f(s)=066<f(s)=kkmax{8u+5(s訃Dk4)kkk=i,2,3,4,5-u)+f〔0.7u+0.9(skk+ikku)]}k從第5年度開始，向前逆推計算。當(dāng)k=5時，有：5max0<u5<S5當(dāng)k=5時，有：5max0<u5<S5+5（s—u）+f[0.7u+0.9（s555655u）]}5max0<u5<s5=max{8u+5（s—u5）}5550<u5<s5{3u+5s}55因是U5的線性單調(diào)增函數(shù)，故得最大解U5*，相應(yīng)的有:①s5)二8s5當(dāng)k=4時，有：f（s）=max44440<uf（s）=max44440<u4<s4=max0<u4<s4=max{u+5（s44^u+5（s44u）+f[0.7u+0.9（s-u）]}45444u）+8[0.7u+0.9（s-u）]}44440<u4<s4=max{13.6u+12.2（s-u）}4440<u4<s4{1.4u+12.2s}44故得最大解，U4*=s4,相應(yīng)的有f(s)=13.6s44依此類推，可求得u*=s,相應(yīng)的f(s)=17.5s3333<u*=0,相應(yīng)的f(s)=20.8s222u*=0,相應(yīng)的f(s)=23.7s1111因s1=1000，故：f(s1)=23700計算結(jié)果表明:最優(yōu)策略為u*=0,u*=0,u*=s,u*=s,u*=s12334455即前兩年應(yīng)把年初全部完好機器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機器投入高負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺。在得到整個問題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即從始端向終端遞推計算出每年年初完好機器數(shù)。已知s1=1000臺，于是可得：s=0.7u*+0.9（s一u*）=0.9s=900（臺）21111s=0.7u*+0.2（s一u*）=0.9s=810（臺）TOC\o"1-5"\h\z2222s=0.7u*+0.9（s一u*）=0.7s=567（臺）3333s=0.7u*+0.9（s一u*）=0.7s=397（臺）4444s=0.7u*+0.9（s一u*）=0.7s=278（臺）55558、有一輛最大貨運量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)單位價值如表4-20所示。應(yīng)如何裝載可使總價值最大？表4-2貨物編號i123單位重量（t）345單位價值ci456解：建模設(shè)三種物品各裝x,x,x件123max(4x+5x+6x)123(3x+4x+5x<102123Ix>0,xg厶j=1,2,3jj利用動態(tài)規(guī)劃的逆序解法求此問題。s=c,D(s)={x10<x<s}

111111s=s一x,D(s)={x10<x<s}

21122222s=s一x,D(s)={x10<x<s}2233333狀態(tài)轉(zhuǎn)移方程為：s=T(s,x)=s-x,k=3,2,1k+1kkkkk該題是三階段決策過程，故可假想存在第四個階段，而x4=0，于是動態(tài)規(guī)劃的基本方程為:f(s)=max[x,f(s)],k=3,2,1kkkk+1k+12xkgDK(sk)f(s)=044k=3,f(s)=max{6x}TOC\o"1-5"\h\z3333x3=0丄,[.\/5]3k=2,f(s)=max[5x+f(s)]22233x?=0丄，[j]=max[5x+f(s一4x)]..2322x2=0,1,,[4]k=1,f(s)=max[4x+f(s)]11x1=0,1,2,3122=max[4x+f(s一3x)]

x1=0,1,2,31211計算最終結(jié)果為x*=2,x*=1,x*=0，最大價值為13。1239、設(shè)有A，B，C三部機器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計結(jié)果表明，機器A，B，C產(chǎn)生次品的概率分別為pA=30%,PB=40%,PC=20%,而產(chǎn)品必須經(jīng)過三部機器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬元進行技術(shù)改造，以便最大限度地提高產(chǎn)品的成品率指標(biāo)?，F(xiàn)提出如下四種改進方案：方案1：不撥款，機器保持原狀；方案2：加裝監(jiān)視設(shè)備，每部機器需款1萬元；方案3：加裝設(shè)備，每部機器需款2萬元；方案4：同時加裝監(jiān)視及控制設(shè)備，每部機器需款3萬元；采用各方案后，各部機器的次品率如表4-21。表4-3ABC不撥款30%40%20%撥款i萬元20%30%i0%撥款2萬元i0%20%i0%撥款3萬元5%i0%6%問如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解：為三臺機器分配改造撥款，設(shè)撥款順序為A,B,C,階段序號反向編號為k即第一階段計算給機器C撥款的效果。設(shè)sk為第k階段剩余款，則邊界條件為s3=5；設(shè)xk為第k階段的撥款額狀態(tài)轉(zhuǎn)移方程為sk-1=sk-xk；目標(biāo)函數(shù)為maxR=(1-PA)(1-PB)(1-PC)仍采用反向遞推第一階段：對機器C撥款的效果R1（si，xi）=d］（si，xi）xR0（s0,x0）=d］（s］,xi）s0123x1*(片,幵*)001121,23343

第二階段：對機器B,C撥款的效果由于機器A最多只需3萬元，故s2>2遞推公式：人2($2，工2)=〃2($2，工2”R](si，xi*)例：R2(3,2)=d2(3,2)xR](l,l)=(l-0.2)x得第二階段最優(yōu)決策表邊界條件：s3=5遞推公式：R3(s3,x3)=d3(s3,x3)xR2(s2,x2*)例：R3(5,3)=d3(5,3)xR2(2,2)=(l-0.05)x得第三階段最優(yōu)決策表\^2x*兀2RI：%3=1,*2=3,X]=l,人3=0.8x0.9xII：x3=2,x2=2,x1=1,R3xxIII：x3=2,x2=3,x1=0,R3xx練習(xí)題五1、考察多目標(biāo)規(guī)劃問題—x+2,—2WxW1其中f(x)=X2,f(x)=]1,1<x<2,試畫出個目標(biāo)函數(shù)的圖形，并求出12x一1,x>2R,R,R,R,R，這里R是min/(x)的最優(yōu)解集。TOC\o"1-5"\h\z12abpawpi一？<工<41解：2、用線性加權(quán)法中的^-法求解下述多目標(biāo)規(guī)劃問題minf(x)=4x+6x112maxf(x)=3x+3x。212'2x+4x<1412s.t<6x+3x<2412x,x>012解：minf(x)二4x+6x最優(yōu)解為x(d=[O0]t；112maxf(x)二3x+3x最優(yōu)解為x(2)=[32]t；212

利用a法得線性方程組：枕*0+九*0=a12<尢*24—尢*15=a12尢+尢=112解得唯一加權(quán)系數(shù)九二[0.3846,0.6154]T原多目標(biāo)規(guī)劃加權(quán)后minF(x)二0.3846f(x)—0.6154f(x)12解得加權(quán)后的最優(yōu)解為：x*=[40]t3、用線性加權(quán)求和法求解下述多目標(biāo)規(guī)劃問題，取九二0.6,九二0.4。12v一minF(x)=(x一3x,2x+x)t12123x+2x<612x+3x<3S.t<122x一x<212x,x>012解：將問題轉(zhuǎn)化為一個新的單目標(biāo)規(guī)劃問題。minv(F(x))=0.6(x一3x)+0.4(2x+x)1212約束條件同上，該問題轉(zhuǎn)化為線性規(guī)劃問題，可用單純形法求解，也可用Matlab命令求解(求解過程略。解得加權(quán)后的最優(yōu)解為：x*=[01]t，最優(yōu)值為-1.4。4、用平方和加權(quán)法求解多目標(biāo)規(guī)劃問題：V一min(f(x),f(x))T2其中x一x<4其中x一x<412f(x)=x,f(x)=x，D:<x+x<8，1122九=*九解：不難看出兩個目標(biāo)函數(shù)下界均為0minF(x)=-x2+—x2313212x,x>012得平方和加權(quán)法后的新目標(biāo)規(guī)劃問題x一x<412D”x+x<812x,x>012利用matlab程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件functionf=fun(x)f=l/3*x(l)人2+2/3*x(2)*x(2);[x,fval]=fmincon(‘f',[00],[1-1;11],[4;8],[],[],[00])解得最優(yōu)解為：x*=[00]t，最優(yōu)值為0。5、用極小極大法和Matlab軟件求解下述多目標(biāo)規(guī)劃問題v-minF(x)=((x-3)2+x2,x2+(x-2)2)tl2l2。s.tx+x<2l2解：取評價函數(shù)為v(F(x))=max[(x—3)2+x2,x2+(x—2)2]，再求l2l2iminv(F(x))=min{max[(x—3)2+x2,x2+(x—2)2]}DiMatlab軟件求解編制M文件functionf=mnmax(x)f(1)=(x(1)-3)A2+x(2)A2;f(2)=x(1)A2+(x(2)-2)A2設(shè)初值x0=[0;0];調(diào)用函數(shù)[x,fval]=fminimax(@mnmax,x0,[11],[2])結(jié)果：fval=可得X*=[1.3,0.7]t；對應(yīng)f=f=3.38從而X*=[1.3,0.7]t為原問題的解。12附習(xí)題中用過的Matlab程序1、bbmethodfunction[x,y]=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options)%整數(shù)線性規(guī)劃分支定界法，可求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃。%y=minf'*xs.t.G*x<=hGeq*x=heqx為全整數(shù)或混合整數(shù)列向量%用法%[x,y]=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options)%參數(shù)說明%lb:解的下界列向量(Default:-int)%ub:解的上界列向量(Default:int)%x:迭代初值列向量%id:整數(shù)變量指標(biāo)列向量，1-整數(shù)，0-實數(shù)(Default:l)globalupperoptcx0AbAeqbeqIDoptions;ifnargin<10,options=optimset({});options.Display='off';options.LargeScale='off';endifnargin<9,id=ones(size(f));endifnargin<8,x=[];endifnargin<7|isempty(ub),ub=inf*ones(size(f));endifnargin<6|isempty(lb),lb=zeros(size(f));endifnargin<5,heq=[];endifnargin<4,Geq=[];endupper=inf;c=f;A=G;b=h;Aeq=Geq;beq=heq;x0=x;ID=id;ftemp=IntLP(lb(:),ub(:));x=opt;y=upper;%下面是子函數(shù)functionftemp=IntLP(vlb,vub)globalupperoptcx0AbAeqbeqIDoptions;[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);ifhow<=0return;end;ifftemp-upper>0.00005%inordertoavoiderrorreturn;end;ifupper-ftemp>0.00005%inordertoavoiderroropt=x';upper=ftemp;return;elseopt=[opt;x'];return;end;end;notintx=find(abs(x-round(x))>=0.00005);%inordertoavoiderrorintx=fix(x);tempvlb=vlb;tempvub=vub;ifvub(notintx(1,1),1)>=intx(notintx(1,1),1)+1;tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1;ftemp=IntLP(tempvlb,vub);end;ifvlb(notintx(1,1),1)<=intx(notintx(1,1),1)tempvub(notintx(1,1),1)=intx(notintx(1,1),1);ftemp=IntLP(vlb,tempvub);end;2、golds.mfunction[s,phis,k,G,E]=golds(phi,a,b,delta,epsilon)%輸入:phi是目標(biāo)函數(shù),a,b是搜索區(qū)間的兩個端點%delta,epsilon分別是自變量和函數(shù)值的容許誤差%輸出：s,phis分別是近似極小點和極小值，G是nx4矩陣，%其第k行分別是a,p,q,b的第k次迭代值[ak,pk,qk,bk],%E=[ds,dphi],分別是s和phis的誤差限.%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%t=(sqrt(5)-1)/2;h=b-a;phia=feval(phi,a);phib=feval(phi,b);p=a+(1-t)*h;q=a+t*h;phip=feval(phi,p);phiq=feval(phi,q);k=1;G(k,:)=[a,p,q,b];while(abs(phib-phia)>epsilon)|(h>delta)if(phip<phiq)b=q;phib=phiq;q=p;phiq=phip;h=b-a;p=a+(1-t)*h;phip=feval(phi,p);elsea=p;phia=phip;p=q;phip=phiq;h=b-a;q=a+t*h;phiq=feval(phi,q);endk=k+1;G(k,:)=[a,p,q,b];endds=abs(b-a);dphi=abs(phib-phia);if(phip<=phiq)s=p;phis=phip;elses=q;phis=phiq;endE=[ds,dphi];function[x,val,k]=grad(fun,gfun,x0)%功能:用最速下降法求解無約束問題:minf(x)%輸入:x0是初始點,fun,gfun分別是目標(biāo)函數(shù)和梯度%輸出：x,val分別是近似最優(yōu)點