【文章內容簡介】 x3，x4，x6非人工變量；a，c，e無限制。（2）當所有非基變量的檢驗數都大于等于0，且其中存在一個非基變量xj檢驗數等于0，而在xj的系數列向量中有大于0的分量時，有無窮多最優(yōu)解。所以f≥0，b=0，d≥0或f≥0，b≥0，d=0，c＞0。x3，x4，x6非人工變量；a，e無限制。（3）當f≥0時現(xiàn)行解為基可行解，當b＞0，d＜0，c＜0時LP的目標函數無界，所以有f≥0，b＞0，d＜0，c＜0。x3，x4，x6非人工變量；a，e無限制。（4）因是可行解，所以有f≥0；非最優(yōu)解且只有x1可以進基，所以有b＜0，d≥0；只有x6可以出基，所以有，故參數應滿足：f≥0，b＜0，d≥0。x3，x4，x6非人工變量；c，e無限制。4. 分別用圖解法和單純形法求解線性規(guī)劃問題，并對照指出單純形法的每步迭代相當于圖解法中可行域的哪一個頂點。 （20分） 解：用圖解法有：有；用表格單純形法求解有：原模型標準化為： Cj21000bCBXBx1x2x3x4x50x30110030x43*1010120x5110015σj2100000x30110032 x111/301/3041x502/3*01/311σj01/302/3080x30011/23/23/22x21001/21/27/21x10101/23/23/2σj0001/21/217/2所以：；其中：表一對應圖中O點；表二對應圖中D點；表三對應圖中C點。5. 寫出求解整數規(guī)劃（max型）的分枝定界法的基本方法步驟。 （10分）解：求解整數規(guī)劃（max型）的分枝定界法的基本方法步驟有：（1）求解原問題的松弛問題，即不考慮整數約束的線性規(guī)劃問題；（2）定界，一般令為松弛問題的目標函數值，為無窮大或明顯的整數解的目標函數值；（3）分枝，選非整數解變量進行分枝，用兩個線性規(guī)劃問題同效表示一個線性規(guī)劃問題；（4）求解并剪枝，求解分枝問題，對無解的問題或目標函數值小于的問題適時剪掉，不再進行分枝；（5）調整上、下界，將迄今為止最好的整數解對應的目標函數值作為，將迄今為止所有未被分枝的問題的目標函數值作為；（6）當所有分枝均已查明，有=時，即得到原問題的最優(yōu)解，求解過程結束。6. 判斷下述函數的凹凸性： （10分）解：因 ； 有： a11=0 ； A2==4﹤0； A3==8﹤0即函數的海賽矩陣為不定矩陣，故為非凸非凹函數。7. 寫出建立動態(tài)規(guī)劃求解模型的基本步驟。 （10分）解：建立動態(tài)規(guī)劃求解模型的基本步驟為：（1）按問題內容劃分階段，K=（1，2，…，n），k=n為終了階段；（2）確定狀態(tài)變量xk和允許狀態(tài)集合Xk；（3）確定決策變量uk和允許決策集合Uk；（4）寫出狀態(tài)轉移方程：； （5）明確階段指標； （6）確定遞推方式和遞推方程，如逆推方程為：（7）明確邊界條件，如，或等。8. 根據市場預測，某企業(yè)其產品的需求量可能為100、150、200或250萬t，產品生產成本為25元/t，而售價為35元/t。假設產品生產后不能外銷其價值為零，要求：（1）寫出該問題的益損值表； （10分）（2）分別用等可能準則、樂觀準則、悲觀準則、后悔值準則，確定企業(yè)最優(yōu)生產數量。 （10分）解：（1）根據題意該問題的益損值表為： Sjαi1001502002501001502002501000250150027501000150025010001000150020007501000150020002500 （2）等可能準則： 樂觀準則： 悲觀準則： 后悔值準則：后悔值矩陣為： 則 （答題畢）2004級（A）1 將線性規(guī)劃問題 化為標準型。 （10分）解：原模型標準化為： 2 用圖解法求解 （10分）解：用圖解法有：（20/19,45/19）（2,0）3x1+5x2=15x2543210 1 2 3 4 5 x15x1+2x2=10該問題有無窮多最優(yōu)解,聯(lián)立 解得；聯(lián)立 解得；所以 ；3 用單純形法求解 （15分）解：原問題標準化為 用表格單純形法求解有：Cj121000bCBXBx1x2x3x4x5x60x4112100100x521401080x61[2]40014σj12100000x43/200101/280x53/20[2]011/2102x21/212001/22σj00300140x43/200101/281x33/40101/21/452x211001112σj9/40003/27/419所以有：X*=(x1,x2,x3,x4,x5,x6)T=(0,12,5,8,0,0)T；Z′*=19還原為原問題有：X*=(0,12,5,8)T；Z*=194 用對偶單純形法求解線性規(guī)劃問題： （15分）解：用對偶單純形法求解有：Cj1100bCBXBx1x2x3x40x3211040x417*017σj110000x313/7*011/731x21/7101/71σj6/7001/711x1107/131/1321/131x2011/132/1310/13σj006/131/1331/13∴ 規(guī)劃問題最優(yōu)解為 X*=(21/13，10/13)T；Z*=31/135 用隱枚舉法求解下列01規(guī)劃問題. 。 （10分）解：將原問題變量重新排列有：. 。枚舉過程如下表：序號X=(x2,x4,x3,x1)T閥值約束1約束2約束3目標函數0(0,0,0,0)T√1(0,0,0,1)T2(0,0,1,0)T√3(0,0,1,1)T4(0,1,0,0)T4√√√45(0,1,0,1)T6(0,1,1,0)T7(0,1,1,1)T8(1,0,0,0)T9(1,0,0,1)T10(1,0,1,0)T11(1,0,1,1)T12(1,1,0,0)T13(1,1,0,1)T14(1,1,1,0)T15(1,1,1,1)T所以：X*=(x2,x4,x3,x1)T=(0,1,0,0)T Z*=4還原有：X*=(x1,x2,x3,x4)T=(0,0,0,1)T Z*=46 用黃金分割法求解：的極小點。只要求迭代一步。 （10分）解：（1） 因 所以舍去區(qū)間（，10]7 試建立求解問題： . 均是非負整數。的動態(tài)規(guī)劃模型（不必求解）。 （10分）解：原問題可改寫為：. 均是非負整數。用動態(tài)規(guī)劃求解時，其模型為：（1）按變量分為3階段，K=（1，2，3，4），k=4為終了階段；（2）xk：各階段得狀態(tài)變量為：x1，x2，x3 ，設：x3 =u3 ，x2=x3+u2， x1=x2+u1=3即u3= x3，0≤u2≤x2 ，0≤u1≤x1=3有X3={0，1，2，3}，X2={0，1，2，3}，X1={3}（3）uk：U3={x3}，U2={0，1，2，…，x2}，U1={0，1，2，3}（4）狀態(tài)轉移方程：x2=x1u1=3u1 ，x3=x2u2（5）階段指標：，（6）遞推方程：（7）邊界條件：8 在圖中用雙標號法求從v1到其它頂點的最短路和最短距離，并指出對v1來說，哪些頂點是不可達的?；∵厰底质窃摶〉拈L度。 （10分）1267634433v8v7v6v5v4v3v14v21解：標號過程如下：(7,v5)(4,v1)(3,v1)(1,v1)(0,v1)16176344323v8v7v6v5v4v3v14v2(10,v6)從v1到其它頂點的最短路和最短距離分別為：v1→v2 最短路 v1→v2 最短距離 4；v1→v3 無最短路；v1→v4 無最短路；v1→v5 最短路 v1→v5 最短距離 1；v1→v6 最短路 v1→v5→v6 最短距離 7；v1→v7 最短路 v1→v7 最短距離 3；v1→v8 最短路 v1→v5→v6→v8 最短距離 10。對v1來說，頂點vv4是不可達的。9 某工廠要制定下年度產品的生產批量計劃，根據市場調查和市場預測的結果，得到產品市場銷路好、中、工廠采用大批、中批、小批生產可能得到收益值也可以計算出來，見下表?，F(xiàn)在要求通過決策分析，合理地確定生產批量，使企業(yè)獲得的收益最大。 （10分） 自然狀態(tài)sj方案di收益銷路好s1銷路中s2銷路差s3p(s1)=p(s2)=p(s3)=大批生產 d120128中批生產 d2161610小批生產 d3121212解：（1）最大可能準則由表可以看出，自然狀態(tài)s2的概率p(s2)=，因此產品的市場銷路中(s2)的可能性也就最大。于是就考慮按照這種市場銷路決策，通過比較可知，企業(yè)采取中批生產收益最大，所以d2是最優(yōu)決策方案?！?（2）最大期望值準則 自然狀態(tài)sj方案di收益E(di)銷路好s1銷路中s2銷路差s3p(s1)=p(s2)=p(s3)=大批生產 d120128中批生產 d2161610小批生產 d3121212∴ （3）決策樹法決策樹如圖所示：決策△12△20△12△8△16△16△10△12△12銷路好 銷路中 銷路差 大批量生產d1d2d3銷路