整数规划应用案例分析ppt课件

1、.一、投资项目的选择一、投资项目的选择 利用线性规划可以来完成资金预算决策，决定对利用线性规划可以来完成资金预算决策，决定对 不同项目投资额各是多少。但实际中，一些资金预算决不同项目投资额各是多少。但实际中，一些资金预算决策不是决定投资多少，而是是否进行一些固定金额的投策不是决定投资多少，而是是否进行一些固定金额的投资。资。 管理层必须经常面对的是：在预投入资金额度一定管理层必须经常面对的是：在预投入资金额度一定的情况下，是否进行一项或几项固定投资。的情况下，是否进行一项或几项固定投资。 对每个是或否的决策：对每个是或否的决策： 1 1，是，是 引入决策变量引入决策变量x=x= 0 0，否，否

2、第四章第四章 整数规划的应用整数规划的应用.例例1 1 投资问题投资问题 设某公司在设某公司在m m个时段里有个时段里有n n项投资计划，由于资金限制不能项投资计划，由于资金限制不能全部进行。已知全部进行。已知 1)1)第第i i个时段里该公司可动用的资金是个时段里该公司可动用的资金是b b i i， 2)2)第第j j项投资计划所需要的资金是项投资计划所需要的资金是a a ijij , , 3) 3)能够得到的利润是能够得到的利润是c c ijij。 问该公司如何选择投资计划，使问该公司如何选择投资计划，使m m个时段内的总利润最大个时段内的总利润最大。.解：设解：设x x ijij表示在第

3、表示在第i i个时段内对第个时段内对第j j个投资计划的决策变量。个投资计划的决策变量。建立该投资问题的数学模型为：建立该投资问题的数学模型为： 表示第表示第i i个时段内选中第个时段内选中第j j个投资计划，个投资计划，表示第表示第i i时段内未选中第时段内未选中第j j个投资计划。个投资计划。01ijx1 , 0, 2 , 1. .max11ijnijiijijmiijijnjxmibxatsxcz.投资项目的选择投资项目的选择例例2. 2. .1,2,31,2,3必须有一项选中必须有一项选中3,43,4只能选中一项只能选中一项5 5被选中前提是被选中前提是1 1选中选中.二、分布系统设计

4、二、分布系统设计- -选址问题选址问题 在如今的全球经济中，许多公司正在全世界各个地在如今的全球经济中，许多公司正在全世界各个地方建立新工厂，为的是获得低劳动力成本等好处。方建立新工厂，为的是获得低劳动力成本等好处。 在为新工厂选址之前，需要分析和比较地点。每个在为新工厂选址之前，需要分析和比较地点。每个可供选择的地点都涉及一个是或否的决策。可供选择的地点都涉及一个是或否的决策。 对每个是或否的决策：对每个是或否的决策： 1 1，是，是 引入决策变量引入决策变量 x=x= 0 0，否，否 在许多案例中，目标是地点的选择以使新建设施的在许多案例中，目标是地点的选择以使新建设施的总的成本最小化，且

5、这新设施能满足生产的需要。总的成本最小化，且这新设施能满足生产的需要。.分布系统设计分布系统设计- -选址问题选址问题例例3 3某企业在某企业在 A A1 1 地已有一个工厂，其产品的生产能力为地已有一个工厂，其产品的生产能力为 30 30 千箱，千箱，为了扩大生产，打算在为了扩大生产，打算在 A A2 2，A A3 3，A A4 4，A A5 5地中再选择几个地方建厂。地中再选择几个地方建厂。已知在已知在 A A2 2 ，A A3 3，A A4 4，A A5 5地建厂的固定成本分别为地建厂的固定成本分别为175175千元、千元、300300千元、千元、375375千元、千元、500500千元

6、，另外，千元，另外， A A1 1产量及产量及A A2 2，A A3 3，A A4 4，A A5 5建成建成厂的产量，各销地的销量以及产地到销地的单位运价厂的产量，各销地的销量以及产地到销地的单位运价( (每千箱运每千箱运费费) )如下表所示。如下表所示。 a) a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小固定成本和总的运输费用之和最小? ? .解解： a) a) 设设 x xijij为从为从A Ai i 运往运往B Bj j 的运输量的运输量( (单位千箱单位千箱) )， y yk k = 1

7、(= 1(当当A Ak k 被选被选中时中时) )或或0 0（当（当A Ak k 没被选中时没被选中时),),k k =2,3,4,5 =2,3,4,5这可以表示为一个整数规这可以表示为一个整数规划问题：划问题：Min 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+9x x41 41 +7+7x x424

8、2+5+5x x4343+10+10 x x51 51 +4+4x x5252+2+2x x5353（其中前（其中前4 4项为固定投资额，后面的项为运输费用。）项为固定投资额，后面的项为运输费用。）s.t. s.t. x x1111+ + x x1212+ + x x1313 30 ( A 30 ( A1 1 厂的产量限制厂的产量限制) ) x x2121+ + x x2222+ + x x2323 10 ( A 10 ( A2 2 厂的产量限制厂的产量限制) ) x x3131+ + x x3232+ + x x33 33 20 ( A 20 ( A3 3 厂的产量限制厂的产量限制) ) x

9、 x4141+ + x x4242+ + x x43 43 30 30 ( A ( A4 4 厂的产量限制厂的产量限制) ) x x5151+ + x x5252+ + x x53 53 40 40 ( A ( A5 5 厂的产量限制厂的产量限制) ) x x1111+ + x x2121+ + x x3131+ + x x41 41 + + x x51 51 = 30 ( B= 30 ( B1 1 销地的限制销地的限制) ) x x1212+ + x x2222+ + x x3232+ + x x42 42 + + x x52 52 = 20 ( B= 20 ( B2 2 销地的限制销地的限

10、制) ) x x1313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 = 20 ( B= 20 ( B3 3 销地的限制销地的限制) ) x xijij 0 0，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。 模型检查！是否有问题？模型检查！是否有问题？.解：解： a) a) 设设 x xijij为从为从A Ai i 运往运往B Bj j 的运输量的运输量( (单位千箱单位千箱) )， y yk k = 1(=

11、1(当当A Ak k 被选中时被选中时) )或或0 0（当（当A Ak k 没被选中时没被选中时),),k k =2,3,4,5 =2,3,4,5这可以表示这可以表示为一个整数规划问题：为一个整数规划问题：Min 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+9x x41 41 +7+7x x4242+5+

12、5x x4343+10+10 x x51 51 +4+4x x5252+2+2x x5353（其中前（其中前4 4项为固定投资额，后面的项为运输费用。）项为固定投资额，后面的项为运输费用。）s.t. s.t. x x1111+ + x x1212+ + x x1313 30 ( A 30 ( A1 1 厂的产量限制厂的产量限制) ) x x2121+ + x x2222+ + x x2323 10 10y y2 2 ( A ( A2 2 厂的产量限制厂的产量限制) ) x x3131+ + x x3232+ + x x33 33 20 20y y3 3 ( A ( A3 3 厂的产量限制厂的产

13、量限制) ) x x4141+ + x x4242+ + x x43 43 30 30y y4 4 ( A ( A4 4 厂的产量限制厂的产量限制) ) x x5151+ + x x5252+ + x x53 53 40 40y y5 5 ( A ( A5 5 厂的产量限制厂的产量限制) ) x x1111+ + x x2121+ + x x3131+ + x x41 41 + + x x51 51 = 30 ( B= 30 ( B1 1 销地的限制销地的限制) ) x x1212+ + x x2222+ + x x3232+ + x x42 42 + + x x52 52 = 20 ( B=

14、 20 ( B2 2 销地的限制销地的限制) ) x x1313+ + x x2323+ + x x3333+ + x x43 43 + + x x53 53 = 20 ( B= 20 ( B3 3 销地的限制销地的限制) ) x xijij 0 0，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。 b) 如果由于政策要求必须在如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂地建一个厂，应在哪几个地方建厂? .练习练习 例例4.4.某钻井队要人以下某

15、钻井队要人以下1010个可供选择的井位中确定个可供选择的井位中确定5 5个个钻井探油钻井探油, ,使总的钻探费用为最小使总的钻探费用为最小, ,若若1010个井位的代号个井位的代号为为 , ,相应的钻探险费用为相应的钻探险费用为 , ,并且并且井位选择上要满足下列限制条件井位选择上要满足下列限制条件: :w 或选择或选择 和和 , ,或选择或选择w 选择了选择了 或或 就不能选就不能选 , ,或反过来也一或反过来也一w 样样w 在在 中最多只能选两个中最多只能选两个. .w 试建成立这个问题的整数规划模型试建成立这个问题的整数规划模型101,ss 101,cc 1s7s8s3s4s5s8765

16、,ssss.解: 设决策变量目标函数为约束条件:1)从10个可供选择的井位中确定5个探油,则2)或选择 和 ,或选择 可表示为否则井位选择钻探第, 0, 1jjsx101minjjjxcZ5101jjx1s7s8s1, 18781xxxx.3)选择了 或 就不能选 ,反过来也一样,可表示为4)在 中最多只能选两个可表示为 综上所述,该问题的整数规划模型如下:3s4s5s1, 15453xxxx8765,ssss28765xxxx101minjjjxcZ1021, 11, 15. .876554875381101或取jjjxxxxxxxxxxxxxxts. 例例5. 5. 某部队为了完成某项特殊

17、任务某部队为了完成某项特殊任务, ,需要昼夜需要昼夜2424小时小时不间断值班不间断值班, ,但每天不同的阶段所需要的人数不同但每天不同的阶段所需要的人数不同, ,具具体情况如下体情况如下. .假设值班人员分别在各时间段开始时上假设值班人员分别在各时间段开始时上班班, ,并连续工作并连续工作8 8小时小时. .该部队要完成这项任务至少需该部队要完成这项任务至少需要配备多少名值班人员要配备多少名值班人员? ? 班次班次 时间段时间段 需要人数需要人数 1 6:00-10:00 601 6:00-10:00 60 2 10:00-14:00 70 2 10:00-14:00 70 3 14:00-

18、18:00 60 3 14:00-18:00 60 4 18:00-22:00 50 4 18:00-22:00 50 5 22:00-2:00 20 5 22:00-2:00 20 6 2:00-6:00 30 6 2:00-6:00 30三、值班安排三、值班安排.解:设分别表示第i个班次开始上班的人数,每个人连续值班8小时.根据题意所求问题归结为如下整数规划的数学模型:).6,.,2 , 1(, 0,30,20,50,60,70,60. .min65544332211661ixxxxxxxxxxxxxtsxziii且为整数.w MODEL:w Sets:w Num/1.6/:b,x;w E

19、ndsetsw Data:w b=60,70,60,50,20,30;w Enddataw OBJmin=sum(num(i):x(i);w x(1)+x(6)=60;w x(1)+x(2)=70;w x(2)+x(3)=60;w x(3)+x(4)=50;w x(4)+x(5)=20;w x(5)+x(6)=30;for(num(i):GIN(x(i);x(i)=0;);END.练习 (兼职值班) 例例6.6.东方大学计算机实验室聘用东方大学计算机实验室聘用4 4名大学生名大学生( (代号代号1,2,3,4)1,2,3,4)和和2 2名研究生名研究生( (代号代号5,6)5,6)值班答疑值班

20、答疑. .已知每人已知每人从周一至周五每天最多可安排的值班时间及每人每小从周一至周五每天最多可安排的值班时间及每人每小时的值班报酬如下时的值班报酬如下: : 班次班次 报酬报酬 每天最多可安排的值班时间每天最多可安排的值班时间 (元元/时时) 周一周一 周二周二 周三周三 周四周四 周五周五 1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3 .w 该实验室开放时间为上午该实验室开放时间为上午8:008:00至晚上至晚上10:00,10:00,开放

21、时间开放时间内须有且仅须一名学生值班内须有且仅须一名学生值班. .规定大学生每周值班不规定大学生每周值班不少于少于8 8小时小时, ,研究生每周不少于研究生每周不少于7 7小时小时, ,每名学生每周值每名学生每周值班不超过班不超过3 3次次, ,每次值班不少于每次值班不少于2 2小时小时, ,每天安排的值班每天安排的值班学生不超过学生不超过3 3人人, ,且其中必须有一名研究生且其中必须有一名研究生. .试为该实试为该实验室安排一张人员值班表验室安排一张人员值班表, ,使总支付的报酬最少使总支付的报酬最少, , 班次班次 报酬报酬 每天最多可安排的值班时间每天最多可安排的值班时间 (元元/时时

22、) 周一周一 周二周二 周三周三 周四周四 周五周五 1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3 .解解: 设设 为学生为学生 i在周在周j的值班时间的值班时间,分析约束条件分析约束条件: 否则的值班时间在周安排学生, 0, 1jiyij不超过可安排的时间)5,.,1; 6,.,1(2. .jiyaxytsijijijijijx小时大学生每周值班不少于8)4,.,1(851jijix小时研究生每周值班不少于7)6 , 5(751jijix小

23、时实验室每天开放14)5,.,1(1461iijjx次每名学生一周不超过3)6,.,1(351jijiy人每天值班不超过3)5,.,1(361iijjy每天有一名研究生值班)5,.,1( 165jyyjj)5,.,1; 6,.,1( 10, 0jiyxijij或.最多可安排的值班时间在周表示学生其中或每天有一名研究生值班人每天值班不超过次每名学生一周不超过小时实验室每天开放小时研究生每周值班不少于小时大学生每周值班不少于不超过可安排的时间jiajiyxjyyjyiyjxixixjiyaxytsxczijijijjjiijjijiijjijjijijijijijijijij)5,.,1; 6,.

24、,1( 10, 0)5,.,1( 13)5,.,1(33)6,.,1(314)5,.,1(147)6 , 5(78)4,.,1(8)5,.,1; 6,.,1(2. .min6561516151516151.四、固定成本问题四、固定成本问题 例例7 7高压容器公司制造小、中、大三种尺寸的金属高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为定费用，每种容器售出一只所得的利润分别为4 4

25、万元、万元、5 5万元、万元、6 6万元，可使用的金属板有万元，可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/ /月，机器有月，机器有100100台台/ /月，此外不管每种容器制造月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是的数量是多少，都要支付一笔固定的费用：小号是l00l00万元，中号为万元，中号为 150 150 万元，大号为万元，大号为200200万元。现在万元。现在要制定一个生产计划，使获得的利润为最大。要制定一个生产计划，使获得的利润为最大。 .解：这是一个整数规划的问题。解：这是一个整数规划的问题。 设设x x1 1，x x2 2，

26、 x x3 3 分别为小号容器、中号容器和大号容器的生分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设为了说明固定费用的这种性质，设 y yi i = 1( = 1(当生产第当生产第 i i种容器种容器, , 即即 x xi i 0 0 时时) ) 或或0 0（当不生产第（当不生产第 i i种容器即种容器即 x xi i = 0 = 0 时）。时）。 引入约束引入约束 x xi i M M y yi i ，i =1i =1，2 2，3 3，M M充分大，以保证充分大，

27、以保证当当 y yi i = 0 = 0 时，时，x xi i = 0 = 0 。 可建立如下的数学模型：可建立如下的数学模型： Max z = 4Max z = 4x x1 1 + 5+ 5x x2 2 + 6+ 6x x3 3 - 100y- 100y1 1 - 150y- 150y2 2 - 200y- 200y3 3 s.t. 2 s.t. 2x x1 1 + 4+ 4x x2 2 + 8+ 8x x3 3 500 500 2 2x x1 1 + 3+ 3x x2 2 + 4+ 4x x3 3 300 300 x x1 1 + 2+ 2x x2 2 + 3+ 3x x3 3 100 1

28、00 x xi i M M y yi i ，i =1i =1，2 2，3 3，M M充分大充分大 x xj j 0 0 y yj j 为为0-10-1变量变量，i i = 1,2,3= 1,2,3.五、五、 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，但由个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把指派每个人去完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使个人，使得完成得完成 n n 项任务的总的效

29、率最高，这就是项任务的总的效率最高，这就是指派问题。指派问题。例例8. 48. 4个人完成个人完成4 4项工作任务，由于个人的技术专长不同，他们完成项工作任务，由于个人的技术专长不同，他们完成4 4项工作任务所获得的收益如下表所示，且规定每人只能做一项工项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需一人操作，试求使收益最大的分派方案？作，一项工作任务只需一人操作，试求使收益最大的分派方案？.解：引入解：引入0101变量变量 x xijij，并令并令 x xij ij = 1(= 1(当指派第当指派第 i i名队员游第名队员游第j j种姿势种姿势) )或或0 0（当

30、不指派第（当不指派第 i i名队员游第名队员游第j j种姿势种姿势) )这可以表示为一个这可以表示为一个0-10-1整数规划问题：整数规划问题：Min Min z=56z=56x x1111+74+74x x1212+61+61x x1313+63+63x x1414+63+63x x2121+69+69x x2222+65+65x x2323+71+71x x2424+57+57x x3131+77+77x x3232+ +6363x x3333+67+67x x3434+55+55x x41 41 +76+76x x4242+62+62x x4343+62+62x x4444s.t. s.

31、t. x x1111+ + x x1212+ + x x1313+ + x x1414= 1 (A= 1 (A只能游一种姿势只能游一种姿势) ) x x2121+ + x x2222+ + x x2323+ + x x2424= 1 (B= 1 (B只能游一种姿势只能游一种姿势) ) x x3131+ + x x3232+ + x x3333+ + x x3434= 1 (C= 1 (C只能游一种姿势只能游一种姿势) ) x x4141+ + x x4242+ + x x4343+ + x x4444= 1 (D= 1 (D只能游一种姿势只能游一种姿势) ) x x1111+ + x x212

32、1+ + x x3131+ + x x4141= 1 ( = 1 ( 自由泳只能一人游自由泳只能一人游) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( = 1 ( 蛙泳只能一人游蛙泳只能一人游) ) x x1313+ + x x2323+ + x x3333+ + x x4343= 1 ( = 1 ( 蝶泳只能一人游蝶泳只能一人游) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( = 1 ( 仰泳只能一人泳仰泳只能一人泳) ) x xijij 为为0-10-1变量变量，i,j i,j = 1,2,

33、3,4= 1,2,3,4 .Model:sets:num_i/1.4/;num_j/1.4/;link(num_i,num_j):a,x;endsetsdata:a=56,74,61,63,63,69,65,71,57,77,63,67,55,76,62,62;enddataOBJmin=sum(link(i,j):a(i,j)*x(i,j);for(num_i(i):sum(num_j(j):x(i.j)=1;);for(num_j(j):sum(num_i(i):x(i,j)=1;);for(link(i,j):BIN(x(i,j); x(i,j)=0;);END.备用备用 例例9.9.某

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

35、能回收本利：第二年初可以投资，到第五年末能回收本利140%140%，但规，但规定其投资额或为定其投资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。 项目项目 D D：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项投资金额不限。此项投资金额不限。 该部门现有资金该部门现有资金1010万元，问它应如何确定给这些项目的每万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大年投资额，使到第五年末拥有的资金本利总额为最大? ?.解：解：1) 设xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额； 设yiA， yiB，是