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

..練習題一1、建立優(yōu)化模型應考慮哪些要素"答：決策變量、目標函數(shù)和約束條件。2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停頓準那么。答：針對一般優(yōu)化模型，討論解的可行域，假設存在一點，對于均有那么稱為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代算法的收斂性是指迭代所得到的序列，滿足，那么迭代法收斂；收斂的停頓準那么有，，，，等等。練習題二1、某公司看中了例2.1中廠家所擁有的3種資源R1、R2、和R3，欲出價收購〔可能用于生產(chǎn)附加值更高的產(chǎn)品〕。如果你是該公司的決策者，對這3種資源的收購報價是多少？〔該問題稱為例2.1的對偶問題〕。解：確定決策變量對3種資源報價作為本問題的決策變量。確定目標函數(shù)問題的目標很清楚——"收購價最小〞。確定約束條件資源的報價至少應該高于原生產(chǎn)產(chǎn)品的利潤，這樣原廠家才可能賣。因此有如下線性規(guī)劃問題：*2、研究線性規(guī)劃的對偶理論和方法〔包括對偶規(guī)劃模型形式、對偶理論和對偶單純形法〕。答：略。3、用單純形法求解以下線性規(guī)劃問題：〔1〕；〔2〕解：〔1〕引入松弛變量x4，x5，x6cj→1-11000CB基bx1x2x3x4x5x60x421[1]-21000x532110100x64-101001cj-zj1-11000因檢驗數(shù)σ2<0，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x4作為換出的基變量。cj→1-11000CB基bx1x4x3x4x5x6-1x2211-21000x5110[3]-1100x64-101001cj-zj20-1100因檢驗數(shù)σ3<0，故確定x3為換入非基變量，以x3的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x5作為換出的基變量。cj→1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/31cj-zj7/3032/31/30因檢驗數(shù)σj>0，說明已求得最優(yōu)解：，去除添加的松弛變量，原問題的最優(yōu)解為：?！?〕根據(jù)題意選取x1，x4，x5，為基變量：cj→0-1100CB基bx1x2x3x4x50x121-21000x420[1]-2100x5501101cj-zj0-1100因檢驗數(shù)σ2<0最小，故確定x2為換入非基變量，以x2的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x4作為換出的基變量。cj→0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x5300[3]-11cj-zj00-110因檢驗數(shù)σ3<0最小，故確定x3為換入非基變量，以x1的系數(shù)列的正分量對應去除常數(shù)列，最小比值所在行對應的基變量x5作為換出的基變量。cj→0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31x31001-1/31/3cj-zj0002/31/3因檢驗數(shù)σj>0，說明已求得最優(yōu)解：。8、某地區(qū)有A、B、C三個化肥廠，供給本地甲、乙、丙、丁四個產(chǎn)糧區(qū)。各化肥廠可供給化肥的數(shù)量和各產(chǎn)糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運價如表2-28所示。試制定一個使總運費最少的化肥調(diào)撥方案。表2-SEQ表2-\*ARABIC28運價/產(chǎn)糧(元/噸)區(qū)化肥廠甲乙丙丁各廠供給量/萬噸A158737A2491078A384293各區(qū)需要量/萬噸6633解：設A、B、C三個化肥廠為A1、A2、A3，甲、乙、丙、丁四個產(chǎn)糧區(qū)為B1、B2、B3、B4；cij為由Ai運化肥至Bj的運價，單位是元/噸；xij為由Ai運往Bj的化肥數(shù)量〔i=1,2,3;j=1,2,3,4〕單位是噸；z表示總運費，單位為元，依題意問題的數(shù)學模型為：該題可以用單純形法或matlab自帶工具箱命令〔linprog〕求解。*9、求解以下不平衡運輸問題〔各數(shù)據(jù)表中，方框的數(shù)字為單位價格，框外右側(cè)的一列數(shù)為各發(fā)點的供給量，框底下一行數(shù)是各收點的需求量〕：〔1〕51710要求收點3的需求必須正好滿足。6468032515752050〔2〕51020要求收點1的需求必須由發(fā)點4供給。32410752159601551015解答略。練習題三1、用0.618法求解問題的間為。答：t=0.8115；最小值-0.0886.〔調(diào)用golds.m函數(shù)〕2、求無約束非線性規(guī)劃問題min=的最優(yōu)解解一：由極值存在的必要條件求出穩(wěn)定點：，，，那么由得，，再用充分條件進展檢驗：，，，，，即為正定矩陣得極小點為，最優(yōu)值為-1。解二：目標函數(shù)改寫成min=易知最優(yōu)解為〔1,0,0〕，最優(yōu)值為-1。3、用最速下降法求解無約束非線性規(guī)劃問題。其中，給定初始點。解一：目標函數(shù)的梯度令搜索方向再從出發(fā)，沿方向作一維尋優(yōu)，令步長變量為，最優(yōu)步長為，那么有故令可得求出點之后，與上類似地，進展第二次迭代：令令步長變量為，最優(yōu)步長為，那么有故令可得此時所到達的精度此題最優(yōu)解，練習題四1、石油輸送管道鋪設最優(yōu)方案的選擇問題：考察網(wǎng)絡圖4-6，設A為出發(fā)地，F(xiàn)為目的地，B，C，D，E分別為四個必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設的位置，線段旁的數(shù)字表示鋪設這些管線所需的費用。問如何鋪設管道才能使總費用最??？圖4-SEQ圖4-\*ARABIC6解：第五階段：E1—F4；E2—F3；第四階段：D1—E1

—F7；D2—E2—F5；D3—E1—F5；第三階段：C1—D1—E1

—F12；C2—D2—E2—F10；C3—D2—E2—F8；C4—D3—E1—F9；第二階段：B1—C2—D2—E2—F13；B2—C3—D2—E2—F15；第一階段：A—B1—C2—D2—E2—F17；最優(yōu)解：A—B1—C2—D2—E2—F最優(yōu)值：172、用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：，最優(yōu)值為9。3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃解：用順序算法階段：分成兩個階段，且階段1、2分別對應。決策變量：狀態(tài)變量：分別為第j階段第一、第二約束條件可供分配的右段數(shù)值。由于，可解的，最優(yōu)值為702.92。4、設四個城市之間的公路網(wǎng)如圖4-7。兩點連線旁的數(shù)字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應的最短距離。圖4-SEQ圖4-\*ARABIC7城市公路網(wǎng)解：城市1到城市4路線——1-3-4距離10；城市2到城市4路線——2-4距離8；城市3到城市4路線——3-4距離4。5、某公司打算在3個不同的地區(qū)設置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表4-19所示。試問在各地區(qū)如何設置銷售點可使每月總利潤最大。表4-SEQ表4-\*ARABIC19解：將問題分為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〔sk〕=｛xk|0≤xk≤sk｝階段指標函數(shù)：gk〔xk〕表示xk個銷售點分配給第k個地區(qū)所獲得的利潤；最優(yōu)指標函數(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ū)設置2個銷售點，第2個地區(qū)設置1個銷售點，第3個地區(qū)設置1個銷售點，每月可獲利潤47。6、設某廠方案全年生產(chǎn)某種產(chǎn)品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。生產(chǎn)產(chǎn)品A的生產(chǎn)費用與產(chǎn)品的平方成正比，系數(shù)為0.005。廠有倉庫可存放產(chǎn)品，存儲費為每公斤每季度1元。求最正確的生產(chǎn)安排使年總本錢最小。解：四個季度為四個階段，采用階段編號與季度順序一致。設sk為第k季初的庫存量，那么邊界條件為s1=s5=0設xk為第k季的生產(chǎn)量，設yk為第k季的訂貨量；sk，xk，yk都取實數(shù)，狀態(tài)轉(zhuǎn)移方程為sk+1=sk+xk-yk仍采用反向遞推，但注意階段編號是正向的目標函數(shù)為：第一步：(第四季度)總效果f4(s4,x4)=0.005x42+s4由邊界條件有：s5=s4+x4–y4=0，解得：x4*=1200–s4將x4*代入f4(s4,x4)得：f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季度)總效果f3(s3,x3)=0.005x32+s3+f4*(s4)將s4=s3+x3–500代入f3(s3,x3)得：第三步：(第二、三、四季度)總效果f2(s2,x2)=0.005x22+s2+f3*(s3)將s3=s2+x2700代入f2(s2,x2)得：第四步：(第一、二、三、四季度)總效果f1(s1,x1)=0.005x12+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、某種機器可在上下兩種不同的負荷下進展生產(chǎn)。設機器在高負荷下生產(chǎn)的產(chǎn)量函數(shù)為g=8u1，其中u1為投入生產(chǎn)的機器數(shù)量，年完好率a=0.7；在低負荷下生產(chǎn)的產(chǎn)量函數(shù)為h=5y，其中y為投入生產(chǎn)的機器數(shù)量，年完好率為b=0.9。假定開場生產(chǎn)時完好機器的數(shù)量s1=1000。試問每年如何安排機器在高、低負荷下的生產(chǎn)，使在5年生產(chǎn)的產(chǎn)品總產(chǎn)量最高。解：構造這個問題的動態(tài)規(guī)劃模型：設階段序數(shù)k表示年度。狀態(tài)變量sk為第k年度初擁有的完好機器數(shù)量，同時也是第k?1年度末時的完好機器數(shù)量。決策變量uk為第k年度中分配高負荷下生產(chǎn)的機器數(shù)量，于是sk?uk為該年度中分配在低負荷下生產(chǎn)的機器數(shù)量。這里sk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如sk=0.6，就表示一臺機器在k年度中正常工作時間只占6/10；uk=0.3，就表示一臺機器在該年度只有3/10的時間能在高負荷下工作。狀態(tài)轉(zhuǎn)移方程為：k段允許決策集合為：設為第k年度的產(chǎn)量，那么故指標函數(shù)為：令最優(yōu)值函數(shù)fk(sk)表示由資源量sk出發(fā)，從第k年開場到第5年完畢時所生產(chǎn)的產(chǎn)品的總產(chǎn)量最大值。因而有逆推關系式：從第5年度開場，向前逆推計算。當k=5時，有：因f5是u5的線性單調(diào)增函數(shù)，故得最大解u5*，相應的有：當k=4時，有：故得最大解，u4*=s4，相應的有依此類推，可求得因s1=1000，故：計算結(jié)果說明：最優(yōu)策略為即前兩年應把年初全部完好機器投入低負荷生產(chǎn)，后三年應把年初全部完好機器投入高負荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺。在得到整個問題的最優(yōu)指標函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即從始端向終端遞推計算出每年年初完好機器數(shù)。s1=1000臺，于是可得：8、有一輛最大貨運量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應單位價值如表4-20所示。應如何裝載可使總價值最大？表4-SEQ表4-\*ARABIC20貨物編號i123單位重量〔t〕345單位價值ci456解：利用動態(tài)規(guī)劃的逆序解法求此問題。狀態(tài)轉(zhuǎn)移方程為：該題是三階段決策過程，故可假想存在第四個階段，而，于是動態(tài)規(guī)劃的根本方程為：計算最終結(jié)果為，最大價值為13。9、設有A，B，C三部機器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術問題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計結(jié)果說明，機器A，B，C產(chǎn)生次品的概率分別為pA=30%,PB=40%,PC=20%,而產(chǎn)品必須經(jīng)過三部機器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬元進展技術改造，以便最大限度地提高產(chǎn)品的成品率指標?，F(xiàn)提出如下四種改良方案：方案1：不撥款，機器保持原狀；方案2：加裝監(jiān)視設備，每部機器需款1萬元；方案3：加裝設備，每部機器需款2萬元；方案4：同時加裝監(jiān)視及控制設備，每部機器需款3萬元；采用各方案后，各部機器的次品率如表4-21。表4-SEQ表4-\*ARABIC21ABC不撥款30%40%20%撥款1萬元20%30%10%撥款2萬元10%20%10%撥款3萬元5%10%6%問如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？解：為三臺機器分配改造撥款，設撥款順序為A,B,C，階段序號反向編號為k，即第一階段計算給機器C撥款的效果。設sk為第k階段剩余款，那么邊界條件為s3=5；設xk為第k階段的撥款額；狀態(tài)轉(zhuǎn)移方程為sk-1=sk-xk；目標函數(shù)為maxR=(1-PA)(1-PB)(1-PC)仍采用反向遞推第一階段：對機器C撥款的效果R1(s1,x1)=d1(s1,x1)R0(s0,x0)=d1(s1,x1)x1s10123x1*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第二階段：對機器B,C撥款的效果由于機器A最多只需3萬元，故s22遞推公式：R2(s2,x2)=d2(s2,x2)R1(s1,x1*)