運籌學(xué)3卷答案

《運籌學(xué)》參考答案及評分細(xì)則（15分）寫出下面線性規(guī)劃的標(biāo)準(zhǔn)形式和對偶規(guī)劃2分則標(biāo)準(zhǔn)形式為：設(shè)對偶變量分別為y1，y2，y3，則對偶規(guī)劃為：二、解：首先寫出線性規(guī)劃問題的標(biāo)準(zhǔn)形式2分Cj→35200θCBXBbx1x2x3x4x50x47212107/10x561[3]4016/3δj35200（3分）0x455/303/21-1/335x221/314/301/36δj4/30-14/30-5/3（5分）3x13105/23/5-1/55x21016/5-1/52/5δj00-26/5-4/5-7/5（4分）此時，原問題得到最優(yōu)解為X*=(3，1，0，0，0)T，maxZ＝14（1分）當(dāng)目標(biāo)函數(shù)系數(shù)變?yōu)椋?，1，3）時，把新系數(shù)帶入最終單純型表：Cj→21300θCBXBbx1x2x3x4x52x13102/53/5-1/515/21x2101[6/5]-1/52/55/6δj001-10（2分）2x18/31-1/302/3-1/33x35/605/61-1/61/3δj0-5/60-5/6-1/3（2分）所以最優(yōu)解為X*=(8/3，0，5/6，0，0)T，maxZ＝47/6三、解：方法一：（1）用最小元素法求得初始解，并計算檢驗數(shù)如下：甲乙丙丁產(chǎn)量uiA（1）（2）4370B3（1）1（-1）4-1C（10）6（12）39-5銷量365620vj29310（初始方案5分，位勢2分，檢驗數(shù)2分）（2）因為σ24<0，所以此方案不是最優(yōu)方案，調(diào)整的新方案并計算新檢驗數(shù)：甲乙丙丁產(chǎn)量uiA（0）（2）5270B3（2）（1）14-2C（9）6（12）39-5銷量365620vj39310（新方案3分，位勢1分，檢驗數(shù)1分）因為所有σij≥0，所以此解為最優(yōu)解，又因為有非基變量檢驗數(shù)δ31＝0，所以該問題有多個最優(yōu)解。其中一個最優(yōu)解為：A-丙：5，A-?。?，B-甲：3，B-?。?，C-乙：6，C-?。?；最小運費z=5×3+2×10+3×1+1×8+6×4+3×5＝85。（1分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評分標(biāo)準(zhǔn)：沃格爾法求得初始方案10分，檢驗數(shù)4分，結(jié)果1分）四、解：用“匈牙利法”求解試指派（6分）列減試指派（6分）列減（3分）行減（4分）所以最優(yōu)解為z*=即：丙→1，甲→2，乙→3，，丁→4（1分）此時總時間W=3+5+5+6=19（1分）五、解：13133327V1V31V4V6V7（6分）最小樹總權(quán)為：7+3+3+3+1+2=19（2分）2、求最大流：增廣鏈流量調(diào)整量V1→V4→V6→V74V1→V2→V3→V5→V73V1→V2→V5→V71（9分）V1→V3→V6→V73V1→V4→V3→V6→V71V1→V4→V3→V5→V71V1→V4→V3→V6→V5→V71所以最大流量為：4+3+1+3+1+1+1=14（1分）最大流量圖為：VV2(4,4)(3,3)(4,3)(3,3)(10,7)(1,1)(3,3)(5,5)(4,4)(2,1)(7,6)(8,6)V1V31V4V5V6V7（3分）((24)六、解：方法一：（逆序法標(biāo)號）AAB1B2B3C1C3C2D1D2E1025115137105675713414(18)(18)(26)(0)(1)(4)(8)(8)(9)(24)（10分）所以A到E最長路為26，路徑為A→B1→C1→D2→E（5分）方法二：（順序法標(biāo)號）AAB1B2B3C1C3C2D1D2E1025115137105675713414(5)(1)(0)(26)(24)(22)(15)(10)(17)(2)