运筹学：03-整数规划

1、整数规划,整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。 根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。,引言,整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。,整数规划研究现状,一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤，设计方案，使携带的物品最重要。,背包问题,解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划: Ma

2、x Z= 20 x1+ 15x2 + 18x3 +14x4 + 8x5 + 4x6 + 10 x7 s.t. 5x1 + 5x2 + 2x3 + 6x4 + 12x5 + 2x6+ 4x7 25 xi=1或xi=0 i=1,2,.7,背包问题规划模型,一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?,一维背包问题,解：如果令xj=1

3、表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划。,一维背包问题规划模型,整数规划(IP)一般数学模型,因为可行方案数目有限，所以找出所有组合方案，经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。 设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。,组合法求解？,先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，

4、特别是0-1规划时，往往不能成功。,四舍五入?,整数规划求解举例,可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4) Z0=58.8，而原整数规划最优解为I(2,4) Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,整数解与松弛问题的解,假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。,整点凸包,假如把可行域分解成五个互不相交的子问题P1 、 P2、 P3、 P4、 P5、 P6之和, P4、 P5 、 P6的定义域都是空集,而放弃

5、整数要求后P1最优解I(2,4),Z1=58， P2最优解(6,3),Z2=57， P3最优解(98/11,2),Z4=52。,分解可行域,假如放弃整数要求后，用单纯形法求得最优解，恰好满足整数性要求，则此解也是原整数规划的最优解。,松弛问题解为整数解,原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P） 都称为（IP）的松驰问题。,分支定界解法,若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。 若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。 若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优

6、解。,松驰问题解的可能性,从不满足整数条件的基变量中任选 一个xl进行分支，它必须满足 xl xl 或 xl xl +1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。,分支,把满足整数条件各分支的最优目标函数值作为上（下）界，用它来判断分支是保留还是剪枝。,定界,把那些子问题的最优值与界值比较，凡不优或不能更优的分支全剪掉，直到每个分支都查清为止。,剪枝,例：max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分支的上界。,分支定界法求

7、解应用,分支定界法求解应用:分支,（P1）max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ，整数 x1 1 用单纯形法可解得相应的（P1）的最优解（1，9/4）, Z=10(3/4),求解子问题P1,（P2）max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ，整数 x1 2 用单纯形法可解得相应的（P2）的最优解（2，1/2）， Z=9(1/2),求解子问题P2,比较子问题的解,（P1）的最优解（1，9/4）, Z=10(3/4) （P2）的最优解（2，1/2），Z=9(1/2) 分支（P1）的解更优

8、，先分解分支（P1）。,分解分支（P1）,（P11）max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , 整数 x1 1, x2 2 用单纯形法可解得相应的（P11）的最优解（1，2），Z=10。,求解子问题P11,（P12）max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , 整数 x1 1, x2 3 用单纯形法可解得相应的（P12）的最优解（0，3），Z=9。,求解子问题P12,分支求解结果,指派问题,设有n 个人A1, A2, An,要分派去做n件事B1, B2 Bn,要求每一件事都 必须有一个

9、人去做,而且不同的事由不同的人去做.已知每个人Ai做每件事Bj的效率(如劳动工时或成本,或创造的价值等)为Cij,问应如何进行指派(哪个人做哪件事),才能使 工作效益最好(如工时最少,或成本最低,或创造的价值最大)?,指派问题：分析,Cij为Ai完成工作Bj的效率,Xij决定Ai是否做工作Bj，为0-1决策变量,指派问题：分配要求,指派问题：模型,指派问题：实例,有4 个工人,要指派他们分别完成4 项工作,每人做各项工作所消耗的时间如下表:问如何指派使总的消耗时间最小?,指派问题：思考问题,1、人数比工作数多怎么处理？ 2、人数比工作数少，模型会怎样变化? 3、计算机求解方法？,互斥约束 矛盾

10、约束 在建立数学模型时，有时会遇到相互矛盾的约束，模型只要求其中的一个约束起作用。,特殊约束的处理,下面两个约束是相互矛盾 f(x) 5 (1) 或 f(x) 0 (2) （1）表示为：5 f(x) 0 (3) 引入一个0-1变量y,则： 5 - f(x) M（1-y） (4) f(x) My (5) M是足够大的整数，y 是0-1变量,矛盾约束,例如：模型希望在下列n个约束中，只能有一个约束有效： fi(x) 0 i=1,2,.n, 引入 n个0-1变量yi （i=1,2,n） yi=0，表示第I个约束无效 yi=1，表示第I个约束有效则上式可改写为： fi(x) M(1-yi) y1+ y

11、2 + + yn=1,多中选一的约束,如果希望有k个约束有效，则： fi(x) M(1-yi), y1+ y2 + + yn= k 如果希望至多有k个约束成立，则： fi(x) M(1-yi), y1+ y2 + + yn k 如果希望至少有k个约束成立，则： fi(x) M(1-yi), y1+ y2 + + yn k,多个约束有效,比较典型的逻辑关系是 if-then关系，也称if-then约束，这类逻辑关系一般涉及两个约束，如果第一个约束成立，则第二个约束也必须成立，否则，如果第一个约束不成立，则第二个约束也可以不成立。可以描述如下： 如果f (x)0成立，则g (x) 0必须成立； 如

12、果f (x)0不成立，则对g (x)无限制。 引入0-1变量： f (x) -M(1-y) (*) g (x) My,逻辑关系约束,如果f (x)0成立，则g (x) 0必须成立； 如果f (x)0不成立，则对g (x)无限制。 引入0-1变量： f (x) -M(1-y) (*) g (x) My 说明： 如果f (x)0成立，则y不能为1，否则与（*）矛盾； 所以 y=0, g (x) 0 成立。 如果 f (x) 0（即f (x)0不成立） 则y的取值已无关紧要，因为y取任何值（*）总成立，所以y的取值由（*）控制，因此g (x) 的取值不受任何限制。,逻辑关系约束说明,集合覆盖和布点问题,给定集合一的每个元素必须被集合二的元素覆盖。在满足覆盖集合一所有元素的前提下，集合二的元素最少。该问题也称为布点问题。,集合覆盖和布点问题,一个城市有六个区，每区都可建消防站。市政府希望建站最少，但必须满足在城市任何地区发生火警时，消防车都能在15分钟内赶到现场，实测各区之间消防车行驶时间如下表：,集合覆盖