最優(yōu)化方法練習(xí)題答案修改建議版本--刪減版

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

2、很清楚-“收購(gòu)價(jià)最小”。確定約束條件 資源的報(bào)價(jià)至少應(yīng)該高于原生產(chǎn)產(chǎn)品的利潤(rùn)，這樣原廠家才可能賣(mài)。因此有如下線性規(guī)劃問(wèn)題：2、研究線性規(guī)劃的對(duì)偶理論和方法（包括對(duì)偶規(guī)劃模型形式、對(duì)偶理論和對(duì)偶單純形法）。答：略。3、用單純形法求解下列線性規(guī)劃問(wèn)題: （1）； （2）解：（1）引入松弛變量x4，x5，x6cj1-11000CB基bx1x2x3x4x5x60x4211-21000x532110100x64101001cjzj1-11000因檢驗(yàn)數(shù)20，故確定x2為換入非基變量,以x2的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量x4作為換出的基變量.cj1-11000CB基bx1x4x

3、3x4x5x6-1x221121000x51103-1100x64101001cj-zj201100因檢驗(yàn)數(shù)30,故確定x3為換入非基變量，以x3的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量x5作為換出的基變量。cj111000CB基bx1x2x5x4x5x61x28/35/3101/32/301x31/31/301-1/31/300x611/34/3001/31/31cj-zj7/3032/31/30因檢驗(yàn)數(shù)j0,表明已求得最優(yōu)解:，去除添加的松弛變量，原問(wèn)題的最優(yōu)解為：.（2）根據(jù)題意選取x1,x4，x5，為基變量:cj01100CB基bx1x2x3x4x50x121-210

4、00x42012100x5501101cj-zj01100因檢驗(yàn)數(shù)20最小，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量x4作為換出的基變量。cj0-1100CB基bx1x2x3x4x50x1610-3201x22012100x5300311cj-zj00110因檢驗(yàn)數(shù)30,表明已求得最優(yōu)解：。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)撥方案。表2 Error! Bookmark not def

5、ined.運(yùn)價(jià)/ 產(chǎn)糧 (元/噸） 區(qū)化肥廠甲乙丙丁各廠供應(yīng)量/萬(wàn)噸A158737A2491078A384293各區(qū)需要量/萬(wàn)噸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),單位為元，依題意問(wèn)題的數(shù)學(xué)模型為:該題可以用單純形法或matlab自帶工具箱命令(linprog）求解。 9、求解下列不平衡運(yùn)輸問(wèn)題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價(jià)格，框外右側(cè)的一列數(shù)為各發(fā)點(diǎn)的供應(yīng)量，框底下一行數(shù)是各收點(diǎn)的

6、需求量)：（1） 5 1 7 10 要求收點(diǎn)3的需求必須正好滿(mǎn)足。 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解答略。練習(xí)題三1、用0。618法求解問(wèn)題的近似最優(yōu)解，已知的單谷區(qū)間為，要求最后區(qū)間精度。答：t=0。8115；最小值0。0886.（調(diào)用golds。m函數(shù)） 2、求無(wú)約束非線性規(guī)劃問(wèn)題min =的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點(diǎn)：，,則由得， 再用充分條件進(jìn)行檢驗(yàn)：，,即為正定矩陣得極小點(diǎn)為，最優(yōu)值為-1.解二：目標(biāo)函數(shù)改寫(xiě)成 min

7、 =易知最優(yōu)解為（1，0,0），最優(yōu)值為-1。3、用最速下降法求解無(wú)約束非線性規(guī)劃問(wèn)題。其中，給定初始點(diǎn)。解一:目標(biāo)函數(shù)的梯度令搜索方向再?gòu)某霭l(fā)，沿方向作一維尋優(yōu)，令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為，則有故令可得 求出點(diǎn)之后,與上類(lèi)似地，進(jìn)行第二次迭代： 令令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為,則有故令可得 此時(shí)所達(dá)到的精度本題最優(yōu)解，練習(xí)題四1、石油輸送管道鋪設(shè)最優(yōu)方案的選擇問(wèn)題：考察網(wǎng)絡(luò)圖4-6,設(shè)A為出發(fā)地，F(xiàn)為目的地,B，C，D，E分別為四個(gè)必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設(shè)的位置,線段旁的數(shù)字表示鋪設(shè)這些管線所需的費(fèi)用。問(wèn)如何鋪設(shè)管道才能使總費(fèi)用最小？圖4 1解：第五階段：E1F 4；E2

8、F 3；第四階段:D1E1-F 7；D2-E2F 5；D3-E1F 5；第三階段：C1D1E1-F 12;C2D2E2F 10；C3D2E2F 8；C4D3E1F 9；第二階段:B1C2-D2E2F 13； B2C3-D2E2F 15；第一階段:AB1C2D2E2F 17；最優(yōu)解：AB1C2D2E2-F最優(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)如

9、圖4-7。兩點(diǎn)連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應(yīng)的最短距離。圖4 2 城市公路網(wǎng)解：城市1到城市4路線1-34 距離10;城市2到城市4路線2-4 距離8；城市3到城市4路線-3-4 距離4。5、某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷(xiāo)售點(diǎn)，根據(jù)市場(chǎng)部門(mén)估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷(xiāo)售點(diǎn)每月可得到的利潤(rùn)如表4-19所示.試問(wèn)在各地區(qū)如何設(shè)置銷(xiāo)售點(diǎn)可使每月總利潤(rùn)最大。 表4- Error! Bookmark not defined.解:將問(wèn)題分為3個(gè)階段，k=1，2,3；決策變量xk表示分配給第k個(gè)地區(qū)的銷(xiāo)售點(diǎn)數(shù)；狀態(tài)變量為sk表示分配給第k個(gè)至第3個(gè)地區(qū)的銷(xiāo)售

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

11、生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0。005.廠內(nèi)有倉(cāng)庫(kù)可存放產(chǎn)品，存儲(chǔ)費(fèi)為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。解：四個(gè)季度為四個(gè)階段，采用階段編號(hào)與季度順序一致. 設(shè) sk 為第k季初的庫(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（s

12、4，x4）得： f4*(s4)=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

13、代入 f1(s1,x1) 得：由此回溯：得最優(yōu)生產(chǎn)庫(kù)存方案 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。假定開(kāi)始生產(chǎn)時(shí)完好機(jī)器的數(shù)量s1=1000.試問(wèn)每年如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高.解：構(gòu)造這個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃模型：設(shè)階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機(jī)器數(shù)量

14、,同時(shí)也是第k1年度末時(shí)的完好機(jī)器數(shù)量.決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是skuk為該年度中分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。這里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出發(fā)，從第k年開(kāi)始到第5年結(jié)束時(shí)所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆推關(guān)系式：從第5年度開(kāi)始,向前逆推計(jì)算。當(dāng)k=5時(shí)，有：因f5是u5的線性單調(diào)增函

15、數(shù)，故得最大解u5*,相應(yīng)的有：當(dāng)k=4時(shí)，有：故得最大解，u4=s4,相應(yīng)的有依此類(lèi)推，可求得因s1=1000，故：計(jì)算結(jié)果表明：最優(yōu)策略為即前兩年應(yīng)把年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)器投入高負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺(tái)。在得到整個(gè)問(wèn)題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還需反過(guò)來(lái)確定每年年初的狀態(tài)，即從始端向終端遞推計(jì)算出每年年初完好機(jī)器數(shù)。已知s1=1000臺(tái)，于是可得:8、有一輛最大貨運(yùn)量為10t 的卡車(chē)，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值如表4-20所示。應(yīng)如何裝載可使總價(jià)值最大?表4 Error! Bookmark not

16、 defined.貨物編號(hào)i123單位重量（t）345單位價(jià)值 ci456解：利用動(dòng)態(tài)規(guī)劃的逆序解法求此問(wèn)題。 狀態(tài)轉(zhuǎn)移方程為： 該題是三階段決策過(guò)程，故可假想存在第四個(gè)階段，而，于是動(dòng)態(tài)規(guī)劃的基本方程為：計(jì)算最終結(jié)果為，最大價(jià)值為13 。9、設(shè)有 A,B，C 三部機(jī)器串聯(lián)生產(chǎn)某種產(chǎn)品,由于工藝技術(shù)問(wèn)題,產(chǎn)品常出現(xiàn)次品。統(tǒng)計(jì)結(jié)果表明，機(jī)器 A，B，C產(chǎn)生次品的概率分別為 pA=30%, PB=40, PC=20， 而產(chǎn)品必須經(jīng)過(guò)三部機(jī)器順序加工才能完成.為了降低產(chǎn)品的次品率,決定撥款 5 萬(wàn)元進(jìn)行技術(shù)改造，以便最大限度地提高產(chǎn)品的成品率指標(biāo).現(xiàn)提出如下四種改進(jìn)方案：方案1:不撥款，機(jī)器保持原狀

17、；方案2:加裝監(jiān)視設(shè)備，每部機(jī)器需款 1 萬(wàn)元;方案3：加裝設(shè)備，每部機(jī)器需款 2 萬(wàn)元;方案4：同時(shí)加裝監(jiān)視及控制設(shè)備，每部機(jī)器需款 3 萬(wàn)元；采用各方案后，各部機(jī)器的次品率如表4-21。表4- Error! Bookmark not defined.ABC不撥款30%40%20撥款 1 萬(wàn)元203010撥款 2 萬(wàn)元102010%撥款 3 萬(wàn)元5%106問(wèn)如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解:為三臺(tái)機(jī)器分配改造撥款，設(shè)撥款順序?yàn)锳， B， C，階段序號(hào)反向編號(hào)為 k,即第一階段計(jì)算給機(jī)器 C 撥款的效果. 設(shè) sk 為第 k 階段剩余款,則邊界條件為 s3=5； 設(shè) xk 為第 k

18、階段的撥款額; 狀態(tài)轉(zhuǎn)移方程為 sk1=skxk; 目標(biāo)函數(shù)為 max R=(1-PA)(1-PB）(1PC) 仍采用反向遞推第一階段 :對(duì)機(jī)器 C 撥款的效果 R1(s1，x1)=d1(s1，x1） R0（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 萬(wàn)元,故 s2 2 遞推公式： R2（s2,x2)=d2（s2，x2) R1（s1，x1*) 例：R2(3，2)=d2(3，2) R1