第3章整数规划.ppt

,第三章整数规划和分配问题,整数规划的数学模型及分类解纯整数规划的分枝定界法解分配问题的匈牙利法,教学目的与要求:能建立整数规划的数学模型,会用匈牙利法解分配问题.重点与难点:重点是建模和解分配问题,难点是在分枝定界法中如何分枝及定界.教学方法:以课堂讲授为主,配合课件和软件.思考题,讨论题,作业:教材第四章习题.参考资料:见前言.学时分配:4学时.,第三章整数规划和分配问题(Integerprogrammingandassignmentproblem),第一节整数规划问题的提出,线性规划的决策变量的取值是非负实数,但是有些实际问题的线性规划模型中,决策变量取值只能是非负整数,甚至只能取0,1两个数,这类的线性规划模型称为整数线性规划,简称整数规划.,例1某厂拟托运甲,乙两种货物,有关数据如下表.问两种货物各托运多少箱,才能获得最大利润.,建立数学模型:,这个模型称为纯整数规划,有时模型中的决策变量一部分取整数,另一部分取实数,称为混合整数规划.,例2投资模型(如物流配送网点的选择,工厂布局,基本设备的配置,科研课题的选择等),这个模型称为0-1整数规划.,在投资模型中,如果只有一种资源限制,则模型可简化为:,该模型称为”背包问题”(Knapsackproblem),整数规划的解法分析,整数规划与线性规划的区别在于对决策变量有无整数限制,因此有人认为,先不考虑整数限制求解线性规划,对求得的非整数解四舍五入可求得整数规划的最优解.但是,这个方法是不行的.从例2中求得,第二节整数规划的解法,整数规划与线性规划解的性质:,如果LP的最优值在其可行域T的某个顶点上达到,则相应的IP最优值,在T中去掉不含整数点的区域后的T*中的整数点上达到.,对于求最大化(最小化)问题,LP最优解对应的目标函数值,是相应的IP最优解对应的目标函数值的上界(下界).,最早的整数规划论文是在1954年发表的,1959年美国的R.E.Gomory提出了割平面法(依据性质1),为IP作出了开创性的工作.1960年美国的A.Land,A.G.Doig提出了分枝定界法(依据性质2),该方法概念简单,方法灵活,容易在计算机上运算,成为IP解法的基础.,一.IP的隐枚举法,穷举法:,可以设想,整数规划的可行解集一定是具有确定数目的点阵,然后搜索这些点,比较目标函数值的大小,从而求得最优解.,0-1整数规划的穷举法:检查决策变量取值为0,1两个值的全部组合,这就是穷举法.当变量个数为n时,要检查的数目是但是当n15时,因计算量太大而无法实现.,例1用穷举法解0-1整数规划,最优解为最优值为S=3.,2.分枝定界法:它是一种隐枚举法,用来解纯整数规划及混合整数规划.,分枝定界法的基本思想:对于给定的IP,去掉整数约束得到LP,称为整数规划的松弛问题.求解该LP,如果其最优解不是整数,就将IP分为两个增加了新约束的IP,此时新IP的可行域被分割,从而缩小了原可行域,由整数规划性质2,进行定界,逐渐求出最优解.,例2用分枝定界法求解整数规划,第三节分配问题(指派问题),分配问题的数学模型:,要求每个工人有一项工作,每项工作只有一个工人来作.如何安排使总的效益最好.,分配问题的匈牙利解法(1955年W.W.Kuhn提出的分配问题解法中,使用了匈牙利数学家Konig的两个定理,故称匈牙利解法.,定理1,证明:不失一般性,取B表示在A的i行各元素减去常数k所得的矩阵,这时以B为系数矩阵的目标函数是,这表明当达到最优值时也达到最优值,也就是说,的最优解一定是的最优解.,例3某配送中心有四项配送任务,分配给四辆汽车去完成,每辆汽车完成各项配送任务的时间如下表,问如何分配任务使总的用时最少.,解:取出效率矩阵进行运算.,在B中找出位于不同行,不同列的四个零元素,作法如下:,先从零元素最少的行(列)开始,选取一个零元素将其圈起来,同时将零元素所在行,列的其余零元素划去;,如果恰有四个被圈起来的零元素,处于不同行不同列,则将这些零改为1,其余元素改为0,得到最优分配方案.,最优分配方案是:,最优值(即总用时)是minS=4+4+9+11=28.,注意:对于来说不是最优方案,但对整体来说达到最优,这就是运筹学思想.,定理2若方阵中的一部分元素为零,一部分非零,则覆盖方阵内所有零元素的最小直线数,等于方阵内位于不同行不同列的零元素的最多个数.,根据定理1,2设计出分配问题的一般解法:,第一步:将效率矩阵A的每一行各减去该行的最小元素,再从新矩阵中的各列减去该列的最小元素,得矩阵B;,第二步:从有零元素最少的行(列)开始,圈出零元素后划去同行(列)的其他零元素.若被圈出的零元素恰好布满B的不同行不同列,则将这些零元素改为1,其余元素改为0,得最优分配矩阵.否则转第三步;,第三步:根据定理2作出覆盖零元素的最小直线集:,对没有被圈出零的行打”;,对有的行上所有有零元素的列打;,再对打的列上有被圈出零的行打;,重复,直到得不出新打的行,列为止;,对没有打的行画横虚线;对所有打的列画纵虚线,这就是覆盖所有零元素的最小直线集,转第四步;,第四步:在没有被覆盖的元素中找出最小元素,对没有画直线的行上各元素都减去这个最小元素;对画有直线的列上各元素都加上这个最小元素,这样得到的矩阵如果不同行不同列上都有被圈出的零,则可将其换为1,其余元素换为0,最优分配方案求出,否则转第三步.,例4工厂有五个独立车间,该厂计划生产五种产品,由于产品性质和各车间设备不同,每个车间生产各种产品消耗的资金(万元)不同,如下表.问如何安排生产任务,使总的耗资最少.,解:,最优分配方案:,最优值为,最大化分配问题的解法,构造矩阵,最大化分配问题的数学模型改为求最小化问题的数学模型: