第四章运筹应用.ppt

第四章线性规划问题的应用 一 人力资源分配的问题例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 解 设xi表示第i班次时开始上班的司机和乘务人员数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5 x6约束条件 s t x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0 50 20 50 0 20 10 例2 福安商场是个中型的百货商场 它对售货员的需求经过统计分析如右表 为了保证售货人员充分休息 售货人员每周工作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 12 0 11 5 0 8 0 二 生产计划的问题例3 明兴公司生产甲 乙 丙三种产品 都需要经过铸造 机加工和装配三个车间 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如右表 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和由外包协作各应多少件 解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外协铸造再由本公司机加工和装配的甲 乙两种产品的件数 求xi的利润 利润 售价 各成本之和可得到xi i 1 2 3 4 5 的利润分别为15 10 7 13 9元 这样我们建立如下的数学模型 目标函数 Max15x1 10 x2 7x3 13x4 9x5约束条件 s t 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 1600 0 0 0 29400 三 套裁下料问题例4 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 解 设计下列5种下料方案 设x1 x2 x3 x4 x5分别为上面前5种方案下料的原材料根数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5约束条件 s t x1 2x2 x4 1002x3 2x4 x5 1003x1 x2 2x3 3x5 100 x1 x2 x3 x4 x5 0 30 10 0 50 0 四 任务安排 解设流水线Ai加工产品Bj的件数为Xij i 1 2 3 j 1 2 3 4 Minz 2 7 x11 1 7 x12 3 7 x13 2 9 x34S tx11 x21 x31 200 x12 x22 x32 150 x13 x23 x33 250X14 x24 x34 3002x11 x12 3x13 2x14 15003x21 2x22 4x23 4x24 1800X31 2x32 x33 2x34 2000Xij 0 例5 有四种产品 可用三条流水线生产 每条流水线加工每件产品所需的工时和产品的需求量如下表 三条流水线的生产成本分别为每小时7 8和9元 如何安排生产 使总成本最少 五 市场销售 例6 广告方式的选择 某公司的一个月的广告预算20000元 要求 一个月内至少有8个电视商业节目 15条报纸广告 且整个电视广告费不超过12000元 电台广播至少隔日有一次 问如何安排 才能取得最佳效果 解 设x1 x2 x3 x4 x5分别是一个月内电视台A 电视台B 每日晨报 星期日报和广播电台宣传的次数 则所求问题 Max50 x1 80 x2 30 x3 40 x4 15x5s t500 x1 1000 x2 100 x3 300 x4 80 x5 20000 x1 x2 8x3 x4 15500 x1 1000 x2 12000 x1 16 x2 10 x3 24 x4 4 x5 25x1 x2 x3 x4 x5 0 六 配料问题例7 某工厂要用三种原料1 2 3混合调配出三种不同规格的产品甲 乙 丙 数据如右表 问 该厂应如何安排生产 使利润收入为最大 解 设xij表示第i种 甲 乙 丙 产品中原料j的含量 这样我们建立数学模型时 要考虑 对于甲 x11 x12 x13 对于乙 x21 x22 x23 对于丙 x31 x32 x33 对于原料1 x11 x21 x31 对于原料2 x12 x22 x32 对于原料3 x13 x23 x33 目标函数 利润最大 利润 收入 原料支出约束条件 规格要求4个 供应量限制3个 目标函数 Maxz 50 x11 x12 x13 35 x21 x22 x23 25 x31 x32 x33 65 x11 x21 x31 25 x12 x22 x32 35 x13 x23 x33 约束条件 s t x11 0 5 x11 x12 x13 原材料1不少于50 x12 0 25 x11 x12 x13 原材料2不超过25 x21 0 25 x21 x22 x23 原材料1不少于25 x22 0 5 x21 x22 x23 原材料2不超过50 x11 x21 x31 100 供应量限制 x12 x22 x32 100 供应量限制 x13 x23 x33 60 供应量限制 xij 0 i 1 2 3 j 1 2 3 maxz 15x11 25x12 15x13 30 x21 10 x22 40 x31 10 x33S t0 5x11 0 5x12 0 5x13 0 原材料1不少于50 0 25x11 0 75x12 0 25x13 0 原材料2不超过25 0 75x21 0 25x22 0 25x23 0 原材料1不少于25 0 5x21 0 5x22 0 5x23 0 原材料2不超过50 x11 x21 x31 100 供应量限制 x12 x22 x32 100 供应量限制 x13 x23 x33 60 供应量限制 xij 0 i 1 2 3 j 1 2 3 x11 100 x12 50 x13 50 其余皆为0 七 投资问题 P171 例8 某公司拥有的100万元可以有5个选择进行投资 在已知其年利润率的情况下 需要满足以下要求 1 电力公司的投资至少要等于化学工业投资的两倍 但每种投资都不得超过投资总额的50 2 购买国库券至少应占整个工业投资的10 3 对光明化工公司的投资最多只能占化学工业投资的65 解 设给第i个项目投资xi万元 Maxz 0 062x1 0 071x2 0 098x3 0 072x4 0 047x5s tx1 x2 2x3 2x4 0 x1 x2 50 x3 x4 50 0 1x1 0 1x2 0 1x3 0 1x4 x5 00 35x3 0 65x4 0 xi 0 例9 某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目D 需在第二年年初投资 第五年末能收回本利155 但规定最大投资额不能超过100万元 据测定每万元每次投资的风险指数如右表 问 a 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 b 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小 解 1 确定决策变量 连续投资问题设xij i 1 5 j 1 2 3 4 表示第i年初投资于A j 1 B j 2 C j 3 D j 4 项目的金额 这样我们建立如下的决策变量 Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24 2 约束条件 第一年 A当年末可收回投资 故第一年年初应把全部资金投出去 于是x11 x12 200 第二年 B次年末才可收回投资 故第二年年初的资金为x11 于是x21 x22 x24 1 1x11 第三年 年初的资金为x21 x12 于是x31 x32 x33 1 1x21 1 25x12 第四年 年初的资金为x31 x22 于是x41 x42 1 1x31 1 25x22 第五年 年初的资金为x41 x32 于是x51 1 1x41 1 25x32 B C D的投资限制 xi2 30 I 1 2 3 4 x33 80 x24 1003 目标函数及模型 a Maxz 1 1x51 1 25x42 1 4x33 1 55x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 xi2 30 I 1 2 3 4 x33 80 x24 100 xij 0 i 1 2 3 4 5 j 1 2 3 4 b Minf x11 x21 x31 x41 x51 3 x12 x22