运筹学05整数规划.ppt

整数规划 Integer Programming,整数规划的数学模型 Mathematical Model of IP 整数规划的分支定界法 Branch and Bound Method for IP 整数规划的割平面法 Cutting Plane Method for IP 0-1整数规划 Binary Integer Programming 指派问题 Assignment Problem,1 整数规划的数学模型,相关定义 一部分或全部决策变量取整数值的规划问题称为整数规划(Integer Programming) 整数规划中不考虑整数条件所对应的规划问题，称为该整数规划的松弛问题(Slack Problem) 松弛问题为线性规划的整数规划问题称为整数线性规划(Integer Linear Programming),整数线性规划一般形式 min(max) z=c1x1+c2x2+cnxn ai1x1+ai2x2+ainxn=bi(i=1,2,m) xi0(i=1,2,n)且部分或全部取整数,整数规划的几种类型 纯整数线性规划(Pure Integer Linear Programming)：决策变量全为整数的线性规划 混合整数线性规划(Mixed Integer Linear Programming)：至少一个变量为整数和非整数的线性规划 0-1型整数线性规划(0-1 Integer Linear Programming)：全部变量为0或1的线性规划,例1：某服务部门各时段(每2小时为一时段)需要的服务员最少人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作班次，使服务部门服务员总数最少。,解答： 设在第j时段开始上班的服务人数为xj。数学模型为： min z=x1+x2+x3+x4+x5 x110 x1+x28 x1+x2+x39 x1+x2+x3+x411 x2+x3+x4+x513 x3+x4+x58 x4+x55 x53 xi取非负整数(i=1,2,3,4,5),整数规划解的特点 松弛问题可行解的集合是一个凸集，任意两点凸组合依然是可行解；而整数线性规划可行解的集合是松弛问题可行解的集合的一个子集，任意两点凸组合不一定是可行解。 整数线性规划的最优解的目标函数值不会优于其松弛问题。 考虑下面的整数规划问题 max z=x1+4x2 -2x1+3x23 x1+2x28 x1,x2取非负整数,0 1 2 3 4 5 6 7 8,P,整数规划最优解,松弛问题最优解,A*,z=x1+4x2=12,z=x1+4x2=94/7,z=x1+4x2,x1,x2,x1+2x2=8,-2x1+3x2=3,2 整数规划的分支定界法,分支定界法(Branch and Bound Method)是在枚举法基础上的改进，是一种隐枚举法(Implicit Enumeration Method)或者部分枚举法(Partial Enumeration Method)，不是一种有效算法。 思路：利用其松弛问题的最优解(值)来分支定界。 关键：分支定界法的关键是分支和定界。 分支：若得到松弛问题的一个最优解，分量x1=x1*不是一个整数。则将原松弛问题分别加上x1x1*和x1x1*+1这两个约束条件，构成两个松弛问题继续求解，这个过程体现了分支。 定界：在以后的计算中遇到整数规划问题的最优解，其目标函数就可以设定为一个界限。不考虑比这个值小的可行解和最优解。,例2：求解整数规划问题A,3 整数规划的割平面法,割平面法的基本思想 求该整数规划松弛问题的最优解 如最优解恰是一个整数解，则停止 如果线性规划的最优解不是整数解： 则要求构造一个新的约束，对线性规划问题的可行域进行切割，切除已经得到的线性规划的最优解，但保留原可行域中所有的整数解 求解新的线性规划问题 如此一直进行,例3：用割平面法求解以下整数规划 Min z=3x1+4x2 3x1+x24 x1+2x24 x1,x20且x1,x2为整数,先求相应的线性规划问题，得到最优单纯形表,选择一个非整数的基变量，如x2构造约束条件，则 b2=8/5=1+3/5，I2=1，F2=3/5 y23=1/5=0+1/5，I23=0，F23=1/5 y24=-3/5=-1+2/5，I24=-1，F24=2/5 故附加的约束条件为：3/5-(1/5x3+2/5x4)0 即1/5x3+2/5x43/5,将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5，得到,用对偶单纯形法，x5离基，x3进基,已获得整数的最优解。,4 0-1整数规划,对于是否执行某些决策等“是-否”或“有-无”问题，可借助0-1整数变量，也可称决策变量、指标变量、逻辑变量、二进制变量。 设xj=1(若决策j为是)，或者xj=0(若决策j为否)，则： 若多个决策方案中恰好选中一个方案，可以表示为xj=1 选中不多于一个方案：xj1 选中不少于一个方案：xj1,对于两个0-1决策变量x1和x2的逻辑关系，若假设其发生则取值为1，否则取值为0，那么基本形式为 (1)或关系：x1或x2，x1+x21 (2)与关系：x1与x2，x1+x2=2 (3)非关系：非x1，x1=0，1-x1=1 (4)蕴含关系：x1发生则x2必发生，x1-x20 (5)当且仅当关系：x1-x2=0,0-1变量可以表示特殊约束,(1)部分约束 m个约束条件ai1x1+ainxnbi(i=1,m)，定义yi=1表示第i个约束条件不起作用,yi=0表示第i个约束条件起作用，定义M为任意大的正数，则其中k个条件起作用的表示为 a11x1+a1nxnb1+My1 a21x1+a2nxnb2+My2 am1x1+amnxnbm+Mym y1+ym=m-k,(2)选择取值 约束条件的左端项是f(x1,xn)，右端项可能是N个值(b1,bN)中的某一个。可以定义yi=1表示选中bi，yi=0表示不选中bi，则 f(x1,xn)biyi y1+yN=1,(3)固定费用 总费用Cj(xj)为固定费用(kj)和变动费用(cjxj)之和，若有产量(xj0)则固定费用发生；若无产量(xj=0)则固定费用不发生。可以设置逻辑变量yi=1表示产量xi0，yi=0表示产量xi=0，则 min z=Cj(xj)=(cjxj+kjyj) 其他原始限制条件 xj-Myj0 xj0,yj=0或1,(4)逻辑关系 若f(x)0成立(即f(x)0不成立)，则g(x)0必须成立；若f(x)0不成立，则g(x)无限制 (a)引进逻辑变量y=1或0，则 f(x)-M(1-y) g(x)My (b)或者设y1,y2取值0或1，则 -f(x)M(1-y1) g(x)My2 y1-y20 可推广到多个约束条件，见(1)部分约束,0-1规划模型求解,(1)枚举法 当问题规模小，枚举法求解0-1规划可列出全部组合方案，从而判断最优解。 例4：用枚举法求解下列0-1规划问题。 max z=2x1+4x2+x3 x1+x2+2x33 2x1-x2+x32 -x1+2x2+3x31 x1,x2,x30,1,(2)隐枚举法 对枚举法加以改进，通过增加某些过滤条件，去除那些明显不是最优解的解，就避免逐一检查是否可行 (a)观察约束条件，如x1+3x2+2x3+2x45，如果x2=1,x3=1,其他任何变量取1都不可行 (b)考察目标函数，如某可行解使z=z0，如果新的可行解z1z0，则绝对不是最优解 举例：略,(3)分枝定界法 与整数规划的分枝定界法一样。由于是0-1规划，故分枝定界较快：对不是整数的某可行解xj，分枝时只要分解为xj=1和xj=0两个枝即可。定界时重新设定目标函数z的上下限。 举例：略,5 指派问题(Assignment Problem),指派问题的标准形式 标准指派问题的匈牙利算法 非标准指派问题及其求解思路,指派问题的标准形式,在我们现实生活中，常有各种性质的指派问题。例如：应如何分配若干项工作给若干个人(或部门)来完成，以达到总体的最佳效果等等。 由于指派问题的多样性，我们有必要定义指派问题的标准形式。,设n个人做n件事，要求每人必须而且只做一件事，每件事允许而且只允许一个人来完成。设第i人做第j件事的费用为cij(i,j=1,2,n)，假定cij0，这样我们可以得到指派问题的系数矩阵C=(cij)nn。指派问题就是，如何指派每个人的任务可使总费用最少。,为了建立标准指派问题的数学模型，我们引入n个0-1变量：设xij=1表示指派第i人做第j事，xij=0表示第i人不做第j事。则数学模型为 min z=cijxij xi1+xi2+xin=1 (i=1,2,n) x1j+x2j+xnj=1 (j=1,2,n) xij0,1 (i,j=1,2,n),标准指派问题的匈牙利算法,步骤1：造零。将费用矩阵每行减去该行的最小值；每列减去该列的最小值。 步骤2：盖零。用最少的线覆盖所有零，线条数等于n就转下一步骤，否则继续造零。 步骤3：保零。保证每行和每列都有且只有一个零。 步骤4：变零。将为零的地方变为1，其余为0，得到任务安排。,例5：求解下列指派问题,解答：利用匈牙利法计算如下,非标准指派问题及其求解思路,在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将他们化为标准形式，然后再用匈牙利算法解之。 (1)最大化指派问题。设最大化指派问题系数矩阵C=(cij)nn，其中最大元素为m，令矩阵B=(bij)nn=(m-