第五章 整数规划主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。

如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题211020m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96m ax ,0,8.421===z x x 。

用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。

下面介绍几种常用解法。

§2 分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。

基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值*z的上界，记为z ；而A 的任意可行解的目标函数值是*z的一个下界z ，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。

现举例说明： 例2 求解A219040m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,702075679x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82,①② ③ ④ ⑤=0z 356（见下图）。

显然，它不符合整数条件⑤。

这时，0z 为问题A 的最优值*z 的上界，记0z z =，而=1x 0, =2x 0显然是问题A 的一个整数可行解，这时z=0，是*z 的一个下界，记0=z ，即2560*≤≤z 。

分枝定界法的解法，首先注意其中一个非整数变量的解，如1x ，在B 中1x =4.81，于是对原问题增加两个约束条件：5411≥≤x x 、，可将原问题分解为两个子问题21B B 、（即两枝），给每枝增加一个约束条件，如图。

8不考虑整数条件解问题21B B 、得到最优解：显然未得到全部变量是整数解，21z z > ，∴将z改为349（z =349），3490*≤≤z 。

继续对问题21B B 、进行分解，21z z > ，∴先分解1B 为两枝，增加条件22≤x 的问题称为3B ；增加条件32≥x 的问题称为4B 。

在上图中再去掉22>x 与32<x 之间的可行域，再求解问题43B B 、，其结果列在下图中，可见问题3B 的解已都是整数，它的目标函数值3403=z ，取z=340，而它大于3274=z ，所以再分解4B 已无必要，而问题2B 的3412=z ，所以*z可能在341340*≤≤z 之间有整数解，于是再对2B 分解，得问题65,B B ，5B 为非整数解，且35308z z <=，问题6B 为无可行解，于是可断定：340*3===z z z ，2,421==x x 为最优整数解。

356=z349,0==z z由以上解题过程可得到分枝定界法的求解步骤：1. 给定原问题的初始上界z解与原问题A 相应的线性规划问题B ，可能出现以下情况之一：①B 没有可行解，这时A 也没有可行解，则停止；②B 有最优解，并符合A 的整数条件，B 的最优解即为A 的最优解，则停止； ③B 有最优解，但不符合A 的整数条件，记它的目标函数值0z 为z 。

2. 给定原问题的初始下界z用观察法找出问题A 的一整数可行解，一般取n j x j ,,2,1,0 ==。

求得其目标函数值，记作z 。

这样，就有z z z ≤≤*。

3. 分枝在B 的最优解中任选一个不符合整数条件的变量j x ，其值为j b ，以[j b ]表示小于j b 的最大整数，构造两个约束条件:][j j b x ≤和1][+≥j j b x并将其分别加入问题B ，求两个后继规划问题21B B 、，不考虑整数条件，解这两个后继问题。

4. 定界（修改上、下界）以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z ，从已符合整数条件的各分支中，找出目标函数值的最大者作为新的下界z 。

5. 比较与剪枝各分枝的最优目标函数值中若有小于z 者，则剪掉这枝，以后不再考虑了，若大于z ，且不符②③ ④ ⑤合整数条件，则继续分枝直到得到z z =*为止，求得最优整数解),,2,1(*n j x j =。

§3 割平面法这个方法的基础仍是用解线性规划的方法去解整数规划问题，首先不考虑变量j x 是整数这个条件，但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。

这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。

例3 求解21m ax x x z += ① ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+-整数21212121,0,431x x x x x x x x 如不考虑条件⑤，求得相应的线性规划的最优解：就是图中可行域R 的极点A ，不符合整数条件。

432100m ax x x x x z +++=⎪⎪⎩⎪⎪⎨⎧==≥=++=++-4,,2,14,,2,10431421321 j x j x x x x x x x j j为整数 不考虑整数条件，用单纯形法求解相应线性规划的最优解。

410max ,47,4321===z x x25max ,47,4321===∴z x x 由最终表中得到变量间的关系式：474143434141432431=++=+-x x x x x x将系数和常数项都分解为整数和非负真分数之和，并移项变为⎪⎭⎫ ⎝⎛+-=-⎪⎭⎫ ⎝⎛+-=-43243314143431414343x x x x x x x现考虑整数条件，21,x x 为非负整数，那么43,x x 也是非负整数。

对上式，从等式左边看是整数，等式右边的（）是正数，所以等式右边定一为负数，即041434343≤⎪⎭⎫⎝⎛+-x x 。

整理得：3343-≤--x x ------切割方程将新的约束方程，引入松驰变量，得到33543-=+--x x x ，将其列入最终表∴最优解TX )0,0,1,1,1(*=，最优值z=2一、割平面法的解题步骤：1. 若i ij b a ,中有分数，先全部整数化，而后引入松驰变量，暂不考虑整数约束条件，用单纯形法求出相应线性规划的最优解。

2. 求切割方程①令i x 是相应线性规划最优解中为分数值的一个基变量，由最终单纯形表得到i kk ik i b x a x =+∑ （1）其中：Q i ∈（Q 指构成基变量下标的集合）K k ∈（K 指构成非基变量下标的集合）②将i b 和ik a 都分解成整数部分N 与真分数f 之和，即i i i f N b +=，其中10<<i f （2） ik ik ik f N a +=，其中10<≤ik f而N 表示不超过b 的最大整数，如：若 b=2.35，则N=2 f=0.35b=–0.45,则N=–1 f=0.55将（2）代入（1）得∑∑-=-+kk ik i i kk ik i x f f N x N x③现在提出变量为整数的条件，上式由左边看必是整数，由右边看，因为10<<i f 所以不能为正，即0≤-∑kk ik i x f f -------- 割线方程3. 把切割方程作为新的约束条件，并入单纯形最优表。

继续换算，取得最优解。

二．割平面法的性质1. 割平面法割去了整数规划原问题相应的线性规划问题的最优解。

2. 割平面未割去整数规划原问题的任一可行解，即未割去其相应的线性规划问题的任一整数可行解。

§4 0–1规划一、0-1变量及其应用0-1型整数规划是整数规划的特殊情形，它的变量i x 仅取值0或1，这时i x 称为0-1变量，或称二进制变量。

0-1变量作为逻辑变量（logical variable ）,常用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。

例如⎩⎨⎧=时）时（即取当决策不取方案时当决策取方案P P P x 01当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述。

一般地，设问题有有限项要素n E E E ,,,21 ，每项i E 有两种选择i A 和),,2,1(n i A i =，则可令),,2,1(01n i A E A E x ii i i i =⎪⎩⎪⎨⎧=选择若选择若那么，向量T n x x x ),,,(21 就描述了问题的特定状态或方案，即⎪⎪⎪⎩⎪⎪⎪⎨⎧=----T n n T T n n T T n n T Tn n T T n A A A A A A A A A A A A A A A A x x x ),,,,(,)0,0,,0,0(),,,,(,)0,0,,0,1(),,,,(,)0,1,,1,1(),,,,(,)1,1,,1,1(),,,(12112112112121 若选择若选择若选择若选择1、选址问题----相互排斥的计划例4 某公司拟在市东、西、南三区建立门市部，拟议中有7个位置A i )7,,2,1( =i 可供选择，规定在东区，由321,,A A A 三个点中至多选两个； 在西区，由54,A A 两个点中至少选一个； 在西区，由76,A A 二个点中至少选一个。

如选用i A 点，设备投资估计为i b 元，每年可获利润估计为i C 元，但投资总额不能超过B 元，问应选择哪几个点可使利润为最大？ 解：先引入0–1变量i x )7,,2,1( =i令 ⎩⎨⎧=点未被选用当点被选用当i i i A A x ,0,1 )7,,2,1( =i于是问题可列成： ∑==71max i i i x c z⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥+≥+≤++≤∑=10112765432171或i i i i x x x x x x x x B x b 2、相互排斥的约束条件例5. 某厂决定生产两种产品，有两种加工方法可供选用，已知设备供应情况：问选用哪种加工方法收益最大。