1整数规划的数学模型2分枝定界法3割平面法40-1型整数规.ppt

2019/10/19,1.整数规划的数学模型2.分枝定界法3.割平面法4.0-1型整数规划5.指派问题,第五章 整数规划,2019/10/19,整数规划的数学模型,max(min)(c1 x1+ c2 x2 + cn xn )a11 x1+ a12 x2 + a1n xn (=,) b1a21 x1+ a22 x2 + a2n xn (=,) b2.am1 x1+ am2 x2 + amn xn (=,) bmx1n 0 且取整数纯整数规划: 所有变量都有取整约束混合整数规划: 只有部分变量有取整约束,2019/10/19,分枝定界法,1.分枝定界法的基本思路2.第65页例5-13.练习题,2019/10/19,分枝定界法的基本思路,2019/10/19,分枝定界法的基本思路,2019/10/19,第65页例5-1,max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1，x2 0且取整,2019/10/19,用分枝定界法解例5-1,1.求解相应的线性规划L0max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1，x2 0,2019/10/19,用分枝定界法解例5-1,x2 5 9x1+7x2=56 4 3 2 7x1+20x2=70 1 0 1 2 3 4 5 6 7 8 9 10 x1L0 : x* = (4.81, 1.82), Z* =356,2019/10/19,用分枝定界法解例5-1,2.将L0分解为L1和L2L1 ：max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1 4 x1，x2 0,L2 ：max z = 40x1 + 90x2 9x1 + 7x2 56 7x1 +20x2 70 x1 5 x1，x2 0,L1 ：X* = (4, 2.10), Z* = 349 L2 ：X* = (5, 1.57), Z* = 341 ,2019/10/19,用分枝定界法解例5-1,3.分解L1形成L3、L4，其中： L3 = L1, x22 L4 = L1, x23 L3 : X* = (4, 2), Z* = 340 L4 : X* = (1.42, 3), Z* = 327(1)取下界min=340(L3);(2)舍弃L4,2019/10/19,用分枝定界法解例5-1,4.分解L2形成L5、L6，其中： L5 = L2, x21 L6 = L2, x22 L5 : X* = (5.44, 1), Z* = 308 L6 : 无可行解(1)舍弃L5、L6；(2)得最优解X* = (4, 2), Z* = 340。,2019/10/19,例5-1求解过程示意图,练习题,max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 12 x1 + 2x2 15 4x1 + 5x3 26 x13 0且取整,2019/10/19,求解练习题,首先求解线性规划L0 :max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 + x 4 = 12 x1 + 2x2 + x5 = 15 4x1 +5x3 + x6 = 26 x16 0,2019/10/19,求解练习题,2019/10/19,求解练习题,2019/10/19,求解练习题,2019/10/19,求解练习题,2019/10/19,求解练习题,2019/10/19,割平面法,1.割平面法的基本思路2.例3.练习题,2019/10/19,割平面法的基本思路,同分枝定界法一样，割平面法也是一种利用连续模型求解非连续问题的常用方法。割平面法的基本思路是：当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。,2019/10/19,例,max z = x1 + x2 - x1 + x2 1 3x1 + x2 4 x1，x2 0且取整,2019/10/19,用割平面法解例,1.求解相应的线性规划L0max z = x1 + x2 - x1 + x2 1 3x1 + x2 4 x1，x2 0,2019/10/19,用割平面法解例,非整数解，为建立割平面，首先考虑非整数解中余数最大的基变量，此例中x1、 x2的余数均为3/4，不妨选取x2 ： x2 +3/4 x3 +1/4 x4 =7/4,2019/10/19,用割平面法解例,x2 +3/4 x3 +1/4 x4 =7/4现将各系数分成整数和非负真分数两部分，从而可得： (1+0)x2+(0+3/4) x3+(0+1/4) x4 =(1+3/4)将整数部分的变量移至等式右端有： 3/4 x3 +1/4 x4 =3/4+（1- x2 ）非负整数解(1- x2)为整数，左端非负故有： 3/4 x3 +1/4 x4 =3/4+非负整数从而： 3/4 x3 +1/4 x4 3/4 或 x2 1以x2 1为割平面可使可行域减少一个包括A点在内的三角形。,2019/10/19,x2 A 1 0 1 x1,用割平面法解例,2019/10/19,用割平面法解例,2019/10/19,练习题,max z = 2x1 + 5x2 + 4x3 x1 + x2 + x3 12 x1 + 2x2 15 4x1 + 5x3 26 x13 0且取整,2019/10/19,求解练习题,2019/10/19,求解练习题,选取x2： 1/2 x1+x2+1/2 x5 =15/2 1/2 x1+1/2 x5 =1/2 +（7- x2 ） 于是有割平面： 1/2 x1+1/2 x5 1/2或 x2 7,2019/10/19,求解练习题,2019/10/19,求解练习题,2019/10/19,0-1型整数规划,1.0-1规划： 0-1规划是整数规划的特例，是所有决策变量仅取0和1的整数规划问题。2.引例 （1）第69页例5-3 （2）引例 23. 0-1规划的隐枚举法 （1）隐枚举法的基本步骤 （2）第70页例5-4 （3）第71页例5-5,2019/10/19,第69页例5-3,某公司拟在东、西、南三个区建立销售门市部，拟议中有7个场点A17可供选择。东区的三个点A13 最多选两个，西区的两个点A45 最少选一个，南区的两个点A67 最少选一个。如果建设 Ai 点，需要投资 bi 元，年可获利 ci 元，公司可筹集到的投资总额为B元，问应如何决策才能使年利潤最大。,2019/10/19,例5-3,令xi = 0 或 1，其中： xi = 0 表示第I个点未被选取 xi = 1表示第I个点被选取其数学模型为： x1+ x2 + x3 2 x4+ x5 1 x6+ x7 1,2019/10/19,引例2,两种运输方式的限制条件分别为： 6x1 + 4x2 30 7x1 + 3x2 40互斥的约束统一于一个模型中： 6x1 + 4x2 30 + Mx3 7x1 + 3x2 40 + M(1-x3) 其中x3 为0-1变量。,2019/10/19,隐枚举法的基本步骤,1.目标函数极小化；2.目标函数系数非负化，如果xj 的系数为负数，可令 xj=1- xj ；3.决策变量按其目标函数系数的大小排列；4.令所有变量为“0”，检查该解的可行性，如果可行此解即为最优解，如果不可行进入下一步；5.按变量的顺序依次令各变量分别取“0”或“1”，根据分枝定界的原理进行剪枝，直至结束。,2019/10/19,第70页例5-4,Max z= 3x1 - 2x2 + 5x3 x1 + 2x2 - x3 2 x1+ 4x2 + x3 4 x13 =0或1第一步：Min w= -3x1 + 2x2 - 5x3 x1 + 2x2 - x3 2 x1+ 4x2 + x3 4 x13 =0或1,2019/10/19,例5-4,第二步：令x1 =1- x1， x3 =1- x3Min w= 3x1 + 2x2 + 5x3 - 8 -x1 + 2x2 + x3 2 -x1 + 4x2 - x3 2 x13 =0或1第三步：Min w= 2x2 + 3x1 + 5x3 - 8 2x2 - x1 + x3 2 4x2 - x1 - x3 2 x13 =0或1第四步： 令所有变量为“0”，得可行解，所以原问题的最优解为（1，0，1），最优值为8。,2019/10/19,max z= 8x1 + 2x2 - 4x3 - 7x4 - 5x5 3x1 + 3x2 + x3 +2x4 +3x5 4 5x1 + 3x2 - 2x3 - x4 + x5 4 x1 5 = 0或1经前三步有：令x1 =1- x1， x2 =1- x2min w= 2x2 + 4x3 + 5x5 + 7x4 + 8x1 - 10 3x2 - x3 - 3x5 - 2x4 + 3x1 2 3x2 +2x3 - x5 + x4 + 5x1 4 x1 5 = 0或1,第71页例5-5,2019/10/19,例5-5,2019/10/19,例5-5,w=-4 4 (可行解) w=-8 x3=1 x2=1 2 w= -10 x3=0 w= -3 1 5 x2=0 w= -6 3,2019/10/19,例5-5,w= -6 x5=1 8 w= -1 x3=1 6 x5=0w= -6 9 w=1 w=2 3 x3=0 w= -5 x4=1 12 w= -5 x5=1 10 7 x5=0 w= -3 x4=0 w=3 11 13,2019/10/19,指派问题,1.指派问题的内涵2.指派问题的数学模型3.指派问题的求解4.指派问题的扩展,2019/10/19,指派问题的内涵,有m 项工作，恰好有m 个人来完成，一个人只完成一项工作，一项工作只由一个人来完成，由于个人的专长不同，完成任务的效率也就不同，于是产生了应指派哪个人去完成哪项任务，才能使完成m 项任务的总效率最高的问题，此类问题称为指派问题或分派问题。指派问题同运输问题一样，是具有一定模型特征一类问题的总称，如m 项加工任务如何在m 台机床上分配；m 条航线如何指定m 艘船去航行等等。指派问题是运输问题的特例，也是0-1规划问题的特例。这一点可由指派问题的数学模型体现出来。,2019/10/19,指派问题的数学模型,2019/10/19,指派问题的求解匈牙利法,2.匈牙利法的基本步骤 (1)第73页例5-6 (2)第74页例5-7 (3)基本步骤总结,2019/10/19,指派问题的扩展,1. 人员与工作不匹配：引入假想的工作或人员 由于假想的工作或人员代表的是剩余的工作或人员，所以其对应的效率矩阵元素全都为零。 例2. 目标函数求极大值：效率矩阵的每一元素乘“-1”，并进一步使其非负化。 第73页例5-6,2019/10/19,第73页例5-6,2019/10/19,例5-6,2019/10/19,第74页例5-7,2019/10/19,例5-7,2019/10/19,例5-7,2019/10/19,例5-7,2019/10/19,例5-7,2019/10/19,例5-7,2019/10/19,例5-7,2019/10/19,例5-7,2019/10/19,基本步骤总结,1.每行减去一个最小元素；2.每列减去一个最小元素；经此两步，效率矩阵每行、列都至少有一个“0”。3.每行、列若只有一个“0”元素，打上“（）”，同时划去与其同列、行的其它零元素，先前已被划去的零元素不计算在内，如果出现零元素的闭合回路，则任选一个零元素打上“（）”，同时划掉与其同行和同列的零元素。经过第三步可能出现两种结果：(1)每行均有打“( )”的零元素,此时已得最优解; (2)并非每行均有打“( )”的零元素，进入第四步。4.给没有“( 0 )”的行做标记“”；5.在做 “”标记的行上对所有“0”所在的列做标记“”；6.覆盖掉没有“”标记行上的所有元素和有 “”标记列上的所有元素。经过此步矩阵中的所有“0”均被覆盖掉了，只留下了部分非零元素。7.每一非零元素减去它们中的最小值，并给同时处在被覆盖掉行和被覆盖掉列的元素加上这一最小值。8.重复37直至得到最优解。,2019/10/19,例,12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10,2019/10/19,例,12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 0 0 0 0 0 ,2019/10/19,例,5 (0) 2 0 2 2 3 (0) 0 0 (0) 10 5 7 5 9 8 0 (0) 4 0 0 0 0 (0) 方案1:甲-B、乙-C、丙-A、丁-D工作E剩余，min z = 26 ,2019/10/19,例,5 0 2 (0) 2 2 3 0 0 (0) (0) 10 5 7 5 9 8 (0) 0 4 0 (0) 0 0 0 方案2:甲-D、乙-E、丙-A、丁-C工作B剩余，min z = 26 ,2019/10/19,例,12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 7 7 6 6 6 方案 :甲-B、乙-C和E、丙-A、丁-D min z = 32,2019/10/19,第73页例5-6,10 9 8 7 3 4 5 6 2 1 1 2 4 3 5 6,2019/10/19,例5-6,-10 -9 -8 -7 -3 -4 -5 -6 -2 -1 -1 -2 -4 -3 -5 -6,2019/10/19,例5-6,0 1 2 3 3 2 1 0 0 1 1 0 2 3 1 0,2019/10/19,例5-6,(0) 0 1 3 3 1 (0) 0 0 (0) 0 0 2 2 0 (0)方案之一为：M1-W1、 M2-W3、 M3-W2、 M4-W4 max z = 22,