线性规划应用.ppt

线性规划应用模型 例1 生产计划问题 统计资料 某车间在每个生产期5天所需要的某种刀具 每一把刀具的成本为0 5元 用过的刀具送到机修车间研磨 每把刀具需花费0 20元 刀具每天用过之后 如果立即送去磨 两天后可以磨好送回 供当天的需用 第5天后 刀具应全部换新 每期开始时 该车间没有任何刀具 问这个车间需要多少刀具才能应付需要 而成本又最低 试建立其线性规划模型 1 决策变量 问题要确定的是每期5天需要新刀具的总数 等价于要确定每天所需用的新刀具数 考虑到刀具用过后 可送去研磨 两天后送回供第3天使用 设决策变量xi i 1 2 3 4 5 为第i天使用的新刀具 yj j 1 2 3 为第j天送去研磨的刀具数 解题分析 2 确定目标函数 由于刀具所花费的成本是由两部分组成 新刀具总的成本0 5 x1 x2 x3 x4 x5 送去研磨的刀具总的费用0 2 y1 y2 y3 因此 目标函数所要求的成本最低 minz 0 5 x1 x2 x3 x4 x5 0 2 y1 y2 y3 3 确定约束条件 由于送去研磨的刀具第3天才能使用 所以第1 2天所使用的只能是新刀具 即x1 120 x2 85从第3天起 每天使用的刀具可以是新的 也可以是磨好后送来回的 所以有 x3 y1 160 x4 y2 145 x5 y3 300 约束条件 在每期的头3天送去研磨的刀具数应满足 y1 120y2 85 120 y1 y3 160 120 y1 85 y2 每天使用新刀具xi和送去研磨的刀具数yj都是非负的整数 即 xi 0 yj 0 且均为整数 生产计划问题的数学模型 minz 0 6 x1 x2 x3 x4 x5 0 2 y1 y2 y3 例2 合理下料问题 某工厂生产某一种型号的机床 每台机床上需2 9m 2 1m 1 5m的轴 分别为1根 2根 1根 这些轴需要用同一种圆钢制作 圆钢的长度为7 4m 如果要生产100台机床 问应如何安排下料 才能用料最省 试建立其线性规划模型 解题分析 对于每一根7 4m长的钢材 可以若干种下料方式把它截取成我们所需要的轴 比如要在7 4m长的钢材上截取2根2 9m的轴和1根1 5m的轴 合计用料2 9 2 1 5 7 3m 残料则为0 1m 现把所有可能的下料方式列于下表中 下料方式 100200100 0041 4 0301 1 0130 8 0220 2 1110 9 1200 3 1030 2010 1 2 9m2 1m1 5m残料 需要量 B8 B7 B6 B5 B4 B3 B2 B1 1 确定决策变量 问题所要确定的是每种下料方式应各用多少根7 4m的圆钢 设x1 x2 x3 x4 x5 x6 x7 x8分别为按B1 B2 B3 B4 B5 B6 B7 B8方式下料的圆钢根数 2 确定目标函数 目标是使总的下料根数最少 即minz x1 x2 x3 x4 x5 x6 x7 x8 3 确定约束条件 由于每台机床所需不同长度的轴的根数是确定的 因此生产100台机床所需2 9m的轴100根 2 1m轴200根 1 5m的轴100根 如果按B1的方式下料 每根圆钢可截取2 9m长的轴2根 则x1根圆钢可截取2 9m长的轴2x1根 按B2 B3 B4方式下料 可在x2 x3 x4根圆钢上分别截取2 9m长的轴x2 x3 x4根 轴的总数约束 因此 所截下的2 9m长的轴的总数不少于100根 即满足约束条 2x1 x2 x3 x4 100所截下的2 1m长的轴的总数满足约束条件2x3 x4 2x5 x6 3x7 200所截下的1 5m长的轴的总数满足约束条件x1 3x2 x4 2x5 3x6 4x8 100 问题的数学模型 圆钢根数要求 按每种下料方式的圆钢根数应满足非负要求 且为整数 即x1 x2 x3 x4 x5 x6 x7 x8 0且为整数 例3 连续投资问题 某公司有20万元资金全部用于投资 投资方案有五种 每种方案的投资额不限 问 公司如何投资才能使到第五年末收回的资金最多 试建立其线性规划模型 方案 A 五年内每年都可投资 在年初投资1元 两年后可收回1 2元B 五年内每年都可投资 每年投1元 3年后可收回1 4元C 只在第一年初有一次投资机会 每投资1元 4年后可收回1 4元D 只在第二年初有一次投资机会 每投资1元 4年后可收回1 7元E 只在第四年初有一次投资机会 每投资1元 1年后可收回1 4元另外 每年年初若将1元资金存入银行 年末可收回1 07元投资所得收益及银行利息也可以用于投资 1 确定决策变量 设Aj j 1 2 3 4 表示第j年初按A种方案的投资金额 设Bj Cj Dj Ej分别表示第j年初按方案B C D E的投资金额 设Fj表示第j年初存入银行的金额 解题分析 2 确定目标函数 第1年初应将20万元资金全部用于投资 以后各年 每后初应将前一年末所得投资收益及银行利益全部用于投资 且各项投资在第五年末应全部收回 根据各方案投资规则 可交各年的投资及收益情况归纳如下表 表中第6栏表示第5年末 即第6年初 所得的各项投资收益 目标函数为maxz 1 7D2 1 4B3 1 2A4 1 07F5 1 2A4 1 4E4 1 07F4 A4 E4 F4 1 4B3 1 2A3 1 07F3 A3 B3 F3 1 7D2 1 4B2 1 2A2 1 07F2 A2 B2 D2 F2 1 4C1 1 4B1 1 2A1 1 07F1 A1 B1 C1 F1 6 5 4 3 2 1 年份 1 07F5 F5 3 确定约束条件 第一年初的投资总额为20万元 即A1 B1 C1 F1 200 000第2 3 4 5年各年满足 各年初投资金额总数 本年初 上年末 收回金额数 A2 B2 D2 F2 1 07F1A3 B3 F3 1 2A1 1 07F2A4 E4 1 4B1 1 2A2 1 07F3F5 1 4C1 1 4B2 1 2A3 1 4E4注意到第4年中投资方案E4较方案F4收益高 投资期限相同 所以投资方案F4可以不采用 各年投资金额均非负 Aj Bj Cj Dj Ej Fj 0 j 1 2 3 4 5 1 2A4 1 4E4 1 07F4 A4 E4 F4 1 4B3 1 2A3 1 07F3 A3 B3 F3 1 7D2 1 4B2 1 2A2 1 07F2 A2 B2 D2 F2 1 4C1 1 4B1 1 2A1 1 07F1 A1 B1 C1 F1 6 5 4 3 2 1 年份 1 07F5 F5 A2 B2 D2 F2 1 07F1 A3 B3 F3 1 2A1 1 07F2 Aj Bj Cj Dj Ej Fj 0 j 1 2 3 4 5 A1 B1 C1 F1 200 000 A4 E4 1 4B1 1 2A2 1 07F3 F5 1 4C1 1 4B2 1 2A3 1 4E4 例4 载货问题 有一艘货轮 分前 中 后三个舱位 它们的容积与最大允许载货量如下表所示 现有三种货物待运 已知有关数据列于下表 又为了航运安全 要求前 中 后舱实际载重量上大体保持各舱最大允许载重量的比例关系 具体要求前 后舱分别与中舱之间载重量比例上偏差不超过15 前后舱之间不超过10 问该货轮应装载A B C各多少件 运货收入为最大 试建立这个问题的线性规划模型 1 确定决策变量 因为A B C三种商品在货轮的前 中 后舱均可装载 令i 1 2 3分别代表商品A B C j 1 2 3分别代表前 中 后舱 决策变量xij为装于j舱位的第i种商品的数量 件 解题分析 2 确定目标函数 商品A的件数为x11 x12 x13 即装于前 中 后舱的商品A的件数之和 商品B的件数为x21 x22 x23商品C的件数为x31 x32 x33为使运费总收入为最大 目标函数为maxz 1000 x11 x12 x13 700 x21 x22 x23 600 x31 x32 x33 3 确定约束条件 前 中 后舱位载重限制为 前 中 后舱位体积限制 A B C三种商品数量限制为 约束条件 xij 0 i 1 2 3 j 1 2 3 问题的线性规划模型 舱体平衡条件 根据各舱实际载重大体应保持各舱最大允许载重量的比例关系 且前 后舱分别与中舱之间载重量比例上偏差不超过15 前 后舱之间不超过10 可得舱体平衡条件为 例5 求a g的值 表中给出的解是否为最优解 例6 求a g的值 表中给出的解是否为最优解 例7 求最小值的初