运筹学课件-第5章-整数规划.ppt

1、第五章第五章 整数规划整数规划整数规划的数学模型整数规划的数学模型分支定界法分支定界法0-10-1型整数规划型整数规划指派问题指派问题例：某公司拟用集装箱托运甲、乙两种货物，这两例：某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所种货物每件的体积、重量、可获利润以及托运所受限制如下表所示。受限制如下表所示。货物货物每件体积每件体积/立方英尺立方英尺每件重量每件重量/百千克百千克每件利润每件利润/百元百元甲甲1951954 42 2乙乙27327340403 3托运限制托运限制13651365140140甲种货物至多托运甲种货物至多托运4 4件，问两种货物各托运

2、多少件，件，问两种货物各托运多少件，可使获得利润最大？可使获得利润最大？整数规划举例整数规划举例解：设解：设x x1 1、x x2 2分别为甲、乙两种货物托运的件数，分别为甲、乙两种货物托运的件数，0,41404041365273195.32max211212121xxxxxxxtsxxz为整数21,xx 整数规划的数学模型整数规划的数学模型1、整数规划数学模型的一般形式、整数规划数学模型的一般形式整数规划问题的松弛问题整数规划问题的松弛问题 )n,2,1j(0 x)m,2,1i(b),(xa.stxczmax(min)jn1jijijn1jjjxj部分或全部取整数部分或全部取整数2、整数规划

3、的类型：、整数规划的类型：纯整数规划：纯整数规划：xj全部是整数全部是整数混合整数规划：混合整数规划：xj部分是整数部分是整数0-1型整数规划：型整数规划：xj=0或或13、整数规划解的特点、整数规划解的特点整数规划的可行域：整数规划的可行域：R 最优目标函数值最优目标函数值Z*松弛问题的可行域：松弛问题的可行域：R 最优目标函数值最优目标函数值Z*则则 ,Z*优于优于Z*RR 分支：若松弛问题最优解中存在变量分支：若松弛问题最优解中存在变量xi=bixi=bi不满不满足整数约束，记足整数约束，记bibi为不超过为不超过bibi的最大整数，的最大整数，则构造两个新则构造两个新 的约束的约束xi

4、 bi xi bi，和，和xi xi bi+1bi+1。将它们分别并入到原松弛问题中，形成。将它们分别并入到原松弛问题中，形成原松弛问题的两个分支（后继问题）。当分支的最原松弛问题的两个分支（后继问题）。当分支的最优解也不满足整数约束时，可以继续构造它们的分优解也不满足整数约束时，可以继续构造它们的分支。支。定界：在分支的过程中，若某个后继问题恰好获得定界：在分支的过程中，若某个后继问题恰好获得了整数规划的一个可行解，则这一可行解的目标函了整数规划的一个可行解，则这一可行解的目标函数值可看成一个数值可看成一个“界限界限”，作为处理其他分支的依，作为处理其他分支的依据。据。分支定界法分支定界法

5、例：求解如下整数规划：例：求解如下整数规划：首先求解其松弛问题：首先求解其松弛问题：0,18241432.23max21212121xxxxxxtsxxz最优解为最优解为X=(3.25,2.5)X=(3.25,2.5)，z=14.75z=14.75取整数且2121212121,0,18241432.23maxxxxxxxxxtsxxz因为x1=3.25，所以将其分为x13和x14两个分支31x41x因为ZBZC,且x2=8/3，所以将其分为x2 2和x2 3两个分支32x22x因为ZDZC,所以不再分支因为ZEZC,所以不再分支所以X*=(4,1)，Z*=14分支定界法要说明的几点：分支定界法

6、要说明的几点：1、对于纯整数规划和混合整数规划都适用、对于纯整数规划和混合整数规划都适用2、缺点：分支越多，要求解的子问题就越多、缺点：分支越多，要求解的子问题就越多，且子问题的约束条件也不断增多，计算量也，且子问题的约束条件也不断增多，计算量也随之增多，对于多变量的大型整数规划问题，随之增多，对于多变量的大型整数规划问题，求解过程非常繁琐和费时。求解过程非常繁琐和费时。0-1型整数规划型整数规划 )n,2,1j(0 x)m,2,1i(b),(xa.stxczmax(min)jn1jijijn1jjjxj=0，11、01型整数规划数学模型型整数规划数学模型例例:广州某食品公司计划在市区的东、西

7、、南、北四广州某食品公司计划在市区的东、西、南、北四区建立销售门市部，目前有区建立销售门市部，目前有1010个位置可供选择，考个位置可供选择，考虑到各地区居民的消费水平及居民居住密集程度，虑到各地区居民的消费水平及居民居住密集程度，规定：规定：在东区由三个点中最多选择两个；在东区由三个点中最多选择两个；在西区由两个点中至少选择一个；在西区由两个点中至少选择一个；在南区由两个点中至少选择一个；在南区由两个点中至少选择一个；在北区由三个点中至少选择两个。在北区由三个点中至少选择两个。投资总额不能超过投资总额不能超过720720万元，问应该选择哪几个销售万元，问应该选择哪几个销售点，可使年利润为最大

8、？点，可使年利润为最大？A1A2A3A4A5A6A7A8A9A10投资额投资额10012015080709080140160180利润利润36405022203025485861109876 5432161584825302022504036maxxxxxxxxxxxz.10,.,3,2,110021127201801501201001098765432110321ixxxxxxxxxxxxxxxxii变量，为且s.t.在东区由三个点中最多在东区由三个点中最多选择两个选择两个在西区由两个点中至少在西区由两个点中至少选择一个选择一个在南区由两个点中至少在南区由两个点中至少选择一个选择一个在北区由

9、三个点中至少在北区由三个点中至少选择两个选择两个设设0-10-1变量，变量，点未被选用点未被选用，当，当点被选用；点被选用；，当，当iiixA0A1多个决策中选一个：多个决策中选一个：n1jjn1jj1x1x或决策之间存在相互依赖的逻辑关系：决策之间存在相互依赖的逻辑关系：jixx 决策之间是一种紧相关关系，即决策必须一致：决策之间是一种紧相关关系，即决策必须一致：jixx 练习：练习：1、某公司拟从六个项目中选择若干项目，用、某公司拟从六个项目中选择若干项目，用01变量表示下列关系变量表示下列关系（1）1，2，3项目中至少选择一个项目中至少选择一个（2）若项目）若项目4被选中，则项目被选中，

10、则项目6不能被选中不能被选中2、某足球队要从、某足球队要从1，2，3，4，5号队员中挑选若号队员中挑选若干名上场，用干名上场，用01变量表示下列关系变量表示下列关系（1）1，2，3号中至少选号中至少选2名名（2）只有）只有3号上场，号上场，4号才上场号才上场例：例：（选址决策问题）一家公司进行生产扩张，打（选址决策问题）一家公司进行生产扩张，打算在甲地、乙地或两地建新工厂，并且至多建一个算在甲地、乙地或两地建新工厂，并且至多建一个仓库，仓库的位置随工厂地点而定，总资本可用量仓库，仓库的位置随工厂地点而定，总资本可用量为为10（百万元），问如何选址能使总净收益最大？（百万元），问如何选址能使总净

11、收益最大？决决策策是是/否否决策决策变量变量净现收益净现收益（百万元）（百万元）资本需求资本需求（百万元）（百万元）1工厂在甲地工厂在甲地x1962工厂在乙地工厂在乙地x2533仓库在甲地仓库在甲地x3654仓库在乙地仓库在乙地x442）（若决策为否若决策为是4321j01xj,）（或4321j10 x0 xx0 xx1xx10 x2x5x3x6tsx4x6x5x9zj42314343214321,.max2、0-1型整数规划的解法：隐枚举法型整数规划的解法：隐枚举法 10,44225422.2maxz32132132132321321或或约约束束条条件件约约束束条条件件约约束束条条件件约约束

12、束条条件件xxxdxxxcxxxbxxaxxxtsxxx解：为提高搜索效率，减少运算量，先按照目标函数解：为提高搜索效率，减少运算量，先按照目标函数中各变量系数的大小顺序重新排列各变量。中各变量系数的大小顺序重新排列各变量。排为排为x x3 3,x,x2 2,x,x1 1。(x(x3 3,x,x2 2,x,x1 1)z z值值约束条件约束条件过滤条过滤条件件a ab bc cd d0 0，0 0，0 00 0，0 0，1 10 0，1 1，0 00 0，1 1，1 11 1，0 0，0 01 1，0 0，1 11 1，1 1，0 01 1，1 1，1 10 0 0z2 2 2z1 1不检验不检

13、验3 3 不检验不检验-1-1不检验不检验1 1不检验不检验0 0不检验不检验2 2 不检验不检验2max0,0,1),(1,0,0),(T321T123 zxxxxxxTT，）（即即，）（所所以以最最优优解解是是指派问题的标准形式指派问题的标准形式:1、有、有n个人个人n件事件事2、第、第i个人作第个人作第j件事的费用件事的费用cij3、人和事一一对应人和事一一对应4、目标求总成本最小、目标求总成本最小 指派问题指派问题A AB BC CD D甲甲1515171721212424乙乙1919232322221818丙丙2626171716161919丁丁1919212123231717444

14、31211414117231715zminxxxxxcijijij 111144434241343332312423222114131211xxxxxxxxxxxxxxxx 111144342414433323134232221241312111xxxxxxxxxxxxxxxx变量变量为为10 ijx指派问题标准形式的数学模型指派问题标准形式的数学模型:令令 若指派第若指派第i 人做第人做第j 事事 若不指派第若不指派第i 人做第人做第j 事事 （i，j=1，2，n）数学模型：数学模型：01xij n,2,1j,i10 xn,2,1i1xn,2,1j1x.stxczminijn1jijn1ii

15、jn1in1jijij或或15172124192322182617161919212317C步骤步骤1：每行，每列中出现每行，每列中出现0元素元素a、每行每行-此行最小元素此行最小元素b、每列每列-此列最小元素此列最小元素匈牙利法求解指派问题匈牙利法求解指派问题0269154010103246001691440100032360步骤步骤2：试指派：试指派a、从从0元素最少的元素最少的列（行）开始，给列（行）开始，给0元素加圈，同时划元素加圈，同时划去去0元素所在列的其元素所在列的其他的他的0b、重复重复a，直到所直到所有的有的0元素被加圈元素被加圈或划去或划去 c、当当个数个数=n，此此指派方

16、案即最优，指派方案即最优，否则调整否则调整0169144010003236001691440100032360-2-2+2步骤步骤4 4：a:a:任选一个没有任选一个没有的行的行,该该行所有元素减去该行除行所有元素减去该行除0 0外外的最小数的最小数(m m)；b:b:该行该行 所在的列所有元素所在的列所有元素加上加上m mc:c:该列中该列中所在的行所在的行所有所有元素再减去除元素再减去除0 0外的最小数外的最小数。如果此时没有出现负数，如果此时没有出现负数，调整结束；否则回到步骤调整结束；否则回到步骤b.b.直到系数矩阵中没有负直到系数矩阵中没有负数，而且整个消耗系数矩数，而且整个消耗系数

17、矩阵的所有元素总和已经变阵的所有元素总和已经变小；此时调整结束，小；此时调整结束，24103001004419610-1-1步骤步骤4 4：a:a:任选一个没有任选一个没有的行的行,该该行所有元素减去该行除行所有元素减去该行除0 0外外的最小数的最小数(m m)；b:b:该行该行 所在的列所有元素所在的列所有元素加上加上m mc:c:该列中该列中所在的行所在的行所有所有元素再减去除元素再减去除0 0外的最小数外的最小数。如果此时没有出现负数，如果此时没有出现负数，调整结束；否则回到步骤调整结束；否则回到步骤b.b.直到系数矩阵中没有负直到系数矩阵中没有负数，而且整个消耗系数矩数，而且整个消耗系

18、数矩阵的所有元素总和已经变阵的所有元素总和已经变小；此时调整结束，小；此时调整结束，041050010244111610041050010133011610041050010133011610试指派试指派041050010133011610调整调整-1041050010022111610+1041150011022011611-1041150011022010500此时找到了此时找到了4 4个独立零元素，所以最优指派方案为：个独立零元素，所以最优指派方案为：01001000*00100001X6917161917*z 65325746798596811练习题：练习题：1723211919161

19、726182223192421181519*Z 70*Z 非标准形式指派问题的处理非标准形式指派问题的处理1、最大化指派问题：目标函数求、最大化指派问题：目标函数求max nn2n1nn22221n11211cccccccccC nn2n1nn22221n11211cmcmcmcmcmcmcmcmcmB最大元素：最大元素：m将原系数矩阵将原系数矩阵C转换为转换为B例：有例：有5 5个工人，要指派去做个工人，要指派去做5 5项工作，每人做各项项工作，每人做各项工作的能力见下表。应如何指派，才能使总的得工作的能力见下表。应如何指派，才能使总的得分最大？分最大？J J1 1J J2 2J J3 3J

20、 J4 4J J5 5S S1 1S S2 2S S3 3S S4 4S S5 515155 51 17 712125 511110 012129 93 3131313130 08 80 08 85 53 39 9121210106 68 81212工人工人工作工作12989128130127651301108131151203515C15151515151515151515151515151515151515151515151515C12989128130127651301108131151203515367637215389102151457241031512100034305013167

21、80131235028315121000342050130678012123501831512909 91 112120 02 2-3-1004205313067501212320183151290+30042080163975012123201831512900041080162975011123200831512801000001000001000001000001*X64*z2、人数、人数事数事数人数人数事数：添加虚拟事数：添加虚拟“事事”，c=03、一个人可以做几件事、一个人可以做几件事将一人化为相同的多个人来接受指派，这多个将一人化为相同的多个人来接受指派，这多个人做同一件事的费用相

22、同人做同一件事的费用相同4、某事不能由某人来做、某事不能由某人来做将相应的费用系数取无穷大将相应的费用系数取无穷大M一个人做多件事例：某大型工程共由例：某大型工程共由5 5个项目个项目A A、B B、C C、D D、E E组成，组成，现有三个公司甲、乙、丙分别来投标，各自给出现有三个公司甲、乙、丙分别来投标，各自给出的报价如下表所示。这里甲乙丙三家公司实力均的报价如下表所示。这里甲乙丙三家公司实力均比较雄厚，可以同时进行两个项目的施工，请给比较雄厚，可以同时进行两个项目的施工，请给出最优施工分配方案。出最优施工分配方案。A AB BC CD DE E甲甲151517179 912121818乙乙14141818101011111616丙丙121219191212131315151517912180151791218014181011 16014181011 1601219121315012191213150C*010000001000000100000001000010100000X15131219121611101814181291715C一人做两事一人做两事1513121912151312191216111018141611101814181291715181291715C人多事少人多事少