多阶段计划问题精选PPT.ppt

多阶段计划问题第1页，此课件共53页哦1、保姆雇佣方案 一家保姆公司专门向雇主提供保姆服务，根据统计，下一年的需求是：春季6000人日，夏季7500人日，秋季5500人日，冬季9000人日。公司新招聘的保姆需要经过5天的培训才能上岗，每个保姆每季度工作（新保姆包括培训）65天，保姆从该公司而不是从雇主那里得到报酬，每人每月工资800元，春季开始时公司拥有120名保姆，在每个季度结束后，将有15%的保姆自动离职。（1）如果公司不允许解聘保姆，请你为公司指定下一年的招聘计划；那些季度需求增加不影响招聘计划，可以增加多少？（2）如果公司在每个季度结束后允许解聘保姆，请为公司制订下一年的招聘计划。第2页，此课件共53页哦季度6000人日7500人日5500人日9000人日120 x1x2x3x4变量设置x1,x2,x3,x4分别为四个季度之初新招聘的保姆数.y1y2y3y1,y2,y3,y4表示四个季度末解聘的保姆数,z1,z2,z3,z4表示每个季度总的保姆数。y4建立模型目标函数z1z2z3z4第3页，此课件共53页哦约束条件：季度6000人日7500人日5500人日9000人日120 x1x2x3x4y1y2y3y4z1z2z3保姆数的变化关系第4页，此课件共53页哦服务保障要求变量非负要求季度6000人日7500人日5500人日9000人日120 x1x2x3x4y1y2y3y4z1z2z3第5页，此课件共53页哦回答问题（1）：不允许解聘，即y1+y2+y3+y4=0，即min=2400*(z1+z2+z3+z4);z1=120+x1;z2=0.85*z1+x2-y1;z3=0.85*z2+x3-y2;z4=0.85*z3+x4-y3;65*z16000+5*x1;65*z27500+5*x2;65*z35500+5*x3;65*z49000+5*x4;y1+y2+y3+y4=0;gin(x1);gin(x2);gin(x3);gin(x4);gin(y1);gin(y2);gin(y3);gin(z1);gin(z2);gin(z3);gin(z4);第6页，此课件共53页哦 Global optimal solution found at iteration:1737 Objective value:401600.0 Variable Value Reduced Cost Z1 120.0000 800.0000 Z2 120.0000 800.0000 Z3 120.0000 800.0000 Z4 142.0000 800.0000 X1 0.000000 0.000000 X2 18.00000 0.000000 Y1 0.000000 0.000000 X3 18.00000 0.000000 Y2 0.000000 0.000000 X4 40.00000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000即在不允许解聘保姆的情况下，第二季度招聘18名保姆，第三季度招聘18名保姆，第四季度招聘40名保姆。第7页，此课件共53页哦 Row Slack or Surplus Dual Price 1 401600.0 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 1800.000 0.000000 7 210.0000 0.000000 8 2210.000 0.000000 9 30.00000 0.000000 10 0.000000 0.000000 从计算的Slack的值来看，四个季度都可以增加需求，分别增加1800,210,2210,30人日，招聘计划不用改变。第8页，此课件共53页哦回答问题（2）：允许公司解聘保姆的最优招聘计划min=2400*(z1+z2+z3+z4);z1=120+x1;z2=0.85*z1+x2-y1;z3=0.85*z2+x3-y2;z4=0.85*z3+x4-y3;65*z16000+5*x1;65*z27500+5*x2;65*z35500+5*x3;65*z49000+5*x4;gin(x1);gin(x2);gin(x3);gin(x4);gin(y1);gin(y2);gin(y3);gin(z1);gin(z2);gin(z3);gin(z4);第9页，此课件共53页哦 Global optimal solution found at iteration:7 Objective value:386400.0 Variable Value Reduced Cost Z1 120.0000 800.0000 Z2 120.0000 800.0000 Z3 100.0000 800.0000 Z4 143.0000 800.0000 X2 18.00000 0.000000 Y2 2.000000 0.000000 X4 58.00000 0.000000 Row Slack or Surplus Dual Price 6 1800.000 0.000000 7 210.0000 0.000000 8 1000.000 0.000000 9 5.000000 0.000000 新的招聘计划是：第二季度招聘18名保姆，第四季度招聘58名保姆。第10页，此课件共53页哦2、飞行员培训计划甲乙双方的一场战争，一部分甲的部队被乙包围长达4个月，由于乙方封锁了所有水陆交通要道，被包围的甲方部队只能靠空中交通维持供给。运送四个月的供给分别需要2次、3次、3次、4次飞行。每次飞行编队由50架飞机组成（每架飞机3名飞行员），可以运送10万吨物资。每架飞机每个月只能飞行一次，每名飞行员也只能飞行一次，在执行任务后返回途中有20%的飞机被乙方部队击落。相应的飞行员也因此失踪。在第一个月开始时，甲方拥有110架飞机和330名熟练飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。新飞机必须经过一个月检查后才能投入使用，新飞行员必须在熟练飞行员的指导下经过一个月培训才能投入飞行。每名熟练飞行员可以作为教练每个月指导20（包括自己在内）进行训练。每名飞行员在完成一个月的飞行任务后，必须有一个月带薪休假。假期结束后才能再次投入飞行。已知各项费用（单位略去）如下表，请你为甲方安排一个飞行计划。第11页，此课件共53页哦第1个月 第2个月 第3个月 第4个月新飞机价格闲置熟练飞行员报酬熟练和新飞行员报酬（包括培训费用）执行飞行任务的熟练飞行员报酬休假期间的熟练飞行员报酬200 195 190 185 7 6.9 6.8 6.7 10 9.9 9.8 9.79 8.9 9.8 9.7 5 4.9 4.8 4.7第12页，此课件共53页哦变量设置Xi 第i月月初购买的飞机；i=1,2,3,4Yi 第i月月初招聘的飞行员；i=1,2,3,4Zi 第i月份闲置的飞行员数量；i=1,2,3,4Ui 第i月份培训新飞行员的熟练飞行员数量；i=1,2,3,4Vi 第i月份休假的飞行员数量；i=1,2,3,4Si 第i月执行飞行任务的飞行员数量；i=1,2,3,4Ti 第i月执行飞行任务的飞机数量；i=1,2,3,4Ri 第i月用于培训的飞机数量；i=1,2,3,4Wi 第i月能用的飞机数量；i=1,2,3,4第13页，此课件共53页哦第i个月=上月休闲飞行员zi-1+上月培训完毕的新飞行员yi-1+上月休假完毕的飞行员vi-1+上月参与培训的熟练飞行员ui-1本月执行飞行任务的飞行员si+本月休闲的飞行员zi+本月参与培训的熟练飞行员ui建立模型（1）飞行员之间的数量关系i=1,2,3,4第14页，此课件共53页哦i=1时，i=2时，i=3时，i=4时，初始飞行员数量：z0=330.各种飞行员之间的关系休假飞行员与参与飞行任务的飞行员的数量关系：第15页，此课件共53页哦每个月执行任务的飞行员的数量：参与培训的熟练飞行员与新飞行员的数量关系：（2）飞机与飞行员的数量关系执行飞行任务的飞行员与执行飞行飞行任务的飞机的数量关系：第16页，此课件共53页哦培训飞机和参与培训的熟练飞行员的数量关系：（3）飞机数量约束每个月飞机总量：执行飞行任务和培训任务的飞机数量约束：（4）变量约束：出现的变量取值非负整数。第17页，此课件共53页哦（4）总费用的计算新飞机的购买费用：休闲飞行员费用：新飞行员和培训熟练飞行员的培训费：执行飞行任务的飞行员的费用：休假飞行员的费用：第18页，此课件共53页哦min=200*x1+195*x2+190*x3+185*x4+7*z1+6.9*z2+6.8*z3+6.7*z4+10*(u1+y1)+9.9*(u2+y2)+9.8*(u3+y3)+9.7*(u4+y4)+9*s1+8.9*s2+9.8*s3+9.7*s4+5*v1+4.9*v2+4.8*v3+4.7*v4;u1+z1+s1z0;s2+u2+z2z1+y1+v1+u1;s3+u3+z3z2+y2+v2+u2;s4+u4+z4=r1;u2=r2;u3=r3;u4=r4;w1=110;w2=0.8*t1+x1+r1;w3=0.8*t2+x2+r2;w4=0.8*t3+x3+r3;r1+t1w1;r2+t2w2;r3+t3w3;r4+t4w4;gin(x1);gin(x2);gin(x3);gin(x4);gin(y1);gin(y2);gin(y3);gin(y4);gin(z1);gin(z2);gin(z3);gin(z4);gin(u1);gin(u2);gin(u3);gin(u4);第19页，此课件共53页哦计算结果：Objective value:63745.80 Variable Value Reduced Cost X1 60.00000 200.0000 X2 30.00000 195.0000 X3 80.00000 190.0000 Z1 3.000000 7.000000 Z2 2.000000 6.900000 U1 23.00000 10.00000 Y1 437.0000 10.00000 U2 11.00000 9.900000 Y2 209.0000 9.900000 U3 12.00000 9.800000 Y3 228.0000 9.800000 R1 10.00000 0.000000 W1 110.0000 0.000000 W2 150.0000 0.000000 W3 150.0000 0.000000 W4 200.0000 0.000000第20页，此课件共53页哦回答问题1：第一、二、三月份各购买新飞机70，30，80架，分别招聘新飞行员437，209，228人。四个月总费用最少为65745.80。回答问题2：根据问题，新飞行员和熟练飞行员之间的关系改为同时取消闲置飞行员，即新的计算结果如下：第21页，此课件共53页哦Objective value:65750.80最小费用有所增加！方案也有所改变：第22页，此课件共53页哦3、北方印染培训计划问题 北方印染公司需要的技术工人分为初级、中级、高级三个层次，统计资料显示：培养出来的每个初级工人每年可为公司增加产值1万元，每个中级每年增加产值4万元，每个高级每年增加产值5.5万元。公司计划在今后三年拔出150万元作为职业培训费用，其中，第一年投资55万元，第二年投资45万元，第三年投资50万元。通过公司过去培养初级、中级、高级的经历并经过咨询，预计培养一名初级工，在高中毕业后需一年，费用为1000元，培养一名中级工，高中毕业需要三年，第一年和第二年的费用为3000，第三年的费用为1000元；培养一位高级工，高中毕业也需要三年，其中第一年费用为3000元，第二年费用为2000元，第三年需要4000元。目前公司共有初级工226人，中级工560人，高级工496人。若通过提高目前技术工人的水平来增加中级和高级工人的第23页，此课件共53页哦的人数，其培养时间和培养费用分别为：由初级工培养为中级工，需要一年时间，费用为2800元；由初级工直接培养为高级工需要两年，第一年费用为2000元，第二年费用为3200元；由中级工培养为高级工需一年，费用为3600元。由于公司目前师资力量不足，教学环境有限，每年可培养的职工人数受到一定限制。根据目前情况，每年在培养的初级工人不超过90人，在培养的中级工人不超过80人，在培养的高级工人数不超过80人。为了利用有限费用和资源，要确定直接由高中生培养初级、中级、高级的人数各多少，通过提高目前技术工人水平增加中级、高级人数的初级工人和中级工人数分别多少，才能使企业三年的增加值最多？第24页，此课件共53页哦高中毕业生初级中级123初级初级初级中级高级1000，x013000,x02300010003000,x03200040001000,x121000,x23中级中级中级高级高级高级高级高级2800,y012000,y0232002800,y112000,y1232002800,y213600,z013600,z113600,z21年初年末第25页，此课件共53页哦变量设置：X01表示第一年年初参加初级培训的高中毕业生人数；X02表示第一年年初参加中级培训的高中毕业生人数；X03表示第一年年初参加高级培训的高中毕业生人数；X12表示第二年年初参加初级培训的高中毕业生人数；X23表示第三年年初参加初级培训的高中毕业生人数；Y01表示第一年年初参加中级培训的初级工人数；Y02表示第一年年初参加高级培训的初级工人数；Y11表示第二年年初参加中级培训的初级工人数；Y12表示第二年年初参加高级培训的初级工人数；Z21表示第三年年初参加中级培训的初级工人数第26页，此课件共53页哦Z01，z02，z03分别表示第一年年初、第二年年初、第三年年初参加高级培训的中级工人数。模型分析：目标：总收益最多每年每个培训班的人数限制第27页，此课件共53页哦第一年三个培训班人数限制第二年三个培训班的人数限制第三年三个培训班的人数限制第28页，此课件共53页哦非负整数限制各年中高级培训的人数限制各年培训费用限制第29页，此课件共53页哦第30页，此课件共53页哦4、食品工程员工培训计划 某工厂生产I、II两种食品，现有50名熟练工人，每名熟练工人每小时可生产食品I 10千克或食品II 6千克。由于需求将不断增长（见下表），该厂计划到第8周末前培训出50名新工人，组织两半生产。已知一名工人每周工作40小时，一名熟练工人用2周可以培训出不多于3名新工人（培训期间熟练工人和培训员工不参加生产）。数量工人每周工资360元，新工人培训期间工资每周120元，培训结束后每周240元，且生产效率同熟练工人。培训过渡期间，工厂将安排部分熟练工人加班，加班1小时另付费12元。又生产食品不能满足订货需求，推迟交货的赔偿费分别为：食品I-0.50元/千克.周，食品II-0.60元/千克.周。工厂应如何全面安排，使各项费用总和最小。食品周12345678I1010121216162020II67.28.410.810.8121212第31页，此课件共53页哦1、问题分析 本题是一个动态员工计划安排，既要满足培训要求，又要尽量满足食品生产计划。关键是熟练工人的安排，影响到新工人的工作安排，影响到食品推迟计划。注意培训新工人培训需要两周，第8周末结束，故开班培训只能1到7周初才合理，食品可以推后，第1周的食品可以推后到第2到8周，第2周的食品可以推迟到第3周到第8周。另外，关于加班，需要灵活处理。按照每周40小时工作，每天工作8小时，不妨设加班8小时（如果建立的模型无解，再增加加班时间）。2、变量设置xi：表示第i周从事食品I的熟练工人数；i=1,2,8;yi：表示第i周从事食品II的熟练工人数；i=1,2,8;zi：表示第i周从事培训新工人的熟练工人数，i=1,2,7;第32页，此课件共53页哦pi：第i周报名参加培训的新工人数，i=1,2,7;ui：第i周参与加工生产食品I的熟练工人数；i=1,2,8;vi：第i周参与加工生产食品II的熟练工人数；i=1,2,8;q1i：第i周参与食品I的新工人数；i=3,4,8;q2i：第i周参与食品II的新工人数；i=3,4,8;rij：本来该第i周交货的食品I，而被推迟到第j周交货的数量，i=1,2,7,j=8,7,1;sij：本来该第i周交货的食品II，而被推迟到第j周交货的数量，i=1,2,7,j=8,7,1;d1i：表示第i周食品I的需求量；d2i：表示第i周食品II的需求量；F ：赔偿总费用第33页，此课件共53页哦3、建立数学模型目标函数：注意，由于熟练工人的工资是常量，故不需要计算在内，只计算培训费、新工人工资、加班费和赔偿费。熟练工人总数约束第34页，此课件共53页哦加班人数约束，只有生产的数量工人可能加班参加培训的熟练工人和被培训的新工人数之间的约束关系,1名熟练工人培训的新工人不超过3人，即新工人分配生产的约束，参加培训两周后参可以参加生产注意到每周工作40小时，可以生产400kg食品I或者240kg食品II，加班8小时可以生产80kg食品I或者48kg食品II，则食品需求的约束为第35页，此课件共53页哦实际生产量=需求量-被推迟的量+推迟到这周的量，关于食品I的约束如下k=3,7第36页，此课件共53页哦关于食品II的约束如下k=3,7第37页，此课件共53页哦关于赔偿总费用的计算变量约束第38页，此课件共53页哦5、生产与存贮问题 某工厂生产并销售某种产品，已知今后四个月市场需求预测如下表。又每个月生产j单位产品的费用为每月库存j单位产品的费用为0.5j（千元），该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存都是零。试指定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求之差。i月 1 2 3 4需求 2 3 2 4第39页，此课件共53页哦6、设备更新问题设置rk(t)：在第k年设备已经使用过t年（役龄为t年），再使用一年时的效益；Uk(t)：在第k年设备役龄为t年，再使用一年的维修费用；Ck(t)：在第k年设备役龄为t年，将设备卖掉，买进一台新设备的更新净费用。某台新设备的年效益、维修费用、更新费用如下表，试确定5年内的更新策略。项目役龄Rk(t)Uk(t)Ck(t)0 1 2 3 4 5 5 4.5 4 3.75 3 2.5 0.5 1 1.5 2 2.5 3 0.5 1.5 2.2 2.5 3 3.5第40页，此课件共53页哦 某厂由于进行技术改造，今后几年内将逐渐减少非技术工人，而增加对半熟练和熟练工人的需求数量。已知现有各类工人数和今后三年内所需的各类工人数，见表1：非技术工人半熟练工人熟练工人现有人数200015001000第1年100014001000第2年50020001500第3年025002000表17、职工分流管理模型、职工分流管理模型第41页，此课件共53页哦 工厂对人员的考虑：一是补充，二是培训，三是下岗，四是充当短工。（1）补充 规定从外面招收的新工人每年限额为非技术工人500人，半熟练工人800人，熟练工人500人。（2）培训 每年允许将200名非技术工人培训成半熟练工人，培训费每人需4000元；将半熟练工人培训为熟练工人，由于培训要在现场进行，所以限定人数不超过同期熟练工人数的1/4，培训费为每人5000元。（3）下岗 对非技术工人下岗后年发给2000元，半熟练或熟练工人发给5000元。（4）超员 全厂范围允许比年需求量超150人。超编人员开支为非技术工人年15000元，半熟练工人年20000元，熟练工人年30000元。（5）充当短工 每类工人中允许各安排不超过50人当短工，当短工的工人开支为非技术工人年5000元，半熟练工人年4000元，熟练工人年4000元。且当短工人员工作效率相当于正常情况下的一半。第42页，此课件共53页哦 又工厂工人均有一定流动性，特别是聘用的第一年流动性很大，超过一年后将大幅度降低。聘用工人中离厂的比例见表2。现有工人均已聘用一年以上。此外工厂还可能对工人降等使用，但降等使用的工人将有50%离厂。非技术工人半熟练工人熟练工人聘用不到一年25%20%10%聘用超过一年10%5%5%表2 要求：（1）若 工 厂 希 望 下 岗 工 人 数 尽 可 能 少，如 何 做 到 这 一 点。（2）若该厂希望支出的费用为最少，则如何安排人员计划。第43页，此课件共53页哦假设假设：工厂的人员变动假设为如下 当年年初某个级别的工人人数+当年补充进来的该级别工人数+上一年进修（培训）回来的人数+上年高一级别的降等的工人数-当年该级别的工人下岗人数-当年该级别的离厂人数-本年该级别去进修（培训）人数-本年度降等的工人数=下年度年初的需求量+超编工人数+短工人数第i年j级别人数第i+1年级别j人数补充离开补充(年初）：招收，进修回来，降等下来离开（当年任何时候）：降等，离厂，下岗，去进修，晋升上去第44页，此课件共53页哦变量设置变量设置：x(i,j)表示第i年第j 种工人聘用人数;y(i,j)表示第i年第j 种工人参加培训的人数;z(i,j)表示第i年第j 种工人的下岗人数;r(i,j,k)表示第i年年末第j 种工人的降等k级的人数;p(i,j)表示第i年第j 种工人的超编人数;q(i,j)表示第i年第j 种工人的短工人数;这里i=1,2,3;j=1,2,3,k=1,2;j=1表示非技术工人，j=2表示半熟练工人，j=3表示熟练工人。数学模型（数学模型（1）为）为第45页，此课件共53页哦第46页，此课件共53页哦第47页，此课件共53页哦第48页，此课件共53页哦第49页，此课件共53页哦利用lingo（整数规划最好利用lingo)求解min=z11+z12+z13+z21+z22+z23+z31+z32+z33;0.75*x11+0.5*r121+0.5*r132-y11-z11-p11-q11=-800;0.9*p11+0.9*q11+0.75*x21+0.5*r221+0.5*r232-y21-z21-p21-p21=-400;0.9*p21+0.9*y21+0.75*x31+0.5*r321+0.5*r332-y31-z31-p31-q31=-450;q11=50;q21=50;q31=50;y11=200;y21=200;y31=200;0.80*x12+0.5*r131-r121-y12-z12-p12-z12=-25;0.95*p12+0.95*q12+0.8*x22+0.5*r231+y11-r221-y22-z22-p22-q22=670;0.95*p22+0.95*q22+0.8*x32+0.5*r331+y21-r321-y32-z32-p32-q32=600;y12=250;y22=250;y32=375;q12=50;q22=50;q32=50;0.9*x13+y12-r131-r132-z13-p13-q13=50;第50页，此课件共53页哦0.95*p13+0.95*q13+0.9*x23+y22-r231-r232-z23-p23-q23=550;0.95*p23+0.95*q23+0.9*x33+y32-r331-r332-z33-p33-q33=575;x11=500;x21=500;x31=500;q13=50;q23=50;q33=50;p11+p12+p13=150;p21+p22+p23=150;p31+p32+p33=150;x13=500;23=500;x33=500;x12=800;x22=800;x32=800;gin(x11);gin(x12);gin(x13);gin(x21);gin(x22);gin(x23);gin(x31);gin(x32);gin(x33);gin(y11);gin(y12);gin(y13);gin(y21);gin(y22);gin(y23);gin(y31);gin(y32);gin(y33);第51页，此课件共53页哦gin(z11);gin(z12);gin(z13);gin(z21);gin(z22);gin(z23);gin(z31);gin(z32);gin(z33);gin(p11);gin(p12);gin(p13);gin(p21);gin(p22);gin(p23);gin(p31);gin(p32);gin(p33);gin(q11);gin(q12);gin(q13);gin(q21);gin(q22);gin(q23);gin(q31);gin(q32);gin(q33);gin(r121);gin(r132);gin(r221);gin(r232);gin(r321);gin(r332);gin(r131);gin(r231);gin(r331);第52页，此课件共53页哦根据计算结果，最小下岗职工人数为848，具体的每年分流计划和引进计划，见计算表。回答：略Objective value:845.0000 Variable Value Reduced Cost Z11 400.0000 1.000000 Z21 80.00000 1.000000 Z31 365.0000 1.000000 Y11 200.0000 0.000000 X12 20.00000 0.000000 Y12 41.00000 0.000000 X22 800.0000 0.000000 Y22 168.0000 0.000000 X32 725.0000 0.000000 Y32 368.0000 0.000000 X13 10.00000 0.000000 X23 470.0000 0.000000 X33 500.0000 0.000000第53页，此课件共53页哦