运筹学(第3版) 习题答案 45
?10?6x1,若x1?0?15?10x2,若x2?0 f(x1)??,g(x2)??若x1?0若x2?0?0,?0,满足约束条件
（1）x1≥8或x2≥6 （2）|x1－x2|=0，4或8
（3）x1+2x2≥20、2x1+x2≥20及x1+x2≥20 三个约束中至少一个满足 （4）x1≥0，x2≥0
将此问题归结为混合整数规划的数学模型。
minZ?10y1?6x1?15y2?10x2?x1?y1M;x2?y2M?x?8?yM3?1?x2?6?(1?y3)M??x1?x2?0y4?4y5?4y6?8y7?8y8【解】??y4?y5?y6?y7?y8?1??x1?2x2?20?y9M?2x1?x2?20?y10M??x1?x2?20?y11M?y?y?y?21011?911??x1?0,x2?0;yj?0或1，j?1,2,?，3.8用分枝定界法求解下列IP问题
条件（1）条件（2）条件（3）
条件（4）maxZ?x1?4x2minZ?x1?2x2?3x1?2x2?9?3x1?x2?10（1）? （2）?
2x?4x?85x?6x?30?1?122?x,x?0且为整数?x,x?0且为整数?12?12【解】(1)X=(4，0),Z=4 （双击打开PPT）
运筹学(第3版) 习题答案 46
习题3.8（1）maxZ?x1?4x2x24.53x1?2x2?9?3x1?2x2?9LP0:?2x?4x?8?12?x,x?0?122x1?4x2?82松弛问题LP0的最优解X=(2.5,0.75),Z0=5.5o34x1 (2) X(1)=(2,4)，X(2)＝(0，5)；Z=10 （双击打开PPT）
习题3.8（2）x210minZ?x1?2x23x1?x2?10LP0:?3x1?x2?10??5x1?6x2?30?x,x?0?125x1?6x2?305松弛问题LP0的最优解X=(2.31, 3.08),Z0=8.46o3.336x1 3.9用割平面法求解下列IP问题
maxZ?2x1?x2（1）?minZ?2x1?3x2?4x1?2x2?14?x1?2x2?9 （2）?
?2x1?x2?10?2x1?x2?10?x,x?0且为整数?x,x?0且为整数?12?12【解】(1) 加入松弛变量x3、x4，单纯形表如下：
运筹学(第3版) 习题答案 47
1 0 0 CB XB X2 X3 X4 0 X3 2 1 0 0 X4 1 0 1 C(j)-Z(j) 1 0 0 2 X1 1/2 1/4 0 0 X4 0 －1/2 1 C(j)-Z(j) 0 －1/2 0 X1行为来源行，割平面方程为：s1?2x2?x3??2，插入到最优表得到
C(j) CB XB 2 X1 0 X4 0 S1 C(j)-Z(j) 2 X1 0 X4 1 X2 C(j)-Z(j) 2 S1 0 X4 1 X2 C(j)-Z(j) 2 X1 1 0 0 0 1 0 0 0 4 0 2 0 1 X2 1/2 0 [－2] 0 0 0 1 0 0 0 1 0 0 X3 1/4 －1/2 －1 －1/2 0 －1/2 1/2 －1/2 0 －1/2 1/2 －1/2 0 X4 0 1 0 0 0 1 0 0 0 1 0 0 0 S1 0 0 1 0 [1/4] 0 －1/2 0 1 0 0 0 C(j) 2 X1 4 2 2 1 0 0 b 14 10 0 7/2 3 －7 b 7/2 3 －2 －7 3 3 1 －7 12 3 7 －7 从表中看出，有两个最优解：X(1)=(3,1)，X(2)＝(0，7)；Z=7 (2) 加入松弛变量x3、x4，单纯形表如下： 3 0 0 b CB XB X2 X3 X4 0 X3 －2 1 0 －9 0 X4 －1 0 1 －10 C(j)-Z(j) 3 0 0 0 0 X3 [－3/2] 1 －1/2 －4 2 X1 1/2 0 －1/2 5 C(j)-Z(j) 2 0 1 －10 3 X2 1 －2/3 1/3 8/3 2 X1 0 1/3 －2/3 11/3 C(j)-Z(j) 0 4/3 1/3 －46/3 以X1行为来源行，割平面方程为：s2?x3?x4??2，插入到最优表得到
C(j) CB 3 2 0 XB X2 X1 S2 2 X1 0 1 0 3 X2 1 0 0 0 X3 －2/3 1/3 －1 0 X4 1/3 －2/3 [－1] 0 S2 0 0 1 b 8/3 11/3 －2 C(j) 2 X1 －1 [－2] 2 0 1 0 0 1 0 运筹学(第3版) 习题答案 48
C(j)-Z(j) 3 X2 2 X1 0 X4 C(j)-Z(j) 0 0 1 0 0 0 1 0 0 0 4/3 －1 1 1 1 1/3 0 0 1 0 0 1/3 －2/3 －1 1/3 －46/3 2 5 2 －16 最优解X=(5,2)；最优值Z=16
3.10用隐枚举法求解下列BIP问题
??x1?x2?4x3?2x4?5?5x1?2x2?x3?6?（1）? （2）?3x1?x2?2x3?2x4?4??4x1?2x2?3x3?8?x1?3x2?2x3?x4?9?x?0或1，j?1,2,3?j?xj?0或1，j?1,2,3,4?【解】(1)X=(1,0，1),Z=8 (2)X=(1,0,1,0),Z=9
3.11思考与简答题 （1）“整数规划的最优解是求其松弛问题最优解后取整得到”为什么不对。 （2）解释“分支”与“定界”的含义。 （3）简述分支定界法的基本步骤。
（4）高莫雷方程是怎样得到的，在割平面法中起到什么作用。
（5）割平面法计算过程中，什么时候可以去掉单纯形表中一行和一列。
maxZ?4x1?3x2＋4x3minZ?4x1?2x2?5x3?3x4
返回顶部