整数规划应用案例分析(课堂PPT).ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,一、投资项目的选择,利用线性规划可以来完成资金预算决策，决定对 不同项目投资额各是多少。但实际中，一些资金预算决策不是决定投资多少，而是是否进行一些固定金额的投资。,管理层必须经常面对的是：在预投入资金额度一定的情况下，是否进行一项或几项固定投资。,对每个是或否的决策：,1，是,引入决策变量x=,0，否,第四章 整数规划的应用,2,例1 投资问题,设某公司在,m,个时段里有,n,项投资计划，由于资金限制不能全部进行。已知,1),第,i,个时段里该公司可动用的资金,是,b,i,，,2),第,j,项投资计划所需要的资金是,a,ij,3),能够得到的利润,是,c,ij,。,问该公司如何选择投资计划，使,m,个时段内的总利润最大,。,3,解：设,x,ij,表示在第i个时段内对第j个投资计划的决策变量。,建立该投资问题的数学模型为：,表示第i个时段内选中第j个投资计划，,表示第i时段内未选中第j个投资计划。,4,项目,投资额(万元),投资收益(万元),1,210,150,2,300,210,3,100,60,4,130,80,5,260,180,该公司只有600万元资金可用于投资，由于技术原因，投资受到以下约束：,1）在项目1、2和3中必须有一项被选中；,2）项目3和4只能选中一项；,3）项目5被选中的前提是项目1必须被选中。,如何在上述条件下，选择一个最好的投资方案，使收益最大。,投资项目的选择,例2.,华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：,5,1 选中项目i,0 未选中项目I,(i=1,5),解：令,x,i,=,Max Z=150 x,1,+,210 x,2,+,60 x,3,+80 x,4,+,180 x,5,s.t.,210 x,1,+,300 x,2,+100 x,3,+130 x,4,+,260 x,5,600,x,1,+,x,2,+,x,3,=1,x,3,+x,4,1,x,5,x,1,x,i,=1或0(i=1,5),1,2,3必须有一项选中,3,4只能选中一项,5被选中前提是1选中,6,解得（1，0，0，1，1）,Max Z=410,即投资项目1、4、5，可以获得410万元。,7,二、分布系统设计-选址问题,在如今的全球经济中，许多公司正在全世界各个地方建立新工厂，为的是获得低劳动力成本等好处。,在为新工厂选址之前，需要分析和比较地点。每个可供选择的地点都涉及一个是或否的决策。,对每个是或否的决策：,1，是,引入决策变量 x=,0，否,在许多案例中，目标是地点的选择以使新建设施的总的成本最小化，且这新设施能满足生产的需要。,8,分布系统设计-选址问题,例3,某企业在 A,1,地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A,2,，A,3,，A,4,，A,5,地中再选择几个地方建厂。已知在 A,2,，A,3,，A,4,，A,5,地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A,1,产量及A,2,，A,3,，A,4,，A,5,建成厂的产量，各销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。,a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?,9,解,：a)设,x,ij,为从A,i,运往B,j,的运输量(单位千箱)，,y,k,=1(当A,k,被选中时)或0（当A,k,没被选中时),k,=2,3,4,5这可以表示为一个整数规划问题：,Min z=175,y,2,+300,y,3,+375,y,4,+500,y,5,+8,x,11,+4,x,12,+3,x,13,+5,x,21,+2,x,22,+3,x,23,+4,x,31,+3,x,32,+4,x,33,+9,x,41,+7,x,42,+5,x,43,+10,x,51,+4,x,52,+2,x,53,（其中前4项为固定投资额，后面的项为运输费用。）,s.t.,x,11,+,x,12,+,x,13,30 (A,1,厂的产量限制),x,21,+,x,22,+,x,23,10 (A,2,厂的产量限制),x,31,+,x,32,+,x,33,20 (A,3,厂的产量限制),x,41,+,x,42,+,x,43,30,(A,4,厂的产量限制),x,51,+,x,52,+,x,53,40,(A,5,厂的产量限制),x,11,+,x,21,+,x,31,+,x,41,+,x,51,=30 (B,1,销地的限制),x,12,+,x,22,+,x,32,+,x,42,+,x,52,=20 (B,2,销地的限制),x,13,+,x,23,+,x,33,+,x,43,+,x,53,=20 (B,3,销地的限制),x,ij,0,，i,=1,2,3,4,5；,j,=1,2,3，,y,k,为0-1变量，,k,=2,3,4,5。,模型检查！是否有问题？,10,解：a)设,x,ij,为从A,i,运往B,j,的运输量(单位千箱)，,y,k,=1(当A,k,被选中时)或0（当A,k,没被选中时),k,=2,3,4,5这可以表示为一个整数规划问题：,Min z=175,y,2,+300,y,3,+375,y,4,+500,y,5,+8,x,11,+4,x,12,+3,x,13,+5,x,21,+2,x,22,+,3,x,23,+4,x,31,+3,x,32,+4,x,33,+9,x,41,+7,x,42,+5,x,43,+10,x,51,+4,x,52,+2,x,53,（其中前4项为固定投资额，后面的项为运输费用。）,s.t.,x,11,+,x,12,+,x,13,30 (A,1,厂的产量限制),x,21,+,x,22,+,x,23,10,y,2,(A,2,厂的产量限制),x,31,+,x,32,+,x,33,20,y,3,(A,3,厂的产量限制),x,41,+,x,42,+,x,43,30,y,4,(A,4,厂的产量限制),x,51,+,x,52,+,x,53,40,y,5,(A,5,厂的产量限制),x,11,+,x,21,+,x,31,+,x,41,+,x,51,=30 (B,1,销地的限制),x,12,+,x,22,+,x,32,+,x,42,+,x,52,=20 (B,2,销地的限制),x,13,+,x,23,+,x,33,+,x,43,+,x,53,=20 (B,3,销地的限制),x,ij,0,，i,=1,2,3,4,5；,j,=1,2,3，,y,k,为0-1变量，,k,=2,3,4,5。,b)如果由于政策要求必须在A,2,，A,3,地建一个厂，应在哪几个地方建厂?,11,练习,例4.某钻井队要人以下10个可供选择的井位中确定5个钻井探油,使总的钻探费用为最小,若10个井位的代号为 ,相应的钻探险费用为 ,并且井位选择上要满足下列限制条件:,或选择 和 ,或选择,选择了 或 就不能选 ,或反过来也一,样,在 中最多只能选两个.,试建成立这个问题的整数规划模型,12,解:设决策变量,目标函数,为,约束条件:,1)从10个可供选择的井位中确定5个探油,则,2)或选择 和 ,或选择 可表示为,13,3)选择了 或 就不能选 ,反过来也一样,可表示为,4)在 中最多只能选两个可表示为,综上所述,该问题的整数规划模型如下:,14,例5.某部队为了完成某项特殊任务,需要昼夜24小时不间断值班,但每天不同的阶段所需要的人数不同,具体情况如下.假设值班人员分别在各时间段开始时上班,并连续工作8小时.该部队要完成这项任务至少需要配备多少名值班人员?,班次 时间段 需要人数,1 6:00-10:00 60,2 10:00-14:00 70,3 14:00-18:00 60,4 18:00-22:00 50,5 22:00-2:00 20,6 2:00-6:00 30,三、值班安排,15,解:设分别表示第i个班次开始上班的人数,每个人连续值班8小时.根据题意所求问题归结为如下整数规划的数学模型:,16,MODEL:,Sets:,Num/1.6/:b,x;,Endsets,Data:,b=60,70,60,50,20,30;,Enddata,OBJmin=sum(num(i):x(i);,x(1)+x(6)=60;,x(1)+x(2)=70;,x(2)+x(3)=60;,x(3)+x(4)=50;,x(4)+x(5)=20;,x(5)+x(6)=30;,for(num(i):GIN(x(i);x(i)=0;);,END,17,练习(兼职值班),例6.东方大学计算机实验室聘用4名大学生(代号1,2,3,4)和2名研究生(代号5,6)值班答疑.已知每人从周一至周五每天最多可安排的值班时间及每人每小时的值班报酬如下:,班次 报酬 每天最多可安排的值班时间,(元/时)周一 周二 周三 周四 周五,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,18,该实验室开放时间为上午8:00至晚上10:00,开放时间内须有且仅须一名学生值班.规定大学生每周值班不少于8小时,研究生每周不少于7小时,每名学生每周值班不超过3次,每次值班不少于2小时,每天安排的值班学生不超过3人,且其中必须有一名研究生.试为该实验室安排一张人员值班表,使总支付的报酬最少,班次 报酬 每天最多可安排的值班时间,(元/时)周一 周二 周三 周四 周五,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,19,解:设 为学生 i在周j的值班时间,分析约束条件:,20,21,四、固定成本问题,例7高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,22,解：这是一个整数规划的问题。,设,x,1,，,x,2,，,x,3,分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设,y,i,=1(当生产第 i种容器,即,x,i,0 时)或,0（当不生产第 i种容器即,x,i,=0 时）。,引入约束,x,i,M,y,i,，i=1，2，3，M充分大，以保证当,y,i,=0 时，,x,i,=0。,可建立如下的数学模型：,Max z=4,x,1,+5,x,2,+6,x,3,-100y,1,-150y,2,-200y,3,s.t.2,x,1,+4,x,2,+8,x,3,500,2,x,1,+3,x,2,+4,x,3,300,x,1,+2,x,2,+3,x,3,100,x,i,M,y,i,，i=1，2，3，M充分大,x,j,0,y,j,为0-1变量,，i,=1,2,3,23,五、,分配问题(Assignment problem),有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由,于每人特长不同，完成各项任务的效率等情况也不同。现假设必须,指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使,得完成 n 项任务的总的效率最高，这就是,指派问题。,例8.4个人完成4项工作任务，由于个人的技术专长不同，他们完成4项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需一人操作，试求使收益最大的分派方案？,24,解：引入01变量,x,ij，,并令,x,ij,=1(当指派第 i名队员游第j种姿势)或0（当不指派第 i名队员游第j种姿势)这可以表示为一个0-1整数规划问题：,Min z=56,x,11,+74,x,12,+61,x,13,+63,x,14,+63,x,21,+69,x,22,+65,x,23,+71,x,24,+57,x,31,+77,x,32,+63,x,33,+67,x,34,+55,x,41,+76,x,42,+62,x,43,+62,x,44,s.t.,x,11,+,x,12,+,x,13,+,x,14,=1 (A只能游一种姿势),x,21,+,x,22,+,x,23,+,x,24,=1 (B只能游一种姿势),x,31,+,x,32,+,x,33,+,x,34,=1 (C只能游一种姿势),x,41,+,x,42,+,x,43,+,x,44,=1 (D只能游一种姿势),x,11,+,x,21,+,x,31,+,x,41,=1 (自由泳只能一人游),x,12,+,x,22,+,x,32,+,x,42,=1 (蛙泳只能一人游),x,13,+,x,23,+,x,33,+,x,43,=1 (蝶泳只能一人游),x,14,+,x,24,+,x,34,+,x,44,=1 (仰泳只能一人泳),x,ij,为0-1变量,，i,j,=1,2,3,4,25,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,26,备用,例9.某公司在今后五年内考虑给以下的项目投资。已知：,项目A：从第一年到第四年每年年初可以投资，并于次年末回收本利115%，但第一年如果投资则最低金额为4万元，第二、三、四年不限；,项目B：第三年初可以投资，到第五年末能回收本利128，但规定最低投资金额为3万元，最高金额为5万元；,项目 C：第二年初可以投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。,项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。,该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?,27,解：,1)设,x,iA、,x,iB、,x,iC、,x,iD,(i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；,设,y,iA,，,y,iB,，是01变量，并规定取 1 时分别表示第 i 年给A、B投资，否则取 0（i=1,2,3,4,5）。,设,y,2C,是非负整数变量，并规定：第2年投资C项目8万元时,，取值为4；第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；,这样我们建立如下的决策变量：,第1年 第2年 第3年 第4年 第5年,A,x,1A,x,2A,x,3A,x,4A,B,x,3B,C,x,2C,=20000y,2C,D,x,1D,x,2D,x,3D,x,4D,x,5D,28,2）约束条件：,第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是,x,1A,+,x,1D,=100000；,第二年：A的投资第二年末才可收回，故第二年年初的资金为1.06,x,1D,，于是,x,2A,+,x,2C,+,x,2D,=1.06,x,1D,；,第三年：年初的资金为 1.15,x,1A,+1.06,x,2D,，于是,x,3A,+,x,3B,+,x,3D,=1.15,x,1A,+1.06,x,2D,；,第四年：年初的资金为 1.15,x,2A,+1.06,x,3D,，于是,x,4A,+,x,4D,=1.15,x,2A,+1.06,x,3D,；,第五年：年初的资金为 1.15,x,3A,+1.06,x,4D,，于是,x,5D,=1.15,x,3A,+1.06,x,4D,。,关于项目A的投资额规定:,x,1A,40000,y,1A,，,x,1A,200000,y,1A,，200000是足够大的数；保证当,y,1A,=0时，,x,1A,=0；当,y,1A,=1时，,x,1A,40000。,关于项目B的投资额规定:,x,3B,30000,y,3B,，,x,3B,50000,y,3B,；,保证当,y,3B,=0时，,x,3B,=0；当,y,3B,=1时，50000,x,3B,30000。,关于项目C的投资额规定:,x,2C,=20000,y,2C,，,y,2C,=0，1，2，3，4。,29,3）目标函数及模型：,Max z=1.15,x,4A,+1.40,x,2C,+1.28,x,3B,+1.06,x,5D,s.t.,x,1A,+,x,1D,=100000；,x,2A,+,x,2C,+,x,2D,=1.06,x,1D,；,x,3A,+,x,3B,+,x,3D,=1.15,x,1A,+1.06,x,2D,；,x,4A,+,x,4D,=1.15,x,2A,+1.06,x,3D,；,x,5D,=1.15,x,3A,+1.06,x,4D,；,x,1A,40000,y,1A,，,x,1A,200000,y,1A,，,x,3B,30000,y,3B,，,x,3B,50000,y,3B,；,x,2C,=20000,y,2C,，,y,iA,，,y,iB,=0,或 1，i=1,2,3,4,5,y,2C,=0，1，2，3，4,x,iA,，,x,iB,，,x,iC,，,x,iD,0 (i=1、2、3、4、5）,30,例10,（电力规划问题,）某地区在制定十年电力规划时，遇到这样一个问题，根据电力需求预测，该地区十年以后发电装机容量需要增加180万千瓦，到时年发电量需增加100亿度，根据调查和讨论，电力规划的备选技术方案有三个,：,扩建原有火电站,，,但最多只能安装,5,台,10,万千瓦机组；,新建水电站，但最多只能安装,4,台,25,万千瓦机组；,新建火电站，但最多只能安装,4,台,30,万千瓦机组,。,通过调研和计算，获得有关参数如下：,31,备选方案,工程特点,前期工程投资(百万元),单机设备投资(百万元),单机容量(万千瓦),允许装机台数,1,扩建火电站,21,10,5,2,新建水电站,504,70,25,4,3,新建火电站,240,65,30,4,32,备选方案,工程特点,资本回收因子,年运行成本(百万元/亿度),负荷因子,1,扩建火电站,0.103,4.11,0.66,2,新建水电站,0.0578,2.28,0.4,3,新建火电站,0.103,3.65,0.7,注：负荷因子=全年满功率运行天数/全年总天数。方案1：241天；方案2：146天；方案3：255天；,33,建立模型：,设置决策变量,设备选方案,1,，,2,，,3,的装机台数分别为,x,1,、,x,2,、,x,3,，,它们的年发电量分别为,x,6,、,x,7,、,x,8,亿度，备选方案,1,无前期土建工程要求，备选方案,2,和,3,都需要前期土建工程，这两个前期土建工程是否施工用变量,x,4,、,x,5,代表,。,34,则x,1,取值0-5之间的整数，x,2、,x,3,取值0-4之间的整数，,x,4、,x,5,只能取0或1，x,6、,x,7、,x,8,大于零。,约束方程,满足装机容量需求约束：,10 x,1,+25x,2,+,30 x,3,180,满足规划年发电量需求约束：,x,6,+x,7,+,x,8,100,35,各电站容量与发电量平衡方程：,机组年发电量等于单机容量乘全年小时数，再乘以负荷因子，换算亿度量纲，即：,方案,1,：,x,6,=(0.66*8760*10/10000)*x,1,方案,2,：,x,7,=(0.4*8760*25/10000)*x,2,36,方案3：,x,8,=(0.7*8760*30/10000)*x,3,得三个约束方程：,5.782 x,1,-,x,6,=0,8.76 x,2,-,x,7,=0,18.39 x,3,-,x,8,=0,37,每个方案最多的装机台数约束：,方案,1,：不需前期土建工程；,x,1,5,方案,2,：前期土建工程是装机的先决条件，且小于最大允许数；,x,2,4 x,4,方案,3,：前期土建工程是装机的先决条件，且小于最大允许数；,x,3,4 x,5,38,变量取值限制,x,1,、,x,2,、,x,3,0,且整数,x,6,、,x,7,、,x,8,0,x,4,或,x,5,=1,前期土建工程要求,x,4,或,x,5,=0,无前期土建工程要求,39,设计目标函数,目标函数：年成本费用最低。,成本包括两大部分：,可变成本,与发电量有关的成本，如：原材料，燃料，动力和活劳动消耗等。即参数表中年运行成本。,不变成本,指与装机容量及前期土建投资有关的成本。,40,方案1：单机投资*回收因子=21*0.103=2.163(百万元）,方案2：单机投资*回收因子=70*0.0578=4.046(百万元）,方案3：单机投资*回收因子=65*0.103=6.695(百万元）,方案2和3的前期土建投资的年资本回收成本分别为504*0.0578=29.131(百万元）,240*0.103=24.72(百万元）,41,对方案1，2，3每发一亿度电的运行成本分别为4.11,2.28,3.65百万元。,则数学模型如下：,Min Z=2.163x,1,+4.046x,2,+,6.695x,3,+,29.131x,4,+,24.72x,5,+,4.11x,6,+,2.28x,7,+,3.65x,8,s.t.10 x,1,+25x,2,+,30 x,3,180,x,6,+x,7,+,x,8,100,42,5.782 x,1,-,x,6,=0,8.76 x,2,-,x,7,=0,18.39 x,3,-,x,8,=0,x,1,5,x,2,4 x,4,x,3,4 x,5,x,1、,x,2、,x,3,0 且整数,x,6、,x,7、,x,8,0 x,4,、x,5,=1或0,43,求解得到：,x,1,=2 x,2,=4 x,3,=3 x,4,=1,x,5,=1 x,6,=11.56,x,7,=,35.04,x,8,=55.17 Z=423.24百万元。,44,扩建原有火电站，安装,2,台,10,万千 瓦发电机组；,新建水电站，安装,4,台,25,万千瓦发电机组；,新建火电站，安装,3,台,30,万千瓦发电机组,。,总装机容量达：,2*10+4*25+3*30=210,万千瓦,45,谢谢大家！,46,