139
目标函数值，并记作z.以z表示问题A的最优目标函数值；这时有
*z?z*?z
进行迭代.
第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示小于bj的最大整数.构造两个约束条件
xj?[bj] 和 xj?[bj]?1
将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2.不考虑整数条件求解这两个后继问题.
定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z.从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z，若无则用z?0.
第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝，即以后不再考虑了.若大于z，且不符合整数条件，则重复第一步骤.一直到最后得到z*?z为止.得最优整数解xj,j?1,?,n.
*7.3 0-1整数规划
0-1整数规划是整数规划中的特殊情形，它的变量xj仅取0或1两个数值．这时xj称为0-1变量，或称二进制变量．xj仅取值0或1这个条件可由下述约束条件：
0?xj?1，且为整数
所代替，是和一般整数规划的约束条件形式一致的．在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了．我们先介绍0-1变量在建立数学模型中的作用，再研究解法．
7.3.1 0-1变量在建立数学模型中的作用
一、 m个约束条件中只有k个起作用 设m个约束条件可表为：
140
定义
?axijj?1nj?bi(i?1,2,?,m) (7.2)
?1,假定第i个约束条件不起作用 yi??0，假定第i个约束条件起作用?又M为任意大的正数,则
?n??aijxj?bi?Myi?j?1 ?m?y?m?k?i??i?1表明(7.2)的m个约束条件中只有(m?k)个的右端项为 (bi?M)，不起约束作用，因而只有
k个约束条件真正起到约束作用.
二、约束条件的右端项可能是r个值b1,b2,?,br中的某一个，即 定义
?axijj?1nj?b1或b2或???或br (7.3)
?1,假定约束右端项为bi yi???0，否则由此,上述约束条件(7.3)可表示为:
r?n??aijxj??biyi?j?1i?1 ?r?y?1?i??i?1三、两组条件中满足其中一组
若x1?4，则x2?2，否则（即x1?4时），x2?3 定义
?1,第i组条件不起作用yi??(i?1,2)
?0，第i组条件起作用又M为任意大的正数,则问题可表达为：
141
?x1?4?y1M?x?2?yM21???x1?4?y2M ?x?3?yM2?2??y1?y2?1四、关于固定费用的问题（Fixed Cost Problem）在讨论线性规划时，有些问题是要求
使成本为最小．那时总设固定成本为常数，并在线性规划的模型中不必明显列出．但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例．
例7.5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加．所以必须全面考虑．今设有三种方式可供选择，令
xj表示采用第j种方式时的产量；
cj表示采用第j种方式时每件产品的变动成本； Kj表示采用第j种方式时的固定成本.
为了说明成本的特点，暂不考虑其它约束条件．采用各种生产方式的总成本分别为
??Kj?cjxj,(xj?0) Cj(xj)?? j?1,2,3 （7.4）
??0, (xj?0) 式中Kj是同产量无关的生产准备费用．问题的目标是使所有产品的总生产成本为最小．即
minz?(k1y1?c1x1)?(k2y2?c2x2)?(k3y3?c3x3) （7.5）
在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量yj，令
??1,当采用第j种生产方式，即xj?0时yj??
0,当不采用第j种生产方式，即x?0时?j?于是将（7.4）、（7.5）表达为：
minz?(k1y1?c1x1)?(k2y2?c2x2)?(k3y3?c3x3)
??0?xj?Myj s.t.???yj?0或1j?1,2, 3. （7.6）
其中M是个充分大的常数.（7.6）式说明，当xj?0时yj必须为1；当xj?0时，为使z极小化，应有yj?0.
142
五、 投资场所的选定——相互排斥的计划
例7.6 某公司拟在市东、西、南三区建立门市部.有7个位置（点）Ai(i?1,2,...,7)可供选择.规定
在东区：由A1,A2,A3三个点中至多选两个； 在西区：由A4,A5两个点中至少选一个；
在南区：由A6,A7两个点中至少选一个．
如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元.问应选择哪几个点可使年利润为最大？
解题时先引入0-1变量xi(i?1,2,...,7) 令
?1,当Ai点被选中 i?1,2,...,7 xi???0，当Ai点没被选中于是问题可列写成：
7maxz??cixi
i?1?7??bixi?B?i?1?x1?x2?x3?2s..t?.
x?x?1?45?x6?x7?1??xi?0或1六、相互排斥的约束条件
1.有两个相互排斥的约束条件5x1?4x2?24或7x1?3x2?45.为了统一在一个问题中，引入0-1变量y，则上述约束条件可改写为：
?5x1?4x2?24?yM??7x1?3x2?45?(1?y)M ?y?0或1?其中M是充分大的正数.
2.约束条件x1?0 或 500?x1?800可改写为:
143
?500y?x1?800y ??y?0或13.如果有m个互相排斥的约束条件：
ai1x1??ainxn?bii?1,2,...,m (7.7)
为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i?1,2,...,m)和一个充分大的正数数M，则问题可表达为： ??ai1x1??ainxn?bi?yiM?y1??ym?m?1i?1,2,...,m （7.8）
7.3.2 0-1整数规划的应用
例7.7 资金分配问题 某企业在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用如表7-3所示.假定每一项已经批准的工程要在整个3年内完成.企业应如何选择工程，使企业总收入最大？
表7-3 每项工程的期望收入和年度费用表
工 程 1 2 3 4 5 最大可用基金数 费用（千元） 第一年 5 4 3 7 8 25 第二年 1 7 9 4 6 25 第三年 8 10 2 1 10 25 收入（千元） 20 40 20 15 30 解 作决策变量x1，x2，x3，x4，x5：
?1,选择第i项工程 i?1,2,3,4,5 xi???0,放弃第i项工程这样，所述问题的数学模型为：
maxz?20x1?40x2?20x3?15x4?30x5
?5x1?4x2?3x3?7x4?8x5?25,可用基金限制?x?7x?9x?4x?6x?25,可用基金限制?2345s..t?1.
8x?10x?2x?x?10x?25,可用基金限制2345?1?xi?0或1(i?1,2,3,4,5)?例7.8 选课策略 某大学规定，运筹学专业硕士生毕业时必须至少学习过两门数学类课
程，两门运筹学类课程和两门计算机类课程．课程中有些只归属某一类，如微积分归属于数