运27第7章习题

习 题

2. 就下面的全整数线性规划作答：

max 5x1 + 8x2 s.t．

6x1 + 5x2≤30 9x1 + 4x2≤36 1x1 + 2x2≤10

x1 ,x2≥0且为整数

a． 画出本题的约束条件，并用点号表示可行的整数解。 b． 求出LP松弛的最优解。进一步近似，以求其可行的整数解。

c． 直接求解最优整数解。比较（c）和（b），看它们所求得的结果是否一致。

4．就下面的全整数线性规划作答：

max 10x1 + 3x2 s.t．

6x1 + 7x2≤40

3x1 + 1x2≤11

x1 ,x2≥0且为整数

a． 列出本题的LP松弛的式子，并求解。使用图解法求解，并作近似，以求

出它的一个可行解。指出最优解的上限值。

b． 使用图解法求出本整数线性规划的解。比较图解法求出的解和（a）中求 出的结果。

c． 假设目标函数变为max 3x1 + 6x2 。重新求解（a）和（b）。

6．就下面的混合整数线性规划作答：

max 1x1 + 1x2 s.t．

7x1 + 9x2≤63 9x1 + 5x2≤45 3x1 + 1x2≤12

x1 ,x2≥0且x2为整数

a. 画出本题的约束条件，并在图上标出所有可行的混合整数结果。

b. 求LP松弛的最优解。取x2 的近似值，从而得到一个可行的混合整数解。求解本规划问题最优解的上下限。

c. 求解问题的最优结果。

8．斯宾塞公司需要从下列一系列投资方案中进行选择。下面列出了所有可能的方案，

以及对应的未来回报的净现值、需求资金以及3年中的可用资金：

可能选择 净现值 需求资金（美元） 2年 1000 3500 3年 4000 3500 可能选择 基础研究 买入新设备 净现值 （美元） 1年 8000 3000 5000 1000 需求资金（美元） 2年 1000 500 3年 4000 900 （美元） 1年 小规模仓库扩建 4000 大规模仓库扩建 6000 3000 2500 测试新产品市场 10500 广告活动 4000 6000 2000 4000 1500 5000 1800 可用资金 10500 7000 8750 a． 构建该问题的整数线性规划模型，以求得最大的净现值。

b． 假设只能有一个仓库扩建方案可行，重新构建整数线性规划模型。 c． 假设，如果将新产品投放市场，则需要进行广

告活动。此时，请重新构建一个整数线性规划 模型。

10．格雷夫市打算迁移其某些警察分局，来通过改变警 察分局的布局实现加强管制高犯罪率地区的效果。 右表是所考虑的地点以及这些地点所能管制到的

区域。

可能的分部地址 A B C D E 覆盖区域 1,5,7 1,2,5,7 1,3,5 2,4,5 3,4,6 F 4,5,6 a． 构建一个整数线性规划模型，以最少数目的地

G 1,5,6,7 点覆盖所有区域，及最有选址问题。

b． 求解上面的线性规划模型。

12．叶慈公司为各郡高速公路部门供盐。叶慈共有3辆卡车，其中两辆载重15吨，另外一

辆载重30吨。公司的决策人员安排明天向波克、达拉斯和贾斯汀3郡供盐。根据卡车的载重量，则两个郡将各收到15吨盐，而另一个郡收到30吨盐。决策者需要决定需要分别向3各郡各送多少盐。令：

P—运往波克郡的吨数；

D—运往达拉斯的吨数；

J—运往贾斯汀的吨数；

1，如果30吨的卡车分配给i郡 Yi= 0，其他

a． 利用这些变量的定义，列出运到各郡的盐的数量约束条件。

b． 30吨的卡车到达3郡的派遣成本不等，分别是：波克100美元，达拉斯85美元，

贾斯波50美元。构建一个混合整数线性规划模型，并求解需要向各郡运输多少吨

盐。

14． 一家汽车制造商拥有5家陈旧的工厂，

分布如下：

密歇根、俄亥俄、加利福尼亚3州 各有一家，纽约有2家。现在管理层打算更新这些工厂以生产一种新型轿车的发动机组和变速器。更新每家工厂的成本和更新后的生产能力如右表。

工厂所在的州 密歇根 纽约 纽约 俄亥俄

加利福尼亚

更新成本 发动机组 变速器 （100万美元） （1000个） （1000个）

25 35

35 40 20

500 800 400 900 200

300 400 800 600 300

假设需要达到900 000个发动

机组和900 000个变速器的总生产能力。问：管理层需要更新那些工厂以达到预定的总生产能力，并且同时使更新的总成本最小。

a． 列出所有可供管理层选择的组合，并指出每种组合中发动机组个数和变速器的个数，并判断每种组合是否能达到预定的生产需要。求出按每种组合更新后的成本。 b． 观察（a）中的结果，对该公司管理层提一些建设性建议。 c． 构建一个0—1整数规划模型，求解本问题的最优解。

d． 求解（c）中构建的模型。

16． 北海岸银行打算为其全职出纳和兼职出纳制定一个有效的工作时间表。时间表须能让

银行有效运作，考虑到提供足够多的客户服务、员工休息等诸多因素。该银行周五营业时间为上午9:00到下午7:00。下面列出周五各个时间段内为提供足够的客户服务所需要的出纳员的数量。

工作时间 上午9:00~上午10:00 上午10:00~上午11:00 上午11:00~正午 正午~下午1:00 下午1:00~下午2:00 出纳员数量 6 4 8 10 9 工作时间 下午2:00~下午3:00 下午3:00~下午4:00 下午4:00~下午5:00 下午5:00~下午6:00 下午6:00~下午7:00 出纳员数量 6 4 7 6 6 每个全职员工需要从整点开始工作，连续工作4个小时后，是一个1小时的午餐时间，然后继续工作3个小时。兼职员工需要从整点开始工作，连续工作4个小时。全职员工和兼职员工的工资和额外福利不一样，因此银行使用全职员工和兼职员工的成本也不一样，分别为每小时15美元（每天105美元）和每小时8美元（每天32美元）。 a． 构建一个整数线性规划模型，以使用最少的人力成本并且以满足顾客服务为目标，构建一个可行的时间表。（提示：令xi 表示第i点钟全职员工开始工作的人数；yi 表示第i点钟兼职员工开始工作的人数。） b． 求解（a）种模型的LP 松弛。

c． 求解出纳员的最优时间表，并解释结果。

d． 考察（c）中求出的结果后，银行经理意识到需要额外提出如下一些要求：每个时

间段内至少要有一个全职员工，而且在所有员工中至少包括5个全职员工。重新构建模型以满足这些要求，并求出最优解。

18．参考第8.3节塞伦食品公司的份额选择例子，回答下面问题、据说国王牌有意退出冷冻

比萨饼业务。此时，塞伦公司的主要对手就变成了安东尼奥比萨饼。 a． 计算安东尼奥比萨饼对表7—4中每位顾客的总效用。

b． 假设安东尼奥牌比萨饼是塞伦的唯一竞争对手，列出能最大化市场份额的选择

问题并求解。最佳的产品设计是什么？将会取得多大的市场份额？

19．参考第14题。管理层认为对纽约工厂的更新成本低估了。假设每个工厂的更新成本均

为4 000万美元，解答如下问题：

a． 结合如上成本的变化，重新构建整数线性规划模型。

b． 根据上面的变化，就此更新计划给管理层提一些建设性建议。

c． 根据新的成本数据，重新求解。管理层认为在同一州关闭两家工厂是不可能的，则如何把这一政策约束加入到你的0—1整数规划模型中去？

d． 基本成本的改变和（c）中的政策约束，你会给管理层提供什么建议？

22． 三角洲集团是一家卫生保健行业的管理咨询公司。他目前打算组建一个小组以研究可

能的新市场，并通过构建线性规划模型来选组员。主管要求组员只能为3、5或7人。组员并不知道如何在模型中体现这个要求。构建的模型要求组员从3各级顶部门抽选，并使用如下变量定义：

x1—从部门1抽选的人数；

x2—从部门2抽选的人数；

x3—从部门3抽选的人数。

试写出约束条件来保证这个组由3、5、或7个人组成。必要时采用的整数变量：

如果3个人分成一组，则y1 =1, 否则y1 =0;

如果5个人分成一组，则y2=1, 否则y2 =0; 如果7个人分成一组，则y2 =1, 否则y2=0。

24．影剧院的管理者使用一个名为SilverScreener 的数学规划系统（属于0—1整数规划模

型）来求解多银屏剧院（一个剧院有多个放电影的银屏）一周内电影播放节目的计划安

排问题（Interfaces，2001年5/6双月刊）。现在，假设谷电影集团的管理层想要调查研究一下，在不同多银屏剧院采用类似的放映计划有何潜在差别。谷电影公司的管理层选择了一个有2个银屏的小型剧院作为研究的样本剧院。研究打算构建一个整数规划模型来帮助制定随后4周的电影放映计划时间表。共有6部电影可以选择放映。下面列出了第一周和最后一周可以放映的电影以及每部电影最多可以播放的周数等信息。

电影编号

1 2 3 4

第一周可以放映的电影

1 1 1 2

最后一周可以放映的电影

2 3 1 4

每部电影最多可以放映的周数

2 2 2 2

5 3 6 3 6 3 5 3

样本剧院的全部电影播放计划时刻表由6部电影的单个的计划播放时刻表组成。每

部电影的计划播放时刻表需要包括以下具体内容：该部电影应该从哪周开始放映，该部

电影在哪几周连续播放。例如，电影2可以采取如下放映计划时间表：在第一周开始放映，并且连续放映2周。剧院的政策是：一旦一部电影开始放映，则它必须连续放映几周，不能有所中断或重新开始。可以使用下面的决策变量来表示每部电影可能的计划时间表：

1, 如果电影i 从第j 周开始连续放映w周

xijw = 0，其他

例如：x532 =1表示电影5在第3周开始放映，并且连续放映2周。为每部电影每个可能的计划放映表分配一个独立变量。

a． 现有3个放映计划和电影1有关。列出代表这3个放映计划的变量表达式。 b． 写出一个约束条件来表达：电影1只能选择一种放映计划。

c． 写出一个约束条件来表达：电影5只能选择一种放映计划。

d． 是什么因素限制了第一周所能播放的电影数？写出一个约束条件来限制第一周可以放映的电影总数。

e． 写出一个约束条件来限制第一周可以放映的电影总数。

案例分析1 课本出版

ASW出版公司是一家小型大学课本出版公司，它目前需要对来年将出版的教材科

目做出决策。以下为考虑出版的书籍和对应书籍3年中的预期销售量。 各学科教材 商务微积分 书籍类型 新书 预期销售量 （1000美元） 20 各学科教材 金融学 书籍类型 新书 预期销售量 （1000美元） 18 有限数学 普通统计学 数理统计学 商务统计学 修订本 新书 新书 修订本 30 财务会计 新书 25 管理会计 修订本 15 50 英语文学 新书 10 20 德语 新书 25 30 被列为修订本的书是已经与ASW签了合同的，并将考虑以新版本发行的书。列为新书的书是已由该公司审阅过，但是合同还未签。

该公司现有3个人可接受这些任务。他们的可用时间不同：约翰有60天可用，苏

珊与莫尼卡都有40天。每个人完成每项任务需要的天数在下表中列出。例如，如果要出版商务微积分，就需要30天约翰的时间和40天苏珊的时间。“X”表示此任务不需要此人。注意，除了金融学，其他每项任务都需要至少两人参与。

各学科教材 商务微积分 有限数学 普通统计学 数理统计学 约翰 30 16 24 20 苏珊 40 24 X X 莫尼卡 X X 30 24 各学科教材 金融学 财务会计 管理会计 英语文学 约翰 X X X 40 苏珊 X 24 28 34 莫尼卡 14 26 30 30 商务统计学 德语 10 X 16 X 50 36 ASW在一年中不会出版两本以上统计学的书和一本以上会计学的书。而且，已决定必定在两本数学书（商务微积分和有限数学）中出版一本，但不会都出版。

管理报告

为ASW的管理编辑写一份报告，说明你关于下一年最优出版方案的决定和建议。在你的分析中，可以假设所有书每本的固定成本和销售收入是相同的。管理人员最关心的是销售总数量的最大化。

管理编辑还要求你的建议考虑到以下可能的变化：

1. 如果必要，苏珊可以从另一任务中抽调出12天的时间。

2. 如果必要，莫尼卡也可再提供10天的时间。

3. 如果一些修订本可以推迟一年出版，应推迟吗？很明显，这样公司会有丢失市场的危险。

在你的报告中请附上你分析的详细细节。

案例问题2 伊戈国有银行

通过直接大胆的邮件促销方法和低介绍利率，伊戈国有银行（YNB）在全美国建立了一个庞大的信用卡客户基础。目前，所有客户都定期把款项寄到该银行在北卡罗莱纳夏洛特的法人办事处。这种客户定期付款的日收款量是巨大的，平均近600 000美元。YNB估计这项资金将达到它总资金的15%，所以想要尽快将这些客户款项划归到银行的账户上。例如，如果从一个客户的款项邮寄、审查、直至划归到银行的账户中共需要5天，YNB潜在中就损失了5天的利息收入。尽管这一收款过程的时间不可能完全消除，但是，如果款项十分巨大，则缩短这一时间是非常有利的。

顾客区 “带锁的箱子”所在州 日集资（千美元）

菲尼克斯 西北 西南 中部 东北 东南 4 2 5 5 4 盐湖城 2 3 3 4 6 亚特兰大 4 4 3 3 2 波士顿 4 6 4 2 3 80 90 150 180 100 为了避免所以信用卡客户都把款项寄到夏洛特，YNB考虑让客户吧款项寄到一个或多个地区性收款中心，也就是银行业中所说的“带锁的箱子”。四个“带锁的箱子”被提议建在菲尼克斯、盐湖城、亚特兰大和波士顿。为了决定开辟哪些“带锁的箱子”以及客户应该把款项寄到哪里，YNB特意把它的客户基础分成了5个地区区域：西北、西南、中部、东北和东南。处于同一区域的客户将被告知把他们的款项寄到同一个“带锁的箱子”。下表给出了款项从各个区域寄到各可能的“带锁的箱子”银行账户前，平均所需要的天数。

管理报告

戴维??沃尔夫，现金管理副行长，要求你做一份关于最优带锁箱子的数量和建设地点的报告。沃尔夫最关心的是利息收入损失最小化，但是你也需要考虑每年维持一个带锁箱子的费用。尽管目前我们不知道具体的费用，但我们可以假设各地的费用都在20 000~30 000美元之间。一旦选定了合适的地点，沃尔夫会查询其费用。

案例问题3 含有更换成本的生产计划

巴克艾制造厂生产一种卡车制造中所用到的发动机头。该生产线十分复杂，长达900英尺，能够生产两种型号的发动机头：P头和H头。P头用于重型卡车，而H头用于小卡车。由于生产线在一个时间点上只能生产一种型号，所以生产线要么设置成生产P头，要么设置成生产H头，而不能同时生产两种。每周末更换一次：从生产P头设置转换到生产H头设置的成本是500美元，反之亦然。当生产P头时，每周最多可生产100件，而H头，每周最多可生产80件。

巴克艾刚刚完成了生产P头的设置。管理者需要为随后的8周制定生产和设置更换计划。目前，巴克艾库存中有125件P头和143件H头。库存成本按库存价的19.5%计算。P头的生产成本是225 美元，H头的生产成本是310美元。制定生产计划的目的是使生产成本、库存成本与更换成本之和达到最小。

巴克艾已经收到一家发动机装配厂9周内的需求计划，如下：

产品需求量 周次 P头 1 2 3 4 5 55 55 44 0 45 H头 38 38 30 0 48 6 7 8 9 周次 P头 45 36 35 35 H头 48 58 57 58 产品需求量 安全库存量要求每周末时库存至少要达到下周需求量的80%。

管理报告

为巴克艾制造厂的管理层制定一个随后8周的设置更换与生产的计划时间表。计划时间表中需要说明总成本中有多少是生产成本，有多少是库存成本，有多少是更换成本。

本文来源：https://www.bwwdw.com/article/kvvh.html