运筹学整数规划建模PPT学习教案

1、会计学1 运筹学整数规划建模运筹学整数规划建模 经济管理当中经常存在人员分派问题，企业中有经济管理当中经常存在人员分派问题，企业中有4 个人可以胜任个人可以胜任4项不同工作的任意一项，但是完成项不同工作的任意一项，但是完成 工作的效率有所不同。如表所示：工作的效率有所不同。如表所示： 为了使得企业获得最好的经济效益，应该如何分派为了使得企业获得最好的经济效益，应该如何分派 这四个人完成四项不同工作？这四个人完成四项不同工作？ 第1页/共40页 第2页/共40页 第3页/共40页 第4页/共40页 设决策变量设决策变量xj为对第为对第j个方案的取（个方案的取（xj=1） 或舍（或舍（xj=0），

2、可得到下列整数规划问题，），可得到下列整数规划问题， 是是01规划。规划。 yj yj yjx xij 为整数 第5页/共40页 第6页/共40页 8 例某公司考虑今后五年内给以下项目投资。例某公司考虑今后五年内给以下项目投资。 项目项目A：每年年初可以投资，于次年末回收本利：每年年初可以投资，于次年末回收本利 115% ，投资金额必须为，投资金额必须为1万元的整数倍；万元的整数倍； 项目项目 B ：每年初可购买公债，于当年末归还，并加：每年初可购买公债，于当年末归还，并加 利息利息6%，投资金额必须为，投资金额必须为1万元的整数倍；万元的整数倍； 项目项目 C：第：第2年初可以投资，到第年初

3、可以投资，到第5年未能回收本利年未能回收本利 140% ，投资金额必须为，投资金额必须为1万元的整数倍；万元的整数倍； 项目项目D：第：第3年初可以投资，到第年初可以投资，到第5年未能回收本利年未能回收本利 128% ，如果投资金额必须大于，如果投资金额必须大于2万元；万元； 该部门现有资金该部门现有资金10万元，问它应如何确定给万元，问它应如何确定给 这些项目的每年投资额，使到第这些项目的每年投资额，使到第 5 年末拥有年末拥有 的资金本利总额为最大的资金本利总额为最大? 第7页/共40页 9 第8页/共40页 1 1, 2, 0 () : i i ij i yim y xij 动 用仓 库

4、 令 否 则 为 指 示 变 量 从 仓 库 到顾 客 运 送 的 货 物 量 第9页/共40页 第10页/共40页 第11页/共40页 ,2,1 10 ,2,1 ,2,1 0 ,2,1 0 ,2,1 . min 11 1 111 miy njmix midyx njdxts yfxc i ij n j ji n j ij j m i ij m i m i ii n j ijij 或 取足够大的数，取足够大的数， 迫使当迫使当yi=0时，时， xij必须为必须为0 第12页/共40页 第13页/共40页 mibxa i n j jij , 2 , 1 1 miMbyMxa iiii n j j

5、ij , 2 , 1 1 第14页/共40页 ky m i i 1 第15页/共40页 niyMx iii , 2 , 1 0 ky m i i 1 第16页/共40页 kibxa i n j jj ,2, 1 1 k bbbb 210 k ccc 21 第17页/共40页 第18页/共40页 用电量8070 第19页/共40页 （6-9） 由此不难看出式（由此不难看出式（6-7）以及式）以及式 （6-8）决定了式（）决定了式（6-6）中的一）中的一 个式子成立，而式（个式子成立，而式（6-9）表明）表明 把相应的代价加到目标函数中。把相应的代价加到目标函数中。 0 01 k i ii n j

6、 jj ybxa 1 1 k i i y k i ii yc 1 第20页/共40页 第21页/共40页 23 第22页/共40页 24 第23页/共40页 25 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj为为0-1变量，变量， j = 1,2,3,10 第24页/共40页 第25页/共40页 27 制定一个生产计划，使获得的制定一个生产计划，使获得的 利利 润为最大。润为最大。 整数规划建模整数规划建模 第26页/共40页 28 第27页/共40页 第28页/共40页 30 第29页/共40页 31 一项工作一项工作)

7、x41+ x42+ x43+ x44= 1 (丁只能干丁只能干 一项工作一项工作) x11+ x21+ x31+ x41= 1 ( A工作只工作只 能一人干能一人干) x12+ x22+ x32+ x42= 1 ( B工作只工作只 能一人干能一人干) x13+ x23+ x33+ x43= 1 ( C工作只工作只 能一人干能一人干) x14+ x24+ x34+ x44= 1 ( D工作只工作只 能一人干能一人干) xij为为0-1变量变量，i,j = 1,2,3,4 第30页/共40页 32 例某企业在例某企业在 A1 地已有工厂，其产品的生产能地已有工厂，其产品的生产能 力为力为30 万箱

8、。为扩大生产，拟在万箱。为扩大生产，拟在 A2，A3，A4 ，A5地中再选择若干地建厂。已知在地中再选择若干地建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为地建厂的固定成本分别为17.5、 30、37.5、50万元，另外，万元，另外， A1产量及产量及A2，A3 ，A4，A5建成厂的产量，那时销地的销量以建成厂的产量，那时销地的销量以 及产地到销地的单位运价及产地到销地的单位运价(每万箱运费每万箱运费)如右下如右下 表所示。表所示。 问应该在哪些地方建厂，在满足销量的前提下，问应该在哪些地方建厂，在满足销量的前提下， 使得其总的固定成使得其总的固定成 本和总的运输费用本和总的运

9、输费用 之和最小之和最小? 整数规划建模整数规划建模 第31页/共40页 33 第32页/共40页 34 例某公司考虑今后五年内给以下项目投资。例某公司考虑今后五年内给以下项目投资。 项目项目A：每年年初需要投资，于次年末回收本利：每年年初需要投资，于次年末回收本利 115%，但要求第，但要求第1年投资最低金额为年投资最低金额为4万元，第万元，第2、3 、4年不限；年不限； 项目项目B：第：第3年初投资，到第年初投资，到第5年未能回收本利年未能回收本利128 ，但规定最低投资金额为，但规定最低投资金额为3万元，最高金额为万元，最高金额为5万元万元 ； 项目项目 C：第：第2年初投资，到第年初投

10、资，到第5年未能回收本利年未能回收本利140% ，但规定其投资额只能为，但规定其投资额只能为2、4、6或或8万元。万元。 项目项目 D：每年初可购买公债，于当年末归还，并加：每年初可购买公债，于当年末归还，并加 利息利息6%，此项投资金额不限。，此项投资金额不限。 该部门现有资金该部门现有资金10万元，问它应如何确定万元，问它应如何确定 给这些项目的每年投资额，使到第给这些项目的每年投资额，使到第 5 年末拥年末拥 有的资金本利总额为最大有的资金本利总额为最大? 第33页/共40页 35 x4D x5D 第34页/共40页 36 2）约束条件：）约束条件： 第一年：年初有第一年：年初有10元，

11、元，D项目在年末可收回投项目在年末可收回投 资，故第一年年初应把全部资金投出去，于是资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 10； 第二年：第二年：A次年末才可收回投资故第二年年初次年末才可收回投资故第二年年初 的资金为的资金为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； 第