∑∑ 4.对于极大化问题maxZ=1=1=1 c=mx,}b=c-c转化为极小化向 mnW=∑∑bx 题 则利用匈牙利法求解时,极大化问题的最优解就是极小化 问题的最优解,但目标函数相差:n+c; 5.如果图中从v至各点均有惟一的最短路,则连接至其他各点的最短路在去掉重复部 分后,恰好构成该图的最小支撑树 试题二答案 、解:设x代表第i月正常生产的柴油机数量, y代表第i月加班生产的柴油机数量, 2代表第i月末的库存量,则=1=4 minz=500Cx+6500∑y+200∑ x1+y1≥3000 二1+x2+y2≥4500 22+x3+y3 ≥3500 3+x4+y4=5000 x2,y1,-≥0,i=1,2,3,4 解: min W=5y,+2y2 y1+2y2≥5 2y1-y2≥12 y1+3y2≥4 1、对偶模型 y≥0,y2无约束 2、由单纯形表可看出 y1*=+(-3)=3由于 yn×x1=0,y2×x2=0,而x1≠0,x2≠0 ya=0,y2=0 则对偶问题的第一、二个约束是紧的,可解出2=-3 将M1,y2代入第三个约束,满足约束条件,则y*=(y,y2)=(普,-3w*=均 3、5和2 2/5-1/5 4、B-1=(1/52/5 5、如果原问题增加一个变量,则对偶问题就增加一个约束条件,它的可行域要么减少,4. 对于极大化问题 max Z = ij n i n j ij c x =1 =1 …令  ij  ij ij c = max c ,b = c − c 转化为极小化问 题 ij n i n j ij W b x = = = 1 1 min ，则利用匈牙利法求解时，极大化问题的最优解就是极小化 问题的最优解，但目标函数相差： n+c； 5. 如果图中从 i v 至各点均有惟一的最短路，则连接至其他各点的最短路在去掉重复部 分后，恰好构成该图的最小支撑树。 试题二答案 一、解：设 i x 代表第 i 月正常生产的柴油机数量， i y 代表第 i 月加班生产的柴油机数量， i z 代表第 i 月末的库存量，则 i z =4 , , 0, 1,2,3,4 5000 3500 4500 3000 min 5000 6500 200 3 4 4 2 3 3 1 2 2 1 1 4 1 4 1 4 1  = + + = + +  + +  +  =  +  +  = = = x y z i z x y z x y z x y x y Z x y z i i i i i i i i i 二、解： 1、 对偶模型 1 2无约束 1 2 1 2 1 2 1 2 0, 3 4 2 12 2 5 min 5 2 y y y y y y y y W y y  +  −  +  = + 2、 由单纯形表可看出， 5 29 5 29 1 y * = −(− ) = 由 于 0, 0 0; 0, 0, 0 1 2 1 1 2 2 1 2  = =  =  =   s s s s y y y x y x 而x x 则对偶问题的第一、二个约束是紧的，可解出 5 2 y2 = − 将 1 2 y , y 代入第三个约束，满足约束条件，则 5 141 5 2 5 29 y* = ( y1 , y2 ) = ( ,− ),w* = T 3、5 和 2 4、 = −1 B         − 1/ 5 2 / 5 2 / 5 1/ 5 5、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少