软考高级常见数学题型解题方法汇总一. 最小生成树kruskal算法克鲁斯卡尔算法求连通图的最小生成树先画出所有节点从权值最小的边开始依次连线。用n-1条边连通n个节点且不能产生环路。选最短连线画图注意计算时要加上描述中的条件。【例题1】己知八口海上油井(编号从1#到8#) 相互之间的距离(单位:海里)如下表所示其中1#油井离海岸最近为5海里。现从海岸开始铺设输油管道经1#油井将这些油井都连接起来管道的总长度至少为(58)海里(为便于计量和维修管道只能在油井处分叉)。(58) A. 5 B. 9 C. 10 D.11【例题2】某小区有七栋楼房①~⑦见下图各楼房之间可修燃气管道路线的长度单位:百米已标记在连线旁。为修建连通各个楼房的燃气管道该小区内部煤气管道的总长度至少为59百米。59A.23 B.25 C.27 D.29二. 最短路径依次算出从起点到每一个节点的最短路径。【例题1】下表记录了六个结点A、B、C、D、E、F之间的路径方向和距离。从A到F的最短距离是____。A.38 B.40 C.44 D.46三. 网络与最大流量1. 一个有权有向图每条边上的权值代表这条边的最大承载能力。2. 目标是找到从起点到终点的一些路径尽量让更多的水流向终点。3. 约束条件水流量不能超过每条边的权重。4. 选定一条路径这条路径上的最大流量是由这条路上的短板决定的。5. 该路径上每条边的权值 – 该路径上的短板 剩余流量。6. 剩余流量为0的边断开。【例题1】X、Y、Z 是某企业的三个分厂每个分厂每天需要同一种原料 20吨下图给出了邻近供应厂 A、B、C 的供应运输路线图每一段路线上标明了每天最多能运输这种原料的吨数。根据该图可以算出从 A、B、C 三厂每天最多能给该企业运来这种原料共59吨。(59) A.45 B. 50 C.55 D.60四. 线性规划y ax b1. 列出不等式2. 列出目标函数3. 求出满足所有不等式的交点带入目标函数线性规划问题的求解结果1. 无最优解(无界解)缺乏必要的约束条件。2. 无可行解(0个解) 矛盾的约束条件。3. 最优解唯一(1个)一定在可行域的某个顶点得到。4. 最优解无穷个若存在2个最优解则连接这2个点的线段内的所有点都是最优解。线性规划模型的标准形式的主要特征1. 目标函数为极大化类型2. 所有的约束条件都是线性等式3. 所有约束方程右端的常数都是非负的4. 所有的决策变量均为非负线性规划问题1. 由线性的目标函数、线性的约束条件变量非负组成。2. 线性规划问题的可行解区可能无界。3. 若增加一个线性约束条件可行解区可能缩小、可能不变。4. 若存在2个最优解则连接这2个点的线段内的所有点都是最优解而线段两段的延长线上可能会超出可行解。5. 只要有2个最优解就会有无穷个最优解。【例题1】某厂拥有三种资源A. B、C.生产中、乙两种产品。生产每吨产品需要消耗的资源、可以获得的利润见下表。日前该厂拥有资源A、资源B和资源C分別为12吨7吨和12吨。根据上述说明适当安排甲、乙两种产品的生产量就能获得最大总利润53。如果生产计划只受资源A和C的约束资源B很容易从市场上以每吨0.5百万元购得则该厂宜再购买54资源B以获得最大的总利润。53A.16百万元 B.18百万元 C.19百万元 D.20百万元54A.1吨 B.2吨 C.3吨 D.4吨五. 动态规划穷举法【例题1】某公司拟将5百万元资金投放下属A、B、C三个子公司以百万元的倍数分配投资各子公司获得部分投资后的收益如下表所示以百万元为单位。该公司投资的总收益至多为56百万元。(56)A. 4.8 B.5 C.5.2 D.5.5六. 伏格尔法伏格尔法经济学名词又称差值法。1、算出每一行和每一列最小元素和次小元素的差值并标出差值最大的若几个差额同为最大则可任取其一。2、在差值最大的行或列中找出最小元素给它填尽可能大的数然后将其划去。3、剩余的行和列重复以上步骤直到得到一个初始解。【例题1】设三个煤场 A1、A2、A3 分别能供应煤 7、12、11 万吨三个工厂 B1、 B2、B3 分别需要煤 10、10、10 万吨从各煤场到各工厂运煤的单价百元吨见下表方框内的数字。只要选择最优的运输方案总的运输成本就能降到53百万元。(53)A 30 B 40 C 50 D 61七. 匈牙利指派法任务指派问题1. 找出每行的最小值这一行的每个值都减去最小值得到表1。2. 在表1的基础上找出每列的最小值这一列的每个值都减去最小值得到表2。3. 按行找0优先指派一行只有一个0的。八. 决策论1.悲观小中取大max(min)先选取每个方案最小的收益再取所有最小收益中最大的。2.乐观大中取大max(max)先选取每个方案最大的收益再取所有最大收益中最大的。3.后悔值矩阵后悔值 最大收益 - 当前选择的收益首先每一种方案选出最大后悔值其次从已经选择出的后悔值中找出最小的。【例题1】某地区仅有甲、乙两个企业为销售同种电子产品竞争市场份额。甲企业有三种策略 A、B、C乙企业也有三种策略Ⅰ、Ⅱ、Ⅲ。两企业分别独立地选择各种策略时预计甲企业将增加的市场份额百分点见下表负值表示乙企业将增加的市场份额。若两企业都采纳稳妥的保守思想从最坏处着想争取最好的结果则57。A甲选择策略 B乙选择策略Ⅲ B甲选择策略 A乙选择策略ⅡC甲选择策略 B乙选择策略Ⅱ D甲选择策略 C乙选择策略Ⅲ九. 关键路径和松弛时间十. 净现值