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

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

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

3、4x3x4x5x6-1x2211-21000x51103-1100x64-101001cj-zj20-1100因檢驗數(shù)30，表明已求得最優(yōu)解：，去除添加的松弛變量，原問題的最優(yōu)解為：。（2）根據(jù)題意選取x1，x4，x5，為基變量：cj0-1100CB基bx1x2x3x4x50x121-21000x4201-2100x5501101cj-zj0-1100因檢驗數(shù)20最小，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應(yīng)去除常數(shù)列，最小比值所在行對應(yīng)的基變量x4作為換出的基變量。cj0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x53003-11cj-zj

4、00-110因檢驗數(shù)30，表明已求得最優(yōu)解：。8、某地區(qū)有A、B、C三個化肥廠，供應(yīng)本地甲、乙、丙、丁四個產(chǎn)糧區(qū)。已知各化肥廠可供應(yīng)化肥的數(shù)量和各產(chǎn)糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運(yùn)價如表2-28所示。試制定一個使總運(yùn)費(fèi)最少的化肥調(diào)撥方案。表2- 1運(yùn)價/ 產(chǎn)糧 (元/噸) 區(qū)化肥廠甲乙丙丁各廠供應(yīng)量/萬噸A158737A2491078A384293各區(qū)需要量/萬噸6633解：設(shè)A、B、C三個化肥廠為A1、A2、A3，甲、乙、丙、丁四個產(chǎn)糧區(qū)為B1、B2、B3、B4；cij為由Ai運(yùn)化肥至Bj的運(yùn)價，單位是元/噸；xij為由Ai運(yùn)往Bj的化肥數(shù)量（i=1,2,3;j=1,2,3,4

5、）單位是噸；z表示總運(yùn)費(fèi)，單位為元，依題意問題的數(shù)學(xué)模型為：該題可以用單純形法或matlab自帶工具箱命令（linprog）求解。 *9、求解下列不平衡運(yùn)輸問題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價格，框外右側(cè)的一列數(shù)為各發(fā)點的供應(yīng)量，框底下一行數(shù)是各收點的需求量）：（1） 5 1 7 10 要求收點3的需求必須正好滿足。 6 4 6 80 3 2 5 15 75 20 50（2） 5 1 0 20 要求收點1的需求必須由發(fā)點4供應(yīng)。 3 2 4 10 7 5 2 15 9 6 0 15 5 10 15解答略。練習(xí)題三1、用0.618法求解問題的近似最優(yōu)解，已知的單谷區(qū)間為，要求最后區(qū)間精度。答：

6、t=0.8115；最小值-0.0886.（調(diào)用golds.m函數(shù)） 2、求無約束非線性規(guī)劃問題min =的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點：，則由得， 再用充分條件進(jìn)行檢驗：，即為正定矩陣得極小點為，最優(yōu)值為-1。解二：目標(biāo)函數(shù)改寫成 min =易知最優(yōu)解為（1,0,0），最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。其中，給定初始點。解一：目標(biāo)函數(shù)的梯度令搜索方向再從出發(fā)，沿方向作一維尋優(yōu)，令步長變量為，最優(yōu)步長為，則有故令可得 求出點之后，與上類似地，進(jìn)行第二次迭代： 令令步長變量為，最優(yōu)步長為，則有故令可得 此時所達(dá)到的精度本題最優(yōu)解，練習(xí)題四1、石油輸送管道鋪設(shè)最優(yōu)

7、方案的選擇問題：考察網(wǎng)絡(luò)圖4-6，設(shè)A為出發(fā)地，F(xiàn)為目的地，B，C，D，E分別為四個必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設(shè)的位置，線段旁的數(shù)字表示鋪設(shè)這些管線所需的費(fèi)用。問如何鋪設(shè)管道才能使總費(fèi)用最??？圖4- 1解：第五階段：E1F 4；E2F 3；第四階段：D1E1F 7；D2E2F 5；D3E1F 5；第三階段：C1D1E1F 12；C2D2E2F 10；C3D2E2F 8；C4D3E1F 9；第二階段：B1C2D2E2F 13； B2C3D2E2F 15；第一階段：AB1C2D2E2F 17；最優(yōu)解：AB1C2D2E2F最優(yōu)值：172、 用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：，最優(yōu)

8、值為9。3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：用順序算法階段：分成兩個階段，且階段1 、2 分別對應(yīng)。決策變量：狀態(tài)變量：分別為第j 階段第一、第二約束條件可供分配的右段數(shù)值。 由于，可解的，最優(yōu)值為702.92。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到城市4路線3-4 距離4。5、某公司打算在3個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設(shè)置不同數(shù)量的銷售點每月可得到的利潤如表4-19所示。試

9、問在各地區(qū)如何設(shè)置銷售點可使每月總利潤最大。 表4- 1解：將問題分為3個階段，k=1，2，3；決策變量xk表示分配給第k個地區(qū)的銷售點數(shù)；狀態(tài)變量為sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中s1=4；允許決策集合：Dk（sk）=xk|0xksk階段指標(biāo)函數(shù)：gk（xk）表示xk個銷售點分配給第k個地區(qū)所獲得的利潤；最優(yōu)指標(biāo)函數(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ū)設(shè)置2個銷售點，第2個

10、地區(qū)設(shè)置1個銷售點，第3個地區(qū)設(shè)置1個銷售點，每月可獲利潤47。 6、設(shè)某廠計劃全年生產(chǎn)某種產(chǎn)品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產(chǎn)產(chǎn)品A的生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0.005。廠內(nèi)有倉庫可存放產(chǎn)品，存儲費(fèi)為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。解：四個季度為四個階段，采用階段編號與季度順序一致。 設(shè) sk 為第k季初的庫存量，則邊界條件為 s1=s5=0 設(shè) xk 為第k季的生產(chǎn)量，設(shè) yk 為第k季的訂貨量；sk ，xk ，yk 都取實數(shù)，狀態(tài)轉(zhuǎn)移方程為 sk+1=sk+xk - yk 仍采用反向遞推，但注意階段編號是正

11、向的目標(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,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 -

12、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； 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。假定開始

13、生產(chǎn)時完好機(jī)器的數(shù)量s1=1000。試問每年如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：構(gòu)造這個問題的動態(tài)規(guī)劃模型：設(shè)階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機(jī)器數(shù)量，同時也是第k1年度末時的完好機(jī)器數(shù)量。決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是skuk為該年度中分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。這里sk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如sk=0.6，就表示一臺機(jī)器在k年度中正常工作時間只占6/10；uk=0.3，就表示一臺機(jī)器在該年度只有3/10的時間能在高負(fù)荷下工作。狀態(tài)轉(zhuǎn)移方程為：k段允許決策集合為：設(shè)為第k年度的產(chǎn)量，

14、則故指標(biāo)函數(shù)為：令最優(yōu)值函數(shù)fk(sk)表示由資源量sk出發(fā)，從第k年開始到第5年結(jié)束時所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆推關(guān)系式：從第5年度開始，向前逆推計算。當(dāng)k=5時，有：因f5是u5的線性單調(diào)增函數(shù)，故得最大解u5*，相應(yīng)的有：當(dāng)k=4時，有：故得最大解，u4*=s4，相應(yīng)的有依此類推，可求得因s1=1000，故：計算結(jié)果表明：最優(yōu)策略為即前兩年應(yīng)把年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)器投入高負(fù)荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺。在得到整個問題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即從始端向終端遞推計算出每年年初完好機(jī)器數(shù)。

15、已知s1=1000臺，于是可得：8、有一輛最大貨運(yùn)量為10t 的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)單位價值如表4-20所示。應(yīng)如何裝載可使總價值最大？表4- 2貨物編號i123單位重量（t）345單位價值 ci456解：利用動態(tài)規(guī)劃的逆序解法求此問題。 狀態(tài)轉(zhuǎn)移方程為： 該題是三階段決策過程，故可假想存在第四個階段，而，于是動態(tài)規(guī)劃的基本方程為：計算最終結(jié)果為，最大價值為13 。9、設(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%, PC=20%, 而產(chǎn)品必須經(jīng)過三部機(jī)器

16、順序加工才能完成。為了降低產(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：同時加裝監(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，階段序號反向編號為

17、k，即第一階段計算給機(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) 仍采用反向遞推第一階段 ：對機(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.

18、94第二階段 ：對機(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 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第三階段 ：對機(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.608