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