1、1 / 15运筹学第五章作业题参考答案51 解：设在 A 处建 幢住宅. jj则数学模型为Max z = nijx1且 为 整 数01jjnijxaDd5.2 解：设每种毛坯截取 根j则数学模型为Max z = nijx1且 为 整 数01jjnixla5.4 解：设 X =i名 队 员 不 上 场第 名 队 员 上 场第 i01数学模型为：Max Z =( 1.92X +1.92X +1.78X )/512850128126418762或iiXX2 / 155.6 用割平面法解下列整数规划（1） Max Z = X + X12s.t 且 为 整 数、 0546221解：将其化为标准型为 Ma
2、x Z = X + X 12s.t 且 为 整 数0,25462143X基 X1X 2X 3X 4bX 32 1 1 0 6X 44 5 0 1 20-Z j1 1 0 0X11 1/2 1/2 0 3X 40 3 -2 1 8-Z j0 1/2 -1/2 0X11 0 5/6 -1/6 5/3X 20 1 -2/3 1/3 8/3-Z j0 0 -1/6 -1/6从表中第二行产生割平面的约束条件：-1/3 X - 1/3 X343/2引入松弛变量 X 为：5-1/3 X 1/3 X + X =-2/33453 / 15基 X1X 2X 3X 4X 5bX11 0 5/6 -1/6 0 5/3
3、X 20 1 -2/3 1/3 0 8/3X 50 0 -1/3 -1/3 1 -2/3-Z j0 0 -1/6 -1/6 0X11 0 0 -1 5/2 0X 20 1 0 1 -2 4X 30 0 1 1 -3 2-Z j0 0 0 0 -1/2X11 0 1 0 -1/2 2X 20 1 -1 0 1 2X 40 0 1 1 -3 2-Z j0 0 0 0 -1/2X =(0, 4) 或 ( 2, 2) ， Z =4*TT*(2) MinZ=5 +X12且 为 整 数0,859321X解: 化为标准型为 max z =-5 -X 1X20,88593543214213X4 / 15C j
4、-5 -1 0 0 0C B 基 b X1X 2X 3X 4X 50 X 3-9 -3 -1 1 0 00 X 4-5 -1 -1 0 1 00 X 5-8 -1 -8 0 0 1C -Zjj-5 -1 0 0 0-1 X 29 3 1 -1 0 00 X 44 2 0 -1 1 00 X 564 23 0 -8 0 1C -Zjj -2 0 -1 0 0因此，原问题的最优解为 X=( 0, 9 ) ，最优值 Z = 9T*5.7 用分支定界法解下列整数规划（1） Max Z=2X +X12且 为 整 数0,652121X解：用图解法求得该整数规划的松弛问题的最优解为X =X =21/8 选择
5、 X =21/8 进行分支1215 / 15B1: B2:Max Z =2X +X Max Z =2X +X12 120,265112X0,3652121X最优解为 X =2 X =3 Z =7； 最优解 X =3 X = 3/2 Z =15/2 2* 2*7选择 X = 3/2 进行分支2B3 B4Max Z =2X +X Max Z =2X +X12 120,13260521XX0,231605112XX最优解为 X =19/6 X =1 Z =22/3 7； 无可行解12*选择 X =19/6 进行分支B5 B6Max Z =2X +X120,316052121XX0,413260521
6、1XX6 / 15最优解为 X =3 X =1 Z = 7； B6 无可行解12*综上：原整数规划最优解为 X = ( 2 , 3)或 ( 3 , 1) Z =7*5.8 解下列 01 型 整数规划：(2) Max Z =2X +X - X12310,42543,321231或X解：（X1，X2, X3 ）Z 值 约束条件a b c d过滤条件（0， 0 ， 0 ） 0 Z 0（0， 0 ， 1 ）-1（0， 1 ， 0 ） 1（0， 1 ， 1 ） 0（1， 0 ， 0 ） 2 Z 2（1， 0 ， 1 ） 1（1， 1 ， 0 ） 3（1， 1 ， 1 ） 2最优解为 X =(1 , 0
7、, 0 ) Z = 2*T*7 / 155.11（1） 解：引入一个虚拟人 A ,使之成为标准的指派问题，则系5数矩阵为C = 00715134296780将各行元素减去本行的最小元素得C = C0034869715602由于只有 4 个独立零元素，小于系数矩阵阶数 n=5，所以将第二行，第三行，第四行都减去 1，第一列和第五列加上 1 得C = C001237586140981023796509C中有 5 个独立零元素，则可确定指派问题的最优指派方案。 8 / 15最优解为X = Z = 22*010010*(2) 解：增加虚拟事件 B ，B ,使之成为标准的指派问题，则系数矩56阵为C =
8、 02675348017263将各列元素减去本列的最小元素得C = C046215370024C中有 6 个独立零元素，则可确定指派问题的最优指派方案，最优解为X = Z = 8* 010010*9 / 155.12 解：原指派问题的系数矩阵为C = 1.06.90.1425.30.18.031由于原问题为最大化指派问题，所以转化为最小化指派问题得1.4EC = = B3.04.185.0423.1. 4.0.146.0将 B 的各行（列）元素减去本行（列）的最小元素得B = B01.502.143. 2.3. .0.15.001.50.1242. .3. .0.1.0由于 B中只有 4 个独立零元素，小于系数矩阵阶数 n=5，所以将第一行，第四行，第五行都减去 0.1，第一列，第五列加上 0.1 得B =D1.0.4.0315.312.2.203. .0. 0.140.354.2. 3.0.1.010 / 15D 中有 5 个独立零元素，则可确定指派问题的最优指派方案.最优解为X = *01001即最优指派方案为 A 去做 B 工作，A 去做 B ， A 去做 B ，A12334去做 B ， A 去做 B ，最大评分为452Z = 1.3 + 0.9 + 1.3 + 1.2 + 1.2 + 1.4 =6.1*
