要么不变,绝对不会变大 、解:此题可看作指派问题求解: 584 1012 467 000 100 优解x21=1,412=Nx3=1,其余为0Z*=19 四、解:将最大化问题化为极小化问题,并将系数转为正,即令x=1-x,整理得 mnz=5x1+7x,+10x2+3x4+x-26 x1-3x2+5x3+x4-4xs≤-2 x1+6x2-3x3-2x4+2x5≤l 2x2+2x3-x4-xs≤-3 0或l( 综上,该0-1规划无可行解 五、解:按三个变量划分为三个阶段,状态转移方程 f(s3)=mx{x3}=,x3*=S2 0≤x3≤S3 第二阶段。(3)=mx(s)=mm(2-x)=s2 0≤x2sS20≤x2SS2 其中 f()=mx41×s2}=mxx×(2-x1)= 0≤x1≤2 0≤x1≤2 其中x*=3 最优解x1* 六、解:依题意,首先给出一个可行流要么不变，绝对不会变大。 三、解：此题可看作指派问题求解： 5 6 10 1 2 5 0 1 4 0 0 3 8 10 12 ~ 4 6 7 ~ 0 2 3 ~ 0 1 2 4 4 5 0 0 0 0 0 0 1 0 0 最优解x21 =1, x12 =1, x33 =1,其余为0，Z* =19 四、解：将最大化问题化为极小化问题，并将系数转为正，即令 ' i 1 i x = − x ，整理得 0 1( 1,2, 5) 2 2 3 2 6 3 2 2 1 3 5 4 2 min 5 7 10 3 26 ' ' 5 ' 4 ' 3 ' 2 ' 5 ' 4 ' 3 ' 2 ' 1 ' 5 ' 4 ' 3 ' 2 ' 1 ' 5 ' 4 ' 3 ' 2 ' 1 ' ' ' = =  − + − −  − − + − − +  − + + −  − = + + + + − x j x x x x x x x x x x x x x x Z x x x x x j 或 0 1 2 3 4 5 6 7 8 9 10 11 12 1 ' x1 = 0 ' x1 = 1 ' x2 = 1 ' x3 = 0 ' x3 = 0 ' x2 = 1 ' x2 = 0 ' x2 = 1 ' x3 = 1 ' 0 x3 = ' x3 = 0 ' x3 = 综上，该 0-1 规划无可行解 五、解：按三个变量划分为三个阶段，状态转移方程 第三阶段： 3 3  3 3 3 * 2 f (s ) = max x = s , x = s 0 3 3  x s 第二阶段：     2 4 2 ' 1 2 2 ' 3 2 ' 2 2 2 f (s ) = max x (s ) = max x (s − x ) = s 2 ' 0 2  x  s 2 ' 0 2  x  s 其中 2 2 ' 1 x2 * = s ( 1 ) 2 ' 2 x = − x 第一阶段：     27 8 2 2 4 1 1 1 2 4 2 1 1 1 1 f (s ) = max x  s = max x  (2 − x ) = 0  x1  2 0  x1  2 其中 3 2 x1 * = 27 8 3 2 3 3 1 3 ' 2 3 2 2 2 1 * * , * 1 * 1 , * =  = = − = − = = Z 最优解x x x x 六、解：依题意，首先给出一个可行流