【文章內(nèi)容簡介】 x3，x4，x6非人工變量；a，c，e無限制。（2）當(dāng)所有非基變量的檢驗數(shù)都大于等于0，且其中存在一個非基變量xj檢驗數(shù)等于0，而在xj的系數(shù)列向量中有大于0的分量時，有無窮多最優(yōu)解。所以f≥0，b=0，d≥0或f≥0，b≥0，d=0，c＞0。x3，x4，x6非人工變量；a，e無限制。（3）當(dāng)f≥0時現(xiàn)行解為基可行解，當(dāng)b＞0，d＜0，c＜0時LP的目標函數(shù)無界，所以有f≥0，b＞0，d＜0，c＜0。x3，x4，x6非人工變量；a，e無限制。（4）因是可行解，所以有f≥0；非最優(yōu)解且只有x1可以進基，所以有b＜0，d≥0；只有x6可以出基，所以有，故參數(shù)應(yīng)滿足：f≥0，b＜0，d≥0。x3，x4，x6非人工變量；c，e無限制。4. 分別用圖解法和單純形法求解線性規(guī)劃問題，并對照指出單純形法的每步迭代相當(dāng)于圖解法中可行域的哪一個頂點。 （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所以：；其中：表一對應(yīng)圖中O點；表二對應(yīng)圖中D點；表三對應(yīng)圖中C點。5. 寫出求解整數(shù)規(guī)劃（max型）的分枝定界法的基本方法步驟。 （10分）解：求解整數(shù)規(guī)劃（max型）的分枝定界法的基本方法步驟有：（1）求解原問題的松弛問題，即不考慮整數(shù)約束的線性規(guī)劃問題；（2）定界，一般令為松弛問題的目標函數(shù)值，為無窮大或明顯的整數(shù)解的目標函數(shù)值；（3）分枝，選非整數(shù)解變量進行分枝，用兩個線性規(guī)劃問題同效表示一個線性規(guī)劃問題；（4）求解并剪枝，求解分枝問題，對無解的問題或目標函數(shù)值小于的問題適時剪掉，不再進行分枝；（5）調(diào)整上、下界，將迄今為止最好的整數(shù)解對應(yīng)的目標函數(shù)值作為，將迄今為止所有未被分枝的問題的目標函數(shù)值作為；（6）當(dāng)所有分枝均已查明，有=時，即得到原問題的最優(yōu)解，求解過程結(jié)束。6. 判斷下述函數(shù)的凹凸性： （10分）解：因 ； 有： a11=0 ； A2==4﹤0； A3==8﹤0即函數(shù)的海賽矩陣為不定矩陣，故為非凸非凹函數(shù)。7. 寫出建立動態(tài)規(guī)劃求解模型的基本步驟。 （10分）解：建立動態(tài)規(guī)劃求解模型的基本步驟為：（1）按問題內(nèi)容劃分階段，K=（1，2，…，n），k=n為終了階段；（2）確定狀態(tài)變量xk和允許狀態(tài)集合Xk；（3）確定決策變量uk和允許決策集合Uk；（4）寫出狀態(tài)轉(zhuǎn)移方程：； （5）明確階段指標； （6）確定遞推方式和遞推方程，如逆推方程為：（7）明確邊界條件，如，或等。8. 根據(jù)市場預(yù)測，某企業(yè)其產(chǎn)品的需求量可能為100、150、200或250萬t，產(chǎn)品生產(chǎn)成本為25元/t，而售價為35元/t。假設(shè)產(chǎn)品生產(chǎn)后不能外銷其價值為零，要求：（1）寫出該問題的益損值表； （10分）（2）分別用等可能準則、樂觀準則、悲觀準則、后悔值準則，確定企業(yè)最優(yōu)生產(chǎn)數(shù)量。 （10分）解：（1）根據(jù)題意該問題的益損值表為： 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目標函數(shù)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 試建立求解問題： . 均是非負整數(shù)。的動態(tài)規(guī)劃模型（不必求解）。 （10分）解：原問題可改寫為：. 均是非負整數(shù)。用動態(tài)規(guī)劃求解時，其模型為：（1）按變量分為3階段，K=（1，2，3，4），k=4為終了階段；（2）xk：各階段得狀態(tài)變量為：x1，x2，x3 ，設(shè)：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)轉(zhuǎn)移方程：x2=x1u1=3u1 ，x3=x2u2（5）階段指標：，（6）遞推方程：（7）邊界條件：8 在圖中用雙標號法求從v1到其它頂點的最短路和最短距離，并指出對v1來說，哪些頂點是不可達的?；∵厰?shù)字是該弧的長度。 （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 某工廠要制定下年度產(chǎn)品的生產(chǎn)批量計劃，根據(jù)市場調(diào)查和市場預(yù)測的結(jié)果，得到產(chǎn)品市場銷路好、中、工廠采用大批、中批、小批生產(chǎn)可能得到收益值也可以計算出來，見下表。現(xiàn)在要求通過決策分析，合理地確定生產(chǎn)批量，使企業(yè)獲得的收益最大。 （10分） 自然狀態(tài)sj方案di收益銷路好s1銷路中s2銷路差s3p(s1)=p(s2)=p(s3)=大批生產(chǎn) d120128中批生產(chǎn) d2161610小批生產(chǎn) d3121212解：（1）最大可能準則由表可以看出，自然狀態(tài)s2的概率p(s2)=，因此產(chǎn)品的市場銷路中(s2)的可能性也就最大。于是就考慮按照這種市場銷路決策，通過比較可知，企業(yè)采取中批生產(chǎn)收益最大，所以d2是最優(yōu)決策方案?！?（2）最大期望值準則 自然狀態(tài)sj方案di收益E(di)銷路好s1銷路中s2銷路差s3p(s1)=p(s2)=p(s3)=大批生產(chǎn) d120128中批生產(chǎn) d2161610小批生產(chǎn) d3121212∴ （3）決策樹法決策樹如圖所示：決策△12△20△12△8△16△16△10△12△12銷路好 銷路中 銷路差 大批量生產(chǎn)d1d2d3銷路