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

《運(yùn)籌學(xué)》參考答案及評分細(xì)則（15分）寫出下面線性規(guī)劃的標(biāo)準(zhǔn)形式和對偶規(guī)劃則標(biāo)準(zhǔn)形式為：設(shè)對偶變量分別為y1，y2，y3，則對偶規(guī)劃為：解：首先寫出線性規(guī)劃問題的標(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分）此時，原問題得到最優(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ù)帶入最終單純型表：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銷量493824vj113-1（初始方案5分，位勢2分，檢驗(yàn)數(shù)（括號中數(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銷量493824vj013-1（新方案3分，位勢1分，檢驗(yàn)數(shù)1分）因?yàn)樗笑襥j≥0，所以此解為最優(yōu)解，又因?yàn)橛蟹腔兞繖z驗(yàn)數(shù)δ31＝0，所以該問題有多個最優(yōu)解。其中一個最優(yōu)解為：A-乙：9，A-丙：1，B-甲：4，B-?。?，C-丙：2，C-?。?；最小運(yùn)費(fèi)z=9×1+1×3+4×2+2×1+2×5+6×1＝38。（1分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評分標(biāo)準(zhǔn)：沃格爾法求得初始方案10分，檢驗(yàn)數(shù)4分，結(jié)果1分）四、解：首先變成最小化指派問題。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此時總得分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)號如下圖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分）最小樹的權(quán)數(shù)為：5+5+4+4+4+4+1=27（1分）六、解：逆序法標(biāo)號(13)(13)(16)(18)(13)(10)(9)(12)(8)(6)(7)(3)(4)(7)(5)(9)(0)