第二讲 整数规划及0-1规划

整数规划与0-1规划主讲：毛何悦电话息与计算科学1什么是整数规划与0-1规划？定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。整数规划的分类（一般指整数线性规划）变量全限制为整数时，称纯（完全）整数规划。变量部分限制为整数的，称混合整数规划。变量只能取0或1时，称之为0-1整数规划。2例13例2背包问题4

整数规划特点(1)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。原线性规划最优解不全是整数，则整数规划最优解小于原线性规划最优解（max）或整数规划最优解大于原线性规划最优解（min）。整数规划无可行解。(2)整数规划最优解不能按照实数最优解简单取整而获得。5整数规划求解方法分类（i）分枝定界法—可求纯或混合整数线性规划。（ii）割平面法—可求纯或混合整数线性规划。（iii）隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法—求解各种类型规划。6整数规划-分枝定界法对有约束条件的最优化问题的可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。7例题演示例3求解下述整数规划s.t.

AB先不考虑整数限制，即解相应的线性规划，得最优解为：

8显然它不符合整数条件。这时Z是问题A的最优目标函数值Z*的上界，记作。而显然是问题A的一个整数可行解，这时Z=0，是Z*的一个下界，记作，即9分支因为当前均为非整数，故不满足整数要求，任选一个进行分枝。设选进行分枝，把可行集分成2个子集：因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：10再定界：

对问题B1再进行分枝得问题B11和B12，它们的最优解为:

再定界：，并将B12剪枝。对问题B2再进行分枝得问题B21和B22，它们的最优解为:

无可行解。将剪枝，于是可以断定原问题的最优解为：110<=Z*<=355.8799340<=Z*<=355.8799340<=Z*<=341.4121314小结从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：首先，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。i）解问题B可能得到以下情况之一：（a）B没有可行解，这时A也没有可行解，则停止．（b）B有最优解，并符合A问题的整数条件，B的最优解即为A的最优解，则停止。（c）B有最优解，但不符合问题的整数条件，记它的目标函数值为。15小结（续）ii）用观察法找问题A的一个整数可行解，一般可取试探，求得其目标函数值，并记作。以表示问题的最优目标函数值；这时有其次，进行迭代。第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示小于bj的最大整数。构造两个约束条件:将这两个约束条件，分别加入B问题，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无作用=0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于者，则剪掉这枝，即以后不再考虑了。若大于，且不符合整数条件，则重复第一步骤。一直到最后得到=为止。得最优整数解。

16分析整数规划关键是找到一下限-最大化问题（或上限-最小化问题），用来剪枝，通过观察法，我们往往可以得到这个下限或上限，但是有没有更好的办法来得到一个相对较好的值呢？初值选取----蒙特卡洛法17MATALB求解命令%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id)%整数线性规划分支定界法，可求解全整数或混合整数线性规划。%y=minf'*xs.t.G*x<=hGeq*x=heqx为全整数或混合整数列向量。%[x,y]=IntLp(f,G,h)%[x,y]=IntLp(f,G,h,Geq,heq)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id)%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options)%x:最优解列向量；y:目标函数最小值；f:目标函数系数列向量%G:约束不等式条件系数矩阵；h:约束不等式条件右端列向量%Geq:约束等式条件系数矩阵；heq：约束登时条件右端列向量%lb:自变量下界列向量（default:-inf）%ub:自变量上界列向量（default:inf）%x:迭代初值列向量%id:整数变量指标列向量，1-整数，0-实数（default:1）%options的设置请参见optimset或linprog18求解例1f=[-20-10];G=[54;25];h=[24;13];[x,y]=IntLp(f,G,h,[],[],[0;0],[inf;inf])

x=[4.00001.0000]z=90190-1型整数规划

0-1型整数规划是整数规划中的特殊情形，它的变量xj仅取值0或1。这时xj称为0-1变量，或称二进制变量。xj仅取值0或1这个条件可由下述约束条件：整数所代替，是和一般整数规划的约束条件形式一致的。我们先介绍引入0-1变量的实际问题，再研究解法。20例4投资场所的选定—相互排斥的计划

某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai(i=1,2,…,7)可供选择。规定在东区：由A1,A2,A3三个点中至多选两个；在西区：由A4,A5两个点中至少选一个；在南区：由A6,A7两个点中至少选一个。

如选用点Ai，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？21解题时先引入0-1变量xi(i=1,2,…,7),令：于是问题可列写成：22例5关于固定费用的问题（FixedCostProblem）

在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决。某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令

xj表示采用第j种方式时的产量；

cj表示采用第j种方式时每件产品的变动成本；

kj表示采用第j种方式时的固定成本。23为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为:在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量yj，令

于是目标函数240-1型整数规划解法之一（过滤隐枚举法）

解0-1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n个组合。对于变量个数n较大（例如n>10），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（ImplicitEnumeration），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

25例6求解思路及改进措施：先试探性求一个可行解，易看出满足约束条件，故为一个可行解，且相应的目标函数值为因为是求极大值问题，故求最优解时，凡是目标值的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：称该条件为过滤条件(FilteringContraint)。

26从而原问题等价于：

s.t.

27从而得最优解，最优值28MATALB求解命令x=bintprog(f)x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)x=bintprog(f,A,b,Aeq,beq,x0)x=bintprog(f,A,b,Aeq,Beq,x0,options)[x,fval]=bintprog(...)[x,fval,exitflag]=bintprog(...)[x,fval,exitflag,output]=bintprog(...)[x,f]=Lp01_e(c,A,b,N)%枚举法[x,f]=Lp01_ie(c,A,b,N)%隐枚举法%Lp01_e和Lp01_ie分别为枚举法和隐枚举法%求解0-1线性规划问题%minf=c'*x,s.t.A*x<=b,x的分量全为整数0或1,%其中N表示约束条件Ax≤b中的前N个是等式，N=0时可以省略。%返回结果x是最优解，f是最优解处的函数值。29练习（一个分派问题）有5个工人，要分派他们分别完成5项工作，每人做各项工作所消耗的时间如下表，问应如何安排工作，可使总的消耗时间最小？工作工人甲乙丙丁戊ABCDE53567645748675646927518683031c=[5684534661557986757674628];A=[1000010000100001000010000010000100001000010000100000100001000010000100001000001000010000100001000010000010000100001000010000111111000000000000000000000000011111000000000