第八章 整数规划

1、第八章第八章 整数规划整数规划整数规划：数学规划问题中，某些决策变量或全部决策变整数规划：数学规划问题中，某些决策变量或全部决策变量要求取整数。量要求取整数。整数线性规划（整数规划整数线性规划（整数规划IPIP）：）：目标函数和约束条件是决目标函数和约束条件是决策变量的线性形式的整数规划问题。策变量的线性形式的整数规划问题。纯整数规划：所有决策变量都是非负整数；纯整数规划：所有决策变量都是非负整数；混合整数规划：部分决策变量为非负整数；混合整数规划：部分决策变量为非负整数；0-10-1规划：所有变量只取规划：所有变量只取0 0或或1 1。例例1 1、某公司拟用集装箱托运甲、乙两种货物，这两种货

2、物的、某公司拟用集装箱托运甲、乙两种货物，这两种货物的每件体积、重量，可获利润以及托运所受限制如下表。其中每件体积、重量，可获利润以及托运所受限制如下表。其中甲种货物至多托运甲种货物至多托运4 4件，怎样安排，利润最大？件，怎样安排，利润最大？ 1 1 整数规划提出及图解法整数规划提出及图解法货物每件体积每件重量每件利润（百元）甲19542乙273403托运限制1365140解：设解：设X X1 1 , X, X2 2 为甲、乙两货物各托运件数为甲、乙两货物各托运件数195X1+273X2 13654X1+40X2 140X1 4X1 , X2 0 0X1 , X2为整数为整数maxZ = 2

3、maxZ = 2X1 + 3 X21 12 23 31 12 23 34 4* * * * * * * * * * * * * * * * * * *最优解：最优解：X X* *=(4,2)=(4,2)T T Z Z* *=2=2* *4+34+3* *2=142=14性质性质1 1 任何求最大目标函数的纯整数规划或混合整数规划的最任何求最大目标函数的纯整数规划或混合整数规划的最大值小于或等于相应的线性规划的最大目标函数值；任何大值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小值求最小目标函数值的纯整数规划或混合整数规划的最小值大于或等于相应的线

4、性规划的最小目标函数值。大于或等于相应的线性规划的最小目标函数值。整数规划最优解整数规划最优解对应线性规划最优解对应线性规划最优解整数规划最优解整数规划最优解对应线性规划最优解对应线性规划最优解目标函数目标函数MAXMAX目标函数目标函数MINMIN2 2 整数规划的应用整数规划的应用（0 01 1规划）规划）一、场址选择一、场址选择例：京成公司计划在市区东、西、南、北四区建立销售门市部，拟议中例：京成公司计划在市区东、西、南、北四区建立销售门市部，拟议中有有1010个位置个位置A Ai i(I=1,2,(I=1,2,10),10)可供选择，考虑到各地区居民的消费水平及可供选择，考虑到各地区居

5、民的消费水平及居民居住密度，规定：居民居住密度，规定：在东区由在东区由A A1 1, A, A2 2, A, A3 3三点至多选两个；在西区由三点至多选两个；在西区由A A4 4, A, A5 5两点至少选一个；两点至少选一个；在南区由在南区由A A6 6, A, A7 7至少选一个；在北区由至少选一个；在北区由A A8 8, A, A9 9, A, A1010三点至少选两个；三点至少选两个；总投资额不超过总投资额不超过720720万，问怎样选择销售点，使利润最大化？万，问怎样选择销售点，使利润最大化？A1A2A3A4A5A6A7A8A9A10投资额100 120 150 8070908014

6、0160180利润36405022203025485861解：设解：设01ixA Ai i点被选用点被选用A Ai i点没被选用点没被选用1098765432161584825302022504036maxxxxxxxxxxxz7201801601408090708015012010010987654321xxxxxxxxxx10,.,2 , 110211210987654321ixxxxxxxxxxxi变量，为二、指派问题二、指派问题例：有四个工人要去完成四项不同的工作，每人做各项工例：有四个工人要去完成四项不同的工作，每人做各项工作所消耗的时间如表，问应如何指派工作，才能使总的消作所消耗的

7、时间如表，问应如何指派工作，才能使总的消耗时间最少。耗时间最少。ABCD甲乙丙丁15192619182317212122162324181917解：设解：设01ijx第第i i个人被指派去完成第个人被指派去完成第j j项工作项工作第第i i个人没被指派去完成第个人没被指派去完成第j j项工作项工作4443424134333231242322211413121117232119191617261822231924211815minxxxxxxxxxxxxxxxxz111144434241343332312423222114131211xxxxxxxxxxxxxxxx111144342414433

8、323134232221241312111xxxxxxxxxxxxxxxx一人只一件工作一人只一件工作一件工作由一人做一件工作由一人做4,3,2,1,1 ,0jixij三、分布系统设计三、分布系统设计例某企业在例某企业在 A1 A1 地已有一个工厂，其产品的生产能力为地已有一个工厂，其产品的生产能力为 30 30 千箱，为了扩大生产，打算在千箱，为了扩大生产，打算在 A2A2，A3A3，A4A4，A5A5地中再选择地中再选择几个地方建厂。已知在几个地方建厂。已知在 A2 A2 ， A3A3，A4A4，A5A5地建厂的固定成地建厂的固定成本分别为本分别为175175千元、千元、300300千元、

9、千元、375375千元、千元、500500千元，另外，千元，另外， A1A1产量及产量及A2A2，A3A3，A4A4，A5A5建成厂的产量，那时销地的销量以建成厂的产量，那时销地的销量以及产地到销地的单位运价及产地到销地的单位运价( (每千箱运费每千箱运费) )如下表所示。如下表所示。 a) a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小总的固定成本和总的运输费用之和最小? ? b) b) 如果由于政策要求必须在如果由于政策要求必须在A2A2，A3A3地建一个厂，应在哪几个地建一个厂，应在哪几个地方建

10、厂地方建厂? ? 解解:a):a)设设x xijij为从为从A Ai i运往运往B Bj j的运输量的运输量 y yk k=1(=1(当当A Ak k被选中被选中) )或或0(0(当当A Ak k没被选中没被选中),),k k =2,3,4,5 =2,3,4,5Min z=175Min z=175y y2 2+300+300y y3 3+375+375y y4 4+500+500y y5 5+8+8x x1111+4+4x x1212+3+3x x1313+5+5x x2121+2+2x x2222+3+3x x2323+4+4x x3131+3+3x x3232+4+4x x3333+9+9

11、x x4141 +7 +7x x4242+5+5x x4343+10+10 x x5151 +4 +4x x5252+2+2x x5353x x1111+ + x x1212+ + x x13 13 3030 x x2121+ + x x2222+ + x x23 23 1010y y2 2 x x3131+ + x x3232+ + x x33 33 2020y y3 3 x x4141+ + x x4242+ + x x4343 30 30y y4 4 x x5151+ + x x5252+ + x x5353 40 40y y5 5 x x1111+ + x x2121+ + x x31

12、31+ + x x4141 + + x x5151 = 30 = 30 x x1212+ + x x2222+ + x x3232+ + x x4242 + + x x5252 = 20 = 20 x x1313+ + x x2323+ + x x3333+ + x x4343 + + x x5353 = 20 = 20 x xijij00,i ,i =1,2,3,4,5;=1,2,3,4,5;j j = 1,2,3,= 1,2,3,y yk k 为为0-10-1变量变量k k =2,3,4,5=2,3,4,5。四、投资问题四、投资问题例例8.8.某公司在今后五年内考虑给以下的项目投资。已知：

13、某公司在今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第四年每年年初需要投资，并于次年末回收：从第一年到第四年每年年初需要投资，并于次年末回收本利本利115%115%，但要求第一年投资最低金额为，但要求第一年投资最低金额为4 4万元万元, ,第二、三、四第二、三、四年不限；年不限；项目项目B B：第三年初需要投资，到第五年末能回收本利：第三年初需要投资，到第五年末能回收本利128128，但，但规定最低投资金额为规定最低投资金额为3 3万元，最高金额为万元，最高金额为5 5万元；万元；项目项目 C C：第二年初需要投资，到第五年末能回收本利：第二年初需要投资，到第五年末能回收本

14、利140%140%，但，但规定其投资额或为规定其投资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。项目项目 D D：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项投资金额不限。，此项投资金额不限。该部门现有资金该部门现有资金1010万元，问它应如何确定给这些项目的每年投万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大资额，使到第五年末拥有的资金本利总额为最大? ?整数规划解法整数规划解法分枝定界法分枝定界法 分枝定界法是先求解整数规划相应的线性规划问题。如果

15、分枝定界法是先求解整数规划相应的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界用增加其最优解不符合整数条件，则求出整数规划的上下界用增加约束条件的方法，并把相应的线性规划的可行域分成子区域约束条件的方法，并把相应的线性规划的可行域分成子区域（分枝），在求解这些子区域上的线性规划问题，不断缩小（分枝），在求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后取得整数规划的最优解。整数规划的上下界的距离，最后取得整数规划的最优解。 例：例：195X1+273X2 13654X1+40X2 140X1 , X2 0 0X1 , X2为整数为整数maxZ = 2maxZ

16、 = 2X1 + 3 X21 1）求相应线性规划问题）求相应线性规划问题LP1LP1的解的解2132maxxxz0,414040413652731952112121xxxxxxxTxz)26. 3 ,44. 2(66.14) 1 () 1 (取取 ，观察取，观察取 66.14z0z取取x x1 1=2.44=2.44进行分支，将约束条件进行分支，将约束条件 加入问题加入问题LP1 LP1 21x31xLP3:LP3:2132maxxxz0,34140404136527319521112121xxxxxxxxTxz)86.2,3(58.14)3()3(2132maxxxz0,24140404136527319521112121xxxxxxxxTxz)30.3 ,2(90.13)2()2(LP2:LP2:58.14z对对LP3LP3进行分支，将约束条件进行分支，将约束条件 加入问题加入问题LP3 LP3 22x32x2132maxxxz0,2341404041365273195212112121xxxxxxxxxTxz)2,4(14)4()4(LP4:LP4:14zLP5:LP5:2132maxxxz0,3341404041365273195212112121xxxxxxxxx无可行解无可行解14zTx)2, 4(*14*zLP1:LP1:Z Z(1