运筹学3卷答案

《运筹学》参考答案及评分细则（15分）写出下面线性规划的标准形式和对偶规划2分则标准形式为：设对偶变量分别为y1，y2，y3，则对偶规划为：二、解：首先写出线性规划问题的标准形式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分）此时，原问题得到最优解为X*=(3，1，0，0，0)T，maxZ＝14（1分）当目标函数系数变为（2，1，3）时，把新系数带入最终单纯型表：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分）所以最优解为X*=(8/3，0，5/6，0，0)T，maxZ＝47/6三、解：方法一：（1）用最小元素法求得初始解，并计算检验数如下：甲乙丙丁产量uiA（1）（2）4370B3（1）1（-1）4-1C（10）6（12）39-5销量365620vj29310（初始方案5分，位势2分，检验数2分）（2）因为σ24<0，所以此方案不是最优方案，调整的新方案并计算新检验数：甲乙丙丁产量uiA（0）（2）5270B3（2）（1）14-2C（9）6（12）39-5销量365620vj39310（新方案3分，位势1分，检验数1分）因为所有σij≥0，所以此解为最优解，又因为有非基变量检验数δ31＝0，所以该问题有多个最优解。其中一个最优解为：A-丙：5，A-丁：2，B-甲：3，B-丁：3，C-乙：6，C-丁：3；最小运费z=5×3+2×10+3×1+1×8+6×4+3×5＝85。（1分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果1分）四、解：用“匈牙利法”求解试指派（6分）列减试指派（6分）列减（3分）行减（4分）所以最优解为z*=即：丙→1，甲→2，乙→3，，丁→4（1分）此时总时间W=3+5+5+6=19（1分）五、解：13133327V1V31V4V6V7（6分）最小树总权为：7+3+3+3+1+2=19（2分）2、求最大流：增广链流量调整量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)六、解：方法一：（逆序法标号）AAB1B2B3C1C3C2D1D2E1025115137105675713414(18)(18)(26)(0)(1)(4)(8)(8)(9)(24)（10分）所以A到E最长路为26，路径为A→B1→C1→D2→E（5分）方法二：（顺序法标号）AAB1B2B3C1C3C2D1D2E1025115137105675713414(5)(1)(0)(26)(24)(22)(15)(10)(17)(2)