运筹学作业题参考答案.docVIP

运筹学第五章作业题参考答案 5．1 解：设在A处建Ｘ幢住宅. 则数学模型为 Max z = 5.2 解：设每种毛坯截取Ｘ根 则数学模型为 Max z = 5.4 解：设X = 数学模型为：Max Z =( 1.92X+1.92X+…+1.78X)/5 5.6 用割平面法解下列整数规划 （1） Max Z = X + X s.t 解：将其化为标准型为 Max Z = X + X s.t 基 X X X X b X 2 1 1 0 6 X 4 5 0 1 20 -Z 1 1 0 0 X 1 1/2 1/2 0 3 X 0 3 -2 1 8 -Z 0 1/2 -1/2 0 X 1 0 5/6 -1/6 5/3 X 0 1 -2/3 1/3 8/3 -Z 0 0 -1/6 -1/6 从表中第二行产生割平面的约束条件： -1/3 X - 1/3 X 引入松弛变量X为： -1/3 X – 1/3 X + X=-2/3 基 X X X X X b X 1 0 5/6 -1/6 0 5/3 X 0 1 -2/3 1/3 0 8/3 X 0 0 -1/3 -1/3 1 -2/3 -Z 0 0 -1/6 -1/6 0 X 1 0 0 -1 5/2 0 X 0 1 0 1 -2 4 X 0 0 1 1 -3 2 -Z 0 0 0 0 -1/2 X 1 0 1 0 -1/2 2 X 0 1 -1 0 1 2 X 0 0 1 1 -3 2 -Z 0 0 0 0 -1/2 X=(0, 4) 或 ( 2, 2)， Z=4 (2) MinZ=5+X 解: 化为标准型为 max z=-5-X C -5 -1 0 0 0 C 基 b X X X X X 0 X -9 -3 -1 1 0 0 0 X -5 -1 -1 0 1 0 0 X -8 -1 -8 0 0 1 C-Z -5 -1 0 0 0 -1 X 9 3 1 -1 0 0 0 X 4 2 0 -1 1 0 0 X 64 23 0 -8 0 1 C-Z -2 0 -1 0 0 因此，原问题的最优解为X=( 0, 9 ) ，最优值Z = 9 5.7用分支定界法解下列整数规划 （1） Max Z=2X+X 解：用图解法求得该整数规划的松弛问题的最优解为 X=X=21/8 选择X=21/8进行分支 B1: B2: Max Z =2X+X Max Z =2X+X 最优解为X=2 X=3 Z=7； 最优解X=3 X= 3/2 Z=15/2 7 选择X= 3/2进行分支 B3 B4 Max Z =2X+X Max Z =2X+X 最优解为X=19/6 X=1 Z=22/3 7； 无可行解 选择X=19/6 进行分支 B5 B6 Max Z =2X+X 最优解为X=3 X=1 Z= 7； B6无可行解 综上：原整数规划最优解为 X= ( 2 , 3)或 ( 3 , 1) Z=7 5.8 解下列0~1型 整数规划： (2) Max Z =2X+X- X 解： （X1，X2, X3 ） Z值 约束条件 a b c d 过滤条件 （0， 0 ， 0 ） 0 ˇ ˇ ˇ ˇ Z0 （0， 0 ， 1 ） -1 （0， 1 ， 0 ） 1 （0， 1 ， 1 ） 0 （1， 0 ， 0 ） 2 ˇ ˇ ˇ ˇ Z2 （1， 0 ， 1 ） 1 （1， 1 ， 0 ） 3 （1， 1 ， 1 ） 2 最优解为X=(1 , 0 , 0 ) Z= 2 5.11（1） 解：引入一个虚拟人A,使之成为标准的指派问题，则系数矩阵为 C = 将各行元素减去本行的最小元素得 C = Cˊ 由于只有4个独立零元素，小于系数矩阵阶数n=5，所以将第二行，第三行，第四行都减去1，第一列和第五列加上1得 Cˊ= C〞 C〞中有5个独立零元素，则可