第七章 整数线性规划
在某些线性规划问题中，变量只有取整数值才有意义。这时约束条件中还需添上变量取整数值的限制，因而称为整数线性规划问题，其一般形式是：
（1）
这称为纯整数规划。若其中只有部分变量要求取整数，则称之为混合整数规划。
整数规划有着广泛的实际背景和明显的经济意义，在许多领域中有着重要应用，但是求解（1）比求解相应的无整限制的线性规划问题（LP）要困难得多，被认为是NP_困难问题。我们在§1、§2中介绍以往常采用的分枝定界法、割平面法，在§3提出一种新程序。
§1分枝定界法此法之原理及步骤前面已有介绍，可适用于纯整数规划及混合整数规划，它是以相应的LP问题为松弛问题，把它的可行解域D分解成若干个子域，对每个子域求解LP问题，具体作法我们通过例子说明。
例1 min z=x1+3x2
x2≥3.13
D,22x1+34x2≥285
x1,x2为非负整数先不考虑x1,x2为整数的条件，求得最优解为：
x1＝8.12,x2=3.13，最优值minz=z0=17.51。
这不是整数，由于对变量的整数限制，则最优解必在如下两个子域D1或D2中：
x1≥9 x18
D1,x2≥3.13 D2,x2≥3.13
22x1+34x2≥285 22x1+34x2≥285
分别在D1及D2上求问题的最优解，得
（D1）：x1＝9，x2＝3.13，min z＝z1＝18.39
（D2）：x1＝8，x2＝3.21，min z＝z2＝17.62
由于所得的解都不是整数解，于是进一步将D1分成D11和D12两个子域，D2分成D21和D22两个子域，并分别求解。由于z2<z1，故求解宜先在D2的子域上进行。这样做的好处是，若在D2的某个子域上已求得整数解，并且相应的最优值不大于z1,则对D1的分枝求解自然不必再进行了。所谓“定界”的意义就在于此。
整个求解过程可列表简示如下，其中分枝方框中只表示在前一约束基础上新加的约束。方框上面括号内的数字表示求解的先后顺序：
如果在分枝求解的过程中，求得的整数解之目标函数值成为所有分枝稍头上诸解的最小值，过程即可停止，此即最优解。否则，对于比整数解之目标函数小的，还需继续分枝搜索。可见，最先得到的整数解未必是最优的。如此例中，第六步已得整数解，但它不是最优的，而于第八步得到的才是最优解，即
x1=7 x2=4 min z=z211=19
需要指出的是，分枝定界法每步迭代，由于是增加一个上限或者下限约束,故一般都要用对偶单纯形法或第五章的方法求解LP问题，且不能保证用最少的迭代次数达到最优解，在不顺利的情况下，甚至需要对全部区域进行搜索。但根据经验，它还是比较有效的，目前应用也最广泛。
§2 割平面法解整数LP问题（1）的割平面法是R·E·Gomory于1959年首先提出来的。从此以后整数规划逐渐形成一个独立的运筹学分支，割平面法被认为是整数规划的核心部分，其基本思想是仍以LP问题为松弛问题。若求得的最优解不是整数，就设法把这个最优的极点连同它的一个邻域，从可行解集中“切除”，但保留其中的全部整数点，从而不影响（1）的求解。如此进行，直到找到整数解为止，而“切除”将通过一个附加的约束条件（称为割平面）来实现，故称为割平面法。具体说明如下：
设与（1）相应的LP问题：
（2）
之最优单纯形表为
（3）
若存在整数，考虑（3）中相应的方程
（4）
它可写成
这里符号表示不超过t的最大整数。，，则，，由有
若问题（1）有整数解（均为整数），则由上式又可得
或
为整数，由上式减去得
（5）
（5）是在（1）有整数解的假定下导出来的新的约束条件，称为割平面方程。用来导出（5）的方程（4）称为诱导方程，（5）的作用由下面的定理可以看出。
定理1、问题（1）的可行解与方程组
（6）
的非负整数解一一对应。
证：（6）的非负整数解，显然是（1）的可行解。
设是（1）的可行解，代入（5）得
可见为整数，又因非负，，故
于是，即（1）的可行解与（6）的非负整数解一一对应。
根据定理1可得结论：整数线性规划（1）与规划
是等价的。
例2．
不计整数限制的最优解如下表：
它右端不全是整数。取第二行为诱导方程，得割平面方程为
填入上表，用对偶单纯形法迭代求解。再加割平面，求解得
于是已得（7）的最优解：
最优值
通常取，以作为割平面方程，，亦可采取使目标函数上升最大的原则选择。
每增加一割平面方程，就增加一松弛变量,在用对偶单纯形法求解时，将离基，但以后它还可能成为基变量。
§3 一种新程序分枝定界法和割平面法只能用来求解中、小规模的问题，对于大型问题，前者常因分枝太多而疲于搜索，后者也往往由于割平面选择不当而收敛很慢，甚至找一个较好的可行解都不容易。因此迫切需要研究出可以求解大型问题的有效算法。
为了克服割平面法收敛慢的弱点，我们设计了一种新程序，这种程序也有明显的几何意义，它迭代步骤简单，计算最小，并可利用多台机器并行计算，从而很快求得最优解。因此颇适宜解大型问题，特别是在相应LP问题的基础上，它可以不必增加多少计算量就能很容易地求出一个相当好的近似解。
设（1）系数矩阵A的秩为m，目标函数系数为整数。再设相应的松弛问题（2）的最优表（3）化为最优典式表示如下
则知检验数，令松弛问题（2）的最优值
（8）
这里表示最优值的整数部分，，则问题（1）的最优值，引进辅助变量，考虑如下辅助问题：
（9）
其中K（以后也总）假定为非负整数。注意，由于（3）是最优表，故有。辅助问题（9）与（1）有如下关系。
定理2、如果问题（1）存在可行解，则X为（1）的可行解之充要条件是存在一个非负整数K，使为（9）的整数解，并且与X相应的（1）之目标函数值。
证：必要性。设X为（1）的可行解，则。因假定是整数，从而是整数。故存在一个非负整数K，使。又由松弛问题（2）之最优典式知，所以
于是由式（8），有
这说明是（9）的整数解。
充分性。如果存在一个非负整数K，使是辅助问题（9）的整数解，注意到式（9）与的关系，则显然，可见X是问题（1）的可行解，由辅助问题（9）的最后一个约束及知
（10）
再由式及（8），便有
（11）
推论、设，当时，式（9）的整数解为，则是问题（1）的最优解。
根据定理2及其推论知，为求解问题（1），可先就K＝0时考察辅助问题（9）的最优解（后面将说明式（9）之最优解极易求得）。若有整数解且等于0，则它即为式（1）的最优解，否则，说明原问题（1）没有目标函数值的可行解；再依次令，重复以上考察。下面的定理表明，上述过程不会无限的进行下去。
定理3、若对某个K，辅助问题（9）的最优值，则问题（1）不存在使自己目标函数值的可行解。
证：易见与问题（9）相应的初始单纯形表如下表所示：
表1
设对上表1实行单纯形迭代求得的最优解为，由定理假定，说明是基变量，注意到初始表中已是基变量，故寻优迭代中主元可不选在这一行。今把表中的K换成，其余不变。若，则行的常数项变大，故主元亦不能选在这一行，这样迭代过程便与原来的完全相同，于是有最优解，其最优值为。
若问题（1）存在的可行解，设，则，对该，由定理2之必要性，辅助问题（9）应有整数解，其最优值为0。这与以上的分析矛盾，故式（1）不存在的可行解。
依据定理3，若随着辅助问题（9）中K值的增加，迭代至某步出现，即可停止，原问题（1）无解。
由于表1最后两行除了这列以外是一样的，故主元一旦选在行，迭代一次后可立得最优解，可见式（9）中的最优解极易求出，然而考察其最优解中是否有整数解却并非易事。实际上注意辅助问题（9）的最后一个约束，当实际就是
（12）
不难看出，它是将（2）的目标函数之最优割平面向其可行解域里面平行推进的结果（程序的几何意义也就在于此），因此只要K取得不是很大，从而保证（12）总是穿过松弛问题（2）的可行域（此为定理3的几何解释），则一方面说明辅助问题（9）的最优值，另一方面又说明式（9）的最优解有无穷多。这样，判断是否有整数解就不容易了。不过易证下述论断成立。
定理4，假定松弛问题（2）是非退化的，又设在由辅助问题（9）出发寻找问题（1）的目标函数的可行解之过程中，典式的基变量仍保持非0的性质，若集合中无整数，则式（1）不存在含有（n-m-1）个0分量的可行解。
证：与典式比较，式（9）中增加了一个约束，故式（9）的基变量比式的多一个，由于假定式的基变量仍保持非0的性质，故迭代至最后，它们仍是基变量，这说明式（9）所增加的基变量必须在表1的（m+1）行取得。由于基变量全相同的基可行解必相等，故一开始就以（m+1）行的那个主元实行一次Gauss消元，所得即为最优解。这样，如果集合中无整数，则最优解中自然不会有整数解。故定理结论成立。
诚然，定理4中的假定事先无法验证，但考虑到问题（1）与其松弛问题（2）的最优解之间虽然可能相差很大，但后者的基变量变为0的情形在实际中比较少见，于是假定也就常被满足了。
基于以上理由，我们可以只考察辅助问题（9）的部分最优基可行解：
（13）
如其中有整数解，就得到问题（1）的一个的可行解；否则，增加K值，继续考察（13），以期得到一个可行解。具体的做法是先计算（13）中的第一式，挑出其中取整数的，看它们是否满足第二式，并取整数，如发现某不为整数，即将此弃之，转而考察别的。若能得到整数解，则已得式（1）的一个可行解，否则令K增加1，重复以上过程。
用本方法求解上节例2
将例2的最优表稍加改变：,检验数变号，即得表1的简化形式：
由定理4知，最小正检验数，故知当K=0时，问题无可行解。今取，最小比值均在最后一行，且知为整数，故宜以为主元，实行Gauss消元，得
故得可行解，它即是最优解，而最优值。
