運籌學試題及答案.doc

班級： 學號： 姓名： 茂名學院2009 年成人學士學位主干課程考試卷專業(yè)：信息與計算科學 科目：運籌學題號一二三四五六七八九總分得分閱卷人一、選擇題（共5小題，每題4分）1、 如果一個線性規(guī)劃問題有n個變量，m個約束方程(mn)，系數(shù)矩陣的數(shù)為m，則基可行解的個數(shù)最為（ C ）。 Am個 Bn個 C D個2、 在 求 最 大 流 量 的問 題 中，已 知 與 起 點 相 鄰 的 三 節(jié) 點 單 位 時 間 的 流 量 分 別 為 10,12,15，則 終 點 單 位 時 間 輸 出 的 最 大 流 量 為（ D ） A. 等 于 27 B.大 于 或 等 于 37 C.小 于37 D.小 于 或 等 于 373、如下圖中每條有向邊上的數(shù)字為該邊的容量限制，則從發(fā)點到收點的最大流是（ C ） A、18 B、11 C、12 D、16解析：用最大流標記法可得：4、用最小元素法求初始調(diào)運方案是，運輸表中數(shù)字格的個數(shù)為（D）個。 A、 m*n B、m+n C、m*n-1 D、m+n-15、若用ESi表示結(jié)點i的最早開始時間，ESj表示結(jié)點j的最早開始時間，Ti，j表示活動ij的作業(yè)時間，LFi表示結(jié)點i的最遲完成時間，LFj表示結(jié)點j的最遲完成時間，則下述公式中正確的是（A）A.ESj=B.ESj=C.LFj=D.LFj=二、填空題（共5小題，每題4分）1、求解運輸問題時，常用的判斷運輸方案是否最優(yōu)的方法，一個是閉合回路，另一個是_位勢法_。2、若用三種時間估計法計算作業(yè)時間，則應先估計出最樂觀時間、_悲觀_時間和最可能時間。3、 Max z=3x1+8x2+5x3 4x1+2x215 S.t 3x1+x39 線性規(guī)劃問題 x1、x2、x30 的標準形式是_ 答案： Max z=3x1+8x2+5x3+0*x4+0*x5 4x1+2x2+x4=15 S.t 3x1+x3+x5=9 x1、x2、x3、x4、x504、寫出線性規(guī)劃問題的對偶問題_ 答案：5、 已知下表是制定生產(chǎn)計劃問題的一張LP最優(yōu)單純形表（極大化問題，約束條件均為“”型不等式），其中x4、x5、x6為松弛變量。XBbx 1x 2x 3x4x 5x6x 12110201x 32/3001104x510-20116Cj -Zj000-40-9對偶問題的最優(yōu)解：_答案：Y=(4,0,9,0,0,0)T3、 計算題（共6小題，每題10分）1、用單純形法求線性規(guī)劃問題 max z = 10 x1 + 5x23x1 + 4x2 95x1 + 2x2 8x1,x20解：在問題的約束條件中分別加入松弛變量x3，x4，得該線性問題的標準型 max z = 10 x1 + 5x23x1 + 4x2 + x3 = 95x1 + 2x2 + x4 = 8x1,x2,x3,x40初始單純形表x1x2x3x4x393410 x485201-z010500 x1為進基變量，min9/3,8/5=8/5 x4為出基變量 以x1代替x4，進行旋轉(zhuǎn)運算，得x1x2x3x4x321/5014/51-3/5x18/512/501/5-z-80/5010-2 x2為進基變量，min 21/5/14/5 , 8/5/2/5 =3/2 x3為出基變量 以x2代替x3，進行旋轉(zhuǎn)運算，得x1x2x3x4x23/2015/14-3/14x1110-1/72/5-z-35/200-5/14-25/14 最優(yōu)解x = (1,3/2,0,0)T 目標函數(shù)的最大值z = 35/22、用動態(tài)規(guī)劃的方法求出AD的最短路徑。答案：最短路徑為AB3C1D為213、已知線性規(guī)劃問題 Max z=2x1+x2+5x3+6x4 對偶變量2x1 +x3 +x48 y12x1+2x2 + x3 +2x412 y2Xj0， j=1,2.。4其對偶問題的最優(yōu)解為y1* =4， y2*=1，試應用對偶問題的性質(zhì)，求原問題的最優(yōu)解。4、用標號法求如圖下所示網(wǎng)絡(luò)的最大流和最小截集(割集)，每弧旁的數(shù)字是（）。 V1 (4,2) V3 (6,6) (6,4) VS (3,1) (3,0) (4,1) Vt (5,3) (7,5)V2 (4,4) V4解：（1） 標號過程首先給Vs標上（0，+）。檢查Vs， 在?。╒s,V1）上，fs1=Cs1=6，不滿足標號條件。 在弧（Vs,V2）上，fs2Cs2,給V2標號（Vs，l（V2） l（V2）=minl（Vs），（Cs2-fs2）=min+，2=2檢查V2， 在?。╒2，V4）上，f24=C24=3，不滿足標號條件。 在弧（V1，V2）上，f12C12，給V1標號（-V2，l（V1） l（V1）=minl(V2),f12=min2,1=1檢查V1， 在弧（V1，V3）上，f13C13,給V3標號（V1，l（V3） l(V3)=minl(V1),(C13-f13)=min1,2=1 在?。╒1，V4）上，f14C14,給V4標號（V1，l（V4） L(V4)=minl(V1),(C14-f14)=min1,3=1在V3，V4中任選一個進行檢查， 例如，在弧（V4，Vt）上，f4tC4t，給Vt標號（V4，l（Vt） L(Vt)=minl(V4),(C4t-f4t)=min1,2=1（2） 調(diào)整過程 按點的第一個標號找到一條增廣鏈，如下圖雙箭頭 V1(-V2,1) (4,2) V3(V1,1) (6,6) (6,4) (0,+)VS (3,1) (3,0) (4,1) Vt(V4,1) (5,3) (7,5)V2 (Vs,2) (4,4) V4(V1,1)易見 u+=(Vs,V2),(V1,V4),(V4,Vt) u-=(V1,V2)按=1在u上調(diào)整f。 u+上：fs2+=3+1=4 f14+=0+1=1 f4t+=5+1=6 u上：f12-=1-1=0 其余fij不變。調(diào)整后得到下圖所示可行流 V1 (4,2) V3 (6,6) (6,4) (0,+)VS (3,0) (3,1) (4,1) Vt (5,4) (7,6)V2(Vs,1) (4,4) V4重復上述步驟：開始給Vs標以（0，+），于是檢查Vs，給V2標以（Vs，1），檢查V2，?。╒2,V4）上，f24=C24，弧（V1，V2）上，f12=0，均不符合條件，標號過程無法繼續(xù)下去，算法結(jié)束。最大流為： V（f）=fs1+fs2=f3t+f4t=10最小截集： （V1，）=(Vs,V1),(V2,V4)=105、某地區(qū)有4個化肥廠，估計每年可供應的數(shù)量為A1 -20萬噸、A2 -30萬噸、A3 -40萬噸、 A4-60萬噸，銷往5個城市，每年每個地區(qū)的需求量為B1- 25萬噸、B2-15萬噸、B3-35萬噸、B4-45萬噸、B5-30萬噸。已知從各化肥廠到各城市的每噸化肥的運價如下表所示（單位：萬元）。 銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A16948520A2106128730A365920940A4213614360銷量2515354530請用伏格爾法求出其運費最少的方案。答案： 銷地產(chǎn)地B1B2B3B4B5行差額A1694851A210612871A36592091A421361431列差額41202銷地產(chǎn)地B1B2B3B4B5產(chǎn)量(剩)A120A230A340A42560(35)銷量2515354530 銷地產(chǎn)地B1B2B3B4B5行差額A1694851A210612871A36592094A421361433列差額41202銷地產(chǎn)地B1B2B3B4B5產(chǎn)量(剩)A120A230A31540(25)A42560(5)銷量2515354530 銷地產(chǎn)地B1B2B3B4B5行差額A1694851A210612871A36592090A421361433列差額41202銷地產(chǎn)地B1B2B3B4B5產(chǎn)量（剩）A120A230A31540(25)A4253060(5)銷量2515354530 銷地產(chǎn)地B1B2B3B4B5行差額A1694854A210612874A365920911A421361438列差額41202銷地產(chǎn)地B1B2B3B4B5產(chǎn)量（剩）A120A230A3152540(0)A4253060(5)銷量2515354530 銷地產(chǎn)地B1B2B3B4B5行差額A1694854A210612874A365920911A421361438列差額41202銷地產(chǎn)地B1B2B3B4B5產(chǎn)量（剩）A120A230A3152540(0)A42553060(0)銷量2515354530 銷地產(chǎn)地B1B2B3B4B5行差額A1694854A210612874A365920911A421361438列差額41802銷地產(chǎn)地B1B2B3B4B5產(chǎn)量（剩）A1520(15)A230A3152540(0)A42553060(0)銷量2515354530 銷地產(chǎn)地B1B2B3B4B5行差額A1694858A210612878A365920911A421361438列差額41802銷地產(chǎn)地B1B2B3B4B5產(chǎn)量（剩）A151520(0)A23030(0)A3152540(0)A42553060(0)銷量2515354530 令u1=0，則u2=0、u3=5、u4=2、v1=0、v2=0、v3=4、v4=8、v5=1銷地產(chǎn)地B1B2B3B4B5uiA148u1=0A28u2=0A359u3=5A4263u4=2vjv1=0v2=0v3=4v4=8v5=1得出(ui+vj):銷地產(chǎn)地B1B2B3B4B5uiA100481u1=0A200481u2=0A3559136u3=5A4226103u4=2vjv1=0v2=0v3=4v4=8v5=1檢驗數(shù)Cij - (ui+vj)都大于0，所以為最優(yōu)解。 Cij - (ui+vj)：銷地產(chǎn)地B1B2B3B4B5uiA169004u1=0A2106806u2=0A310073u3=5A4011040u4=2vjv1=0v2=0v3=4v4=8v5=1因此最有方案為：x13=5, x14=15, x24=30, x32=15, x33=25, x41=25, x43=5, x45=30, 最少運費為=850萬元。6、已知某工程的有關(guān)資料如表，畫出其工程網(wǎng)絡(luò)計劃圖。答案：（做題關(guān)鍵：了解網(wǎng)絡(luò)計劃基本元素緊前工作、緊后工作、虛工作和平行工作的定義） 第 11 頁 （共 頁）