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