运筹学06整数规划ppt课件.ppt

《运筹学06整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章整数规划与分派问题整数线性规划IntegerLinearProgramming1§1整数规划的特点及作用一、问题的提出2例1工作分配问题甲乙丙丁译成英文21097译成日文154148译成德文13141611译成俄文415139甲乙丙丁四人翻译把专利说明书译成四种文字，所需翻译时间如下表。怎样分配最省时？3工作分配问题数学模型4例2急救中心选址问题某市有八个区，救护车从一个区至另一个区的车程用时如下表所示（单位：分钟）。若要求救护车在8分钟内必须赶到，应建几个救护中心？建于何处？23456781891113148152101213111714377812104

2、8710958141661077121127212334564345653456634568717868急救中心设在k区，救护车在8分钟内能赶到的区：5急救中心选址问题数学模型6二、整数规划模型常见类型：1、一般整数规划2、0-1整数规划73、混合整数规划8三、带逻辑变量的数学规划问题1、m个约束只有k个起作用92、右端项有多种选择103、带条件约束或分段约束114、价格系数分段定价有先期投入12四、与线性规划的关系整数规划松弛问题ILP的可行解包含在LP的可行解中ILP的最优值小于或等于LP的最优值131415例1工作分配问题甲乙丙丁译成英文21097译成日文1

3、54148译成德文13141611译成俄文415139甲乙丙丁四人翻译把专利说明书译成四种文字，所需翻译时间如下表。怎样分配最省时？§2分配(分派)问题16工作分配问题员工1员工2。。。员工m工作1a11a12A1m工作2A21a22A2m。。。工作mam1am2ammm个人完成m项任务，每项任务由一人完成，每人分担一项任务。怎样分派才能效率最高，或用时最少？工作效率（或工时）矩阵17工作分配问题数学模型18匈牙利法（Konig)定理1设原效率矩阵A=[aij]每行减去常数ui，每列减去常数vj新的效率矩阵B=[bij],则　A与Ｂ的最优解相同。定理2若A的元素可

4、分成0与非0，则盖住0的最小直线数=不同行、不同列的0的最大个数。19算法原理设A的元素≥0，且有一组不同行不同列的0，则分配问题有一组最优解。令：与0对应的xij=1，其余xij=0，就是一个最优解。此时：z=0达到最优。087511010423500110520匈牙利法（Konig)21097154148131416114151392411408751101042350011951、先对行造0。每行最小值——行位势21匈牙利法（Konig)08751101042350011952、再对列造0每列最小值——列位势005008251105423000114522匈

5、牙利法（Konig)3、加括号，画直线；(0)82511(0)5423(0)00114523匈牙利法（Konig)4、再用位势法造0(0)82511(0)5423(0)001145未划掉数字中的最小值22202080311032450001123-2-20024匈牙利法（Konig)5、返回308(0)311(0)32450(0)(0)112325匈牙利法（Konig)最后，每行每列都有0，得到最优解。08(0)311(0)32450(0)(0)1123甲——俄语乙——日语丙——英语丁——德语英日德俄甲乙丙丁z=4+4+9+11=28(小时)26§3分支定界法27

6、分支的方法：28对0-1整数规划分支2930定界的方法（剪枝）当前得到的最好整数解的目标函数值分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解31选一分支写出并求解放松问题，同时从分支集中删除该分支判定是否为整数解初始分支为可行解集，初始界为无穷大判定是否分支集空是停止当前最好解为优解是否32算例33343536注释求解混合整数规划问题，只对整数变量分支，对非整数变量不分支

7、。37§4割平面法38由放松问题的可行域向整数规划的可行域逼近方法—利用超平面切除要求整数解保留放松问题最优值增加§4割平面法39