15.093J 期中考试 2001.11.6 1考试时间2小时. 2考试结来后试卷和答案一并交上来。 3.可参考教材、课堂笔记、作业及蓉案。 4.祝你好运1 问题1(30分)】 假设我们负责一个生产四类产品的工厂的生产计划。生产每类产品消耗原料的量是有限制 的。通过求解形知maxm心C、:A,≤6，x20的线性规划问题计算最优生产量。求得下表 所示的解和灵敏度信息（注意一些空教覆盖了）。 最终值 缩诚费用 目标系数 允许增量 允许减诚量 名移 产品 12 .9 0 ) 产品2 27 ) 6 无穷 5 产品3 0 0 12 8 4 产品4 0 7 6 7 无穷 最终值 影子价格 的束 允许增量 允许减量 名称 名称 R.H.S 产品1 资源1 200 14 100 50 50 产品2 资源2 200 ) 300 ) U) 产品B 资源3 100 75 100 80 90 产品4 表1变量和钓束条作 回答下面的月题并知以解释
15.093J 期中考试 2001.11.6 1.考试时间 2 小时。 2.考试结束后试卷和答案一并交上来。 3.可参考教材、课堂笔记、作业及答案。 4.祝你好运！ 问题 1（30 分） 假设我们负责一个生产四类产品的工厂的生产计划。生产每类产品消耗原料的量是有限制 的。通过求解形如 maximize ' x : C Ax ≤ b，x ≥ 0 的线性规划问题计算最优生产量，求得下表 所示的解和灵敏度信息（注意一些空被覆盖了）。 名称 最终值 缩减费用 目标系数 允许增量 允许减量 产品 1 0 -9 12 ( f ) ( ) f 产品 2 27 ( ) f 6 无穷 5 产品 t3 0 0 12 8 4 产品 4 0 -7 6 7 无穷 名称 名称 最终值 影子价格 约束 R.H.S 允许增量 允许减量 产品 1 资源 1 200 14 100 50 50 产品 2 资源 2 200 ( f ) 300 ( ) f ( f ) 产品 t3 资源 3 100 75 100 80 90 产品 4 表 1 变量和约束条件 回答下面的问题并加以解释。 0
)如果可以再购买10单位的原料3，花费$700。利是否采纳这个建议： b)闻果再购买100单位的原料3，共需5000元，是否采纳这个建议？ ()在产品3的贵用系数允许的变化范围内，产品3的最大和最小产量是什么？ (d生产产品4的最小日标系数是什么？ ()如果不增加任何费用的情况下，可以增加任何一种原料10单位，应该选择爆种原料？ (0在标记U)的空白处填上正确的值。 (g柳是递化的吗？ 问题2(30分) 考虑在T阶段内生产一种产品。如果在1时段开始生产，则建设费用为C 前面阶段多生产的产品储存以调足后面阶段的需求，而最后后面阶段时，前面所有的必须都 己经满足。1=LK,T,令d为阶段的产品雷求，P,H分别为每阶段的生产费用和库 存费用。 ()构造一个整数规划门题，使总的生产、库存和建设费用最小， b)假设除阶段T外都有需求损失，每搬失一个单位消耗的费用为B,如何建立这个问题的 核型？ ()限设最多可以在5个阶段开始生产，每两次生产不能连线。说明如何建立模型解决这个 问题
(a)如果可以再购买 10 单位的原料 3，花费$700。问是否采纳这个建议？ (b)如果再购买 100 单位的原料 3，共需$8000 元，是否采纳这个建议？ (c)在产品 3 的费用系数允许的变化范围内，产品 3 的最大和最小产量是什么？ (d)生产产品 4 的最小目标系数是什么？ (e)如果不增加任何费用的情况下，可以增加任何一种原料 10 单位，应该选择哪种原料？ (f)在标记( f )的空白处填上正确的值。 (g)解是退化的吗？ 问题 2（30 分） 考虑在T 阶段内生产一种产品。如果在t 时段开始生产，则建设费用为Cj 前面阶段多生产的产品储存以满足后面阶段的需求，而最后后面阶段时，前面所有的必须都 已经满足。 ，令 为t 阶段的产品需求， 、 分别为每阶段的生产费用和库 存费用。 t = 1,Κ ,T i d Pi Hi (a)构造一个整数规划问题，使总的生产、库存和建设费用最小。 (b)假设除阶段T 外都有需求损失，每损失一个单位消耗的费用为 ，如何建立这个问题的 模型？ i b (c)假设最多可以在 5 个阶段开始生产，每两次生产不能连续。说明如何建立模型解决这个 问题。 1
问题3(30分) 用单纯形法求解标准线性规划问题时得到下面单纯形表： X X:X:X Xs 00 C30 C5 = 0110 B X. 0 022y = 040 6 3 设矩阵最后三列形成一个单位矩阵。 )哈出表中基为最优基的充分必要条件（用表中的系数项） b假设此时基为最优。且G一0找出出表中所示外的一个最优基可行解。 (e)设720，正明：不考虑G和G的值。存在最优基本可行解。 (d假设表中有最优基，原始问题中的点棱A+8取代，求使最优基不变的日的范用. ()限设表中有最优基，原间愿的G按G+8取代，求使最优基不变的8的意围. 同题4(10分) United Airlines有因架琉机从芝加哥飞往波十镜，分别为：10am,12am2pm,4pm。前两架容 量为1O0人，后两架分别能容纳150人。知果过量订票导致不能按时乘坐，United Airlines 会将乘客转移到下一班，并暗偿每位乘客200和每个小时s20。 如果乘客核推迟到4pm以后，那么United Airlines会将乘客安排到8pm的另一架航班，不需 要多循纳费用，这个航班青定能容钠所有人。例如，如果一位乘客应该2印m起飞，结果被 安排到了8即m的航班，他会得到5200+6×20320的赠偿。假设某一天开始这四架航班已 确定的订票数分别为：110,160.100和140。说明如何建立最小费用流问题得到最经济的 安排乘客的策略
问题 3（30 分） 用单纯形法求解标准线性规划问题时得到下面单纯形表： x1 x2 x3 x4 x5 0 0 c 0 3 − c5 − 1 0 1 -1 0 β 2 0 0 2 2 γ x =2 x =4 x =1 3 1 0 4 0 δ 设矩阵最后三列形成一个单位矩阵。 (a)给出表中基为最优基的充分必要条件（用表中的系数项） (b)假设此时基为最优，且 3 c = 0 找出出表中所示外的一个最优基可行解。 (c)设γ ≥ 0 ，证明：不考虑 3 c 和 5 c 的值，存在最优基本可行解。 (d)假设表中有最优基，原始问题中的b1被 1 b +θ 取代，求使最优基不变的θ 的范围。 (e)假设表中有最优基，原问题的c1被 1 c +θ 取代，求使最优基不变的θ 的范围。 问题 4（10 分） United Airlines 有四架班机从芝加哥飞往波士顿，分别为：10am,12am,2pm,4pm。前两架容 量为 100 人，后两架分别能容纳 150 人。如果过量订票导致不能按时乘坐，United Airlines 会将乘客转移到下一班，并赔偿每位乘客$200 和每个小时$20。 如果乘客被推迟到 4pm 以后,那么 United Airlines 会将乘客安排到 8pm 的另一架航班，不需 要多缴纳费用，这个航班肯定能容纳所有人。例如，如果一位乘客应该 2pm 起飞，结果被 安排到了 8pm 的航班，他会得到$200+6×20=$320 的赔偿。假设某一天开始这四架航班已 确定的订票数分别为：110，160，100 和 140。说明如何建立最小费用流问题得到最经济的 安排乘客的策略。 2