线性规划应用

1 运筹学 任课教师 徐咏梅博士副教授硕士生导师 txuym OperationsResearch 2 第3章线性规划应用 3 线性规划 在一定的约束条件 限制条件 下 使得某一目标函数取得最大 或最小 值 当规划问题的目标函数与约束条件都是线性函数 便称为线性规划 Linearprogramming LP 4 1 生产计划问题 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 5 1 生产计划问题 问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 人力约束9X1 4X2 360设备约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 6 1 生产计划问题 7 1 生产计划问题 多种产品 8 2 市场营销应用 9 2 市场营销应用 问如何选择各个媒体的使用次数使宣传效果最好约束条件 预算不超过3万美元至少10部电视受众至少5万人 2 市场营销应用 1 确定决策变量 各个媒体的使用次数是多少 2 确定目标函数 maxZ 65X1 90X2 40X3 60X4 20X53 确定约束条件 媒体可用性X1 15 预算1500X1 3000X2 400X3 1000X4 100X5 30000电视X1 X2 10受众1000X1 2000X2 1500X3 2500X4 300X5 50000非负性约束X1 0X2 0X3 0X4 0X5 0 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 000X3 X4 50 000债券X5 0 25 X3 X4 太平洋石油X2 0 6 X1 X2 非负性约束X1 0X2 0X3 0X4 0X5 0 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 300 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单位脂肪 已知两种营养品每斤 AB含量变量 X1X2碳水化合物 蛋白质 脂肪 非负条件 52 32 51 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 混合配方问题 规格 XB1 0 25 XA1 XB1 XC1 XD1 XC1 0 2 XA1 XB1 XC1 XD1 XA2 0 5 XA2 XB2 XC2 XD2 XD2 0 25 XA2 XB2 XC2 XD2 XA3 0 25 XA3 XB3 XD3 XB3 0 25 XA3 XB3 XD3 供应量 需求量 26 5 混合配方问题 销售收入 原料成本 目标函数 27 5 混合配方问题 一般规格汽油的每种石油成分的用量多少 及特殊规格汽油的每种石油成分的用量多少 28 6 人员安排 29 6 人员安排 设第j时段开始上班的人数为Xj j 1 2 6 目标函数 minZ 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 3X6序号2时段上班的人 3元 3X1 3X2序号3时段上班的人 3元 3X2 3X3序号4时段上班的人 4元 4X3 4X4序号5时段上班的人 4元 4X4 4X5序号6时段上班的人 5元 5X5 5X6Minz 6X1 6X2 7X3 8X4 9X5 8X6 32 若工资变了 33 6 人员安排 选讲 探讨1 如何作领导 34 6 人员安排 选讲 探讨2 转换时间 35 6 人员安排 选讲 36 6 人员安排 选讲 hs22 37 6 人员安排 选讲 人力资源分配的问题福安商场是个中型的百货商场 它对售货员的需求经过统计分析如右表 为了保证售货人员充分休息 售货人员每周工作5天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足工作需要 又使配备的售货人员的人数最少 6 人员安排 选讲 人力资源分配的问题福安商场是个中型的百货商场 它对售货员的需求经过统计分析如右表 为了保证售货人员充分休息 售货人员每周工作5天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足工作需要 又使配备的售货人员的人数最少 解 设xi i 1 7 表示星期一至日开始上班的人数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5 x6 x7约束条件 s t x1 x2 x3 x4 x5 28x2 x3 x4 x5 x6 15x3 x4 x5 x6 x7 24x4 x5 x6 x7 x1 25x5 x6 x7 x1 x2 19x6 x7 x1 x2 x3 31x7 x1 x2 x3 x4 28x1 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 2002X3 2X4 X5 X6 3X7 2003X1 X2 2X3 3X5 X6 4x8 200解得 X1 60 X2 20 X4 100Z 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 动态生产计划问题 选讲 P53例16动态生产计划问题对照P108工厂做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只能取各种零部件数量的最小值 即y min cijxij 目标函数 maxz y约束条件 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 排产问题 选讲 作业 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万元用于投资 可选择