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

1、1、建立優(yōu)化模型應考慮哪些要素?答：決策變量、目標函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準則。答：針對一般優(yōu)化模型，討論解的可行域，若存在一點，對于均有則稱為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭代所得到的序列，滿足，則迭代法收斂；收斂的停止準則有，等等。練習題二1、某公司看中了例中廠家所擁有的3種資源R1、R2、和R3，欲出價收購（可能用于生產(chǎn)附加值更高的產(chǎn)品）。如果你是該公司的決策者，對這3種資源的收購報價是多少？（該問題稱為例的對偶問題）。解：確定決策變量對3種資源報價作為本問題的決策變量。確定目標函數(shù)問題的目標很清楚“收購價最小”。確定約束條

2、件資源的報價至少應該高于原生產(chǎn)產(chǎn)品的利潤，這樣原廠家才可能賣。因此有如下線性規(guī)劃問題：*2、研究線性規(guī)劃的對偶理論和方法（包括對偶規(guī)劃模型形式、對偶理論和對偶單純形法）。答：略。3、用單純形法求解下列線性規(guī)劃問題：（1）；（2）解：（1）引入松弛變量x4，x5，x6cj1-11000CB基bx1x2x3x4x5x60x4211-21000x532110100x64-101001cj-zj1-11000因檢驗數(shù)2<0，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x4作為換出的基變量。cj1-11000CB基bx1x4x3x4x5x6-1x221

3、1-21000x51103-1100x64-101001cj-zj20-1100因檢驗數(shù)3<0，故確定x3為換入非基變量，以x3的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x5作為換出的基變量。cj1-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)解為：。（2）根據(jù)題意選取x1，x4，x5，為基變量：cj0-1100CB基bx1x2x3x4x50x121-

4、21000x4201-2100x5501101cj-zj0-1100因檢驗數(shù)2<0最小，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x4作為換出的基變量。cj0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x53003-11cj-zj00-110因檢驗數(shù)3<0最小，故確定x3為換入非基變量，以x1的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x5作為換出的基變量。cj0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31x31001-1/31/3cj-zj

5、0002/31/3因檢驗數(shù)j>0，表明已求得最優(yōu)解：。4、分別用大法、兩階段法和Matlab軟件求解下列線性規(guī)劃問題：（1）；（2）解：（1）大M法根據(jù)題意約束條件1和2可以合并為1，引入松弛變量x3，x4，構造新問題。cj41M0CB基bx1x2x3x4Mx3331100x431201cj-zj4-3M1-M004x1111/31/300x4205/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、-6;3;Aeq=3,1;beq=3;lb=0;0;x,fval = linprog(f,A,b,Aeq,beq,lb)輸出結(jié)果：Optimization terminated.x =fval =（2）大M法引入松弛變量x4，x5，x6，x7構造新問題。單純形表計算略；當所有非基變量為負數(shù)，人工變量=0.5，所以原問題無可行解。請同學們自己求解。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ī)劃問

7、題：解：用內(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é)果：Optimization terminated.x =fval =6、用分支定界法求解下列問題：（1）；（2）解：（1）調(diào)用matlab編譯程序bbmethodf=-5; -8;G=1 1;5 9;h=6; 45x,y=bbmethod(f,G,h,0;0,1;1,1)x = 3 3y = -39最優(yōu)解3 3；最優(yōu)值39（2）調(diào)用matlab編譯程序bbmethod

8、f=-7; -9;G=-1 3; 7 1;h=6; 35x,y=bbmethod(f,G,h,0;0,1;0,1)x = 5 0y = -35最優(yōu)解5 0；最優(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），目標函數(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）分別帶入到約束條件中，可以得到：原問題

9、的最優(yōu)解是（1，1，0，0，0），目標函數(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ù)向量bx, 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， 中的分

10、號“；”% 為行分隔符b=4; 8;-1;% 不等式約束右端常數(shù)向量bx, 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- 1運價/ 產(chǎn)糧 (元/噸) 區(qū)化肥廠甲乙丙丁各廠供應量/萬噸A158737A2491078A384293各區(qū)需要量/萬噸6633解：設A、B、C三個化肥廠為

11、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ù)學模型為：該題可以用單純形法或matlab自帶工具箱命令（linprog）求解。 *9、求解下列不平衡運輸問題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價格，框外右側(cè)的一列數(shù)為各發(fā)點的供應量，框底下一行數(shù)是各收點的需求量）：（1） 5 1 7 10 要求收點3的需求必須正好滿足。 6 4 6 80 3 2 5 15 75 20 50（2） 5 1 0 20 要求收點1的需求

12、必須由發(fā)點4供應。 3 2 4 10 7 5 2 15 9 6 0 15 5 10 15解答略。10、一公司經(jīng)理要分派4位推銷員去4個地區(qū)推銷某種商品。推銷員各有不同的經(jīng)驗和能力，因而他們在不同地區(qū)能獲得的利潤不同，其獲利估計值如表2-29所示。公司經(jīng)理應怎樣分派才使總利潤最大？表2- 2地區(qū)推銷員1234135272837228342940335243233424322528解：用求極大值的“匈牙利法”求解。效率矩陣表示為：行約簡MCijM=40標號列約簡所畫（）0元素少于n（n4），未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）：未被直線覆蓋的最小元素為cij=2，在

13、未被直線覆蓋處減去2，在直線交叉處加上2。標號得最優(yōu)解：使總利潤為最大的分配任務方案為：11，24，33，42此時總利潤W=35+40+32+32=139練習題三1的近似最優(yōu)解，已知的單谷區(qū)間為，要求最后區(qū)間精度。答：t=0.8115；最小值-0.0886.（調(diào)用golds.m函數(shù)） 2、求無約束非線性規(guī)劃問題min =的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點：，則由得，再用充分條件進行檢驗：，即為正定矩陣得極小點為，最優(yōu)值為-1。解二：目標函數(shù)改寫成 min =易知最優(yōu)解為（1,0,0），最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。其中，給定初始點。解一：目標函數(shù)的梯度令搜索

14、方向再從出發(fā)，沿方向作一維尋優(yōu)，令步長變量為，最優(yōu)步長為，則有故令可得 求出點之后，與上類似地，進行第二次迭代： 令令步長變量為，最優(yōu)步長為，則有故令可得 此時所達到的精度本題最優(yōu)解，解二：利用matlab程序求解首先建立目標函數(shù)及其梯度函數(shù)的M文件function f=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é)果

15、x= -1.0000 ,val=k=33即迭代33次的到最優(yōu)解x= -1.0000 ,；最優(yōu)值val=。4、試用Newton法求解第3題。解一：計算目標函數(shù)的梯度和Hesse陣目標函數(shù)的梯度，其逆矩陣為計算。本題最優(yōu)解，解二：除了第3題建立兩個M文件外，還需建立Hesse矩陣的M文件利用matlab程序求解首先建立目標函數(shù)及其梯度函數(shù)的M文件function f=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);function g=gfun(x)g=1+4*x(1)+2*x(2),-1+2*x(1) +2* x(2);function h

16、=hess(x)g=4 2;22;調(diào)用newton.m文件x0=0,0;x,val,k=newton('fun','gfun','hess',x0)結(jié)果x= -1.0000 ,val=k=15、用FletcherReeves法求解問題其中，要求選取初始點。解一：，第一次迭代：令，即，第二次迭代：，第三次迭代：（建議同學們自己做下去，注意判別）解二：利用matlab程序求解首先建立目標函數(shù)及其梯度函數(shù)的M文件function f=fun(x)f=x(1)2+25* x(2)*x(2);function g=gfun(x)g=2*x(1), 50*

17、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ī)劃問題其中解：設計罰函數(shù) 采用Matlab編程計算，結(jié)果x=1 0；最優(yōu)結(jié)果為1。（調(diào)用）7、用內(nèi)點法（內(nèi)點障礙罰函數(shù)法）求解非線性規(guī)劃問題：解：容易看出此問題最優(yōu)解為x=1 0；最優(yōu)值為8.給出罰函數(shù)為 令；從而當時，（建議同學自己編程序計算）8、用乘子法求解下列問題解：建立乘子法的增廣目標函數(shù)：令：解上述關于x的二元一次方程組得

18、到穩(wěn)定點當乘子取2時，或發(fā)參數(shù)趨于無窮時，得到即最優(yōu)解。（建議同學自己編程序計算）練習題四1、石油輸送管道鋪設最優(yōu)方案的選擇問題：考察網(wǎng)絡圖4-6，設A為出發(fā)地，F(xiàn)為目的地，B，C，D，E分別為四個必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設的位置，線段旁的數(shù)字表示鋪設這些管線所需的費用。問如何鋪設管道才能使總費用最?。繄D4- 1解： 第五階段：E1F4；E2F 3；第四階段：D1E1 F 7；D2E2F  5；D3E1F  5；第三階段：C1D1E1 F  12；C2D2E2F 

19、; 10；C3D2E2F  8；C4D3E1F  9；第二階段：B1C2D2E2F   13；B2C3D2E2F  15；  第一階段：AB1C2D2E2F  17；最優(yōu)解：AB1C2D2E2F    最優(yōu)值：172、用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：，最優(yōu)值為9。3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：用順序算法階段：分成兩個階段，且階段1 、2 分別對應。決策變量：狀態(tài)變量：分別為第j階段第一、第二約束條件可供分配的右

20、段數(shù)值。由于，可解的，最優(yōu)值為702.92。4、設四個城市之間的公路網(wǎng)如圖4-7。兩點連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應的最短距離。圖4- 2城市公路網(wǎng)解：城市1到城市4路線1-3-4 距離10；城市2到城市4路線2-4 距離8；城市3到城市4路線3-4 距離4。5、某公司打算在3個不同的地區(qū)設置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表4-19所示。試問在各地區(qū)如何設置銷售點可使每月總利潤最大。表4- 1解：將問題分為3個階段，k=1，2，3；決策變量xk表示分配給第k個地區(qū)的銷售點數(shù)；狀態(tài)變量為sk表示分配給第k個至

21、第3個地區(qū)的銷售點總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中s1=4；允許決策集合：Dk（sk）=xk|0xksk階段指標函數(shù)：gk（xk）表示xk個銷售點分配給第k個地區(qū)所獲得的利潤；最優(yōu)指標函數(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ū)設置2個銷售點，第2個地區(qū)設置1個銷售點，第3個地區(qū)設置1個銷售點，每月可獲利潤47。6、設某廠計劃全年生產(chǎn)某種產(chǎn)品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。

22、已知生產(chǎn)產(chǎn)品A的生產(chǎn)費用與產(chǎn)品的平方成正比，系數(shù)為。廠內(nèi)有倉庫可存放產(chǎn)品，存儲費為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。解：四個季度為四個階段，采用階段編號與季度順序一致。設sk為第k季初的庫存量，則邊界條件為s1=s5=0設xk為第k季的生產(chǎn)量，設yk為第k季的訂貨量；sk ，xk ，yk都取實數(shù)，狀態(tài)轉(zhuǎn)移方程為sk+1=sk+xk - yk仍采用反向遞推，但注意階段編號是正向的目標函數(shù)為：第一步：(第四季度) 總效果f4(s4,x4)=0.005 x42+s4由邊界條件有：s5= s4 + x4 y4=0，解得：x4*=1200 s4將x4*代入f4(s4,x4)得：f4*(s

23、4)=0.005(1200 s4)2+s4=7200 11 s4+0.005 s42第二步：(第三、四季度) 總效果f3(s3,x3)=0.005 x32+s3+ f4*(s4)將s4= s3 + x3 500 代入f3(s3,x3) 得：第三步：(第二、三、四季度) 總效果f2(s2,x2)=0.005 x22+s2+ f3*(s3)將s3= s2 + x2 -700 代入f2(s2,x2) 得：第四步：(第一、二、三、四季度) 總效果f1(s1,x1)=0.005 x12+s1+ f2*(s2)將s2= s1 + x1 600= x1 600 代入f1(s1,x1) 得：由此回溯：得最優(yōu)生

24、產(chǎn)庫存方案x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300； x4*=900。7、某種機器可在高低兩種不同的負荷下進行生產(chǎn)。設機器在高負荷下生產(chǎn)的產(chǎn)量函數(shù)為g=8u1，其中u1為投入生產(chǎn)的機器數(shù)量，年完好率a；在低負荷下生產(chǎn)的產(chǎn)量函數(shù)為h=5y，其中y為投入生產(chǎn)的機器數(shù)量，年完好率為b。假定開始生產(chǎn)時完好機器的數(shù)量s1=1000。試問每年如何安排機器在高、低負荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：構造這個問題的動態(tài)規(guī)劃模型：設階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機器數(shù)量，同時也是第k1年度末時的完好機器數(shù)量。決策變量uk為第k年

25、度中分配高負荷下生產(chǎn)的機器數(shù)量，于是skuk為該年度中分配在低負荷下生產(chǎn)的機器數(shù)量。這里sk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如sk，就表示一臺機器在k年度中正常工作時間只占6/10；uk，就表示一臺機器在該年度只有3/10的時間能在高負荷下工作。狀態(tài)轉(zhuǎn)移方程為：k段允許決策集合為：設為第k年度的產(chǎn)量，則故指標函數(shù)為：令最優(yōu)值函數(shù)fk(sk)表示由資源量sk出發(fā)，從第k年開始到第5年結(jié)束時所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆推關系式：從第5年度開始，向前逆推計算。當k=5時，有：因f5是u5的線性單調(diào)增函數(shù)，故得最大解u5*，相應的有：當k=4時，有：故得最大解，u4*=s4，相

26、應的有依此類推，可求得因s1=1000，故：計算結(jié)果表明：最優(yōu)策略為即前兩年應把年初全部完好機器投入低負荷生產(chǎn)，后三年應把年初全部完好機器投入高負荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺。在得到整個問題的最優(yōu)指標函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即從始端向終端遞推計算出每年年初完好機器數(shù)。已知s1=1000臺，于是可得：8、有一輛最大貨運量為10t 的卡車，用以裝載3種貨物，每種貨物的單位重量及相應單位價值如表4-20所示。應如何裝載可使總價值最大？表4- 2貨物編號i123單位重量（t）345單位價值 ci456解：利用動態(tài)規(guī)劃的逆序解法求此問題。狀態(tài)轉(zhuǎn)移方程為：

27、 該題是三階段決策過程，故可假想存在第四個階段，而，于是動態(tài)規(guī)劃的基本方程為：計算最終結(jié)果為，最大價值為13 。9、設有 A，B，C 三部機器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術問題，產(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 萬元進行技術改造，以便最大限度地提高產(chǎn)品的成品率指標。現(xiàn)提出如下四種改進方案：方案1：不撥款，機器保持原狀；方案2：加裝監(jiān)視設備，每部機器需款 1 萬元；方案3：加裝設備，每部機器需款 2 萬元；方案4：同時加裝監(jiān)視及控制設備，每部

28、機器需款 3 萬元；采用各方案后，各部機器的次品率如表4-21。表4- 3ABC不撥款30%40%20%撥款 1 萬元20%30%10%撥款 2 萬元10%20%10%撥款 3 萬元5%10%6%問如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解：為三臺機器分配改造撥款，設撥款順序為A, B, C，階段序號反向編號為 k，即第一階段計算給機器 C 撥款的效果。 設 sk 為第 k 階段剩余款，則邊界條件為 s3=5； 設 xk 為第 k 階段的撥款額； 狀態(tài)轉(zhuǎn)移方程為 sk-1=sk-xk； 目標函數(shù)為 max R=(1-PA)(1-PB)(1-PC) 仍采用反向遞推第一階段 ：對機器 C 撥款的效

29、果R1(s1,x1)=d1(s1,x1)´R0(s0,x0)= d1(s1,x1)x1 s10123x1*R1(s1, x1*)001121, 2334353第二階段 ：對機器 B, C 撥款的效果 由于機器 A 最多只需 3 萬元，故 s2³ 2 遞推公式： R2(s2,x2)=d2(s2,x2)´R1(s1,x1*) 例：R2(3,2)=d2(3,2)´R1(1,1)=(1-0.2) ´ 得第二階段最優(yōu)決策表x1 s1x1*R1(s1, x1*)001121, 2334353x2 s20123x2*R2(s2, x2*)2232,34353

30、第三階段 ：對機器 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) ´得第三階段最優(yōu)決策表x2 s2x2*R2(s2, x2*)2232,34353s3 x30123x3*R3(s3, x3*)51,2回溯 ：有多組最優(yōu)解。 I：x3=1, x2=3, x1=1, R3=0.8 ´0.9 ´ II：x3=2, x2=2, x1=1, R3´´III：x3=2, x2=3, x1=0

31、, R3´´練習題五1、考察多目標規(guī)劃問題其中，試畫出個目標函數(shù)的圖形，并求出，這里是的最優(yōu)解集。解：2、用線性加權法中的法求解下述多目標規(guī)劃問題。解：最優(yōu)解為；最優(yōu)解為；利用法得線性方程組：解得唯一加權系數(shù)原多目標規(guī)劃加權后解得加權后的最優(yōu)解為：3、用線性加權求和法求解下述多目標規(guī)劃問題，取。解：將問題轉(zhuǎn)化為一個新的單目標規(guī)劃問題。約束條件同上，該問題轉(zhuǎn)化為線性規(guī)劃問題，可用單純形法求解，也可用Matlab命令求解（求解過程略）。解得加權后的最優(yōu)解為：，最優(yōu)值為-1.4。4、用平方和加權法求解多目標規(guī)劃問題：其中，。解：不難看出兩個目標函數(shù)下界均為0，得平方和加權法后的新

32、目標規(guī)劃問題：利用matlab程序求解首先建立目標函數(shù)及其梯度函數(shù)的M文件function f=fun(x)f=1/3*x(1)2+2/3* x(2)*x(2);x,fval=fmincon(f,0 0,1 -1;1 1,4;8,0 0)解得最優(yōu)解為：，最優(yōu)值為0。5、用極小極大法和Matlab軟件求解下述多目標規(guī)劃問題。解：取評價函數(shù)為，再求Matlab軟件求解：編制M文件function f=mnmax(x)f(1)=(x(1)-3)2+x(2)2;f(2)=x(1)2+(x(2)-2)2設初值x0=0;0;調(diào)用函數(shù)x,fval=fminimax(mnmax,x0,1 1,2)結(jié)果：x =

33、fval =可得；對應從而為原問題的解。附習題中用過的Matlab程序1、bbmethodfunction x,y=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options) %整數(shù)線性規(guī)劃分支定界法，可求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃。 %y=minf*x s.t. G*x<=h Geq*x=heq x為全整數(shù)或混合整數(shù)列向量 %用法 %x,y=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options) %參數(shù)說明 %lb:解的下界列向量（Default:-int） %ub:解的上界列向量（Default:int） %x:迭代初值列向量

34、%id：整數(shù)變量指標列向量，1-整數(shù)，0-實數(shù)（Default:1） global upper opt c x0 A b Aeq beq ID options; if nargin<10,options=optimset();options.Display='off' options.LargeScale='off'end if nargin<9,id=ones(size(f);end if nargin<8,x=;end if nargin<7 |isempty(ub),ub=inf*ones(size(f);end if nargin

35、<6 |isempty(lb),lb=zeros(size(f);end if nargin<5,heq=;end if nargin<4,Geq=;end upper=inf;c=f;A=G; b=h;Aeq=Geq;beq=heq;x0=x;ID=id; ftemp=IntLP(lb(:),ub(:); x=opt;y=upper; %下面是子函數(shù) function ftemp=IntLP(vlb,vub) global upper opt c x0 A b Aeq beq ID options; x,ftemp,how=linprog(c,A,b,Aeq,beq,vlb

36、,vub,x0,options); if how <=0 return; end; if ftemp-upper>0.00005 %in order to avoid error return; end; if upper-ftemp>0.00005 %in order to avoid error opt=x'upper=ftemp; return; else opt=opt;x' return; end; end; notintx=find(abs(x-round(x)>=0.00005); %in order to avoid error intx

37、=fix(x);tempvlb=vlb;tempvub=vub; if vub(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; if vlb(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.mfunc

38、tion s,phis,k,G,E=golds(phi,a,b,delta,epsilon)%輸入: phi是目標函數(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(ph

39、i,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); else a=p; phia=phip; p=q; phip=phiq; h=b-a; q=a+t*h; phiq=feval(phi,q); end k=k+1; G(k,:)=a, p, q, b; endds=abs(b-a);

40、dphi=abs(phib-phia);if(phip<=phiq) s=p; phis=phip;else s=q; phis=phiq;endE=ds,dphi;function x,val,k=grad(fun,gfun,x0)% 功能: 用最速下降法求解無約束問題: min f(x)%輸入: x0是初始點, fun, gfun分別是目標函數(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)

41、; %計算梯度 d=-g; %計算搜索方向 if(norm(d)<epsilon), break; end m=0; mk=0; while(m<20) %Armijo搜索 if(feval(fun,x0+rhom*d)<feval(fun,x0)+sigma*rhom*g'*d) mk=m; break; end m=m+1; end x0=x0+rhomk*d; k=k+1;endx=x0;val=feval(fun,x0);4、newton.mfunction x,val,k=newton(fun,gfun,Hess,x0)%功能: 用尼牛頓法求解無約束問題:

42、min f(x)%輸入: x0是初始點, fun, gfun, Hess 分別是求% 目標函數(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=-Gkgk' %解方程組Gk*dk=-gk, 計算搜索方向 if(norm(gk)<epsilon), break; end %檢驗終止準則 x0=x0+dk' k=k+1;endx=x0;val=feval(fun,x);5、function x,val,k=frcg(fun,gfun,x0)% 功能: 用FR共軛梯度法求解無約束問題: min f(x)%輸入: x0是初始點, fun, gfun分別是目標函數(shù)和梯度%輸出: x, val分別是近似最優(yōu)點和最