運籌學(xué)試卷試題和答案

1、 試 題 2009 年 2010 年第 1 學(xué)期課程名稱： 運籌學(xué)基礎(chǔ) 專業(yè)年級： 信息（電專）0803、0804 考生學(xué)號： 考生姓名： 試卷類型： A卷 B卷 考試方式: 開卷 閉卷 一、 填空（每題4分，共20分）1. 線性規(guī)劃問題MaxZ=CX；AX=b，X0（A為kxl的矩陣，且l>k）的基的最多個數(shù)為_，基的可行解的最多個數(shù)為_.2.指派問題的最優(yōu)解的性質(zhì)_.3.線性規(guī)劃問題的所有可行解構(gòu)成的集合是_,它們有有限個_,線性規(guī)劃問題的每個基可行解對應(yīng)可行域的_,若線性規(guī)劃問題有最優(yōu)解，必在_得到。4影子價格的經(jīng)濟含義_.在完全市場經(jīng)濟的條件下，當某種資源的市場價格低于影子價格時

2、，企業(yè)應(yīng)_該資源，而當某種資源的市場價格高于影子價格時，則企業(yè)應(yīng)_該資源，可見影子價格對市場有_作用。5. 運輸問題的產(chǎn)銷平衡表中有m個產(chǎn)地n個銷地，其決策變量的個數(shù)有_個，其數(shù)值格有_個二、 計算（共60分）1 對下列線性規(guī)劃問題 Max z=2x1+x2+3x3 x1+ x2+2x3 5 s.t. 2x1+3x2+4x312x1, x2, x30（1） 寫出其對偶問題；（5分）（2） 已知（3，2，0）T是上述問題的最優(yōu)解，根據(jù)互補松弛理論求出對偶問題的最優(yōu)解；（10分）2. （15分）運用單純形法求解下面線性規(guī)劃問題。 3 （15分）已知運輸問題的產(chǎn)銷平衡表與單位運價表如下表所示 銷地產(chǎn)

3、地B1B2B3B4產(chǎn)量A11067124A21610599A35410104銷量5246試用運用伏格爾法求出初始運輸方案。4 （15分）用匈牙利法求解下列分配問題，已知效益矩陣為 798561274879667810三、 建模（第1題10分，第2題10分，共20分）1 某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員 （15分）2. 某工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：

4、應(yīng)如何下料，可使所用原料最?。?5分） 試卷答案 2009 年 2010 年第 1 學(xué)期課程名稱： 運籌學(xué)基礎(chǔ) 專業(yè)年級： 信息（電專）0803、0804 考生學(xué)號： 考生姓名： 試卷類型： A卷 B卷 考試方式: 開卷 閉卷 四、 填空（每空2分，共20分）1:Clk , Clk 2設(shè)指派問題的效率矩陣為C= ，若將該矩陣的某一行（或某一列）的各個元素都減去統(tǒng)一常數(shù)，得到新的效率矩陣，則以為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。3 凸集，頂點，頂點，頂點4其它條件不變的情況下，單位第i種資源變化所引起目標函數(shù)值的變化量。買進，賣出。5 ，五、 計算（每題15分，共60分）1. 解（

5、1）（5分）寫出其對偶問題； Minw=5y1+12y2 s.t. y1+2y22 y1+3y21 2y1+4y23 y10， y2 無約束 （2） （10分）已知（3，2，0）T是上述問題的最優(yōu)解，根據(jù)互補松弛理論求出對偶問題的最優(yōu)解； 由于原問題x1和x2為正，根據(jù)互補松弛理論，有對偶問題取最優(yōu)解時（1）、（2）取嚴格等式，即為 y1+2y22 y1+3y21解得y2-1 y14故對偶問題最優(yōu)解為Y*（4，1），w*=82. 解（1）（3分）加入松弛變量，上述模型可轉(zhuǎn)化為（10分） cj3130CBXBbx1x2x3x40x315351050x42462014z031000x33041-0

6、.51.23x1411/301/6-z12000-0.5（2分）最優(yōu)解，最優(yōu)值3. （1） （7分）用最小元素法求得初始可行基如下 銷地產(chǎn)地B1B2B3B4產(chǎn)量A110 36 ×7 ×12 14 0 A216 ×10 ×5 49 59 -3A35 24 210 ×10 ×4 -5銷量5 102 94 86 12（2） （8分）位勢方程組為u1+v1=10 u1+v4=12u2+v3=5 u2+v4=9u3+v1=5 u3+v2=4令u10，解得v1=10 v2=9 v3=8 v4=12 u2 =-3 u3 =-5 各非基變量檢驗數(shù)為1

7、26（09）-3137（08）-12116（103）92210（93）43310（85）73410（125）3存在非基變量檢驗數(shù)為負，沒有達到最優(yōu)解4 用匈牙利法求解下列分配問題，已知效益矩陣為 798561274879667810第一步（5分），把Cij轉(zhuǎn)化為Cij, 2410281030210104第二步（5分），求初始分配方案及尋找覆蓋所有零元素的最少直線，2410281030210104第三步（5分），調(diào)整，求最優(yōu)解。1300170030220105所以，最優(yōu)解為六、 建模（第1題10分，第2題10分，共30分）1. 解：設(shè) xi 表示第i班次時開始上班的司機和乘務(wù)人員數(shù), （2分）這樣我們建立如下的數(shù)學(xué)模型。 目標函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 （3分） 約束條件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0（5分）2. 解： 共可設(shè)計下列5 種下料方案，見下表（5分）設(shè) x1,x2,x3,x4,x5 分別為上面 5 種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。（5分） 目