《運籌學(xué)》課程考試試卷及答案

1、運籌學(xué)課程考試試卷一、填空題（共 10 分，每空 1 分）1、線性規(guī)劃問題的3 個要素是：、和。2、單純形法最優(yōu)性檢驗和解的判別，當現(xiàn)有頂點對應(yīng)的基可行解是最優(yōu)解當線性規(guī)劃問題有無窮多最優(yōu)解，當線性規(guī)劃問題存在無界解。4、連通圖的是指：。5、樹圖指，最小樹是。6、在產(chǎn)銷平衡運輸問題中，設(shè)產(chǎn)地為m 個，銷地為n 個，運輸問題的解中的基變量為。二、簡答題簡算題（共20分）1、已知線性規(guī)劃問題，如下：max Z=7x1-2x+5 x321 x st14x1 3x 63x833x xi請寫出其對偶問題。（10 分）2、已知整數(shù)規(guī)劃問題：maxz 10 x15x23x4x9s.t.125x 2x85x

2、12x0,且x x 為整數(shù)1212在解除整數(shù)約束后的非整數(shù)最優(yōu)解為(x1, x2)=(1, 1.5)2 個子問題（不需求解（10 分）利用單純形法求解上述問題（14 分，單純形表格已給出, 如若不夠, 可自行添加）三、計算題（共 70 分）（噸）現(xiàn)有原料1A1，A2 B1，B2，（噸）現(xiàn)有原料原料B1B2B3（噸）A121030A202450每噸可得利潤（萬元）320.5在現(xiàn)有原料的條件下，應(yīng)如何組織生產(chǎn)才能使該廠獲利最大？（共 20 分）寫出該線性規(guī)劃問題的數(shù)學(xué)模型（4 分）將上面的數(shù)學(xué)模型化為標準形式（2 分）利用單純形法求解上述問題（14 分，單純形表格已給出, 如若不夠, 可自行添加）

3、2、考慮下列運輸問題：B1B2B3產(chǎn)量A16424A28575銷量333 分）工作34ACD（10 分）工作機器ABCD4107527633344466346 個車間的道路如下圖所示，已知每條道路的的距離，求沿部分道路6 （10 圈法或破圈法均可，但必須用圖或文字描述詳細步驟）V28VV28V41627533616VV355用Ford-Fulkerson標號算法求解下圖中VsVt 的最大流量并標出網(wǎng)絡(luò)的最小割集。（15 分）24vv24(4,3)(3,3)vs(5,1)(1,1)(3,0)(5,3)vt(2,1)v1(2,2)v3運籌學(xué)課程考試試卷參考答案一、填空題(共 10 分，每空 1 分

4、)1、決策變量目標函數(shù)約束條件2、所有的j 0所有的j0，某個非基變量xj-cjzj=0某個j 0 ，Pj相量所有分量aij04、在一個圖中，若每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖5、無圈的連通圖樹枝總長最小的部分樹6、m+n-1二、簡答題。簡算題。（共 20 分）解：（2分）1解：（2分）（82分）（82分）解：選擇 x2 進行分支，得到以下 2 個子問題：253三、計算題（70分）1（20 分）(1) 寫出該線性規(guī)劃問題的數(shù)學(xué)模型（4 分）將上面的數(shù)學(xué)模型化為標準形式（2分）cj320.500CB0cj320.500CB00XBB3050 x1x2x3x4x5x4x5c -zj

5、j203122040.510001030 x1x51550c -zjj1000.520.5040.50.50-1.501030.5x1x31512.5c -zjj1000.50.50.250100.50-1.500.25-0.12532x1x22.525c -zjj100010-12-0.50.50-1.5-0.250.5-0.253214） 2（15分）法求初始解（7分）B1B2B3產(chǎn)量A16/142/34226A28/25/375238銷量333215212校驗數(shù)（7分）B1B2B3uiA116A238vj0-3-4當前調(diào)運方案：x11=1，x13=3，x21=2，x22=3，其余為零，為

6、最優(yōu)方案。最優(yōu)值為6*1+2*3+8*2+5*3=43（1 分）3、解：41075 2763 0631 0 0 16253 0321110541（1）（2）0011（3）3344133004663 3001061u 2u1 04 1 0531（4） 0 1u2 ）（5）11 132u3 2 03v 2 v 12v 0 v434 2 110 括號對應(yīng)的 xij=1，最優(yōu)分配方案。最有效率值 7+2+3+3=15（以上每步 2 分）4、解：方法 1：避圈法V1V1VV，VV為(V1。邊(V1是最小樹內(nèi)的邊。VV2V，VV2V，VV間最短邊為(V2。邊(V2是最小樹內(nèi)的邊。VV3V，VV3V，VV間

7、最短邊為(V3。邊(V3是最小樹內(nèi)的邊。VV5V，VV5V，VV間最短邊為(V5。邊(V5是最小樹內(nèi)的邊。VV4V，VV4V，VV間最短邊為(V4。邊(V4是最小樹（或：VV間最短邊為(V5。邊(V5是最小樹內(nèi)的邊）V28V41V28V416V1275336V28V416V1275336V6V3V5V3V5V28V28V416V7125336V3V5V28V416V7125336V3V56V6V28VV28V416V7125336V3V5V28V416V7125336V3V5V66或沿最終圖中紅線標識的邊架設(shè)電話網(wǎng)，電話線總距離最短 1+2+3+5+6=17。上述 5 個步驟（文字描述或繪圖均

8、可）各的 2 分，若最終結(jié)論沒有給出或給錯扣 1分。方法 2：破圈法1）(1, 2, 3, 1，去掉最大的一邊1, 3，得圖 1V28VV28V4162753616VV35圖 11 (2, 4, 3, 2，去掉最大的一邊2, 4，得圖 2V2V4V2V4162753616VV35圖 22 (3, 4, 5, 3，去掉最大的一邊3, 4，得圖 3V2V4V2V416253616VV35圖 33 (4, 5, 6, 4，去掉最大的一邊4, 6，得4（去掉最大的一邊（5, 64）.V2V412536V2V412536V2V41625316V3V5或V3V5圖 4沿最終圖中的邊架設(shè)電話網(wǎng)，電話線總距離最短 1+2+3+5+6=17。4 個步驟（文字描述或繪圖均可）2.5 1 分。5、解：24vv24(4,3)(3,3)vs(5,1)(1,1)(3,0)(5,3)vt(2,1)v1(2,2)v3標號法找增廣鏈 vs-v1-v2-v4-v