习题
2．考虑下面这个运输问题的网络模型：
得梅因 14 30 杰斐逊城 7 堪萨斯州 8 10 20 奥马哈 5 圣路易斯 供给 9 25 15 10 需求 此网络图注明了每个节点的供给量和需求量以及单位运输成本。
a. 为这个问题构建一个线性规划模型，记得在模型中定义所有的变量。、
b. 求解这个线性规划模型，找出最优解。 4．阿挪富制造商生产中央处理器（CPU），这些CPU是在西雅图、哥伦比亚和纽约生产的并被运到位于匹兹堡、莫比尔、丹佛市、洛杉矶和华盛顿市的仓库中，以等待进一步的销售。以下所示的运输表显示了每一工厂所能提供的CPU数据。同时，每个单元各种的数据表示由生产地运到每个仓库的运输成本（美元／单位）。 工厂 西雅图 2 哥伦比亚 1 纽约 需求量 3000 5000 4000 6000 3000 10 仓库 匹兹堡 10 莫比尔 丹佛市 20 5 洛杉矶 9 华盛顿 供给量 10 9000 8 30 6 4000 20 7 10 4 8000 21000
a. 设计一个表示该问题的网络图。
b. 确定每个工厂运送多少货物到每个仓库中去、使得总的运输成本最低。
c. 匹兹堡仓库新近增加了1000个单位的订单，且阿挪富已授权匹兹堡工厂增加1000
个单位的生产量。这一变化将导致总运输成本增加还是减少？请求出一个新的最佳解决方案。
6．克雷尔化工厂公司生产一种特殊的油基原料。最近此原料非常短缺，克雷尔公司的4个客户已经下了订单，总额超过了克雷尔公司旗下的两个工厂的生产能力。克雷尔公司的管理层要决定给每个客户多少单位的原料。因为这4个客户属于不同的行业所以基于行业的价格结构不同，可以向他们收取不同的 工厂 克利夫·斯普林丹威尔 客户 D1 D2 D3 D4 $32 $34 $32 $40 $34 $30 $28 $38
原料价格。然而，两个工厂的生产成本不同，工厂与客户之间的运输成本也不同，所以，这使得“卖给最高出价者”的决策并不可取。综合考虑价格、生产成本和运输成本之后，克雷尔公司计算出下表中所示的每个工厂—客户组合中每单位原材料的利润率。工厂的生产能力 以及客户的订单如下所示：
工厂的生产能力（单位） 客户的订单（单位） D1 2000 克利夫·斯普林 5000
D2 5000
D3 3000 丹威尔 3000
D4 2000 为了最大化公司利润，每个工厂给每个客户提供多少单位的的产品？哪个客户的需求将不被满足？构建网络模型和线性规划模型。
8.幺点制造公司收到3种类似的产品的订单：
产品 订单（单位）
A 2000 B 500
C 1200 该公司有3套设备可以以同样的生产率制造这些产品。然而，由于每套设备生产每种产品的次品率不同，所以产品的单位成本也不同，这取决于所使用的机器。下个星期设备的生产能力以及单位生产成本如下所示：
产品（美元） 设备 生产能力（单位） 设备 A B C 1 1500 1 1.00 1.20 0.90 2 1500 2 1.30 1.40 1.20 3 1000 3 1.10 1.00 1.20 利用运输模型为产品和设备开发一个最低成本的生产计划方案。写出线性规划模型。 10.地毯安装公司为金融大厦销售和安装地毯。布拉德是这家公司的业务主管，他刚刚获得5个项目的合同，现在必须给每个项目分配一组工作人员。因为布拉德所获得的佣金取决于地毯安装公司的利润，他将决定如何分配以使得总的安装成本最小。目前，有5个安装小组可以被分配，每个小组用颜色来编号。下面这个表格显示了每个小组完成每个项目所需要的时
间： 红色 白色 小组 蓝色 绿色 项目 1 2 3 4 5 30 44 38 47 31 25 32 45 44 25 23 40 37 39 29 26 38 37 45 28 棕色 26 34 44 43 28 a.设计一个表述该问题的网络图。 b.构建一个该问题的线性规划模型，并求解得出使总成本最小的最优解。
12.美国电缆公司利用包括5个分销中心、8个客户区域的分销系统分销产品。配给每个客户区域一个专门的资源供应商，且其所有电缆产品都来自同一分销中心。为了能平衡分销中心的客户需要和雇员的工作量，公司负责物流的副总裁特别指明一个分销中心最多负责3个客户区。下面的表格就是这5个分销中心以及每个客户区的供给成本（单位：1000美元）： A．求出能使总成本最小的客户区—分销中心的组合方式。 b．如果有，哪一分销中心没有分派任务？
c．假设每个分销中心最多只能负责2个客户区，那么这个限制条件将如何改变指派和客户区的供给成本？ 分销中心 普莱诺 纳什维尔 弗拉各斯塔夫 斯普林菲尔德 博尔德 客户区 洛杉矶 芝加哥 哥伦比亚 亚特兰大 纽约 堪萨斯 丹佛 达拉斯 70 47 22 53 98 21 27 13 75 38 19 58 90 34 40 26 15 78 37 82 111 40 29 32 60 23 8 39 82 36 32 45 45 40 29 75 86 25 11 37 14.美国中西部大学的管理科学系主任计划在下一个秋季给每门课分配教授。4门核心课程需要分配教授，分别是UG、MBA、MS和Ph.D.水平的课程。有4位教授可以被分配，每位教授只接一门课。已知前一个学期学生对教授的评价分5个等级：4（优秀）、3（好）、2（一般）、1（及格）、0（不及格）。每个教授的平均得分如下表。
教授D没有获得博士学位，因此不能教授Ph.D.水平的学生，所以D—Ph.D.这个组合是不可接受的。如果系主任基于最大化4门课总的学生评价来分配教学任务的话，那么该如何分配教授？ 教授 A B C 课程 UG MBA MS Ph.D. 2.8 2.2 3.3 3.0 3.2 3.0 3.6 3.6 3.3 3.2 3.5 3.5 3.2 2.8 2.5 — D 16.海齐公司的5个部门在生产过程中使用一种叫Rbase的化学物质，这种物质只有6个供应商能够满足海齐公司的质量控制标准。所有6家供应商都可以生产足够的Rbase满足海齐公司任一部门的要求。下表显示了海齐公司不同部门对Rbase的需求量，以及不同供应商每加仑Rbase的报价：
部门 需求量 1 40
2 45 3 50 4 35 5 45
供应商 每加仑单价（美元）
1 12.60 2 14.00 3 10.20 4 14.20 5 12.00 6 13.00
下表显示了从不同供应商到不同部门的每加仑Rbase的运输成本（单位：美元）： 部门 1 2 3 4 5 供应商 1 2 3 4 5 6 2.75 2.50 3.15 2.40 2.75 2.75 0.80 0.20 5.40 1.20 3.40 1.00 4.70 2.60 5.30 2.80 6.00 5.60 2.60 1.80 4.40 2.40 5.00 2.80 3.40 0.40 5.00 1.20 2.60 3.60 海齐公司坚信，将其采购分散给不同的供应商会减轻公司对供应商的依赖（例如，供应商发生罢工或者原材料短缺都不会对公司造成太大的影响）。公司的这种政策需要每个部门都不必须有一个独立的供应商。
a.对每组供应商—部门组合，计算出满足部门需求的总供给成本为多少？ b.得出最优的供应商—部门指派。
18.参考第17题。假设两个仓库之间的运输成本被限制在每单位2美元，且直接从工厂3运输到客户区4的单位成本为7美元。 a.设计该问题的网络图。
b.构建该问题的线性规划模型。
c.求解最优的运输方案。
20.摩尔·哈曼公司正在从事谷类买卖业务。该公司此业务一个非常重要的方面就是把买来的谷物运送到客户手中。如果公司能够保持低水平的运输费用，那么公司的利润将会更高。 目前，公司在印第安纳州的曼西和巴西城各买了3车皮和6车皮的谷物，在俄亥俄洲的齐尼亚购买了5车皮的谷物。公司已经销售出去12车皮的谷物。各地区名字以及该地区销售出去的数量如下表所示。
所有装运的货物都必须取道路易斯维尔或辛辛那提运往目的地。下表所示的是从起点到路易斯维尔和辛辛那提的每蒲式耳的运输费用（单位：美分），以及从路易斯维尔和辛辛那提到目的地的每蒲式耳的运输费用（单位：美分）。 地点 销售车皮数
梅肯，佐治亚州 2 格林伍德，南卡罗来纳州 4
康科德，南卡罗来纳州 3 查塔姆，北卡罗来纳州 3
35 22.某出租车公司的7个分店的汽车分布不均匀。下面的网络图显示了分店分布（节点）和分店之间运输一辆汽车所需的成本。节点上的正数表示该节点的过量供应的部分，负数表示该节点过量需求的部分。
+5 30 2 20 -8 25 30 15 25 20 3 +3 5 +2 35 28 45 45 -3 4 27 7 1 12 6 -5 a. 设计一个线性规划模型来修复分店之间的平衡。
b. 求解（a）部分建立的模型，并确定应该如何在各个分店重新指派这些汽车。
24.在开始的Gorman建筑公司问题中，我们找到了从办事处（节点1）到坐落在节点6的建筑地点的最短距离。由于一些道路是高速公路，另外一些是城市街道，所以办事处与建筑地点间最短距离的路径未必能给出最快或最短的路径时间。这里所显示的是Gorman的道路网络图，弧上的标注是行程时间，而不是距离。如果目标是最小化行程时间，而不是距离，找到从Gorman的办事处到坐落在节点6的建筑地点的最短路径。
行程分钟数 25 2 40 1 36 3 15 5 6 12 4 8 6 11 23
26.摩根运输公司在4个州的范围，即芝加哥和6个其他城市之间经营一项特殊的快速投递