运筹学06整数规划课件

《运筹学06整数规划课件》由会员分享，可在线阅读，更多相关《运筹学06整数规划课件（39页珍藏版）》请在装配图网上搜索。

1、第第1页页第四章第四章 整数规划与分派问题整数规划与分派问题整数线性规划整数线性规划Integer Linear ProgrammingInteger Linear Programming第第2页页1 整数规划的特点及作用整数规划的特点及作用一、问题的提出一、问题的提出第第3页页 例例1 工作分配问题工作分配问题甲甲乙乙丙丙丁丁译成英文译成英文21097译成日文译成日文154148译成德文译成德文13141611译成俄文译成俄文415139甲乙丙丁四人翻译把专利说明书译成四种文字，所需甲乙丙丁四人翻译把专利说明书译成四种文字，所需翻译时间如下表。怎样分配最省时？翻译时间如下表。怎样分配最省时？

2、第第4页页工作分配问题数学模型工作分配问题数学模型第第5页页 例例2 急救中心选址问题急救中心选址问题某市有八个区，救护车从一个区至另一个区的车程用时某市有八个区，救护车从一个区至另一个区的车程用时如下表所示（单位：分钟）。若要求救护车在如下表所示（单位：分钟）。若要求救护车在8分钟内分钟内必须赶到，应建几个救护中心？建于何处？必须赶到，应建几个救护中心？建于何处？234567818911131481521012131117143778121048710958141661077121127212334564345653456634568717868急救中心设在急救中心设在k 区，救护车在区，救

3、护车在8分钟内能赶到的区：分钟内能赶到的区：第第6页页 急救中心选址问题数学模型急救中心选址问题数学模型第第7页页二、整数规划模型常见类型：二、整数规划模型常见类型：1、一般整数规划、一般整数规划2、0-1 整数规划整数规划第第8页页3、 混合整数规划混合整数规划第第9页页 三、带逻辑变量的数学规划问题三、带逻辑变量的数学规划问题 1、m个约束只有个约束只有k个起作用个起作用), 2 , 1(,1mibxanjijij kmyyymiyMbxaminjijij 211), 2 , 1(, 不不起起作作用用约约束束起起作作用用约约束束iiyi10第第10页页rnjjijbbbbxa,2110或或

4、 1,2111 rriiinjjijyyyybxa iiibby约约束束值值约约束束值值01 2、右端项有多种选择、右端项有多种选择第第11页页3),4(, 1, 42121 xxxx则则否否则则则则若若134142122211211 yyMyxMyxMyxMyx2 , 110 iiiyi不不起起作作用用约约束束起起作作用用约约束束 3、带条件约束或分段约束、带条件约束或分段约束第第12页页 0 00,)(jjjjjjjxxxcKxC若若若若 njyMyxyKxczjjjnjjjjj, 2 , 11 , 00min1 增增加加约约束束：nixxyiii,2, 10100 4、价格系数分段定价、

5、价格系数分段定价 njjjxCz1)(min有先期投入有先期投入第第13页页四、四、 与线性规划的关系与线性规划的关系整数规划整数规划 松弛问题松弛问题ILP的可行解包含在的可行解包含在LP的可行解中的可行解中ILP的最优值小于或等于的最优值小于或等于LP的最优值的最优值第第14页页第第15页页第第16页页 例例1 工作分配问题工作分配问题甲甲乙乙丙丙丁丁译成英文译成英文21097译成日文译成日文154148译成德文译成德文13141611译成俄文译成俄文415139甲乙丙丁四人翻译把专利说明书译成四种文字，所需甲乙丙丁四人翻译把专利说明书译成四种文字，所需翻译时间如下表。怎样分配最省时？翻译

6、时间如下表。怎样分配最省时？2 分配分配(分派分派)问题问题第第17页页 工作分配问题工作分配问题员工员工1员工员工2。员工员工m工作工作1a11a12A1m工作工作2A21a22A2m。工作工作mam1am2amm m 个人完成个人完成 m 项任务，每项任务由一人完成，项任务，每项任务由一人完成，每人分担一项任务。怎样分派才能效率最高，或用每人分担一项任务。怎样分派才能效率最高，或用时最少时最少 ？ 工作效率（或工时）矩阵工作效率（或工时）矩阵第第18页页工作分配问题数学模型工作分配问题数学模型第第19页页 匈牙利法（匈牙利法（Konig)定理定理1 1 设原效率矩阵设原效率矩阵 A = =

7、a ijij 每行减去常数每行减去常数ui ，每列减去常数，每列减去常数vj 新的效率矩阵新的效率矩阵 B = =b bij ij , 则则A A与的最优解相同。与的最优解相同。定理定理2 2 若若A A的元素可分成的元素可分成 0 0 与非与非0 0，则，则 盖住盖住0 0的最小直线数的最小直线数 = = 不同行、不同列的不同行、不同列的0 0的最大个数。的最大个数。第第20页页 算法原理算法原理 设设A A的元素的元素00，且有一组不同行不同列的，且有一组不同行不同列的0 0，则分配问题有一组最优解。则分配问题有一组最优解。令：与令：与0 0对应的对应的xij =1=1，其余，其余xij

8、=0=0， 就是一个最优解。就是一个最优解。此时：此时：z = 0 = 0 达到最优。达到最优。0875110104235001105第第21页页 匈牙利法（匈牙利法（Konig)21097154148131416114151392411408751101042350011951 1、先对行造、先对行造0 0。每行最小值每行最小值 行位势行位势第第22页页 匈牙利法（匈牙利法（Konig)08751101042350011952 2、再对列造、再对列造0 0每列最小值每列最小值 列位势列位势0050082511054230001145第第23页页 匈牙利法（匈牙利法（Konig)3 3、加括号

9、，画直线；、加括号，画直线；(0)82511(0)5423(0)001145第第24页页 匈牙利法（匈牙利法（Konig)4 4、再用位势法造、再用位势法造0 0(0)82511(0)5423(0)001145未划掉数字中的最小值未划掉数字中的最小值22202080311032450001123-2-200第第25页页 匈牙利法（匈牙利法（Konig)5 5、返回、返回3 308(0)311(0)32450(0)(0)1123第第26页页 匈牙利法（匈牙利法（Konig) 最后，每行每列都有最后，每行每列都有0 0，得到最优解。，得到最优解。08(0)311(0)32450(0)(0)1123

10、 甲甲 俄语俄语 乙乙 日语日语 丙丙 英语英语 丁丁 德语德语英英日日德德俄俄甲甲乙乙丙丙丁丁 z = 4+4+9+11 z = 4+4+9+11 = 28( = 28(小时小时) )第第27页页NB1IbBcB1N0bB1Zbxrr rrrbxb3 分支定界法分支定界法第第28页页为整数xxbAxtsxc, 0. .min 为整数xxbxbAxtsxcrr, 0. .min 为整数xxbxbAxtsxcrr, 0. .min 分支的方法：分支的方法：第第29页页n对对0-1整数规划分支整数规划分支1 ,0.minxbAxtsxc 1 ,01.minxxbAxtsxcr 1 ,00.minx

11、xbAxtsxcr 第第30页页第第31页页定界的方法（剪枝）定界的方法（剪枝）n当前得到的最好整数解的目标函数值当前得到的最好整数解的目标函数值n分支后计算放松的线性规划的最优解分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好整数解且目标值小于原有最好解的值则替代原有最好解解整数解且目标值大于原有最好解的值则整数解且目标值大于原有最好解的值则 删除该分支删除该分支其中无最优解其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该非整数解且目标值大于等于原有最好解的值则删除

12、该分支其中无最优解分支其中无最优解第第32页页选一分支写出并求解选一分支写出并求解放松问题，同时从分放松问题，同时从分支集中删除该分支支集中删除该分支判判定是否定是否为整数为整数解解初始分支为可行解初始分支为可行解集，初始界为无穷大集，初始界为无穷大判判定是否定是否分支集分支集空空是停止是停止当前最好解当前最好解为优解为优解是是否否第第33页页算算 例例第第34页页第第35页页第第36页页第第37页页注注 释释n求解混合整数规划问题，只对整数变量分支，求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。对非整数变量不分支。第第38页页4 割平面法割平面法第第39页页n由放松问题的可行由放松问题的可行域向整数规划的可域向整数规划的可行域逼近行域逼近n方法方法利用超平面切利用超平面切除除n要求要求 整数解保留整数解保留 放松问题最优值增放松问题最优值增加加4 割平面法割平面法