运筹学06整数规划.ppt

第四章第四章 整数规划与分派问题整数规划与分派问题整数线性规划整数线性规划Integer Linear ProgrammingInteger Linear Programming11 整数规划的特点及作用整数规划的特点及作用一、问题的提出一、问题的提出2 例例1 工作分配问题工作分配问题甲甲乙乙丙丙丁丁译成英文译成英文21097译成日文译成日文154148译成德文译成德文13141611译成俄文译成俄文415139甲乙丙丁四人翻译把专利说明书译成四种文字，所需甲乙丙丁四人翻译把专利说明书译成四种文字，所需翻译时间如下表。怎样分配最省时？翻译时间如下表。怎样分配最省时？3工作分配问题数学模型工作分配问题数学模型4 例例2 急救中心选址问题急救中心选址问题某市有八个区，救护车从一个区至另一个区的车程用时某市有八个区，救护车从一个区至另一个区的车程用时如下表所示（单位：分钟）。若要求救护车在如下表所示（单位：分钟）。若要求救护车在8分钟内必分钟内必须赶到，应建几个救护中心？建于何处？须赶到，应建几个救护中心？建于何处？234567818911131481521012131117143778121048710958141661077121127212334564345653456634568717868急救中心设在急救中心设在k 区，救护车在区，救护车在8分钟内能赶到的区：分钟内能赶到的区：5 急救中心选址问题数学模型急救中心选址问题数学模型6二、整数规划模型常见类型：二、整数规划模型常见类型：1、一般整数规划、一般整数规划2、0-1 整数规划整数规划73、混合整数规划混合整数规划8 三、带逻辑变量的数学规划问题三、带逻辑变量的数学规划问题 1、m个约束只有个约束只有k个起作用个起作用9 2、右端项有多种选择、右端项有多种选择10 3、带条件约束或分段约束、带条件约束或分段约束11 4、价格系数分段定价、价格系数分段定价有先期投入有先期投入12四、四、与线性规划的关系与线性规划的关系整数规划整数规划 松弛问题松弛问题ILP的可行解包含在的可行解包含在LP的可行解中的可行解中ILP的最优值小于或等于的最优值小于或等于LP的最优值的最优值131415 例例1 工作分配问题工作分配问题甲甲乙乙丙丙丁丁译成英文译成英文21097译成日文译成日文154148译成德文译成德文13141611译成俄文译成俄文415139甲乙丙丁四人翻译把专利说明书译成四种文字，所需甲乙丙丁四人翻译把专利说明书译成四种文字，所需翻译时间如下表。怎样分配最省时？翻译时间如下表。怎样分配最省时？2 分配分配(分派分派)问题问题16 工作分配问题工作分配问题员工员工1员工员工2。员工员工m工作工作1a11a12A1m工作工作2A21a22A2m。工作工作mam1am2amm m 个人完成个人完成 m 项任务，每项任务由一人完成，项任务，每项任务由一人完成，每人分担一项任务。怎样分派才能效率最高，或用每人分担一项任务。怎样分派才能效率最高，或用时最少时最少？工作效率（或工时）矩阵工作效率（或工时）矩阵17工作分配问题数学模型工作分配问题数学模型18 匈牙利法（匈牙利法（Konig)定理定理1 1 设原效率矩阵设原效率矩阵 A=a ijij 每行减去常数每行减去常数ui，每列减去常数，每列减去常数vj 新的效率矩阵新的效率矩阵 B=b bijij ,则则A A与的最优解相同。与的最优解相同。定理定理2 2 若若A A的元素可分成的元素可分成 0 0 与非与非0 0，则，则 盖住盖住0 0的最小直线数的最小直线数 =不同行、不同列的不同行、不同列的0 0的最大个数。的最大个数。19 算法原理算法原理 设设A A的元素的元素0 0，且有一组不同行不同列的，且有一组不同行不同列的0 0，则分配问题有一组最优解。则分配问题有一组最优解。令：与令：与0 0对应的对应的xij=1=1，其余，其余xij=0=0，就是一个最优解。就是一个最优解。此时：此时：z=0=0 达到最优。达到最优。087511010423500110520 匈牙利法（匈牙利法（Konig)21097154148131416114151392411408751101042350011951 1、先对行造、先对行造0 0。每行最小值每行最小值 行位势行位势21 匈牙利法（匈牙利法（Konig)08751101042350011952 2、再对列造、再对列造0 0每列最小值每列最小值 列位势列位势005008251105423000114522 匈牙利法（匈牙利法（Konig)3 3、加括号，画直线；、加括号，画直线；(0)82511(0)5423(0)00114523 匈牙利法（匈牙利法（Konig)4 4、再用位势法造、再用位势法造0 0(0)82511(0)5423(0)001145未划掉数字中的最小值未划掉数字中的最小值22202080311032450001123-2-20024 匈牙利法（匈牙利法（Konig)5 5、返回、返回3 308(0)311(0)32450(0)(0)112325 匈牙利法（匈牙利法（Konig)最后，每行每列都有最后，每行每列都有0 0，得到最优解。，得到最优解。08(0)311(0)32450(0)(0)1123 甲甲 俄语俄语 乙乙 日语日语 丙丙 英语英语 丁丁 德语德语英英日日德德俄俄甲甲乙乙丙丙丁丁 z=4+4+9+11z=4+4+9+11 =28(=28(小时小时)263 分支定界法分支定界法27分支的方法：分支的方法：28n对对0-1整数规划分支整数规划分支2930定界的方法（剪枝）定界的方法（剪枝）n当前得到的最好整数解的目标函数值当前得到的最好整数解的目标函数值n分支后计算放松的线性规划的最优解分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好整数解且目标值小于原有最好解的值则替代原有最好解解整数解且目标值大于原有最好解的值则整数解且目标值大于原有最好解的值则 删除该分支删除该分支其中无最优解其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解分支其中无最优解31选一分支写出并求解选一分支写出并求解放松问题，同时从分放松问题，同时从分支集中删除该分支支集中删除该分支判判定是否定是否为整数为整数解解初始分支为可行解初始分支为可行解集，初始界为无穷大集，初始界为无穷大判判定是否定是否分支集分支集空空是是停止停止当前最好解当前最好解为优解为优解是是否否32算算 例例33343536注注 释释n求解混合整数规划问题，只对整数变量分支，求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。对非整数变量不分支。374 割平面法割平面法38n由放松问题的可行域由放松问题的可行域向整数规划的可行域向整数规划的可行域逼近逼近n方法方法利利用超平面切用超平面切除除n要求要求 整数解保留整数解保留 放松问题最优值增放松问题最优值增加加4 割平面法割平面法39