最優(yōu)化方法練習(xí)題答案

練習(xí)題一1、建立優(yōu)化模型應(yīng)考慮哪些要素?答：決策變量、目標(biāo)函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準(zhǔn)那么。答：針對一般優(yōu)化模型，討論解的可行域，假設(shè)存在一點，對于均有那么稱為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭代所得到的序列，滿足，那么迭代法收斂；收斂的停止準(zhǔn)那么有，，，，等等。練習(xí)題二1、某公司看中了例2.1中廠家所擁有的3種資源R1、R2、和R3，欲出價收購〔可能用于生產(chǎn)附加值更高的產(chǎn)品〕。如果你是該公司的決策者，對這3種資源的收購報價是多少？〔該問題稱為例2.1的對偶問題〕。解：確定決策變量對3種資源報價作為本問題的決策變量。確定目標(biāo)函數(shù)問題的目標(biāo)很清楚——“收購價最小”。確定約束條件資源的報價至少應(yīng)該高于原生產(chǎn)產(chǎn)品的利潤，這樣原廠家才可能賣。因此有如下線性規(guī)劃問題：*2、研究線性規(guī)劃的對偶理論和方法〔包括對偶規(guī)劃模型形式、對偶理論和對偶單純形法〕。答：略。3、用單純形法求解以下線性規(guī)劃問題：〔1〕；〔2〕解：〔1〕引入松弛變量x4，x5，x6cj→1-11000CB基bx1x2x3x4x5x60x421[1]-21000x532110100x64-101001cj-zj1-11000因檢驗數(shù)σ2<0，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量x4作為換出的基變量。cj→1-11000CB基bx1x4x3x4x5x6-1x2211-21000x5110[3]-1100x64-101001cj-zj20-1100因檢驗數(shù)σ3<0，故確定x3為換入非基變量，以x3的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量x5作為換出的基變量。cj→1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/31cj-zj7/3032/31/30因檢驗數(shù)σj>0，說明已求得最優(yōu)解：，去除添加的松弛變量，原問題的最優(yōu)解為：?！?〕根據(jù)題意選取x1，x4，x5，為基變量：cj→0-1100CB基bx1x2x3x4x50x121-21000x420[1]-2100x5501101cj-zj0-1100因檢驗數(shù)σ2<0最小，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量x4作為換出的基變量。cj→0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x5300[3]-11cj-zj00-110因檢驗數(shù)σ3<0最小，故確定x3為換入非基變量，以x1的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量x5作為換出的基變量。cj→0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31x31001-1/31/3cj-zj0002/31/3因檢驗數(shù)σj>0，說明已求得最優(yōu)解：。4、分別用大法、兩階段法和Matlab軟件求解以下線性規(guī)劃問題：〔1〕；〔2〕解：〔1〕大M法根據(jù)題意約束條件1和2可以合并為1，引入松弛變量x3，x4，構(gòu)造新問題。cj→41M0CB基bx1x2x3x4Mx33[3]1100x431201cj-zj4-3M1-M004x1111/31/300x420[5/3]-1/31cj-zj0-1/3M-4/304x13/5102/5-1/51x26/501-1/53/5cj-zj00M-7/51/5因檢驗數(shù)σj>0，說明已求得最優(yōu)解：。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=0.60001.2000fval=3.6000〔2〕大M法引入松弛變量x4，x5，x6，x7構(gòu)造新問題。單純形表計算略；當(dāng)所有非基變量為負(fù)數(shù)，人工變量=0.5，所以原問題無可行解。請同學(xué)們自己求解。Matlab調(diào)用代碼：f=[-10;-15;-12];A=[5,3,1;-5,6,15;-2,-1,-1];b=[9;15;-5];lb=[0;0;0];x=linprog(f,A,b,[],[],lb)輸出結(jié)果：原題無可行解。5、用內(nèi)點法和Matlab軟件求解以下線性規(guī)劃問題：解：用內(nèi)點法的過程自己書寫，參考答案：最優(yōu)解；最優(yōu)值5Matlab調(diào)用代碼：f=[2;1;1];Aeq=[1,2,2;2,1,0];beq=[6;5];lb=[0;0;0];[x,fval]=linprog(f,[],[],Aeq,beq,lb)輸出結(jié)果：Optimizationterminated.x=1.33332.33330.0000fval=5.00006、用分支定界法求解以下問題：〔1〕；〔2〕解：〔1〕調(diào)用matlab編譯程序bbmethodf=[-5;-8];G=[11;59];h=[6;45][x,y]=bbmethod(f,G,h,[],[],[0;0],[],[1;1],1)x=33y=-39最優(yōu)解[33]；最優(yōu)值39〔2〕調(diào)用matlab編譯程序bbmethodf=[-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〕；〔2〕解：隱枚舉法：〔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];%價值向量fA=[2,-5,3;-4,-1,-3;0,-1,-1];%不等式約束系數(shù)矩陣A，[]中的分號“；”%為行分隔符b=[4;-3;-1];%不等式約束右端常數(shù)向量b[x,fval]=bintprog(f,A,b,[],[]);%調(diào)用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。輸出結(jié)果x=001fval=2〔2〕調(diào)用代碼：f=[-3;-2;5;2;3];%價值向量fA=[1,1,1,2,1;7,0,3,-4,3;-11,6,0,-3,3];%不等式約束系數(shù)矩陣A，[]中的分號“；”%為行分隔符b=[4;8;-1];%不等式約束右端常數(shù)向量b[x,fval]=bintprog(f,A,b,[],[]);%調(diào)用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。輸出結(jié)果x=11000fval=-5最優(yōu)值5。8、某地區(qū)有A、B、C三個化肥廠，供給本地甲、乙、丙、丁四個產(chǎn)糧區(qū)。各化肥廠可供給化肥的數(shù)量和各產(chǎn)糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運價如表2-28所示。試制定一個使總運費最少的化肥調(diào)撥方案。表2-SEQ表2-\*ARABIC28運價/產(chǎn)糧(元/噸)區(qū)化肥廠甲乙丙丁各廠供給量/萬噸A158737A2491078A384293各區(qū)需要量/萬噸6633解：設(shè)A、B、C三個化肥廠為A1、A2、A3，甲、乙、丙、丁四個產(chǎn)糧區(qū)為B1、B2、B3、B4；cij為由Ai運化肥至Bj的運價，單位是元/噸；xij為由Ai運往Bj的化肥數(shù)量〔i=1,2,3;j=1,2,3,4〕單位是噸；z表示總運費，單位為元，依題意問題的數(shù)學(xué)模型為：該題可以用單純形法或matlab自帶工具箱命令〔linprog〕求解。*9、求解以下不平衡運輸問題〔各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價格，框外右側(cè)的一列數(shù)為各發(fā)點的供給量，框底下一行數(shù)是各收點的需求量〕：〔1〕51710要求收點3的需求必須正好滿足。6468032515752050〔2〕51020要求收點1的需求必須由發(fā)點4供給。32410752159601551015解答略。10、一公司經(jīng)理要分派4位推銷員去4個地區(qū)推銷某種商品。推銷員各有不同的經(jīng)驗和能力，因而他們在不同地區(qū)能獲得的利潤不同，其獲利估計值如表2-29所示。公司經(jīng)理應(yīng)怎樣分派才使總利潤最大？表2-SEQ表2-\*ARABIC29地區(qū)推銷員1234135272837228342940335243233424322528解：用求極大值的“匈牙利法”求解。效率矩陣表示為：行約簡M－C行約簡M－CijM=40標(biāo)號列約簡所畫〔〕0元素少于n〔n＝4〕，未得到最優(yōu)解，需要繼續(xù)變換矩陣〔求能覆蓋所有0元素的最少數(shù)直線集合〕：標(biāo)號列約簡√√√√√√未被直線覆蓋的最小元素為cij=2，在未被直線覆蓋處減去2，在直線交叉處加上2。標(biāo)號標(biāo)號∴得最優(yōu)解：∴使總利潤為最大的分配任務(wù)方案為：1→1，2→4，3→3，4→2此時總利潤W=35+40+32+32=139練習(xí)題三1、用0.618法求解問題的間為。答：t=0.8115；最小值-0.0886.〔調(diào)用golds.m函數(shù)〕2、求無約束非線性規(guī)劃問題min=的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點：，，，那么由得，，再用充分條件進(jìn)行檢驗：，，，，，即為正定矩陣得極小點為，最優(yōu)值為-1。解二：目標(biāo)函數(shù)改寫成min=易知最優(yōu)解為〔1,0,0〕，最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。其中，給定初始點。解一：目標(biāo)函數(shù)的梯度令搜索方向再從出發(fā)，沿方向作一維尋優(yōu)，令步長變量為，最優(yōu)步長為，那么有故令可得求出點之后，與上類似地，進(jìn)行第二次迭代：令令步長變量為，最優(yōu)步長為，那么有故令可得此時所到達(dá)的精度此題最優(yōu)解，解二：利用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)用grad.m文件x0=[0,0];[x,val,k]=grad('fun','gfun',x0)結(jié)果x=[-1.0000,1.5000]val=-1.2500k=33即迭代33次的到最優(yōu)解x=[-1.0000,1.5000]；最優(yōu)值val=-1.2500。4、試用Newton法求解第3題。解一：計算目標(biāo)函數(shù)的梯度和Hesse陣目標(biāo)函數(shù)的梯度，其逆矩陣為計算。此題最優(yōu)解，解二：除了第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,1.5000]val=-1.2500k=15、用Fletcher—Reeves法求解問題其中，要求選取初始點。解一：，第一次迭代：令，即，第二次迭代：，，第三次迭代：……〔建議同學(xué)們自己做下去，注意判別〕解二：利用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*[0.2651,0.0088]val=7.2182e-014k=616、試用外點法〔二次罰函數(shù)方法〕求解非線性規(guī)劃問題其中解：設(shè)計罰函數(shù)采用Matlab編程計算，結(jié)果x=[10]；最優(yōu)結(jié)果為1?！舱{(diào)用waidianfa.m〕7、用內(nèi)點法〔內(nèi)點障礙罰函數(shù)法〕求解非線性規(guī)劃問題：解：容易看出此問題最優(yōu)解為x=[10]；最優(yōu)值為8.給出罰函數(shù)為令；從而當(dāng)時，〔建議同學(xué)自己編程序計算〕8、用乘子法求解以下問題解：建立乘子法的增廣目標(biāo)函數(shù)：令：解上述關(guān)于x的二元一次方程組得到穩(wěn)定點當(dāng)乘子取2時，或發(fā)參數(shù)趨于無窮時，得到即最優(yōu)解。〔建議同學(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-SEQ圖4-\*ARABIC6解：第五階段：E1—F4；E2—F3；第四階段：D1—E1—F7；D2—E2—F5；D3—E1—F5；第三階段：C1—D1—E1

—F12；C2—D2—E2—F10；C3—D2—E2—F8；C4—D3—E1—F9；第二階段：B1—C2—D2—E2—F13；B2—C3—D2—E2—F15；第一階段：A—B1—C2—D2—E2—F17；最優(yōu)解：A—B1—C2—D2—E2—F最優(yōu)值：172、用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：，最優(yōu)值為9。3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：用順序算法階段：分成兩個階段，且階段1、2分別對應(yīng)。決策變量：狀態(tài)變量：分別為第j階段第一、第二約束條件可供分配的右段數(shù)值。由于，可解的，最優(yōu)值為702.92。4、設(shè)四個城市之間的公路網(wǎng)如圖4-7。兩點連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應(yīng)的最短距離。圖4-SEQ圖4-\*ARABIC7城市公路網(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-SEQ表4-\*ARABIC19解：將問題分為3個階段，k=1，2，3；決策變量xk表示分配給第k個地區(qū)的銷售點數(shù)；狀態(tài)變量為sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=sk－xk，其中s1=4；允許決策集合：Dk〔sk〕=｛xk|0≤xk≤sk｝階段指標(biāo)函數(shù)：gk〔xk〕表示xk個銷售點分配給第k個地區(qū)所獲得的利潤；最優(yōu)指標(biāo)函數(shù)fk〔sk〕表示將數(shù)量為sk的銷售點分配給第k個至第3個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃根本方程為：k=3時，k=2時，k=1時，，最優(yōu)解為：x1*=2，x2*=1，x3*=1，f1(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ù)為0.005。廠內(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ù)為：第一步：(第四季度)總效果f4(s4,x4)=0.005x42+s4由邊界條件有：s5=s4+x4–y4=0，解得：x4*=1200–s4將x4*代入f4(s4,x4)得：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)得：第三步：(第二、三、四季度)總效果f2(s2,x2)=0.005x22+s2+f3*(s3)將s3=s2+x2700代入f2(s2,x2)得：第四步：(第一、二、三、四季度)總效果f1(s1,x1)=0.005x12+s1+f2*(s2)將s2=s1+x1–600=x1–600代入f1(s1,x1)得：由此回溯：得最優(yōu)生產(chǎn)–庫存方案x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。7、某種機(jī)器可在上下兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g=8u1，其中u1為投入生產(chǎn)的機(jī)器數(shù)量，年完好率a=0.7；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為h=5y，其中y為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開始生產(chǎn)時完好機(jī)器的數(shù)量s1=1000。試問每年如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：構(gòu)造這個問題的動態(tài)規(guī)劃模型：設(shè)階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機(jī)器數(shù)量，同時也是第k?1年度末時的完好機(jī)器數(shù)量。決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是sk?uk為該年度中分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。這里sk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如sk=0.6，就表示一臺機(jī)器在k年度中正常工作時間只占6/10；uk=0.3，就表示一臺機(jī)器在該年度只有3/10的時間能在高負(fù)荷下工作。狀態(tài)轉(zhuǎn)移方程為：k段允許決策集合為：設(shè)為第k年度的產(chǎn)量，那么故指標(biāo)函數(shù)為：令最優(yōu)值函數(shù)fk(sk)表示由資源量sk出發(fā)，從第k年開始到第5年結(jié)束時所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆推關(guān)系式：從第5年度開始，向前逆推計算。當(dāng)k=5時，有：因f5是u5的線性單調(diào)增函數(shù)，故得最大解u5*，相應(yīng)的有：當(dāng)k=4時，有：故得最大解，u4*=s4，相應(yīng)的有依此類推，可求得因s1=1000，故：計算結(jié)果說明：最優(yōu)策略為即前兩年應(yīng)把年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)器投入高負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺。在得到整個問題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即從始端向終端遞推計算出每年年初完好機(jī)器數(shù)。s1=1000臺，于是可得：8、有一輛最大貨運量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)單位價值如表4-20所示。應(yīng)如何裝載可使總價值最大？表4-SEQ表4-\*ARABIC20貨物編號i123單位重量〔t〕345單位價值ci456解：利用動態(tài)規(guī)劃的逆序解法求此問題。狀態(tài)轉(zhuǎn)移方程為：該題是三階段決策過程，故可假想存在第四個階段，而，于是動態(tài)規(guī)劃的根本方程為：計算最終結(jié)果為，最大價值為13。9、設(shè)有A，B，C三部機(jī)器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計結(jié)果說明，機(jī)器A，B，C產(chǎn)生次品的概率分別為pA=30%,PB=40%,PC=20%,而產(chǎn)品必須經(jīng)過三部機(jī)器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬元進(jìn)行技術(shù)改造，以便最大限度地提高產(chǎn)品的成品率指標(biāo)。現(xiàn)提出如下四種改良方案：方案1：不撥款，機(jī)器保持原狀；方案2：加裝監(jiān)視設(shè)備，每部機(jī)器需款1萬元；方案3：加裝設(shè)備，每部機(jī)器需款2萬元；方案4：同時加裝監(jiān)視及控制設(shè)備，每部機(jī)器需款3萬元；采用各方案后，各部機(jī)器的次品率如表4-21。表4-SEQ表4-\*ARABIC21ABC不撥款30%40%20%撥款1萬元20%30%10%撥款2萬元10%20%10%撥款3萬元5%10%6%問如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解：為三臺機(jī)器分配改造撥款，設(shè)撥款順序為A,B,C，階段序號反向編號為k，即第一階段計算給機(jī)器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)仍采用反向遞推第一階段：對機(jī)器C撥款的效果R1(s1,x1)=d1(s1,x1)R0(s0,x0)=d1(s1,x1)x1s10123x1*R1(s1,x1*)00.800.810.80.910.920.80.90.91,20.930.80.90.90.9430.9440.80.90.90.9430.9450.80.90.90.9430.94第二階段：對機(jī)器B,C撥款的效果由于機(jī)器A最多只需3萬元，故s22遞推公式：R2(s2,x2)=d2(s2,x2)R1(s1,x1*)例：R2(3,2)=d2(3,2)R1(1,1)=(1-0.2)0.9=0.72得第二階段最優(yōu)決策表x1s1x1*R1(s1,x1*)000.8110.921,20.9330.94430.94530.94x2s20123x2*R2(s2,x2*)20.540.630.6420.6430.5640.630.720.722,30.7240.5640.6580.720.8130.8150.5640.6580.7520.8130.81第三階段：對機(jī)器A,B,C撥款的效果邊界條件：s3=5遞推公式：R3(s3,x3)=d3(s3,x3)R2(s2,x2*)例：R3(5,3)=d3(5,3)R2(2,2)=(1-0.05)0.64=0.608得第三階段最優(yōu)決策表x2s2x2*R2(s2,x2*)220.6432,30.72430.81530.81s3x30123x3*R3(s3,x3*)50.5670.6480.6480.6081,20.648回溯：有多組最優(yōu)解。I：x3=1,x2=3,x1=1,R3=0.80.90.9=0.648II：x3=2,x2=2,x1=1,R3=0.90.80.9=0.648III：x3=2,x2=3,x1=0,R3=0.90.90.8=0.648練習(xí)題五1、考察多目標(biāo)規(guī)劃問題其中，試畫出個目標(biāo)函數(shù)的圖形，并求出，這里是的最優(yōu)解集。解：2、用線性加權(quán)法中的法求解下述多目標(biāo)規(guī)劃問題。解：最優(yōu)解為；最優(yōu)解為；利用法得線性方程組：解得唯一加權(quán)系數(shù)原多目標(biāo)規(guī)劃加權(quán)后解得加權(quán)后的最優(yōu)解為：，最優(yōu)值為-1.23123、用線性加權(quán)求和法求解下述多目標(biāo)規(guī)劃問題，取。解：將問題轉(zhuǎn)化為一個新的單目標(biāo)規(guī)劃問題。約束條件同上，該問題轉(zhuǎn)化為線性規(guī)劃問題，可用單純形法求解，也可用Matlab命令求解〔求解過程略〕。解得加權(quán)后的最優(yōu)解為：，最優(yōu)值為-1.4。4、用平方和加權(quán)法求解多目標(biāo)規(guī)劃問題：其中，，。解：不難看出兩個目標(biāo)函數(shù)下界均為0，得平方和加權(quán)法后的新目標(biāo)規(guī)劃問題：利用matlab程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件functionf=fun(x)f=1/3*x(1)^2+2/3*x(2)*x(2);[x,fval]=fmincon(‘f’,[00],[1-1;11],[4;8],[],[],[00])解得最優(yōu)解為：，最優(yōu)值為0。5、用極小極大法和Matlab軟件求解下述多目標(biāo)規(guī)劃問題。解：取評價函數(shù)為，再求Matlab軟件求解：編制M文件functionf=mnmax(x)f(1)=(x(1)-3)^2+x(2)^2;f(2)=x(1)^2+(x(2)-2)^2設(shè)初值x0=[0;0];調(diào)用函數(shù)[x,fval]=fminimax(@mnmax,x0,[11],[2])結(jié)果：x=1.30000.7000fval=3.38003.3800可得；對應(yīng)從而為原問題的解。附習(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:1〕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;ifmax(abs(x.*ID-round(x.*ID)))<0.00005ifupper-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)%功能:0.618法精確線搜索%輸入: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];3、grad.mfunction[x,val,k]=grad(fun,gfun,x0)%功能:用最速下降法求解無約束問題:minf(x)%輸入:x0是初始點,fun,gfun分別是目標(biāo)函數(shù)和梯度%輸出:x,val分別是近似最優(yōu)點和最優(yōu)值,k是迭代次數(shù).maxk=5000;%最大迭代次數(shù)rho=0.5;sigma=0.4;k=0;epsilon=1e-5;while(k<maxk)g=feval(gfun,x0);%計算梯度d=-g;%計算搜索方向if(norm(d)<epsilon),break;endm=0;mk=0;while(m<20)%Armijo搜索if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d)mk=m;break;endm=m+1;endx0=x0+rho^mk*d;k=k+1;endx=x0;val=feval(fun,x0);4、newton.mfunction[x,val,k]=newton(fun,gfun,Hess,x0)%功能:用尼牛頓法求解無約束問題:minf(x)%輸入:x0是初始點,fun,gfun,Hess分別是求%目標(biāo)函數(shù),梯度,Hesse陣的函數(shù)%輸出:x,val分別是近似最優(yōu)點和最優(yōu)值,k是迭代次數(shù).maxk=100;%給出最大迭代次數(shù)sigma=0.4;k=0;epsilon=1e-5;while(k<maxk)gk=feval(gfun,x0);%計算梯度Gk=feval(Hess,x0);%計算Hesse陣dk=-Gk\gk';%解方程組Gk*dk=-gk,計算搜索方向if(norm(gk)<epsilon),break;end%檢驗終止準(zhǔn)那么x0=x0+dk';k=k+1;endx=x0;val=feval(fun,x);5、frcg.mfunction[x,val,k]=frcg(fun,gfun,x0)%功能:用FR共軛梯度法求解無約束問題:minf(x)%輸入:x0是初始點,fun,gfun分別是目標(biāo)函數(shù)和梯度%輸出:x,val分別是近似最優(yōu)點和最優(yōu)值,k是迭代次數(shù).maxk=5000;%最大迭代次數(shù)rho=0.6;sigma=0.4;k=0;epsilon=1e-6;n=length(x0);while(k<maxk)g=feval(gfun,x0);%計算梯度itern=k-(n+1)*floor(k/(n+1));itern=itern+1;%計算搜索方向if(itern==1)d=-g;elsebeta=(g'*g)/(g0'*g0)