運籌學試卷H試題

1、中國計量學院200 200學年第學期運籌學課程考試試卷（H）開課二級學院：經(jīng)管學院，考試時間：年_月 _日時考試形式：閉卷、開卷，允許帶計算器、鋼筆（圓珠筆） 、學生證入場考生姓名：學號：專業(yè)：班級：一、單項選擇題（共 20 分，每題2 分）1、使函數(shù) Z=-X1+X2-4X3增加的最快的方向是（）裝A 、（-1 ，1，-4 ） B 、（-1 ，-1，-4 ） C 、（1， 1，4） D、（1， -1 ，-4 ）2、如果決策變量數(shù)相等的兩個線規(guī)劃的最優(yōu)解相同，則兩個線性規(guī)劃（）A、約束條件相同B、目標函數(shù)相同C、最優(yōu)目標函數(shù)值相同D、以上結(jié)論都不對3、maxZ=3x1+2x2,2x1+3x2&

2、lt;=14,x1+0.5x2<=4.5,x1,x2>=0且為整數(shù)， 對應線性規(guī)劃的最優(yōu)解是（ 3.25， 2.5），它的整數(shù)規(guī)劃的最優(yōu)解是（）A、（ 4，1）B、（ 4，3）C、（3，2）D、（ 2， 4）4、已知規(guī)范形式原問題（max）的最優(yōu)表中的檢驗數(shù)為（ 1， 2， n），松弛變量的檢驗數(shù)為（ n+1, n+2, n+m） ,則對偶問題的最優(yōu)解為（）A、（ 1， 2， n）B、（ 1， 2， n）C、（ n+1, n+2, n+m） D 、（ n+1, n+2, n+m）訂5、下列正確的目標規(guī)劃的目標函數(shù)是（）A 、 minZ=P 1 d1- P2d2-B 、 maxZ=

3、P 1d1- +P 2d2-+-+d1+-C 、 minZ=P 1 d1 +P 2(d2 -d2 ) D、 minZ=P 1(d1)+P2 (d2 +d2 )6、下列說法正確的有（）A 、運輸問題的運價表第r行每個 cij同時加上一個非0 常數(shù) k ，其最優(yōu)調(diào)運方案變化。B、運輸問題的運價表的所有cij 同時乘以一個非0 常數(shù) k，其最優(yōu)調(diào)運方案不變。C、運輸問題的運價表第p列每個 cij 同時乘以一個非0 常數(shù) k，其最優(yōu)調(diào)運方案不變。D、運輸問題的運價表的所有cij 同時乘以一個非0 常數(shù) k，其最優(yōu)調(diào)運方案變化。7、 是關于可行流 f的 增廣鏈，則在 上有（）+，c+，c線A 、對任意（

4、 i， j） ，有 fB、對任意（ i ， j） ，fij<ijij<=ijC 、對任意（ i， j ） -，有 f ij <=cijD、 對任意（ i ，j ） - ，有 f ij >=08、工序（ i,j）的總時差 R（ i， j）等于（）A 、TLF（i ， j ） - T EF（ i ， j ） B、 TEF（ i ， j ） - T ES（ i ， j ）C 、T （i ， j ） + T （ i ， j ） D、 T （ j ）- T（ i ） + tijLSESLE中國計量學院 200 200學年第 學期 運籌學課程試卷（ H）第1頁共6 頁9、用動態(tài)規(guī)劃

5、方法求背包問題時，以下正確的說法是（）A、將裝載的物品品種數(shù)作為階段數(shù)。B 、將背包的容量作為決策。C、將背包的容量作為狀態(tài)。D、將裝載的物品品種數(shù)作為決策。10、對于不確定型的決策，某人采用樂觀主義準則進行決策，A、大中取大B、大中取小C、小中取大則應在收益表中 （ D 、小中取?。﹩雾椷x擇題答題表題號1答案2345678910二、判斷題，正確打，錯誤打× ,并將修改建議簡寫在對應題號下的改錯欄。（ 20 分，每題2 分）1、 按最小元素法給出的初始基可行解，從每一空格出發(fā)可以找出而且僅能找出唯一的閉回路。（）2、 當最優(yōu)解中存在為 0 的基變量時，則線形規(guī)劃具有多重最優(yōu)解。（）3

6、、 檢驗數(shù) j 表示非基變量 Xj 增加一個單位時目標函數(shù)值的改變量。（）4、 中國郵路問題是遍歷每一個點的問題。()5、 在折衷主義準則中，樂觀系數(shù) 的確定與決策者對風險的偏好有關。( )6、 工序時間是隨機的，期望值等于3 種時間的算術平均值。 ( )7、 目標規(guī)劃沒有系統(tǒng)約束時，一定存在滿意解。( )8、 整數(shù)規(guī)劃中求最大值問題的目標函數(shù)值是各分支函數(shù)值的下界。（）9、 在任一圖 G中，當點集 V 確定后，樹圖是G中邊數(shù)最少的連通圖。 （）10、用動態(tài)規(guī)劃求解一般線性規(guī)劃問題是將變量數(shù)作為階段數(shù)，資源限量作為狀態(tài)變量。（）三、（ 20分）已知以下線性規(guī)劃問題，max z 10x1 5x2

7、st. 3x1 4x2 95x1 2x2 8x1, x2 0（ 1） 用單純形法求解下列線性規(guī)劃問題。（10分）（ 2） 寫出上述線性規(guī)劃問題的對偶問題。（4分）（ 3） 求解上述線性規(guī)劃問題的對偶問題的最優(yōu)解。（6分）中國計量學院200200學年第學期運籌學課程試卷（H ）第2 頁共 6頁裝四、（ 20 分）在下面的運輸問題中總需要量超過總供應量。假定對銷地B1、B2 和 B3 未滿足需要量的單位罰款成本是3 元 /噸、 2 元 /噸和 1 元 /噸。求最小運費和最優(yōu)的運輸方案。運價（元 /噸）B1B2B3產(chǎn)量（噸）A151710A264680A332515銷量（噸）752050五、（ 10

8、 分）某工廠生產(chǎn)，兩種產(chǎn)品。已知有關數(shù)據(jù)見下表。擁有量中國計量學院200200學年第學期運籌學課程試卷（H ）第3 頁共 6頁裝原材料 kg2111設備hr1210利潤元 / 件810公司在決策時需考慮以下問題：p1：根據(jù)市場信息，產(chǎn)品銷售有下降趨勢，故產(chǎn)品產(chǎn)量不大于產(chǎn)品產(chǎn)量p2：盡可能利用設備，但不能加班p ：應盡可能達到并超過利潤56 元3為確定生產(chǎn)計劃，試建立該問題的目標規(guī)劃模型( 不需要求解 )六、（ 10 分）公司由于規(guī)模擴大，增設了幾個新的部門，管理層決定對現(xiàn)有部門的電話內(nèi)線重新鋪設， 現(xiàn)在一共有 12 個部門如下圖所示， v1 v12 代表 12 個部門辦公室， 圖中的邊是可能聯(lián)

9、網(wǎng)的途徑，邊上的賦權為這條路線的長度，單位為百米，請設計一個網(wǎng)絡能聯(lián)通 12 個部門 , 并能保證總的路線長度最短。34762511984863724中國計量學院200200學年第學期運籌學課程試卷（H ）第4 頁共 6頁中國計量學院 200 200學年第學期運籌學課程試卷（ H ）參考答案及評分標準開課二級學院：經(jīng)管學院，學生班級：，教師：一、單項選擇題（20 分，每題2分）單項選擇題答題表題號12345678910答案ADACDBBACA二、判斷題（ 20 分，每題 2 分）判斷及改錯題答題表題號12345678910答案××××改錯最優(yōu)解是遍歷每等

10、于是上界退化或非一邊(a+4 m+b)/6基變量檢驗數(shù)為零三、（ 20分）已知以下線性規(guī)劃問題，max z 10x1 5x2st. 3x1 4x2 95x1 2x2 8x1, x2 0（ 4） 用單純形法求解下列線性規(guī)劃問題。（10分）（ 5） 寫出上述線性規(guī)劃問題的對偶問題。（4分）（ 6） 求解上述線性規(guī)劃問題的對偶問題的最優(yōu)解。（6分）解：（1）首先，將問題化為標準型（ 4分）。加松弛變量 x3， x4，得其次，列出初始單純形表，計算最優(yōu)值（4分）。中國計量學院200200學年第學期運籌學課程試卷（H ）第5 頁共 6頁由單純形表一得最優(yōu)解為x(1,3/ 2)T , z*35/ 2.（2

11、分）（ 2）對偶問題為(4 分 ) ：min w 9y1 8y2st. 3y1 5y2 104y1 2y2 5y1, y2 0（ 3）用互補松弛地定理求出對偶問題的解為(6 分 , 其中步驟 4分，結(jié)果 2分 ) ：先化為標準型，則有min w 9y1 8y2st. 3y15y2 y3 =104y1 2y2 y4 =5y1, y2 ， y3 ， y4 0根據(jù)互補松弛定理有，x1*y3=0, x2*y4=0, x1>0, x2>0,則有： y3=y4=0 ，帶入對偶問題標準型則有3y1 5y2 =104y1 2y2 =5則有： y1=5/14 y2=25/14, minW=35/2.

12、四、（ 20 分）在下面的運輸問題中總需要量超過總供應量。假定對銷地B1、B2 和 B3 未滿足需要量的單位罰款成本是3 元 /噸、 2 元 /噸和 1 元 /噸。求最小運費和最優(yōu)的運輸方案。運價（元 /噸）B1B2B3產(chǎn)量（噸）A151710A264680A332515銷量（噸）752050中國計量學院200200學年第學期運籌學課程試卷（H ）第6 頁共 6頁解答：虛設供應地A4，虛設地運價為懲罰成本，則有最優(yōu)方案為3B 11B 23B 3產(chǎn)量0A 15（ 2）【10】17（ 4）103A 2【60】6【10】4【10】 6800A 3【15】32（ 1）5(2)15-2 A43 (2)2

13、 (3)【40】 140銷量752050則有最優(yōu)運輸方案為X12=10, X21=60, X22=10, X23=10, X31=15, X43=40.最小運輸費用為555。（步驟為 15 分，結(jié)果為5 分）五、（ 10 分）某工廠生產(chǎn)，兩種產(chǎn)品。已知有關數(shù)據(jù)見下表。擁有量原材料 kg2111設備hr1210利潤元 / 件810公司在決策時需考慮以下問題：p1：根據(jù)市場信息，產(chǎn)品銷售有下降趨勢，故產(chǎn)品產(chǎn)量不大于產(chǎn)品產(chǎn)量p2：盡可能利用設備，但不能加班p3：應盡可能達到并超過利潤56 元為確定生產(chǎn)計劃，試建立該問題的目標規(guī)劃模型( 不需要求解 )解： minZ p dp（d-+ d+d-2） + p33（3 分）11222x1+ x211分）（ 1x -x+d- d+=0分）1121（ 1- +x 1+2x2+d2 - d 2 =10（