《运筹学》作业
第2章
1. 某公司计划生产两种产品,已知生产单位产品所需的三种原材料的消耗及所获的利润,
如下表所示。问应如何安排生产使该工厂获利最多?(建立模型,并用图解法求解) 原材料A 原材料B 原材料C 单位产品获利 产品1 1 3 0 40万元 产品2 2 2 2 50万元 可用的材料数 30 60 24 模型:线性规划 1)决策变量:产品1和产品2的产量。
设:X为产品1的产量;Y为产品2的产量。 X、Y为本问题的决策变量。 2)目标函数:获利最多。
由于产品1和产品2单位获利分别为40万元和50万元,其产量分别为X和Y,则总获利可计算如下: 总获利=40X+50Y
3)约束条件:四个。材料A、B、C及产量非负约束。 则可得线性规划模型: O.B. Max 40X+50Y S.T. X +2Y≦30;
3X+2Y≦60 2Y≦24 X,Y≧0
图解:
y 30 25 ① ①40x+50y=1000 ② 20 3X+2Y=60 ②40x+50y=800 15 A B 2Y=24 10 C X+2Y=30 5
O D x 5 10 15 20 25 30 在坐标中绘制对约束条件相应的直线,得到满足条件的区域,即位于第一象限的凸多边形OABCD(包括边界)为满足所有约束条件的解的集合。
由图可见,可行域内离原点最远点为C,则:x+2y=30 3x+2y=60 解得:x=15;y=7.5
即产品1和产品2的产量分别为15和7.5,则获最大利润15*40+7.5*50=975(万元)
2.某公司计划生产两种产品,已知生产单位产品所需的两种原材料的消耗和人员需要及所获的利润,如下表所示。问应如何安排生产使该工厂获利最多?(建立模型,并用图解法求解)
原材料A 原材料B 人时 单位产品获利 产品1 1 0 3 300万元 产品2 0 2 2 500万元 可用的材料数 4 12 24
线性规划模型:设产品1、2的产量分别为x、y,则有: O.B. Max 300x+500y S.T. x≦4 2y≦12 3X+2y≦24 x,y≧0
图解: y 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)是否愿意付出11元的加班费,让工人加班;
2)如果工人的劳动时间变为402小时,日利润怎样变化? 3)如果第二种家具的单位利润增加5元,生产计划如何变化?
Microsoft Excel 9.0 敏感性报告 工作表 [ex2-6.xls]Sheet1 报告的建立: 2001-8-6 11:04:02 约束
单元格 $G$6 $G$7 $G$8
单元格 $B$15 $C$15 $D$15 $E$15
名字 日产量 (件) 日产量 (件) 日产量 (件) 日产量 (件)
名字
木材 (单位/件) 玻璃 (单位/件)
终 值 100 80 40 0 终 值 600 800
递减 成本 20 0 0 -2.0 阴影 价格 8 4 0
目标式 系数 60 20 40 30 约束 限制值 400 600 1000
允许的 增量 1E+30 10 20 2.0 允许的 增量 25 200 1E+30
允许的 减量 20 2.5 5.0 1E+30 允许的 减量 100 50 200
可变单元格
劳动时间 (小时/件) 400
1)由以上敏感性报告可知,劳动时间的影子价格为8元,在劳动时间的增量不超过25小时的条件下,每增加1小时的劳动时间,该厂的利润(目标值)将增加8元,因此,付给工人11元以增加1小时劳动时间是不值得的,将亏损11-8=3(元)。
2)劳动时间变为402小时,该增加量在允许的增量(25小时)内,所以劳动时间的影子价格不变,仍为8元,因此,该厂的日利润变为:60+20+40+30+8*(402-400)=166(元),比原来增加16元利润。
3)第二种产品增加利润5元,在允许的增量(10元)内,此时最优解不变,因此,生产计划无需变化。
4某公司计划生产两种产品,已知生产单位产品所需的三种原材料的消耗及所获的利润,如下表所示。问应如何安排生产使该工厂获利最多?(建立模型,并用图解法求解)(20分)
原材料A 原材料B 原材料C 单位产品获利
产品1 0.6 0.4 0 25元 产品2 0.5 0.1 0.4 10元 可用的材料数 12000 4000 6000
线性规划模型: O.B. Max S.T. 图解: y 40000
25x+10y
0.6x+0.5y≦12000 0.4x+0.1y≦4000 0.4y≦6000 x,y≧0
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=6250;y=15000
即产品1和产品2产量为6250和15000时,工厂获最大利润25*6250+10*15000=306250元
5. 线性规划的解有唯一最优解、无穷多最优解、无界解 和无可行解四种。
6. 在求运费最少的调度运输问题中,如果某一非基变量的检验数为4,则说明如果在该空格中增加一个运量,运费将 增加4 。
7.“如果线性规划的原问题存在可行解,则其对偶问题一定存在可行解”,这句话对还是错? 错
第3章
1. 一公司开发出一种新产品,希望通过广告推向市场。它准备用电视、报刊两种广告形式。这两种广告的情况见下表。要求至少30万人看到广告,要求电视广告数不少于8个,至少16万人看到电视广告。应如何选择广告组合,使总费用最小(建立好模型即可,不用求解)。 媒体 电视 报刊 可达消费者数 2.3 1.5 单位广告成本 1500 450 媒体可提供的广告数 15 25 目标:总费用最小,设:电视、报刊投放数分别为x、y 线性模型: O.B. min 1500x+450y S.T. 15≥x≥8 2.3x≥160000
2.3x+1.5y≥300000 25≥y>0
2.医院护士24小时值班,每次值班8小时。不同时段需要的护士人数不等。据统计: 序号 1 2 3 4 5 6 时段 06—10 10—14 14—18 18—22 22—02 02—06 最少人数 60 70 60 50 20 30 应如何安排值班,使护士需要量最小。
目标:护士人数最小
因:每次值班8小时,因此,每班次必跨两个时段,用决策变量Xij表示跨i和j两个时段值班的护士人数,则有: O.B. min X12+X23+X34+X45+X56+X61 S.T. X12+X23≥70
X23+X34≥60 X34+X45≥50 X45+X56≥20 X56+X61≥30 X61+ X12≥60
第4章
1. 对例4.5.1,如果三个工厂的供应量分别是:150,200,80, 两个用户的需求量不变.请重新建
立模型,不需要求解.
工厂供应量发生量变,则虚节点产生量变。
虚节点的净流出量= —(150+200+80-300-160)=30(吨),此时为供应虚节点。所以是供需不平衡的运输最小费用流问题。辅助图示如下
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+DG≦300 EF+EG≦160 AD,AE,BD,BE,CD,CE,DF,DG,EF,EG≥0
2. 已知运输问题的调运和运价表如下,求最优调运方案和最小总费用。 B1 B2 B3 销地 产量 产地 A1 A2 A3 销量 5 3 6 18 9 1 2 12 2 7 8 16 15 11 20 虚节点的净流出量= —(15+11+20-18-12-16)=0,所以是属于供需平衡的最小费用流问题。 设各产至销地的产品量分别为:A1B1,A1B2,A1B3,A2B1,A2B2,A2B3,A3B1,A3B2,A3B3 则可建模型: O.B. min 5A1B1+9A1B2+2A1B3+3A2B1+A2B2+7A2B3+6A3B1+2A3B2+8A3B3 S.T. A1B1+A1B2+A1B3=15 A2B1+A2B2+A2B3=11 A3B1+A3B2+A3B3=20 A1B1+A2B1+A3B1=18 A1B2+A2B2+A3B2=12 A1B3+A2B3+A3B3=16 A1B1,A1B2,A1B3,A2B1,A2B2,A2B3,A3B1,A3B2,A3B3≥0
第5章
1.考虑4个新产品开发方案A、B、C、D,由于资金有限,不可能都开发。要求A与B至少开发一个,C与D中至少开发一个,总的开发个数不超过三个,预算经费是30万,如何选择开发方案,使企业利润最大(建立模型即可)。 方案 A B C D
开发成本 12 8 19 15 利润 50 46 67 61
目标:企业利润最大
设ABCD四种新产品开发个数分别为:X1\\X2\\X3\\X4,则有 O.B. max 50X1+46X2+67X3+61X4 S.T. X1+X2≥1 X3+X4≥1
X1+X2+X3+X4≦3
12X1+8X2+19X3+15X4≦30
第9章
1. 某厂考虑生产甲、乙两种产品,根据过去市场需求统计如下: 方案 甲 乙 自然状态 概率 旺季 0.3 8 10 淡季 0.2 3 2 正常 0.5 6 7 分别用乐观主义、悲观主义和最大期望值原则进行决策,应该选择哪种产品? 乐观主义:在最乐观的自然状态下具有最大效益值的方案为最佳方案 甲,旺季的最大效益值=0.3×8=2.4 乙,旺季的最大效益值=0.3×10=3 所以,应该选择方案乙。
悲观主义:认为在最悲观的自然状态下具有最大效益值的方案为最佳方案 甲,淡季的最大效益值=0.2×3=0.6 乙,淡季的最大效益值=0.2×2=0.4 所以,应该选择方案甲。 最大期望值:
各方案的年利润期望值应等于该方案在三个自然状态下的年利润与该自然状态发生的概率的乘积之和。因此,可分别计算出方案甲和乙的年利润期望值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.在不同市场前景下,不同生产规模下企业的利润如下表.请你分析这个问题的决策过程,并通过建立概念模型(决策中的主要因素),用决策树方法辅助决策。 生产规模大 生产规模小 市场规模大 20000 10000 市场规模小 -5000 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 20000 8000 1+A 需求小0.2 -5000 1+B 11000 1+B 6000 2生产规模小10000 需求大0.8 10000 11000 需求小0.2 10000
调查-2000
不好0.4 1000 A生产规模大2500 需求大0.3 20000 5000 2+A 需求小0.7 -5000 8000 2+B 4000 B生产规模小10000 需求大0.3 10000 需求小0.7 10000 不生产0
决策结果:进行调查,在好的时候以大规模生产方式生产,不好的时候以小规模生产方式生产,期望效益可达11000
因篇幅问题不能全部显示,请点此查看更多更全内容