运筹学离线作业答案

1、浙江大学远程教育运筹学课程作业 姓名： 学 号： 年级： 学习中心： 第2章 1某公司计划生产两种产品，已知生产单位产品所需的三种原材料的消耗及所获的利润，如下表所示。问应如何安排生产使该工厂获利最多？（建立模型， A B 2Y=24 10 产品1 产品2 可用的材料数 原材料A 原材料B 原材料C 1 3 0 2 2 2 30 60 24 单位产品获利 40万元 50万元 并用图解法求解） 答： 模型：线性规划 1）决策变量：产品1和产品2的产量。 设：X为产品1的产量；Y为产品2的产量。 X、Y为本问题的决策变量。 2）目标函数：获利最多。 由于产品1和产品2单位获利分别为40万元和50万

2、元，其产量分别为X和Y，则总获利可计算如下： 总获利=40X+50Y 3）约束条件：四个。材料A、B、C及产量非负约束。 则可得线性规划模型： O.B. Max 40X+50Y S.T. X +2Y33X+2Y60 2Y24 X,Y0 图解： y 30 25 40x+50y=1000 20 3X+2Y=60 40x+50y=800 15 C X+2Y=30 5 O D x 5 10 15 20 25 30 在坐标中绘制对约束条件相应的直线，得到满足条件的区域，即位于第一象限的凸多边形OABCD（包括边界）为满足所有约束条件的解的集合。 由图可见，可行域内离原点最远点为C，则：x+2y=30 3

3、x+2y=60 解得：x=15;y=7.5 即产品1和产品2的产量分别为15和7.5，则获最大利润15*40+7.5*50=975（万元） 2某公司计划生产两种产品，已知生产单位产品所需的两种原材料的消耗和人员需要及所获的利润，如下表所示。问应如何安排生产使该工厂获利最多？ 产品1 产品2 可用的材料数 原材料A 原材料B 人时 1 0 3 0 2 2 4 12 24 单位产品获利 300万元 500万元 （建立模型，并用图解法求解） 答： 线性规划模型：设产品1、2的产量分别为x、y，则有： O.B. Max 300x+500y S.T. x4 2y12 3X+2y24 x,y0 图解： y

4、 13 12 11 3x+2y=24 10 9 8 x=4 7 6 A B 2y=12 5 4 300x+500y=4200 3 2 1 O C x 1 2 3 4 5 6 7 8 9 10 11 在坐标中绘制对约束条件相应的直线，得到满足条件的区域，即位于第一象限的矩形OABC（包括边界）为满足所有约束条件的解的集合。 可行域内最远离原点的点为B,则: x=4 2y=12 3x+2y=24 解得：x=4;y=6 即产品1和产品2的产量分别为4和6时，工厂获得最大利润4*300+6*500=4200（万元） 3. 下表是一个线性规划模型的敏感性报告，根据其结果，回答下列问题： 1）是否愿意付出

5、11元的加班费，让工人加班； 2）如果工人的劳动时间变为402小时，日利润怎样变化？ 3）如果第二种家具的单位利润增加5元，生产计划如何变化？ Microsoft Excel 9.0 敏感性报告 工作表 ex2-6.xlsSheet1 报告的建立: 2001-8-6 11:04:02 可变单元格 终 递减 目标式 允许的 允许的 单元格 名字 值 成本 系数 增量 减量 $B$15 日产量 （件） 100 20 60 1E+30 20 $C$15 日产量 （件） 80 0 20 10 2.5 $D$15 日产量 （件） 40 0 40 20 5.0 $E$15 日产量 （件） 0 -2.0 3

6、0 2.0 1E+30 约束 终 阴影 约束 允许的 允许的 单元格 名字 值 价格 限制值 增量 减量 $G$6 劳动时间 （小时/件） 400 8 400 25 100 $G$7 木材 （单位/件） 600 4 600 200 50 $G$8 玻璃 （单位/件） 800 0 1000 1E+30 200 答： 1）由以上敏感性报告可知，劳动时间的影子价格为8元，在劳动时间的增量不超过25小时的条件下，每增加1小时的劳动时间，该厂的利润（目标值）将增加8元，因此，付给工人11元以增加1小时劳动时间是不值得的，将亏损11-8=3（元）。 2）劳动时间变为402小时，该增加量在允许的增量（25小

7、时）内，所以劳动时间的影子价格不变，仍为8元，因此，该厂的日利润变为：60+20+40+30+8*（402-400）=166（元），比原来增加16元利润。 3）第二种产品增加利润5元，在允许的增量（10元）内，此时最优解不变，因此，生产计划无需变化。 4某公司计划生产两种产品，已知生产单位产品所需的三种原材料的消耗及所获的利润，如下表所示。问应如何安排生产使该工厂获利最多？（建立模型，并用 产品1 产品2 可用的材料数 原材料A 原材料B 原材料C 0.6 0.4 0 0.5 0.1 0.4 12000 4000 6000 单位产品获利 25元 10元 图解法求解）（20分） 答： 线性规划模

8、型： O.B. Max 25x+10y S.T. 0.6x+0.5y12000 0.4x+0.1y4000 0.4y6000 x,y0 图解： y 40000 0.4x+0.1y=4000 30000 25x+10y=300000 20000 A B 0.4y=6000 10000 0.6x+0.5y=12000 C O 5000 10000 15000 20000 x 在坐标中绘制对约束条件相应的直线，得到满足条件的区域，即位于第一象限的梯形OABC（包括边界）为满足所有约束条件的解的集合。 可行域内最远离原点的点为B，则: 0.4y=6000 0.4x+0.1y=4000 解得：x=625

9、0；y=15000 即产品1和产品2产量为6250和15000时，工厂获最大利润25*6250+10*15000=306250元 5. 线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。 6. 在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明如果在该空格中增加一个运量，运费将 增加4 。 7.“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错 第3章 1一公司开发出一种新产品，希望通过广告推向市场。它准备用电视、报刊两种广告形式。这两种广告的情况见下表。要求至少30万人看到广告，要求电视广告数不少于8个，至少16万人看到电视广

10、告。应如何选择广告组合，使媒体 可达消费者数 单位广告成本 媒体可提供的广告数 电视 2.3 1500 15 报刊 1.5 450 25 总费用最小（建立好模型即可，不用求解）。 答： 目标：总费用最小，设：电视、报刊投放数分别为x、y 线性模型： O.B. min 1500x+450y S.T. 15x8 2.3x160000 2.3x+1.5y300000 25y0 2医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计： 序号 时段 最少人数 1 0610 60 2 1014 70 3 1418 60 4 1822 50 5 2202 20 6 0206 30 应如何

11、安排值班，使护士需要量最小。 答： 目标：护士人数最小 因：每次值班8小时，因此，每班次必跨两个时段，用决策变量Xij表示跨i和j两个时段值班的护士人数，则有： O.B. min X12+X23+X34+X45+X56+X61 S.T. X12+X23X23+X3460 X34+X4550 X45+X5620 X56+X6130 X61+ X1260 第4章 1对例4.5.1,如果三个工厂的供应量分别是:150,200,80, 两个用户的需求量不变.请重新建立模型,不需要求解. 答： 工厂供应量发生量变，则虚节点产生量变。 虚节点的净流出量= （150+200+80-300-160）=30（吨

12、），此时为供应虚节点。所以是供需不平衡的运输最小费用流问题。辅助图示如下 A工厂1 D仓库1 F用户1 B工厂2 C工厂3 E仓库2 G用户2 设两个节点间运输量分别为：AD,AE,BD,BE,CD,CE,DF,DG,EF,EG，则可建立模型： O.B. min 3AD+AE+BD+BE+CD+0.5CE+6DF+DG+2EF+7EG S.T. AD+AE=150 BD+BE=200 CD+CE=80 DF+DG300 EF+EG160 AD,AE,BD,BE,CD,CE,DF,DG,EF,EG0 第5章 1考虑4个新产品开发方案A、B、C、D，由于资金有限，不可能都开发。要求A与B至少开发一

13、个，C与D中至少开发一个，总的开发个数不超过三个，方案 开发成本 利润 A 12 50 B 8 46 C 19 67 D 15 61 预算经费是30万，如何选择开发方案，使企业利润最大（建立模型即可）。 答： 目标：企业利润最大 设ABCD四种新产品开发个数分别为：X1X2X3X4，则有 O.B. max 50X1+46X2+67X3+61X4 S.T. X1+X21 X3+X41 X1+X2+X3+X43 12X1+8X2+19X3+15X430 第9章 1某厂考虑生产甲、乙两种产品，根据过去市场需求统计如下： 方案 自然状态 概率 0.3 0.2 正常 0.5 甲 乙 8 10 3 2 6

14、 7 分别用乐观主义、悲观主义和最大期望值原则进行决策，应该选择哪种产品？ 答： 乐观主义：在最乐观的自然状态下具有最大效益值的方案为最佳方案 甲，旺季的最大效益值=0.3×8=2.4 乙，旺季的最大效益值=0.3×10=3 所以，应该选择方案乙。 悲观主义：认为在最悲观的自然状态下具有最大效益值的方案为最佳方案 甲，淡季的最大效益值=0.2×3=0.6 乙，淡季的最大效益值=0.2×2=0.4 所以，应该选择方案甲。 最大期望值： 各方案的年利润期望值应等于该方案在三个自然状态下的年利润与该自然状态发生的概率的乘积之和。因此，可分别计算出方案甲和乙的年

15、利润期望值E甲和E乙。 E甲=0.3×8+0.2×3+0.5×6=6 E乙=0.3×10+0.2×2+0.5×7=6.9 所以，应该选择方案乙。 2某公司准备生产一种新产品，但该产品的市场前景不明朗。公司一些领导认为应该是先做市场调查，以确定市场的大小，再决定是否投入生产和生产规模的大小，而另一些领导认为没有必要花钱与浪费时间进行市场调查，应立即投入生产。根据估计，市场调查的成本是2000元，市场调查结果好的概率是0.6,而市场调查结果好时市场需求大的概率是0.8,市场调查结果不好时市场需求大的概率是0.3。假设市场规模大与小的概率都

16、是0.5。在不同市场前景下,不同生产规模下企业的利润如下表.请你分析这个问题的决策过程，并通 市场规模大 市场规模小 生产规模大 20000 -5000 生产规模小 10000 10000 过建立概念模型（决策中的主要因素），用决策树方法辅助决策。 答： 分析：决策中有三个方案：（1）先做市场调查，（2）不做市场调查即投入生产，（3）不生产。 估计调查结果好的概率为0.6，不好的为0.4。调查成本2000元，可能出现两种市场调查结果：好，市场需求大概率为0.8；不好，市场需求大概率为0.3。 此外，有两种生产规模供选择，生产规模大和生产规模小。 步骤： （1）估计自然状态的先验概率P（s）为：好，0.6；不好，0.4 （2）估算客观自然状态为sj时，调查结果为Ik的条件概率：好时，市场需求大的概率为0.8；不好时，市场需求大的概率为0.3 （3）建立决策树，用各自然状态的后验概率代替先验概率，运用决策树方法从右向左计算各方案的期望效益并选择出最优方案。 好0.6 10000 生产规模大 20000 10000 不好0.4 不调查即投入生产 -5000 好0.6 10000 生产规模小 10000 10000 不好0.4 10000 好0.6 9000 1生产规模大15000 需求大0.8 2