项目管理师运筹学常见考点

解答运筹学题目三个要点：

首先要知道考的是哪类问题，从而选择合适的算法

尽可能用穷举法和排除法，选择题不追求过程只要结果

不可恋战，考试时间有限，运筹学题目再复杂也只有1分。

1. 最大流量问题

总运输能力，首先要留意结点间双向运输能力是否相同，把运输能力数据标在图上。

然后寻找首尾两节点运输能力最大的那条路径。路径上扣除该最大值，剩余流量为0的线段则将其删除。

继续寻找首尾结点运输能力最大的那条路径，累加总运输能力，剩余流量为0的线段则将其删除。

重复上述步骤，直到首尾结点间再无通路。总运输能力也就是前面各流程相加的结果。

2. 最小生成树问题

无向连通图最小生成树问题－任取一点，将其纳入已完成部分。将其与其他结点最小距离找出，将对应的边和结点纳入已完成集合部分。

寻找该结点集合与剩余结点集合之间最短距离，任选其一，纳入已完成部分。

如此循环，直到所有结点均已连通，将这些边的权值。

3. 排课表问题

图示建模法，将各课程看成是结点，不能安排在同一天考试它们之间划一条直线。同一人任何两门都不能放在同一天应画出连线。

这样同一天可安排的课程就是没有连线的结点。看线的单独结点和重复结点决定选项。

集装箱不能放在一起的物品选出连线最多的结点放入第一箱，辅之以没有与该结点连线的集装箱。然后看其它结点分配情况。

4. 最短路径问题

可转化为网络图，Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

该最短路径算法的思想：最短路径的任意一段都是局部最优的。

若序列(Vs, V1, V2, ..., Vt-1, Vt)是从Vs到Vt最短路径，则序列(Vs, V1, V2, ..., Vt-1)是从Vs到Vt-1的最短路径。

TSP问题要求经过每个城市一次且仅一次。

5. 线性规划－认真审题求最大还是最小

求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。

可行解：满足线性约束条件的解(x,y)叫可行解。

可行域：由所有可行解组成的集合叫做可行域。

最优解：使目标函数取得最大值或最小值的可行解叫做线性规划问题的最优解。

图解法是解决线性规划问题最直观常用的方法，但考试时经常用线性规划问题最优解的特点通常是约束线的交点。三个交点分别算出，求最满足约束条件的最优解。

两个约束条件，最优解就是二者的交点。

三个变量的规划时，考虑单位利润率，可以对题目进行简化。单位利润率最低的不考虑生成。

试题类型：至少需要原材料，最多获得利润

6. 工序问题

最简单的两道工序，每道工序一台设备。解法：首先找到各道工序最小工时，看这个值是前一道工序还是后一道工序，如果是前一道工序则该零件应尽早加工，如果是后一道工序该零件则应最后加工。

若有两个数字相同且为最小怎么办？如果两个最小数字在不同工序，前一道工序最小的放前面，后一道工序最小的放后面；如果两个最小的都存在于同一道工序，看这两个工序在另一道工序的顺序；如果仍然相同，则无所谓先后次序了。

找出加工顺序后，可以使用甘特图来计算工时，或者使用网络图关键路径圈工时。

一些2*2的简单工序可以用穷举法进行，超过三个工序可以从首尾工序角度去确定顺序

7.分配问题－平均收益法

计算单位投入平均收益，将有限的资源优先投入到单位收益高的销售点。

先考虑简单场景，不转运得出一个结果，再逐步扩展。

各种分配问题的思路是一致的，就是让人去做他最擅长的工作。

8. 边际收益法

变动成本法、差值法，也叫伏格尔法，主要思路：求运费最便宜和次便宜之间的差，先满足运费差值大的。最小运费求值

方法原理：某产地产品如不能按最小运费就近供应，就考虑次小运费，这就产生一个差额；差额越大，说明不能按最小运费调运时，运费增加越多；因而对差额最大产地，就应当采用最小运费调运。

最小运费求值－步骤是增加变动成本计算，计算出每列最小成本与次小成本的差值－变动成本大的优先分配，分配完的机型去掉，调整任务剩余量－持续进行，将最小成本对应的机型分配出去，直到分配完所有机型－列出表格计算总成本。

边际收益法构造边际收益矩阵（变动收益矩阵－每增加一个X能带来的收益），主要用于边际利润不变或递减情形，即单位收益不变或随资本投入递减的情况。

最大利润求值－步骤就是先构造一个边际收益矩阵，增加一箱货物带来的利润，依次挑选边际利润最大的。

9. 匈牙利算法

项目要求每个人只能完成一项任务，匈牙利数学家克尼格证明的两个定理得名。

具体步骤：

第一，找出效率矩阵每行的最小元素，并分别从每行中减去该行的最小元素，这称为行变换

若不能分配，理解成无穷大或者大数即可

第二，找出效率矩阵中每列的最小元素，并分别从每列中减去该最小元素，称之为列变换

第三，用最少的直线覆盖所有的0。若所用直线数等于矩阵纬度，说明最优分配已产生，可以停止行变换和列变换

第2到N轮的变换规则，从矩阵中未被直线覆盖的数字中找出一个最小的数k；直线相交处元素加上k，未被直线覆盖元素减去k，被直线覆盖的元素保持不变。

第四，寻找四个独立的0（任意两个0不能同时出现在同一行或同一列）独立的0的对应最优分配。

10. 不确定决策

满足四个条件的称为不确定性决策：存在一个明确的决策目标、存在两个或两个以上的随机自然状态、存在可供决策选择的两个或两个以上的行动方案、可求得各方案在各状态下的损益矩阵（函数）。

乐观准则：MaxMax、最大最小准则、冒险准则－对于任何行动都认为将是最好的状态发生，即益损值最大的状态发生，然后比较各行动方案实施后的结果，即具有最大损益值的行动为最优行动。

悲观准则：MaxMin、最大最小准则、保守型决策－对任何行动方案，都认为最坏的状态会发生，即损益值最小的状态会发生。然后比较各行动方案实施结果，具有最大损益值的行动为最优行动。

最小后悔准则：最小机会损失决策、最小－最大后悔值决策－对任何行动方案，都认为将是最大后悔值对应的状态发生。比较各行动方案后果，具有最小后悔值行动为最优行动。

步骤是构造后悔值矩阵（后悔值是一个决策方案收益与该情况下所有决策最佳收益之差），求出每行最大后悔值，最后得到最小的“最大后悔值”。

11. 博弈论

囚徒困境，作为决策者思考对手决策的各种可能性，怎么样自己能够受益。

掌握规则，按规则答题

预期货币价值：结果，结果的价值，发生结果的概率。

再说一遍，穷举法和排除法优先，仔细审题和计算，放弃或者猜也只有一分，不要花费太多时间。