3第三章线性规划应用.ppt

1,运 筹 学,任课教师：徐咏梅博士 教授 硕士生导师,Operations Research,2,第3章线性规划应用,3,线性规划,在一定的约束条件（限制条件）下，使得某一目标函数取得最大（或最小）值，当规划问题的目标函数与约束条件都是线性函数，便称为线性规划。Linear programming（LP）,4,1、生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,5,1、生产计划问题,问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20,6,1、生产计划问题,多种产品？,7,1、生产计划问题,8,2、市场营销应用,9,2、市场营销应用,问如何选择各个媒体的使用次数使宣传效果最好 约束条件：预算不超过3万美元 至少10次电视 受众至少5万人,2、市场营销应用,1、确定决策变量：各个媒体的使用次数是多少？2、确定目标函数：maxZ=65X1+90X2+40X3+60X4+20X53、确定约束条件：媒体可用性X115。预算1500X1+3000X2+400X3+1000X4+100X530000 电视 X1+X2 10 受众 1000X1+2000X2+1500X3+2500X4+300X550000 非负性约束 X10 X20 X30 X40 X50思考：电视费用不超过2万美元？,11,2、市场营销应用,问以最小访问成本满足合同要求的家庭时间访问计划是怎样的？访问费用：访问有儿童的家庭需要额外的访问时间 晚间访问费用高 如下表：,12,2、市场营销应用,要求：至少1000次访问 至少访问400个有儿童的家庭 至少访问400个无儿童的家庭 晚间访问的家庭数量必须不少于日间访问的家庭数目 至少40的有儿童家庭必须在晚上访问 至少40的无儿童家庭必须在晚上访问,13,2、市场营销应用,决策变量目标函数约束条件 总数 访问类型（5个）非负约束,14,3、财政应用,15,3、财政应用,10万美元资金，投资方针1、对钢铁和石油，每个行业的投资不得多于50000美元2、对政府债券的投资至少相当于钢铁行业投资的25%3、对于太平洋石油，高收益高风险，投资额不得多于整个石油行业投资的60%,16,3、财政应用,1、确定决策变量：投资方案2、确定目标函数：maxZ=0.073X1+0.103X2+0.064X3+0.075X4+0.045X53、确定约束条件：资金 X1+X2+X3+X4+X5 100,000 行业 X1+X2 50,000 X3+X4 50,000 债券 X5 0.25(X3+X4)太平洋石油 X2 0.6(X1+X2)非负性约束X10 X20 X30 X40 X50,17,4、混合问题,某公司饲养试验用的动物，这些动物的生长对三种营养元素特别敏感，我们分别称它们为营养元素A、B、C。已知这些动物每天至少需要700克营养元素A，30克营养元素B，而营养元素C的需要量刚好是200毫克，不够和过量都是有害的。五种饲料可供选用，各种饲料每千克所含的营养元素及单价如下表。为了避免过多使用某种饲料，规定混合饲料中各种饲料的最高含量分别为50、60、50、70、40千克。要求确定满足动物需要而费用最低的饲料配方。,18,4、混合问题,19,4、混合问题,设抓取饲料1为x1kg;饲料2为x2kg;饲料3为x3kg目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5约束条件营养要求：3x2+2x2+x3+6x4+18x5 700 x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1 50,x2 60,x3 50,x4 70,x5 40非负性要求：x1 0,x2 0,x3 0,x4 0,x5 0,20,学校准备为学生添加营养餐，每个学生每月至少需要补充60单位的碳水化合物，40单位的蛋白质和35单位脂肪.已知两种营养品每斤:A B 含量 变量:X1 X2 碳水化合物,蛋白质,脂肪,非负条件,5 2,3 2,5 1,5、混合问题,21,22,5、混合配方问题,一家化工厂将四种原料A、B、C、D混合调配出三种产品，三种产品的销售价格分别为每公斤9元、8.5元和8元，各种原料A、B、C、D的供应量分别是1000、1000，750和800公斤；单价分别是每公斤5元、6元、4元和4.5元。该厂应如何安排生产才能使获得的利润最大？,23,5、混合配方问题,24,5、混合配方问题,解：令Xij表示用第j种产品中i种原料的数量(公斤)，i=A、B、C、D；j=1，2，3。由于产品3不含有C，故XC3=0，因此，共有11个变量产品1：XA1+XB1+XC1+XD1产品2：XA2+XB2+XC2+XD2产品3：XA3+XB3+XD3原料A：XA1+XA2+XA3 原料B：XB1+XB2+XB3原料C：XC1+XC2原料D：XD1+XD2+XD3,25,5、混合配方问题,规格：XB10.25(XA1+XB1+XC1+XD1)XC10.2(XA1+XB1+XC1+XD1)XA20.5(XA2+XB2+XC2+XD2)XD20.25(XA2+XB2+XC2+XD2)XA30.25(XA3+XB3+XD3)XB30.25(XA3+XB3+XD3)供应量：需求量：,26,5、混合配方问题,销售收入：原料成本：目标函数：,27,5、混合配方问题,一般规格汽油的每种石油成分的用量多少，及特殊规格汽油的每种石油成分的用量多少 P119,28,6、人员安排,29,6、人员安排,设第j时段开始上班的人数为Xj,j=1,2,6,目标函数：min Z=x1+x2+x3+x4+x5+x6约束条件：x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x6+x1 60非负性约束：xj 0,j=1,2,6,30,若每时段的人员工资不同，我们还可建立最小费用模型,31,序号1时段上班的人（3元）：3X1+3 X6序号2时段上班的人（3元）：3X1+3X2序号3时段上班的人（3元）：3X2+3X3序号4时段上班的人（4元）：4X3+4X4序号5时段上班的人（4元）：4X4+4X5序号6时段上班的人（5元）：5X5+5X6Minz=6 X1+6 X2+7 X3+8 X4+9 X5+8 X6,32,若工资变了？,33,6、人员安排（选讲）,探讨1（如何作领导？）,34,6、人员安排（选讲）,探讨2：转换时间,35,6、人员安排（选讲）,36,6、人员安排（选讲）,hs22,37,6、人员安排（选讲）,人力资源分配的问题 福安商场是个中型的百货商场，它对售货员的需求经过统计分析如右表：为了保证售货人员充分休息，售货人员每周工作 5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,6、人员安排（选讲）,人力资源分配的问题福安商场是个中型的百货商场，它对售货员的需求经过统计分析如右表：为了保证售货人员充分休息，售货人员每周工作 5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,解：设 xi(i=1-7)表示星期一至日开始上班的人数,这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5+x6+x7 约束条件：s.t.x1+x2+x3+x4+x5 31 x2+x3+x4+x5+x6 28 x3+x4+x5+x6+x7 28 x4+x5+x6+x7+x1 15 x5+x6+x7+x1+x2 24 x6+x7+x1+x2+x3 25 x7+x1+x2+x3+x4 19 x1,x2,x3,x4,x5,x6,x7 0,6、人员安排（选讲）,40,7、合理下料问题,料长7.4米，截成2.9、2.1、1.5米各200根。如何截取使用原料最省？关键：设变量 对比：如何截取余料最少？（选讲）,41,7、合理下料问题,设每种方案下料根数为X1，X2，X3，X4，X5，X6，X7，X8Obj：MinZ=X1+X2+X3+X4+X5+X6+X7+X8S.T X1+2X2+X4+X6 200 2X3+2X4+X5+X6+3X7 200 3X1+X2+2X3+3X5+X6+4x8 200 解得：X1=60；X2=20；X4=100 Z=180二维下料问题：平面下料问题三维下料问题：运输装配问题,42,8、动态投资问题,某公司有100万元用于投资，可选择的投资项目如下：项目A：从第一年到第四年每年年初都可以投资，并于次年末回收本利110%，规定每年的最低投资额为10万元。项目B：第二年初可以投资，到第五年年末能收回本利的135%，规定投资额不超过20万元。项目C：第三年初可以投资，到第五年末回收本利的125%，规定最低投资额为20万元，最高投资额为40万元。项目D：五年内每年年初都可以投资，年末回收本利的104%。问公司应该如何投资，使第五年末的本利和最大？,43,8、动态投资问题,兹有100万元闲钱，投资方向有四：,第四年,第一年,第二年,第三年,A项目110%,B项目135%,C项目125%,D项目104%,第五年,各年投资什么项目，使第五年末资本总额为最大？,44,8、动态投资问题,45,9、动态生产计划问题（选讲）,动态生产计划问题 工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本要增加ej、库存能力为I、库存单位成本hj，设期初、期末库存为零。求费用最小的生产计划。设第月正常生产xj件，加班生产件yj，存储zj件。则：本期生产+上期库存-本期库存=本期需求,46,10、配套生产问题（选讲）,P53例17 配套生产问题 某工厂有m个车间，生产一种由n种不同部件组成的产品，每个车间均可生产这n种部件。已知车间i的工时限制为bi（小时），生产第j种部件的生产率为Cij（件/小时）。问各车间应如何分配工时，才能使产品的件数最多？试建立这个问题的优化模型。设Xij为车间i分配给第j种部件的工时数，为产品的产量,47,10、配套生产问题（选讲）,解：设i车间产j部件xij小时，y为产品产量j部件数量：cijxij 产品数y只能取各种零部件数量的最小值，即ymin cijxij 目标函数：maxzy约束条件：cijxij y，cijxij bi，xij，y 0,i=1,m,j,i=1,m,i=1,m,i=1,m,48,11、排产问题（选讲）,某厂生产、，每种产品要经过A、B两道工序加工，A工序可以在A1、A2设备上完成；B工序可以在B1、B2、B3上完成。产品可在A、B任何设备上加工；产品可在任何A上完成，但是只能在B1上完成B工序；产品只能在A2上完成A工序、B2上完成B工序，各种生产参数见表所示。如何规划，使该厂利润最大？,49,11、排产问题（选讲）,50,作 业,P57-59 13，14，15（5辆），16（选做，简单），17，18，20（选做，难），21（选做，难）所有保留小数，不要取整书后答案一半是错的，不要看答案,作业,1.某一企业家需要找人清理5间会议室、12张桌子和18个货架。今有两个临时工A和B供企业家雇佣。A一天可清理1间会议室、3张桌子和3个货架；而B一天可清理1间会议室、2张桌子和6个货架，A的工资每天25元，B的工资每天22元。为使成本最低，应雇佣A和B各多少天？（用线性规划图解法求解，保留小数）,2.某公司生产甲和乙两种产品，它们的单位利润分别是300元和200元。该公司有两个机械加工中心，它们每天工作的有效时间都是20小时。每种产品都需要经过两个中心加工，生产每单位产品甲在加工中心1需要1小时，在中心2需要3小时。生产每单位产品乙在中心1和中心2各需2小时和1小时。根据市场调查知产品甲每天的需求量不会超过5单位，而产品乙无论生产多少均能销售完。问公司应如何安排生产才能获利最大？试建立问题的线性规划模型，并用图解法求解（保留小数）。,3.一家化工厂将四种原料A、B、C、D混合调配出三种产品，三种产品的销售价格分别为每公斤9元、8.5元和8元，各种原料A、B、C、D的供应量分别是1000、1000，750和800公斤；单价分别是每公斤5元、6元、4元和4.5元。该厂应如何安排生产才能使获得的利润最大？,4.若例题中，医院付给护士的工资为6点至18点每小时3元，18点至23点每小时4元，23点至6点每小时5元。并要求2点开始上班的人数不得超过4人，求最优安排计划。,5.某养殖场厂共饲养万只火鸡，用豆粕和谷糠的混合饲料喂养。已知每只火鸡每天至少吃混合饲料1公斤，每只火鸡每天至少需要0.25公斤蛋白质和0.02公斤钙。豆粕含36蛋白质和0.37%的钙，购价5元/公斤；谷糠含10%蛋白质和2.5%的钙，购价2元/公斤。问怎样搭配饲料，才能使饲养成本最低？,6.某建筑工地有一批长为10m的钢筋（型号相同），现要截成长度为3m的钢筋90根，长度为4m的钢筋60根。问如何下料才能使所有的原材料最省？,7.某厂有一批长度为8.5m的钢管原材料(数量充分多)，今为制造零件要将它们截成长度为3.5m，2.0m，1.5m的管料，需要量都是200根，问应如何下料，使用的原材料最少？,8.某公司有900万元用于投资，可选择的投资项目如下：项目A：从第一年到第五年每年年初都可以投资，并于次年末回收本利108%，规定每年的最低投资额为150万元。项目B：第二年初可以投资，到第六年年末能收回本利120%，规定投资额不超过200万元。（仅第二年可投资）项目C：第三年初可以投资，到第六年末回收本利116%，规定最低投资额为200万元，最高投资额为300万元。项目D：六年内每年初都可以投资，年末回收本利103%。问公司应该如何投资，使第六年末的本利和最大？,9.有A、B两种产品，都需要经过前后两道化学反应过程。每一单位的A需要前道过程2小时和后道过程3小时。每一单位B产品需要前道过程3小时和后道过程4小时。可供利用的前道过程有200小时，后道过程时间有240小时。每生产一个单位的B产品的同时，会产生两个单位的副产品C，且不需要外加任何费用，副产品C最多可售出10个单位，其余只能加以销毁，每个单位的销毁费用是1元。出售A产品每单位可获利5元，B产品每单位可获利10元，出售C产品每单位可获利3元。为了使获得的总利润达到最大，试建立这个问题的线性规划模型。,