双语运筹学B答案.docVIP

标准答案及评分标准 B卷 Single Choice（本大题共 小题，每小题 1 分，总计 分） Translation（本大题共小题，每个分，共分） Modeling（本大题共 2 小题，总计 1 分） x1、x2，设总利润为z，则有： max z = 2 x1 + x2 （10分） 解：12：00休息全日制职员人数y1，13：00休息为 y2，非全日制职员六批次人数分别为x1，x2，x3，x4，x5，x6 minZ=240（y1+y2）+80(x1+x2+x3+x4+x5+x6) y1+y2+x1≥4 y1+y2+x1+x2≥5 y1+y2+x1+x2+x3≥6 y2 +x2+x3+x4≥6 y1+x3+x4+x5≥5 y1+y2+x4+x5+x6≥6 y1+y2+x5+x6≥8 y1+y2+x7≥8 y1,y2,x1,x2,x3,x4,x5,x6≥0 Write out dual problem of following LP（本大题 分） Converted the problems into general constraint using 0-1（本大题 分）x=0x1+3x2+5x3+7x4 x1+x2+x3+x4=1 xi=0或1，i=1,2,3,4≥50 解：X≥50-My1 X=3+ My2 y1+y2=1 y1,y2≥0 Solution（本大题共 小题，总计 1 分） A 300 15 100 17 22 400 2 5 B 20 150 24 350 16 500 4 8 需要量 300 250 350 5 7 6 7 6 （2）逐次给出分配方案并采用闭回路法进行最优性检验（5分） 城市 煤矿 甲 乙 丙 供应量 A 15 17 13 22 400 B -2 20 24 16 500 需要量 300 250 350 城市 煤矿 甲 乙 丙 供应量 A 150 15 250 17 22 400 B 150 20 0 24 350 16 500 需要量 300 250 350 对于“A丙”空格，△z＝22－15＋20－16＝11，检验数大于0； 对于“B乙”空格，△z＝24－17＋15－20＝2，检验数大于0 得最优解，运费为15100元，该方案即最优方案。（2分） 解： （2分） （5分） 即：（2分） 指派问题的解为：1+2+2+2+2=9 （1分） 解：（1）最小树为图中双线所示 （8分） （2）最小树长14（2分） 解： （4分） 由于所有点都被标号即可以找到增广链，所以流量还可以调整，调整量为1， （4分） 由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为?(vs,v1), ( vs,v3), ( v2,v5)，所以从vs到vt的最大流为fst=5+3+5=13 （1分） - 3 - 3 V3 V5 2 V1 5 3 V6 2 5 6 V2 V4 4 5