134
第7章 整数规划
在我们讨论线性规划问题时，其中的变量xj是非负实数，它可以是整数，也可以是分数、小数.但是，在实际问题中，常常要求问题中全部或部分变量只能取整数值.例如，在研究经济管理问题时，装货的车辆数，工人看管的机器数，完成工作的人员数等，都要求取非负整数值.此外还有一些问题，如要不要在某地建设工厂，可选用一个逻辑变量x，令x?1表示在该地建厂，x?0表示不在该地建厂，逻辑变量也是只允许取整数值的一类变量.这就需要我们研究整数规划问题. 整数规划是在1958年由R.E.戈莫里提出割平面法之后形成独立分支的,几十多年来发展出很多方法以解决各种问题.
0-1规划在整数规划中占有重要地位:一方面，许多实际问题,如指派问题、选址问题、送货问题都可归结为此类规划；另一方面，任何有界变量整数规划都与0-1规划等价，用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究.
7.1 整数规划模型
7.1.1 整数规划的定义
如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题称为整数规划问题．其模型称为整数规划模型．
如果整数规划的目标函数和约束条件都是线性的，则称此问题为整数线性规划问题．在这里我们只就整数线性规划问题进行讨论，整数线性规划的一般模型为：
max(min)z??cjxj,
j?1n?n??aijxj?(?,?)bi(i?1,2,,m)t?j?1. (7.1) s..?x?0,x为整数(j?1,2,,n)j?j7.1.2 整数规划的分类
整数规划问题根据对设计变量的取值要求的不同可以分为四类： （1）纯（完全）整数规划：所有决策变量全限制为整数的整数规划； （2）混合整数规划：部分决策变量限制为整数的整数规划； （3）0-1整数规划：所有决策变量全限制为0-1的整数规划； （4）混合0-1整数规划：部分决策变量限制为0-1的整数规划.
135
7.1.3 整数规划的模型
例7.1 背包问题 有一辆最大货运量为10t的货车，用它装载3种货物，每种货物的单位重量及相应单位价值如表7-1所示．问应如何装载，可使得价值最大．
表7-1 每种货物的单位重量及相应单位价值表
货物编号i 单位重量（t） 单位价值Ｃi 1 3 4 2 4 5 3 5 6 解: 设第i种货物装载件的数量为xi（i?1,2,3）,则所述问题可表为：
maxz?4x1?5x2?6x3
?3x1?4x2?5x3?10s..t?. ?xi?0,xi为整数(i?1,2,3)例7.2 二维装包问题 有一船能装的货物有5种，各种货物的单位重量wi和单位体积vi以及它们相应的价值Ri如表7-2表示：
表7-2 各种货物的单位重量、单位体积及它们相应的价值表
货物i 1 2 3 4 5 wi 5 8 3 2 7 vi 1 8 6 5 4 Ri 4 7 6 5 4 货物的最大载重和体积分别w=112,v=109．现要确定怎样装运这些货物，使装运价值最大．
解: 设第i种货物装载件数为xi（i=1,2,3,4,5）．则所述问题为 max 5z=4x1?7x2?6x3?5x4?4x?5x1?8x2?3x3?2x4?7x5?112?t?x1?8x2?6x3?5x4?4x5?109. s..?x?0,x为整数(i?1,...,5)i?i7.1.4 整数规划求解思想和方法分类
对于实际中的某些整数规划问题,我们有时候可以想到先略去整数约束的条件,即视为一
个线性规划问题,求得线性规划问题的最优解后,对其进行取整处理.实际上,这样得到的解未必是原整数规划问题的最优解,因此不能按照线性规划问题实数最优解简单取整而获得.但可借鉴这种思想.
136
整数规划求解方法总的基本思想是：去掉整数规划问题(7.1)中的整数约束,使构成易于求解的新问题：松弛问题(A),如果这个问题(A)的最优解是原问题(7.1)的可行解,则就是原问题(7.1)的最优解；否则，在保证不改变松弛问题(A)的可行性的条件下，修正松弛问题(A)的可行域（增加新的约束），变成新的问题(B),再求问题(B)的解,重复这一过程直到修正问题的最优解在原问题(7.1)的可行域内为止,即得到了原问题的最优解.
注：如果每个松弛问题的最优解不是原问题的可行解,则这个解对应的目标函数值z一定是原问题最优值z的上界(最大化问题),即z?z；或下界(最小化问题),即z?z.
整数规划求解方法分类：
（1）分枝定界法：可求纯或混合整数线性规划； （2）割平面法：可求纯或混合整数线性规划；
（3）隐枚举法：求解0-1整数规划，有过滤隐枚举法和分枝隐枚举法； （4）匈牙利法：解决指派问题（0-1规划特殊情形）； （5）蒙特卡洛法：求解各种类型规划. 下面将简要介绍常用的几种求解整数规划的方法.
***7.2 分枝定界法
对于求解整数规划问题，大家往往会有如下两种想法.
（1）通过枚举法对结果进行比较总能求出最好方案这种想法对于维数很低的整数规划问题行得通，但是随着决策变量维数的增加，该方法的计算量是不可想象的，因而此种想法不可行.
（2）考虑先忽略整数约束，解一个线性规划问题，然后用四舍五入法取得其整数解，事实证明，这样经过四舍五入的结果甚至不是问题的可行解.下面看一个例子 . 例7.3 求解如下整数规划问题：
max f?5x1?8x2
x1?x2?6? （7-2） ?s..t?5x1?9x2?45.?x,x?0,且取整数值?12T**若忽略整数约束，可得最优解和目标函数值为x??94,154?;f?1654,对其进行四舍五
入，可得一组整数解x(1)??2,4?,发现其不满足5x1?9x2?45，故不是整数规划式（7-2）的
(2)T可行解；我们再尝试一下舍位归整，得到另一组整数解x解，目标函数值f(2)??2,3?,它是原整数规划的可行
TT?34,但x(2)不是最优解，因为若令x(3)??0,5?,可以验证x(3)为原整数
137
规划的可行解，且f(3)?40?f(2)所以上述两种想法均不可行.
下面给出求解整数规划的一般方法：分枝定界法.
对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容.通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界．在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝．这就是分枝定界法的主要思路．
分枝定界法可用于解纯整数或混合整数规划问题．在二十世纪六十年代初由Land Doig和Dakin等人提出．由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法．目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等．
设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么问题B的最优目标函数值必是整数规划问题A的最优目标函数值z的上界，记作z；而A的任意可行解的目标函数值将是z的一个下界z．分枝定界法就是将B的可行域分成子区域再求其最大值的方法．逐步减小z和增大z，最终求到z．现用下例来说明：
例7.4 用分枝定界法求解下述整数规划问题
***maxz?40x1?90x2
?9x1?7x2?56?s..t?7x1?20x2?70. ?x,x?0且为整数?12解：（1）记原整数规划问题为(A),去掉x1,x2为整数的约束，得到松弛问题(B)，求解得(B)的最优解为：x1?4.8092,x2?1.8168,z0?355.8779,可见它不符合整数条件.这时
z0是问题A的最优目标函数值z*的上界，记作z.而x1?0,x2?0显然是问题A的一个整数
**可行解，这时z?0，是z的一个下界，记作z，即0?z?356.
（2）分枝：因为x1,x2当前均为非整数，故不满足整数要求，任选一个进行分枝.设选x1?4，x1?[4.8092]?1?5,因为4与5之进行分枝，把可行集分成2个子集：x1?[4.8092]间无整数，故这两个子集内的整数解必与原可行集整数解一致.这样将(B)分为两个子问题(B1)和(B2)：
问题B1： maxz?40x1?90x2
138
?9x1?7x2?56?t?7x1?20x2?70. s..?0?x?4,x?012?最优解为：x1?4.0,x2?2.1,z1?349.
问题B2： maxz?40x1?90x2
?9x1?7x2?56?t?7x1?20x2?70. s..?x?5,x?02?1最优解为:x1?5.0,x2?1.57,z1?341.4.
再定界：0?z?349.
（3）对问题B1再进行分枝得问题B11和B12，它们的最优解为 B11: B12:*x1?4,x2?2,z11?340
x1?1.43,x2?3.00,z12?327.14
*再定界：340?z?341，并将B12剪枝.
（4）对问题B2再进行分枝得问题B21和B22，它们的最优解为 B21:x1?5.44,x2?1.00,z21?308 B22:无可行解. 将B21,B22剪枝.
于是可得原整数问题（A）的最优解为：
x1?4,x2?2,z*?340.
从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：
开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B. （1）解问题B可能得到以下情况之一:
①B没有可行解，这时A也没有可行解，则停止．
②B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止. ③B有最优解，但不符合问题A的整数条件，记它的目标函数值为z.
（2）用观察法找问题A的一个整数可行解，一般可取xj?0,j?1,?,n，试探，求得其