(整理)《運(yùn)籌學(xué)》期末考試試題與參考答案

1、運(yùn)籌學(xué)試題參考答案一、填空題（每空2分，共10分）1、在線性規(guī)劃問題中，稱滿足所有約束條件方程和非負(fù)限制的解為可行解 。2、在線性規(guī)劃問題中，圖解法適合用于處理變量 為兩個(gè)的線性規(guī)劃問題。3、求解不平衡的運(yùn)輸問題的基本思想是設(shè)立虛供地或虛需求點(diǎn)，化為供求平衡的標(biāo)準(zhǔn)形式。4、在圖論中，稱 無圈的 連通圖為樹。5、運(yùn)輸問題中求初始基本可行解的方法通常有最小費(fèi)用法 、 西北角法 兩種方法。二、（每小題5分，共10分）用圖解法求解下列線性規(guī)劃問題：1） max z = 6x 1+4x2小2xi X2 10X1 X28X27X，X20、(6)解：此題在“運(yùn)籌學(xué)復(fù)習(xí)參考資料.doc”中已有，不再重復(fù)2)

2、min z = 3x1+2x2-L/2x14x222x14x2102x1x27x 3x2 1x1,x2 0、(7)解:可行解域?yàn)閍bcda,最優(yōu)解為b點(diǎn)。2x1 4x222由方程組c解出X1=11, X2=0x2 0* X1、T.X= = (11, 0)X2.min z = -3X 11+2X 0= 33三、（15分）某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要 A、B、C三種資源，每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷售后所能獲得的利潤值以及這三種資源的儲備如下表所示：ABC甲94370乙46101203602003001）建立使得該廠能獲得最大利潤的生產(chǎn)計(jì)劃的線性規(guī)劃模型；（5分）10分）2）用單純

3、形法求該問題的最優(yōu)解。解： 1）建立線性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為 XI、X2,則XI、X20,設(shè)z是產(chǎn)品售后的總利潤，則maX z =70X 1+120X2s.t.9X1 4X2 3604X1 6X2 2003X1 10X2300X1， X202）用單純形法求最優(yōu)解：加入松弛變量X3, X4, X5,得到等效的標(biāo)準(zhǔn)模型：maX z =70X 1+120X2+0 X 3+0 X 4+0 X 5s.t.9X1 4X2 X33604X1 6X2X42003X1 10X2X5 300X j 0, j 1,2,.,5列表計(jì)算如下：CbXbb70Xi120X20X30X40X5e l0x3

4、36094100900x420046010100/30x53003(10)001300000070120T0000x324039/5010-2/5400/130x420(11/5 )001-3/5100/11120x2303/101001/1010036120001234 T000-120x31860/1100139/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/1143000701200170/1130/1111000-170/1130/11 溫(嗎11300111860110,0) Tmax z =70x 100+120X11300_4

5、30001111四、（10分）用大M法或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€性規(guī)劃模型:min z =5x 1 + 2x2+ 4x33xi X2 2x346x1 3x2 5x3 10Xl,X2,X30解：用大M法，先化為等效的標(biāo)準(zhǔn)模型:max z/ = 5x1 2x2 4x3s.t.3x1x2 2x3 x446x1 3x2 5x3x5 10yj 0, j 1,2,.,5增加人工變量x6、 x7 ，得到：max z/ = 5x 1 2x2 4x3 Mx6 Mx7s.t3x1x2 2x3 x4x646x1 3x2 5x3x5x7 10xj 0,j 1,2,.,7大M法單純形表求解過程如下:-5-2一 400-M

6、-MQXbbXiX2X3X4X5X6X7e l-MX64(3)12-10104/3-MX71063501015/39M-4M7MMM-M-M9Mk 5 T4Mk 27M- 4-M-M005X14/311/32/3 1/301/30-MX72011(2)1-2115-M-5/3-M- 10/3-2M+5/3M2M- 5/3-M0Ml- 1/3M- 2/32M- 5/3 T一 M3M+5/30-5Xi5/311/25/60-1/601/610/30X410(1/2)1/21 1/2-11/22-5 5/2-25/605/60 5/601/2 T1/60-5/6一 M-M+5/6-5Xi2/3101

7、/3-11/31 1/3-2X2201121-2122一-5-2 11/311/3-1 1/3300 1/3-1 1/3-M+1-M+1/3.x= (/, 2, 0, 0, 0) 3最優(yōu)目標(biāo)函數(shù)值 min z = max Z =五、（15分）給定下列運(yùn)輸問題：（表中數(shù)據(jù)為產(chǎn)地A到銷地B的單位運(yùn)費(fèi)）B1B2B3B4SiA123410A876580A91011915d82212181）用最小費(fèi)用法求初始運(yùn)輸方案，并寫出相應(yīng)的總運(yùn)費(fèi)；（5分）2）用1）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。B2Z=1X 8+2X 2+6X 2+5x 18+10X 20+11

8、x 10=4242)用閉回路法，求檢驗(yàn)數(shù):費(fèi)銷BiB2B3B4SAi2304-21082xxA8一 47-26520xx218A9010119130x2010xdj8221218N。6034=10,其余 j0二選X34作為入基變量迭代調(diào)整用表上閉回路法進(jìn)行迭代調(diào)整:調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)j0,已得最優(yōu)解最小運(yùn)費(fèi) Z=1X 8+2X 2+6X 12+5x 8+10X 20+9X 10=414六、（8分）有甲、乙、丙、丁四個(gè)人，要分別指派他們完成 A B、G D四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示:ABCD甲21097乙154148丙13141611丁415139問：應(yīng)該如何指派，才能使總的消耗時(shí)間為最少?解：用“匈牙利法”求解。效率矩陣表示為：21097行約簡he-087515414811010413141611 235041513901195列約簡標(biāo)號(0)8211(0)523(0)*01240134(0)6(0)310(0)5至此已得最優(yōu)解:000101001000(0)30010使總消耗時(shí)間為最少的分配任務(wù)方案為:甲7C,乙f B,丙f D, 丁7 A此時(shí)總消耗時(shí)間W=9+4+11+4=28七、（6分）計(jì)算下圖所示的網(wǎng)絡(luò)從 A點(diǎn)到