
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