运筹学 案例文档格式.doc
《运筹学 案例文档格式.doc》由会员分享，可在线阅读，更多相关《运筹学 案例文档格式.doc（14页珍藏版）》请在冰点文库上搜索。
用广告的浏览量来衡量广告的受众数量。
J公司已经为三种媒介广告进行了初步的计划，并且估计了每种媒介广告的每次广告的受众数量，如表1所示。
表1超级食品公司广告组合问题的成本和广告受众数据
成本分类
成本（美元）
每次电视广告
每份杂志广告
每份星期天增刊广告
1.广告预算
300,000
150,000
100,000
2.酬金预算
90,000
30,000
40,000
广告受众期望量
1,300,000
600,000
500,000
每种媒介上可投放的广告数目受广告预算（400万美元）与计划预算（给G&
J公司的酬金100万美元）的限制。
另一限制条件是：
在促销活动期间，媒介1，即星期六上午儿童节目的电视广告已所剩无几，很难买到，只有五个广告时段的长度适合（另外两种广告媒介上有足够的选择余地）。
问题的解决
（1）请建立线性规划模型求解该问题。
（2）模型的准确性评价。
模型与实际问题并不是完全吻合的。
数学模型只能使实际问题的抽象表示，而为了将实际问题抽象出来，就必须进行一些近似或简化的假设。
值得庆幸的是，我们所要求的也只是数学模型与实际问题具有较高的关联性。
该公司决策团队现在面临的工作是确定上述模型是否符合这一标准。
请分析该模型可能存在的与实际不符的问题。
案例2：
控制大气污染
N&
L公司是一家全球著名的钢铁制造商，位于钢铁之城。
该公司目前雇佣了50,000名员工，是当地的主要劳动力雇佣者，因此整个城市都为这家公司而繁荣与发展起来，这里的人们也一直都认为凡是对公司有利的必然对整个城市有利。
但是现在人们的观点发生了一定的变化：
公司锅炉中排放出的气体因未加治理，正破坏者城市的风貌并日益危及者城市居民的身体健康。
最近的一次股东大会选举产生了一个较为英明的新董事会，其中的董事成员正与城市官员和居民讨论如何处理空气污染问题，他们一起制定出了很严格的大气排放质量标准。
所排放的污染气体中三种主要的成分是：
大气微尘、氧化硫和碳氢化合物。
新制定的排放气体质量标准要求公司降低这些污染气体的排放量，具体要求如表1所示。
董事会已经指示公司的管理人员召集工程人员，用最经济的方法将低污染气体的排放量。
表1污染物排放要求
污染物
要求每年排放减少量（百万磅）
大气微尘
60
氧化硫
150
碳氢化合物
125
公司的污染气体主要来自于两个方面，一是铸生铁的鼓风炉，一是炼钢的敞口式反射炉。
在这两方面，工程师都认为最有效的降低污染的方法是：
（1）增加烟囱的高度①①在本次研究之前，这一方法引起了人们的争议。
因为，增加烟囱的高度，只不过是通过降污染的范围扩大而减少近距离的污染。
环境专家认为，硫化物长久的留在大气中极易引起酸雨。
最后，美国的环境保护协会制定新的规则，规定不许使用增加烟囱高度的方法来减少污染。
；
（2）在烟囱中加入过滤装置；
（3）在燃料中加入清洁的高级燃料。
三种方法都有其技术限制（例如，烟囱可增加的高度是有限的），但考虑在各自的技术限制内，采取一定程度的措施。
表2显示了在技术允许的范围内，最大限度地使用各种方法可以降低两个炉子污染气体的排放量。
表2最大限度地使用各种降污方法可以降低污染气体的年排放量
污染气体
增加烟囱的高度
加入过滤装置
加入清洁的高级燃料
鼓风炉
反射炉
12
9
25
20
17
13
35
42
18
31
56
49
37
53
28
24
29
为了方便分析，假设各种方法也可以在技术允许的范围内部分实施，从而达到一定程度地减少污染气体的效果。
此外，各种方法在两个炉子上的实施比例可以不同，且在效果上也是互不影响的。
在分析了上面的数据之后，可以发现，没有一种方法可以实施全部的降污要求，而另一方面，在两个炉子上都同时最大限度地使用各种方法的组合，会超额完成降污任务，但这样做的费用是昂贵的，不利于公司的产品保持竞争力。
因此，工程师认为，应该在考虑各种方法的成本与效益的基础上，合理地组合各种方法。
此外，因为两个炉子的情况并不相同，所以针对两个炉子的治理方法也将不同。
分析每种方法的一年总成本，该成本包括运营和维护费用，以及因为适用降污方法而致使生产效率降低，进而减少了的收入。
为了使一开始的启动成本与今后的年成本可以相互比较，必须考虑货币的时间价值，将年成本折现。
这样可以生成下面的数据表，表3表示的是最大限度地使用各种方法估计的年成本。
并且，各种方法的使用成本与可获得的降污能力是呈比例的，也就是说，要取得一定比例的降污效果，所实施方法的成本在总成本中占同样的比例。
现在，可以制定出降污规划大致的框架了，即，这一规划必须确定在两个炉子上使用那几种方法，每种方法的实施程度。
表3最大限度地使用各种降污方法估计的年成本（百万美元）
降污方法
8
10
7
6
11
假设你被任命为运筹工作小组组长，管理层要求你以最小的成本实现降低各种污染气体的年排放量要求，应如何规划？
案例3：
P&
T公司的配送问题
背景
T公司是一家由家族经营的小公司。
它收购生菜并在食品罐头厂中把它们加工成为罐头，然后再把这些罐头食品分销到各地卖出去。
这个公司的一个主要产品是豌豆罐头。
这些豌豆罐头在三个食品罐头厂（靠近华盛顿的贝林翰、俄勒冈州的尤基尼、明尼苏达州的艾尔贝·
李）加工，然后用卡车把它们运送到美国西部的四个分销仓库（加利福尼亚州的萨克拉门托、犹他州的盐湖城、南达科他州的赖皮特城、新墨西哥州的奥尔巴古）。
如图1所示。
图1P&
T公司问题中的仓库和加工厂位置图。
公司目前的做法
许多年来，公司一直用下面的策略确定需要从每个罐头加工工厂运送多少罐头食品到各个仓库。
当前的运输策略：
1、因为在贝林翰的罐头厂距离仓库最远，所以把它的产品运送到最近的一个仓库，也就是萨克拉门托的那个仓库。
如果还有剩余的话，就把它们运送到盐湖城的仓库中去。
2、因为在奥尔巴古的仓库距离食品罐头厂最远，所以就要从最近的一个罐头厂（艾尔贝·
李的罐头厂）中运送产品到奥尔巴古。
如果还有剩余的话，就把它们运送到赖皮特城的仓库中去。
对于即将来临的收获季度，每一个罐头厂的产量都进行了估计，并且每一个仓库都从豌豆罐头总供应量中分配到了一定的比例。
这些数据如表1所示。
表1P&
T公司的运输数据表（单位：
车）
罐头加工厂
产量
仓库
分配量
贝林翰
75
萨克拉门托
80
尤基尼
盐湖城
65
艾尔贝·
李
100
赖皮特城
70
奥尔巴古
85
合计
300
把当前运输策略应用表1的数据，得到表2所示的运输计划。
在这个即将来临季节中每车的运输成本如表3所示。
表2P&
T公司的当前运输计划（单位：
从
至
仓库
5
55
15
表3P&
T公司的单位卡车的运输成本（单位：
美元）
464
513
654
867
352
416
690
791
995
682
388
685
合并表2和表3得到，即将来临的季节中，当前运输计划下的总运输成本：
总的运输成本=75×
464＋5×
352＋65×
416＋55×
690＋15×
388＋85×
=165595（美元）
检查当前的运输计划，看看是否能够制定出一个新的运输计划，使总运输成本下降到一个绝对最小值。
案例4：
划分学生入学区域
米德尔城学区（MiddletownSchoolDistrict）开办了第三所中学，需要为每一所学校重新规定这个城市内的服务区域。
在初步的计划中，这个城市被分成了拥有大致相同数量人口的9个区域（在进一步细化的计划之中，就把城市分成了超过100个更小的区域）。
表1给出了每一所学校与每一个区域之间的近似距离。
最右一列给出了明年每一区域的高中学生数量（这些数字在未来几年内估计会有缓慢的增长）。
最下面的两行表示了每一所学校所能够安排的最少和最多的学生数量。
表1米德尔城学区问题的数据
学校
区域
区域、学校之间的距离
学生数量
1
2
3
2.2
1.9
2.5
500
1.4
1.3
1.7
400
0.5
1.8
1.1
450
4
1.2
0.3
2.0
0.9
0.7
1.0
1.6
0.6
2.7
1.5
0.8
最小招生数
1200
1100
1000
最大招生数
1800
1700
1500
学区管理者认为划分入学区域界限的适当目标是要使学生到学校的平均路程最短。
在这个初步的计划之中，它们要确定为了实现这一目标每一个区域内有多少学生要安排到每一所学校中，同时又要满足标最后两行规定的约束条件。
案例5：
默登公司的联网问题
默登（Modern）公司的管理层已经决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信（数据、声音和图像）。
图1中的节点显示了该公司主要中心（包括了公司的总部、巨型计算机、研究区、生产和配送中心）的分布图。
虚线是铺设光缆可能的位置（其它的两个中心之间也可能铺设光缆，但由于不经济已经排除在外了）。
每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本（单位：
百万美元）。
A
B
C
E
G
F
D
图1光缆铺设费用图
为了充分利用光线技术在中心之间高速通信的优势，不需要在每两个中心之间都用一条光缆把它们直接连接起来。
那些需要光缆直接连接的中心有一系列的光缆连接它们。
现在的问题就是要确定需要铺设哪些光缆使得提供给每两个中心之间的高速通信的总成本最低。
案例6BMZ公司的最大流问题
背景
BMZ公司是欧洲一家生产豪华汽车的制造商。
它因为提供优质的服务而获得很好的声誉，保持这个声誉一个很重要的秘诀就是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商合授权维修店。
这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。
卡尔（BMZ公司的供应链的经理）优先考虑的是改进这些配送中心的不足之处。
该公司在美国有几个配送中心。
但是，离洛杉机中心最近的一个配送中心却坐落离洛杉机1000多英里的西雅图。
保证洛杉机中心良好的供应是尤为重要的。
因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问题。
大部分的汽车配件以及新车是在该公司坐落于德国的斯图加特的总厂和新车一起生产的。
也就是这家工厂向洛杉机中心供应汽车配件。
每月有超过300000立方英尺的配件需要运到。
现在，下个月需要多得多的数量以补充正在减少的库存。
问题
卡尔需要尽快制定一个方案，使得下个月从总厂运送到洛杉机配送中心的供应件尽可能多。
他认识到了这是个最大流的问题——一个使得从总厂运送到洛杉机配送中心的配件流最大的问题。
因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是公司配送网络的容量。
ST
RO
BO
LI
NO
NY
LA
50
40
30
图1网络模型
这个配送网络如下图1。
在图中，标有ST和LA的节点分别代表斯图加特的工厂和洛杉机的配送中心。
由于工厂所在地有一个铁路运转点，所以首先通过铁路把配件运输到欧洲的三个港口：
鹿特丹（RO）波尔多（BO）和里斯本（LI）；
然后通过船运到美国的港口纽约（NY）或新奥尔良（NO）；
最后用卡车送到洛杉机的配送中心。
经营这些铁路、船舶和卡车的组织是独立所有的公司，这些公司为很多的公司运输货物。
由于对这些老主顾原有的承诺，这些公司不可以在短时间内为任何一个客户大量增加运输空间配额。
因此，BMZ公司只能够保证获得下个月每条运输航线有限的运输空间。
图1已经给出可以获得的空间数量，以100立方米为1个单位（由于每100立方米比3500立方英尺大一点，所以，需要运送的这批货物体积是很大的）。
模型描述和求解
这是一个最大流问题，每一条弧下方括号里的数字代表了该弧的容量。
通过标号法求得最大流，在各线路上的运输方案如表1所示。
最大流量为150单位。
表1最大流分配方案
出发点
目的地
运输量
斯图加特
鹿特丹
波尔图
里斯本
纽约
新奥尔良
洛杉矶
进一步改善的方案
在柏林，即斯图加特的工厂的北面，公司有一家较小一点的工厂也生产汽车配件。
虽然通常这家工厂用来协助供应给北欧、加拿大和美国北部地区的配送中心（包括在西雅图的一个），但是它也同样可以运输配件到洛杉矶的配送中心去。
而且，当洛杉矶配送中心出现库存短缺时，西雅图的配送中心有能力供应配件给洛杉矶配送中心的客户。
受到这一点的启发，卡尔为解决当前洛杉矶存货短缺的问题开发了一个更好的方案。
他决定与其仅仅使得从斯图加特的工厂到洛杉矶配送中心的运输量最大，不如使得两个工厂到洛杉矶和西雅图这两个配送中心的运输量最大。
图2扩展的网络模型
BE
HA
BN
SE
图2显示的网络模型代表扩展后的配送网络。
这个经过扩展的网络包括了两个工厂和两个配送中心。
除了图1的节点以外，节点BE代表了位于柏林的较小的工厂，节点HA和节点BN分别代表为这家工厂提供服务的汉堡和波士顿别外两大港口。
SE代表了西雅图。
和以前一样，弧代表了运输路线，每一条弧下方括号里的数字代表了该弧的容量，即下个月可以通过这条运输路线的最大运输单位数。
将经过扩展的BMZ问题看作是最大流问题的网络模型。
重新求解，得到改善的最大流分配方案如表2所示。
最大流量为220单位。
其中，运送到洛杉矶的单位数由150增长到160，另外的新加60单位到西雅图作为洛杉矶库存短缺的备份，这个方案不但解决了洛杉矶的危机，而且也使卡尔赢得了高层管理的称赞。
表2改善的最大流分配方案
60
10
50
70
30
（1）标号法求解最大流问题时，如何获得初始可行流？
（2）对于图2所示的扩展的网络模型，是否满足最大流问题对网络图的要求？
应如何处理？
案例7：
博弈论案例
生活中的“囚徒困境”例子——商家价格战
出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱。
当一些商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来。
譬如，2000年我国几家生产彩电的大厂商合谋将彩电价格维持高位，他们搞了一个“彩电厂家价格自律联盟”，并在深圳举行了由多家彩电厂商首脑参加的“彩电厂商自律联盟高峰会议”。
当时，国家有关部门还未出台相关的反垄断法律，对于这种在发达国家明显属于违法行为的所谓“自律联盟”，国家在法律上暂时还是无能为力的。
寡头厂商在光天化日之下进行价格合谋，并且还通过媒体大肆炒作，这在发达国家是不可思议的。
但是，尽管政府当时无力制止这种事情，公众也不必担心彩电价格会上涨。
这是因为，“彩电厂商自律联盟”只不过是一种“囚徒困境”，彩电价格不会上涨。
在高峰会议之后不到二周，国内彩电价格不是上涨而是一路下跌。
这是因为厂商们都有这样一种心态：
无论其他厂商是否降价，我自己降价是有利于自己的市场份额扩大的。
问题：
明确该博弈问题的各要素：
局中人、策略集、赢得矩阵
14
升级会员 