運(yùn)籌學(xué) 試卷及答案 卷4

課程名稱:運(yùn)籌學(xué)課程名稱:運(yùn)籌學(xué)題號(hào)一二三四五六七八九十總分得分評(píng)分人一、（10分）寫(xiě)出下面線性規(guī)劃的標(biāo)準(zhǔn)形式和對(duì)偶規(guī)劃：二、（20分）用單純形法求解；并考慮若目標(biāo)函數(shù)的系數(shù)變?yōu)镃=(3,0.5)T后，最優(yōu)解的變化情況。三、（15分）運(yùn)用表上作業(yè)法求解下列運(yùn)輸問(wèn)題，表格中間的數(shù)字為運(yùn)價(jià)。產(chǎn)銷(xiāo)甲乙丙丁產(chǎn)量A413610B23616C37518銷(xiāo)量4938學(xué)院：專業(yè)：學(xué)號(hào)：姓名：裝訂線四、（15分）有5個(gè)工人，要指派去做5項(xiàng)工作，每人做各項(xiàng)工作的能力見(jiàn)下表。應(yīng)如何指派，才能使總的得分最大？業(yè)務(wù)工人J1J2J3J4J5S1S2S3S4S51.50.51.00.71.20.51.101.20.90.31.31.300.800.80.51.30.91.21.00.60.81.2五、（25分）下圖為一網(wǎng)絡(luò)圖，邊上數(shù)字為邊的容量或者長(zhǎng)度：求從頂點(diǎn)1到頂點(diǎn)8的最大流（10分）；用Dijkstra算法求解從頂點(diǎn)1到頂點(diǎn)8最短路（8分）；畫(huà)出最小生成樹(shù)（7分）。VV1V2V4V3V5V7V6V85671446459754在如下的網(wǎng)絡(luò)中，從起點(diǎn)A到終點(diǎn)G分六個(gè)階段，每個(gè)階段各有若干條可選擇的道路，每條道路的長(zhǎng)度如下圖所示。試確定從A點(diǎn)到G點(diǎn)的最短路線。（15分）《運(yùn)籌學(xué)》參考答案及評(píng)分細(xì)則（15分）寫(xiě)出下面線性規(guī)劃的標(biāo)準(zhǔn)形式和對(duì)偶規(guī)劃則標(biāo)準(zhǔn)形式為：設(shè)對(duì)偶變量分別為y1，y2，y3，則對(duì)偶規(guī)劃為：解：首先寫(xiě)出線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式2分Cj→32000θCBXBbx1x2x3x4x50x341110040x42-11010-0x518[6]20013δj32000（2分）0x310[2/3]10-1/63/20x4504/3011/615/43x1311/3001/69δj0100-1/2（3分）2x23/2013/20-1/40x4300-211/23x15/210-1/201/4δj00-3/20-1/4（3分）此時(shí)，原問(wèn)題得到最優(yōu)解為X*=(5/2，3/2，0，3，0)T，maxZ＝21/2（2分）當(dāng)目標(biāo)函數(shù)系數(shù)變?yōu)椋?，0.5）時(shí)，把新系數(shù)帶入最終單純型表：Cj→30.5000θCBXBbx1x2x3x4x50.5x23/201[3/2]0-1/410x4300-211/2-3x15/210-1/201/4-δj003/40-5/8（3分）0x3102/310-1/60x4504/3011/63x1311/3001/6δj0-1/200-1/2（3分）所以新的最優(yōu)解為X*=(3，0，1，5，0)T，maxZ＝9（2分）三、解：方法一：（1）用最小元素法求得初始解，并計(jì)算檢驗(yàn)數(shù)如下：甲乙丙丁產(chǎn)量uiA（3）91（7）100B（-1）（0）（1）662C4（4）2282銷(xiāo)量493824vj113-1（初始方案5分，位勢(shì)2分，檢驗(yàn)數(shù)（括號(hào)中數(shù)字）2分）（2）因?yàn)棣?4<0，所以此方案不是最優(yōu)方案，調(diào)整的新方案并計(jì)算新檢驗(yàn)數(shù)：甲乙丙丁產(chǎn)量uiA（4）91（7）100B4（0）（1）262C（1）（4）2682銷(xiāo)量493824vj013-1（新方案3分，位勢(shì)1分，檢驗(yàn)數(shù)1分）因?yàn)樗笑襥j≥0，所以此解為最優(yōu)解，又因?yàn)橛蟹腔兞繖z驗(yàn)數(shù)δ31＝0，所以該問(wèn)題有多個(gè)最優(yōu)解。其中一個(gè)最優(yōu)解為：A-乙：9，A-丙：1，B-甲：4，B-丁：2，C-丙：2，C-?。?；最小運(yùn)費(fèi)z=9×1+1×3+4×2+2×1+2×5+6×1＝38。（1分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評(píng)分標(biāo)準(zhǔn)：沃格爾法求得初始方案10分，檢驗(yàn)數(shù)4分，結(jié)果1分）四、解：首先變成最小化指派問(wèn)題。B=(1.5-Cij)5×5（2分）行減（2分）行減（2分）試指派4分，劃直線2分調(diào)整（2分）調(diào)整（2分）再指派2分即：S1→J1，S2→J2，S3→J3，S4→J4，S5→J5此時(shí)總得分W=1.5+1.1+1.3+1.3+1.2=6.4（1分）五、解：（1）求最大流：增廣鏈流量調(diào)整量V1→V2→V4→V6→V84V1→V3→V5→V7→V81（4分）所以最大流量為：4+1=5（1分）最大流量圖為：VV1V2V4V3V5V7V6V8(5,0)(6,1)(7,1)(1,1)(4,0)(4,0)(6,1)(4,4)(5,4)(9,4)(7,0)(5,0)(4,4)（5分）（2）求最短路。標(biāo)號(hào)如下圖66(8,8)(14,14)V1V2V4V3V5V7V6V8571446459754(4,4)(9,9)(13,13)(6,6)(17,15)（6分）所以V1到V8的最短路長(zhǎng)為15。路徑為：V1→V2→V5→V7→V8。（2分）（3）求最小樹(shù)。最小樹(shù)如下圖：VV1V2V4V3V5V7V6V85144454（6分）最小樹(shù)的權(quán)數(shù)為：5+5+4+4+4+4+1=27（1分）六、解：逆序法標(biāo)號(hào)(13)(13)(16)(18)(13)(10)(9)(12)(8)(