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

1、2022-12-202022-12-20整数规划的数学模型整数规划的数学模型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 且取整数且取整数纯整数规划纯整数规划:所有变量都有取整约束所有变量都有取整约束混合混合整数规划整数规划:只有部分变量有取整约束只有部分变量有取整约束2022-12-202022-12-20分枝定界法的基本思路分枝定界法的基本思路2022-12-20分枝定界法的基本思路分枝定界法的基本思路202

2、2-12-20第第65页例页例5-1max z=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1，x2 0且取整2022-12-20用分枝定界法解例用分枝定界法解例5-11.求解相应的线性规划L0max z=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1，x2 02022-12-20用分枝定界法解例用分枝定界法解例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*=3562022-12-20用分枝定界法解例用分枝定界

3、法解例5-12.将L0分解为L1和L2L1：max z=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 4 x1，x2 0L2：max z=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 5 x1，x2 0L1：X*=(4,2.10),Z*=349 L2：X*=(5,1.57),Z*=341 2022-12-20用分枝定界法解例用分枝定界法解例5-13.分解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)

4、;(2)舍弃L42022-12-20用分枝定界法解例用分枝定界法解例5-14.分解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。2022-12-20例例5-1求解过程示意图求解过程示意图L0(4.81，1.82)356L1(4，2.1)349L2(5，1.57)341L3(4，2)340L4(1.42，3)327L5(5.44，1)308L6无可行解2022-12-20练练习题习题max z=2x1+5x2+4x3 x1+x2+x3 12 x1+2x

5、2 15 4x1 +5x3 26 x13 0且取整2022-12-20求解求解练练习题习题首先求解线性规划L0:max z=2x1+5x2+4x3 x1+x2+x3+x 4=12 x1+2x2 +x5=15 4x1 +5x3+x6 =26 x16 02022-12-20求解求解练练习题习题2022-12-20求解求解练练习题习题2022-12-20求解求解练练习题习题2022-12-20求解求解练练习题习题线性规划 L1的最终单纯形表 cj2 5 4 0 0 0 0CBXBx1 x2 x3 x4 x5 x6 x7 b4500 x3x2x6x51 0 1 1 0 0 -10 1 0 0 0 0

6、1-1 0 0 -5 0 1 51 0 0 0 1 0 -2 5 7 1 1 -2 0 0 -4 0 0 -1L1有整数最优解 X*=（0，7，5），Z*=55线性规划 L2无可行解所以原整数规划的最优解为 X*=（0，7，5）最优值为 Z*=552022-12-20求解求解练练习题习题L0（0，15/2，9/2）111/2 L1（0，7，5）55 L2 无可行解2022-12-20割平面法割平面法1.割平面法的基本思路2.例3.练习题2022-12-20割平面法的基本思路割平面法的基本思路同分枝定界法一样，割平面法也是一种利用连续模同分枝定界法一样，割平面法也是一种利用连续模型求解非连续问题

7、的常用方法。割平面法的基本思型求解非连续问题的常用方法。割平面法的基本思路是：当得到的解不满足取整约束时，就设法在问路是：当得到的解不满足取整约束时，就设法在问题上增加一个约束条件，把包含这个非整数解的一题上增加一个约束条件，把包含这个非整数解的一部分可行域从原来的可行域中割除，但不割掉任何部分可行域从原来的可行域中割除，但不割掉任何一个整数可行解。这个新增加的约束条件就称为割一个整数可行解。这个新增加的约束条件就称为割平面。平面。2022-12-20例例max z=x1+x2 -x1+x2 1 3x1+x2 4 x1，x2 0且取整2022-12-20用用割平面法割平面法解例解例1.求解相应

8、的线性规划L0max z=x1+x2 -x1+x2 1 3x1+x2 4 x1，x2 0 2022-12-20用用割平面法割平面法解例解例 表 1（线 性 规 划 最 终 单 纯 形 表）cj1 1 0 0CBXBx1 x2 x3 x4 b11x2x10 1 3/4 1/41 0 -1/4 1/4 7/4 3/4 0 0 -1/2 -1/2 Z=5/2非整数解，为建立割平面，首先考虑非整数解中余数最大非整数解，为建立割平面，首先考虑非整数解中余数最大的基变量，此例中的基变量，此例中x1、x2的余数均为的余数均为3/4，不妨选取，不妨选取x2：x2+3/4 x3+1/4 x4=7/4 2022-

9、12-20用用割平面法割平面法解例解例 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为割平面可使可行域减少一个包括为割平面可

10、使可行域减少一个包括A点在内的三角形点在内的三角形。2022-12-20 x2 A 1 0 1 x1用割平面法解例 2022-12-20用用割平面法割平面法解例解例 表2（加 入 割 平 面 的 单 纯 形 表）cj1 1 0 0 0CBXBx1 x2 x3 x4 x5 b110 x2x1x50 1 3/4 1/4 01 0 -1/4 1/4 00 1 0 0 17/43/4 1 基 变 量 系 数 向 量 单 位 化 表3（最 终 单 纯 形 表）cj1 1 0 0 0CBXBx1 x2 x3 x4 x5 b110 x2x1x30 1 0 0 11 0 0 1/3 -1/30 0 1 1/3

11、 -4/3 1 1 1 0 0 0 -1/3 -2/3 Z =22022-12-20练练习题习题max z=2x1+5x2+4x3 x1+x2+x3 12 x1+2x2 15 4x1 +5x3 26 x13 0且取整2022-12-20求解练习题线性规划 L0的最终单纯形表 cj 2 5 4 0 0 0CBXB x1 x2 x3 x4 x5 x6b450 x3x2x61/2 0 1 1 -1/2 01/2 1 0 0 1/2 03/2 0 0 -5 5/2 1 9/215/2 7/2 -5/2 0 0 -4 -1/2 02022-12-20求解求解练练习题习题选取x2：1/2 x1+x2+1/

12、2 x5=15/2 1/2 x1+1/2 x5=1/2+（7-x2）于是有割平面：1/2 x1+1/2 x5 1/2或 x2 72022-12-20求解练习题 cj 2 5 4 0 0 0 0CBXB x1 x2 x3 x4 x5 x6 x7b4500 x3x2x6x71/2 0 1 1 -1/2 0 01/2 1 0 0 1/2 0 03/2 0 0 -5 5/2 1 0 0 1 0 0 0 0 1 9/215/2 7/2 7 基 变 量 系 数 向 量 单 位 化 cj 2 5 4 0 0 0 0CBXB x1 x2 x3 x4 x5 x6 x7b4500 x3x2x6x71/2 0 1

13、1 -1/2 0 01/2 1 0 0 1/2 0 03/2 0 0 -5 5/2 1 0-1/2 0 0 0 -1/2 0 1 9/215/2 7/2-1/2 -5/2 0 0 -4 -1/2 0 02022-12-20求解练习题 cj2 5 4 0 0 0 0CBXBx1 x2 x3 x4 x5 x6 x7 b4500 x3x2x6x51 0 1 1 0 0 -10 1 0 0 0 0 1-1 0 0 -5 0 1 51 0 0 0 1 0 -2 5 7 1 1 -2 0 0 -4 0 0 -1已 得 整 数 最 优 解 X*=（0，7，5），Z*=5 5所 以 原 整 数 规 划 的 最

14、 优 解 为 X*=（0，7，5）最 优 值 为 Z*=552022-12-200-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-52022-12-20第第69页例页例5-3 某公司拟在东、西、南三个区建立销售门市部，拟议中有7个场点A17可供选择。东区的三个点A13 最多选两个，西区的两个点A45 最少选一个，南区的两个点A67 最少选一个。如果建设 Ai 点，需要投资 bi 元，年可获利 ci 元，

15、公司可筹集到的投资总额为B元，问应如何决策才能使年利潤最大。2022-12-20例例5-3 令xi=0 或 1，其中：xi=0 表示第I个点未被选取 xi=1表示第I个点被选取其数学模型为：x1+x2+x3 2 x4+x5 1 x6+x7 1 iiixcMaxz71 Bxbiii712022-12-20引例引例2 两种运输方式的限制条件分别为：6x1+4x2 30 7x1+3x2 40互斥的约束统一于一个模型中：6x1+4x2 30+Mx3 7x1+3x2 40+M(1-x3)其中x3 为0-1变量。2022-12-20隐枚举法的基本步骤隐枚举法的基本步骤 1.目标函数极小化；2.目标函数系数

16、非负化，如果xj 的系数为负数，可令 xj=1-xj；3.决策变量按其目标函数系数的大小排列；4.令所有变量为“0”，检查该解的可行性，如果可行此解即为最优解，如果不可行进入下一步；5.按变量的顺序依次令各变量分别取“0”或“1”，根据分枝定界的原理进行剪枝，直至结束。2022-12-20第第70页例页例5-4Max 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或12022-12-20例例5-4第二步：令x1=1-x1，x3=1-x3Min w=

17、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。2022-12-20max 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+3

18、x1 2 3x2+2x3-x5+x4+5x1 4 x1 5=0或1第第71页例页例5-52022-12-20例例5-5 w=-8 x2=1 2 w=-10 1 x2=0 w=-6 3 2022-12-20例5-5 w=-4 4 (可行解)w=-8 x3=1 x2=1 2 w=-10 x3=0 w=-3 1 5 x2=0 w=-6 32022-12-20例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 132022-12-20指派问题指派

19、问题 1.指派问题的内涵2.指派问题的数学模型3.指派问题的求解4.指派问题的扩展2022-12-20指派问题的内涵指派问题的内涵 有有m 项工作，恰好有项工作，恰好有m 个人来完成，一个人只完个人来完成，一个人只完成一项工作，一项工作只由一个人来完成，由于个人的专成一项工作，一项工作只由一个人来完成，由于个人的专长不同，完成任务的效率也就不同，于是产生了应指派哪长不同，完成任务的效率也就不同，于是产生了应指派哪个人去完成哪项任务，才能使完成个人去完成哪项任务，才能使完成m 项任务的总效率最项任务的总效率最高的问题，此类问题称为指派问题或分派问题。指派问题高的问题，此类问题称为指派问题或分派问

20、题。指派问题同运输问题一样，是具有一定模型特征一类问题的总称，同运输问题一样，是具有一定模型特征一类问题的总称，如如m 项加工任务如何在项加工任务如何在m 台机床上分配；台机床上分配；m 条航线如条航线如何指定何指定m 艘船去航行等等。指派问题是运输问题的特例，艘船去航行等等。指派问题是运输问题的特例，也是也是0-1规划问题的特例。这一点可由指派问题的数学模规划问题的特例。这一点可由指派问题的数学模型体现出来。型体现出来。2022-12-20指派问题的数学模型指派问题的数学模型ijmimjijxcw 11min,11njijxmi,2,1mjxmiij,2,1,1110 或ijx2022-12

21、-20 指派问题的求解匈牙利法2.匈牙利法的基本步骤(1)第73页例5-6(2)第74页例5-7(3)基本步骤总结1.匈牙利法的基本思想：效率矩阵的任一行（或列）减去（或加上）任一常数对原指派问题的最优解不会发生影响。例如，效率矩阵第一行的各元素均减去 k，那么指派问题的目标函数将变为：ijmimjijjmjjbxcxkcz21111)(kzxkxczmjjmimjijijb11112022-12-20指派问题的扩展指派问题的扩展 1.人员与工作不匹配：引入假想的工作或人员 由于假想的工作或人员代表的是剩余的工作或人员，所以其对应的效率矩阵元素全都为零。例例2.目标函数求极大值：效率矩阵的每一

22、元素乘“-1”，并进一步使其非负化。第第73页例页例5-62022-12-20第73页例5-6 W1W2W3W4M110 9 8 7M2 3 4 5 6M3 2 1 1 2M4 4 3 5 62022-12-20例5-6W1W2W3W4M1 3 2 1(0)M2(0)1 2 3M3 1 0(0)1M4 1(0)2 32022-12-20第74页例5-7 W1W2W3W4M110 9 7 8M2 5 8 7 7M3 5 4 6 5M4 2 3 4 52022-12-20例5-7W1W2W3W4M1 3 2 0 0M2 0 3 2 1M3 1 0 2 0M4 0 1 2 22022-12-20例5

23、-7W1W2W3W4M1 3 2 0 0M2(0)3 2 1M3 1 0 2 0M40 1 2 22022-12-20例5-7W1W2W3W4M1 3 2(0)0M2(0)3 2 1M3 1(0)20M40 1 2 22022-12-20例5-7W1W2W3W4M1 3 2(0)0M2(0)3 2 1 M3 1(0)20M40 1 2 2 2022-12-20例5-7W1W2W3W4M1 3 2 0 0M2-1 2 1 0M3 1 0 2 0M4-1 0 1 12022-12-20例5-7W1W2W3W4M1 4 2 0 0M2 0 2 1 0M3 2 0 2 0M4 0 0 1 12022-

24、12-20例5-7W1W2W3W4M1 4 2(0)0M2(0)2 10M3 20 2(0)M40(0)1 12022-12-20基本步骤总结 1.每行减去一个最小元素；2.每列减去一个最小元素；经此两步，效率矩阵每行、列都至少有一个“0”。3.每行、列若只有一个“0”元素，打上“（）”，同时划去与其同列、行的其它零元素，先前已被划去的零元素不计算在内，如果出现零元素的闭合回路，则任选一个零元素打上“（）”，同时划掉与其同行和同列的零元素。经过第三步可能出现两种结果：(1)每行均有打“()”的零元素,此时已得最优解;(2)并非每行均有打“()”的零元素，进入第四步。4.给没有“(0)”的行做标

25、记“”；5.在做“”标记的行上对所有“0”所在的列做标记“”；6.覆盖掉没有“”标记行上的所有元素和有“”标记列上的所有元素。经过此步矩阵中的所有“0”均被覆盖掉了，只留下了部分非零元素。7.每一非零元素减去它们中的最小值，并给同时处在被覆盖掉行和被覆盖掉列的元素加上这一最小值。8.重复37直至得到最优解。2022-12-20例 12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 102022-12-20例例 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 2022-12-20例 5 (0

26、)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 2022-12-20例 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 2022-12-20例 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 2022-12-20第73页例5-6 10 9 8 7 3 4 5 6 2 1 1 2 4 3 5 62022-12-20例5-6-10 -9 -8 -7 -3 -4 -5 -6 -2 -1 -1 -2 -4 -3 -5 -62022-12-20例5-6 0 1 2 3 3 2 1 0 0 1 1 0 2 3 1 02022-12-20例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