第三章 整数线性规划
【教学内容】
整数线性规划问题举例、整数线性规划模型及其求解的困难性、可用线性规划求解的整数线性规划问题、求解整数线性规划问题的Gomory割平面法、求解整数线性规划问题的分枝定界方法、0－1规划问题举例、0－1规划问题的解法、整数线性规划问题的一些例子、用LINGO软件包求解整数线性规划问题。
【教学要求】
要求学生熟悉整数线性规划模型，能熟练地掌握求解整数线性规划问题的Gomory割平面法和分枝定界方法；熟悉并会求解0－1规划问题，能够建立整数线性规划模型并用软件求解整数线性规划问题。
【教学重点】
整数线性规划模型，Gomory割平面法，分枝定界方法，0－1规划问题。
【教学难点】
Gomory割平面法，分枝定界方法，0－1规划问题的求解。
【教材内容及教学过程】
整数线性规划(Integer Linear Programming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。其中变量只取0或1的整数线性规划问题称为0－1规划。只要求部分变量取整数值的线性规划称为混合整数线性规划。
整数线性规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是以相应的线性规划的最优解为出发点的。但是变量取整数值的要求本质上是一种非线性约束，因此解整数线性规划的“困难度”大大超过线性规划，一些著名的“困难”问题都是整数线性规划问题。
本章主要介绍整数线性规划一些基本概念、基本理论、实际背景及常用算法。
第一节 整数线性规划模型
§1．1 整数线性规划问题举例
例[2] 工地上需要长度为的钢材数分别为根，取长为的原材料进行截取。已知有种截取方案：
，
其中，表示一根原料用第种方案可截得长为的钢材的根数（，），因此
，
下料问题就是在满足要求：截取长度为的钢材数分别为根时，用的原料材根数最少的方案。假定表示按方案截取用的原钢材数目，于是问题表示为：
()
在许多实际问题中，我们所研究的量具有不可分割的性质，如人数、机器数、项目数等；而开与关、取与舍、真与假等逻辑现象都需要用取值仅为0或1的变量来进行数量化的描述。涉及这些量的线性规划问题，非整数的解答显然不合乎要求。
§1．2 整数线性规划模型及其求解的困难性
考虑如下形式的整数线性规划问题ILP
()
其中，，以及，，，中的元素皆为整数。在()中除去为整数向量这一约束后，就得到对应的标准线性规划问题
()
称()是()的松弛问题。如果()对应的标准线性规划问题()的最优解是整数，则它也是()的最优解。对于标准线性规划问题，已有有效的算法。那么能不能通过求解对应的线性规划问题，然后将其解舍入到最靠近的整数解呢？
考察图所示的情况，可以看出舍入方法是不可取的。
既然ILP的可行域是一些离散的整数点（图），如果其可行域有界，那么所包含的整数点的数目就是有限的，可否用枚举法来解ILP问题呢？对一般ILP问题，枚举法是无能为力的。如50个城市的旅行售货员问题（见例），所有可能的旅行路线个数为，这是一个天文数字。
由上可见，求解整数线性规划问题ILP比求解对应的线性规划问题LP要困难得多。事实上，整数线性规划模型并不是线性模型。仅以0－1规划而言，决策变量取值为0或1这个约束是可以用一个等价的非线性约束
()
来代替的。因而变量限制为整数本质上是一个非线性约束。
第二节 求解整数线性规划问题的常用方法
从1959年提出解整数线性规划的割平面算法至今，经过几十年的努力，已经发展起来了一些常用算法，如各种类型的割平面算法、分枝定界算法、解0－1规划的隐枚举法、分解方法、群论方法、动态规划方法等等，本节主要介绍求解整数线性规划问题的几个常用算法。
§2．1 可用线性规划求解的整数线性规划问题
可用线性规划问题求解的整数线性规划问题，实际上是这样的一类问题，它的解就是线性规划解，即可以通过单纯形法来求整数规划的解。
定义矩阵 EMBED ，若它的任一子行列式的值均为，或者，则称这样的矩阵为幺模矩阵。
幺模矩阵的所有元素都是，或者。
定理 若 EMBED 是幺模矩阵，是由中的个列向量组成的矩阵，若可逆，则的所有元素都是，或者。
定理 若 EMBED 是幺模矩阵，是由中的个列向量组成的可逆矩阵，，若是整数，则是整数。
因此，对于规划问题()，若系数矩阵 EMBED 为幺模矩阵，且右端项是整数，则可以用单纯形方法直接求解对应的标准线性规划问题()，就可以得到它本身的最优整数解。
§2．2 求解整数线性规划问题的Gomory割平面法
整数线性规划问题与其对应的松弛问题的关系
解整数线性规划问题的割平面法有多种类型，但它们的基本思想是相同的。以下我们介绍Gomory割平面法。它在理论上是重要的，被认为是整数线性规划的核心部分。
设()的可行域为D，对应的松弛问题()的可行域为（多面凸集），当时它是由有限个或可数的整数点构成的集合。问题()和问题()之间具有如下明显的关系：
⑴．；
⑵．若问题()无可行解，则问题()无可行解；
⑶．问题()的最优值是问题()的最优值的一个下界；
⑷．若问题()的最优解是整数向量，则是问题()的最优解。
割平面法的基本思想
用单纯形法先解松弛问题()，若问题()的最优解是整数向量，则是ILP问题()的最优解；若问题()的最优解的分量不全是整数，设法构造一个线性约束条件（称它为割平面条件），新增加的这个割平面条件将问题()的可行区域割掉一块，且这个非整数解恰好在被割掉的区域内，而原ILP问题()的任何一个可行解（整数点）都没有被割去。给问题()增加这个约束条件，用得到的问题替换问题()，继续以上过程。
Gomory割平面法的割平面条件
用单纯形方法求解问题()的松弛问题()，得到最优基本可行解，设它对应的基为，为基变量，基变量的下标集合为，非基变量的下标集合为。最优解所对应的问题()是
()
为使符号简便计，令，，。如果，全是整数，已经得到了问题()的最优解；否则至少有一个不是整数，设所对应的约束方程是
()
我们用表示不超过的最大整数，则有
()
其中（）是的分数部分；（）是的分数部分。由于方程()中的变量是非负的，因此有
()
从而方程()变为
()
因为为整数向量，故()式左端为整数，所以右端用的整数部分去代替后，()式的不等式关系仍成立，即有
()
()减去()，得
()
注意到()关系式，我们得到线性约束
()
称它为对应于生成行的Gomory割平面条件。
将()改写为（引进松弛变量）超平面方程()
()
称它为割平面。将割平面()加到问题()，就得到了一个新的线性规划问题，且已经具有满足最优性条件的基本不可行解。
定理 如果把割平面()加到问题()中，那么没有割掉问题()的任何整数可行点，当不是整数时，新问题是一个满足最优性条件的不可行基本解。
Gomory割平面法计算步骤
第1步 求解问题()。若问题()没有最优解（包括无可行解和无有限最优解），则问题()也没有最优解；若问题()有最优解，且是整数向量，则是问题()的最优解，输出；否则转第2步。
第2步 任选的一个非整数分量 EMBED ，按关系式()和()得到割平面方程
()
第3步 将()加到第1步所得的问题()的最优形式()中，用对偶单纯形法求解这个问题。若其最优解为整数解，则它是问题的最优解，输出这个最优解；否则将这个最优解重新记为，返回第2步。若对偶单纯形算法发现了对偶问题是无界的，此时原ILP问题是不可行的。
§2．3 求解整数线性规划问题的分枝定界方法
分枝定界法可用于解纯整数线性规划和混合整数线性规划，它是目前求解整数线性规划的成功方法之一。本节介绍该方法的基本思想和计算步骤。
分枝定界方法的基本思想
分枝定界法是以“巧妙”的枚举问题()的可行解的思想为依据设计的。
与割平面方法类似，求解不是直接针对问题()，而是求解它的松弛问题()。设问题()的最优解为，则是问题()的最优值的一个下界。若的某个分量不是整数，由于问题()的整数最优解的第个分量必定落在区域或中，因此可将原问题()分为两个子问题来求解。这两个子问题是：
()
和
()
这两个子问题将问题()的可行域分成两部分，且把不满足整数要求的问题()的最优解排斥在外。这一步称为分枝。分别用()和()代替原问题()，则分枝过程一直可以进行下去。每得到松弛问题的一个解，都会修正原问题目标函数最优值的下界。
假设在某一时刻，到当时为止所得到的最好的满足整数要求解的目标函数值是（目标函数最优值的一个上界），而且我们正打算由某一点分枝，该点所对应的ILP的下界为，若，这意味着点的所有后代得到的各个解的目标函数值均有
因此无须由继续分枝。在这种情况下，我们说已被剪枝。这个过程可以“巧妙”地减少一些不必要的分枝。
总之，分枝定界方法的思想是按照下面三步进行的：
第一步，通过求解松弛问题对原问题进行分枝；
第二步，通过每个松弛问题的最优目标函数值对原问题的目标函数值定界；
第三步，一旦某个松弛问题的最优解是整数，就得到原问题最优解的一个近似，其目标函数值就是原问题目标函数值的一个近似值（上界）。如果以后某个松弛问题的最优目标函数值比这个近似值大，那么这个松弛问题及它的所有子问题都不用求解了。
之所以说分枝定界方法是“巧妙”的枚举方法，主要是因为“剪枝”步骤，通过“剪枝”步骤就不用枚举问题的所有可行解。
分枝定界法计算步骤
第1步 求解问题()。若问题()没有最优解（包括无可行解和无有限最优解），则问题()也没有最优解；若问题()有最优解，且是整数向量，则是问题()的最优解，输出；否则，令，，，转第2步。
第2步 若，则转第7步，否则，选择一个分枝点，；
第3步 解对应的松弛问题，若此问题无解，转第2步；
第4步 若对应的松弛问题的最优值，则点被剪枝，转第2步；
第5步 若对应的松弛问题的最优解为整数，则，，转第2步；
第6步 若对应的松弛问题的最优解不是整数，按某个非整数分量生成的两个分枝点和，令，转第2步；
第7步 若，，则原ILP问题无解；否则，为原ILP问题的最优解，是最优值，计算停止。
分枝定界法的思想不仅适用于解ILP问题，也适用于任何组合最优化问题。
第三节 0－1规划问题及其求解方法
0－1规划是整数规划中的特殊情况，它的变量仅取值0或1。
§3．1 0－1规划问题举例
例[1] 某部门在今后五年中可用于投资的资金总额为万元，有个可以考虑的投资项目，假定每个项目最多投资一次，第个项目所需的资金为万元，将会获得的利润为万元。问应如何选择投资项目，才能使获得的总利润最大。
解 设投资决策变量为
设获得的总利润为，则上述问题的数学模型为
()
显然，问题()是一个0－1规划。
§3．2 0－1规划问题的解法
由于0－1规划问题的特殊性，虽然上面介绍过的割平面方法和分枝定界方法都可以用来求解，但是正是由于它的特殊性，这里介绍专门用来求解0－1规划问题的一些方法。
DFS搜索法
DFS是Depth First Search的缩写，即深度优先搜索的意思。典型的思想可以从下面例子看出。
例 用DFS搜索法求解整数规划问题
()
首先确定搜索树，假定自上而下的搜索顺序为，引进栈用以记录搜索过程，栈是按后进先出的顺序来建立数据结构。属于栈的变量定义为固定变量。，属于的变量定义为自由变量。，作为约定栈顶元素为，中间为，栈底为。若从中取走栈顶元素，则取出的是，取走之后的为，栈顶元素则为。
搜索空间即搜索树（如图所示）。
，，由于，和不论为0或1均不能满足
。故应放弃。
，前进一步，再前进一步
，，。
从栈顶元素后退，改为，。
不满足约束，应放弃。
，前进一步为，应放弃。
进入，不满足约束，应放弃，故后退。直到，
停止。
故得最优解。
隐枚举法
隐枚举法是通过建立过滤条件而使计算工作量大为减少的穷举法，用下面的例题加以说明。
例 用隐枚举法求解整数规划问题
()
解题时，先通过试探的方法找一个可行解，容易看出就是合于条件的，算出相应的目标函数值。
我们求最优解，对于极大化问题，当然希望，于是增加一个约束条件：
()
后加的条件称为过滤的条件。这样，原问题的线性约束条件就变成5个。用全部枚举的方法，3个变量共有个解，原来四个约束条件，共需32次运算。现在增加了过滤条件()，如按下述方法进行，就可减少运算次数，将5个约束条件按顺序排好（表），对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件就不必再检查，因而减少了运算次数。本例计算过程如表，实际只作24次运算。
表
点
条 件
满足条件？
是（√）否（×）
值
（0）
（1）
（2）
（3）
（4）
（0，0，0）
（0，0，1）
（0，1，0）
（0，1，1）
（1，0，0）
（1，0，1）
（1，1，0）
（1，1，1）
0
5
-2
3
3
8
1
6
-1
1
1
0
2
1
5
1
2
6
0
1
1
1
0
1
×
√
×
×
√
√
×
×
5
3
8
于是求得最优解，。
在计算过程中，若遇到值已超过条件()右边的值，应改变条件()，使右边为迄今为止最大者，然后继续作。例如，当检查点（0，0，1）时因，所以应将条件()换成
()
这种对过滤条件的改进，更可以减少计算量。
注：一般重新排列的顺序使目标函数中的系数是递增（递减）的。在上例中，改写，因为，3，5是递增的。变量也按下述顺序取值：（0，0，0），（0，0，1），（0，1，0），（0，1，1），这样，最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化。
第四节 整数线性规划问题的一些例子
例 （分配问题）设有个人被分配去做件工作，规定每个人只做一件工作，每件工作只能由一个人去做。已知第个人去做第件工作的效率（时间或费用）为（；），并假设。问应如何分配才能使总效率（总时间或总费用）最高（最少）？
设决策变量
那么第个人去做第件工作的效率为，从而即为总效率，（）表示每件工作都有人去做，（）表示每个人都有工作做；于是分配问题的数学模型为
例 （旅行售货员问题）有一推销员，从城市出发，要遍访城市各一次，最后返回，已知从到的旅费为，问他应该按怎样的次序访问这些城市，使得总旅费最少？（设，为充分大的正数，）。
对每一对城市和，我们指定一个变量，令
该问题的数学模型为
()
例 （最短路问题）设给定了一个有个节点，条弧的网络，每条弧的长度为。对给定的两个节点，设为和，找出从到的总长度最短的路。
若用表示弧是否在这条路上，因此显然有或1，则问题的数学模型是
例 （一维背包问题）有一个人带一个背包上山，其可携带物品重量的限度为。设有种不同的物品可供他选择装入背包中，已知第种物品的重量为，单位价值为（）。问此人应如何选择携带物品的方案，使总价值最大？
设为第种物品的装入件数，则问题的数学模型是
第五节 用LINGO软件包求解整数线性规划问题
例如，用LINGO求解线性规划问题：
模型的输入
使用LINGO求解上述整数规划模型，LINGO程序如下：
MODEL:
max=3*x1+4*x2+8*x3-100*y1-150*y2-200*y3;
2*x1+4*x2+8*x3<=500;
2*x1+3*x2+4*x3<=300;
x1+2*x2+3*x3<=100;
3*x1+5*x2+7*x3<=700;
x1<=200*y1;
x2<=150*y2;
x3<=300*y3;
@GIN(x1);@GIN(x2);@GIN(x3);
@BIN(y1);@BIN(y2);@BIN(y3);
END
执行
点击LINGO菜单下的SOLVE键，或按CTRL+S键，即可求得问题的解。
此问题的解为：，最优值为：200。
当运用LINGO求解此问题后，系统会弹出一个名为Solution Report的文本框，其文本框中包含了求解的详细信息，如下：
Rows= 8 Vars= 6 No. integer vars= 6 ( all are linear)
Nonzeros= 28 Constraint nonz= 18( 4 are +- 1) Density=
Smallest and largest elements in abs value=
No. < : 7 No. =: 0 No. > : 0, Obj=MAX, GUBs <= 3
Single cols= 0
Global optimal solution found at step: 4
Objective value:
Branch count: 0
Variable Value Reduced Cost
X1
X2
X3
Y1
Y2
Y3
Row Slack or Surplus Dual Price
1
2
3
4
5
6
7
8
LINGO程序注解
MODEL：LINGO模型程序的开始标志。
END：LINGO模型程序的结束标志。
max=3*x1+4*x2+8*x3-100*y1-150*y2-200*y3：表明目标函数是，问题为求最大值。
2*x1+4*x2+8*x3<=500：对应约束条件，其余类似。
@GIN(x1)：对应约束条件为整数，函数用来限定变量为整数，其余类似。
@BIN(y1)：对应约束条件为0－1变量，函数用来限定变量为二进制整数。
关于LINGO的详细使用方法，参见本部分附录的《LINGO使用手册》。
练习题
食油厂精炼两种类型的原料油——硬质油和软质油，并将精制油混合得到一种食油产品。硬质原料油来自两个产地：产地1和产地2，而软质原料油来自另外三个产地：产地3，产地4和产地5。据预测，这5种原料油的价格从一至六月份分别为附录表1所示，产品油售价200元/吨。
硬质油和软质油需要由不同的生产线来精炼。硬质油生产线的每月最大处理能力为200吨，软质油生产线最大处理能力为250吨/月。五种原料油都备有贮罐，每个贮罐的容量均为1000吨，每吨原料每月的存贮费用为5元。而各种精制油以及产品无油罐可存贮。精炼的加工费用可略去不计。产品的销售没有任何问题。
产品食油的硬度有一定的技术要求，它取决于各种原料油的硬度以及混合比例。产品食油的硬度与各种成分的硬度以及所占比例呈线性关系。根据技术要求，产品食油的硬度必须不小于而不大于。各种原料油的硬度如附录表2（精制过程不会影响硬度）。
假设在一月初，每种原料油都有500吨存贮而要求在六月底仍保持这样的贮备。
问题1：根据附录表1预测的原料油价格，编制逐月各种原料油采购量、耗用量及库存量计划，使本年内的利润最大。
问题2：考虑原料油价格上涨对利润的影响。据市场预测分析，如果二月份硬质原料油价格比附录表1中的数字上涨，则软质油在二月份的价格将比附录表1 中的数字上涨。相应地，三月份，硬质原料油将上涨，软质原料油将上涨，依此类推至六月份。试分析从1到20的各情况下，利润将如何变化？
附加下列条件后，求解新的问题：
每一个月所用的原料油不多于三种。
如果在某一个月用一种原料油，那么这种油不能少于20吨。
如果在一个月中用了硬质油1或硬质油2，则在这个月中就必须用软质油5。
附录表1 原料油的价格（元/吨）
硬质1
硬质2
软质3
软质4
软质5
一月
二月
三月
四月
五月
六月
110
130
110
120
100
90
120
130
140
110
120
110
130
110
130
120
150
140
110
90
100
120
110
80
115
115
95
125
105
135
附录表2 各种原料油的硬度（无量纲）
硬质1
硬质2
软质3
软质4
软质5
机械加工厂生产7种产品（产品1到产品7）。该厂有以下设备：四台磨床、两台立式钻床、三台水平钻床、一台镗床和一台刨床。每种产品的利润（元/件，在这里，利润定义为销售价格与原料成本之差）以及生产单位产品需要的各种设备的工时（小时）如附录3，其中的短划表示这种产品不需要相应的设备加工。
从一月份至六月份，每个月中需要检修的设备见附录表4所示（在检修的月份，被检修的设备全月不能用于生产）。每个月各种产品的市场销售量的上限如附录表5 所示。
每种产品的最大库存量为100件，库存费用为每件每月元，在一月初，所有产品都没有库存；而要求在六月底，每种产品都有50件库存。工厂每天开两班，每班8小时，为简单起见，假定每月都工作24天。
生产过程中，各种工序没有先后次序的要求。
问题1：制定六个月的生产、库存、销售计划，使六个月的总利润最大。
问题2：在不改变以上计划的前提下，哪几个月中那些产品的售价可以提高以达到增加利润的目的。价格提高的幅度是多大？
问题3：哪些设备的能力应该增加？请列出购置新设备的优先顺序。
问题4：是否可以通过调整现有设备的检修计划来提高利润？提出一个新的设备检修计划，使原来计划检修的设备在这半年中都得到检修而使利润尽可以有增加。
问题5：最优设备检修计划问题：构造一个最优设备检修计划模型，使在这半年中各设备的检修台数满足案例中的要求而使利润为最大。
附录表3 产品的利润（元/件）和需要的设备工时（小时/件）
产品
1
2
3
4
5
6
7
单位产品利润
磨床
立钻
水平钻
镗床
刨床
—
—
—
—
—
—
—
—
—
—
—
—
—
—
附录表4 设备检修计划
月份
计划检修设备及台数
月份
计划检修设备及台数
一月
二月
三月
一台磨床
二台立式钻床
一台镗床
四月
五月
六月
一台立式钻床
一台磨床和一台立式钻床
一台刨床和一台水平钻床
附录表5 产品的市场销售量上限（件/月）
产品
1
2
3
4
5
6
7
一月
二月
三月
四月
五月
六月
500
600
300
200
0
500
1000
500
600
300
100
500
300
200
0
400
500
100
300
0
0
500
100
300
800
400
500
200
1000
1100
200
300
400
0
300
500
100
150
100
100
0
60
参考文献
刁在筠等编，运筹学，北京：高等教育出版社，2001年
卢开澄，单目标、多目标与整数规划，北京：清华大学出版社，1999
甘应爱等，运筹学，北京：北京：清华大学出版社，1990
PAGE
- PAGE 80 - DATE \@ "yyyy-M-d"
