第3章整数规划课件

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