管理运筹学 第五章 整数规划

1、5.1 整数规划实例及一般模型整数规划实例及一般模型5.2 分支定界法分支定界法5.3 0-1整数规划整数规划5.4 指派问题指派问题例例5.1 某公司拟用集装箱托运甲、乙两种货物，这两种货某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下物每件的体积、重量、可获利润以及托运所受限制如下表所示。表所示。 货物每件体积/立方英尺每件重量/百千克每件利润/百元甲19542乙273403托运限制1365140 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？l解解 设x1、x2分别为甲、乙两种货物托运的件数，建立模型为整数2121121212

2、1,0,41404041365273195. .32maxxxxxxxxxxtsxxz例例5.2 某服务部门各时段（每某服务部门各时段（每2小时为一时段）需要的服务小时为一时段）需要的服务员人数如下表。按规定，服务员连续工作员人数如下表。按规定，服务员连续工作8个小时（个小时（4个个时段），问如何安排服务员，使服务员总数最少。时段），问如何安排服务员，使服务员总数最少。时段时段12345678服务员最少所需人数服务员最少所需人数10891113853且为整数0,35813119810min5215545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxx

3、xxxzl例5.3 某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂，已知在A2地建厂的固定成本为175千元，在A3地建厂的固定成本为300千元，在A4地建厂的固定成本为375千元，在A5地建厂的固定成本为500千元，另外，在A1的产量，A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价（每千箱运费）如下表5-3所示。问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小？如果A2和A3两地必须有且只有一个建厂，怎么办？1、整数规划数学模型的一般形式、整数规划数学模型的

4、一般形式整数规划问题的松弛问题整数规划问题的松弛问题 )n, 2 , 1j (0 x)m, 2 , 1i (b),(xa.stxczmax(min)jn1jijijn1jjjxj部分或全部取整数部分或全部取整数整数规划的类型整数规划的类型l纯整数规划：变量纯整数规划：变量全部全部是整数是整数l混合整数规划：变量部分整数，部分非整数混合整数规划：变量部分整数，部分非整数l0-1型整数规划：变量型整数规划：变量= 0或或110 整数规划对应松弛问题最优解为：x1=2.44, x2=3.26,目标函数值为14.66。 整数规划的最优解为：x1=4, x2=2,目标函数值为14。12341232x1+

5、3x2 =14.66x1 x2 2x1+3x2 =142x1+3x2 =6整数规划解的特点（整数规划解的特点（1、整数规划的可行解集合是其松弛问题可行解集合的子集 ；整数规划最优解的目标函数值不会优于松弛问题最优解的目标函数值。2、整数规划的最优解不一定是对松弛问题最优解变量的简单取整。l分支：若松弛问题最优解中存在变量xi=bi不满足整数约束，记bi为不超过bi的最大整数，则构造两个新 的约束xi bi ，和xi bi+1。将它们分别并入到原松弛问题中，形成原松弛问题的两个分支（后继问题）。当分支的最优解也不满足整数约束时，可以继续构造它们的分支。l定界：在分支的过程中，若某个后继问题恰好获

6、得了整数规划的一个可行解，则这一可行解的目标函数值可看成一个“界限”，作为处理其他分支的依据。l例5.4 求解如下整数规划：首先求解其松弛规划：0,18241432. .23max21212121xxxxxxtsxxz最优解为X=(3.25,2.5)，z=14.75因为x1=3.25，所以将其分为x1=4两个分支31x41x因为x2=8/3，所以将其分为x2=3两个分支32x22x所以X*=(4,1)，Z*=14l例5.5 广州某食品公司计划在市区的东、西、南、北四区建立销售门市部，目前有10个位置可供选择，考虑到各地区居民的消费水平及居民居住密集程度，规定：l在东区由三个点中最多选择两个；l

7、在西区由两个点中至少选择一个；l在南区由两个点中至少选择一个；l在北区由三个点中至少选择两个。投资总额不能超过720万元，问应该选择哪几个销售点，可使年利润为最大？ 109876 5432161584825302022504036maxxxxxxxxxxxz.10,.,3 , 2 , 110021127201801501201001098765432110321ixxxxxxxxxxxxxxxxii变量，为且s.t.在东区由三个点中最多选择两个在西区由两个点中至少选择一个在南区由两个点中至少选择一个在北区由三个点中至少选择两个l例例5.6 有三种资源被用于生产三种产品，资源量、产品单件可变费用

8、及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。解解 为提高搜索效率，减少运算量，先按照目标函数中各变量系数的大小顺序重新排列各变量。 对于求极大值问题，按照从小到大对于求极大值问题，按照从小到大排为x3,x2,x1。（注意：对于求极小值问题，应从大到小排序求极小值问题，应从大到小排序）(x3,x2,x1)z值约束条件过滤条件abcd0，0，00，0，10，1，00，1，11，0，01，0，11，1，01，1，100z22z1不检验3不检验-1不检验1不检验0不检验2不检验l例例5.9 有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗

9、的时间(我们称之为消耗系数)如表5-6所示，问应如何分配任务，才能使总的消耗时间最少？l步骤1：首先让每一行、每一列减去该行（列）的最小数，保证每一行、每一列都有零。l步骤2：试指派。l将只有一个0元素的行（列）的0最先画圈，变为0（称为独立零元素独立零元素）。然后将其所在列（行）其它的0划掉。然后继续寻找，直到没有0可划为止。l步骤3：如果独立零元素的个数等于n计算停止，按照独立零元素对应的位置进行指派即可。否则进入下一步进行调整。l步骤4：调整：l任意选择一个没有独立零元素的行，将该行所有元素减去该行除外的最小数(m)；l然后该行的将会变为，为了将负数删除，我们将该行所有元素加上m；l则原

10、来的所在的列中的0会被变为正数。为了使0所在行能够找到新的0，须让该行所有元素再减去除0外的最小数。如果此时没有出现负数，调整结束；否则继续使负数所在列加上一个常数，继续循环。l直到系数矩阵中没有负数，而且整个消耗系数矩阵的所有元素总和已经变小；此时调整结束，重新回到step2。15172124192322182617161919212317C每行减该行最小数每行减该行最小数02691540101032460每列减该列最小数每列减该列最小数0169144010003236001691440100032360此时独立零元素有3个，第四行没有，故转入步骤4。01691440100032360l第四

11、行没有独立零元素，所第四行没有独立零元素，所以让该行减以让该行减2l第四行第四列的第四行第四列的0变为变为-2，所以让第四列再加所以让第四列再加2l第四列的独立零元素被破坏，第四列的独立零元素被破坏，所以让第二行再减所以让第二行再减1 -2+2 -1016110332100050140016110332100050140此时独立零元素还是只有3个，第二行没有，故转入步骤4。l第二行没有独立零元素，所第二行没有独立零元素，所以让该行减以让该行减2l第二行第一列的第二行第一列的0变为变为-2，所以让第一列再加所以让第一列再加2l第一列的独立零元素被破坏，第一列的独立零元素被破坏，所以让第一行再减所

12、以让第一行再减1 -2+2 -1016110332100050140105100110120052140105100110120052140此时找到了4个独立零元素，所以最优方案为：01001000*00100001X6917161917*z 65325746798596811练习题：练习题： 1723211919161726182223192421181519*Z 70*Z 非标准形式指派问题的处理非标准形式指派问题的处理1、最大化指派问题：目标函数求、最大化指派问题：目标函数求max nn2n1nn22221n11211cccccccccC nn2n1nn22221n11211cmcmcm

13、cmcmcmcmcmcmB最大元素：最大元素：m将原系数矩阵将原系数矩阵C转换为转换为B有5个工人，要指派去做5项工作，每人做各项工作的能力见下表。应如何指派，才能使总的得分最大？ J1J2J3J4J5S1S2S3S4S51551712511012931313080853912106812工人工作12989128130127651301108131151203515C15151515151515151515151515151515151515151515151515C1298912813012765130110813115120351536763721538910215145724103151

14、21000343050131678013123502831512100034205013067801212350183151290-3 +3-10041080162975011123200831212801000001000001000001000001*X64*z2、人数、人数事数事数人数人数事数：添加虚拟事数：添加虚拟“事事”， c = 03、一个人可以做几件事、一个人可以做几件事将一人化为相同的多个人来接受指派，这多个将一人化为相同的多个人来接受指派，这多个人做同一件事的费用相同人做同一件事的费用相同4、某事不能由某人来做、某事不能由某人来做将相应的费用系数取无穷大将相应的费用系数取无穷大Ml例5.12 某大型工程共由5个项目A、B、C、D、E组成，现有三个公司甲、乙、丙分别来投标，各自给出的报价如下表所示。这里甲乙丙三家公司实力均比较雄厚，可以同时进行两个项目的施工，请给出最优施工分配方案。ABCDE甲151791218乙141810