整数规划应用案例分析

1、.,.,一、投资项目的选择利用线性规划可以来完成资金预算决策，决定对不同项目投资额各是多少。但实际中，一些资金预算决策不是决定投资多少，而是是否进行一些固定金额的投资。管理层必须经常面对的是：在预投入资金额度一定的情况下，是否进行一项或几项固定投资。对每个是或否的决策：1，是引入决策变量x=0，否,第四章整数规划的应用,.,例1投资问题,设某公司在m个时段里有n项投资计划，由于资金限制不能全部进行。已知1)第i个时段里该公司可动用的资金是bi，2)第j项投资计划所需要的资金是aij,3)能够得到的利润是cij。问该公司如何选择投资计划，使m个时段内的总利润最大。,.,解：设xij表示在第i个时

2、段内对第j个投资计划的决策变量。,建立该投资问题的数学模型为：,表示第i个时段内选中第j个投资计划，,表示第i时段内未选中第j个投资计划。,.,该公司只有600万元资金可用于投资，由于技术原因，投资受到以下约束：1）在项目1、2和3中必须有一项被选中；2）项目3和4只能选中一项；3）项目5被选中的前提是项目1必须被选中。如何在上述条件下，选择一个最好的投资方案，使收益最大。,投资项目的选择例2.华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：,.,1选中项目i0未选中项目I(i=1,5),解：令xi=,MaxZ=150 x1+210 x2+60 x3+80 x4+180

3、 x5s.t.210 x1+300 x2+100 x3+130 x4+260 x5600 x1+x2+x3=1x3+x41x5x1xi=1或0(i=1,5),1,2,3必须有一项选中,3,4只能选中一项,5被选中前提是1选中,.,解得（1，0，0，1，1）MaxZ=410即投资项目1、4、5，可以获得410万元。,.,二、分布系统设计-选址问题,在如今的全球经济中，许多公司正在全世界各个地方建立新工厂，为的是获得低劳动力成本等好处。在为新工厂选址之前，需要分析和比较地点。每个可供选择的地点都涉及一个是或否的决策。,对每个是或否的决策：1，是引入决策变量x=0，否在许多案例中，目标是地点的选择以

4、使新建设施的总的成本最小化，且这新设施能满足生产的需要。,.,分布系统设计-选址问题例3某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，各销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?,.,解：a)设xij为从Ai运往Bj的运输量(单位千箱)，yk=1(当Ak被选中时)或

5、0（当Ak没被选中时),k=2,3,4,5这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53（其中前4项为固定投资额，后面的项为运输费用。）s.t.x11+x12+x1330(A1厂的产量限制)x21+x22+x2310(A2厂的产量限制)x31+x32+x3320(A3厂的产量限制)x41+x42+x4330(A4厂的产量限制)x51+x52+x5340(A5厂的产量限制)x11+x21+x31+x41+

6、x51=30(B1销地的限制)x12+x22+x32+x42+x52=20(B2销地的限制)x13+x23+x33+x43+x53=20(B3销地的限制)xij0，i=1,2,3,4,5；j=1,2,3，yk为0-1变量，k=2,3,4,5。,模型检查！是否有问题？,.,解：a)设xij为从Ai运往Bj的运输量(单位千箱)，yk=1(当Ak被选中时)或0（当Ak没被选中时),k=2,3,4,5这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x4

7、3+10 x51+4x52+2x53（其中前4项为固定投资额，后面的项为运输费用。）s.t.x11+x12+x1330(A1厂的产量限制)x21+x22+x2310y2(A2厂的产量限制)x31+x32+x3320y3(A3厂的产量限制)x41+x42+x4330y4(A4厂的产量限制)x51+x52+x5340y5(A5厂的产量限制)x11+x21+x31+x41+x51=30(B1销地的限制)x12+x22+x32+x42+x52=20(B2销地的限制)x13+x23+x33+x43+x53=20(B3销地的限制)xij0，i=1,2,3,4,5；j=1,2,3，yk为0-1变量，k=2,

8、3,4,5。b)如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?,.,练习,例4.某钻井队要人以下10个可供选择的井位中确定5个钻井探油,使总的钻探费用为最小,若10个井位的代号为,相应的钻探险费用为,并且井位选择上要满足下列限制条件:或选择和,或选择选择了或就不能选,或反过来也一样在中最多只能选两个.试建成立这个问题的整数规划模型,.,解:设决策变量目标函数为约束条件:1)从10个可供选择的井位中确定5个探油,则2)或选择和,或选择可表示为,.,3)选择了或就不能选,反过来也一样,可表示为4)在中最多只能选两个可表示为综上所述,该问题的整数规划模型如下:,.,例5.某部队为了

9、完成某项特殊任务,需要昼夜24小时不间断值班,但每天不同的阶段所需要的人数不同,具体情况如下.假设值班人员分别在各时间段开始时上班,并连续工作8小时.该部队要完成这项任务至少需要配备多少名值班人员?班次时间段需要人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030,三、值班安排,.,解:设分别表示第i个班次开始上班的人数,每个人连续值班8小时.根据题意所求问题归结为如下整数规划的数学模型:,.,MODEL:Sets:Num/1.6/:b,x;EndsetsData:b=60,70,6

10、0,50,20,30;EnddataOBJmin=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,.,练习(兼职值班),例6.东方大学计算机实验室聘用4名大学生(代号1,2,3,4)和2名研究生(代号5,6)值班答疑.已知每人从周一至周五每天最多可安排的值班时间及每人每小时的值班报酬如下:,班次报酬每天最多可安排的值班时间(元/时)周一周二周三周四周五110.060607210.006060

11、39.94830549.855604510.830480611.306063,.,该实验室开放时间为上午8:00至晚上10:00,开放时间内须有且仅须一名学生值班.规定大学生每周值班不少于8小时,研究生每周不少于7小时,每名学生每周值班不超过3次,每次值班不少于2小时,每天安排的值班学生不超过3人,且其中必须有一名研究生.试为该实验室安排一张人员值班表,使总支付的报酬最少,班次报酬每天最多可安排的值班时间(元/时)周一周二周三周四周五110.060607210.00606039.94830549.855604510.830480611.306063,.,解:设为学生i在周j的值班时间,分析约束

12、条件:,.,.,四、固定成本问题例7高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,.,解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，

13、为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi0时)或0（当不生产第i种容器即xi=0时）。引入约束xiMyi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x35002x1+3x2+4x3300 x1+2x2+3x3100 xiMyi，i=1，2，3，M充分大xj0yj为0-1变量，i=1,2,3,.,五、分配问题(Assignmentproblem)有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。

14、现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。例8.4个人完成4项工作任务，由于个人的技术专长不同，他们完成4项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需一人操作，试求使收益最大的分派方案？,.,解：引入01变量xij，并令xij=1(当指派第i名队员游第j种姿势)或0（当不指派第i名队员游第j种姿势)这可以表示为一个0-1整数规划问题：Minz=56x11+74x12+61x13+63x14+63x21+69x22+65x23+71x24+57x31+77x32+63x33+67x34+55x4

15、1+76x42+62x43+62x44s.t.x11+x12+x13+x14=1(A只能游一种姿势)x21+x22+x23+x24=1(B只能游一种姿势)x31+x32+x33+x34=1(C只能游一种姿势)x41+x42+x43+x44=1(D只能游一种姿势)x11+x21+x31+x41=1(自由泳只能一人游)x12+x22+x32+x42=1(蛙泳只能一人游)x13+x23+x33+x43=1(蝶泳只能一人游)x14+x24+x34+x44=1(仰泳只能一人泳)xij为0-1变量，i,j=1,2,3,4,.,Model:sets:num_i/1.4/;num_j/1.4/;link(nu

16、m_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.某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初可以投资，并于次年末回收本利115%，但第

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

18、时分别表示第i年给A、B投资，否则取0（i=1,2,3,4,5）。设y2C是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；这样我们建立如下的决策变量：第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx2C=20000y2CDx1Dx2Dx3Dx4Dx5D,.,2）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是x1A+x1D=100000；第二年：A的投资第二年末才可收回，故第二年年

19、初的资金为1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的资金为1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的资金为1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D。关于项目A的投资额规定:x1A40000y1A，x1A200000y1A，200000是足够大的数；保证当y1A=0时，x1A=0；当y1A=1时，x1A40000。关于项目B的投资额规定:x3B30000y3B，x3

20、B50000y3B；保证当y3B=0时，x3B=0；当y3B=1时，50000x3B30000。关于项目C的投资额规定:x2C=20000y2C，y2C=0，1，2，3，4。,.,3）目标函数及模型：Maxz=1.15x4A+1.40 x2C+1.28x3B+1.06x5Ds.t.x1A+x1D=100000；x2A+x2C+x2D=1.06x1D；x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A40000y1A，x1A200000y1A，x3B30000y3B，x3B50000y3B；x2C

21、=20000y2C，yiA，yiB=0或1，i=1,2,3,4,5y2C=0，1，2，3，4xiA，xiB，xiC，xiD0(i=1、2、3、4、5）,.,例10（电力规划问题）某地区在制定十年电力规划时，遇到这样一个问题，根据电力需求预测，该地区十年以后发电装机容量需要增加180万千瓦，到时年发电量需增加100亿度，根据调查和讨论，电力规划的备选技术方案有三个：,扩建原有火电站，但最多只能安装5台10万千瓦机组；新建水电站，但最多只能安装4台25万千瓦机组；新建火电站，但最多只能安装4台30万千瓦机组。通过调研和计算，获得有关参数如下：,.,.,注：负荷因子=全年满功率运行天数/全年总天数。

22、方案1：241天；方案2：146天；方案3：255天；,.,建立模型：设置决策变量设备选方案1，2，3的装机台数分别为x1、x2、x3，它们的年发电量分别为x6、x7、x8亿度，备选方案1无前期土建工程要求，备选方案2和3都需要前期土建工程，这两个前期土建工程是否施工用变量x4、x5代表。,.,则x1取值0-5之间的整数，x2、x3取值0-4之间的整数，x4、x5只能取0或1，x6、x7、x8大于零。约束方程满足装机容量需求约束：10 x1+25x2+30 x3180满足规划年发电量需求约束：x6+x7+x8100,.,各电站容量与发电量平衡方程：机组年发电量等于单机容量乘全年小时数，再乘以负荷因子，换算亿度量纲，即：方案1：x6=(0.66*8760*10/10000)*x1方案2：x7=(0.4*8760*25/10000)*x2,.,方案3：x8=(0.7*8760*30/10000)*x3得三个约束方程：5.782x1-x6=08.76x2-x7=018.39x3-x8=0,.,每个方案最多的装机台数约束：方案1：不需前期土建工程；x15方案2：前期土建工程是装机的先决条件，且小于最大允许数；x24x4方案3