北京理工大学运筹学

北京理工大学——运筹学OperationsResearch:科学决策与系统优化的基石Contents课程目录北京理工大学运筹学课程核心章节概览，涵盖基础理论与前沿应用方法。01运筹学基础与发展历史02线性规划与对偶理论03网络模型与图论应用04整数规划与目标规划05动态规划与排队论CHAPTER01运筹学基础与发展历史从二战战火到现代管理科学的演进历程OVERVIEW运筹学概述与核心思想运筹学是应用数学方法对系统进行科学决策与优化的交叉学科。其核心在于建立工程和管理问题的数学模型，通过求解计算获得最优决策，实现资源的最优配置。北京理工大学·校园建筑风貌01起源与核心目标：运筹学起源于二战时期的军事决策，核心思想是在约束条件下寻找目标函数极值，实现系统整体最优而非局部最优02学科定位：作为工业工程、智能制造、管理科学等专业的核心课程，运筹学为复杂系统提供定量分析框架与科学决策工具03学科特点：应用牵引与学科交叉，强调数学建模、算法设计与实际问题的紧密结合，具有持续拓展的活跃性DevelopmentHistory运筹学发展历史运筹学从二战军事应用起步，经历了战后工业化、管理科学化、计算机化三个发展阶段，现已成为数字经济时代系统优化的核心技术支撑。1940s二战起源英国Blackett团队首次将科学方法应用于军事决策，解决雷达部署与反潜作战问题，奠定学科基础1950s战后工业化单纯形法发明与计算机普及，推动运筹学从军事领域扩展至工业生产、资源分配等企业管理场景华罗庚中国发展华罗庚先生推广"优选法"与"统筹法"，开创中国运筹学应用先河，现已在高铁调度、物流优化等领域取得世界领先成果AI时代现代融合与大数据、机器学习深度结合，在供应链优化、智能交通、金融风控等复杂系统中发挥关键作用METHODOLOGY运筹学方法论与问题解决流程运筹学提供了一套从问题分析到方案实施的完整科学决策范式，强调数学建模与算法求解的紧密结合，确保决策的系统性与可验证性。01模型构建决策变量与目标函数明确决策变量、目标函数与约束条件三要素，将实际管理问题抽象为可计算的数学表达，建立问题与数学形式之间的映射关系02模型构建模型框架选择区分确定性模型与随机模型，根据问题特征选择线性规划、动态规划或排队论等合适框架，匹配工具与场景03求解与验证算法求解与灵敏度运用单纯形法、分支定界等算法求解模型，并通过灵敏度分析检验解的稳健性与适用范围，评估参数扰动影响04求解与验证方案实施与迭代将最优解转化为可执行的决策方案，在实施过程中持续监控并根据反馈迭代优化模型，形成闭环改进机制OPTIMIZATION&SEARCH优化与搜索基础优化问题是运筹学的数学基础，通过经典极值理论与迭代搜索算法，为复杂约束条件下的最优解决策提供理论支撑与计算工具。经典极值问题通过一阶导数为零的必要条件与二阶导数判别的充分条件，求解无约束或简单约束下的目标函数极值点一阶·二阶导数最优化条件KKT条件将拉格朗日乘子法推广至不等式约束，为判断解的最优性提供系统性准则KKTConditions迭代算法框架梯度下降法沿负梯度方向更新，牛顿法利用二阶信息加速收敛，通过迭代逐步逼近全局最优解Gradient·Newton一维搜索技术黄金分割法、斐波那契法等区间消去策略，为多维优化中的线搜索提供高效单变量求解方法GoldenSectionCHAPTER02线性规划与对偶理论运筹学核心模型与求解方法的系统性学习LinearProgramming·CaseStudy线性规划问题引入：生产计划案例线性规划是研究在线性约束条件下优化线性目标函数的数学方法，广泛应用于生产计划、资源分配等管理决策场景。问题描述工厂拥有A/B/C三种设备，生产甲、乙两种产品，每种产品需占用不同设备机时，设备能力受限甲产品利润1500元/件，乙产品利润2500元/件，目标是确定生产数量使总利润最大化数学建模决策变量：x₁为甲产品产量，x₂为乙产品产量目标函数：maxZ=1500x₁+2500x₂约束条件：3x₁+2x₂≤65（设备A），2x₁+x₂≤40（设备B），3x₂≤75（设备C），x₁,x₂≥0生产计划数据表设备类型产品甲机时/件产品乙机时/件设备能力h设备A3265设备B2140设备C0375设备能力约束下的双产品生产利润优化问题GraphicalMethod线性规划的图解法图解法通过可视化可行域与目标函数等值线，直观展示线性规划最优解在可行域顶点达到的几何本质，为单纯形法提供理论基础。线性规划图解法：可行域多边形与目标函数等值线的几何关系01可行域构建将所有约束不等式转化为半平面，其交集形成凸多边形可行域，每个顶点对应一个基本可行解02等值线平移目标函数等值线沿梯度方向平移，与可行域最后接触的顶点即为最优解，揭示"顶点最优"定理03特殊情况识别通过图形可直观判断无界解（可行域无界且目标可无限增大）、无可行解（约束矛盾）等异常情形运筹学·线性规划线性规划的标准型与转化标准型是单纯形法求解的基础，通过统一目标方向、约束形式和变量符号，将各类线性规划问题转化为可计算的规范形式。FEATURES标准型特征目标函数为最大化形式，所有约束条件转化为等式，右端常数项非负，决策变量满足非负约束max·=·b≥0·x≥0METHODS转化方法01min转max：目标函数取负号，最优值反号还原02不等式转等式：≤约束加松弛变量，≥约束减剩余变量03自由变量处理：用两个非负变量之差替换无符号限制的变量LINEARPROGRAMMING单纯形法原理与求解过程单纯形法通过在可行域顶点间迭代搜索，利用检验数判断最优性，是求解线性规划问题的经典高效算法。基本思想从初始基本可行解出发，选择检验数为正的变量进基，按最小比值原则确定出基变量，迭代至所有检验数非正检验数几何解释在凸多面体可行域的顶点间移动，每次迭代使目标函数值严格增加或不变，最终到达最优顶点凸多面体表格形式通过矩阵行变换更新单纯形表，基变量列构成单位矩阵，检验数行反映对各非基变量的敏感度单位矩阵LINEARPROGRAMMING单纯形法的初始解获取对于缺乏明显初始基的线性规划问题，大M法和两阶段法通过引入人工变量构造辅助问题，为单纯形法提供可行的起始点。大M法01在目标函数中给人工变量赋予极大惩罚系数M（求max时取−M，求min时取+M），迫使人工变量在迭代过程中出基02若最终最优解中人工变量仍为正值，说明原问题无可行解；否则去掉人工变量即得原问题最优解两阶段法01第一阶段：构造辅助问题，目标为最小化人工变量之和，用单纯形法求解，若最优值>0则原问题无可行解02第二阶段：以第一阶段得到的基本可行解为起点，去掉人工变量，求解原目标函数的最优解DUALITYTHEORY对偶模型与影子价格对偶理论揭示了原问题与对偶问题的数学对称性，对偶变量的经济含义——影子价格，为资源定价与投资决策提供定量依据。对偶问题构建原问题每个约束对应对偶问题一个变量，原问题求max则对偶问题求min，系数矩阵转置，右端项与目标系数互换。这种对称结构使得原问题与对偶问题形成完美的数学映射关系。矩阵转置影子价格含义对偶变量的最优值表示对应资源的边际价值，即每增加一单位资源对目标函数的贡献量。影子价格反映了资源的稀缺程度，为管理者评估资源投入效益提供关键参考。边际价值对偶性质弱对偶性保证原问题任一可行解目标值≤对偶问题任一可行解目标值；强对偶性说明两者最优值相等。互补松弛条件进一步刻画了最优解的结构特征。强弱对偶SensitivityAnalysis灵敏度分析灵敏度分析研究模型参数变化对最优解的影响，确定参数允许变化范围，为不确定性环境下的管理决策提供鲁棒性支撑。价值系数灵敏度◆分析目标函数系数cj变化对最优解的影响，确定使当前最优基保持不变的cj允许变化范围通过检验数判断系数变化是否改变最优基，为产品定价策略调整提供量化依据◆非基变量系数变化仅影响自身检验数；基变量系数变化影响所有非基变量检验数，需重新计算判断区分变量类型对灵敏度分析的影响程度，建立系统化的参数扰动响应机制cj目标函数系数资源限量灵敏度◆分析约束右端项bi变化对最优解的影响，利用对偶变量（影子价格）评估资源增减的经济价值影子价格反映资源稀缺程度，指导管理者识别关键约束瓶颈与资源优化方向◆在基不变的范围内，目标函数最优值的变化量等于影子价格乘以资源变化量，为资源采购决策提供依据量化资源投入边际收益，建立成本效益分析框架，支持预算编制与投资决策bi约束右端项Chapter03网络模型与图论应用图论方法在交通、物流、通信网络中的优化应用TransportationProblem运输问题与运输单纯形法运输问题是研究产销平衡条件下最小化运输成本的线性规划特例，运输单纯形法利用问题的特殊结构实现高效求解。数学模型m个产地、n个销地，决策变量xij表示从产地i到销地j的运量，目标最小化总运费，约束为产销量平衡。产销平衡初始解方法西北角法从左上角开始分配，最小元素法优先满足运费最低的路线，元素差额法考虑次优选择的惩罚成本。西北角法最优性检验闭回路法沿格子回路计算检验数，位势法利用对偶变量计算，检验数为负说明当前解非最优需调整。检验数OPERATIONSRESEARCH指派问题与匈牙利法指派问题是n对n的特殊运输问题，匈牙利法通过矩阵变换与独立零元素匹配，高效求解最优人员-任务分配方案。问题特征n×n方阵n个人完成n项任务，每人一项、每项一人，成本矩阵为n×n方阵，是产销平衡且供需均为1的运输问题特例TransportationSpecialCase01矩阵变换行变换：每行减去该行最小元素；列变换：每列减去该列最小元素，使矩阵出现多个零元素02画线覆盖用最少的水平线和垂直线覆盖所有零元素，若线数等于n则找到最优解，否则调整矩阵继续迭代03最优指派在零元素中选择n个独立零（不同行不同列），对应位置即为最优人员-任务分配方案NETWORKOPTIMIZATION最小支撑树与最短路径最小支撑树与最短路径是网络图论的两类基础优化问题，为交通网络设计、通信线路铺设、导航路径规划提供核心算法支撑。SECTION01最小支撑树01问题定义：在连通赋权图中找包含所有顶点的树，使边权总和最小。该问题广泛应用于网络基础设施设计，如电力线路铺设、通信网络建设等场景，目标是以最低成本实现全网连通。02Kruskal算法：按边权从小到大排序，依次加入不构成回路的边，直至选出n-1条边构成最小支撑树。采用并查集数据结构可高效检测回路，时间复杂度为O(mlogm)。SECTION02最短路径01Dijkstra算法：从起点开始，逐步扩展已知最短距离的顶点集合，每次选择距离最小的未访问顶点更新邻居距离。适用于边权非负的图，是导航系统的核心算法基础。02Floyd算法：动态规划思想，通过中间顶点逐步迭代，求解所有点对之间的最短路径。时间复杂度O(n³)，适合稠密图的全局最短路径计算，如城市间距离矩阵求解。NETWORKFLOWOPTIMIZATION最大流与最小费用流最大流与最小费用流是网络流优化的核心问题，最大流最小割定理揭示了流量与割集的深刻对偶关系，为物流与通信网络优化提供理论基础。最大流问题在容量限制下求源点到汇点的最大流量，Ford-Fulkerson方法通过增广链迭代增加流量直至无法增广。增广链最大流最小割定理网络最大流量等于最小割容量，割集是分离源汇的最小边集，揭示流量与容量的对偶本质。对偶定理最小费用流在满足流量需求前提下最小化总运输费用，结合最短路算法寻找费用最小的增广链进行流量调整。最短路Chapter04整数规划与目标规划离散决策变量与多目标优化的建模与求解方法IntegerProgramming整数规划与分支定界法整数规划处理离散决策变量的优化问题，分支定界法通过系统分支与定界剪枝，在可行解空间中精确搜索最优整数解。问题分类纯整数规划（所有变量整数）、混合整数规划（部分变量整数）、0-1规划（变量仅取0或1，表示是否选择）。三类模型适用于不同决策场景。三类模型分支定界原理求解线性规划松弛，对分数变量分支为两个子问题，利用上下界剪枝排除非优分支，逐步收敛至最优整数解。算法效率取决于分支策略。剪枝收敛0-1规划应用项目投资选择、设施选址、任务指派等离散决策问题，可用隐枚举法或转化为整数规划求解。广泛应用于资源配置与组合优化。离散决策GoalProgramming目标规划：多目标决策方法目标规划通过引入偏差变量与优先级层次，将相互冲突的多目标决策问题转化为分阶段优化的单目标序列，寻求满意妥协方案。核心概念求解方法偏差变量正偏差d⁺表示超出目标值的部分，负偏差d⁻表示未达目标值的部分。目标约束通过引入偏差变量转化为等式形式，使决策模型能够同时处理目标的不足与超额情况，为后续优化提供量化基础。序贯式算法按优先级顺序逐层求解，每一层将上层最优值作为硬约束加入模型，依次优化各层目标的偏差变量。该方法严格保证高优先级目标的实现，在低优先级优化时不损害已达成的高优先级成果。优先级层次将多个目标按重要性排序为P₁、P₂…Pₖ，形成明确的优先层级结构。高优先级目标优先满足，低优先级目标在不损害高优先级目标的前提下进行优化，体现决策者的价值偏好与战略重点。加权法为同层目标赋予权重系数，将多目标转化为单目标加权和进行求解。适用于目标间可量化权衡的场景，通过权重调整反映不同目标的相对重要性，实现资源的合理配置与平衡。Chapter05动态规划与排队论多阶段决策优化与随机服务系统性能分析DynamicProgramming动态规划基本原理动态规划基于最优化原理，将多阶段决策问题分解为相互关联的子问题，通过递推求解获得全局最优策略，是处理序贯决策的强大工具。最优化原理最优策略的任一子策略对于其初始状态也是最优的，这一性质使问题可以分解递推求解。该原理保证了局部最优与全局最优的一致性。子问题分解状态与决策状态变量描述系统当前状况，决策变量确定阶段选择，状态转移方程刻画系统演化规律。二者共同构成动态规划的核心要素。状态转移递推方程从边界条件出发，逆序（或顺序）计算各阶段最优值函数，最终获得全程最优策略与最优值。递推是动态规划的核心计算方式。逆序求解维数灾难状态变量维度增加导致计算量指数增长，限制了动态规划在高维问题中的直接应用。需要结合近似方法或启发式策略来缓解。指数增长ClassicApplications动态规划经典应用动态规划在最短路径、资源分配、背包问题、生产存储等领域有广泛应用，通过合理定义状态与递推关系，高效求解多阶段优化问题。资源分配问题多项目资源最优分配将M单位资源分配给N个项目，每个项目收益为分配量的函数，动态规划按项目分阶段决策，状态为剩余资源量。M→N阶段决策资源分配问题逆推求解全局最优从最后一个项目开始，计算各状态下最优分配方案与最大收益，逐步回推获得全局最优策略。逆向递推背包问题0-1背包决策模型容量W，n个物品各有重量和价值，决策是否装入，状态为剩余容量，递推比较装入与不装入的最优值。W容量约束背包问题完全背包重复选取物品可重复选取，递推时考虑选取多个同物品的情况，状态转移与0-1背包略有不同。可重复选取QueueingTheory排队论基本概念排队论研究随机服务系统的性能分析与优化，通过到达过程、排队规则、服务机制三要素建模，为服务系统设计提供定量决策依据。系统组成顾客源、到达过程、排队结构、服务规则、服务台构成随机服务系统，Kendall记号标准化描述模型特征。Kendall记号到达与服务泊松到达（指数分布间隔时间）是最常见假设，服务时间通常为指数分布、Erlang分布或一般分布。泊松分布性能指标平均队长Ls、平均等待时间Wq、服务台利用率ρ、顾客损失概率等核心度量指标。L=λWQueueingTheory·ClassicalModels经典排队模型分析M/M/1与M/M/c是排队论的基础模型，通过稳态概率分析获得系统性能指标的解析解，为服务系统设计与资源优化配置提供定量依据。M/M/1模型01单服务台、泊松到达率λ、指数服务率μ，服务强度