去年《運(yùn)籌學(xué)》試題參考答案

去年《運(yùn)籌學(xué)》試題參考答案資料加工、整理人——楊峰（函授總站高級(jí)講師）一、填空題（每空2分，共10分）1、在線性規(guī)劃問(wèn)題中，稱滿足所有約束條件方程和非負(fù)限制的解為可行解。2、在線性規(guī)劃問(wèn)題中，圖解法適合用于處理變量為兩個(gè)的線性規(guī)劃問(wèn)題。3、求解不平衡的運(yùn)輸問(wèn)題的基本思想是設(shè)立虛供地或虛需求點(diǎn)，化為供求平衡的標(biāo)準(zhǔn)形式。4、在圖論中，稱無(wú)圈的連通圖為樹(shù)。5、運(yùn)輸問(wèn)題中求初始基本可行解的方法通常有最小費(fèi)用法、西北角法兩種方法。5分，共10分）用圖解法求解下列線性規(guī)劃問(wèn)題：1）maxz=6x+4x⑴122xx⑵12xx8⑶12x7⑷2xx01⑸、⑹2解：此題在“.doc”中已有，不再重復(fù)?！哆\(yùn)籌學(xué)》復(fù)習(xí)參考資料2）minz3x+2x122x4x22⑵12x4x10⑶122xx7⑷12x3x1⑸12,0xx⑹、⑺12第1頁(yè)共11頁(yè)解：x2⑷⑹8⑵⑶⑸c→0x⑺1-10→－-8可行解域?yàn)閍bcda，最優(yōu)解為b點(diǎn)。2x4x22由方程組12解出xx=0x0122x∴X=1=（110）*Tx2∴minz－3×11×0－3315分）某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要、B、C三種資源，每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷(xiāo)售后所能獲得的利潤(rùn)值以及這三種資源的儲(chǔ)備如下表所示：ABC甲乙94346第2頁(yè)共11頁(yè)15分）210分）解：）建立線性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為xx，則xx0，設(shè)z是產(chǎn)品售后的總利1212潤(rùn)，則maxz=70x+120x12s.t.9x4x360126x2004x123x10x30012x，x0122）用單純形法求最優(yōu)解：加入松弛變量xx，x，得到等效的標(biāo)準(zhǔn)模型：345maxz=70x+120x+0x+0x+0x41235s.t.9x4xx3602001234x6xx1243x10xx300125xjj列表計(jì)算如下：第3頁(yè)共11頁(yè)θbxxxBL1234590345342120－39/11312701204300011700120000-170/11－30/111003001860∴X（，，，0，0）*T11111110030043000∴maxz×+120×=11111110分）用大M法或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€性規(guī)劃模型：maxz=5x2x4x1233xx2x41236x3x5x10123x,x,x0123第4頁(yè)共11頁(yè)解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxz=－5x－2x－4x/123s.t.324x10xxxx12346x3x5x1235yjj增加人工變量xx，得到：67maxz=－5x－2x－4xMx－x/12367s.t32x4xxxx123466x3x5xxx1012357xjj大M法單純形表求解過(guò)程如下：第5頁(yè)共11頁(yè)θbLxxxxxxx123456767－4M－7MM21/3142/311701M0010214M11120－20－11/3－1/32230－1－1/3－+1+1/3M2∴x（，2，0，0）*T322223最優(yōu)目標(biāo)函數(shù)值minz－max/－（－）=3AB15到銷(xiāo)地的單位運(yùn)費(fèi)）ij第6頁(yè)共11頁(yè)12311089765801510119dj822121815分）2）用110分）解：用“表上作業(yè)法”求解。1）先用最小費(fèi)用法（最小元素法）求此問(wèn)題的初始基本可行解：費(fèi)銷(xiāo)用BBBBSi地1234產(chǎn)地1893645912382××6060dj8∴初始方案：BBBBB822010123423AAA123218BZ=18+22+62+518+1020+1110=424第7頁(yè)共11頁(yè)2）①用閉回路法，求檢驗(yàn)數(shù)：費(fèi)銷(xiāo)BBBBSi用地1234產(chǎn)地1893645912382××××2××60dj860∵=1＞0，其余≤034j∴選作為入基變量迭代調(diào)整。x34②用表上閉回路法進(jìn)行迭代調(diào)整：費(fèi)銷(xiāo)BBBBSi用地1234產(chǎn)地1893645912382×××××6060dj8調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)≤0，已得最優(yōu)解。j∴最優(yōu)方案為：第8頁(yè)共11頁(yè)BBBBBB821282010123424AAA123最小運(yùn)費(fèi)Z=182+612+5820+910=4148分）有甲、乙、丙、丁四個(gè)人，要分別指派他們完成CD四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示：C9D7甲乙丙丁151341416131415119問(wèn)：應(yīng)該如何指派，才能使總的消耗時(shí)間為最少？解：用“匈牙利法”求解。效率矩陣表示為：2944702875580411305909√(0)1128(0)3254(0)11255(0)340*5(0)40*5(0)4√0*120*12第9頁(yè)共11頁(yè)0*6(0)53134(0)340*2(0)3(0)10000101001000001至此已得最優(yōu)解：0∴使總消耗時(shí)間為最少的分配任務(wù)方案為：甲→C，乙→B，丁→A此時(shí)總消耗時(shí)間W=9+4+11+4=286分）計(jì)算下圖所示的網(wǎng)絡(luò)從A點(diǎn)到F點(diǎn)的最短路線及其長(zhǎng)度。此題在“.doc”中已有。9BCD4111523EE48165ABCDF2229421474572BCD333第10頁(yè)共11頁(yè)549BCD4111123E819065ABCDF22297E