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

資料資料x(k+1)x(k+1)?一x(k)||x(k)II，f(x(k+1))-f(x(k))<￡，f(x(k+1))-f(x(k))〈￡，||vf(x(k))<￡等等。練習(xí)題一1、建立優(yōu)化模型應(yīng)考慮哪些要素?答：決策變量、目標(biāo)函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準(zhǔn)則。minf(x)答：針對(duì)一般優(yōu)化模型s.t.g,(x)?0,i=1,2,m，討論解的可行域。，若存在一點(diǎn)h(x)=0,j=1,,p〃 ??jX*eD，對(duì)于VXeD均有f(X*)<f(X)則稱X*為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭

代算法的收斂性是指迭代所得到的序列X(1),X⑵，，X(K)，滿足f(X(K+1))<f(X(K))，則迭代法收斂；收斂的停止準(zhǔn)則有I忖k+1)-x(k)|卜￡二練習(xí)題二1某公司看中了例 中廠家所擁有的種資源、、和，欲出價(jià)收購(gòu)(可能12 3用于生產(chǎn)附加值更高的產(chǎn)品)。如果你是該公司的決策者，對(duì)這3種資源的收購(gòu)報(bào)價(jià)是多少？(該問題稱為例2.的1對(duì)偶問題)。解：確定決策變量對(duì)種資源報(bào)價(jià)y,y-作為本問題的決策變量。123確定目標(biāo)函數(shù)問題的目標(biāo)很清楚——“收購(gòu)價(jià)最小”。確定約束條件資源的報(bào)價(jià)至少應(yīng)該高于原生產(chǎn)產(chǎn)品的利潤(rùn)，這樣原廠家才可能賣。因此有如下線性規(guī)劃問題：minw=170y+100y+150y1235y+2y+y>10123s.t./y+3y+5y>18123y,y,y>0123*、2研究線性規(guī)劃的對(duì)偶理論和方法(包括對(duì)偶規(guī)劃模型形式、對(duì)偶理論和對(duì)偶單純形法)。答：略。minz=x.I―x?+x3minz=4-x2+x3x.1+x2一2x3<2x1一2x2+x3（）St<S..2x.+xo+xQ<3123 ；（）S.t.<x2-2x3+x4一x.1 +x3<4x2+x& +x乙 Jx.,x9,x2>0123x.>0（i=1,2,…i、用單純形法求解下列線性規(guī)劃問題：二2二25=5,5）解：（）引入松弛變量，，TOC\o"1-5"\h\zminz=x-x+x+0*x+0*x+0*x123 4 5 6x+x一2x+x =2\o"CurrentDocument"2 3 4x+x+x +x5 =3S.t.< 1 2 3一x1+x3 +x6=4x1,x2,x3,x4,x5,x6>0因檢驗(yàn)數(shù)。,故確定為換入非基變量，以的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，22 2最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。 T基因檢驗(yàn)數(shù)。，故確定為換入非基變量，以的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，33 3最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。 T基因檢驗(yàn)數(shù)。,表明已求得最優(yōu)解：X*=(0,8/3,1/3,0,0,11/3)，去除添加的松弛變量，原問題的最優(yōu)解為：X*=(0,8/3,1/3)。(2)根據(jù)題意選取(2)根據(jù)題意選取，，為基變量:x1-2x2+x3x2-2x3+x4TOC\o"1-5"\h\zx2+x3 +x5乙 J Jx.>0(i=1,2,…,5)因檢驗(yàn)數(shù)。最小，故確定為換入非基變量，以的系數(shù)列的正分量對(duì)應(yīng)去除22 2常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。 T 基因檢驗(yàn)數(shù)。最小，故確定為換入非基變量，以的系數(shù)列的正分量對(duì)應(yīng)去除33 1常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。 T 基因檢驗(yàn)數(shù)。，表明已求得最優(yōu)解：X*=(9,4,1,0,0)。、分別用大m法、兩階段法和軟件求解下列線性規(guī)劃問題:minz-4X1+x23X]+x2-39X[+3Xc>612；X]+2x2<3maxz=10x]+15x?+12x3x1,x25x1+3x2+x3<9

J- 4 J一5x1+6x2+15x3<15

_L 4 J2x]+x2+x3>5x1,x2,x3>0根據(jù)題意約束條件和可以合并為，引入松弛變量，，構(gòu)造新問題。minz=4x+x+Mx+0*x12 3 4x+x+x=312 3s.t.<x+2x +x=3124x,x>014因檢驗(yàn)數(shù)。0表明已求得最優(yōu)解：X*=(3/5,6/5)。調(diào)用代碼:輸出結(jié)果：()大法引入松弛變量，，，構(gòu)造新問題。maxz=10元+15元+12元+0元+0元+0元一Mx1 2 3456 75x+3x+x+x1 234-5x+6x+15x+xS.t.< 1 2 3 52x+x+x123二9二15—x+x—567x,,x>017單純形表計(jì)算略；當(dāng)所有非基變量為負(fù)數(shù)，人工變量x7.，所5以原問題無可行解。請(qǐng)同學(xué)們自己求解。調(diào)用代碼：輸出結(jié)果：原題無可行解。5、用內(nèi)點(diǎn)法和軟件求解下列線性規(guī)劃問題:minz—2x1+x2+x3x]+2x2+2x3—6s.t/2x]+x2 —5x],x2,x3>0解：用內(nèi)點(diǎn)法的過程自己書寫，參考答案：最優(yōu)解X—[4/37/30]；最優(yōu)值調(diào)用代碼:輸出結(jié)果：6、用分支定界法求解下列問題：maxz=7x1+9x2maxz=7x1+9x2-X1+3x2<6s.t.< 7x1+x2<35x,x.>0且x1為整數(shù)12 1^ x1+x2<6() 11, “s.t.< 5X]+9x2<45X1,X2>0且均為整數(shù)12解：()調(diào)用編譯程序最優(yōu)解［3；3最］優(yōu)值()調(diào)用編譯程序最優(yōu)解；0最優(yōu)解；0最］優(yōu)值、用隱枚舉法和 軟件求解下列問題:minz-4minz-4x^+3x?+2x32x1-5x2+3x&<4maxz=3xj+2x2-5x3-2x4+3x54x.1+x2+3x3>3x2+x3>1x.=0或1(j=1,2,3)jx1+ x2 +x3 +2x4 +x5 <4,L 乙 J tT J7%] +3x3-4x4+3x5<811x]一6x2+3x4一3x5>1

xj=0或1(j-1,2,…,5)解：隱枚舉法：（1）將（0，，0）（0，0，1））（1，0，0）（0，1，1）（1，，0）（1，1，1）分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是（，1），目標(biāo)函數(shù)最優(yōu)值（2）將（（2）將（0，，，，1，1，1，1）分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是，，，0），目標(biāo)函數(shù)最優(yōu)值-。5軟件求解:調(diào)用代碼：價(jià)值向量不等式約束系數(shù)矩陣A中的分號(hào)“；”為行分隔符不等式約束右端常數(shù)向量調(diào)用函數(shù) 。注意兩個(gè)空數(shù)組的占位作用。輸出結(jié)果調(diào)用代碼：價(jià)值向量不等式約束系數(shù)矩陣A中的分號(hào)“；”為行分隔符0,-3,3];不等式約束右端常數(shù)向量調(diào)用函數(shù) 。注意兩個(gè)空數(shù)組的占位作用。輸出結(jié)果最優(yōu)值5。8某地區(qū)有、、三個(gè)化肥廠，供應(yīng)本地甲、乙、丙、T四個(gè)產(chǎn)糧區(qū)。已知各化肥廠可供應(yīng)化肥的數(shù)量和各產(chǎn)糧區(qū)對(duì)化肥的需要量，以及各廠到各區(qū)每噸化肥的運(yùn)價(jià)如表2-2所8示。試制定一個(gè)使總運(yùn)費(fèi)最少的化肥調(diào)撥方案。表運(yùn)價(jià)\產(chǎn)糧化肥廠甲乙丙T各廠供應(yīng)量萬噸各區(qū)需要量萬噸解：設(shè)、、三個(gè)化肥廠為、、，甲、乙、丙、T四個(gè)產(chǎn)糧區(qū)為、、、123 123為由運(yùn)化肥至的運(yùn)價(jià)，單位是元噸；為由運(yùn)往的化肥數(shù)量ij i j ij i j）單位是噸；表示總運(yùn)費(fèi)，單位為元，依題意問題的數(shù)學(xué)模型為:minz立二，ijiji=1j=1X+X+X1121X+X12 22X+X13 23S.t.<X+X14 24X+X11 12X+X21 22X+X31 32+x=631+x=632+x=333+x=334+x+x=713 14+x+x=823 24+x+x=733 34該題可以用單純形法或自帶工具箱命令（ ）求解。、求解下列不平衡運(yùn)輸問題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價(jià)格C..，框外右ij側(cè)的一列數(shù)為各發(fā)點(diǎn)的供應(yīng)量q，框底下一行數(shù)是各收點(diǎn)的需求量b.）：aij要求收點(diǎn)3的需求必須正好滿足。0要求收點(diǎn)3的需求必須正好滿足。0要求收點(diǎn)1的需求必須由發(fā)點(diǎn)4供應(yīng)。解答略。1、0一公司經(jīng)理要分派4位推銷員去4個(gè)地區(qū)推銷某種商品。推銷員各有不同的經(jīng)驗(yàn)和能力，因而他們?cè)诓煌貐^(qū)能獲得的利潤(rùn)不同，其獲利估計(jì)值如表2-2所9示。公司經(jīng)理應(yīng)怎樣分派才使總利潤(rùn)最大？(35272837)28342940M-C, h352432331. P、24322528JM=40解：用求極大值的“匈牙利法”求解。效率矩陣表示為:（513123)126110行約簡(jiǎn)[——51687<1681512J(2 10(21090）126126110列約簡(jiǎn)011321=>(0)11I8074J標(biāo)號(hào)、8(0)6 （0）]8 0*0* 2所畫（）元素少于4 4）（=），未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有元素的最少數(shù)直線集合）:，在未被直線覆蓋處減去，在直線交叉處加上。((0)840*)(0840)1046(0)10460標(biāo)號(hào)01104'>0*11(0)418046J18(0)46)未被直線覆蓋的最小元素為(1000)??得最優(yōu)解：00010010[0100J??.使總利潤(rùn)為最大的分配任務(wù)方案為:此時(shí)總利潤(rùn)練習(xí)題三1、用0.6法1求8解問題min3(t)=13-21+1t>0的近似最優(yōu)解，已知叭t)的單谷區(qū)間為[0,3],要求最后區(qū)間精度￡=05。答： ；最小值 (調(diào)用 函數(shù))、2求無約束非線性規(guī)劃問題nf(x1,x2,x3)Xnf(x1,x2,x3)TOC\o"1-5"\h\z\o"CurrentDocument"1 23 1的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點(diǎn)：=2=2x―2， =8x， =2x，則由Vf(x)=0得x=1，x=0，x=0dx 1 dx 2dx 3 1 2 31 23再用充分條件進(jìn)行檢驗(yàn)：s2f_2S2f_8S2f_2 S2f_0S2f_0 S2f_02，8， 2，0，0，0Sx2 Sx2 Sx2 SxSx SxSx SxSx1 2 3 12 13 23'200、即V2f=080為正定矩陣得極小點(diǎn)為x*=(1,0,0)t，最優(yōu)值為、002,解二：目標(biāo)函數(shù)改寫成f(x,x,x)(x一1)2+4x2+x2-1

123 1 2 3易知最優(yōu)解為(1,0),，0最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。minf(X)=x-x+2x2+2xx+x21 2 1 12 2其中X=(x,x)T，給定初始點(diǎn)X0=(0,0)T。12解一:目標(biāo)函數(shù)f(X)的梯度Vf(X)=/(X)S(x)16f(x)S(x)21+4x+2x12-1+2x+2x12-11-九

九Vf(X(0))=」令搜索方向d(1)=-Vf(X(0))=；再?gòu)腦(0)出發(fā)，沿d-11-九

九優(yōu)，令步長(zhǎng)變量為九，最優(yōu)步長(zhǎng)為九，則有X(0)+九d(1)=1故f(x)=f(X(0)+九d(1));(-九)-九+2(-九)2+2(-九認(rèn)+X2=九2-2九二3(九)1令p(九)二2令p(九)二2九一2=0可得九=1X⑴=X(0)+九d(1)二與上類似地，進(jìn)行第二次迭代：Vf(X(1))=-1-1-11-11求出X⑴點(diǎn)之后，令d(2)=-Vf(X(1))=令步長(zhǎng)變量為九，最優(yōu)步長(zhǎng)為九，則有2X(1)X(1)+九d⑵=[19卜九-1九十1故f(x)=f(X(1)十九d(2))二(九一1)-(九+1)+2(九一1)2+2(九一1)(九+1)+(九+1)2:5九2-2九-1二((九)2令?'(九)二10九令?'(九)二10九一2=0可得入=—2、 2 5X⑵=X⑴+九d(2)二21+[1-0.81.2Vf(X⑵)=0.2-0.2此時(shí)所達(dá)到的精度|"(X⑵”六0.2828本題最優(yōu)解X*=15，f(X*)=-1,25

.解二：利用 程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的文件調(diào)用文件結(jié)果即迭代次的到最優(yōu)解、試用 法求解第題。解一：計(jì)算目標(biāo)函數(shù)的梯度和 陣目標(biāo)函數(shù)f(X)的梯度Vf(X)=/(X)S(x)1/(X)

S(x)21+4x+2x12-1+2x+2x12「42] 「0.5V2f(X)=22=G，其逆矩陣為G-1=—乙 U?J-0.51X⑴=X(0)-G-1Vf(X(0))」0,0卜-055—0?5h'T}=[-1,1.5卜計(jì)算I|Vf(X⑴)卜0?！弧?「-11本題最優(yōu)解X*= ，f(X*)=-1,25?解二：除了第題建立兩個(gè)文件外，還需建立矩陣的文件利用 程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的文件調(diào)用 文件結(jié)果、用 一法求解問題minf(X)=x2+25x21 2其中X=(x,x)>要求選取初始點(diǎn)X0=(2,2)r,e=10-6。12解一:…1， 、f…1， 、f(工)=2(x1,x)205050,r=Vf(x)=(2x,50x)r.第一次迭代：令p第一次迭代：令p=-r=(-4,-100)r,0(4,100)rrr―0-0—pr(4,100)rrr―0-0—prGp00(-4,-100)即，X(1)=X(0)100-450050-100+ap=(1.92,0)r00第二次迭代:r=(3.84,0)r,第二次迭代:r=(3.84,0)r,1aIIrII2 3D=—1——= 0IIrII2 20000p=-r+Pp=(-3.846,-0.15)t1 1 00(3.84,0)rTr=-(3.84,0)rTr=-i~i—pTGp11(-3.846,-0.15)3.84]0」20『3.846050_|[-0.15:0.4802X⑵=X(i)+ap=(0.0732,-0.072)r11第三次迭代：丫=(0.1464,-3.6)r……(建議同學(xué)們自己做下去，注意判別廠11<￡2 k11解二：利用 程序求解首先建立目標(biāo)函數(shù)及其梯度函數(shù)的文件調(diào)用文件結(jié)果6、試用外點(diǎn)法(二次罰函數(shù)方法)求解非線性規(guī)劃問題Jminf(X)=(x-2)2+x2|s.t.g(X)=x-1>02其中X-(x,x)GR212解：設(shè)計(jì)罰函數(shù)P(x,M)-f(X)+M*[g(X)]A2采用編程計(jì)算，結(jié)果1最優(yōu)結(jié)果為。(調(diào)用7、用內(nèi)點(diǎn)法(內(nèi)點(diǎn)障礙罰函數(shù)法)求解非線性規(guī)劃問題：min(x+1)3+x<s.t.x-11>0 2x1>02解：容易看出此問題最優(yōu)解為 ；最優(yōu)值為給出罰函數(shù)為 P(x,r)=(x+1)3+x+r(1/(x一1)+1/x)TOC\o"1-5"\h\z\o"CurrentDocument"1 2 1 2令二3(x+1)2--^―二0； P^二1-二二0x1 (x一1)2 x x2\o"CurrentDocument"1 1 2 2從而當(dāng)r-0+時(shí)，(建議同學(xué)自己編程序計(jì)算)minf(X)=x2+x2、用乘子法求解下列問題|h(x)=x+x1-22=0TOC\o"1-5"\h\zi1 1 2解：建立乘子法的增廣目標(biāo)函數(shù)：V(x,九,o)=x2+x2-九(x+x-2)+—(x+x-2)八21 2 1 2 2 1 2令：加區(qū)出二2x-X+a(x+x-2)二0d.x 1 1 21^A￡2二2x-X+a(x+x-2)二0ax 2 121解上述關(guān)于的二元一次方程組得到穩(wěn)定點(diǎn)一2a+九一__2a+2x―2a+X2a+2當(dāng)乘子X取時(shí)，或發(fā)參數(shù)a趨于無窮時(shí)，得到x=1=x*即最優(yōu)解。1(建議同學(xué)自己編程序計(jì)算)練習(xí)題四1石油輸送管道鋪設(shè)最優(yōu)方案的選擇問題：考察網(wǎng)絡(luò)圖,設(shè)為出發(fā)地，為目的地，BCD分別為四個(gè)必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設(shè)的位置，線段旁的數(shù)字表示鋪設(shè)這些管線所需的費(fèi)用。問如何鋪設(shè)管道才能使總費(fèi)用最小？圖4-1解：第五階段：一；一；第四階段：一一7 2— 5一1第三階段：一一一；一一一； ?；第二階段： 一一一一3一一2一第一階段：一一一一一；最優(yōu)解：一一一一一最優(yōu)值：2、用動(dòng)態(tài)規(guī)劃方法求解非線性規(guī)劃maxf(x)=\；x+、；x+x+x+x=27《1 2 3x,x,x>0123解：x=9,x=9,x=9，最優(yōu)值為°1233、用動(dòng)態(tài)規(guī)劃方法求解非線性規(guī)劃maxz=7x2+6x+5x21 1 2s.t.x+2x<10< 1 2x-3x<912x,x>012解：用順序算法階段：分成兩個(gè)階段，且階段、分別對(duì)應(yīng)x,x。12決策變量：x,x12狀態(tài)變量：V,攻分別為第階段第一、第二約束條件可供分配的右段數(shù)值。ii

max{7x2+6x}=min{7v2+6v,7w2+6w}0<x<v0<x<v0<x；<>11x*-min{v,w}1 11f*(v,w)=max{5x2+f*(v-2x,w+3x)}222 2 12 22 20<x<52-max{5x2+min{7(v-2x)2+6(v一2x),7(w+3x)2+6(w+3x)}}

2 22 22 22 220<x<52由于v=10,w=9,22f*(v,w)=f*(10,9)-max{min{33x2一292x+760,68x2+396x+621}222 2 2 2 2 20<x<52可解的x-9.6,x-0.2，最優(yōu)值為.12、設(shè)四個(gè)城市之間的公路網(wǎng)如圖。、設(shè)四個(gè)城市之間的公路網(wǎng)如圖。7兩點(diǎn)連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應(yīng)的最短距離。圖4-2圖4-2城市公路網(wǎng)解：城市1到城市4路線——1-3-距4離1；0城市2到城市4路線——2-4距離8；城市3到城市4路線——3-4距離4。5、某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場(chǎng)部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤(rùn)如表4-1所9示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤(rùn)最大。表地區(qū)銷售點(diǎn)01234101625303220121721223010141617解：將問題分為3個(gè)階段，

決策變量表示分配給第個(gè)地區(qū)的銷售點(diǎn)數(shù);狀態(tài)變量為表示分配給第個(gè)至第個(gè)地區(qū)的銷售點(diǎn)總數(shù);狀態(tài)轉(zhuǎn)移方程： 一，其中4允許決策集合： （）{ 0W}階段指標(biāo)函數(shù)：（）表示個(gè)銷售點(diǎn)分配給第個(gè)地區(qū)所獲得的利潤(rùn)；最優(yōu)指標(biāo)函數(shù)（）表示將數(shù)量為的銷售點(diǎn)分配給第個(gè)至第個(gè)地區(qū)所得到的最大利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為：f(S)=max[g(x)+f(s-x)] k=3,2,1kk2/kk k+1kk0-xk-skf(s)=0443寸，f(s)=max[g(x)]33 33g3（x3）f3(s3)x3*012340000110101214142316163417174max[g(x)+fmax[g(x)+f(s-x)]g2(x2)+/3(s2一芯2)f2(s2)x2*01234000010+1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312,32時(shí)，f(s)=22220-x2-s2 2 232 2

1時(shí)，f(s)=max[g(X)1時(shí)，f(s)=max[g(X)+f(s—%)]f(s)=max[g(X)+f(4—%)]110<X1<s1 1 121 1，110<X1<4 1 121最優(yōu)解為： ，ii ,即在第個(gè)地區(qū)設(shè)置個(gè)銷售點(diǎn)，第個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，第3個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，每月可獲利潤(rùn)6設(shè)某廠計(jì)劃全年生產(chǎn)某種產(chǎn)品。其四個(gè)季度的訂貨量分別為 公斤，公斤，公斤和公斤。已知生產(chǎn)產(chǎn)品的生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0.0。0廠5內(nèi)有倉庫可存放產(chǎn)品，存儲(chǔ)費(fèi)為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。解：四個(gè)季度為四個(gè)階段，采用階段編號(hào)與季度順序一致。設(shè)為第季初的庫存量，則邊界條件為設(shè)為第季的生產(chǎn)量，設(shè) 為第季的訂貨量；，， 都取實(shí)數(shù)，狀態(tài)轉(zhuǎn)移方程為 仍采用反向遞推，但注意階段編號(hào)是正向的目標(biāo)函數(shù)為：f(%)=minX(0.005%2+s)TOC\o"1-5"\h\z1 ii%1，%2,%3,%4i=1第一步：(第四季度)總效果f4(s4,x4)=0.x0420+s54由邊界條件有： - ，解得： -將代入 得：第二步：(第三、四季度)總效果得：代0入得：f(s,x)=0.005x2+s+7200-11(x+s—500)333 3 3 3 3+0.005(x+s-500)233=0.01x2+0.01xs-16x+0.005s2-15s+139503 33 3 3 3儲(chǔ)(s3,x3)=0.02x+0.01s-16=0\o"CurrentDocument"d.x 3 33解得 x*=800-0.5s, 代入/i(s,x)得3 3 333f*(s)=7550-7s+0.0025s2

33 3 3第三步：(第二、三、四季度)總效果將 -代入 得：f(s,x)=0.005x2+s+7550-7(x+s-700)222 2 2 2 2+0.0025(x+s-700)222.(s2,x2)=0.015x+0.005(s-700)-7=0ax 2 22解得 x*=700-(1/3)s,代入(s,x)得2 2 2 2 2f*(s)=10000-6s+(0.005/3)s2

22 2 , 2第四步：(第一、二、三、四季度)總效果代入 得:f(s,x)=0.005x2+s+10000-6(x-600)111 1 1+(0.005/3)(x1-600)2af(s,x)—1_1-1ax1

解得=(0.04/3)x1-8=0x*=600,代2(s,x)得

1 111f*(s)=1180012由此回溯：得最優(yōu)生產(chǎn)-庫存方案，00*=；0*=8，00*=3；、某種機(jī)器可在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為，其中為投入生產(chǎn)的機(jī)器數(shù)量，年完好率；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為 ，其中為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為 .假定開始生產(chǎn)時(shí)完好機(jī)器的數(shù)量 0試問每年如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在年內(nèi)生1產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：構(gòu)造這個(gè)問題的動(dòng)態(tài)規(guī)劃模型：設(shè)階段序數(shù)表示年度。狀態(tài)變量為第年度初擁有的完好機(jī)器數(shù)量，同時(shí)也是第-年度末時(shí)的完好機(jī)器數(shù)量。決策變量為第年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是-為該年度中分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。這里和均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如，就表示一臺(tái)機(jī)器在年度中正常工作時(shí)間只占 1 ,就表示一臺(tái)機(jī)器在該年度只有 的時(shí)間能在高負(fù)荷下工作。狀態(tài)轉(zhuǎn)移方程為：s=au+b(s-u)=0.7u+0.9(s-u),k=1,2,,5k+i kkk k kk段允許決策集合為：D(s)={u10<u<s} …設(shè)v設(shè)v(s,ukkk)為第年度的產(chǎn)量，則v=8u+5(s-u)kkkk故指標(biāo)函數(shù)為：V=￡v(s,u)1,5 kkkk=1令最優(yōu)值函數(shù) 表示由資源量 出發(fā)，從第年開始到第年結(jié)束時(shí)所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆推關(guān)系式：f(sf(s)=066f(s)=max(8ukk kU^Dk(sk)+5(sk-u)+f[0.7u+0.9(s-u)]}k k+1 k kkk=1,2,3,4,5從第5年度開始，向前逆推計(jì)算。當(dāng)時(shí)，有：

f5(s5)=max0<u5<s,

max0<u5<s

max0<u5<s{8u+5(s—u5 55)+ff5(s5)=max0<u5<s,

max0<u5<s

max0<u5<s{8u+5(s—u5 55)+f[0.7u+0.9(s-u)]}{8u+5(s—u5)}

5 55{3u+5s}556555因是的線性單調(diào)增函數(shù)，故得最大解,相應(yīng)的有:f5(s5)=8s5時(shí)4，有：故得最大解，f(s)=max4444 0<u<s44=max0<u4<s4=max0<u4<s4=max0<u<s444相應(yīng)的有{8u+5(s44{8u+5(s44)+f[0.7u+0.9(s-u)]}5444)+8[0.7u+0.9(s-u)]}44依此類推可求得{l3.6u+12.2(s—u)}

4 44{l.4u+12.2s}f(s)=13.6s

44 4u*=s33u*=0,2u*=0,1相應(yīng)的f(s)=17.5s33 3相應(yīng)的f(s)=20.8s22 2相應(yīng)的f(s)=23.7s11,故：f(s)=2370011計(jì)算結(jié)果表明：最優(yōu)策略為u*= 0,u* =0,u* =s,u* =s,u* =s1 2 3 34 45 5即前兩年應(yīng)把年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)器投入高負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為臺(tái)0。0在得到整個(gè)問題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即從始端向終端遞推計(jì)算出每年年初完好機(jī)器數(shù)。已知臺(tái)0，0于是可得：s=0.7u*+0.9(s—u*)=0.9s=900(臺(tái))TOC\o"1-5"\h\z1 11 1s=0.7u*+0.2(s—u*)=0.9s=810(臺(tái))2 22 2s=0.7u*+0.9(s—u*)=0.7s=567(臺(tái))3 33 3s=0.7u*+0.9(s—u*)=0.7s=397(臺(tái))4 44 4s=0.7u*+0.9(s—u*)=0.7s=278(臺(tái))

6 5 55 5

、有一輛最大貨運(yùn)量為 的卡車，用以裝載種貨物，每種貨物的單位重量及表相應(yīng)單位價(jià)值如表4-2所0示。應(yīng)如何裝載可使總價(jià)值最大？貨物編號(hào)單位重量（）單位價(jià)值解：建模設(shè)三種物品各裝x,x,x件123j利用動(dòng)態(tài)規(guī)劃的逆序解法求此問題。max(4x+5x+6x)123f3x+4x+5x<j利用動(dòng)態(tài)規(guī)劃的逆序解法求此問題。max(4x+5x+6x)123f3x+4x+5x<10J1 2 3Ix>0,xGI,j=1,2,3s=c,D(s)={x10<x<s}11 111狀態(tài)轉(zhuǎn)移方程為：s二s21s二s32一x,D(s)={x10<x<s}1 22 222一x,D(s)={x10<x<s}2 33 333s=T(s,x)=s-x,k=3,2,1k+1 kkkkk該題是三階段決策過程，故可假想存在第四個(gè)階段，而x=0,于是動(dòng)態(tài)規(guī)劃的基本方4程為：f(s)=max[x,f(s)],k=3,2,1kk kk+1k+1xkGDK(sk)f(s)=044k=3,f(s)=max {6x}33 333 x3=0,1,,[s3/5] 3k=2,f(s)=max[5x+f(s)]

2 2 2 3 3x2=0,1,,[s2]max[5x+f(s-4x)]2 3 2 2x2=0,1,,[j]k=1,f(s)=max[4f(s)=max[4x+f(s)]尢1=0,12322max[4x+f(s-3x)]x1=0,1,2,321TOC\o"1-5"\h\z計(jì)算最終結(jié)果為x*=2,x*=1,x*=0，最大價(jià)值為 。1 239、設(shè)有A，B，C三部機(jī)器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計(jì)結(jié)果表明，機(jī)器，，產(chǎn)生次品的概率分別為 而ABC產(chǎn)品必須經(jīng)過三部機(jī)器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬元進(jìn)行技術(shù)改造，以便最大限度地提高產(chǎn)品的成品率指標(biāo)?，F(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表不撥款撥款萬元撥款萬元撥款萬元問如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解：為三臺(tái)機(jī)器分配改造撥款，設(shè)撥款順序?yàn)?B階段序號(hào)反向編號(hào)為，即第一階段計(jì)算給機(jī)器撥款的效果。設(shè)為第階段剩余款，則邊界條件為 ；設(shè)為第階段的撥款額；狀態(tài)轉(zhuǎn)移方程為sk-=1sk-xk；目標(biāo)函數(shù)為 maR=x(1PA)-(1PB)-(1PC-)仍采用反向遞推第一階段：對(duì)機(jī)器撥款的效果

第二階段：對(duì)機(jī)器撥款的效果由于機(jī)器最多只需萬元，故>遞推公式：例：X例：X2R)(1,1)=(X1第三階段：對(duì)機(jī)器 撥款的效果邊界條件：遞推公式：X例：得第三階段最優(yōu)決策表回溯：有多組最優(yōu)解。X80.X9X.09.XX.09.X練習(xí)題五1、考察多目標(biāo)規(guī)劃問題'-X+2,-2<X<1其中f(X)=X2,f(X)=[ 1,1<X<2,試畫出個(gè)目標(biāo)函數(shù)的圖形，并求出12X一1,X>2解：R,解：R,R,R,R,R，這里R是minf(x)的最優(yōu)解集。12由PawP i _2<x<4i2用線性加權(quán)法中的a-法求解下述多目標(biāo)規(guī)劃問題minf(x)=4x+6xTOC\o"1-5"\h\z1 12maxf(x)=3x+3x。2 12'2x+4x<141 2s.t.<6x+3x<2412X,X>012解：minf(x)=4x+6x最優(yōu)解為x(D=[00]t；1 12

maxf(x)=3x+3x最優(yōu)解為x(2)=[32]t；2 12利用a法得線性方程組：由*0+入*0=a1 21入*24—入*15=a12入+入=112解得唯一加權(quán)系燃=。3846,0.6154]T原多目標(biāo)規(guī)劃加權(quán)后minF(x)=0.3846f(x)-0.6154f(x)解得加權(quán)后的最優(yōu)解為：x*=[40]t,最優(yōu)值為3用線性加權(quán)求和法求