运筹学实验指导书

1、运筹学实验指导书运筹学实验指导书彭佑元闫莹刘东霞编经济与管理学院前 言在目前的环境中，运筹学的性质正在改变。这是因为人们对以算法为中心的课程不再有足够的耐心，相反，他们对以商业环境为背景的课程更为需要， 包括一些著名的非数学问题、使用电子表格，以及建立和评估模型，而并非对模型结 构本身的研究。在教学中使用电子表格软件已经成为管理教学的一个明显的新潮 流。这意味着，原先在传统运筹学教科书中占有重要地位的代数学的门帘已经可 以被轻轻拉开了。对于未来的管理者和管理咨询人员， 本实验将把重点放在电子表格在管理科 学知识的应用上。 然而，对一个实际问题建立电子表格模型通常需要花很多时间 在模型设计和数据

2、输入上。 因此，常常按照下列工作程序， 一步一步地完成建模： 理解问题；以书面形式逐步展开某些重要结构； 收集数据； 用定量的语言表达数 据间的关系； 最后形成电子表格模型。 这种结构化的方法重点突出了建模的主要 元素（数据、决策目标、约束条件、绩效度量）及其相应的不同类型的单元格。另外，电子表格并不是进行管理科学分析的唯一工具， 偶尔应用的代数学或 图形分析工具也享有的重要地位。电子表格软件只是我们达到某一目标的工具， 而并非目标本身。计算机运行的环境本实 验介绍使 用 的应 用软件是 Microsoft Office 2000 中 文版 中的Microsoft Excel ，需要 Micr

3、osoft Excel 中的加载宏程序。启动 Excel 后，在“工具”菜单上，单击“加载宏”命令。在“加载宏”列 表框中，选定待添加加载宏选项左侧的复选框。单击“确定”按钮后，在“工具”菜单上就可以找到 “规划求解” 的命令项， 这表明安装成功。使用 Excel 的加载宏 TreePlan 在电子表格上进行构建和分析决策树。与其 他 Excel 加载宏一样，这些加载宏需要安装才能在 Excel 中显示出来。目录1 实验一 线性规划113.1 实验目的11.2 案例71.3 实验内容71.4 实验要求81.5 练习9 实验二 指派问题92.1 实验目的92.2 案例152.3 实验内容152.

4、4 实验要求162.5 练习17实验三 网络最优化 - 最短路问题173.1 实验目的173.2 案例213.3 实验内容213.4 实验要求223.5 练习23 实验四 决策分析234.1 实验目的234.2 案例274.3 实验内容274.4 实验要求284.5 练习29 附录 经典应用30（1）确定潘得罗索工业公司的产品组合31（2）联合航空公司的员工排程32（ 3） Citgo 石油公司的供应、配送和营销规划实验一 线性规划线性规划是一种对问题进行求解的方法， 可以帮助管理者制定决策。 以下是 几种应该使用线性规划方法的典型情况：（1）制造者希望建立一个生产时间表和库存计划，以满足未来

5、一段时间的 市场需求。 最理想的情况是， 既满足市场上产品的需求， 同时又使生产和库存的 成本最低。（2）金融分析员必须选择一种股票或证券进行投资。金融分析员希望是自 己的投资有最大的回报率。（3）营销经理希望能够从广播、电视、报纸、杂志这几种媒体中选择一种 合适的组合，确定广告预算是自己的广告效益最好。（4）公司的仓库分布于全美各地，现在有一些顾客订单，公司希望确定每 个仓库的发货量，使总成本最低。这些只是线性规划应用的一小部分， 但足可以看出线性规划广泛的应用。 经 过仔细的观察， 我们可以发现这些例子有共同的特点。 每个例子都要求我们使用 实现目标函数值最大化或最小化。 另外，存在约束条

6、件， 而且这些约束条件会影 响目标的实现1.1 实验目的理解线性规划的概念。对于一个问题，能够建立基本的线性规划模型。会运用Excel解决线性规划电子表格模型。1.2 案例派公司是一个生产高尔夫器材的小型公司， 公司决定生产高中价位的高尔夫 袋。分销商对新产品十分感兴趣，并且同意买进派公司下 3 个月内的全部产品。在对整个高尔夫袋生产步骤进行了详细的调查以后， 管理阶层明确了高尔夫 袋的生产过程：（1）切割并印染原材料（2）缝合3）成型（插入支撑架、球棒分离装置等）4）检测和包装生产制定者详细分析生产过程的每一步， 得出以下结论， 生产一个标准高尔 夫袋需要用： 7/10 小时完成切割并印染原

7、材料，用 1/2 小时完成缝合，用 1 小 时完成成型，用 1/10 小时检测和包装。生产高级袋则需要：用 1 小时完成切割 和印染，用 5/6 小时完成缝合，用 2/3 小时完成成型，用 1/4 小时检测和包装。 生产信息列于下表：表 1.1 生产每个高尔夫袋所需要的时间生产耗时部门 标准袋 高档袋切 割并 印 染 原 材 料 7/1011/2缝合5/6成型2/31/10检测和包装1/4派公司的生产还受各个部门生产能力的限制。 经过对整个生产部门工作量的 研究。生产制定者分析得出， 3 个月内每个部门的最大生产时间分别是：切割印 染 630 小时，缝合 600 小时，成型 708 小时，检测

8、包装 135 小时。会计部门经过对生产数据、 各种生产成本的分析得出了以下的结论， 生产一 个标准袋的利润是 10 美元，生产一个高级袋的利润是 9 美元。1.2.1 问题成型问题成型或问题建模， 是将语言文字上的问题转化为数学问题。 可以说， 这 是一项艺术创造， 只有通过不断地练习才能熟练掌握。 虽然， 实际生活中的每个 问题都有其独特之处， 但其中大部分还是有共性的。 所以， 可以用以下普遍适用 的方法来帮助建立数学模型。下面以派公司为例讲解一下建立数学模型的方法。完整地了解问题 对于一个比较复杂的例子来说， 可能需要更加详细的思考， 才能获得准确的模型。 处理复杂的例子， 可以先快速地

9、浏览一下整个问题以了解 问题所包含的内容，然后将重点和关键问题记录下来以供详细地分析。描述目标 本题的目标就是使产品的利润最大。描述约束条件 对于生产时间来说，一共有 4 个约束条件，它们制约着两种 高尔夫袋的生产。约束条件 1 用于切割和印染的总时间必须小于等于切割和印染部所能承受 的最大工作时间。约束条件 2 用于缝合的总时间必须小于等于缝合部所能承受的最大工作时 间。约束条件 3 用于成型的总时间必须小于等于成型部所能承受的最大工作时 间。约束条件 4 用于检测和包装的总时间必须小于等于检测和包装部所能承受 的最大工作时间。定义决策变量 派的决策变量有两个： （1）标准袋的产量；（2）高

10、档袋的产 量。设5=是标准袋的产量D=1高档袋的产量根据决策可变量写出模型目标 派公司的利润来源于两方面： （1）生产标准 袋所获得的利润；（2）生产高档袋所获得的利润。因为，公司生产一个标准袋的 利润是 10美元，生产一个高档袋所获得的利润是 9 美元。因此，可以得到总利润=1OS+9D因为公司的目标是使总利润最大，总利润又是决策可变量S和D的函数，所 以称10S+9D为目标函数。使用max来表示使函数最大化，则派公司的目标如下：max z=1OS+9D根据决策变量写出约束条件约束条件 1 ：（S个标准袋和D个高档袋切割合印染所用的时间）w（公司切割印染部的 最大工作时间）所以7/10S+1

11、D 630约束条件 2：（S个标准袋和D个高档袋缝合所用的时间）w（公司缝合部的最大工作时间）所以1/2S+5/6D 600约束条件 3：（S个标准袋和D个高档袋成型所用的时间）w（公司成型部的最大工作时间）所以1S+2/3D 708约束条件 4：（S个标准袋和D个高档袋检测和包装所用的时间）W（公司检测和包装部的最大工作时间）所以1/10S+1/4D 0 和 D 0因此它被称为非负约这一过程通常称为数学这两个条件必须加上。 它可以确保模型的解是非负值， 束。非负约束是线性规划问题里经常会遇到的。1.2.2 派公司问题的数学表述将问题的目标以及约束条件转化成为一组数学关系，模型。完整的数学模型

12、如下：max z=10S+9Dst. 7/10S+1D 6301/2S+5/6D 6001S+2/3DW 7081/10S+1/4D 0找到合适的组合（比如S和D的组合），既满足约束条件，又能使目标函数的值最大。一旦这些值都计算出来了，也就找到了函数的最优解。派的数学模型为线性规划模型或线性规划。 正如上文所言， 该问题有目标和 约束条件， 这是所有线性规划问题共有的特点。 同时，可以发现这道题的约束条 件都是线性函数（约束不等式的左边） 。线性函数是指函数中的每个变量都是独立的并且幂次为1 。目标函数（10S+9D就是线性函数，因为它的两个变量都是独立的，并且是一次幕。同理, 切割和印染的生

13、产时间函数也是线性函数（7/10S+1D）。同理，所有约束不等式 的左侧都是线性函数。因此，称这个问题为线性规划问题。对于线性规划问题的 3 种基本的假设是：比例性、可加性、可除性。比例性 是指有目标函数和约束条件都与决策变量成严格的比例性。 可加性是指目标函数 的值和总使用资源可以通过汇总所有的决策变量对应的目标函数和使用资源获 得。可除性是指决策可变量是持续性的。 可除性假设与非负条件意味着决策可变 量可以取大于或等于零的一切数值。1.2.3 在工作表中建模在一个工作表中建立线性规划模型，包括以下步骤：工作表包括两部分： 数据部分和模型部分。 按照上述五步为派公司建立工作表，如图 1.1

14、：第一步 在工作表的顶部输入数据单元格 7B5:C8 显示每件产品的工作时间要求。单元格 B9:C9 显示这两种产品的每一件的利润单元格 D5:D8 显示每个部门的可工作时间。第二步 确定每个决策变量所对应的可变单元格的位置。可变单元格 B16 是标准袋的产量，可变单元格 C16 是高档袋的产量第三步 选择单元格输入公式，找到目标函数的值。单元格 B18: =SUMPRODU(CTB9:C9,B16:C16)第四步 选择一个单元格输入公式，计算每个约束条件左边的值。对于这个模型中的 4 个约束条件，使单元格 B21: =SUMPRODU(CTB16:C16,B5:C5)单元格 B22: =SU

15、MPRODU(CTB16:C16,B6:C6)单元格 B23: =SUMPRODU(CTB16:C16,B7:C7)单元格 B24: =SUMPRODU(CTB16:C16,B8:C8)第五步 选择一个单元格输入公式，计算每个约束条件右边的值。对于这个模型中的 4 个条件，使单元格 D21: =D5单元格 D22: =D6单元格 D23: =D7单元格 D24: =D8这里，每个输出单元格（包括目标单元格）的 Excel 等式可以表示为一个SUMPRODU函数。SUMPRODU函数能对相等行数和相等列数的两个变化范围的 单元格中的值相乘后进行加和。 被加和的每个值是对第一个变化范围的一些值和

16、对应位置的第二个变化范围的一些值的积。 这里加和的每一项是一个数据单元格 与一个可变单元格的乘积。例如，SUMPRODUCB9:C9,B16:C16）就表示B9X B16 + C9X C1& SUMPRODU数在线性规划的电子表格模型中被广泛使用。1.2.4 使用 Excel 求解建立了电子表格模型，就可以利用 Excel 中的工具 Solver （规划求解）求 解线性规划问题了。第一次用 Solver （规划求解）的时候，需要在 Excel 宏菜 单下安装 Solver （规划求解），然后就能在工具菜单下找到它。开始时，一个任意的试验解通过设定为零进入可变单元格。求解问题后，Solver （

17、规划求解）会使这个值改变为最优值。第一步 在工具菜单中选择 Solver （规划求解），如图 1.1图 1.1 派公司模型第二步 当出现规划求解参数对话框（如图 1.2 ）时，设置目标单元格 B18， 并选中最大值 , 使得求解的目标最大化。图 1.2 规划求解参数第三步 在可变单元格中输入 B16:C16。第四步 添加约束对话框用来具体化所有的函数约束。点击“添加”按钮来 实现，会弹出添加约束对话框 ,如图 1.3：图 1.3 约束对话框在单元格引用位置中输入 B21:B24；在约束值框中输入 D21:D24；对于两边中间的符号，有菜单可以选择，本题选 <= （可以全部约束条件 一次输

18、入，也可以一次只输入一个约束条件） ；单击确定到此为止， Solver （规划求解）对话框根据电子表格概述了全部的模型。但 是在要求 Solver （规划求解）求解模型之前还需要再做一步程序。第五步 点击“选项”按钮弹出如图 1.4 所示的对话框，在对话框中细化求 解选项，最重要的是“采用线性模型”和“假定非负”选项，其他为默认值。点 击确定回到规划求解参数对话框。图 1.4 规划求解选项框第六步 点击规划求解参数对话框中的“求解”按钮，开始对问题求解。几 秒钟之后（对于一个小型问题） ，就会显示运行结果，本题得到一个最优解，如 图 1.5 。如果模型没有可行解或没有最优解，对话框会显示“找不

19、到可行解”或 “设定的单元格值不能收敛” 。对话框还显示了产生各种报告的选项。图 1.5 规划求解结果框求解模型之后，Solver （规划求解）用最优值代替了可变单元格中的初始值。图 1.6 完整模型如图 1.6 是电子表格的最优解。最优解是标准袋 540 个，高档袋 252 个1.3 实验内容线性规划的一大应用适用于联邦航空公司的工作人员排程， 为每年节省开支超过 600 万美元。联邦航空公司正准备增加其中心机场的往来航班， 因此需要雇佣更多的客户 服务代理商， 但是不知道到底要雇用多少数量的代理商。 管理层意识到在向公司 的客户提供令人满意的服务水平的同时必须进行成本控制， 因此，必须寻找

20、成本 与收益之间合意的平衡。 于是，要求管理团队研究如何规划人员才能以最小的成 本提供令人满意的服务。分析研究新的航班时间表， 以确定一天之中不同时段为实现客户满意水平必 须工作的代理商数目。 在表 1.2 的最后一栏显示了这些数目， 其中第一列给出对 应的时段。表中的其它数据反映了公司与客户服务代理商协会所定协议上的一项 规定，这一规定要求每一代理商工作 8 小时为一班，各班的时间安排如下：轮班 1: 6:00AM2:00PM轮班 2: 8:00AM4:00PM轮班 3：中午 8:00PM轮班4: 4:00PM午夜轮班 5: 10:00PM6:00AM表中打勾的部分表示这段时间是有相应轮班的

21、。 因为轮班之间的重要程度有 差异，所以协议中工资也因轮班所处的时间而不同。 每一轮班对代理商的补偿 （包 括收益）如最低行所示。问题就是，在最低行数据的基础上，确定将多少代理商 分派到一天之中的各个轮班中去， 以使得人员费用最小， 同时，必须保证最后一 栏中所要求的服务水平的实现。表 1.2 联邦航空公司人员排程问题的数据轮班的时段时段12345最少需要代理商的数量6:00 AM8:00 AMV488:00AM10:00AM7910:00AM中午65中 午 2:00PM872:00PM 4:00PMVVVVVVVV644:00PM 6:00PM736:00PM 8:00PM828:00PM

22、10:00PM10:00PM午夜4352午夜6:00AMV15每个代理商的每日成本 170 160 175 180 1951.4 实验要求（1）如何规划人员才能以最小的成本提供令人满意的服务？（2）根据实验内容自行设计模型，求解最优方案。（3）完成并提交实验报告。1.5 练习利博（ Profit&Gambit ）公司生产家用的清洁产品，这是一个高度竞争 的市场，公司为了增加市场份额连续挣扎多年。 管理层决定集中在下列三个主要 产品上实行一个大规模的新的广告活动。一种喷雾去污剂种新的液体洗涤剂一种成熟的洗衣粉这一广告运动会采用电视和印刷媒体。 一个商业广告已经形成， 要在全国的 电视上做

23、液体洗涤剂的广告来帮助推出这一新产品。 印刷媒体的广告将用来促销 所有三种产品， 包括消费者可用来以低价购买产品的象征性优惠券。 总的目标是 增加所有这些产品 （但着重是液体洗涤剂） 的销售在明年有一个大的飞跃。 管理 部门特别设定了如下广告运动的目标：喷雾去污剂必须至少增加 3%的市场份额新的液体洗涤剂必须至少增加 18%的市场份额洗衣粉占洗涤剂市场的份额必须增加 4%表 1.3 显示了在各自的媒体上做一单位广告的相应产品市场份额的估计增 加额（一个单位是指利博公司通常采用的一个广告标准批量， 但其他数量也是允 许的）。在电视一列中洗衣粉的增加份额为 -1%的原因是新的液体洗涤剂的电视商 业

24、广告会带走一些洗衣粉的销售额。 表中最低行显示了两种媒体中每一种媒体上 做广告的单位成本。管理部门的目标是决定以最低的总成本下达到市场份额的目标要在每种媒体上做多少钱的广告。表 1.3 利博公司广告组合问题的数据产品每单位广告增加的市场份额 （%） 需要最小的增加量（ %）电视 印刷媒体去污剂0 1 3液体洗涤剂 3 218洗衣粉-1 4 4单位成本100万美元 200 万美元实验二 指派问题 很多决策过程中都会产生指派问题。典型的指派问题包括将工作指派给机 器，将任务指派给代理商， 将销售人员指派到销售区域， 将合同指派给投标人等 等。指派问题的一个明显特征就是每个代理商只能指派到一个并且只

25、有一个任 务。特别要寻找可以将以设立目标优化的配置， 如将成本和时间最小化， 或将利润最大化2.1 实验目的理解指派问题的特点。对于一个指派问题，能够建立电子表格模型。会运用Excel求解电子表格模型。2.2 案例福尔市场研究公司刚刚从 3 个新客户那里得到进行市场研究的要求。 该公司 面临的问题就是如何给每个客户指派一个项目主管（代理商） 。目前，有 3 个人 手头没有其他的工作， 可以胜任项目主管。 然而， 福尔的管理层意识到完成每项 市场研究所需要的实践完全取决于该项目主管的经验和能力。这 3个项目的优先顺序大致相当。公司希望其委派的项目主管们都能够用最短的时间完成这 3 个项 目。如果

26、每个项目主管只指派到一个客户，那么应该怎样指派呢？要回答这个问题， 福尔的管理层首先必须考虑所有可能的项目主管客户搭配的指派方法，并估算出相应的项目所需的时间（用天表示）图 2.1 用网络说明了福尔的指派问题。 节点代表项目主管和客户， 弧线代表 示可能的项目主管客户搭配。每个起点节点的供给和终点节点的需求均为 1；将一个项目主管配置给一个客户的成本就是项目主管完成该客户任务所需的 时间。注意：指派问题的网络模型图（见图 2.1 ）与运输问题的网络模型是相似 的图。指派问题是运输问题的一个特例。 在这个运输问题中， 所有的供给和需求 值都等于 1，并且每条弧线所运输的货物数量为 0或 1。表

27、2.1 福尔市场营销调查配置问题的预计项目完成时间客户项目主管1 2 3特瑞101卡尔918迈克孟德 6 142.2.1 数学模型3此指派问题是一个特殊的可以用线性规划方程的运输问题。 给每个节点都赋 予约束条件，并对每个弧都赋予一个参数。 在运输问题中， 使用双下标决策可变 量。x11代表项目主管1 （特瑞）和客户1, x12代表项目主管1 （特瑞）和客户 2 依次类推。所以，将福尔指派问题的决策可变量定义如下：1 表示项目主管是，客户是0 其他情况这里=1， 2， 3；j=1 ， 2， 3使用表 2.1 中的符号和完成时间数据，我们得出了完成时间表达式： 特瑞完成指派所用的总天数卡尔完成指

28、派所用的总天数迈克孟德完成指派所用的总天数3 个项目主管完成时间总和将提供完成 3 个指派所需要的总天数。因此，目标函数如下：最小化指派问题约束反映的情况如下： 每个项目主管将赋予一个客户， 并且每个客户必须被赋予一个项目主管。这些约束条件如下：特瑞的指派卡尔的指派迈克孟德的指派客户 1客户 2客户 3注意：在图 2.1 中每个节点都有一个约束条件。 因为此处的项目主管和客户的人数相等，所以所有的约束条件都可以写成等式。将目标函数和约束条件合并， 于是得到有 9个变量和 6 个约束条件的关于福尔市场营销调查指派问题的线性规划模型。最小化约束条件EMBED Equation.3 EMBED Eq

29、uation.3Equation.3EMBED Equation.3 EMBED Equation.3EMBEDEMBED Equation.3Equation.3EMBEDEMBED Equation.3项目主管客户（起点节点）（终点节点）完成时间10159918614供给 可能的安排（弧）需求图 2.1 福尔市场营销调查指派问题的网状模型特瑞被指派给客户 2（），卡尔被指派给客户 3（）迈克孟德被指派给客户 1）。总共所需要的时间是 26 天表 2.2 对此解决方案做了总结。表 2.2 福尔市场营销调查配置问题中的项目主管最优指派项 目主 管 被 分配 的 客户 天数特 瑞 215卡 尔

30、35迈克孟德6计 262.2.2 指派问题线性规划的一般模型 一般指派问题包括个代理和个任务。如果依据代理是否被指派给任务使或0，并且用来表示代理指派给任务的成本，那么可以将基本指派模型表示如下： 最小化约束条件AgentsTasksall and指派模型是一类特殊的线性规划模型。 这是由线性规划模型的特殊数学结构决定的。每个变量值在一个供给的约束条件和一个需求约束条件中出现， 并且约束条件方程式中的所有系数都是 1和 0。关于配置问题，所有的供给和需求等于 1。因此，最优解必须为整数值，而且整数必须为 0 或12.2.3 EXCEL 实现配置问题第一步是在工作表的底端部分输入指派费用的相关数

31、据。 尽管指派模型 是运输模型中的一个特殊案例，但由于原始供给及目的地需求都等于1，所以没有必要输入原始供给和目的地的相关数据。在工作表的底端部分设计线性规则。 对于所有的线性规划而言， 这种模 型都含有 4 种要素：决策要素、目标函数、左侧值的约束条件及右侧值约束条件。 在配置问题中，决策可变量说明的是一个代理机构能否接受一项任务 （1 为肯定， 0 为否定）；目标函数为所有指派费用的总和；左侧值为指派给每个代理机构的 任务数及被指派到任务的所有代理机构数目； 右侧值为每个代理机构能够解决的 任务数（ 1） 和每个任务所需要的代理机构（ 1）。图 2.2 说明了其公式和解决方法。图2.2 福

32、尔市场研究问题的EXCELS答1）列公式A1:D7 单元格包含了所有的数据及叙述性标志。注意，由于在指派问题中， 供给与需求的价值都等于 1，所以没有输入供给与需求的相关数据。模型位于工 作表的底端，所有的要素都予以涂黑。决策可变量 B16:D18 单元格式为决策可变量保留的。 最优值为所有其它变 量都为零。目标函数在C12单元格内输入公式=B16*B5+C16*C5+D16*D5+B17*B6+C17*C6+D17*D6+B18*B7+C18*C7+D18*M=SUMPRODUBT:D7,B16:D18）。说明完成所有工作的天数，最少的时间为 26 天。左侧值 E16:E18 单元格包含了每

33、个项目领导所能应付的客户的左侧值约 束条件， B 1 9 : D 1 9包含了每个客户必须配给一个项目领导的左侧值约束条件。单元格 E16=SUM求和）（B16:D16）（复制到 E17:E18）单元格 B19=SUM（求和）（B16:B18）（复制到 C19:D19）右侧值 G16:G18 单元格为右侧值项目领导约束条件， B21:D21 为右侧值客 户约束条件，所有右侧值单元格的价值都为 1（2）Excel 的解决方法为了得到图 2.2 的解决方法，在菜单的“工具”种选择“规划求解” ，在对 话框中的“规划求解参数”中输入正确的信息， 如图 2.3 所示。然后选择“选项”。 在图 2.4

34、中，具体说明“采用线性模型” ，“假设非负”的选择。图 2.3 规划求解参数图 2.4 规划求解选项 （ 3）敏感性分析2.3 实验内容 塞尔默公司的营销经理将要主持召开一年一度的有营销区域经理以及销售 人员参加的销售协商会议。 为了更好地安排这次会议， 他雇用了四个临时工 （安、 伊恩、琼、肖恩），每一个人负责完成下面的一项任务：书面陈述的文字处理； 制作口头和书面陈述的电脑图； 会议材料的准备，包括书面材料的抄写和组织； 处理与会者的提前和当场注册报名； 现在他需要确定要将哪一项任务指派个哪一个人。虽然这四个临时工都有完成这四项任务所需的基本能力， 但是在他们完成每 一项任务时所表现出来的

35、有效程度是有很大差异的。 表 2.3 显示了每一个人完成 每一项任务所用的时间（单位：小时） 。最右一列给出了以每个人能力为基础的 小时薪水。表 2.3 塞尔默公司问题的数据临时工每一项任务所需要的时间 （小时）每小时工资文字处理 绘图 材料准备记录安 35 41 27 40 14伊恩 47 45 32 51 12琼 39 56 36 43 13肖恩 32 51 25 46 152.4 实验要求1）求塞尔默公司最优的指派方案（2）根据实验内容自行设计模型，求解最优方案。（3）完成并提交实验报告。2.5 练习娇普肖普公司（Job Shop Company购买了三种不同类型的新设备。但是在 车间里

36、却有五个不同的地点可供安装， 其中某些地点比其他的地点更为需要某些 设备，原因是他们十分接近工作中心， 流入和流出这些设备的工作很多 （新设备 之间并没有工作流）。因此，该问题的目标是把这些设备安装到有效的地点上， 使物料处理成本达到最小。 每一个设备处理原料的单位成本已经在表 2.4 中列出 来。地点 2 不能安装设备 2，所以这里没有给出成本。表 2.4 娇普肖普公司文体中的原料处理成本数据位置 每小时成本（美元）1 2 3 45机器113161214152151320163471067实验三 网络最优化 - 最短路问题网络在各种实际背景问题中以各种各样的形式存在。 交通、电子和通讯网络

37、遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问 题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划 为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助， 广泛 应用于科学、社会和经济活动的每个领域中。法国国家铁路就是一个很好的例子。它每年通过其巨大的铁路网，运载约5000万的乘客。在边沿科学杂志1998年12月期刊中描述了它如何通过网络 最优化问题来适应乘客的喜好， 并且调整日运行量来满足需求。 这些技巧的运用 使每年的收入增加 1500万美元，同时降低了运行成本并提高了服务质量。这个管理科学的应用获得了 1997年弗兰茨厄德曼奖许多网络

38、最优化问题实质上是线性规划问题的特殊类型。 其中最小费用流问 题，也称为网络配送问题， 主要解决如何以最小成本在一个配送网络中运输货物。 最大流问题是涉及诸如怎样使得配送网络中的物流量最大之类的问题。 最短路问 题的目标是为了寻找源地和目的地的最短路（总长度最小的路） 。不是所有的最短路问题都涉及要找从原地到目标地的最短行进距离。事实 上，它们可能根本不涉及行进。 边或弧可能代表了其他类型的活动， 所以选择网 络中的路和选择最佳的序列活动相对应。例如，表示边的“长度”的数字可能表 示活动的成本， 在这种情况下， 该问题的目标就是确定使得这一系列活动的总成 本最小。最短路问题应用的三种类型：（1

39、）行进的总距离最小。（2）一系列活动的总成本最小。（3）一系列活动的总时间最小。3.1 实验目的理解网络最优化问题的特点和实质对于一个最短路问题，能够建立电子表格模型。会运用Excel求解电子表格模型。3.2 案例奎克（Quick）公司获悉它的一个竞争对手计划将把一种很有销售潜力的新 产品投放市场。奎克公司也一直在研制一种类似的产品，并计划在 20 个月后投 放市场。但是，研究临近结束，奎克公司的管理者希望迅速推出产品去参与竞争。现在还有四个没有时间重叠的阶段没有完成， 包括正以正常速度进行剩下的 研究工作（第一阶段） 。然而，每个阶段的实施水平可以从正常水平提高为优先 水平或应急水平， 使之

40、能够加速完成， 而且最后三个阶段中都可以考虑提高实施 水平。第一阶段可以以正常速度也可以加速完成。 表 3.1 列出了在这些水平下所 需要的时间。管理层现在已经给这四个阶段拨款 3000 万美元。每个阶段的费用如表 3.2 所示。管理层希望确定这四个阶段各自应该采取哪一种水平，从而在 3000 万美元预算限制内，使得这种产品可以尽早推向市场表 3.1 准备奎克新产品的各阶段所需时间水平生产和分销正常剩下的研究5 个 月研制制造系统设计开始优先2个月4 个 月3 个 月5 个 月应急1 个月2 个 月2 个 月3 个 月表 3.2准备奎克新产品各阶段的费用（单位：万美元）水平剩下的研究研制制造系

41、统设计开始生产和分销正常30030060000应急90090012003优先5优先2优先3应急1应急5 正常 2应急3优先5优先2优先（目标地）4 优先 2应急3应急1应急源）2 应急 3优先5优先2优先03应急1应急02应急5优先2优先图 3.1 奎克公司的最短路问题描述上图显示了将这个问题作为最短路问题的网络规划。 每一个节点代表了那个 时间点的情况。 除了目标地以外， 每个节点有两个数字表示， 第一个数则代表完 成的阶段，第二个数字代表剩下阶段资金的剩余（单位：百万元） 。每条弧都给 除了完成这个阶段所需要的时间（单位：月） 。源地代表现在，即阶段 0 已完成，还余下全部的 3000万美

42、元的预算。每条 弧代表了那个阶段某一特定努力水平 （在弧上注明） 的选择。 在这个努力水平下 完成这个阶段所需要的时间（单位：月） ，用弧的长度（在弧上注明）表示。选择时间作为弧长的尺度是因为目标是为了使得所有四个阶段所花费的总时间最 小。把网络中某一条路的所有弧长度加起来就得到了对应这条路的方案的总时 间。因此，网络中的最短路就是使得完成所有阶段的总时间最短的方案。最短路问题有且仅有一个目标地。 所以，当网络中实际行进在多于一个节点 结束时，在每个这样的节点和虚拟目标地之间插入一条长度为 0 的弧，从而使得 网络中仍然只有一个目标地。因为指向虚拟目标地的每一条弧的长度都为0，对网络的这些改动

43、不会影响从源地到终点的总路长。图 3.2 奎克公司的最短路问题的电子表格模型图 3.3 规划求解参数图 3.4 规划求解选项图 3.2 是最短路问题奎克问题的电子表格。其中：目标是使总时间最少，所以目标单元格 D32=SUMPROD(UCOTnRoute,Time) 。其他输出单元格( I4 ： I20 )是净流量(流出减流入) , 其中 I4=SUMIFFrom,H4,OnRoute)-SUMIF(To,H4,OnRoute) ，其他同理得到。可变单元格所选路(D4: D30的值1显示的是通过规则求解得到的最优解。点击Solver的按钮以后，可变单元格所选路（D4: D30）表明了哪些弧位于

44、使得总时间最短的路上。因此，最短路为：总长为2+3+3+2+0=10（个月），如总时间（D32）所示。完成这四个阶段的最终方案见表 3.3。虽然这个方案花费了整个总预算 3000 万美元，但是它的确缩短了产品推向市场前的这段时间，从原来计划的 20 个月缩短到仅仅 10个月表 3.3 通过 Execel Solver 软件获得的奎克最短路问题的最优解阶段水平时间成本（万美元）剩 下 的 研 究应急2900研制优先3600应急制造系统设计1200开始生产和分销300优先10合计3000注意：SUMIF(A,B,C)可以将A B C三项相应的数据相加。该函数在计算 网络节点流量时非常有用。在净流量

45、( I4 ： I20 )中输入的等式，用两个 SUMIF 函数的差来计算每个节点产生的是净流量(流出减流入) 。在每一点，第一个 SUMIF函数计算流出节点的流量，第二个 SUMIF函数计算流入节点的流量。比如 I4=SUMIF ( From,H4,OnRoute)-SUMIF ( To,H4,OnRoute) 中 ， SUMIF(From,H4,O nRoute)将On Route ( D4:D30)中的值加总，只要这个值所在行的单 元格来自From( B4:B30)的值与H4的值一样。因为 H4= (0,30)，对应From列 中 B4 B5、B6,所以 On Route 列只加 D4 D

46、5 和 D6,即 D4+ D5+ D6。同样，SUMIF(To,H4,OnRoute)将On Route (D4:D30)中的值加总，只要这个值所在行的单元 格来自TO(C4:C30)的值与H4的值一样。因为H4=(0,30)，没有出现在TO列 中，所以和是0。因此I4的等式就是I4=D4+ D5+ D6,也就是(0,30)电产生的净流量。3.3 实验内容里特城(Littletown )是一个农村的小镇。它的消防队要为包括许多农场社 区在内的大片地区提供服务。 在这个地区里有很多的路， 从消防站到任何一个社 区都有很多条路线。 因为时间是到达火灾发生点的主要因素， 所以消防队队长希 望实现能够

47、确定从消防站到每个农场社区的最短路。 下图标示了连接消防站和其 中一个农场社区的道路系统， 图中包含了每条路的英里数。 你能够找到从消防站 到这个农场社区的最短路线吗？643 1 6 3466535277图3.4里特城的消防站和某一农场社区间的道路系统，其中， A, B,，H是交叉口，每条路旁边的数字表示单位为英里的距离。3.4 实验要求（1）请找出从消防站到这个农场社区的最短路线。（2）根据实验内容自行设计模型，求解最短路问题。（ 3）完成并提交实验报告。3.5 练习莎拉刚刚高中毕业。 在毕业典礼上， 他的父母给了她 21000美元的汽车基金帮助她购买并保养一辆使用了三年的二手车， 以供她上

48、大学使用。 由于开车费用和维修费用随着汽车的老化而飞速上涨， 所以莎拉的父母告诉她在接下来的三个 夏天里，她也可以一次或几次折价将她的汽车置换为其它使用了三年的二手车。 如果她觉得这样做可以使它的总净成本最小的话， 他们会同意她这样做的。 他们 也告诉莎拉， 在四年后，他们会送给她一辆新车作为大学毕业的礼物。 所以莎拉 到那时肯定要计划把旧车折价卖出。下表 3.4 给出了每个时期莎拉购买一辆使用了三年的二手车的相关数据。 例 如，如果她两年后折价卖掉自己的车， 那么在三年级时她就对下一辆车有一年的 所有权，其他情况以此类推。表 3.4 莎拉每个时期购买一辆使用了三年的二手车的数据购买价格拥有年

49、份的开车和保养的费用（美元）最后一年卖出的价值（美元）123412341200020003000450065008500650045003000在接下来的三个夏天里， 什么时候莎拉应该折价卖掉她的汽车 （如果有必要的话）可以使得她在大学四年里买车、开车、保养汽车的总费用最小。实验四 决策分析管理人员经常需要在具有不确定性环境中进行决策。例如：1）制造商向市场推出新产品。这是潜在顾客将会做出什么反应？制造商应当生产多少产品？在决定全面分销前是否需要在一个小区域中进行试销？为了成功推出产品，制造商需要打多少广告？（2）一个金融公司投资有价证券。 那些市场板块和单个有价证券前景最好？ 经济趋势如何？

50、利率会怎样变化？这些因素如何影响投资决策？（3）一个政府工程承包商投标一个新的合同。工程的实际成本是多少？其 他哪些公司会投标？他们可能的投标价是多少？（4）一根农业公司为即将到来的季节选择农作物和家畜的组合。天气状况 如何？价格趋势是什么样的？成本会是多少？（5）一个石油公司决策是否在一个特定地点钻探石油。那里有石油的可能 性有多大？有多少石油？他们需要钻探多深？在钻探前是否需要地质学家做进 一步的勘查？所有这些面临巨大不确定性的决策都是决策分析的使用对象。 当结果不确定 时，决策分析提供了进行理性决策制定的框架和方法。4.1 实验目的理解决策问题的特点对于一个不确定型决策问题，能够建立决策

51、树。会运用TreePlan求解。4.2 案例马克斯弗雷尔是高富布鲁克公司的全资所有人。他将一生的积蓄都花在了 公司上，希望通过发现一个大油田使公司壮大起来。他的公司买了许多块地， 一位咨询地质学家告诉马克斯， 他认为其中有一块 地有 1/4 的概率有石油。马克斯对咨询地质学家的有石油的概率的报告保持怀 疑。在这块地上钻探石油需要大约 100000美元的投资。 如果这块地是干涸的 （没 有石油），整个投资都将会损失。由于他的公司没有多少资金，这个损失将会非 常严重。另一方面，如果这块地蕴含有石油， 咨询地质学家估计那里的石油足够可以 获得约 800000美元的收入。尽管这不是马克斯一直等待的大发

52、现，但还是会给 公司带来相当不错的资金流入，使得公司能够维持运转直到他遇到真正的大发 现。这里还有一个选择。 另一个石油公司听说了这个咨询地质学家的报告， 决定出价 90000 美元来购买这块土地。 这非常诱人。因为这也可以为公司带来不错的 现金流入，而且无需承担 100000 美元损失的巨大风险试用决策树帮他分析这个问题4.1 马克斯的备选方案和预期的收益土地状况利润（美元）备选方案涸有石油 干700000钻探石油-10000090000出售土地90000概率1/43/44.2.1 运用决策树来用图表示和分析问题它的一个非常好的特点是它决策树在对问题图像化以及分析问题时很有用。可以用于需要进

53、行一系列决策的更加复杂的问题分析收益700有石油 1/4钻探1干涸 3/4-100出售90图 4.1 高富布鲁克公司的决策树使用 Excel 的加载宏 TreePlan 在电子表格上进行构建和分析决策树。与其 他 Excel 加载宏一样，这些加载宏需要安装才能在 Excel 中显示出来。4.2.2 用 TreePlan 创建一个决策树第一步选择工具菜单中的“创建新树” （Decision Tree）,如图4.2。创建 得到默认决策树，如图 4.3 。图 4.2 创建决策树图 4.3 默认决策树要改变节点的类型（例如从一个决策节点变成事件节点） 或者添加删除树枝， 点击包含节点的单元格，然后选择

54、工具菜单里的决策树选项，如图 4.4 所示。图 4.4 改变节点类型对话框第二步 要在决策树的末尾创建一个节点，选择包含结束节点的单元格，再 选择工具菜单里的决策树选项。 这样就可以将结束节点转化为含有所希望的树枝 数目（15条）的决策节点或事件节点，如图 4.5所示如果决策是钻探， 下一个事件就是了解这块土地是否有石油。 创建一个事件 节点，点击在钻探树枝末端包含结束节点的单元格， 即那条水平线的右端， 然后 选择工具菜单里的决策树选项。图 4.5 创建节点对话框选择左边的“改变为事件节点”选项和右边的“选择两条树枝”选项，然后 点击“确定”。第三步 决策树上的默认标签（ Decision1,Decision2,Event1,Event2 ），可 以通过点击他们并且输入新的标签来改变。 被替换为“钻探”，“出售”，“有石油” 和“干涸”。第四步 最初，每一条树枝都会有一个自动产生的默认值为 0 的净现金流量（在树枝标签下面出现的数字：如图 D6,D14,H4,H9）。同样，两条树