《運籌學(xué)》試題參考答案

工商管理03級（本）已考《運籌學(xué)》試題參考答案資料加工、整理人楊玲（函授總站高級講師）※考試提示：可帶計算器，另外建議帶上鉛筆、直尺、橡皮，方便繪圖或分析。一、填空題（每空2分，共10分）1、在線性規(guī)劃問題中，稱滿足所有約束條件方程和非負(fù)限制的解為可行解。2、在線性規(guī)劃問題中，圖解法適合用于處理變量為兩個的線性規(guī)劃問題。3、求解不平衡的運輸問題的基本思想是設(shè)立虛供地或虛需求點，化為供求平衡的標(biāo)準(zhǔn)形式4、在圖論中，稱無圈的連通圖為樹。5、運輸問題中求初始基本可行解的方法通常有最小費用法、西北角法兩種方法。二、（每小題5分，共10分）用圖解法求解下列線性規(guī)劃問題：TOC\o"1-5"\h\z1）maxz=6xj4x2 ⑴\o"CurrentDocument"'2x+x<10 ⑵1 2\o"CurrentDocument"x+x<8 ⑶<1 2x<7 ⑷2[x1，x2>0 ⑸、⑹解：此題在《運籌學(xué)》復(fù)習(xí)參考資料網(wǎng)”中已有，不再重復(fù)。2）minz=—3X1+2X2 ⑴⑵⑶⑷⑸⑹、⑺

2x+4x<2212-x+4x<101212x-x<72x-3x<12x,x>012解：可行解域為abcda可行解域為abcda,最優(yōu)解為b點。I2x+4x=22由方程組11 「Ix二0i 2x1x2=x1x2=(11,0)T???X*=I???minz=—3x11+2X0=—33三、（15分）某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要A、B、C三種資源，每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷售后所能獲得的利潤值以及這三種資源的儲備如下表所示：ABC甲94370乙46101203602003001）建立使得該廠能獲得最大利潤的生產(chǎn)計劃的線性規(guī)劃模型；（5分）2）用單純形法求該問題的最優(yōu)解。（10分）解：1）建立線性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為X1、x2,則x1、X2三0,設(shè)z是產(chǎn)品售后的總利潤，則maxz=70x1+120x2s.t.。x+4x<3601 24x+6x<200V1 23x+10x<30012x,x>0122）用單純形法求最優(yōu)解：加入松弛變量x3,x4,x5,得到等效的標(biāo)準(zhǔn)模型：maxz=70x1+120x2+0x3+0x4+0x5s.t.TOC\o"1-5"\h\z9x+4x+x=3601 2 34x+6x +x=2001 2 43x+10x +x=3001 2 5%—0,j=1,2,…5k/列表計算如下:

CBXBb701200000L0X336094100900X420046010100/30X53003(10)001300000070120t0000X324039/5010-2/5400/130X420(11/5)001-3/5100/11120X2303/101001/1010036120001234t000—120X31860/11001—39/1119/1170X1100/111005/11-3/11120X2300/11010-3/222/1143000701200170/1130/1111000-170/11—30/11.?.X*=(100,300,I860,0,0)T11 11 11??.maxz=70義100+120義300=4300011 11 11四、（10分）用大M法或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€性規(guī)劃模型:minz=5x1＋2x2＋4x33x+x+2x>4123<6x+3x+5x>1023x,x,x>0123

解：用大M法，先化為等效的標(biāo)準(zhǔn)模型:maxz/=－5x－2x－4x123s.t.3x+x+2x一x=42 3 4<6x+3x+5x -x=10235y>0,j=1,2,…5j增加人工變量x6、x7,得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7+x+x=46+x=1073x+x+2x-x1 2 3 4<6x+3x+5x23x>0,j=1,2,…,7j大M法單純形表求解過程如下:

CBXBb—5x1—2x2—4x30x40x5—Mx6—Mx70L-Mx64(3)12—10104/3-Mx7106350—1015/3—9M—4M—7MMM—M—M9M—5t4M—27M—4—M—M00一5x14/311/32/3—1/301/30—Mx72011(2)—1—211一5-M—5/3-M—10/3-2M+5/3M2M—5/3-M0M—1/3M—2/32M—5/3t—M—3M+5/30—5x15/311/25/60—1/601/610/30x410(1/2)1/21—1/2—11/22—5—5/2—25/605/60—5/601/2t1/60—5/6—M—M+5/6—5x12/3101/3—11/31—1/3—2x220112—1—2122—5—2—11/311/3—1—1/3T00—1/3—1—1/3—M+1—M+1/3「?x*=(23，2，0，0，0)T最優(yōu)目標(biāo)函數(shù)值minz=—maxz/=一（—五）=22

3 3

五、（15分）給定下列運輸問題：（表中數(shù)據(jù)為產(chǎn)地Aj到銷地Bj的單位運費）B2B3B4s.iA1123410A2876580A391011915d.j82212181）用最小費用法求初始運輸方案，并寫出相應(yīng)的總運費；（5分）2）用1）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。1）先用最小費用法（最小元素法）求此問題的初始基本可行解：

20Z=1X8+2X2+6X2+5X18+10X20+11X10=42434 j?,?選x作為入基變量迭代調(diào)整。34②用表上閉回路法進(jìn)行迭代調(diào)整：費\銷7\地^地^BiB2B3B4SiAi123一14-31082XXA28-37一16520XX128

A3901011一1930X20X10dj82212186060調(diào)整后，從上表可看出，所有檢驗數(shù)OW0,已得最優(yōu)解。j?,?最優(yōu)方案為:最小運費Z=1X8+2X2+6X12+5X8+10X20+9X10=414六、（8分）有甲、乙、丙、丁四個人，要分別指派他們完成A、B、C、D四項不同的工作，每人做各項工作所消耗的時間如下表所示：ABCD甲21097乙154148丙13141611丁415139問應(yīng)該如何指派，才能使總的消耗時間為最少？解用“匈牙利法”求解。效率矩陣表示為：[21510 94147：8行約簡[011807105、4列約簡1 131416112350標(biāo)號1415139J101195J，(0)112、0*8

(0)31225(0)4,(0) 8 2 5、 (Q) 5 —2 3——(0)——0*-「)* 12 4 5,至此已得最優(yōu)解:TOC\o"1