管理运筹学-整数规划

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 整数规划,1 整数规划的图解法,2整数规划的计算机求解,3整数规划的应用,4整数规划的分枝定界法,1 整数规划的图解法,例1.,某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备,需要,A、B,两种材,料的消耗以及资,源的限制，如右,表。,问题：工厂应分,别生产多少件甲、乙种仪器设备才,能使工厂获利最多？,解、,目标函数：,Max z=x,1,+x,2,约束条件：,s.t.,3 x,1,+2 x,2,10,2 x,2,5,x,1，,x,2,0,为整数,不考虑整数约束得到最优解：,x,1,=1.667，x,2,=2.5；z =4.167,考虑整数约束得到最优解：,x,1,=2，x,2,=2；,z =4,整数规划的最优目标值小于相应,线性规划的最优目标值(相当于附加一个约束),2整数规划的计算机求解,例2：,Max z=15,x,1,+10,x,2,+7,x,3,s.t.,5,x,1,-10,x,2,+7,x,3,8,6,x,1,+4,x,2,+8,x,3,12,-3,x,1,+2,x,2,+2,x,3,10,x,1,x,2,x,3,0,为整数,例2：,Max z=15,x,1,+10,x,2,+7,x,3,s.t.,5,x,1,-10,x,2,+7,x,3,8,6,x,1,+4,x,2,+8,x,3,12,-3,x,1,+2,x,2,+2,x,3,10,x,1,x,2,x,3,0,x,3,为整数,x,1,为0-1变量,用管理运筹学软件求解得：,x,1,=0,x,2,=3,x,3,=0,z=30,用管理运筹学软件求解得：,x,1,=1,x,2,=1.5,x,3,=0,z=30,3整数规划的应用(1),一、投资场所的选择,例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置,A,j,(,j1，2，3，10),可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：,在东区由,A,1,，,A,2,，,A,3,三个点至多选择两个；,在西区由,A,4,，,A,5,两个点中至少选一个；,在南区由,A,6,，,A,7,两个点中至少选一个；,在北区由,A,8,，,A,9,，,A,10,三个点中至少选两个,。,A,j,各点的设备投资及每,年可获利润由于地点不同都是,不一样的，预测情况见右表所,示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,解：,设：0-1变量,x,i,=1(A,i,点被选用）或 0,(,A,i,点没被选用）。,这样我们可建立如下的数学模型：,Max z=36,x,1,+40,x,2,+50,x,3,+22,x,4,+20,x,5,+30,x,6,+25,x,7,+48,x,8,+58,x,9,+61,x,10,s.t.100,x,1,+120,x,2,+150,x,3,+80,x,4,+70,x,5,+90,x,6,+80,x,7,+140,x,8,+160,x,9,+180,x,10,720,x,1,+,x,2,+,x,3,2,x,4,+,x,5,1,x,6,+,x,7,1,x,8,+,x,9,+,x,10,2,x,j,0,x,j,为0-1变量,，,i,=1,2,3,10,二、固定成本问题,例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机,器设备，制造一个容器所需的各种资源的数量如右,表所示。不考虑固定费用，每种容器售出一只所得,的利润分别为 4万元、5万元、6万元，可使用的金,属板有500吨，劳动力有300人月，机器有100台月，,此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是,l00,万元，中号为 150,万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,解：这是一个整数规划的问题。,设,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,3整数规划的应用(2),例6有四个工人，要分别指派他们完,成四项不同的工作，每人做各项工作所消,耗的时间如右表所示，问应如何指派工作，,才能使总的消耗时间为最少。,解,：,引入01变量,x,ij，,并令,x,ij,=1(,当指派第,i,人去完成第,j,项工作时)或0（当不指派第,i,人去完成第,j,项工作时),这可以表示为一个0-1整数规划问题：,Min z=15,x,11,+18,x,12,+21,x,13,+24,x,14,+19,x,21,+23,x,22,+22,x,23,+18,x,24,+26,x,31,+17,x,32,+16,x,33,+19,x,34,+19,x,41,+21,x,42,+23,x,43,+17,x,44,s.t.,x,11,+,x,12,+,x,13,+,x,14,=1 (,甲只能干一项工作),x,21,+,x,22,+,x,23,+,x,24,=1 (,乙只能干一项工作),x,31,+,x,32,+,x,33,+,x,34,=1 (,丙只能干一项工作),x,41,+,x,42,+,x,43,+,x,44,=1 (,丁只能干一项工作),x,11,+,x,21,+,x,31,+,x,41,=1 (A,工作只能一人干),x,12,+,x,22,+,x,32,+,x,42,=1 (B,工作只能一人干),x,13,+,x,23,+,x,33,+,x,43,=1 (C,工作只能一人干),x,14,+,x,24,+,x,34,+,x,44,=1 (D,工作只能一人干),x,ij,为0-1变量,，,i,j,=1,2,3,4,*求解可用管理运筹学软件中整数规划方法。,3整数规划的应用(3),三、指派问题,有,n,项不同的任务，恰好,n,个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把,n,项任务指派给,n,个人，使得完成,n,项任务的总的效率最高，这就是指派问题。,四、分布系统设计,例7,某企业在,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),问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?,b,)如果由于政策要求必须在,A,2,，,A,3,地建一个厂，应在哪几个地方建厂?,解：,a),设,x,ij,为从,A,i,运往,B,j,的运输量(单位千箱)，,y,i,=1(,当,A,i,被选中时)或0（当,A,i,没被选中时),这可以表示为一个整数规划问题：,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,厂的产量限制),b）,增加约束：,y,2,+,y,3,=1,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,y,i,为0-1变量,，,i,=1,2,3,4,5；,j,=1,2,3,*求解可用管理运筹学软件中整数规划方法。,3整数规划的应用(4),3整数规划的应用(5),五、投资问题,例8,某公司在今后五年内考虑给以下的项目投资。已知：,项目,A：,从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限,；,项目,B：,第三年初需要投资，到第五年未能回收本利128，但规定最低投资金额为3万元，最高金额为5万元,；,项目,C：,第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。,项目,D：,五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。,该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?,解：,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,iC,是非负整数变量，并规定：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,3整数规划的应用(6),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,1