武漢科技大學(xué)本科歷年運籌學(xué)試題

.z.2002級〔A〕參考答案寫出下述線性規(guī)劃模型的標準型?！?0分〕解：令原問題標準化為：2.有線性規(guī)劃模型：〔10分〕〔1〕用圖解法求解；〔2〕用單純形法求解；〔3〕指出每個單純形表的可行域頂點。解：〔1〕用圖解法求解；∴X*=〔1，1/2〕T；Z*=35/2〔2〕用單純形法求解；原模型標準化為：那么求解過程為：Cj-10-500bCBXBx1x2x3x400x3x434105*20198σj-10-50000-10x3x1014/51-3/512/501/524/58/5σj0-10216-5-10x2x1015/14-3/1410-1/72/73/21σj005/1425/1435/2T0T1T2∴X*=〔1，1/2〕T；Z*=35/2〔3〕指出每個單純形表的可行域頂點。T0表對應(yīng)O點；T1表對應(yīng)B點；T2表對應(yīng)A點，也是最優(yōu)點。3.求解：〔10分〕解：原問題標準化為：用對偶單純形法求解為：Cj52400bCBXBx1x2x3x4x500x4x5-3-1-210-6-3*-501-4-10σj52400002x4x2-1*0-1/31-1/3215/30-1/3-2/310/3σj102/302/320/3-5-10x1x2101/3-11/30112-12/32σj001/311/322/3∴X*=〔2/3，2，0〕T；Z*=22/3〔注：用大M法、兩階段法求解均可〕4.寫出線性規(guī)劃問題：的對偶規(guī)劃?！?0分〕解：原問題的對偶規(guī)劃為：5.有一最小化指派問題的系數(shù)矩陣如下，試求其最優(yōu)解?！?0分〕解：用匈牙利算法求解為：變換后：-5再變換為：再變換：∴Z*=286.寫出函數(shù)的梯度和海賽矩陣，并判斷其凹凸性?！?0分〕解：的梯度矩陣為：的海賽矩陣為：這里H矩陣的各階主子式均大于0，所以為嚴格凸函數(shù)。7.某廠有4臺設(shè)備，擬分給3個用戶〔工廠〕使用，各用戶利用設(shè)備提供的盈利如下表。問如何分配設(shè)備才能使總盈利最大？試建立其動態(tài)規(guī)劃求解模型〔可不求解〕?！?0分〕用戶設(shè)備臺數(shù)12301234046770256803578解：根據(jù)題意，原問題用動態(tài)規(guī)劃求解模型為：按用戶分為3階段，K=〔1，2，3，4〕，k=4為終了階段；xk：第k階段初擁有待分配設(shè)備臺數(shù)；x1=4，0≤x2≤4，0≤x3≤4，x4=0；uk：第k階段分配給第k用戶的設(shè)備數(shù)，有：U1={0,1,2,3,4}，U2={0,1,2,…,x2}，U3={x3};狀態(tài)轉(zhuǎn)移方程：；階段指標：見表，如：；；遞推方程：邊界條件：。v6v5v4v3v6v5v4v32,25,33,01,02,25,24,33,3v1v2證明：對原流圖用標號法找可擴大路有：vv6v5v4v32,25,33,01,02,25,24,33,3v1v2(-，(-，∞)(v(v1,3)標號過程進展不下去，即不存在v1-v6的可擴大路，根據(jù)可擴大路定理，圖示流即為最大流,maxQ=5。9.以下圖為求至的最小費用最大流時得到的某一流圖，弧邊數(shù)字為，試構(gòu)造其費用有向圖〔流增量圖〕?！?0分〕v14,4,1v37,4,6v58,5,43,0,22,0,35,5,2v2v46,5,1解：由原流圖可作出其費用有向圖為：v1-v3v5-6-4423-2-1v2v410.某商行夏季訂購一批西瓜，根據(jù)以往的經(jīng)歷，西瓜銷售量可能為10000、15000、20000、25000kg。假瓜售價為0.35元/kg，商行支出本錢為0.25元/kg。〔1〕建立益損矩陣；〔3分〕〔2〕?！?分〕解:〔1〕原問題的益損矩陣為；αiSj10000150002000025000100001500020000250001000100010001000-250150015001500-150025020002000-2750-10007502500〔2〕悲觀準那么：∴樂觀準那么：∴等可能準那么：∴懊悔值準那么：懊悔值矩陣為：那么∴〔答題畢〕2002級〔B〕參考答案1.求解線性規(guī)劃問題：的最優(yōu)解?！?5分〕解：圖解過程如下：44321432102.寫出下述線性規(guī)劃的對偶規(guī)劃。〔15分〕；無限制。解：對偶規(guī)劃為MaxZd=-7w1+14w2+3w3s.t.w1+6w2+28w3≤52w1-3w2+17w3≤-6-w1+w2-4w3=7-w1-7w2-2w3=4w1無限制，w2，w3≥0。3.某一求目標函數(shù)極小值的線性規(guī)劃問題，用單純形法求解時得到某一步的單純形表如下。問a1、a2、a3、c、d各為何值以及變量x屬哪一類性質(zhì)變量時，〔1〕現(xiàn)有的解為唯一最優(yōu)解；〔2〕現(xiàn)有解為最優(yōu)，但最優(yōu)解有無窮多個；〔3〕存在可行解，但目標函數(shù)無界；〔4〕此線性規(guī)劃問題無可行解。〔15分〕基變量x1x2x3x4x5bx3x4x5-13100a14010a2a300141dcj-zjc2000解：〔1〕d≥0，c＞0，x3，x4，x5為非人工變量；〔2〕d≥0，c=0，a1，a2中至少一個大于零，x3，x4，x5為非人工變量；〔3〕d≥0，c＜0，a1≤0，a2≤0，x3，x4，x5均為非人工變量；〔4〕d＞0，c＞0，a1＞0，a2≤0，a3=0，x5為人工變量。4.用黃金分割法求解單變量函數(shù)尋優(yōu)問題時，每迭代一次，尋優(yōu)區(qū)間縮小多少倍？假設(shè)要將區(qū)間縮小至原區(qū)間的10%以下，那么至少要多少次迭代？〔10分〕解：用黃金分割法求解單變量函數(shù)尋優(yōu)問題時，每迭代一次，尋優(yōu)區(qū)間是原區(qū)間的0.618倍。經(jīng)n次迭代后，區(qū)間長度為：sn=0.618ns0。假設(shè)要將區(qū)間縮小至原區(qū)間的10%以下，即sn/s0≤0.1，那么迭代次數(shù)≥ln0.1/ln0.618=4.78。所以假設(shè)要將區(qū)間縮小至原區(qū)間的10%以下，那么至少要5次迭代。5.某人外出旅行，需將五件物品裝入包裹，但包裹總重量不超過13kg。物品重量及價值如表。問如何裝這些物品使整個包裹價值最大？〔15分〕〔只建模，可不求解〕物品重量〔kg〕價值〔元〕ABCDE7543194320.5解：用動態(tài)規(guī)劃求解時，其模型為：1.按物品類別分為5階段，K=〔1,2,3,4,5,6〕，k=6為終了階段；2.xk：k階段的狀態(tài)變量，即裝第k項物品前剩余重量；有X1={13}；X2={6,13}；X3={1,3,6,8,13}；X4={0,1,2,3,4,5,6,8,9,13}；X5={0,1,2,3,4,5,6,7,8,9,10,134}；X6={0}3.uk：k階段的決策變量，即裝第k類物品的數(shù)量；U1={0,1…,[x1/7]}；U2={0,1,2…,[x2/5]}；U3={0,1,2,…,[x3/4]}；U4={0,1…,[x4/3]}；U5={0,1,2…,[x5/1]}4.狀態(tài)轉(zhuǎn)移方程：5.階段指標見表，；6.遞推方程〔逆推〕：7.邊界條件：6.證明以下圖所示s-t流為最大流?；∵厰?shù)字為〔〕〔15分〕21,2121,2124,2436,027,030，3054，3078，5712，1260，5445，3375，4533，042，3069，57①③②⑥④⑦⑤ts證明：對原流圖用標號法找增廣鏈有30，3054，3024,24〔+vs，12〕①③⑤24,2442，3060，5427,036,027,036,0〔-，∞〕s〔+v4，12〕⑥t21,2175，4521,2169，57 33，045，33〔+vs，12〕②④⑦78，57〔+v2，12〕12，12標號過程進展不下去，即不存在s-t增廣鏈，根據(jù)增廣鏈定理，圖示s-t流即為最大流。7.某決策問題的收益矩陣D為：D=分別用樂觀法、悲觀法、等可能法和懊悔值法確定其最優(yōu)決策?！?5分〕解：樂觀準那么：∴悲觀準那么：∴等可能準那么：∴懊悔值準那么：懊悔值矩陣為：那么∴解題畢。2003級〔A〕參考答案1.某晝夜效勞的公交線路每天各時間所需司機和乘務(wù)人員數(shù)如下表。設(shè)司機和乘務(wù)人員分別在各時間段一開場時上班，并連續(xù)工作8小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又使司機和乘務(wù)人員配備最少？試建立求解該問題的模型〔可不求解〕?！?0分〕班次123456時間所需人數(shù)607060502030解：設(shè)表示第班次開場上班的司機和乘務(wù)人員數(shù)〔〕，那么有：2.有線性規(guī)劃模型：〔1〕用單純形法求解；〔10分〕〔2〕寫出其對偶問題；〔5分〕〔3〕求解對偶問題。〔5分〕解：〔1〕用單純形法求解：原模型標準化為：那么求解過程為：Cj-3-2000bCBXBx1x2x3x4x50x3-1210040x432010120x51*-10013σj-3-200000x30110170x405*01-33-3x11-10013σj0-500390x3001-1/58/5*32/5-2x20101/5-3/53/5-3x11001/52/518/5σj00010120x5005/8-1/814-2x2013/81/803-3x110-1/41/402σj0001012∴該問題有無窮多最優(yōu)解；Z*=12〔2〕其對偶問題為：〔3〕用對偶單純形法求解對偶問題有：Cj412300bCBYBy1y2y3y4y50y41-3-1*10-30y5-2-2101-2σj41230000y3-131-1030y5-1-5*011-5σj73030-90y3-8/501-2/53/50-2y21/510-1/5-1/51σj32/50018/53/5-12∴對偶問題最優(yōu)解為Y*=(0,1,0)T；W*=123.線性規(guī)劃的目標函數(shù)是，在用標準的單純形法迭代過程中，得到下表，其中a，b是常數(shù)，局部數(shù)據(jù)有缺損。Cj-2-5-8000bCBXBx1x2x3x4x5x6x603020x2a1/2bx4-2-118σj2〔1〕在所有的空格中填上適當?shù)臄?shù)〔其中可含參數(shù)a、b〕?！?分〕〔2〕判斷在什么情況下此解為最優(yōu)解？〔5分〕解：〔1〕如下表Cj-2-5-8000bCBXBx1x2x3x4x5x60x600300120-5x2a1201/20b0x4-20-11108σj-2+5a0205/20〔2〕當時，表中解為最優(yōu)解。4.某房地產(chǎn)公司方案在一住宅小區(qū)建立5棟不同類型的樓房B1、B2、B3、B4、B5。由3家建筑公司A1、A2、A3進展投標，允許每家建筑公司可承建1~2棟樓，通過投標得出建筑公司Ai對新樓Bj的預(yù)算費用Cij如下表，求使總費用最少的分配方案?！?0分〕B1B2B3B4B5A13871511A279101412A36913127解：設(shè)每家建筑公司承建2棟樓，虛設(shè)一棟樓B6，那么有：矩陣變換有：-1矩陣再變換有：所以有：或即：A1承建B1和B3樓；A2承建B2樓；A3承建B4和B5樓?？傎M用為38。5.用最速下降法求，取初始點為?！驳淮渭纯伞场?5分〕解：∴令∵令∴因此得∵∴此時精度為：6.某企業(yè)新來8名工人，擬分給3個作業(yè)班組，每個作業(yè)班組最多只分5名工人。各作業(yè)班組得到新工人后產(chǎn)量增加量如下表。問如何分配新工人才能使總產(chǎn)量增加最大？試建立其動態(tài)規(guī)劃求解模型〔可不求解〕?！?0分〕增加人數(shù)作業(yè)班組012345第一班組第二班組第三班組0001610122514173016213217223317.522.5解：根據(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}?！?〕uk：第k階段分配給第k作業(yè)班組的新工人數(shù)；有：U1={0,1,2,3,4,5}，U2={0,1,2,…,x2}(x25)；U2={x2-5,…,5}(x2>5)，U3={x3}?！?〕狀態(tài)轉(zhuǎn)移方程：；〔5〕階段指標：見表，如：；；〔6〕遞推方程：〔7〕邊界條件：。7.寫出求解網(wǎng)絡(luò)最小費用最大流問題的算法步驟?！?5分〕解：設(shè)分別表示〔容量，流量，費用〕，最小費用最大流問題的算法步驟為：〔1〕給定初始可行流，迭代后得；〔2〕構(gòu)造費用有向圖〔流增量圖〕，設(shè)中弧得權(quán)為：，其中的弧可以去掉；〔3〕求中v1至vn的最小費用路〔可擴大路〕P；〔4〕在最小費用路〔可擴大路〕P上調(diào)整流量式中〔5〕重復(fù)〔2〕~〔4〕步，找不到v1至vn的最小費用路〔可擴大路〕P時，那么得到最小費用最大流，迭代完畢。8.某農(nóng)場需決定種植農(nóng)作物的種類：A1、A2、A3。種植不同作物的收益〔元〕主要取決于天氣〔見下表〕，要求：〔1〕用不確定型決策方法，決定種哪一種作物?！?分〕〔2〕如天氣預(yù)報給出好天氣的概率為0.3，中等天氣的概率為0.4，壞天氣的概率為0.3，用風(fēng)險型決策方法決定種哪一種作物。〔5分〕自然狀態(tài)策略收益好天氣中等天氣壞天氣A1250001800010000A230000120008000A3200001600012000解：〔1〕用不確定型決策方法等可能準那么：∴樂觀準那么：∴悲觀準那么：∴懊悔值準那么：懊悔值矩陣為：那么∴〔2〕用風(fēng)險型決策方法〔最大期望收益〕的決策樹為：eq\o\ac(○,2)1eq\o\ac(○,4)eq\o\ac(○,3)△12000△25000△18000△10000△30000△12000△8000△20000△16000好天氣0.3好天氣0.3好天氣0.3中等天氣0.4中等天氣0.4中等天氣0.4壞天氣0.3壞天氣0.3壞天氣0.3A1A2A316200177001600017700∴，〔答題畢〕2003級〔B〕參考答案1.證明，假設(shè)線性規(guī)劃問題有兩個不同的最優(yōu)解，那么它有無窮多最優(yōu)解?！?0分〕證明：設(shè)、是線性規(guī)劃問題：的兩個不同最優(yōu)解，那么有，從而，對有：，兩式相加有：由此可知是線性規(guī)劃問題的可行解。而所以也是線性規(guī)劃問題的最優(yōu)解。故線性規(guī)劃問題有無窮多最優(yōu)解。2.有甲、乙、丙三種類型的煤，每種煤的含硫量、發(fā)熱量及價格如下表?，F(xiàn)將三種煤混合使用，混合后要求每公斤煤的發(fā)熱量不低于21×4.19×103J，含硫量不超過0.025%，問如何混合才能使本錢最低？試建立其數(shù)學(xué)模型?！?0分〕類型含硫量〔%〕發(fā)熱量〔4.19×103J/kg〕價格〔元/t〕甲乙丙0.010.050.03202422201618.5解：設(shè)每噸混合煤分別使用甲、乙、丙三種煤噸，混合煤的本錢為Z。那么有：3.某一極小化線性規(guī)劃問題在單純形法計算時得到下表，其中a，b，c，d，e，f是未知數(shù)，原問題中要求各變量均非負，問a，b，c，d，e，f應(yīng)滿足什么條件，有下面各解成立？〔10分〕CBXBx1x2x3x4x5x6bx3x4x62c10e0-1-501-10a-300-41f23σjbd0030〔1〕是唯一最優(yōu)解；〔2〕有無窮多最優(yōu)解；〔3〕無界解；〔4〕是可行解但非最優(yōu)解，只有x1可以進基且出基變量必為第3個變量。解：〔1〕當現(xiàn)行解為可行解，且對應(yīng)的非基變量的檢驗數(shù)均大于0時，LP問題才有唯一最優(yōu)解，即f≥0，b＞0，d＞0。x3，x4，x6非人工變量；a，c，e無限制?！?〕當所有非基變量的檢驗數(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無限制?！?〕當f≥0時現(xiàn)行解為基可行解，當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ī)劃問題，并對照指出單純形法的每步迭代相當于圖解法中可行域的哪一個頂點?！?0分〕解：用圖解法有：有；用表格單純形法求解有：原模型標準化為：Cj-2-1000bCBXBx1x2x3x4x50x30110030x43*1010120x5110015σj-2-100000x3011003-2x111/301/304-1x502/3*0-1/311σj0-1/302/30-80x30011/2-3/23/2-2x21001/2-1/27/2-1x1010-1/23/23/2σj0001/21/2-17/2所以：；其中：表一對應(yīng)圖中O點；表二對應(yīng)圖中D點；表三對應(yīng)圖中C點。5.寫出求解整數(shù)規(guī)劃〔max型〕的分枝定界法的根本方法步驟?！?0分〕解：求解整數(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〕當所有分枝均已查明，有=時，即得到原問題的最優(yōu)解，，求解過程完畢。6.判斷下述函數(shù)的凹凸性：〔10分〕解：因；有：a11=0；A2==-4﹤0；A3==-8﹤0即函數(shù)的海賽矩陣為不定矩陣，故為非凸非凹函數(shù)。7.寫出建立動態(tài)規(guī)劃求解模型的根本步驟?！?0分〕解：建立動態(tài)規(guī)劃求解模型的根本步驟為：〔1〕按問題容劃分階段，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ù)量?！?0分〕解：〔1〕根據(jù)題意該問題的益損值表為：Sjαi1001502002501001502002501000-250-1500-275010001500250-10001000150020007501000150020002500〔2〕等可能準那么：樂觀準那么：悲觀準那么：懊悔值準那么：懊悔值矩陣為：那么〔答題畢〕2004級〔A〕1將線性規(guī)劃問題化為標準型?！?0分〕解：原模型標準化為：2用圖解法求解〔10分〕解：用圖解法有：〔20/19,45/19〕〔20/19,45/19〕〔2,0〕3x1+5x2=15x254321012345x15x1+2x2=10該問題有無窮多最優(yōu)解,聯(lián)立解得；聯(lián)立解得；所以；3用單純形法求解〔15分〕解：原問題標準化為用表格單純形法求解有：Cj1-21000bCBXBx1x2x3x4x5x60x411-2100100x52-1401080x6-1[2]-40014σj1-2100000x43/20010-1/280x53/20[2]011/210-2x2-1/21-2001/22σj00-3001-40x43/20010-1/281x33/40101/21/45-2x211001112σj9/40003/27/4-19所以有：X*=(x1,x2,x3,x4,x5,x6)T=(0,12,5,8,0,0)T；Z′*=-19復(fù)原為原問題有：X*=(0,12,5,8)T；Z*=194用對偶單純形法求解線性規(guī)劃問題：〔15分〕解：用對偶單純形法求解有：Cj1100bCBXBx1x2x3x40x3-2-110-40x4-1-7*01-7σj110000x3-13/7*01-1/7-31x21/710-1/71σj6/7001/711x110-7/131/1321/131x2011/13-2/1310/13σj006/131/1331/13∴規(guī)劃問題最優(yōu)解為X*=(21/13，10/13)T；Z*=31/135用隱枚舉法求解以下0-1規(guī)劃問題s.t.?！?0分〕解：將原問題變量重新排列有：s.t.。枚舉過程如下表：序號X=(x2,x4,x3,x1)T閥值約束1約束2約束3目標函數(shù)0(0,0,0,0)T√×1(0,0,0,1)T×2(0,0,1,0)T√×3(0,0,1,1)T×4(0,1,0,0)T4√√√45(0,1,0,1)T×6(0,1,1,0)T×7(0,1,1,1)T×8(1,0,0,0)T×9(1,0,0,1)T×10(1,0,1,0)T×11(1,0,1,1)T×12(1,1,0,0)T×13(1,1,0,1)T×14(1,1,1,0)T×15(1,1,1,1)T×所以：X*=(x2,x4,x3,x1)T=(0,1,0,0)TZ*=4復(fù)原有：X*=(x1,x2,x3,x4)T=(0,0,0,1)TZ*=46用黃金分割法求解：的極小點。只要求迭代一步?！?0分〕解：〔1〕因所以舍去區(qū)間〔6.18，10]7試建立求解問題：s.t.均是非負整數(shù)。的動態(tài)規(guī)劃模型〔不必求解〕?！?0分〕解：原問題可改寫為：s.t.均是非負整數(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=x1-u1=3-u1，x3=x2-u2〔5〕階段指標：，，〔6〕遞推方程：〔7〕邊界條件：8在圖中用雙標號法求從v1到其它頂點的最短路和最短距離，并指出對v1來說，哪些頂點是不可達的?；∵厰?shù)字是該弧的長度?！?0分〕11267634433v8v7v6v5v4v3v14v21解：標號過程如下：(7,(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來說，頂點v3、v4是不可達的。9某工廠要制定下年度產(chǎn)品的生產(chǎn)批量方案，根據(jù)市場調(diào)查和市場預(yù)測的結(jié)果，得到產(chǎn)品市場銷路好、中、差三種自然狀態(tài)的概率分別為0.3、0.5、0.2，工廠采用大批、中批、小批生產(chǎn)可能得到收益值也可以計算出來，見下表?，F(xiàn)在要求通過決策分析，合理地確定生產(chǎn)批量，使企業(yè)獲得的收益最大?！?0分〕自然狀態(tài)sj方案di收益銷路好s1銷路中s2銷路差s3p(s1)=0.3p(s2)=0.5p(s3)=0.2大批生產(chǎn)d120128中批生產(chǎn)d2161610小批生產(chǎn)d3121212解：〔1〕最大可能準那么由表可以看出，自然狀態(tài)s2的概率p(s2)=0.5最大，因此產(chǎn)品的市場銷路中(s2)的可能性也就最大。于是就考慮按照這種市場銷路決策，通過比擬可知，企業(yè)采取中批生產(chǎn)收益最大，所以d2是最優(yōu)決策方案?！唷?〕最大期望值準那么自然狀態(tài)sj方案di收益E(di)銷路好s1銷路中s2銷路差s3p(s1)=0.3p(s2)=0.5p(s3)=0.2大批生產(chǎn)d12012813.6中批生產(chǎn)d216161014.8小批生產(chǎn)d312121212.0∴〔3〕決策樹法決策樹如下圖：決策決策△12△20△12△8△16△16△10△12△12銷路好0.3銷路中0.5銷路差0.2大批量生產(chǎn)14.813.612.014.8d1d2d3銷路好0.3銷路好0.3銷路中0.5銷路中0.5銷路差0.2銷路差0.2中批量生產(chǎn)小批量生產(chǎn)∴2004級〔B〕1用圖解法求解〔10分〕解：用圖解法有：〔10,0〕〔10,0〕x1+x2=1x2=4x1+2x2=10x254321012345678910x1聯(lián)立解得；2用表格單純形法求解〔15分〕解：原問題標準化為:用單純形表格迭代有：Cj-2.5-100bCBXBx1x2x3x40x33510150x4[5]20110σj-2.5-10000x30[19/5]13/59-2.5x112/501/52σj0001/2-5-1x2015/193/1945/19-2.5x110-2/1913/9520/19σj0001/2-5所以；3寫出線性規(guī)劃問題：的對偶規(guī)劃?！?0分〕解：原問題的對偶規(guī)劃為：或4用大M法求解：為自由變量?！?5分〕解：原問題標準化為：為自由變量。用表格迭代有Cj-5-3-6600MbCBXBx1x2x3x4x5x6x70x5121-1100180x621[3]-301016Mx7111-100110σj-5-M-3-M-6-M6+M00010M0x51/35/3001-1/3038/3-6x32/31/31-101/3016/3Mx71/3[2/3]000-1/3114/3σj-1-M/3-1-2M/30002+M/30-32+14M/30x5-1/200011/2-5/21-6x3[1/2]01-101/2-1/23-3x21/21000-1/23/27σj-1/200003/2-390x5001-1114-5x1102-2016-3x201-1[1]0-14σj001-102-420x50100108-5x112000-1146x401-110-14σj010001-46所以有：X*=(x1,x2,x3,x4,x5,x6,x7)T=(14,0,0,4,8,0,0)T；Z′*=-46復(fù)原為原問題有：X*=(14,0,-4)T；Z*=465求解整數(shù)規(guī)劃問題：s.t.且為整數(shù)?！?0分〕解：原問題用圖解法求解過程為：00426486x18x22∴X*=(0,5)T；Z*=406判斷函數(shù)：的凹凸性。〔10分〕解：的海賽矩陣為：==，當時，所以為凸函數(shù)。7有100臺機器分四期使用，每期有兩種任務(wù)：任務(wù)一高負荷工作，報廢率1/3，收益10；任務(wù)二低負荷工作，報廢率1/10，收益7。試建立其動態(tài)規(guī)劃模型〔不必求解〕?！?0分〕解：(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ù)為xk-uk，有：0≤u1≤x10≤u2≤x20≤u3≤x30≤u4≤x4(4)狀態(tài)轉(zhuǎn)移方程：(5)階段指標函數(shù)：(6)遞推方程：(7)邊界條件：8以下圖為求vs至vt的最小費用最大流時得到的某一流圖，弧邊數(shù)字為，試構(gòu)造其費用有向圖?！?0分〕4,4,64,4,63,3,83,3,33,2,72,0,33,0,62,1,32,2,32,2,22,0,34,2,44,4,24,4,24,4,2vtv6v5v4v3v2vsv1解：由原流圖可作出其費用有向圖為：-4-4-7-3-6-8-37363-3-234-2-2-2vtv6v5v4v3v2vsv19某企業(yè)擬利用剩余生產(chǎn)能力開發(fā)新產(chǎn)品?，F(xiàn)有四種品種可供選擇，市場銷路有好、中、差三種情況，銷售狀態(tài)概率及每一品種在不同狀態(tài)下的收益見下表，試用最大可能法、最大期望收益法和決策樹法進展方案選擇?！?0分〕銷路品種收益(萬元)銷路好銷路中銷路差p(θ1)=0.3p(θ2)=0.5p(θ3)=0.2A1141412A2221410A3181610A420128解：〔1〕最大可能準那么由表可以看出，銷路中的概率p=0.5最大，因此產(chǎn)品的市場銷路中的可能性也就最大。因max(14,14,16,12)=16∴〔2〕最大期望值準那么因max(E(A1),E(A2),E(A3),E(A4))=max(13.6,15.6,15.4,13.6)=15.6∴〔3〕決策樹法決策樹如下圖：決策決策品種A115.6△14△14△12銷路好0.3銷路中0.5銷路差0.213.6A1△22△14△1015.6A2銷路好0.3銷路中0.5銷路差0.2△18△16△1015.4A3銷路好0.3銷路中0.5銷路差0.2△20△12△813.6A4銷路好0.3銷路中0.5銷路差0.2品種A2品種A3品種A4∴2005級〔A〕1用圖解法求解以下線性規(guī)劃問題，并指出問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解?！?0分〕解：圖解過程見以下圖012012x1x221有：該問題有無窮多最優(yōu)解。2將以下線性規(guī)劃問題化為標準形式，并列出初始單純形表?！?0分〕解：原問題標準化為：其初始單純形表為：Cj-3-11-20000Xjx1x/2x//2x/3x4x5x6x7000x4x6x7128524331-1-3-114-2-31000-10010001cj-zj-3-11-200003某線性規(guī)劃問題用單純形法迭代時得到中間某兩步的單純形表如表所示，試將表中空白處數(shù)字填上?！?0分〕354000x1x2x3x4x5x6500x2x5x68/314/329/32/3-4/35/31000541/3-2/3-2/3010001cj-zj-1/304-5/300┇┇543x2x3x150/4162/4189/4100110001015/41-6/41-2/418/415/41-12/41-10/414/4115/41cj-zj000-45/41-24/41-11/414線性規(guī)劃問題：試應(yīng)用對偶理論證明上述線性規(guī)劃問題最優(yōu)解為無界?！?0分〕解：原問題的對偶問題為：由約束條件可知，其對偶問題無解；又因是原問題的可行解。由對偶定理可知原線性規(guī)劃問題最優(yōu)解為無界。5東興煤炭公司下屬桔祥、平安、雙福三個煤礦，年生產(chǎn)能力分別為120、160、100萬t。公司同3個城市簽訂了下年度的供貨合同：城市1-110萬t，城市2-150萬t，城市3-70萬t，但城市3表示愿購置剩余的全部煤炭。另有城市4雖未簽訂合同，但也表示只要公司有剩余煤炭，愿全部收購。從各礦至4個城市的煤炭單位運價見表。將此問題歸結(jié)為運輸問題，列出相應(yīng)的產(chǎn)銷平衡表與單位運價表。〔10分〕單位運價表單位：元/t城市煤礦1234桔祥平安雙福856724513235解：該問題的運輸問題產(chǎn)銷平衡表與單位運價表為城市煤礦1233/4/產(chǎn)量桔祥平安雙福虛設(shè)礦山856M724M513M5130235012016010050銷量1101507050506以下五名運發(fā)動各種姿勢的游泳成績(各為50m，單位：s)如表所示。試問如何從中選拔一個4×50m混合泳的接力隊，使預(yù)期的比賽成績?yōu)樽詈谩！?0分〕錢王周仰泳蛙泳蝶泳自由泳37.743.433.329.232.933.128.526.438.842.238.929.637.034.730.428.535.441.833.631.1解：原問題用匈牙利算法求解為：變換后：再變換為：再變換：再變換為：∴Z*=127.87分別用破圈法和避圈法求以下圖的最小局部樹?！?0分〕22222222233335514解：用破圈法求最小局部樹為：W〔Tmin〕=18注意有多重解22222222233335514用避圈法求最小局部樹為：W〔Tmin〕=18222222222333355148用標號法求以下圖中v1至各點的最短路?！?0分〕vv1v6v5v7v3v2198v42857410373解：標號過程如下圖：vv1v6v5v7v3v2198v42857410373〔0,v1〕〔14,v4〕〔13,v5〕〔11,v2〕〔10,v2〕〔9,v1〕〔8,v1〕由圖可得：v1→v2L=9v1→v3L=8v1→v2→v4L=11v1→v2→v5L=10v1→v2→v4→v6L=14v1→v2→v5→v7L=139現(xiàn)有8名青工，要分配給3個采礦隊，每隊限最多分5名，每個采礦隊增加不同青工后產(chǎn)量增加如下表，如何分配才能使產(chǎn)量增加最大？試建立其動態(tài)規(guī)劃求解模型?！?0分〕增加青工數(shù)采礦隊012345第一采礦隊第二采礦隊第三采礦隊0001610122514173016213217223317.522.5解：根據(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}?！?〕uk：第k階段分配給第k作業(yè)班組的新工人數(shù)；有：U1={0,1,2,3,4,5}，U2={0,1,2,…,x2}(x25)；U2={x2-5,…,5}(x2>5)，U3={x3}?！?〕狀態(tài)轉(zhuǎn)移方程：；〔5〕階段指標：見表，如：；；〔6〕遞推方程：〔7〕邊界條件：。10某書店希望訂購最新出版的圖書出售。根據(jù)以往經(jīng)歷，新書的銷售量可能為50、100、150或200本。假定每本書的訂購價為4元，銷售價為6元，剩書處理價為每本2元。分別依據(jù)悲觀主義、樂觀主義、等可能性、最小時機損失決策準那么決定該書店應(yīng)訂購新書的數(shù)量?！?0分〕解：〔1〕根據(jù)題意該問題的益損值表為：Sjαi50100150200501001502001000-100-2001002001000100200300200100200300400〔2〕悲觀準那么：∴樂觀準那么：∴等可能準那么：∴最小時機損失準那么：損失矩陣為：那么∴答題畢2005級〔B〕1用圖解法求解以下線性規(guī)劃問題，并指出問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解?！?0分〕解：圖解過程見以下圖0123401234x1x2321由圖可見，該問題具有無界解。2將以下線性規(guī)劃問題化為標準形式，并列出初始單純形表。〔10分〕解：原問題標準化為：其初始單純形表為：Cj-3-5-110000Xjx1x2x/3x//3x4x5x6x7000x5x6x761610121211135-1-3-5-100100010001cj-zj-3-5-1100003寫出以下線性規(guī)劃問題的對偶問題?！?0分〕解：原問題的對偶規(guī)劃為：4用對偶單純形法求解以下線性規(guī)劃問題?！?0分〕解：用對偶單純形法求解有：Cj-5-2-400bCBXBx1x2x3x4x50x4-3-1-210-40x5-6-3*-501-10σj-5-2-4000x4-1*0-1/31-1/3-2/32x2215/30-1/310/3σj-10-2/30-2/320/35x1101/3-11/32/32x20112-12σj00-1/3-1-1/322/3∴規(guī)劃問題最優(yōu)解為X*=(2/3，2，0)T；Z*=22/35運輸問題的產(chǎn)銷平衡表與單位運價表如表所示，試用Vogel法求出其近似最優(yōu)解?！?0分〕銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3A491081081091012121111131412121824612銷量614355解：該問題用Vogel法求其近似最優(yōu)解為：銷地414414224475B1B2B3B4產(chǎn)量A1A2A3A49108108109101212111113141212182461210103231-231-211銷量61435511001-002-00--006求解整數(shù)規(guī)劃問題：〔10分〕解：用圖解法有：00426486x18x22●●●∴X*=(5，0)T或X*=(4，1)T或X*=(3，2)T；Z*=57用單純形求解下述目標規(guī)劃問題：〔10分〕解：用單純形法求解有000P2P30P4P11.5P4P1基x1x2d1-d1+d2-d2+d3-d3+d4-d4+0P3P41.5P4d1-d2-d3-d4-40100301511[1]011011000-100001000-100001000-100001000-1P10000000101P20001000000P3-1-100010000P4-1-1.500000101.50P301.5P4d1-d2-x1-d4-107030150010[1]1011000-100001000-100-1-11011-100001000-1P10000000101P20001000000P30-100011100P40-1.500001001.50P301.5P4x2d2-x1-d4-1060305001010001-10-1-110[1]01000-100-101110-1-10001000-1P10000000101P20001000000P3001-1011100P4001.5-1.500-0.51.501.50P30P2x2d2-x1-d1+155530500101000000-1000101000-1000-11[1]01-1-11-101-110-1P10000000101P2001000-11-11P30000011-11-1P4000000101.500P30P4x2d2-x1-d3-1560255001010000-11-101-1101000-1000001000-110-11-101-1P10000000101P20001000000P3001-1010000P4001-100010.51∴X*=(25，15)T8用Ford-Fulkerson的標號算法求以下圖中所示各容量網(wǎng)絡(luò)中從vs到vt的最大流。圖中各弧旁數(shù)字為容量cij，括弧中為流量fij?！?0分〕vvsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)解：用Ford-Fulkerson方法求解?！?〕根據(jù)初始流，那么尋找可擴大路〔增廣鏈〕的標號過程如下：vvsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)〔-，∞〕〔+vs，2〕〔-v5，1〕〔+v2，1〕〔-v3，1〕〔+v1，1〕〔+v4，1〕〔2〕調(diào)整流量，繼續(xù)標號有：vvsv5v4v3v2v1vt3(2)3(3)5(5)6(5)3(3)2(0)4(4)2(1)5(5)2(0)6(6)8(7)〔+vs，1〕〔-，∞〕〔3〕由圖所示，標號過程進展不下去，即不存在vs-vt的可擴大路〔增廣鏈〕，根據(jù)可擴大路〔增廣鏈〕定理，圖示流即為最大流，maxQ=13。9某項工程有三個設(shè)計方案。據(jù)現(xiàn)有條件，這些方案不能按期完成的概率分別為0.40，0.60，0.80，即三個方案均完不成的概率為0.40×0.60×0.80=0.192。為使這三個方案中至少完成一個的概率盡可能大，決定追加2萬元投資，當使用追加投資后，上述方案完不成的概率見下表。問應(yīng)如何分配追加投資，使其中至少有一個方案完成的概率為最大?！仓唤Ｐ汀场?0分〕追加投資〔萬元〕各方案完不成的概率1230120.400.200.150.600.400.200.800.500.30解：(1)階段：每個設(shè)計方案為一階段，K={1,2,3,4}，k=4為完畢階段。(2)狀態(tài)變量sk：k階段初待分派的資金；S1={2}、S2={0,1,2}、S3={0,1,2}。(3)決策變量xk：k階段分派給k設(shè)計方案的資金；D1(s1)={0,1,2}、D2(s2)={0,1,2}、D3(s3)={s3}。(4)狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk(5)階段指標函數(shù)：vk(sk,xk)見表所示。(6)遞推方程：(采用逆推法)(7)邊界條件：10有一塊海上油田進展勘探和開采的招標。根據(jù)地震資料的分析，找到大油田的概率為0.3，開采期可賺取20億元；找到中油田的概率為0.4，開采期可賺取10億元；找到小油田的概率為0.2，開采期可賺取3億元；油田無工業(yè)開采價值的概率為0.1，按招標規(guī)定，開采前的勘探等費用均由中標者負擔(dān)，預(yù)期需1.2億元，以后不管油田規(guī)模多大，開采期賺取的利潤中標者分成30%。有A、B、C三家公司，其效用函數(shù)分別為：A公司U(M)=(M+1.2)0.9-2B公司U(M)=(M+1.2)0.8-2C公司U(M)=(M+1.2)0.6-2試根據(jù)效用值，并用期望值法確定每家公司對投標的態(tài)度。〔10分〕解：決策樹見以下圖：4.84.80-1.2-0.31.80.10.20.40.3中油田小油田無開采價值大油田不投標或未中標投標并中標計算效用期望值見下表。大油田中油田小油田無開采價值EMV0.30.40.20.1A公司3.01580.6872-1.0905-20.7615B公司2.19300.4089-1.0802-20.4054C公司0.9302-0.0668-1.0613-2-0.1560結(jié)論為A公司和B公司愿參加投標，C公司不參加投標。答題畢2006級〔A〕1用圖解法求解以下線性規(guī)劃問題?！?0分〕解：圖解過程見以下圖0510152005101520x1x22015105由得有：。該問題具有唯一最優(yōu)解。2.求解：〔10分〕解：原問題標準化為：用對偶單純形法求解為：Cj52400bCBXBx1x2x3x4x500x4x5-3-1-210-6-3*-501-4-10σj52400002x4x2-1*0-1/31-1/3215/30-1/3-2/310/3σj102/302/320/3-5-10x1x2101/3-11/30112-12/32σj001/311/322/3∴X*=〔2/3，2，0〕T；Z*=22/3〔注：用大M法、兩階段法求解均可〕3線性規(guī)劃問題如下，原問題最優(yōu)解為，，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解?！?0分〕解：其對偶問題為：∵原問題的最優(yōu)解為，設(shè)對偶問題的松弛變量分別為y5，y6，y7，y8，原問題的松弛變量為x5，x6，x7，x8。將最優(yōu)解代入原問題約束條件中得：x5=0，x6=0，x7=0，x8≠0根據(jù)互補松弛性知：x*ws=0∴x1*y5=x2*y6=x3*y7=x4*y8=0∴y5=y6=y7=0，y8≠0即有：再由互補松弛性知：y*zs=0即：y1*x5=y2*x6=y3*x7=y4*x8=0因x8≠0，所以y4*=0，那么有：解得：∴對偶問題的最優(yōu)解為，4某廠生產(chǎn)A、B、C三種產(chǎn)品，其所需勞動力，材料等有關(guān)數(shù)據(jù)見表，該問題的最優(yōu)單純形表如下?，F(xiàn)如果設(shè)計一種新產(chǎn)品D，單件勞動力消耗為8單位，材料消耗為2單位，每件可獲利3元，問該種產(chǎn)品是否值得生產(chǎn)?！?0分〕產(chǎn)產(chǎn)品消耗定額資源ABC可用量〔單位〕勞動力材料6334554530產(chǎn)品利潤〔元/件〕314Cj31400bCBXBx1x2x3x4x534x1x310-1/31011/3-1/5-1/32/553σj0-20-1/5-3/527解：由題意有：，那么由于，需繼續(xù)迭代。有Cj314300bCBXBx1x2x3x4x534x1x310-1/3101[2]-4/51/3-1/5-1/32/553σj0-201/5-1/5-3/52734x4x31/22/5-1/613/1501101/6-1/15-1/64/155/25σj-1/10-59/3000-7/30-17/3027.5即：此線性規(guī)劃問題的解為：x*=(0，0，5，5/2)T,z*=27.5由此可見該產(chǎn)品是值得生產(chǎn)的。5某鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油，目的使總的鉆探費用最小，假設(shè)10個井位代號為S1，S2，…，S10，相應(yīng)的鉆探費用為C1，C2，…，C10，并且井位的選擇上要滿足以下條件：①或選擇S2和S7，或選擇鉆探S9；②選擇了S3或S4就不能選擇S5，或反過來也一樣。③在S1，S6，S8，S10中最多只能選兩個。試建立這個問題的數(shù)學(xué)模型。〔10分〕解:設(shè)鉆井隊是否選擇某個鉆井的事件為xi(i=1,2,…,10)∴建立的數(shù)學(xué)模型如下：6運輸問題的產(chǎn)銷平衡表、最優(yōu)運方案及單位運價表分別如下表所示，試分析：從A至B的單位運價C在什么圍變化時，最優(yōu)調(diào)運方案不變?！?0分〕產(chǎn)銷平衡表及最優(yōu)方案銷地產(chǎn)地B1B2B3B4產(chǎn)量A151015A20101525A355銷量5151510單位運價表銷地產(chǎn)地B1B2B3B4A11012011A2127920A32141618解：當C22變化時,最優(yōu)方案不變即應(yīng)使各檢驗數(shù)大于等于零?？傻茫杭串攺腁2至B2的單位運價C22在3至10之間變時，上述最優(yōu)調(diào)運方案不變。7用破圈法和避圈法求以下圖中的最小局部樹?！?0分〕4467985545V7V53V3V1V4V2V66解：最小局部樹為：44679855645V7V53V3V2V1V4V6所以：MinW〔T〕=268證明以下圖中v1至v5流為最小費用最大流?；∵厰?shù)字為〔cij，fij，aij〕〔10分〕(5,5,2)(5,5,2)(2,0,3)(6,5,1)(3,0,2)(8,5,4)(7,4,6)(4,4,1)V5V4V3V2V1證明：由原流圖可作出其費用有向圖為：而費用有向圖中不存在從v1至v5的費用最短路，所以原圖所示為最小費用最大流。其最大流為9，最小費用為。9有600萬元資金用于三個工廠的更新改造，投資數(shù)以百萬元為單位取整數(shù)，工廠Ⅱ的投資不超過300萬元，工廠Ⅰ和Ⅲ的投資均不少于100萬元，又不超過400萬元，各工廠投資更新改造后，每年可增加的效益如下表所示：效益投資工廠0100200300400Ⅰ361114Ⅱ051012Ⅲ481115試建立動態(tài)規(guī)劃求解其預(yù)期效益最大的投資分配方案模型?！?0分〕解：〔1〕按工廠劃分階段，有k=1，2，3，4〔4表示資金分配完畢階段〕〔2〕取狀態(tài)變量sk為第k階段初待分配資金，有，，，〔3〕取決策變量xk為第k階段分配給k工廠的資金，有，，〔4〕狀態(tài)轉(zhuǎn)移方程為：〔5〕階段指標見表，如，〔6〕遞推方程為：〔7〕邊界條件：10某工程隊承當一橋梁的施工任務(wù)，由于該地區(qū)夏季多雨，由三個月時間不能施工，在不施工期，該工程隊可將施工機械搬走或留在原處，假設(shè)搬走，需花搬遷費1800元，如果留在原處，一種方案是花500元筑一護堤，防止河水上漲發(fā)生高水位侵襲；假設(shè)不筑護堤，發(fā)生高水位侵襲時將損失10000元，又假設(shè)下暴雨發(fā)生洪水，那么不管是否修護堤，施工機械留在原處都將受到60000元的損失，如果預(yù)測在這三個月中，高水位的發(fā)生率是25%，洪水的發(fā)生率為2%，試依據(jù)決策樹的方法來分析該施工隊要不要把施工機械搬走及要不要修筑護堤?！?0分〕解：該問題的決策樹如下：由此可見，該施工隊需選擇施工機械不搬走，且要修筑護堤。答題畢2006級〔B〕1分別用圖解法和單純形法求解線性規(guī)劃問題，并對照指出單純形法的每步迭代相當于圖解法中可行域的哪一個頂點?！?0分〕解：用圖解法有：有；用表格單純形法求解有：原模型標準化為：Cj-2-1000bCBXBx1x2x3x4x50x30110030x43*1010120x5110015σj-2-100000x3011003-2x111/301/304-1x502/3*0-1/311σj0-1/302/30-80x30011/2-3/23/2-2x21001/2-1/27/2-1x1010-1/23/23/2σj0001/21/2-17/2所以：；其中：表一對應(yīng)圖中O點；表二對應(yīng)圖中D點；表三對應(yīng)圖中C點。2某工廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工，設(shè)A工序可分別在設(shè)備A1或A2上完成，有B1、B2、B3三種設(shè)備可用于完成B工序，產(chǎn)品Ⅰ可在A、B任何一種設(shè)備上加工；產(chǎn)品Ⅱ可在任何規(guī)格的A設(shè)備上加工，但完成B工序時，只能在B1設(shè)備上加工；產(chǎn)品Ⅲ只能在A2與B2設(shè)備上加工，加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)見下表，試安排最優(yōu)生產(chǎn)方案，使該廠獲利最大?！仓唤Ｐ汀场?0分〕設(shè)備產(chǎn)品設(shè)備有效臺時設(shè)備加工費ⅠⅡⅢA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料費〔元/件〕0.250.350.5售價〔元/件〕1.252.002.803寫出以下線性規(guī)劃問題的對偶問題?！?0分〕解:上述問題轉(zhuǎn)化為標準形式為：4線性規(guī)劃問題其最優(yōu)單純形表如下，分析兩個約束的右端項分別在什么圍變化，該問題的最優(yōu)基不變?！?0分〕Cj2-1100bCBXBx1x2x3x4x520x1x51013111101610σj0-3-1-2012解：因為最優(yōu)基不變的條件是：所以：，代入原問題有：，時該問題的最優(yōu)基不變。5運輸問題的產(chǎn)銷平衡表與單位運價表如下表所示，試用表上作業(yè)法求各題最優(yōu)解，同時用Vogel法求出各題的近似最優(yōu)解?！?0分〕銷地產(chǎn)地B1B2B3B4產(chǎn)量A1102201115A212792025A321416185銷量5151510解：銷地產(chǎn)地B1B2B3B4產(chǎn)量A1051015A2101525A355銷量5151510調(diào)運方案的總費用為：5×2+5×2+10×7+15×9+10×11=3356分配問題的效率矩陣如下，試用匈牙利法求出最優(yōu)解?！?0分〕解：用匈牙利法求解有：，7造船廠生產(chǎn)用于河運輸?shù)目拓泝捎么?，下年度各季的合同交貨量、各季度正常及加班時間的生產(chǎn)能力及相應(yīng)每條船在正常及加班時間生產(chǎn)出來的本錢見下表季度合同交貨數(shù)正常生產(chǎn)加班生產(chǎn)能力每條本錢〔百萬元〕能力每條本錢〔百萬元〕116125.076.0217135.176.4315145.376.7418155.577.0該廠確定安排生產(chǎn)方案的優(yōu)先級目標為：P1：按時完成合同交貨數(shù)；P2：每季度末庫存不超過2條〔年初無庫存〕；P3：完成全年合同的總本錢不超過355萬元。要求建立相應(yīng)的目標規(guī)劃模型?！?0分〕解：設(shè)xi為i季度正常生產(chǎn)的船只，yi為i季度加班生產(chǎn)時間生產(chǎn)的船只，si為i季度末庫存數(shù)〔s0=0〕。那么有：8八口海上油井，相互間距離如下表所示。1號井離海岸最近為5海里。問從海岸經(jīng)1號井鋪設(shè)油管將油井連接起來，應(yīng)如何鋪設(shè)使輸油管線長度最短。〔為便于計量和檢修，油管只準在各井位處分叉〔10分〕表1各油井間距離到從234567811.32.10.90.71.82.01.520.91.81.22.62.31.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.5解：用避圈法求其最短長度，如圖。2238541760.61.00.90.80.70.70.5最短輸油管線長度為：L*=5+0.7+0.7+0.8+0.5+0.6+1.0+0.9=10.2海里。9建立求解以下規(guī)劃問題的動態(tài)規(guī)劃模型?！?0分〕解：〔1〕按變量劃分階段，有k=1，2，3，4〔4表示完畢階段〕〔2〕sk：各階段得狀態(tài)變量為：s1，s2，s3，設(shè)：s1=s2+2x1≤3，s2=s3+x2，s3=x3〔3〕xk為決策變量，有：0≤x1≤3/2；0≤x2≤s2；0≤x3≤s3〔4〕狀態(tài)轉(zhuǎn)移方程：s3=s2-x2，s2=s1-2x1，〔5〕階段指標：，，〔6〕遞推方程：〔7〕邊界條件：10某書店希望訂購最新出版的圖書出售。根據(jù)以往經(jīng)歷，新書的銷售量可能為50、100、150或200本。假定每本書的訂購價為4元，銷售價為6元，剩書處理價為每本2元。書店統(tǒng)計過去銷售新書數(shù)量的規(guī)律如下表：銷售量50100150200占得比率〔%〕20403010試用最大期望收益值準那么〔EMV〕決定訂購數(shù)量；假設(shè)書店負責(zé)人能確切掌握新書