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

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

2、的目標(biāo)很清楚“收購價(jià)最小”。確定約束條件 資源的報(bào)價(jià)至少應(yīng)當(dāng)高于原生產(chǎn)產(chǎn)品的利潤(rùn)，這樣原廠家才可能賣。因此有如下線性規(guī)劃問題：*2、爭(zhēng)辯線性規(guī)劃的對(duì)偶理論和方法（包括對(duì)偶規(guī)劃模型形式、對(duì)偶理論和對(duì)偶單純形法）。答：略。3、用單純形法求解下列線性規(guī)劃問題： （1）； （2）解：（1）引入松弛變量x4，x5，x6cj1-11000CB基bx1x2x3x4x5x60x4211-21000x532110100x64-101001cj-zj1-11000因檢驗(yàn)數(shù)2<0，故確定x2為換入非基變量，以x2的系數(shù)列的正重量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量x4作為換出的基變量。cj1-11000

3、CB基bx1x4x3x4x5x6-1x2211-21000x51103-1100x64-101001cj-zj20-1100因檢驗(yàn)數(shù)3<0，故確定x3為換入非基變量，以x3的系數(shù)列的正重量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量x5作為換出的基變量。cj1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/31cj-zj7/3032/31/30因檢驗(yàn)數(shù)j>0，表明已求得最優(yōu)解：，去除添加的松弛變量，原問題的最優(yōu)解為：。（2）依據(jù)題意選取x1，x4，x5，為基變量：cj0-11

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

5、2/31x31001-1/31/3cj-zj0002/31/3因檢驗(yàn)數(shù)j>0，表明已求得最優(yōu)解：。4、分別用大法、兩階段法和Matlab軟件求解下列線性規(guī)劃問題：（1）； （2）解：（1）大M法依據(jù)題意約束條件1和2可以合并為1，引入松弛變量x3，x4，構(gòu)造新問題。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因檢驗(yàn)數(shù)j>0，表明已求得最優(yōu)解：。Matlab調(diào)用

6、代碼：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é)果：Optimization terminated.x = 0.6000 1.2000fval = 3.6000（2）大M法引入松弛變量x4，x5，x6，x7構(gòu)造新問題。單純形表計(jì)算略；當(dāng)全部非基變量為負(fù)數(shù)，人工變量=0.5，所以原問題無可行解。請(qǐng)同學(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

7、,A,b,lb)輸出結(jié)果：原題無可行解。5、用內(nèi)點(diǎn)法和Matlab軟件求解下列線性規(guī)劃問題： 解：用內(nèi)點(diǎn)法的過程自己書寫，參考答案：最優(yōu)解；最優(yōu)值5 Matlab調(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 = 1.3333 2.3333 0.0000fval = 5.00006、用分支定界法求解下列問題： （1） ； （2）解：（1）調(diào)用matlab編譯程序bbmethodf=-5; -8;G=1 1;5 9;h=6; 45x

8、,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編譯程序bbmethodf=-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），目標(biāo)函數(shù)最優(yōu)值2.（

9、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;% 價(jià)值向量fA=2,-5,3; -4,-1,-3;0,-1,-1;% 不等式約束系數(shù)矩陣A， 中的分號(hào)“；”% 為行分隔符b=4; -3;-1;% 不等式約束右端常數(shù)向量bx, fval=bintprog(f, A, b, , );%調(diào)用函數(shù)bintprog。留意兩個(gè)空數(shù)組的占位作用。輸出結(jié)果 x=001fval=2（2）調(diào)用代

10、碼：f=-3; -2;5;2;3;% 價(jià)值向量fA=1,1,1,2,1; 7,0,3,-4,3;-11, 6,0,-3, 3;% 不等式約束系數(shù)矩陣A， 中的分號(hào)“；”% 為行分隔符b=4; 8;-1;% 不等式約束右端常數(shù)向量bx, fval=bintprog(f, A, b, , );%調(diào)用函數(shù)bintprog。留意兩個(gè)空數(shù)組的占位作用。輸出結(jié)果 x=11000fval=-5最優(yōu)值5。8、某地區(qū)有A、B、C三個(gè)化肥廠，供應(yīng)本地甲、乙、丙、丁四個(gè)產(chǎn)糧區(qū)。已知各化肥廠可供應(yīng)化肥的數(shù)量和各產(chǎn)糧區(qū)對(duì)化肥的需要量，以及各廠到各區(qū)每噸化肥的運(yùn)價(jià)如表2-28所示。試制定一個(gè)使總運(yùn)費(fèi)最少的化肥調(diào)撥方案。表

11、2- 1運(yùn)價(jià)/ 產(chǎn)糧 (元/噸) 區(qū)化肥廠甲乙丙丁各廠供應(yīng)量/萬噸A158737A2491078A384293各區(qū)需要量/萬噸6633解：設(shè)A、B、C三個(gè)化肥廠為A1、A2、A3，甲、乙、丙、丁四個(gè)產(chǎn)糧區(qū)為B1、B2、B3、B4；cij為由Ai運(yùn)化肥至Bj的運(yùn)價(jià)，單位是元/噸；xij為由Ai運(yùn)往Bj的化肥數(shù)量（i=1,2,3;j=1,2,3,4）單位是噸；z表示總運(yùn)費(fèi)，單位為元，依題意問題的數(shù)學(xué)模型為：該題可以用單純形法或matlab自帶工具箱命令（linprog）求解。 *9、求解下列不平衡運(yùn)輸問題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價(jià)格，框外右側(cè)的一列數(shù)為各發(fā)點(diǎn)的供應(yīng)量，框底下一行數(shù)是各收點(diǎn)的

12、需求量）：（1） 5 1 7 10 要求收點(diǎn)3的需求必需正好滿足。 6 4 6 80 3 2 5 15 75 20 50（2） 5 1 0 20 要求收點(diǎn)1的需求必需由發(fā)點(diǎn)4供應(yīng)。 3 2 4 10 7 5 2 15 9 6 0 15 5 10 15解答略。10、一公司經(jīng)理要分派4位推銷員去4個(gè)地區(qū)推銷某種商品。推銷員各有不同的閱歷和力量，因而他們?cè)诓煌貐^(qū)能獲得的利潤(rùn)不同，其獲利估量值如表2-29所示。公司經(jīng)理應(yīng)怎樣分派才使總利潤(rùn)最大？表2- 2 地區(qū)推銷員1234135272837228342940335243233424322528解：用求極大值的“匈牙利法”求解。效率矩陣表示為：行約簡(jiǎn)

13、MCijM=40 標(biāo)號(hào)列約簡(jiǎn) 所畫（）0元素少于n（n4），未得到最優(yōu)解，需要連續(xù)變換矩陣（求能掩蓋全部0元素的最少數(shù)直線集合）：未被直線掩蓋的最小元素為cij=2，在未被直線掩蓋處減去2，在直線交叉處加上2。標(biāo)號(hào) 得最優(yōu)解：使總利潤(rùn)為最大的安排任務(wù)方案為：11，24，33，42此時(shí)總利潤(rùn)W=35+40+32+32=139練習(xí)題三1、用0.618法求解問題的近似最優(yōu)解，已知的單谷區(qū)間為，要求最終區(qū)間精度。答：t=0.8115；最小值-0.0886.（調(diào)用golds.m函數(shù)） 2、求無約束非線性規(guī)劃問題min =的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點(diǎn)：，則由得， 再用充分條件進(jìn)行檢驗(yàn)：，即

14、為正定矩陣得微小點(diǎn)為，最優(yōu)值為-1。解二：目標(biāo)函數(shù)改寫成 min =易知最優(yōu)解為（1,0,0），最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。其中，給定初始點(diǎn)。解一：目標(biāo)函數(shù)的梯度令搜尋方向再從動(dòng)身，沿方向作一維尋優(yōu)，令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為，則有故令可得 求出點(diǎn)之后，與上類似地，進(jìn)行其次次迭代： 令令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為，則有故令可得 此時(shí)所達(dá)到的精度本題最優(yōu)解，解二：利用matlab程序求解首先建立目標(biāo)函數(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=gfu

15、n(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.5000val= -1.2500k=33即迭代33次的到最優(yōu)解x= -1.0000 ,1.5000；最優(yōu)值val= -1.2500。4、試用Newton法求解第3題。解一：計(jì)算目標(biāo)函數(shù)的梯度和Hesse陣目標(biāo)函數(shù)的梯度，其逆矩陣為計(jì)算。本題最優(yōu)解，解二：除了第3題建立兩個(gè)M文件外，還需建立Hesse矩陣的M文件利用matlab程序求解首先建立目標(biāo)函數(shù)及其梯度

16、函數(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=hess(x)g=4 2;2 2 ;調(diào)用newton.m文件x0=0,0;x,val,k=newton('fun','gfun','hess',x0)結(jié)果x= -1.0000 ,1.5000val= -1.2500k=15、用FletcherReeves法求解問題其中，要求選取初

17、始點(diǎn)。解一： ，第一次迭代：令，即，其次次迭代：，第三次迭代：（建議同學(xué)們自己做下去，留意判別）解二：利用matlab程序求解首先建立目標(biāo)函數(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* 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.0088val =7.2182e-014k = 616、試用外

18、點(diǎn)法（二次罰函數(shù)方法）求解非線性規(guī)劃問題其中解：設(shè)計(jì)罰函數(shù) 接受Matlab編程計(jì)算，結(jié)果x=1 0；最優(yōu)結(jié)果為1。（調(diào)用waidianfa.m）7、用內(nèi)點(diǎn)法（內(nèi)點(diǎn)障礙罰函數(shù)法）求解非線性規(guī)劃問題：解：簡(jiǎn)潔看出此問題最優(yōu)解為x=1 0；最優(yōu)值為8.給出罰函數(shù)為 令；從而當(dāng)時(shí)，（建議同學(xué)自己編程序計(jì)算）8、用乘子法求解下列問題解：建立乘子法的增廣目標(biāo)函數(shù)：令：解上述關(guān)于x的二元一次方程組得到穩(wěn)定點(diǎn)當(dāng)乘子取2時(shí)，或發(fā)參數(shù)趨于無窮時(shí)，得到即最優(yōu)解。（建議同學(xué)自己編程序計(jì)算）練習(xí)題四1、石油輸送管道鋪設(shè)最優(yōu)方案的選擇問題：考察網(wǎng)絡(luò)圖4-6，設(shè)A為動(dòng)身地，F(xiàn)為目的地，B，C，D，E分別為四個(gè)必需建立油泵

19、加壓站的地區(qū)。圖中的線段表示管道可鋪設(shè)的位置，線段旁的數(shù)字表示鋪設(shè)這些管線所需的費(fèi)用。問如何鋪設(shè)管道才能使總費(fèi)用最??？圖4- 1解： 第五階段：E1F 4；E2F 3；第四階段：D1E1 F  7；D2E2F   5；D3E1F   5；第三階段：C1D1E1 F   12；C2D2E2F   10；C3D2E2F   8；C4D3E1F   9；其次階段：B1C2D2E2F    13； B2C3D2E2

20、F   15；  第一階段：AB1C2D2E2F   17；最優(yōu)解：AB1C2D2E2F    最優(yōu)值：172、 用動(dòng)態(tài)規(guī)劃方法求解非線性規(guī)劃解：，最優(yōu)值為9。3、用動(dòng)態(tài)規(guī)劃方法求解非線性規(guī)劃解：用挨次算法階段：分成兩個(gè)階段，且階段1 、2 分別對(duì)應(yīng)。決策變量：狀態(tài)變量：分別為第j 階段第一、其次約束條件可供安排的右段數(shù)值。 由于，可解的，最優(yōu)值為702.92。4、設(shè)四個(gè)城市之間的大路網(wǎng)如圖4-7。兩點(diǎn)連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應(yīng)的最短距離。圖4- 2

21、城市大路網(wǎng)解：城市1到城市4路線1-3-4 距離10；城市2到城市4路線2-4 距離8；城市3到城市4路線3-4 距離4。5、某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，依據(jù)市場(chǎng)部門估量，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤(rùn)如表4-19所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤(rùn)最大。 表4- 1解：將問題分為3個(gè)階段，k=1，2，3；決策變量xk表示安排給第k個(gè)地區(qū)的銷售點(diǎn)數(shù)；狀態(tài)變量為sk表示安排給第k個(gè)至第3個(gè)地區(qū)的銷售點(diǎn)總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中s1=4；允許決策集合：Dk（sk）=xk|0xksk階段指標(biāo)函數(shù)：gk（xk）表示xk個(gè)銷售點(diǎn)安排給第k個(gè)地區(qū)所

22、獲得的利潤(rùn)；最優(yōu)指標(biāo)函數(shù)fk（sk）表示將數(shù)量為sk的銷售點(diǎn)安排給第k個(gè)至第3個(gè)地區(qū)所得到的最大利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為：k=3時(shí)，k=2時(shí)，k=1時(shí)，最優(yōu)解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1個(gè)地區(qū)設(shè)置2個(gè)銷售點(diǎn)，第2個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，第3個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，每月可獲利潤(rùn)47。 6、設(shè)某廠方案全年生產(chǎn)某種產(chǎn)品A。其四個(gè)季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產(chǎn)產(chǎn)品A的生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0.005。廠內(nèi)有倉庫可存放產(chǎn)品，存儲(chǔ)費(fèi)為每公斤每季度1元。求最佳的生產(chǎn)支配使年總成本最小。解：四個(gè)季度為四個(gè)階段，接受階段

23、編號(hào)與季度挨次全都。 設(shè) sk 為第k季初的庫存量，則邊界條件為 s1=s5=0 設(shè) xk 為第k季的生產(chǎn)量，設(shè) yk 為第k季的訂貨量；sk ，xk ，yk 都取實(shí)數(shù)，狀態(tài)轉(zhuǎn)移方程為 sk+1=sk+xk - yk 仍接受反向遞推，但留意階段編號(hào)是正向的目標(biāo)函數(shù)為：第一步：(第四季度) 總效果 f4(s4,x4)=0.005 x42+s4 由邊界條件有： s5= s4 + x4 y4=0，解得：x4*=1200 s4 將x4*代入 f4(s4,x4)得： f4*(s4)=0.005(1200 s4)2+s4=7200 11 s4+0.005 s42其次步：(第三、四季度) 總效果 f3(s3

24、,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)生產(chǎn)庫存方案 x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300；

25、 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)時(shí)完好機(jī)器的數(shù)量s1=1000。試問每年如何支配機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：構(gòu)造這個(gè)問題的動(dòng)態(tài)規(guī)劃模型：設(shè)階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機(jī)器數(shù)量，同時(shí)也是第k1年度末時(shí)的完好機(jī)器數(shù)量。決策變量uk為第k年度中安排高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是skuk為該年度中安排在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量

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

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

28、的基本方程為：計(jì)算最終結(jié)果為，最大價(jià)值為13 。9、設(shè)有 A，B，C 三部機(jī)器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常消滅次品。統(tǒng)計(jì)結(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)提出如下四種改進(jìn)方案：方案1：不撥款，機(jī)器保持原狀；方案2：加裝監(jiān)視設(shè)備，每部機(jī)器需款 1 萬元；方案3：加裝設(shè)備，每部機(jī)器需款 2 萬元；方案4：同時(shí)加裝監(jiān)視及把握設(shè)備，每部機(jī)器需款 3 萬元；接受各方案后，各部機(jī)器的次品率如表4-21

29、。表4- 3ABC不撥款30%40%20%撥款 1 萬元20%30%10%撥款 2 萬元10%20%10%撥款 3 萬元5%10%6%問如何配置撥款才能使串聯(lián)系統(tǒng)的牢靠性最大？解：為三臺(tái)機(jī)器安排改造撥款，設(shè)撥款挨次為A, B, C，階段序號(hào)反向編號(hào)為 k，即第一階段計(jì)算給機(jī)器 C 撥款的效果。 設(shè) sk 為第 k 階段剩余款，則邊界條件為 s3=5； 設(shè) xk 為第 k 階段的撥款額； 狀態(tài)轉(zhuǎn)移方程為 sk-1=sk-xk； 目標(biāo)函數(shù)為 max R=(1-PA)(1-PB)(1-PC) 仍接受反向遞推第一階段 ：對(duì)機(jī)器 C 撥款的效果 R1(s1,x1)=d1(s1,x1)´ R0(

30、s0,x0)= d1(s1,x1)x1 s1 0123x1*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其次階段 ：對(duì)機(jī)器 B, C 撥款的效果 由于機(jī)器 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) ´0.9=0.72 得其次階段最優(yōu)決策表x1 s1

31、x1*R1(s1, x1*)000.8110.921, 20.9330.94430.94530.94x2 s2 0123x2*R2(s2, x2*)20.540.630.6420.6430.5640.630.720.722,30.7240.5640.6580.720.8130.8150.5640.6580.7520.8130.81第三階段 ：對(duì)機(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.6

32、08得第三階段最優(yōu)決策表x2 s2 x2*R2(s2, x2*)220.6432,30.72430.81530.81s3 x30123x3*R3(s3, x3*)50.5670.6480.6480.6081,20.648回溯 ：有多組最優(yōu)解。 I：x3=1, x2=3, x1=1, R3=0.8 ´0.9 ´0.9=0.648 II：x3=2, x2=2, x1=1, R3= 0.9´0.8´0.9=0.648III： x3=2, x2=3, x1=0, R3= 0.9´0.9´0.8=0.648練習(xí)題五1、考察多目標(biāo)規(guī)劃問題其中，試

33、畫出個(gè)目標(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)化為一個(gè)新的單目標(biāo)規(guī)劃問題。 約束條件同上，該問題轉(zhuǎn)化為線性規(guī)劃問題，可用單純形法求解，也可用Matlab命令求解（求解過程略）。解得加權(quán)后的最優(yōu)解為：，最優(yōu)值為-1.4。4、用平方和加權(quán)法求解多目標(biāo)規(guī)劃問題： 其中 ，。解：不難看出兩個(gè)目標(biāo)函數(shù)下界均為0，得平方和加權(quán)法后的新目標(biāo)規(guī)劃問題：利用matlab程序求解首

34、先建立目標(biāo)函數(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軟件求解下述多目標(biāo)規(guī)劃問題。解：取評(píng)價(jià)函數(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設(shè)初值x0=0;0;調(diào)用函數(shù)x,fval=fminimax(mnmax,x0,1 1,2)結(jié)果：x = 1.30000.7000fval =

35、3.3800 3.3800可得；對(duì)應(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*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:迭

36、代初值列向量 %id：整數(shù)變量指標(biāo)列向量，1-整數(shù)，0-實(shí)數(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

37、 nargin<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,

38、beq,vlb,vub,x0,options); if how <=0 return; end; if ftemp-upper>0.00005 %in order to avoid error return; end; if max(abs(x.*ID-round(x.*ID)<0.00005 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-roun

39、d(x)>=0.00005); %in order to avoid error intx=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)

40、,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ū)間的兩個(gè)端點(diǎn)% delta, epsilon分別是自變量和函數(shù)值的容許誤差%輸出: s, phis分別是近似微小點(diǎn)和微小值, 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=fev

41、al(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); else a=p; phia=phip; p=q; phip=phiq; h=b-a; q=a+t*h; p

42、hiq=feval(phi,q); end k=k+1; G(k,:)=a, p, q, b; endds=abs(b-a); dphi=abs(phib-phia);if(phip<=phiq) s=p; phis=phip;else s=q; phis=phiq;endE=ds,dphi;3、grad.mfunction x,val,k=grad(fun,gfun,x0)% 功能: 用最速下降法求解無約束問題: min f(x)%輸入: x0是初始點(diǎn), fun, gfun分別是目標(biāo)函數(shù)和梯度%輸出: x, val分別是近似最優(yōu)點(diǎn)和最優(yōu)值, k是迭代次數(shù).maxk=5000; %最大迭

43、代次數(shù)rho=0.5;sigma=0.4;k=0; epsilon=1e-5;while(k<maxk) g=feval(gfun,x0); %計(jì)算梯度 d=-g; %計(jì)算搜尋方向 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

44、);4、newton.mfunction x,val,k=newton(fun,gfun,Hess,x0)%功能: 用尼牛頓法求解無約束問題: min f(x)%輸入: x0是初始點(diǎn), fun, gfun, Hess 分別是求% 目標(biāo)函數(shù),梯度,Hesse 陣的函數(shù)%輸出: x, val分別是近似最優(yōu)點(diǎn)和最優(yōu)值, k是迭代次數(shù).maxk=100; %給出最大迭代次數(shù)sigma=0.4;k=0; epsilon=1e-5;while(k<maxk) gk=feval(gfun,x0); %計(jì)算梯度 Gk=feval(Hess,x0); %計(jì)算Hesse陣 dk=-Gkgk' %解方程組Gk*dk=-gk, 計(jì)算搜尋方向 if(norm(gk)<epsilon), break; end %檢驗(yàn)終止準(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共軛梯度法求解無約束問題: min f