司守奎数学建模刷书_第2章_0-1整数规划_1

第二章整数规划2
定义：0-1型整数规划是整数规划中的特殊情况，它的变量x仅取值0或1.这时x称为0-1变量，或称为二进制变量。可用下面的约束条件表示：
本文行文思路：

先介绍引入0-1变量的实际问题，然后再讨论解法。

【1】引入0-1变量的实际问题

投资场所的选定问题–相互排斥的计划。
某公司在东、西、南三区建立门市部。
有7个位置点可供选择，有如下限定
在东区：三个点中最多选择两个。
在西区：两个点至少选择一个。
在南区：两个点最少选择一个。

符号定义：如果选用点，设备投资估计为元，每年可获得利润估计为元，投资总额限制不超过元。问题：应该选择哪几个点可使得年利润最大？

解题时引入0-1变量并令成下面形式

于是问题可以写成：
其中 目标函数z是利润的表达式，下面xi是0-1整型变量，只能取值0或1.

【2】核心思想
0-1整数规划的核心思想是相互排斥的约束条件！！

【举例1】有两个相互排斥的约束条件

为了统一在一个问题中，引入0-1变量y，则上述约束条件改写为：

其中M式充分大的数。

【举例2】再来看一个相互排斥的约束条件

可以改写成0-1变量的形式：

如果有m个相互排斥的约束条件：
为了保证这m个约束条件只有一个起作用，我们引入 m 个0-1变量和一个充分大的常数M，而下面这一组m+1个约束条件就符合要求。

对于(2)式，m个y中只有一个能取零，设，代入(1)式，就只有的约束条件起作用，而别的式子都是多余的。

知道了整数规划的核心，我们来看下面的扩展应用。
【3】带有0-1的混合整数规划

关于固定费用的问题(Fixed Cost Problem)

在讨论线性规划时，有些问题时要求使成本最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但是有些固定费用(固定成本)的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决。

为了说明成本的特点，暂时不考虑其他约束条件。采用各种生产方式的总成本分别为固定成本k加上每件产品的变动成本c，如下式：

在构成目标函数时，为了统一在一个问题中讨论，现在引入0-1变量.其含义式采用第j种方式时，y=1;不用该种方式时,y=0.
这是一个二值问题。
（3）

于是目标函数（总成本）：

我们把(3)式表述为下面这种形式：线性约束条件

（4）
其中epsilon式一个充分小的正常数，M式一个充分的正的常数。（4）式说明，xj>0时，yj必须为1；当xj=0时，只有yj=0时才有意义。所以(4)式可以代替(3)式。

这里给读者提供一个思路，0-1规划很可能结合在规划问题里面，作为一部分出现。

【4】0-1型整数规划解法-过滤隐枚举法
解0-1型整数规划最容易想到的方法，和一般的整数规划的情形一样，就是穷举法。顾名思义，穷举法就是检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2^n个组合。对于变量个数n较大(例如n>100)，这几乎是不可能的。

因此，通常设计一些方法，只检查变量取值的组合的一部分，就能求得问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。

下面通过例子说明使用隐枚举法解0-1规划问题。

求解思路和改进措施：

• 先试探性求一个可行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，而且得到z=3.
• 因为该题是求极大值，故求最优解时，目标值z<3的解不必检验即可删除，因为它肯定不是最优解，
• 于是应该增加一个约束条件(目标值下界)，即改进过滤条件。
• 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z大的组合，这样提高过滤门槛，以减少计算量。

【总结】
1. 整数规划中的0-1型整数规划，主要在于二值情形的考量。
2.结合实际问题，在混合的整数规划中合理使用0-1型整数规划。
3.隐枚举法求解。试探可行解，改善过滤条件。

后记：部分公式为笔者使用Mathtype手打出来

参考资料：
司守奎，数学建模算法与应用(第2版)，国防工业出版社