運籌學4卷答案

《運籌學》參考答案及評分細則（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分）當目標函數系數變?yōu)椋?，0.5）時，把新系數帶入最終單純型表：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）用最小元素法求得初始解，并計算檢驗數如下：甲乙丙丁產量uiA（3）91（7）100B（-1）（0）（1）662C4（4）2282銷量493824vj113-1（初始方案5分，位勢2分，檢驗數（括號中數字）2分）（2）因為σ24<0，所以此方案不是最優(yōu)方案，調整的新方案并計算新檢驗數：甲乙丙丁產量uiA（4）91（7）100B4（0）（1）262C（1）（4）2682銷量493824vj013-1（新方案3分，位勢1分，檢驗數1分）因為所有σij≥0，所以此解為最優(yōu)解，又因為有非基變量檢驗數δ31＝0，所以該問題有多個最優(yōu)解。其中一個最優(yōu)解為：A-乙：9，A-丙：1，B-甲：4，B-?。?，C-丙：2，C-?。?；最小運費z=9×1+1×3+4×2+2×1+2×5+6×1＝38。（1分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評分標準：沃格爾法求得初始方案10分，檢驗數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分）最小樹的權數為：5+5+4+4+4+4+1=27（1分）六、解：逆序法標號(13)(13)(16)(18)(13)(10)(9)(12)(8)(6)(7)(3)(4)(7)(5)(9)(0)