運籌學 試卷及答案 卷4

課程名稱:運籌學課程名稱:運籌學題號一二三四五六七八九十總分得分評分人一、（10分）寫出下面線性規(guī)劃的標準形式和對偶規(guī)劃：二、（20分）用單純形法求解；并考慮若目標函數(shù)的系數(shù)變?yōu)镃=(3,0.5)T后，最優(yōu)解的變化情況。三、（15分）運用表上作業(yè)法求解下列運輸問題，表格中間的數(shù)字為運價。產(chǎn)銷甲乙丙丁產(chǎn)量A413610B23616C37518銷量4938學院：專業(yè)：學號：姓名：裝訂線四、（15分）有5個工人，要指派去做5項工作，每人做各項工作的能力見下表。應如何指派，才能使總的得分最大？業(yè)務工人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)絡圖，邊上數(shù)字為邊的容量或者長度：求從頂點1到頂點8的最大流（10分）；用Dijkstra算法求解從頂點1到頂點8最短路（8分）；畫出最小生成樹（7分）。VV1V2V4V3V5V7V6V85671446459754在如下的網(wǎng)絡中，從起點A到終點G分六個階段，每個階段各有若干條可選擇的道路，每條道路的長度如下圖所示。試確定從A點到G點的最短路線。（15分）《運籌學》參考答案及評分細則（15分）寫出下面線性規(guī)劃的標準形式和對偶規(guī)劃則標準形式為：設對偶變量分別為y1，y2，y3，則對偶規(guī)劃為：解：首先寫出線性規(guī)劃問題的標準形式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分）此時，原問題得到最優(yōu)解為X*=(5/2，3/2，0，3，0)T，maxZ＝21/2（2分）當目標函數(shù)系數(shù)變?yōu)椋?，0.5）時，把新系數(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）用最小元素法求得初始解，并計算檢驗數(shù)如下：甲乙丙丁產(chǎn)量uiA（3）91（7）100B（-1）（0）（1）662C4（4）2282銷量493824vj113-1（初始方案5分，位勢2分，檢驗數(shù)（括號中數(shù)字）2分）（2）因為σ24<0，所以此方案不是最優(yōu)方案，調整的新方案并計算新檢驗數(shù)：甲乙丙丁產(chǎn)量uiA（4）91（7）100B4（0）（1）262C（1）（4）2682銷量493824vj013-1（新方案3分，位勢1分，檢驗數(shù)1分）因為所有σij≥0，所以此解為最優(yōu)解，又因為有非基變量檢驗數(shù)δ31＝0，所以該問題有多個最優(yōu)解。其中一個最優(yōu)解為：A-乙：9，A-丙：1，B-甲：4，B-?。?，C-丙：2，C-丁：6；最小運費z=9×1+1×3+4×2+2×1+2×5+6×1＝38。（1分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評分標準：沃格爾法求得初始方案10分，檢驗數(shù)4分，結果1分）四、解：首先變成最小化指派問題。B=(1.5-Cij)5×5（2分）行減（2分）行減（2分）試指派4分，劃直線2分調整（2分）調整（2分）再指派2分即：S1→J1，S2→J2，S3→J3，S4→J4，S5→J5此時總得分W=1.5+1.1+1.3+1.3+1.2=6.4（1分）五、解：（1）求最大流：增廣鏈流量調整量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）求最短路。標號如下圖66(8,8)(14,14)V1V2V4V3V5V7V6V8571446459754(4,4)(9,9)(13,13)(6,6)(17,15)（6分）所以V1到V8的最短路長為15。路徑為：V1→V2→V5→V7→V8。（2分）（3）求最小樹。最小樹如下圖：VV1V2V4V3V5V7V6V85144454（6分）最小樹的權數(shù)為：5+5+4+4+4+4+1=27（1分）六、解：逆序法標號(13)(13)(16)(18)(13)(10)(9)(12)(8)(