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

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

3、x1x4x3x4x5x6-1x2211-21000x51103-1100x64-101001cj-zj20-1100因檢驗數3<0，故確定x3為換入非基變量，以x3的系數列的正分量對應去除常數列，最小比值所在行對應的基變量x5作為換出的基變量。cj1-11000CB基bx1x2x5x4x5x6-1x28/35/3101/32/301x31/31/301-1/31/300x611/3-4/3001/3-1/31cj-zj7/3032/31/30因檢驗數j>0，表明已求得最優解：，去除添加的松弛變量，原問題的最優解為：。（2）根據題意選取x1，x4，x5，為基變量：cj0-1100CB

4、基bx1x2x3x4x50x121-21000x4201-2100x5501101cj-zj0-1100因檢驗數2<0最小，故確定x2為換入非基變量，以x2的系數列的正分量對應去除常數列，最小比值所在行對應的基變量x4作為換出的基變量。cj0-1100CB基bx1x2x3x4x50x1610-320-1x2201-2100x53003-11cj-zj00-110因檢驗數3<0最小，故確定x3為換入非基變量，以x1的系數列的正分量對應去除常數列，最小比值所在行對應的基變量x5作為換出的基變量。cj0-1100CB基bx1x2x3x4x50x1910011-1x240101/32/31

5、x31001-1/31/3cj-zj0002/31/3因檢驗數j>0，表明已求得最優解：。8、某地區有A、B、C三個化肥廠，供應本地甲、乙、丙、丁四個產糧區。已知各化肥廠可供應化肥的數量和各產糧區對化肥的需要量，以及各廠到各區每噸化肥的運價如表2-28所示。試制定一個使總運費最少的化肥調撥方案。表2- 1運價/ 產糧 (元/噸) 區化肥廠甲乙丙丁各廠供應量/萬噸A158737A2491078A384293各區需要量/萬噸6633解：設A、B、C三個化肥廠為A1、A2、A3，甲、乙、丙、丁四個產糧區為B1、B2、B3、B4；cij為由Ai運化肥至Bj的運價，單位是元/噸；xij為由Ai運往

6、Bj的化肥數量（i=1,2,3;j=1,2,3,4）單位是噸；z表示總運費，單位為元，依題意問題的數學模型為：該題可以用單純形法或matlab自帶工具箱命令（linprog）求解。 *9、求解下列不平衡運輸問題（各數據表中，方框內的數字為單位價格，框外右側的一列數為各發點的供應量，框底下一行數是各收點的需求量）：（1） 5 1 7 10 要求收點3的需求必須正好滿足。 6 4 6 80 3 2 5 15 75 20 50（2） 5 1 0 20 要求收點1的需求必須由發點4供應。 3 2 4 10 7 5 2 15 9 6 0 15 5 10 15解答略。練習題三1、用0.618法求解問題的近

7、似最優解，已知的單谷區間為，要求最后區間精度。答：t=0.8115；最小值-0.0886.（調用golds.m函數） 2、求無約束非線性規劃問題min =的最優解解一：由極值存在的必要條件求出穩定點：，則由得， 再用充分條件進行檢驗：，即為正定矩陣得極小點為，最優值為-1。解二：目標函數改寫成 min =易知最優解為（1,0,0），最優值為-1。3、用最速下降法求解無約束非線性規劃問題。其中，給定初始點。解一：目標函數的梯度令搜索方向再從出發，沿方向作一維尋優，令步長變量為，最優步長為，則有故令可得 求出點之后，與上類似地，進行第二次迭代： 令令步長變量為，最優步長為，則有故令可得 此時所達到

8、的精度本題最優解，練習題四1、石油輸送管道鋪設最優方案的選擇問題：考察網絡圖4-6，設A為出發地，F為目的地，B，C，D，E分別為四個必須建立油泵加壓站的地區。圖中的線段表示管道可鋪設的位置，線段旁的數字表示鋪設這些管線所需的費用。問如何鋪設管道才能使總費用最小？圖4- 1解： 第五階段：E1F 4；E2F 3；第四階段：D1E1 F  7；D2E2F   5；D3E1F   5；第三階段：C1D1E1 F   12；C2D2E2F   10；C3D2E2F  &#

9、160;8；C4D3E1F   9；第二階段：B1C2D2E2F    13； B2C3D2E2F   15；  第一階段：AB1C2D2E2F   17；最優解：AB1C2D2E2F    最優值：172、 用動態規劃方法求解非線性規劃解：，最優值為9。3、用動態規劃方法求解非線性規劃解：用順序算法階段：分成兩個階段，且階段1 、2 分別對應。決策變量：狀態變量：分別為第j 階段第一、第二約束條件可供分配的右段數值。 由于，可解的，最優值為70

10、2.92。4、設四個城市之間的公路網如圖4-7。兩點連線旁的數字表示兩地間的距離。使用迭代法求各地到城市4的最短路線及相應的最短距離。圖4- 2 城市公路網解：城市1到城市4路線1-3-4 距離10；城市2到城市4路線2-4 距離8；城市3到城市4路線3-4 距離4。5、某公司打算在3個不同的地區設置4個銷售點，根據市場部門估計，在不同地區設置不同數量的銷售點每月可得到的利潤如表4-19所示。試問在各地區如何設置銷售點可使每月總利潤最大。 表4- 1解：將問題分為3個階段，k=1，2，3；決策變量xk表示分配給第k個地區的銷售點數；狀態變量為sk表示分配給第k個至第3個地區的銷售點總數；狀態轉

11、移方程：sk+1=skxk，其中s1=4；允許決策集合：Dk（sk）=xk|0xksk階段指標函數：gk（xk）表示xk個銷售點分配給第k個地區所獲得的利潤；最優指標函數fk（sk）表示將數量為sk的銷售點分配給第k個至第3個地區所得到的最大利潤，動態規劃基本方程為：k=3時，k=2時，k=1時，最優解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1個地區設置2個銷售點，第2個地區設置1個銷售點，第3個地區設置1個銷售點，每月可獲利潤47。 6、設某廠計劃全年生產某種產品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產產品A的生產費用與產

12、品的平方成正比，系數為0.005。廠內有倉庫可存放產品，存儲費為每公斤每季度1元。求最佳的生產安排使年總成本最小。解：四個季度為四個階段，采用階段編號與季度順序一致。 設 sk 為第k季初的庫存量，則邊界條件為 s1=s5=0 設 xk 為第k季的生產量，設 yk 為第k季的訂貨量；sk ，xk ，yk 都取實數，狀態轉移方程為 sk+1=sk+xk - yk 仍采用反向遞推，但注意階段編號是正向的目標函數為：第一步：(第四季度) 總效果 f4(s4,x4)=0.005 x42+s4 由邊界條件有： s5= s4 + x4 y4=0，解得：x4*=1200 s4 將x4*代入 f4(s4,x4

13、)得： 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 代入

14、f1(s1,x1) 得：由此回溯：得最優生產庫存方案 x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x4*=900。7、某種機器可在高低兩種不同的負荷下進行生產。設機器在高負荷下生產的產量函數為g=8u1，其中u1為投入生產的機器數量，年完好率a=0.7；在低負荷下生產的產量函數為h=5y，其中y為投入生產的機器數量，年完好率為b=0.9。假定開始生產時完好機器的數量s1=1000。試問每年如何安排機器在高、低負荷下的生產，使在5年內生產的產品總產量最高。解：構造這個問題的動態規劃模型：設階段序數k表示年度。狀態變量sk為第k年度初擁有的完好機器

15、數量，同時也是第k1年度末時的完好機器數量。決策變量uk為第k年度中分配高負荷下生產的機器數量，于是skuk為該年度中分配在低負荷下生產的機器數量。這里sk和uk均取連續變量，它們的非整數值可以這樣理解，如sk=0.6，就表示一臺機器在k年度中正常工作時間只占6/10；uk=0.3，就表示一臺機器在該年度只有3/10的時間能在高負荷下工作。狀態轉移方程為：k段允許決策集合為：設為第k年度的產量，則故指標函數為：令最優值函數fk(sk)表示由資源量sk出發，從第k年開始到第5年結束時所生產的產品的總產量最大值。因而有逆推關系式：從第5年度開始，向前逆推計算。當k=5時，有：因f5是u5的線性單調

16、增函數，故得最大解u5*，相應的有：當k=4時，有：故得最大解，u4*=s4，相應的有依此類推，可求得因s1=1000，故：計算結果表明：最優策略為即前兩年應把年初全部完好機器投入低負荷生產，后三年應把年初全部完好機器投入高負荷生產。這樣所得的產量最高，其最高產量為23700臺。在得到整個問題的最優指標函數值和最優策略后，還需反過來確定每年年初的狀態，即從始端向終端遞推計算出每年年初完好機器數。已知s1=1000臺，于是可得：8、有一輛最大貨運量為10t 的卡車，用以裝載3種貨物，每種貨物的單位重量及相應單位價值如表4-20所示。應如何裝載可使總價值最大？表4- 2貨物編號i123單位重量（t

17、）345單位價值 ci456解：利用動態規劃的逆序解法求此問題。 狀態轉移方程為： 該題是三階段決策過程，故可假想存在第四個階段，而，于是動態規劃的基本方程為：計算最終結果為，最大價值為13 。9、設有 A，B，C 三部機器串聯生產某種產品，由于工藝技術問題，產品常出現次品。統計結果表明，機器 A，B，C產生次品的概率分別為 pA=30%, PB=40%, PC=20%, 而產品必須經過三部機器順序加工才能完成。為了降低產品的次品率，決定撥款 5 萬元進行技術改造，以便最大限度地提高產品的成品率指標。現提出如下四種改進方案：方案1：不撥款，機器保持原狀；方案2：加裝監視設備，每部機器需款 1

18、萬元；方案3：加裝設備，每部機器需款 2 萬元；方案4：同時加裝監視及控制設備，每部機器需款 3 萬元；采用各方案后，各部機器的次品率如表4-21。表4- 3ABC不撥款30%40%20%撥款 1 萬元20%30%10%撥款 2 萬元10%20%10%撥款 3 萬元5%10%6%問如何配置撥款才能使串聯系統的可靠性最大？解：為三臺機器分配改造撥款，設撥款順序為A, B, C，階段序號反向編號為 k，即第一階段計算給機器 C 撥款的效果。 設 sk 為第 k 階段剩余款，則邊界條件為 s3=5； 設 xk 為第 k 階段的撥款額； 狀態轉移方程為 sk-1=sk-xk； 目標函數為 max R=

19、(1-PA)(1-PB)(1-PC) 仍采用反向遞推第一階段 ：對機器 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第二階段 ：對機器 B, C 撥款的效果 由于機器 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 得第二