【正文】 （1）在所有的空格中填上適當?shù)臄?shù)（其中可含參數(shù)a、b）。4. 某房地產(chǎn)公司計劃在一住宅小區(qū)建設5棟不同類型的樓房BBBBB5。 （10分）B1B2B3B4B5A13871511A279101412A36913127解：設每家建筑公司承建2棟樓，虛設一棟樓B6，則有： 矩陣變換有： 1矩陣再變換有： 所以有： 或即：A1承建B1和B3樓；A2承建B2樓；A3承建B4和B5樓。5. 用最速下降法求 ，取初始點為。各作業(yè)班組得到新工人后產(chǎn)量增加量如下表。 （10分） 增加人數(shù)作業(yè)班組012345第一班組第二班組第三班組00016101225141730162132172233解：根據(jù)題意，原問題用動態(tài)規(guī)劃求解模型為：（1）按作業(yè)班組分為3階段，K=（1，2，3，4），k=4為終了階段；（2）xk：第k階段初擁有待分配新工人數(shù)；有：X1={8}，X2={8,7,6,5,4,3}，X3={5,4,3,2,1,0}，X={0}。（4）狀態(tài)轉移方程：； （5）階段指標：見表，如： ；；（6）遞推方程：（7）邊界條件：。 （15分）解：設分別表示（容量，流量，費用），最小費用最大流問題的算法步驟為：（1）給定初始可行流，迭代后得；（2）構造費用有向圖（流增量圖），設中弧得權為： ， 其中的弧可以去掉；（3）求中v1至vn的最小費用路（可擴充路）P；（4）在最小費用路（可擴充路）P上調整流量式中 （5）重復（2）~（4）步，找不到v1至vn的最小費用路（可擴充路）P時，則得到最小費用最大流，迭代結束。種植不同作物的收益（元）主要取決于天氣（見下表），要求：（1）用不確定型決策方法，決定種哪一種作物。 （5分） 自然狀態(tài)策略收益好天氣中等天氣壞天氣A1250001800010000A230000120008000A3200001600012000解：（1）用不確定型決策方法等可能準則： ∴ 樂觀準則： ∴ 悲觀準則： ∴ 后悔值準則：后悔值矩陣為： 則 ∴ （2）用風險型決策方法（最大期望收益）的決策樹為：1△12000　　　△25000　　　△18000　　　△10000　　　△30000　　　△12000　　　△8000　　　△20000　　　△16000　　　好天氣 　　　好天氣 　　　好天氣 　　　中等天氣 　　　中等天氣 　　　中等天氣 　　　壞天氣 　　　壞天氣 　　　壞天氣 　　　A1　　　A2　　　A3　　　16200　　　17700　　　16000　　　17700　　　∴ ，（答題畢）2003級（B）參考答案1. 證明，若線性規(guī)劃問題有兩個不同的最優(yōu)解，則它有無窮多最優(yōu)解。而所以也是線性規(guī)劃問題的最優(yōu)解。2. 有甲、乙、丙三種類型的煤，每種煤的含硫量、發(fā)熱量及價格如下表。 （10分） 類 型含硫量（%）發(fā)熱量（103J/kg）價格（元/t）甲乙丙2024222016解：設每噸混合煤分別使用甲、乙、丙三種煤噸，混合煤的成本為Z。解：（1）當現(xiàn)行解為可行解，且對應的非基變量的檢驗數(shù)均大于0時，LP問題才有唯一最優(yōu)解，即f≥0，b＞0，d＞0。（2）當所有非基變量的檢驗數(shù)都大于等于0，且其中存在一個非基變量xj檢驗數(shù)等于0，而在xj的系數(shù)列向量中有大于0的分量時，有無窮多最優(yōu)解。x3，x4，x6非人工變量；a，e無限制。x3，x4，x6非人工變量；a，e無限制。x3，x4，x6非人工變量；c，e無限制。 （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點。 （10分）解：求解整數(shù)規(guī)劃（max型）的分枝定界法的基本方法步驟有：（1）求解原問題的松弛問題，即不考慮整數(shù)約束的線性規(guī)劃問題；（2）定界，一般令為松弛問題的目標函數(shù)值，為無窮大或明顯的整數(shù)解的目標函數(shù)值；（3）分枝，選非整數(shù)解變量進行分枝，用兩個線性規(guī)劃問題同效表示一個線性規(guī)劃問題；（4）求解并剪枝，求解分枝問題，對無解的問題或目標函數(shù)值小于的問題適時剪掉，不再進行分枝；（5）調整上、下界，將迄今為止最好的整數(shù)解對應的目標函數(shù)值作為，將迄今為止所有未被分枝的問題的目標函數(shù)值作為；（6）當所有分枝均已查明，有=時，即得到原問題的最優(yōu)解，求解過程結束。7. 寫出建立動態(tài)規(guī)劃求解模型的基本步驟。8. 根據(jù)市場預測，某企業(yè)其產(chǎn)品的需求量可能為100、150、200或250萬t，產(chǎn)品生產(chǎn)成本為25元/t，而售價為35元/t。 （10分）解：（1）根據(jù)題意該問題的益損值表為： Sjαi1001502002501001502002501000250150027501000150025010001000150020007501000150020002500 （2）等可能準則： 樂觀準則： 悲觀準則： 后悔值準則：后悔值矩陣為： 則 （答題畢）2004級（A）1 將線性規(guī)劃問題 化為標準型。 （10分）解：將原問題變量重新排列有：. 。只要求迭代一步。的動態(tài)規(guī)劃模型（不必求解）。用動態(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來說，哪些頂點是不可達的。 （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。9 某工廠要制定下年度產(chǎn)品的生產(chǎn)批量計劃，根據(jù)市場調查和市場預測的結果，得到產(chǎn)品市場銷路好、中、工廠采用大批、中批、小批生產(chǎn)可能得到收益值也可以計算出來，見下表。 （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)的可能性也就最大?！?（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銷路好 銷路好 銷路中 銷路中 銷路差 銷路差 中批量生產(chǎn)小批量生產(chǎn)∴ 2004級（B）1 用圖解法求解 （10分）解：用圖解法有：（10,0）x1+x2=1x2=4x1+2x2=10x2543210 1 2 3 4 5 6 7 8 9 10 x1聯(lián)立 解得；2 用表格單純形法求解 （15分）解：原問題標準化為: 用單純形表格迭代有：Cj100bCBXBx1x2x3x40x33510150x4[5]20110σj10000x30[19/5]13/59x112/501/52σj0001/251x2015/193/1945/19x1102/1913/9520/19σj0001/25所以 ；3 寫出線性規(guī)劃問題： 的對偶規(guī)劃。 （15分）解：原問題標準化為：為自由變量。 （10分）解：原問題用圖解法求解過程為：0426486x18x22∴X*=(0,5)T； Z*=406 判斷函數(shù)：的凹凸性。7 有100臺機器分四期使用，每期有兩種任務：任務一高負荷工作，報廢率1/3，收益10；任務二低負荷工作，報廢率1/10，收益7。 （10分）解：(1) 按機器使用周期分為5個階段，第5階段為結束階段，即 K={1，2，3，4，5}；(2) 選xk為k階段初完好的機器數(shù)，有：x1=1000≤x2≤1000≤x3≤1000≤x4≤100(3) 選uk為k階段投入高負荷工作的機器數(shù)，則投入低負荷工作的機器數(shù)為 xkuk，有：0≤u1≤x10≤u2≤x20≤u3≤x30≤u4≤x4(4) 狀態(tài)轉移方程：(5) 階段指標函數(shù)：(6) 遞推方程：