乐凯1905软考高项--第十六课--第27章--管理科学基础知识

1、来乐凯学软考高项，让你“乐”在其中，“凯”旋而归 乐凯培训学院 第27章 管理科学基础知识 来乐凯学软考高项，让你“乐”在其中，“凯”旋而归 第27章 管理科学基础知识 图论图论最小生成树最小生成树普里姆算法（普里姆算法（P P- -864864）-掌握掌握 例：下图是某地区的通信线路图，假设其中标注的数字代表通信线路的长度（单位为千米），现在要求至 少要架设多长的线路，才能保持6个城市的通信联通。 步骤1：设两个集合，U为已选节点集合；V为未选节点集合； 步骤2：任选1个节点放入U，比如选节点A，形成如下2个集合 U=A；V=B，C，D，E，F； 步骤3：从集合U中的每个节点出发，找出所有能

2、直接联通的路线 在这些路线中挑选最短的，把终点的节点从集合V移到集合U； A-B(300); A-C(400); A-E(200); A-F(300); 最短的是A-E 把节点E从集合V移到集合U中，U=A，E；V=B，C，D，F； 并在无连接的图上把A-E联接上 200 第27章 管理科学基础知识 图论图论最小生成树最小生成树普里普里姆算法（姆算法（P P- -864864）-掌握掌握 步骤4：重复步骤3，从集合U中的每个节点出发，找出所有能直接联通的 路线，在这些路线中挑选最短的，把终点的节点从集合V移到集合U； A-B(300); A-C(400); A-F(300); E-F(400)

3、; 最短的是A-B或A-F，任选B或F从V移到U U=A，E，B；V=C，D，F；并把A-F联接上 300 第27章 管理科学基础知识 图论图论最小生成树最小生成树普里普里姆算法（姆算法（P P- -864864）-掌握掌握 步骤5：重复步骤3，从集合U中的每个节点出发，找出所有能直接联通的 路线，在这些路线中挑选最短的，把终点的节点从集合V移到集合U； A-C(400); A-F(300); E-F(400); B-C(400); B-F(300); 最短的是A-F或B-F，将F从V移到U U=A，E，B，F；V=C，D； A-F或B-F任选一条联接上 300 第27章 管理科学基础知识 图

4、论图论最小生成树最小生成树普里普里姆算法（姆算法（P P- -864864）-掌握掌握 步骤6：重复步骤3，从集合U中的每个节点出发，找出所有能直接联通的 路线，在这些路线中挑选最短的，把终点的节点从集合V移到集合U； A-C(400); A-F(300); E-F(400); B-C(400); F-C(400); F-D(200); 最短的是F-D，将D从V移到U U=A，E，B，F，D；V=C； F-D联接上 200 第27章 管理科学基础知识 图论图论最小生成树最小生成树普里普里姆算法（姆算法（P P- -864864）-掌握掌握 步骤7：重复步骤3，从集合U中的每个节点出发，找出所有

5、能直接联通的 路线，在这些路线中挑选最短的，把终点的节点从集合V移到集合U； A-C(400); A-F(300); E-F(400); B-C(400); F-C(400); D-C(300); 最短的是A-F和D-C，优先选择不在U集合中的节点C， U=A，E，B，F，D，C；V=； D-C联接上 300 第27章 管理科学基础知识 图论图论最小生成树最小生成树克鲁斯卡尔算法（克鲁斯卡尔算法（P P- -864864）-掌握掌握 例：下图是某地区的通信线路图，假设其中标注的数字代表通信线路的长度（单位为千米），现在要求至 少要架设多长的线路，才能保持6个城市的通信联通。 步骤1：寻找所有的

6、边中最短（权值最小）的一条，如有多条，取任意一条； A-E，F-D都是200，比如取A-E，将A、E连接； 步骤2：在剩余的边中再取权值最小的边，并且该边不会构成回路 F-D最小为200，而且未构成回路； 步骤3：重复以上第2步，寻找权值最小的边，并且不构成回路加入联接； A-F、A-B、B-F、C-D都是300，都不构成回路，任选一条 200200 200 200 200 300 第27章 管理科学基础知识 图论图论最小生成树最小生成树克鲁斯卡尔算法（克鲁斯卡尔算法（P P- -864864）-掌握掌握 步骤4：重复以上第2步，寻找权值最小的边，并且不构成回路加入联接； A-B、B-F、C-

7、D都是300，都不构成回路，任选一条 步骤5：重复以上第2步，寻找权值最小的边，并且不构成回路加入联接 A-B、B-F都是300，而且未构成回路；任选一条如B-F 步骤6：至此所有节点都已加入到树中，并且没有构成回路，并且整个树的 权重是最小的； 注：在以上寻找权值最小边的循环中，如发现某路径构成回路，则排除并 后续永不考虑。 200 200 300 300 200 300 300 300 200 第27章 管理科学基础知识 图论图论最短路径最短路径迪杰斯特拉算法（迪杰斯特拉算法（P P- -866866） 例：如图所示，有一批货物要从城市s发送到城市t，线条上的数字代表通过这条路的费用（单位

8、为万元）。 那么，运送这批货物，至少需要花费多少元？ 第27章 管理科学基础知识 红点集D1D2D3D4D5D6D7D8D9Dt s s-1(25);s-2(21) 2521 s，2 s-1(25) s-2-1(44)舍弃 s-2-3(41) s-2-4(46) 254146 s，2，1 s-1-7(36) s-1-8(31) s-2-3(41) s-2-4(46) 41463631 s，2，1，8 s-1-7(36) s-1-8-7(56)舍弃 s-1-8-9(64) s-2-3(41) s-2-4(46) 41463664 图论图论最短路径最短路径迪杰斯特拉算法（迪杰斯特拉算法（P P-

9、-866866） 第27章 管理科学基础知识 红点集D1D2D3D4D5D6D7D8D9Dt s，2，1，8，7 s-1-7-5(71) s-1-7-9(91)舍弃 s-1-8-9(64) s-2-3(41) s-2-4(46) 41467164 s，2，1，8，7，3 s-1-7-5(71)舍弃 s-1-8-9(64) s-2-3-4(53)舍弃 s-2-3-5(61) s-2-4(46) 466164 s，2，1，8，7，3，4 s-1-8-9(64) s-2-3-5(61) s-2-4-6(91) 619164 图论图论最短路径最短路径迪杰斯特拉算法（迪杰斯特拉算法（P P- -8668

10、66） 第27章 管理科学基础知识 红点集D1D2D3D4D5D6D7D8D9Dt s，2，1，8，7，3，4，5 s-1-8-9(64) s-2-3-5-6(69) s-2-3-5-t(82) s-2-4-6(91)舍弃 696482 s，2，1，8，7，3，4，5，9 s-1-8-9-t(82) s-2-3-5-6(69) s-2-3-5-t(82) 6982 s，2，1，8，7，3，4，5，9，6 s-1-8-9-t(82)舍弃 s-2-3-5-6-t(81) s-2-3-5-t(82)舍弃 81 s，2，1，8，7，3，4，5，9，6，t s-2-3-5-6-t(81) 图论图论最短路

11、径最短路径迪杰斯特拉算法（迪杰斯特拉算法（P P- -866866） 第27章 管理科学基础知识 图论图论网络与最大流量（网络与最大流量（P P- -868868） 例：如图所示，标出了某地区的运输网，各节点之间的运输能力，如下表所示，那么从节点到节点的 最大运输能力（流量）可以达到多少万吨/小时？ 解题思路：从起点开始到终点任找一条路径，按节点间的瓶颈 作为最大流量，将路径上其他线段减掉该流量，并把瓶颈线段 断开。再寻找其他起点到终点的路径，重复以上步骤，直到起 点到终点无路可通，将之前所有瓶颈流量加总，既为最大流量 第27章 管理科学基础知识 图论图论网络与最大流量（网络与最大流量（P P

12、- -868868） 步骤1：先根据表格数据将流量及节点方向标记在图上，便于识 别可通路径及寻找每条路径的瓶颈流量。 6 5 10 10 14 21 7 4 1 步骤2：任选一条从节点1到节点6的路径，比如1-4-6，两 段路线1-4（10），4-6（5），瓶颈流量是最小值为5，因 此把4-6断开，1-4减掉5。形成左图 6 5 10 14 21 7 4 1 第27章 管理科学基础知识 图论图论网络与最大流量（网络与最大流量（P P- -868868） 步骤3：再任选一条从节点1到节点6的路径，比如1-3-5-6， 三段路线1-3（10），3-5（14）， 5-6（21），瓶颈流 量是最小值为

13、10，因此把1-3断开，3-5减掉10， 5-6减 掉10。形成左图 6 5 4 11 7 4 1 步骤4：重复以上步骤再任选一条从节点1到节点6的路径，比 如1-2-5-6，三段路线1-2（6），2-5（7）， 5-6 （11），瓶颈流量是最小值为6，因此把1-2断开，2-5减掉 6， 5-6减掉6。形成左图 5 4 5 1 4 1 第27章 管理科学基础知识 图论图论网络与最大流量（网络与最大流量（P P- -868868） 步骤5：重复以上步骤再任选一条从节点1到节点6的路径，比 如1-4-3-5-6，四段路线1-4（5），4-3（1）， 3- 5（4）， 5-6（5），瓶颈流量是最小值

14、为1，因此把4-3 断开， 1-4减掉1， 3-5减掉1， 5-6减掉1。形成右图 4 3 4 1 4 步骤6：重复以上步骤再任选一条从节点1到节点6的路径，比 如1-4-2-5-6，四段路线1-4（4），4-2（4）， 2- 5（1）， 5-6（4），瓶颈流量是最小值为1，因此把2-5 断开， 1-4减掉1， 4-2减掉1， 5-6减掉1。形成右图 3 3 3 3 步骤7：至此已没有从节点1到节点6的通路了，因此最大流量 把之前几个步骤的瓶颈流量最小值加总=5+10+6+1+1=23 第27章 管理科学基础知识 决策论决策论不确定型决策（不确定型决策（P P- -872872） 例：某公司需

15、要根据下一年度宏观经济的增长趋势预测决定投资策略。宏观经济增长趋势又不景气、不变 和景气三种，投资策略有积极、稳健和保守三种，各种状态的收益如下表所示。 乐观主义准则（最大最大准则）-决策的原则是“大中取大”，争取以“好中之好”的态度来选择决策方案。 500500 300 400 300 400 500 所以按照乐观主义“大中取大”的原则，该题最终的答案是500 步骤 步骤 第27章 管理科学基础知识 决策论决策论不确定型决策（不确定型决策（P P- -872872） 悲观主义准则（最大最小准则）-决策的原则是“小中取大”，在各种最坏的可能结果中选取最好的。 5050 150 200 150

16、200 200 所以按照悲观主义“小中取大”的原则，该题最终的答案是200 步骤 步骤 后悔值准则（萨维奇准则、最小机会损失准则）-后悔值里大中取小。 350350 250 300 250 所以按照后悔值里面“大中取小”的原则，该题最终的答案是250 步骤 步骤 250 0 100 50 0 0 200 300 步骤 第27章 管理科学基础知识 决策论决策论灵敏度分析（敏感性分析）（灵敏度分析（敏感性分析）（P P- -874874） 例：假设有外表完全相同的木盒100只，将其分为2组，一组装白球，有70盒；另一组装黑球，有30盒。 现从这100盒中任取一盒，请你猜，如果这盒内装的是白球，猜对

17、了得500分，猜错了罚200分；如果这 盒内装的是黑球，猜对了得1000分，猜错了罚150分。为使期望得分最多，应选哪一个方案？ 步骤1：根据题干描述，画出决策树 步骤2：计算各方案的期望值 “猜白”（500*0.7）+（-200*0.3）= 290； “猜黑”（1000*0.3）+（-150*0.7） = 195； 所以按题意描述，猜白的期望得分最多。 步骤3：如需计算白球黑球达到怎样的比例，可以无论 猜黑还是猜白的期望值相同，则设置白球占比为p。 500 * p + (-200) * (1-p) = 1000*(1-p) + (-150) * p 最后算出来p=0.65。表示白球65%时是

18、转折概率。 第27章 管理科学基础知识 线性规划（线性规划（P P- -876876） 例：某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原料 的消耗，如表所示。该工厂每生产一件产品 可获利2元，每生产一件产品可获利3元，问应该如何安 排计划使该工厂获利最多。 步骤1：设获利最多时，生产产品数量为x，生产产品数量为y，根据题意可以列出以下不等式； 1、x 1 + y 2 8；2、x 4 + y 0 16；3、x 0 + y 4 12； 4、x 0； 5、y 0； 简化后得到：1、x + 2y 8；2、 4 x 16；3、4y 12； 4、x 0； 5、y 0；

19、 另最多的获利设为：z；所以目标函数就是：z= 2x + 3y；因此最终是需要求z的最大值。 第27章 管理科学基础知识 线性规划（线性规划（P P- -876876） 步骤2：用图解法解决如上线性规划问题，先将上列不等式各取极值，获得所有解的集合（可行域），既阴影部分。 x y 4x=16 4y=12 x+2y=8 x=0 y=0 8 4 第27章 管理科学基础知识 线性规划（线性规划（P P- -876876） x y 4x=16 4y=12 x+2y=8 x=0 y=0 8 4 步骤3：对于目标函数，先设截距z为0（最小期望值），根据斜率为-2/3，可算出倾斜角，画出等直线l。 2x+3

20、y=0 目标函数等值线l 倾斜角 斜率（角系数）-是一条直线对于 横坐标轴正向夹角的正切，反映直线 对水平面的倾斜度。 对于一次函数y=kx+b，k就是斜率， 或ax+by+c=0中，k=-（a/b） k和倾斜角的关系： k=tan 第27章 管理科学基础知识 线性规划（线性规划（P P- -876876） x y 4x=16 4y=12 x+2y=8 x=0 y=0 8 4 2x+3y=0 目标函数等值线l 步骤4：将目标函数的等直线l沿倾斜角平移，分别会和阴影部分的Q1，Q2，Q3，Q4顶点交汇，将这些点的 坐标x，y分别代入目标函数z= 2x + 3y ，取z的最大值。 倾斜角 Q1坐标

21、（4，0）代入，得z=8; Q2坐标（4，2）代入，得z=14; Q3坐标（2，3）代入，得z=13; Q2坐标（0，3）代入，得z=9; 由此可知可行域（阴影面积）中Q2点是 最优解，最优方案就是：生产4件产品、 2件产品，可得最大理论为14元。 第27章 管理科学基础知识 指派问题指派问题匈牙利法匈牙利法补充补充 例：某项目有、四项不同的任务，恰有甲、乙、丙、丁四个人去完成各项不同的任务。由于 任务性质及每人的技术水平不同，他们完成各项任务所需时间也不同，具体如下表所示，项目要求每个人 只能完成一项任务，为了使项目花费的总时间最短，应该指派丁完成（）任务？ 第27章 管理科学基础知识 指派

22、问题指派问题匈牙利法匈牙利法补充补充 步骤1：根据表格数据做出二维矩阵 并找出每一行的最小值 215134 1041415 9141613 78119 步骤2：每一行的每个数字减去该行最小值， 在结果矩阵中找出每一列的最小值。 013112 601011 0574 0142 步骤3：每一列的每个数字减去该列最小 值 甲01370 乙6069 丙0532 丁0100 步骤4：标记为0的位置代表适合指派 某人干某个任务，因此得到如下线索： 甲-适合做、； 乙-只适合做； 丙-只适合做； 丁-适合做、 、； 步骤5：根据这些线 索得到如下结论： 甲做； 乙做； 丙做； 丁做； 第27章 管理科学基础

23、知识 运费问题运费问题伏格尔法伏格尔法补充补充 例：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产 量（单位：吨）、各销售点的销售量（单位：吨）以及各工厂到各销售点的单位运价（百元/吨）示于下 表中，适当安排调运方案，最小总运费为（）百元？ 第27章 管理科学基础知识 步骤1：根据表格数据做出二维矩阵并算出 各行各列中最小元素和次小元素的差额， 得到行差X和列差Y。 B1B2B3B4Y A14124110 A2210391 A3851161 X2513 运费问题运费问题伏格尔法伏格尔法补充补充 步骤2：对行差X和列差Y进行对比，找出最大差额 （当前步骤

24、为B2列的5），倾其所在行的产量，最大 限度地满足所在列的需求；一旦需求（或库存）被彻 底满足（或库存调光），则随即划去该列（或行）的 所有运价信息。 由于最大的差5对应B2列最小值5在A3行，因此将A3 行的产量（44）最大限度满足B2列的需求（28） 由于B2彻底满足，划去B2列，并且A3剩余产量为16 B1B2B3B4Y A14124110 A2210391 A3851161 X2513 结论1：A3-B2 28 A1A2A3 322044-28 B1B2B3B4 1628(A3)2824 第27章 管理科学基础知识 步骤3：将以上划去列后剩余的部分重新排列 成矩阵，并重复步骤1：算出各

25、行各列中最小 元素和次小元素的差额，得到行差X和列差Y。 B1B3B4Y A144110 A22391 A381162 X213 运费问题运费问题伏格尔法伏格尔法补充补充 步骤4：重复步骤2，找出最大行列差（当前步骤为 B4列的3）； 由于最大的差3对应B4列最小值6在A3行，因此将A3 行的产量（还剩16）最大限度满足B4列的需求（24） 由于16并不能彻底满足B4列的24需求，而A3已经耗 尽，因此划去A3行，并且B4剩余需求为24-16=8 结论1：A3-B2 28 结论2：A3-B4 16 A1A2A3 322016-16 B1B2B3B4 1628(A3)2824-16 B1B3B4

26、Y A144110 A22391 A381162 X213 第27章 管理科学基础知识 步骤5：将以上划去列后剩余的部分重新排列 成矩阵，并重复步骤1：算出各行各列中最小 元素和次小元素的差额，得到行差X和列差Y。 注：当出现相同行列差时，随机取一个 B1B3B4Y A144110 A22391 X212 运费问题运费问题伏格尔法伏格尔法补充补充 步骤6：重复步骤2，找出最大行列差（由于有2个2， 随机取一个，比如取B4列的2）； 由于该列差对应B4列最小值9在A2行，因此将A2行 的产量（20）最大限度满足B4列的需求（8） 由于B4彻底满足，划去B4列，并且A2剩余产量为 20-8=12

27、结论1：A3-B2 28 结论2：A3-B4 16 结论3：A2-B4 8 A1A2A3 3220-80 B1B2B3B4 1628(A3)28 24(A3-16、 A2-8) B1B3B4Y A144110 A22391 X212 第27章 管理科学基础知识 步骤7：将以上划去列后剩余的部分重新排列 成矩阵，并重复步骤1：算出各行各列中最小 元素和次小元素的差额，得到行差X和列差Y. B1B3Y A1440 A2231 X21 运费问题运费问题伏格尔法伏格尔法补充补充 步骤8：重复步骤2，找出最大行列差（当前步骤为 B1列的2 ）； 由于该列差对应B1列最小值2在A2行，因此将A2行 的产量

28、（12）最大限度满足B1列的需求（16） 由于12并不能彻底满足B1列的16需求，而A2已经耗 尽，因此划去A2行，并且B1剩余需求为16-12=4 结论1：A3-B2 28 结论2：A3-B4 16 结论3：A2-B4 8 结论4：A2-B1 12 A1A2A3 3200 B1B2B3B4 16-1228(A3)28 24(A3-16、 A2-8) B1B3Y A1440 A2231 X21 第27章 管理科学基础知识 步骤9：当矩阵只剩下1行或1列时，根据当前 的产量和需求表，已经能把剩余的产量对应到 剩余的需求，当前为A1的32要分28满足B3， 分4满足B1剩余的需求。因此得到如下结论： 运费问题运费问题伏格尔法伏格尔法补充补充 结论1：A3-B2 28 结论2：A3-B4 16 结论3：A2-B4 8 结论4：A2-B1 12 结论5：A1-B3 28 结论6：A1-B1 4 A1A2A3 3200 B1B2B3B4 428(A3)28 24(A3-16、 A2-8) 步骤10：将结论分配方案，代回到原题表格， 根据方案的每一步，查到对应的运费，然后进