工商管理03級(jí)(本)已考運(yùn)籌學(xué)試題參考答案

工商管理03級(jí)（本）已考《運(yùn)籌學(xué)》試題參考答案資料加工、整理人——楊峰（函授總站高級(jí)講師）※考試提示：可帶計(jì)算器，另外建議帶上鉛筆、直尺、橡皮，方便繪圖或分析。一、填空題（每空2分，共10分）1、在線(xiàn)性規(guī)劃問(wèn)題中，稱(chēng)滿(mǎn)足所有約束條件方程和非負(fù)限制的解為可行解。2、在線(xiàn)性規(guī)劃問(wèn)題中，圖解法適合用于處理變量為兩個(gè)的線(xiàn)性規(guī)劃問(wèn)題。3、求解不平衡的運(yùn)輸問(wèn)題的基本思想是設(shè)立虛供地或虛需求點(diǎn)，化為供求平衡的標(biāo)準(zhǔn)形式。4、在圖論中，稱(chēng)無(wú)圈的連通圖為樹(shù)。5、運(yùn)輸問(wèn)題中求初始基本可行解的方法通常有最小費(fèi)用法、西北角法兩種方法。二、（每小題5分，共10分）用圖解法求解下列線(xiàn)性規(guī)劃問(wèn)題：

1）maxz=6x14x2解：此題在“《運(yùn)籌學(xué)》復(fù)習(xí)參考資料.doc”中已有，不再重復(fù)。

2）⑴minz=－3x12x2解：可行解域?yàn)閍bcda，最優(yōu)解為b點(diǎn)。由方程組解出x1=11，x2=0∴X*==（11，0）T∴minz=－3×112×0=－33三、（15分）某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要A、B、C三種資源，每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷(xiāo)售后所能獲得的利潤(rùn)值以及這三種資源的儲(chǔ)備如下表所示：ABC甲94370乙46101203602003001）建立使得該廠能獲得最大利潤(rùn)的生產(chǎn)計(jì)劃的線(xiàn)性規(guī)劃模型；（5分）2）用單純形法求該問(wèn)題的最優(yōu)解。（10分）解：1）建立線(xiàn)性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為x1、x2，則x1、x2≥0，設(shè)z是產(chǎn)品售后的總利潤(rùn)，則maxz=70x1120x2s.t.2）用單純形法求最優(yōu)解：加入松弛變量x3，x4，x5，得到等效的標(biāo)準(zhǔn)模型：maxz=70x1120x20x30x40x5s.t.列表計(jì)算如下：CBXBb70120000θLx1x2x3x4x50x336094100900x420046010100/30x53003（10）001300000070120↑0000x324039/5010-2/5400/130x420（11/5）001-3/5100/11120x2303/101001/1010036120001234↑000－120x31860/11001－39/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/11701200170/1130/11000-170/11－30/11∴X*=（，，，0，0）T∴maxz=70×120×=四、（10分）用大M法或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€(xiàn)性規(guī)劃模型：minz=5x1＋2x2＋4x3解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxz/=－5x1－2x2－4x3s.t.增加人工變量x6、x7，得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t大M法單純形表求解過(guò)程如下：CBXBb－5－2－400－M－MθLx1x2x3x4x5x6x7－Mx64（3）12－10104/3－Mx7106350－1015/3－9M－4M－7MMM－M－M9M－5↑4M－27M－4－M－M00－5x14/311/32/3－1/301/30——－Mx72011（2）－1－211－5-M－5/3-M－10/3-2M5/3M2M－5/3-M0M－1/3M－2/32M－5/3↑－M－3M5/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/2↑1/60－5/6－M－M5/6－5－2x12/3101/3－11/31－1/3x220112－1－21－－5－2－11/311/3－1－1/300－1/3－1－1/3－M1－M1/3∴x*=（，2，0，0，0）T最優(yōu)目標(biāo)函數(shù)值minz=－maxz/=－（－）=五、（15分）給定下列運(yùn)輸問(wèn)題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷(xiāo)地Bj的單位運(yùn)費(fèi)）B1B2B3B4siA1A2A312348765910119108015dj82212181）用最小費(fèi)用法求初始運(yùn)輸方案，并寫(xiě)出相應(yīng)的總運(yùn)費(fèi)；（5分）2）用1）得到的基本可行解，繼續(xù)迭代求該問(wèn)題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。1）先用最小費(fèi)用法（最小元素法）求此問(wèn)題的初始基本可行解：地產(chǎn)用費(fèi)地銷(xiāo)B1B2B3B4SiA112341082××A2876520××218A391011930×2010×dj82212186060

∴初始方案：Z=1×82×26×25×1810×2011×10=4242）①用閉回路法，求檢驗(yàn)數(shù)：地產(chǎn)用費(fèi)地銷(xiāo)B1B2B3B4SiA112304－21082××A28－47－26520××218A39010119130×2010×dj82212186060∵=1＞0，其余≤0∴選作為入基變量迭代調(diào)整。②用表上閉回路法進(jìn)行迭代調(diào)整：地產(chǎn)用費(fèi)地銷(xiāo)B1B2B3B4SiA1123－14－31082××A28－37－16520××128A3901011－1930×20×10dj82212186060調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)≤0，已得最優(yōu)解。∴最優(yōu)方案為：最小運(yùn)費(fèi)Z=1×82×26×125×810×209×10=414六、（8分）有甲、乙、丙、丁四個(gè)人，要分別指派他們完成A、B、C、D四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示：ABCD甲21097乙154148丙13141611丁415139問(wèn)：應(yīng)該如何指派，才能使總的消耗時(shí)間為最少？解：用“匈牙利法”求解。效率矩陣表示為：至此已得最優(yōu)解：∴使總消耗時(shí)間為最少的分配任務(wù)方案為：甲→C，乙→B，丙→D，丁→A此時(shí)總消耗時(shí)間W=94114=28七、（6分）計(jì)算下圖所示的網(wǎng)絡(luò)從A點(diǎn)到F點(diǎn)的最短路線(xiàn)及其長(zhǎng)度。此題在“《運(yùn)籌學(xué)參考綜合習(xí)題》（我站搜集信息自編）.doc”中已有。19245534168943526574145247解：此為動(dòng)態(tài)規(guī)劃之“最短路問(wèn)題”，可用逆向追蹤“圖上標(biāo)號(hào)法”解決如下：14451931245541490168594311726574142524712

87最佳策略為：A→B2→C1→D1→E2→F此時(shí)的最短距離為54122=14八、此題在“《運(yùn)籌學(xué)參考綜合習(xí)