第21章 管理科学基础
1考情分析
管理运筹学这部分的试题主要涉及线性规划、动态规划、图论、排序与统筹、决策分析以及运输问题这六大块。这六大板块中的重中之重是线性规划、动态规划与图论。
1.1本章重点
2考点精讲
2.1管理运筹学
1．图论—图与最小生成树
图由点和边构成的，可以反映一些对象之间的关系。图论中的点通常记为Vi，点之间的连线称之为边，通常记为Ei。带箭头的连线，称之为弧，图论中的弧记为Ai。
如果“A认识B”，我们用一条连接A、B的箭头指向B的弧来表示。
由点和边构成的图叫无向图（简称图），无向图记为G=（V，E），其中V是图G的点的集合，E是图G的边的集合。
由点和弧构成的图叫有向图，有向图记为D=（V，A），其中V为图D的点集合，A为图D的弧的集合。
（1）最小生成树问题
一个无圈的连通图即为树。
最小生成树就是在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和最小。
求解最小生成树的破圈算法如下：
（一）在给定的赋权的连通图上任找一个圈；
（二）在所找的圈中去掉一条权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）；
（三）如果所余下的图中不含圈，则计算结束，所余下的图即为最小生成树。否则返回步聚（一）。
【例】用破圈法求下图21-3中的最小生成树。
解：（一）去掉圈（V1，V6，V7，V1）中权值（权值为10的边）最大的边[V1，V6]后，如图21-3（b）所示：
（二）去掉圈（V5，V4，V3，V5）中权值为8的边[V5，V4]后，如图21-3（c）所示：
（三）同理依次去掉权值为5，4，4的边后，最终得到的最小生成树如图21-3（d）所示：
在图21-3（d）中已找不到任何一个圈了，可知其即为图21-3的最小生成树，这个最小生成树的所有边的总权数为3+3+3+1+2+7=19。
2．动态规划
（1）多阶段决策过程最优化问题
动态规划是解决多阶段决策过程最优化问题的一种方法。这种方法把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题，解决了这一系列较容易的单阶段问题，也就解决了这个困难的多阶段决策问题。用动态规划可以解决管理中的最短路问题、资源分配等问题。
【例】如下图21-4所示，给定一个运输网络，两点之间连线的数字表示两点间的距离，试求一条从A到E的运输线路，使总距离为最短。
解：本题可考虑分阶段来求解。从而首先定义：
第一阶段：以A点为起始点，而以距离A点正好一个弧远的点（B1，B2，B3，B4）为终点；
第二阶段：以（B1，B2，B3，B4）为始点，以与A点距离两个弧远的点（C1，C2，C3）为终点；
第三阶段：以（C1，C2，C3）为始点，以与A点距离三个弧远的点（D1，D2）为终点；
第四阶段：以（D1，D2）为始点，以与距离A点四个弧远的点（E）为终点。
显然这是一个四阶段决策过程的最优化问题，用动态规划来解这个问题。即要把这个四阶段的决策问题转化为一系列较容易解决的单阶段决策的问题。
求解时我们从最后一个阶段（第四阶段）开始，从终点（E）向始点（A）方向逐阶段逆推，找出各点到终点的最短距离，并把每个点到终点的最短距离标注在该点上。最后，当逆推到始点时，也即找到了从始点到终点的全过程最短距离。
求解过程如下：
从而可知从A到E的最短距离为14。路径是A-B4-C3-D1-E。
3．线性规划
线性规划是研究在有限的资源条件下，如何有效地使用这些资源达到预定目标的数学方法。用数学的语言来说，也就是在一组约束条件下寻找目标函数的极值问题。
求极大值（或极小值）的模型表达如下：
在上述条件下，求解 ，使满足下列表达式的z取极大值（或极小值）：
（1）图解法
解线性规划问题的方法有很多，最常用的有图解法和单纯形法。图解法简单直观，有助于了解线性规划问题求解的基本原理，下面，通过一个例子来说明图解法的应用。
【例】某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原料的消耗，如表21-3所示。
表21-3产品及原料表
该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应该如何安排计划使该工厂获利最多？
【解】该问题可用以下数学模型来描述，设
分别表示在计划期内产品Ⅰ、Ⅱ的产量，因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品Ⅰ、Ⅱ的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为
同理，因原料A、B的限量，可以得到以下不等式
该工厂的目标是在不超过所有资源限制的条件下，如何确定产量
，以得到最大的利润。若用z表示利润，这时
。综上所述，该计划问题可用数学模型表示为：
目标函数：
满足约束条件：
在以
为坐标轴的直角坐标系中，非负条件
是指第一象限。上述每个约束条件都代表一个半平面。例如，约束条件
代表以直线
为边界的左下方的半平面。若同时满足
，
，
和
的约束条件的点，必然落在由这三个半平面相交组成的区域内，如图5-2中的阴影部分所示。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），因而此区域是本题的线性规划问题的解的集合，称它为可行域。
图5-2图解法
再分析目标函数
，在坐标平面上，它可表示以z为参数，-2/3为斜率的一组平行线：
位于同一直线上的点，具有相同的目标函数值，因此称它为等值线。当z值由小变大时，直线沿其法线方向向右上方移动。当移动到
点时，使z值在可行域边界上实现最大化，这就得到了本题的最优解
，
点的坐标为（4，2）。经过计算，可以得出z=14。
这说明该厂的最优生产计划方案是：生产4件产品Ⅰ，2件产品Ⅱ，可得最大利润为14元。
3章节问答
1．我上大学时没有学过管理运筹学相关知识，这方面零基础，如何去学习，才能达到考试合格标准？
答：
（1）学习时间较少的考生朋友可以详读本章相关内容即可；
（2）学习时间较充裕的考生朋友可以去各大书店或在线购买《管理运筹学》相关教材，并学习相关内容。
2．对于产销不平衡的管理运筹学问题如何来求解？
答：对于产销不平衡的运输问题，我们可以先化为产销平衡的运输问题，然后再求解。
例：某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各产地产量和各销地销量以及各产地运往各销地的每件物品的运输表如下表所示：
应如何组织运输，使得总运输费用最少？
从表格中的数据可知，总产量是600件，而总销量是500件，这是一个产大于销的运输问题，为此我们可建立一个假想的销地B4，B4是产地A1，A2的各自的仓库，B4的销量为100件。因为A1把物品放在自己的仓库，A2把物品放在自己的仓库都不需要运费。从而令C14=0，C24=0，从而得到如下表所示的产销平衡与运价表，这样我们就把产大于销的运输问题转化成了产销平衡的运输问题。
然后采用最小元素法来求解，得到本题的最优解：
X11=50；X12=150；X13=0；X14=100；X21=100；X22=0；X23=200；X24=0；
总运输费用最小为2500元。
