一、数学与经济管理 00:001. 最小生成树 01:521基本概念 02:19定义将nnn个结点连通且总成本最低的树形结构需要n−1n-1n−1条边核心要求连通性所有节点必须连通无环性不能产生环路最小成本边权总和最小算法选择主要采用克鲁斯卡尔(Kruskal)算法普里姆(Prim)算法了解即可边数规律nnn个节点需要n−1n-1n−1条边超过会产生环路2克鲁斯卡尔算法步骤操作流程将图中所有边按权值从小到大排序初始化空图包含所有节点但不含边依次选取最小权值边加入检查是否形成环路若形成则舍弃终止条件当选中边数达到n−1n-1n−1条时停止注意事项需要预先画出所有独立节点每次添加边后要检查连通性和环路图形可能不唯一但总成本唯一3例题小区管道铺设题目解析解题过程确认9个节点需要8条边按顺序选取边权4个1→3个2→1个3排除会产生环路的边计算结果总成本4×13×21×3134×13×21×3134×13×21×313千元易错点可能忽略环路检查错误计算总边数图形特性最小生成树图形不唯一但成本总和唯一4例题油井管道铺设 07:47题目解析特殊条件1号油井离海岸5海里需计入总长度解题步骤从表格中找出最小边权0.51-5和7-8依次选取次小边权0.5→0.6→0.7→0.8→0.9→1.0→1.1计算最小生成树总长度5海里关键陷阱容易忽略海岸连接的5海里正确答案应为551055105510海里审题技巧所有给定条件都有用需逐一标记确认5解题技巧总结表格处理可将距离表转化为邻接矩阵不画图也能直接选取最小边注意事项严格检查n−1n-1n−1条边的限制添加每条边时实时检查环路总成本计算要准确累加效率建议熟练者可直接操作表格不熟练者建议画出节点图辅助理解2. 最短路径 12:251例题:最短路径应用 13:55与关键路径的区别关键路径求项目工期的最长路径而最短路径求真正的最短距离关键路径出现在项目工期场景最短路径是纯数学应用题迭代计算法从起点开始依次计算到各顶点的最短路径当前顶点最短路径前驱顶点最短路径当前边权值比较所有可能路径取最小值计算步骤A→B唯一路径11A→C比较直接16与A→B→C(111324)取16A→D比较直接24、A→B→D(111627)、A→C→D(161430)取24A→E比较直接36、A→B→E(112132)、A→C→E(161733)、A→D→E(241438)取32A→F比较直接54、A→B→F(112940)、A→C→F(162238)、A→D→F(241741)、A→E→F(321547)取38特点逻辑清晰但计算量大前驱计算结果可直接复用最终答案为A→F最短距离383. 网络与最大流量 21:281例题:网络与最大流量应用 21:37核心原理运输能力由路径中的最小边决定短板效应类比桥梁承重整条路径的运输能力受限于最小容量段计算步骤选择1→3→5→6路径运输10吨更新剩余容量选择1→2→5→6路径运输6吨更新剩余容量选择1→4→6路径运输5吨更新剩余容量选择1→4→3→5→6路径运输1吨更新剩余容量选择1→4→2→5→6路径运输1吨路径断开关键要点短板优先每次选择当前路径的最小容量实时更新运输后立即扣除已用容量终止条件起点到终点不再连通最终结果各次运输量累加10651123万吨2例题:网络与最大流量应用 29:41特殊场景多起点A、B、C多终点X、Y、Z每个分厂日需20吨原料解题方法A厂15吨A→M→N→Z105B厂20吨先运10吨B→M→Y再运10吨B→N→XC厂20吨直接C→Z结果计算总运输量15(A)20(B)20©55吨注意事项运输后及时更新线路剩余容量多起点情况需分别计算各起点贡献实际考试可简化计算过程4. 线性规划 33:291基本概念定义: 在一组约束条件下寻找目标函数的极值极大值和极小值问题组成要素:线性目标函数线性约束条件变量非负条件实际问题中变量一般为非负可行解域: 满足约束条件的非负变量组的集合最优解: 可行解域中使目标函数达到极值的解解的性质: 最优解可能有0个、唯一1个或无穷多个只要有2个就会有无穷个2解题方法 35:20基本步骤:列出所有约束条件不等式确定目标函数表达式求约束条件方程组的交点解验证解是否满足所有约束条件将有效解代入目标函数求极值极值位置: 极值必定出现在约束条件的交点处验证方法: 将交点解代入未被求解的约束条件验证是否满足3例题解析题目解析变量设定:设生产I产品数量为xxx吨设生产II产品数量为yyy吨约束条件:xy≤4x y \leq 4xy≤4甲材料限制4x3y≤124x 3y \leq 124x3y≤12乙材料限制x3y≤6x 3y \leq 6x3y≤6丙材料限制x≥0x \geq 0x≥0,y≥0y \geq 0y≥0非负条件目标函数:z9x12yz 9x 12yz9x12y利润最大化求解过程:联立(1)(2)得x0,y4x0,y4x0,y4→ 验证(3)不满足126126126联立(1)(3)得x3,y1x3,y1x3,y1→ 验证(2)不满足151215121512联立(2)(3)得x2,y4/3x2,y4/3x2,y4/3→ 验证(1)满足10/3410/3410/34最优解计算:9×212×(4/3)349×2 12×(4/3) 349×212×(4/3)34万元剩余材料分析:甲材料使用量24/310/342 4/3 10/3 424/310/34乙材料使用量4×23×(4/3)124×2 3×(4/3) 124×23×(4/3)12刚好用完丙材料使用量23×(4/3)62 3×(4/3) 623×(4/3)6刚好用完最终答案:最大利润34万元选项B剩余材料甲选项A二、知识小结知识点核心内容考试重点/易混淆点难度系数最小生成树通过普里姆算法或克里斯卡尔算法用最小成本连通所有节点需 n-1条边避免环路总成本唯一但图形不唯一需注意题目隐含条件如陆地连接成本⭐⭐最短路径迭代计算起点到各节点的最短路径如A→B→C…逐步推导至终点区分 关键路径最长 与最短路径运算量大但逻辑清晰⭐⭐⭐网络与最大流量运输能力由路径短板决定实时更新剩余流量直至无法连通短板优先需多次减掉已用流量并重绘图⭐⭐⭐⭐线性规划在约束条件下求目标函数极值如利润最大化联立方程求交点并验证需列不等式组极值出现在约束条件交点处⭐⭐⭐动态规划/博弈论覆盖法等解题思想经济学原理基础概念高频考点但复杂度高需掌握典型例题⭐⭐⭐⭐