整数规划(第4章).ppt

,第四章 整数规划,1 引 言 整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。 根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。,整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。,例1：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。问如何携带他能够受益最大？,解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划: Max Z= 20x1+15x2 +18x3 +14x4 +8x5 +4x6 +10x7 s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1或xi=0 i=1,2,.7,数学模型 整数规划(IP)的一般数学模型: Max (min) Z = cjxj s.t. aijxj bi(i=1,2,m) xj 0 且部分或全部是整数,求解误区：先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。,例2 求下列问题： Max Z=3x1+13x2 s.t.2x1+9x2 40 11x1-8x2 82 x1,x2 0,且取整数值,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4) Z0=58.8，而原整数规划最优解I(2,4) Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。但求“整点凸包”十分困难。,E,F,G,H,I,J,2 分枝定界解法 （Branch and Bound Method) 原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P） 都称为（IP）的松驰问题。,最通常的松驰问题是放弃变量的整数性要求后，（P）为线性规划问题。,分枝定界法步骤 一般求解对应的松驰问题，可能会出现下面几种情况： 若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。,分枝定界法步骤 一般求解对应的松驰问题，可能会出现下面几种情况： 若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。 若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。,若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。,若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。 从不满足整数条件的基变量中任选 一个xl进行分枝，它必须满足xl xl 或xl xl +1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。,定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。,定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。 剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。,例3用分枝定界法求解： Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。,0 1 2 3 4,4 3 2 1,x1,x2,分枝：X1 1,x1 2,P1,P2,两个子问题： （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),（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),0 1 2 3 4,4 3 2 1,x1,x2,再对（P1）分枝：X1 1 （P3） x2 2 （P4） x2 3,P1,P2,P3,P4,（P1）两个子问题： （P3）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 2整数 用单纯形法可解得相应的（P3）的最优解（1，2） Z=10,（P1）两个子问题： （P4）Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 3整数 用单纯形法可解得相应的（P4）的最优解（0，3） Z=9,X1 2,X2 2,X1 1,X2 3,P1:(1,9/4) Z=10(3/4),P4: (0,3) Z=9,P2:(2,1/2) Z=9(1/2),P3: (1,2) Z=10,P:(6/5,21/10) Z=111/10,原问题的最优解（1，2） Z=10,例4用分枝定界法求解： Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解（10/3，4/3）Z=26/3为各分枝的下界。,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,选 x1进行分枝： (P1) x1 3 (P2) x1 4 为空集,P1,（P1） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 3 整数 用单纯形法可解得（P1）的最优解（3，3/2）Z=9,（P2） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 4 整数 无可行解。,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,对(P1) x1 3 选 x2进行分枝： (P3) x2 1无可行解 (P4) x2 2,P4,（P3） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 1整数 无可行解。,（P4） Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0， x1 3 ，x2 2整数 用单纯形法可解得（P4）的最优解（2，2）Z=10,X1 4,X2 1,X1 3,X2 2,P1:(3,3/2) Z=9,P4:(2,2) Z=10,P2:无可行解,P3:无可行解,P:(10/3,4/3) Z=26/3,原问题的最优解（2，2） Z=10,3、0-1型整数规划 0-1型整数规划是整数规划中的特殊情形，它的变量仅取值0或1。在本节我们先介绍引入0-1变量的实际问题，再研究其解法隐枚举法。 一、引入0-1变量的实际问题 1、相互排斥的变量 2、相互排斥的约束条件 3、关于固定费用的问题 二、0-1型整数规划的解法-隐枚举法,指 派 问 题,在生活中经常遇到这样的问题，某单位需完成n项任务,恰好有n个人可承担这些任务。由于每人的专长不同，个人完成任务不同，效率（或所费时间）也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最少）。这类问题称为指派问题或分派问题，它是0-1规划的特例,例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种德说明书所需时间如下表所示。问应指派何人去完成何工作，使所需总时间最少？,