运筹学历年真题解法汇总
2006年11月第61、63 ● 某公司需要根据下一年度宏观经济的增长趋势预测决定投资策略。宏观经济增长趋势有不景气、不变和景气 3 种，投资策略有积极、稳健和保守 3 种，各种状态的收益如下表所示。基于 maxmin 悲观准则的最佳决策是 （61） 。
（61）A.积极投资 B.稳健投资 C.保守投资 D.不投资 【答案】C
【解析】本题考查的是决策的基本知识，这个建议掌握。
本题属于决策分析范畴。所谓决策，简单地说就是做决定，详细地说，就是为确定未来某个行动的目标，根据自己的经验，在占有一定信息的基础上，借助于科学的方法和工具，对需要决定的问题的诸因素进行分析、计算和评价，并从两个以上的可行方案中，选择一个最优方案的分析判断过程。
根据决策结局的多少，可以将决策分为确定型决策（每个方案只有一个结局）和不确定型决策（每个方案有多个结局）。本题是不确定型决策问题。 由于不确定型决策问题所面临的几个自然状态是不确定，是完全随机的，这使得不确定型决策始终伴随着一定的盲目性，决策者的经验和性格常常在决策中起主导作用。 决策准则包括乐观准则、悲观准则、乐观系数准则和后悔值准则等。
Maxmin 悲观准则是指对于任何行动方案，都认为将是最坏的状态发生，即收益值最小的状态发生。然后，比较各行动方案实施后的结果，取具有最大收益值的行动为最优行动的决策原则，也称为最大最小准则。
题目表中给出的三种投资策略，收益值最小的分别是积极时为 50，稳健时为 100，保守 时为 200，那么最大收益值是 200，即基于 Maxmin 悲观准则的最佳决策对应的行动是保守投资。
● 下图标出了某地区的运输网。
各节点之间的运输能力如下表（单位：万吨/小时）：
从节点①到节点⑥的最大运输能力（流量）可以达到 (63) 万吨/小时。 （63）A.26 B.23 C.22 D.21 【答案】B
【解析】本题考查的是运筹学中求最大流程的问题。
从结点①到结点⑥可以同时沿多条路径运输，总的最大流量应是备条路径上的最大流量之和，每条路径上的最大流量应是其各段流量的最小值。
解题时，每找出一条路径算出流量后，该路径上各段线路上的流量应扣除已经算过的流量，形成剩余流量。剩余流量为 0 的线段应将其删除（断开）。这种做法比较简单直观。例如，路径①③⑤⑥的最大流量为 10 万吨，计算过后，该路径上各段流量应都减少 10万吨。从而①③之间将断开，③⑥之间的剩余流量是 4 万吨，⑤⑥之间的剩余流量是 11 万吨（如下图）。
依次执行类似的步骤，从结点①到⑥的最大流量应是所有可能运输路径上的最大流量之和： (1)路径①③⑤⑥的最大流量为10 万吨： (2)路径①②⑤⑥的剩余最大流量为6 万吨； (3)路径①④⑥的剩余最大流量为5 万吨； (4)路径①④③⑤⑥的剩余最大流量为1 万吨； (5)路径①④②⑤⑥的剩余最大流量为1 万吨。 从而，从结点①到⑥的最大流量应是 23 万吨。
按照习惯，每次应尽量先找出具有最大流量的路径。理论上可以证明，虽然寻找各种路径的
办法可以不同，运输方案也可以有很多种，但总的最大流量值是唯一确定的。
2007年11月第69、70 ● 某车间需要用一台车床和一台铣床加工 A、B、C、D 四个零件。每个零件都需要先 用车床加工，再用铣床加工。车床与铣床加工每个零件所需的工时（包括加工前的准备时间 以及加工后的处理时间）如下表：
若以 A、B、C、D 零件顺序安排加工，则共需 32 小时。适当调整零件加工顺序，可使 所需总工时最短。在这种最短总工时方案中，零件 A 在车床上的加工顺序安排在第 （69） 位，四个零件加工共需 （70）小时。 （69）A. 1 B. 2 C. 3 D. 4 （70）A. 21 B. 22 C. 23 D. 24 【答案】C、B
【解析】本题考查的是活动排序的相关问题，掌握。
对于指定的加工顺序，如何描述其加工所需的时间（加工进度计划）呢？这是解答本体首先需要解决的问题。 分析一：
车床 C2 D4 A8 B6 这1小时 C3 D12 A3 B1
分析二：
以顺序安排加工 A、B、C、D 这四个零件为例，人们可以用甘特图将工作进度计划描述 如下：
其中横轴表示时间，从零件 A 在车床上加工开始作为坐标 0，并以小时为单位，纵轴表 示车床和铣床。
车床和铣床加工某零件的进度情况（从某一时刻到另一时刻）以横道表示。
在车床上，零件 A、B、C、D 一个接一个顺序加工，所需要 8+6+2+4=20 小时。 在铣床上，零件 A 只能等车床加工完 A 后才开始，所以，其横道的横坐标为 8—11；零
件 B 只能等车床加工完 B 后才开始，所以，其横道的横坐标为 14—15；零件 C 只能等车床加工完 C 后才开始，所以，其横道的横坐标为 16—19；零件 D 智能等车床加工完 D 后才开始，所以，其横道的横坐标为 20—32.
这样顺序加工 A、B、C、D 零件总共需要 32 小时。
从上例看出，为缩短总工时，应适当那个调整加工零件的顺序，以缩短铣床最后的加工 时间（车床完工后还需要用铣床的时间），并缩短车床最先的加工时间（铣床启动前需要等 待的时间）。所以应采取如下原则来安排零件的加工顺序。
在给定的工时表中找出最小值，如果他是铣床时间，则该零件应最后加工；如果他是车 床时间，则该零件应最先加工。除去该零件后，又可以按此原则继续进行安排。按此原则， 本体中，最小工时为 1 小时，这是零件 B 所用的铣床加工时间。所以，零件 B 应放在最后加工。除去零件 B 后，最小工时为 2 小时，这是零件 C 所需的车床加工时间，所以，零件 C应最先加工，再除去零件 C 以后，工时表中最小的时间为 3 小时，是零件 A 所需的铣床加工时间。因此，零件 A 应安排在零件 D 以后加工，这样，最优方案影视 C、D、A、B 零件的顺序来加工，甘特图如下：
在车床上，零件 C、D、A、B 一个接一个顺序加工，需要 2+4+8+6 =20 小时。
在铣床上，零件 C 只能等车床加工完 C 后才开始，所以，其横道的横坐标为 2—5；零 件 D 只能等车床加工完 D 后才开始，所以，其横道的横坐标为 6—18；零件 A 可以再铣床加工完 D 后立即开始（此时车床已经加工完零件 A），所以，其横道的横坐标为 18—21；零件B 可以再铣床加工零件 A 后立即开始（此时车床已加工完零件 B），所以，其横道的横坐标为 21—22.
这样按 C、D、A、B 零件顺序进行加工，总共只需要 22 小时，这是最优方案。
2008年5月第66-69 ● 下图标明了六个城市（A～F）之间的公路（每条公路旁标注了其长度公里数）。为将部分公路改造成高速公路，使各个城市之间均可通过高速公路通达，至少要改造总计（66）公里的公路，这种总公里数最少的改造方案共有（67）个。 （66）A. 1000 B. 1300 C. 1600 D. 2000 （67）A. 1 B. 2 C. 3 D. 4
【答案】(66) B (67) C
【解析】本题考查的是求方案和最小成本的问题，这个尽量掌握吧。偶尔考
从图论上看，本题要求得到上图的最小支撑树(即选取部分边，使其保持连通，又使其 总长度最小)。
如下算法可以逐步实现这个要求。
任取一点，例如 A，将其纳入已完成部分。点 A 与其他各点中的最小距离为 AE=200.从而将边 AE 以及点 E 纳入已完成部分。点 A, E 与其他各点 B, C, D, F 这两个集合之间的最段距离为 AB=AF=300，从而可以将边 AB 与点 B(或边 AF 与点 F)纳入己完成部分。点 A, B, E 与点 C, D, F 两个集合的最短距离为 AF=BF=300，从而可以将边 AF (或边 BF)与点 F 纳入已完成部分。点 A, B, E, F 与点 C, D 两个集合之间的最段距离为 FD=200，从而将边 FD 与点 D 纳入已完成部分。点 A, B, E, F, D 与点 C 两个集合之间的最短距离为 CD=300，从而将边 CD 与点 C 纳入已完成部分。 此时，所有 6 个点都已经接通，其边为 AE, AB, AF, FD. CD，总长度为 1300(如下图所示)。
连通这 6 个点的边至少需要 5 条，最短总长等于 2 个 200 以及 3 个 300。图中共有 4 条边长 300，其中，CD 边在最短总长度方案中不可缺少，而 AB, BF, AF 中可以任选 2 条。因此，共有 3 个最短总长度的方案。除了上面给出的外，还可以有两种(如下图所示):