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

1、練習(xí)題一1建立優(yōu)化模型應(yīng)考慮哪些要素答：決策變量、目標(biāo)函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準(zhǔn)則min f(x)答：針對一般優(yōu)化模型s.tgix0, i1,2,L m，討論解的可行域D，若存在一點hjx0, j1,L , pX* D，對于 X D均有f (X*) f (X)則稱X*為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭代所得到的序列 X,X，L ,X(K)L ，滿足f(X(K1) f(X(K)，則迭代法收斂；收斂的停止準(zhǔn)則有x(k1) x(k)(k 1)x(k)f x(k 1 fx(k) |f x(k)x(k1)x(k)等等練習(xí)題二1、某公司看中了

2、例中廠家所擁有的 3種資源R、R、和R3，欲出價收購(可能用于 生產(chǎn)附加值更高的產(chǎn)品)。如果你是該公司的決策者，對這 3種資源的收購報價是多少 (該問題稱為例的對偶問題)。解：確定決策變量對3種資源報價,作為本問題的決策變量。確定目標(biāo)函數(shù)問題的目標(biāo)很清楚一一“收購價最小”。確定約束條件資源的報價至少應(yīng)該咼于原生產(chǎn)產(chǎn)品的利潤，這樣原廠家才可能因此有如下線性規(guī)劃問題： min w 170 y1 100y2 150y35y1 2y2 y310s.t 2y1 3y2 5y3 18y1, y2, y30*2、研究線性規(guī)劃的對偶理論和方法(包括對偶規(guī)劃模型形式、對偶理論和對偶單純形法）答：略。3、用單純形

3、法求解下列線性規(guī)劃問題:minzx1x2x3minz 4 x2X3x1x22X32X1 2x2 X32（1）s.t.2x1 x2x33 ；（2）s.t.x2 2x3X42X1x34x2 x3x55X1,X2,X30Xi 0 （i1,2,5）解：（1）引入松弛變量X4, X5, X6minzX1X2X30* x40* X50* X6X1X22x3X4=2st2NX2X3x5=3x1x3x6=4x1,x2,x3,x4,x5,x6 0Cj 1-11000CB基bX1X2X3X4X5X60X4211-21000X532110100X64-101001Cj-乙1-11000因檢驗數(shù)（7 20,故確定X2

4、為換入非基變量，以X2的系數(shù)列的正分量對應(yīng)去除常數(shù) 列，最小比值所在行對應(yīng)的基變量 X4作為換出的基變量。Cj 1-11000CB基bX1X4X3X4X5X6-1X2211-21000X51103-1100X64-101001Cj-Zj20-1100因檢驗數(shù)7 30,表明已求得最優(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，為基變量：min z 4 x2x3X 2x2 x32x22x3s.t.23x42x2x3x55Xi 0 (i1,2,5)C 0 -1100CB基bX1X2X3X4X

5、50X121 -21000X420 1-2100X550 1101Cj- Zj0 -1100因檢驗數(shù)(7 20最小，故確定X2為換入非基變量，以X2的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量 X4作為換出的基變量c 0-1100G基bX1X2X3X4X50X1610-320-1X2201-2100X53003-11Cj-Zj00-110因檢驗數(shù)（7 30,表明已求得最優(yōu)解：X*(9,4,1,0,0)。4、分別用大M法、兩階段法和Matlab軟件求解下列線性規(guī)劃問題：min z4x1X2maxZ10x115x212x33x1x235x13x2X3 9(1)s.t. 9X13x26

6、 ；（2）st5x16x215x315X12x232x1 X2 X35X1, X20X1, X2 , X30解：（1）大M法根據(jù)題意約束條件1和2可以合并為1,引入松弛變量X3,X4,構(gòu)造新冋題。min z=4x 1 +x 2 +Mx 3 +0*x 4X33x433x-| x2 st x1 2x2xX4Cj T41M0C基bX1X2X3X4MX3331100X431201Cj-乙4-3M1-M004X1111/31/300X4205/3-1/31Cj- Zj0-1/3M -4/304X13/5102/5-1/51X26/501-1/53/5Cj-乙00M-7/51/5因檢驗數(shù) e0,表明已求得

7、最優(yōu)解：X* (3/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 = lin prog(f,A,b,Aeq,beq,lb)輸出結(jié)果：Optimization terminated.x =fval =（2）大M法引入松弛變量X4，X5，X6，X7構(gòu)造新問題max z 10X! 15x212x3 0x4 0x5 0x6 Mx7s.t5x1 6x2 15x3x5152x1x2x3x6 x7 5x1,L ,x7 0單純形表計算略；當(dāng)所有非基變量為負(fù)數(shù)，人工變量 x7 =，所以原問題無可行解 請同學(xué)們自己求解。

8、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ī)劃問題： min z 2x1 x2 x3 x1 2x2 2x3 6 s.t. 2x1 x25x1,x2,x3 0解：用內(nèi)點法的過程自己書寫，參考答案：最優(yōu)解 X 4/3 7/3 0 ；最優(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,

9、beq,lb)輸出結(jié)果：Optimization terminated.fval =6、用分支定界法求解下列問題：max z 5x1 8x2max z 7x1 9x2x1x26x13x26（ 1）s.t. 5x19x245； （2） s.t.7x1x235x1,x2 0且均為整數(shù)XX2 0且為整數(shù)解：（1）調(diào)用 matlab 編譯程序 bbmethod f=-5; -8;G=1 1;5 9;h=6; 45 X,y=bbmethod（f,G,h,0;0,1;1,1） X =3 3y =-39最優(yōu)解 3 3 ；最優(yōu)值 392）調(diào)用 matlab 編譯程序 bbmethodf=-7; -9;G=-1

10、 3; 7 1;h=6; 35 x,y=bbmethod（f,G,h,0;0,1;0,1） x =5 0-35最優(yōu)解 5 0 ；最優(yōu)值 357、用隱枚舉法和 Matlab 軟件求解下列問題：minz4x13x22x3max z3x1 2x2 5x3 2x4 3x52x15x23X34x1x2x32x4x54(1)s.t.4x1x23X33 ； (2)7x1s.t.3x34x43x58x2x3111x16x23x43x51Xj0 或 1(j1,2,3)xj0 或 1 (j1,2,5)解：隱枚舉法：(1) 將(0, 0, 0) (0, 0, 1) (0, 1, 0) (1, 0, 0) (0, 1

11、, 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;%不等式約束系數(shù)矩陣 A,中的分號“；” %為行分隔符,-1,-3;0,-1,-1;b=4;

12、 -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,%不等式約束系數(shù)矩陣A，中的分號“；” %為行分隔6,0,-3, 3;符b=4; 8;-1;%不等式約束右端常數(shù)向量 bx, fval=bintprog(f. A, b,%調(diào)用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。);輸出結(jié)果x=11000fval=-5最優(yōu)值58某地區(qū)有A、B C三個化肥廠，

13、供應(yīng)本地甲、乙、丙、丁四個產(chǎn)糧區(qū)。已知各 化肥廠可供應(yīng)化肥的數(shù)量和各產(chǎn)糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運價如表2-28所示。試制定一個使總運費最少的化肥調(diào)撥方案?；蕪SA158737A2491078A84293各區(qū)需要量/萬噸6633解：設(shè)A、B、C三個化肥廠為A、A、A,甲、乙、丙、丁四個產(chǎn)糧區(qū)為B、B、R、B4； Cj為由A運化肥至Bj的運價，單位是元/噸；Xj為由A運往B的化肥數(shù)量（i=1,2,3;j=1,2,3,4）單位是噸；z表示總運費，單位為元，依題意問題的數(shù)學(xué)模型為：34min zCij Xji 1 j 1X11X21X316X12X22X326X13X23X333s

14、.tx14X24X343X11X12X13X147X21X22X23X248X31X32X33X347該題可以用單純形法或 matlab自帶工具箱命令（linprog ）求解。*9、求解下列不平衡運輸問題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價格q，框外右ai，框底下一行數(shù)是各收點的需求量bj）:要求收點3的需求必須正好滿足側(cè)的一列數(shù)為各發(fā)點的供應(yīng)量（1）6375 20 50要求收點1的需求必須由發(fā)點4供應(yīng)7 5 2 159 6 0 155 10 15解答略。10、一公司經(jīng)理要分派4位推銷員去4個地區(qū)推銷某種商品。推銷員各有不同的經(jīng)驗和能力，因而他們在不同地區(qū)能獲得的利潤不同，其獲利估計值如表2-2

15、9所示。公司經(jīng)理應(yīng)怎樣分派才使總利潤最大表2- 2地區(qū)推銷員1234135272837228342940335243233424322528解：用求極大值的“匈牙利法”求解。效率矩陣表示為：3527283752834294012352432335M=402432252816221090126110列約簡12(0)011328074標(biāo)號8131236110行約簡168781512106(0)68*011*02所畫（）0兀素少于n(0)44（n=4）,未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）：VV未被直線覆蓋的最小兀素為Cjj =2,在未被直線覆蓋處減去2,10460

16、11004(0)100844611(0)(0)4在直線交叉處加上2*0(0)4610 0 0二得最優(yōu)解:-使總利潤為最大的分配任務(wù)方案為:1宀 1, 4, 3宀3, 4宀2此時總利潤 W=35+40+32+32=139練習(xí)題三1、用法求解問題0.5呷t3 2t 1的近似最優(yōu)解，已知 的單谷區(qū)間為0,3，要求最后區(qū)間精度 答：t=;最小值.(調(diào)用函數(shù))2 、求無約束非線性規(guī)劃問題min f (x1, x2,x3) = x1 4x； x3 2石的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點:2x1 2 ，8x2，X32x3，則由f x0 得 x11， X20， X30X1X2再用充分條件進(jìn)行檢驗：2

17、f2f2f2f2f2f2 2， 28，22，0，0，-0xx2X3x1 x2X1 xX2 X3200即2f 0 8 0為正定矩陣得極小點為x* (1,0,0)T，最優(yōu)值為-10 0 2解二：目標(biāo)函數(shù)改寫成minf (xi,X2,X3)= (Xi 1)2 4x； x； 1易知最優(yōu)解為(1,0,0)，最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。minf(X) X1X22x2x1x22X2其中X(X1, X2)T，給定初始點Xc(0,0)Tf(x)解一：目標(biāo)函數(shù)f (x)的梯度f(x)(X1)14為2x2f(x)12x-|2x2(X2)1f (X(0)令搜索方向d1f(X(0)11再從X

18、0)出發(fā)，沿d方向作一維尋優(yōu)，令步長變量為 ，最優(yōu)步長為1，則有x(0)d0101故 f (x) f(X(0)d(1)()2( )22()2 2；21()令1( )22 0可得11 X(1) x()d011求出X點之后，011與上類似地，進(jìn)行第二次迭代：f(X )1令 d(2)f(X )111令步長變量為，最優(yōu)步長為2，則有Xd(2)111111故f(x)f(X d(2) ( 1)(1) 2(1)22( 1)( 1)(2 21)5212()令2（)10 20可得 21x(2)X(1)d(2) 1 1 10.8515 11.2f(X）0.2此時所達(dá)到的精度f(X(2)0.28280.21本題最優(yōu)

19、解X1.5，f（X ）1,25解二：利用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=gf un(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(fu n,gfu n,xO)結(jié)果x=,val=k=33即迭代33次的到最優(yōu)解x=,;最優(yōu)值val=4、試用Newton法求解第3題解一：計算目標(biāo)函數(shù)的梯度和Hesse陣x=,目標(biāo)函數(shù)f (x)f(x)的梯度

20、 f(x)(X1)f(x)(X2)1 4x-|1 2x12x22x22f(X)G，其逆矩陣為G0.50.50.51X(1) X(0)G1f (X(0)T0,00.50.50.511,T1,1.5計算f（X）本題最優(yōu)解X11.5，f(X )1,25解二：除了第3題建立兩個M文件外，還需建立Hesse矩陣的M文件利用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=gf un(x)g=1+4*x(1)+2*x (2) ,-1+2*x(1

21、) +2* x(2);function h=hess(x)g=4 2;2 2 ;調(diào)用文件x0=0,0；x,val,k=n ewton (fu n,gfu n,hess,xO)結(jié)果val=k=15、用 FletcherReeves法求解問題2 2min f(X) x-i 25x2其中X(xX2)T，要求選取初始點X0(2,2)T10120X120Q f(x) ；(m,X2),G，r050X2050解一:f (x)(2x1 ,50x2 )t .第一次迭代：令P0r0 ( 4, 100)T ,TP0 Gp0(4,100)4100204(4, 100)050100150即，X(1) X(0)0 P0(

22、1.92,0)T第二次迭代：r1 (皿，0 鶉僉，P1r1 0p ( 3.846, 0.15)T3.84(3.84,0)0203.846(3.846, 0.15)0500.15T1 APGp10.4802(2)(1)TX X 1 P1(0.0732, 0.072)第三次迭代：D (0.1464, 3.6)t(建議同學(xué)們自己做下去，注意判別|h|)解二：利用matlab程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的 M文件function f=fun(x) f=x(1)A2+25* x(2) *x(2);function g=gf un(x)g=2*x(1), 50* x(2);調(diào)用文件x0=2,2 ;

23、epsilon=1e-6;x,val,k=frcg(fun,gfun,x0, epsilon)結(jié)果x = *,val =k = 616、試用外點法(二次罰函數(shù)方法)求解非線性規(guī)劃問題min f (X)(% 2)2 x；s.t. g(X) x2 1 0其中 X (x1,x2) R2解：設(shè)計罰函數(shù) P(x,M ) f(X) M * g(X)A 2采用Matlab編程計算，結(jié)果x=1 0；最優(yōu)結(jié)果為1。(調(diào)用)7、用內(nèi)點法(內(nèi)點障礙罰函數(shù)法)求解非線性規(guī)劃問題：min(x1 1)3 x2s.t x1 1 0x；0解：容易看出此問題最優(yōu)解為x=1 0；最優(yōu)值為8.給出罰函數(shù)為3P(x,r) (x,1)

24、 X2r(1/(X!1)1/ x；)令 P(x,r)3(洛X1r2X，從而當(dāng)r 0時，x(r)(1 .TT3)1/2匚(建議同學(xué)自己編程序計算)&用乘子法求解下列問題min f(X)h1(X)為2X1x22X22 0解：建立乘子法的增廣目標(biāo)函數(shù):(X, , ) X： X；(x X2 2 -(x X2 2)a2令：_(x, , ) 2x：Xi(Xi x；2)0(x,)Xi(Xi x； 2)0解上述關(guān)于X的二元一次方程組得到穩(wěn)定點22 2 X22 21當(dāng)乘子 取2時，或發(fā)參數(shù) 趨于無窮時，得到XX*即最優(yōu)解1（建議同學(xué)自己編程序計算）練習(xí)題四1、石油輸送管道鋪設(shè)最優(yōu)方案的選擇問題：考察網(wǎng)絡(luò)圖4-6

25、，設(shè)A為出發(fā)地，F(xiàn)為目的地，B，C, D, E分別為四個必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪 設(shè)的位置，線段旁的數(shù)字表示鋪設(shè)這些管線所需的費用。問如何鋪設(shè)管道才能使總費用 最小圖4-1解: 第五階段：E 1 F 4 ； E2- F 3 ；5; D3-Ei F5 ;第四階段：Di E1 F 7 ; D2-E2-F第三階段：C1 D1 E1 F 12; C2-D2-E2-F10 ; C3-D2-E2-F8;C4 D3- E1-F9;第二階段：B1 C2 D2-E2-F13; B2C3-D2-E2-F15 ;第一階段：A B1 C2- D2- E2- F17 ;最優(yōu)解：A B1C2- D

26、2- E2 F最優(yōu)值：172、用動態(tài)規(guī)劃方法求解非線性規(guī)劃maxf(x)x!.區(qū).x3x1 x2 x327X1, X2,X30解：x-i 9, x2 9,x3 9，最優(yōu)值為 9。3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃max z 7x； 6x 5x；s.t x-i 2x210x-i 3x29x1, x20解：用順序算法階段：分成兩個階段，且階段1、2分別對應(yīng)“X2。決策變量：x-i, x2狀態(tài)變量：Vi，Wi分別為第j階段第一、第二約束條件可供分配的右段數(shù)值。* 2 2 2f1 (v1, w-i) max7 x-i 6x min7 V| 6v1,7w1 6w10 X1 w*x1 mi nWwdf2 (

27、v2, w2) max5 x2 f1 (v2 2x2,w2 3x2)05222max5 x2 min7( v2 2x2)6(v2 2x2),7( w2 3x2) 6(w2 3x2)由于 v210, w29，*22f2 (v2, w2) f2 (10,9) maxmin33 x2 292x2 760,68 x2 396x2 621可解的Xi96X20.2，最優(yōu)值為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到城市

28、4路線3-4 距離4。5、某公司打算在3個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場部門估計，在不同地 區(qū)設(shè)置不同數(shù)量的銷售點每月可得到的利潤如表 4-19所示。試問在各地區(qū)如何設(shè)置銷 售點可使每月總利潤最大。表4-1地 銷售點區(qū)012341016253032 :20121721223010141617解：將問題分為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 (sQ = Xk|0 Xk 700)2(s2，x2)X20.015x2 0.005& 700)

29、 7 0解得X2 700 (1：3)代入f2(s2,x2)得f2 (s,) 10000 6s2 (0.005 3)sf第四步：（第一、二、三、四季度）總效果f 1(s1, x1)= x12+s1+ f 2*( s2)將 S2=+ x - 600= x - 600 代入 fi(Si，x)得:2f1(s),x1) 0.005% s 10000 6(% 600) (0.0053)(x, 600)2f1(s,x1)(0.043)% 8 0 x1解得x1 600,代入($,%)得f1 (s2) 11800由此回溯：得最優(yōu)生產(chǎn)-庫存方案X*=600, S2*=0 ；X2*=700，S3*=0 ；X3*=8

30、00，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=；在低負(fù)荷下生產(chǎn)的產(chǎn)量函 數(shù)為h=5y，其中y為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為b=。假定開始生產(chǎn)時完好機(jī)器的數(shù)量3=1000。試問每年如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(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)

31、的機(jī)器數(shù)量。這里sk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如 sk=，就表示一臺機(jī)器 在k年度中正常工作時間只占6/10 ； uk=，就表示一臺機(jī)器在該年度只有 3/10的時間能 在高負(fù)荷下工作。狀態(tài)轉(zhuǎn)移方程為：s, , auk b(sk uk) 0.7uk 0.9(sk uk), k 1,2,L ,5k段允許決策集合為：Dk (sk)uk 0 uk sk設(shè)Vk(Sk，uk)為第k年度的產(chǎn)量，則Vk 8u, 5(Sk uk)5故指標(biāo)函數(shù)為：V,5vk(sk,uk)k 1令最優(yōu)值函數(shù)fk(sk)表示由資源量sk出發(fā)，從第k年開始到第5年結(jié)束時所生產(chǎn)的產(chǎn) 品的總產(chǎn)量最大值。因而有逆推關(guān)系

32、式：f6(s0 0fk(sk)max、8uk 5(sk uk) fk1 0.7uk 0.9( s, uQUk Dk (sk)k 123,4,5從第5年度開始，向前逆推計算。當(dāng)k=5時，有：f5(E) max 8u5 5$ 比)f6 0.7u5 0.9(e 比) 0 u5 Emax 8u5 5(s5 u55)0 u5 s5max 3u5 5ss0 u5 s55因f5是u5的線性單調(diào)增函數(shù)，故得最大解u5*，相應(yīng)的有：f5(ss) 8s當(dāng)k=4時，有:f4(s4) max0 U4 s48u45(s4 u4)f5 0.7u40.9(s4 u4)max0 U4 S48u45(s4 u4)8 0.7u4

33、 0.9(s4 u4)max0 U4 S413.6u4 12.2(s4U4)max0 U4 S41.4u4 12.2s4故得最大解，u4*=S4，相應(yīng)的有f4(s4)13.6s4依此類推，可求得U3U20,相應(yīng)的相應(yīng)的f3(S3)f?(s?)17.5s,20.8s?Ui0,相應(yīng)的fi(S)23.7si因 s1=1000,故：fsj23700計算結(jié)果表明：最優(yōu)策略為Ui 0,U?0,U3 S3,U4 S4,U5 S5即前兩年應(yīng)把年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)器投入高 負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為 23700臺。在得到整個問題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還

34、需反過來確定每年年初的狀態(tài)，即 從始端向終端遞推計算出每年年初完好機(jī)器數(shù)。已知s1=1000臺，于是可得：S20.7u；0.9(q*Ui)0.9900(臺)S30.7u；0.2(s；*U；)0.9s；810(臺)S40.7u30.9(S3*U3)0.7S3567(臺)S50.7u40.9(S4*U4)0.7S4397(臺)S60.7u50.9(S5*U5)0.7S5278(臺)&有一輛最大貨運量為10t的卡車，用以裝載；3種貨物，每種貨物的單位重量及相應(yīng)單位價值如表4-20所示。應(yīng)如何裝載可使總價值最大表4- 2貨物編號i單位重量（t）345單位價值ci456解：建模設(shè)三種物品各裝Xi,X2,

35、 X3件max（4 x1 5x2 6x3）3x-| 4x2 5x310Xj 0內(nèi) I , j 1,2,3利用動態(tài)規(guī)劃的逆序解法求此問題。S1c,D1（S1） X1 |0X1S1S2S, X1,D2（S2）區(qū)|0X2!S3S2X2 , D3 （S3）X3|0X3；狀態(tài)轉(zhuǎn)移方程為：Sk 1Tk（Sk,Xk） Skxk,k3,2,1該題是三階段決策過程，故可假想存在第四個階段，而x4 0，于是動態(tài)規(guī)劃的基本方程為：k 3,fk（Sk）max Xk, fk 1（Sk 1）,k 3,2,1Xk DK（Sk）f4（S4）0f3（S3）max6x3X3 0,1L ,Sa/5k 2,f2（S2）max 5x2

36、X 0,1L 吟f3（S3）k 1,max 5x2X2 0,1L ,字4f3（S24X2）fi（s）max4xi f2（S2）x1 U,l，2,3max 4 x1x 0,1,2,1f2（Si 3XJ計算最終結(jié)果為X12,X2 1,X3 0，最大價值為139、設(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%, Pf20%,而 產(chǎn)品必須經(jīng)過三部機(jī)器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬元進(jìn)行技術(shù)改造，以便最大限度地提高產(chǎn)品的成品率指標(biāo)。現(xiàn)提出如下四種改進(jìn)方案：方案1不撥

37、款，機(jī)器保持原狀；方案2:加裝監(jiān)視設(shè)備，每部機(jī)器需款 1萬元；方案3:加裝設(shè)備，每部機(jī)器需款2萬元；方案4:同時加裝監(jiān)視及控制設(shè)備，每部機(jī)器需款 3萬元；采用各方案后，各部機(jī)器的次品率如表 4-21。表4- 3ABC不撥款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)函

38、數(shù)為 max R=(1- Pa)(1- PB)(1- P。仍采用反向遞推第一階段：對機(jī)器C撥款的效果r1(s1, x1)=d1(s1, x1)r)(s0,x0)= d1(s1, x1Xis 10123X1*R(S1, X 1*)001121,2334353第二階段：對機(jī)器B, C撥款的效果由于機(jī)器A最多只需3萬元，故s22遞推公式：R2( s2, x2)= d2( s2, x2)Ri( si, xi*)例：F2(3,2)= d2(3,2)R1(1,1)=得第二階段最優(yōu)決策表s 1X1*R(s1, X 1*)001121,2334353s 20123X2*F2(S2, X2*)2232,3435

39、3第三階段：對機(jī)器A, B, C 撥款的效果邊界條件：S3 = 5遞推公式：R 3(s3, x3)=d3(s3, x3)R2(s2,x2*)例：電(5,3)= d3(5,3)R2(2,2)=得第三階段最優(yōu)決策表I : %3=1, %2=3, x=1,R=II : x3=2, x2=2, xi=1, 13=III :X3=2, X2=3, X=0,電=練習(xí)題五1考察多目標(biāo)規(guī)劃問題x 2,2 x 1其中 f1(x) x , f2(x)1, 1 x 2 ，試畫出個目標(biāo)函數(shù)的圖形，并求出x 1, x 2Rl,R2, Rab, Rpa , Rwp，這里R是即1 ( X)的最優(yōu)解集。解：2、用線性加權(quán)法中的法求解下述多目標(biāo)規(guī)劃問題min f/x) 4人 6x2 max f2(x) 3x 3x2。2x 4x214s.t 6x 3x224Xi,X20解：min f1(x) 4x-| 6x2 最優(yōu)解為 x(1)=0 0T ；max f2(x) 3x1 3x2 最優(yōu)解為 x二3 2 T ;利用法得線性方程組：1*0 2*01*242*15解得唯一加權(quán)系數(shù)0.3846,0.6154原多目標(biāo)規(guī)劃加權(quán)后min F (x)0.3