清华运筹学教学课件

清华大学运筹学教学课件基础理论算法应用前沿···第一章运筹学概述与发展学科定位与发展历程11939-1945二战期间军事应运筹学（）是一门应用数学分支学科，利用数学模型、统计分析Operations Research用兴起和算法设计等方法，寻求复杂系统中的最优决策21947从二战军事应用发展至今，运筹学已成为现代管理科学和决策支持系统的核心理论基础，在人工智能时代继续焕发新的活力单纯形法的发明31960-1980理论体系完善4至今1990运筹学的现实意义资源有限性与优化需求在资源有限的现实世界中，如何实现最优配置是各行业面临的共同挑战运筹学提供了系统化的方法论和工具，帮助决策者在复杂约束下找到最佳解决方案交通运输航班调度、高铁网络规划、智能交通系统优化制造业生产计划排程、供应链优化、设备维护策略金融服务投资组合优化、风险管理、算法交易物流行业配送路径规划、仓储布局、库存管理课程结构与学习目标课程内容结构学习目标理论基础掌握运筹学基本概念和核心理论线性规划、整数规划、非线性规划等核心数学理论能够构建实际问题的数学模型模型构建熟悉主流优化算法的实现原理问题抽象、数学建模、约束表达的系统方法算法实现能够使用专业软件求解优化问题经典算法原理与实现，计算效率优化培养综合运用能力解决复杂决策问题案例分析实际工程问题的运筹学解决方案第二章线性规划基础线性规划模型构成线性规划是运筹学中最基础也最重要的模型类型，它要求目标函数和约束条件均为线性函数标准线性规划模型由以标准型与松弛型转换下要素构成决策变量需要确定的未知量，通常用表示x1,x2,...,xn目标函数需要最大化或最小化的线性函数z=c1x1+c2x2+...+cnxn约束条件问题中的限制条件，表示为线性等式或不等式非负约束标准型所有约束为等式，变量非负通常要求，即决策变量非负xi≥0松弛型引入松弛变量将不等式约束转为等式线性规划几何解释可行域与凸多面体最优解存在性与唯一性线性规划问题的约束条件在几何上形成一个凸多面体（或凸多胞形），称为可行域每个约束条件对应空间中的一个半空间，它们的交集构成可行域凸多面体的重要性质任意两点间的连线完全位于凸多面体内部•若可行域有界，则必为凸多胞形•若可行域无界，则延伸至无穷远•线性规划的基本定理若可行域非空且有界，则必存在最优解

1.若目标函数有最优值，则必有一个极点是最优解若多个极点都是最优解，则它们的任意凸组合也是最优解

3.这一性质是单纯形法的理论基础，解释了为什么我们只需考察可行域的顶点单纯形法核心思想从可行域顶点到顶点的迭代优化基本可行解与基变量在标准形式中，当个变量中有个变量值不为零（其中为约束方程数），且这个变量对应的系数矩阵列向量线性无关时，称这组解n m mm为基本可行解单纯形法的核心步骤从一个初始基本可行解开始

1.判断当前解是否最优，若最优则停止

2.若非最优，寻找能改善目标函数值的非基变量

3.确定换入变量和换出变量

4.通过高斯消元法更新基本可行解

5.返回步骤继续迭代

6.2单纯形法迭代路径示意图图中展示了单纯形法在求解过程中沿着凸多面体顶点移动的路径算法从一个初始可行解（顶点）出发，每次迭代都选择一个相邻的能够改善目标函数值的顶点，直至达到最优解几何直观理解单纯形法实际上是沿着可行域边界爬山（最大化问题）或下山（最小化问题）的过程，每次移动都确保目标函数值变得更优迭代优势数学保证只需考察可行域顶点（极点）线性规划基本定理确保了若问题有最优•解，则必有一个极点解是最优的单纯每次迭代目标函数值单调改善•形法正是利用这一性质，通过有限次迭有限步内可达最优解（若存在）•代找到最优极点对偶理论与灵敏度分析对偶问题构造对偶定理及经济解释对于任意线性规划原问题（称为原始问题），都可构造一个与之相关的对偶对偶理论的核心结论问题弱对偶性对任意可行解，原问题目标值对偶问题目标值≤强对偶性若原问题有最优解，则对偶问题也有最优解，且最优值相等原始问题P互补松弛性最优解时，原问题变量与对应对偶约束的松弛互为零影子价格与灵敏度分析对偶变量表示原问题中第个资源的边际价值（影子价格），衡量该资yi i源增加一单位对目标函数的贡献灵敏度分析研究参数变化对最优解的影响，帮助决策者理解模型的稳定性和对偶问题关键约束D第三章整数规划与组合优化整数规划模型特点与难点整数规划是线性规划的扩展，要求部分或全部决策变量取整数值这类问题广泛应用于不可分割资源分配、设施选址、生产计划等领域主要特点变量取离散值（整数或）•0-1可行域不再是连续凸集•求解计算复杂度显著增加•常见的整数规划类型•纯整数规划混合整数规划整数规划0-1要求所有变量均为整数部分变量为整数，部分为连续变量变量仅取或，表示选择与否01分支定界法基本框架分支定界法是求解整数规划的经典精确算法，核心思想是通过线性规划松弛和递归分支逐步逼近整数解经典组合问题介绍离散优化的重要应用场景指派问题背包问题将个任务分配给个工人，每个工人只能完从若干物品中选择装入背包，在满足容量约束n n成一个任务，目标是最小化总成本可通过匈的条件下，使总价值最大化是难问题的NP牙利算法高效求解代表旅行商问题TSP寻找穿过所有城市且每个城市只访问一次的最短闭合回路是组合优化中最著名的难问题之一NP难问题与启发式算法需求NP这些组合问题大多属于难问题，随着问题规模增大，精确求解变得不可行因此，在实际应用中，NP常需要借助启发式算法或元启发式算法获取接近最优的解启发式与元启发式算法面向大规模组合优化问题的实用方法贪心算法在每一步选择中都采取当前状态下最优的选择，不考虑全局简单高效但可能陷入局部最优局部搜索从一个初始解开始，不断寻找邻域中更优的解，直至无法改进包括爬山法、模拟退火、禁忌搜索等遗传算法模拟自然进化过程，通过选择、交叉、变异等操作不断优化解的种群，逐代接近全局最优启发式算法放弃寻找精确最优解的保证，转而追求在合理时间内找到满意的近似最优解第四章动态规划动态规划基本原理状态转移方程推导动态规划是解决具有重叠子问题和最优子结构特性的问题的有力方法其核心思想是将复杂问题分解为一系列子问题，并存储子问题的解以避免重复计算动态规划的关键要素1问题的阶段划分将问题分解为若干个子问题或阶段2状态的定义描述每个阶段可能的系统状况3决策变量的选择每个阶段需要做出的决策4状态转移方程描述决策如何影响状态变化状态转移方程是动态规划的核心，它描述了当前状态与之前状态之间的递推关系5边界条件问题求解的起点其中表示第个阶段的最优值•fn n表示最优操作（如最大或最小）•opt{...}表示第个阶段的决策价值•valn n正确构建状态转移方程是解决动态规划问题的关键动态规划经典实例背包问题动态规划解法设备更新问题模型与求解0-1背包问题从n个物品中选择若干放入容量为W的背包，使总价值最大化状态定义fi,w表示前i个物品放入容量为w的背包的最大价值状态转移方程其中wi和vi分别是第i个物品的重量和价值边界条件f0,w=0,对所有0≤w≤W设备随使用年限增加而效率降低、维护成本上升，需要决定每年是保留还是更换设备动态规划在实际中的应用资源分配库存管理解决多阶段资源分配问题，如预算分配、人确定最优库存策略，在需求波动环境下平衡力资源调度等动态规划能够找到在各个时库存成本与缺货风险间点上的最优分配策略案例季节性产品的生产与库存计划，考虑案例企业年度预算在多个部门间的最优分生产成本、库存成本和缺货损失配，实现整体收益最大化路径规划求解最短路径问题、网络流问题等，广泛应用于交通、通信和物流领域案例送货车辆的路径优化，考虑时间窗口约束和车辆容量限制动态规划的魅力在于将复杂问题分解为简单子问题，通过递推关系逐步构建最优解在实际应用中，关键是正确识别问题的最优子结构和重叠子问题特性第五章网络优化网络模型基本概念网络优化是运筹学中一个重要分支，研究在网络结构上的资源流动和优化问题网络用图GV,E表示，其中V是节点集，E是边集最短路径算法基本网络元素节点Nodes表示网络中的位置点，如路口、仓库、服务器等弧Arcs连接节点的边，可以是有向的或无向的，代表两点间的连接关系流Flow在网络上流动的物质或信息，如交通流、数据包、商品等容量Capacity弧上能够承载的最大流量算法Dijkstra最大流与最小割定理最大流问题最大流最小割定理给定一个有向图，每条边有一个容量，网络流理论中的基本定理，阐述了GV,E cu,v≥0源点和汇点，求从到的最大流量最大流与最小割之间的等价关系s ts t算法Ford-Fulkerson在任何网络中，最大流求解最大流的经典算法，核心思想是不断寻找增广路径的值等于最小割的容量并更新流量，直到不存在增广路径为止算法步骤这一定理不仅具有理论价值，也为初始化所有边的流量为

1.0设计算法提供了重要思路寻找一条从源点到汇点的增广路径

2.s t应用示例交通流量优计算路径上的可增加流量（即路径上所有边的剩余

3.化容量的最小值）更新路径上各边的流量

4.最大流算法可用于城市道路网络的

5.重复步骤2-4，直到不存在增广路径交通流量优化，通过分析路网结构，确定关键路段，提高整体通行能力最小费用流问题模型构建与求解方法求解算法最小费用流问题综合了网络流量与成本考虑，目标是在满足流量需求的前提下，最小化总传输成本循环消除法数学模型寻找负权回路并消除，逐步优化流量分配连续最短路径法通过迭代求解最短路径，逐步构建最优流量网络单纯形法其中线性规划单纯形法在网络上的特殊实现•cij边i,j上的单位流量成本•xij边i,j上的流量物流配送中的应用案例•bi节点i的净供应量（供应为正，需求为负）•uij边i,j的容量第六章非线性规划基础无约束优化问题求解方法梯度法利用函数梯度信息，沿负梯度方向迭代搜索步长选择对收敛性有重要影响牛顿法利用函数的二阶导信息，收敛速度比梯度法更快，但每次迭代计算量更大拟牛顿法避免计算和存储矩阵，使用近似矩阵替代，平衡计算效率和收敛速度Hessian无约束优化问题是求解其中是非线性函数与线性规划不同，非线性规划的解空间更为复杂，可能存在多个局fx部最优解无约束优化方法是处理复杂非线性问题的基础，也是约束优化方法中的子问题梯度信息的利用是这类方法的共同特点，准确的梯度计算对优化效果至关重要约束优化与条件KKT拉格朗日函数与对偶理论最优性条件详解KKT对于标准形式的约束优化问题构造拉格朗日函数其中是不等式约束的拉格朗日乘子•λi≥0是等式约束的拉格朗日乘子•μj拉格朗日对偶函数对偶问题条件是约束优化问题最优解的必要条件，在一定条件下也是充分条件Karush-Kuhn-Tucker KKT条件包括KKT稳定性条件∇xLx*,λ*,μ*=0原始可行性gix*≤0,hjx*=0对偶可行性λi*≥0互补松弛性λi*gix*=0条件是非线性规划算法设计的理论基础，也是判断解的最优性的重要工具KKT二次规划与半正定规划典型模型与应用领域应用领域二次规划QP目标函数为二次函数，约束为线性的优化问题应用领域•投资组合优化（Markowitz模型）•机器学习中的支持向量机•模型预测控制•轨迹规划半正定规划SDP决策变量为对称矩阵，约束为矩阵半正定的优化问题•控制系统设计与分析•图论中的松弛问题•传感器网络定位•量子信息处理算法实现要点二次规划算法有效集法、内点法、增广拉格朗日法等，对于凸二次规划（Q半正定）可高效求解半正定规划算法主要基于内点法，如主-对偶内点法，需要高效的线性代数运算库支持实现考虑第七章运筹学软件与编程实现常用优化软件介绍CPLEX Gurobi公司开发的商业优化求解器，功能强大，求解速度快，支持多种新一代商业优化求解器，性能卓越，算法实现效率高IBM编程语言接口优秀的求解性能•MIP线性规划、混合整数规划、二次规划等•良好的多线程并行计算支持•提供、、等多种•C++Java PythonAPI现代化的设计•API广泛应用于企业级优化系统•Lingo集建模语言和求解器于一体的优化软件，用户界面友好内置建模语言，易于学习和使用•支持广泛的优化问题类型•适合教学和中小规模应用•与中的优化工具箱Matlab Python优化工具箱优化库Matlab Python基本优化功能科学计算优化模块•Optimization Toolbox•SciPy.optimize全局优化线性规划建模工具•Global OptimizationToolbox•PuLP与其他工具箱良好集成凸优化问题建模••CVXPY强大的可视化和分析能力开发的优化工具集••OR-Tools Google算法编程示例单纯形法核心代码结构动态规划示例代码讲解#单纯形法Python实现示例import numpyas npdefsimplexc,A,b:求解线性规划标准形式min c^T xs.t.Ax=bx=0m,n=A.shape#m个约束，n个变量#初始化基变量索引basis=listrangen-m,n#构造单纯形表tableau=np.zerosm+1,n+1tableau[0,0:n]=c tableau[1:m+1,0:n]=A tableau[1:m+1,n]=b whileTrue:#检查最优性if np.alltableau[0,0:n]=0:break#选择进基变量enter=np.argmintableau[0,0:n]#选择出基变量ratios=[]for i in range1,m+1:iftableau[i,enter]0:ratios.appendtableau[i,n]/tableau[i,enter]else:ratios.appendfloatinf ifallr==floatinf forr inratios:return Unboundedleave=ratios.indexminratios+1#高斯-约当消元更新表pivot=tableau[leave,enter]tableau[leave,:]/=pivot for iin rangem+1:if i!=leave:factor=tableau[i,enter]tableau[i,:]-=factor*tableau[leave,:]#更新基变量索引basis[leave-1]=enter#提取解x=np.zerosn fori,b inenumeratebasis:x[b]=tableau[i+1,n]return x,-tableau[0,n]#返回最优解和最优值#0-1背包问题的动态规划实现def knapsack_01weights,values,capacity:解决0-1背包问题weights:物品重量列表values:物品价值列表capacity:背包容量返回最大价值和选择方案n=lenweights#物品数量#创建DP表dp=[[0for_in rangecapacity+1]for_in rangen+1]#填充DP表foriinrange1,n+1:for win rangecapacity+1:if weights[i-1]=w:#可以放入当前物品dp[i][w]=max values[i-1]+dp[i-1][w-weights[i-1]],dp[i-1][w]else:#不能放入当前物品dp[i][w]=dp[i-1][w]#回溯确定选择了哪些物品selected=[]w=capacity foriin rangen,0,-1:if dp[i][w]!=dp[i-1][w]:selected.appendi-1w-=weights[i-1]return dp[n][capacity],selected第八章运筹学前沿与发展趋势大数据与机器学习结合的优化方法随着数据量爆炸式增长和计算能力的提升，运筹学与大数据、机器学习的结合日益紧密，产生了一系列新的研究方向和方法强化学习在运筹学中的应用论数据驱动的优化直接从历史数据中学习优化策略，减少对显式数学模型的依赖通过大数据挖掘发现问题模式和隐含结构•利用统计学习改进参数估计和预测•机器学习辅助优化利用机器学习提高传统优化算法的效率预测约束的活性，减少搜索空间•强化学习通过试错与环境交互，学习最优决策策略，特别适合动态决策问题学习问题结构，自动选择合适的算法•在运筹学中的应用通过迁移学习加速类似问题的求解•动态资源分配与调度•库存管理与供应链优化•智能交通控制系统•能源系统管理•强化学习的价值在于能处理具有复杂动态、不确定性和大状态空间的决策问题，传统运筹学方法在这些问题上常面临计算挑战智能优化与元启发式算法进展生物启发算法最新研究实际案例分享智能制造调度粒子群优化模拟鸟群觅食行为的群智能算法，近年来发展了自适应参数调整、多目标扩展和混合变体等新方向蚁群算法模拟蚂蚁觅食路径的群体智能方法，新研究重点包括并行实现、参数自适应和与其他算法的混合策略进化算法基于自然选择和遗传机制的优化方法，最新进展包括差分进化、自适应进化策略和多种群并行进化某智能制造企业应用混合元启发式算法解决复杂生产调度问题，取得显著效果28%35%生产效率提升交付周期缩短通过优化工序安排和资源分配减少平均等待时间和流程瓶颈15%能源消耗降低优化设备运行模式和闲置时间运筹学在人工智能时代的角色自动决策系统与优化模型融合随着人工智能技术的快速发展，运筹学在智能决策系统中扮演着日益重要的角色，两者的融合产生了一系列创新应用和研究方向数据获取与处理问题建模与求解技术实现大规模数据的智能采集、清洗和特征提取，为优化模型提供高质量输运筹学方法提供严谨的数学框架，确保决策的最优性和可解释性AI入策略执行与调整持续优化与学习系统实现实时监控和自适应调整，应对动态变化的环境机器学习算法从历史数据中学习改进，不断提升优化模型的准确性AI未来研究方向展望未来运筹学将进一步深化与人工智能的融合，可能的发展方向包括可解释的优化、端到端自动建模系统、量子计算在组合优化中的应用、分布式协同优化等这些方AI向将显著扩展运筹学的应用边界，为复杂系统决策提供更强大的工具课程复习与知识框架总结重点模型与算法回顾123线性规划整数规划动态规划单纯形法、对偶理论、灵敏度分析分支定界法、割平面法、启发式算法最优子结构、状态转移方程、自底向上求解45网络优化非线性规划最短路径、最大流、最小费用流梯度法、条件、二次规划KKT典型应用场景串讲资源配置路径规划风险管理产能规划物流配送投资组合•••预算分配网络设计供应链风险•••人员调度交通规划应急预案•••本课程涵盖了运筹学的核心理论体系和算法框架，强调模型构建与实际应用的结合掌握这些知识点，将为解决复杂决策问题奠定坚实基础典型案例分析某大型物流企业配送路径优化生产计划动态调整实例问题描述某制造企业生产多种产品，面临订单变化频繁、设备故障随机发生等不确定因素，需要动态调整生产计划建模与求解问题描述构建多阶段随机规划模型，将未来不确定性通过情景树表示某电商物流公司每日需要从中心仓库向城市内数百个配送点派送包裹，需要设计合理的车辆路径以最小化总运输成本•第一阶段确定主生产计划建模与求解•后续阶段根据实际情况动态调整•目标函数平衡生产成本、库存成本和交付延迟惩罚将问题建模为带时间窗的车辆路径问题VRPTW，考虑车辆容量约束、客户时间窗要求和交通拥堵情况求解方法•采用混合整数规划建立数学模型•结合遗传算法和局部搜索的混合启发式算法求解•样本平均近似结合分解算法•利用历史交通数据预测路段行驶时间•滚动时域优化策略•机器学习预测关键参数变化实施效果实施效果•配送成本降低23%课程学习资源推荐提升运筹学实践能力的资源导航经典教材开源资源《运筹学》（清华大学出版社）系统全面地介绍运筹学基础理论与经典算法，是入门学习的首选教材《线性规划与网络流》（机械工业出版社）深入讲解线性规划和网络流理论，算法描述清晰，例题丰富《整数规划》（科学出版社）专注于整数规划理论与算法，包含最新研究进展《非线性规划理论与算法》（高等教育出版社）系统介绍非线性优化理论与计算方法代码库与在线课程GitHub:OR-Tools示例集GitHub:PyOptSparse-Python优化工具集Coursera:离散优化-墨尔本大学EdX:线性规划与组合优化-MIT实践平台NEOS Server-免费在线求解优化问题Kaggle-优化相关竞赛平台致谢与互动环节感谢您的参与和关注本课程旨在为同学们提供系统的运筹学知识框架，培养实际问题的数学建模和算法实现能力希望这些内容能够帮助大家在未来的学习和工作中更好地应用优化思维解决复杂问题欢迎提问与讨论关于课程内容的任何问题，都欢迎在课后与我们交流您可以通过以下方式联系课后当面交流•教学平台留言•邮件咨询•预约办公时间•鼓励深化学习运筹学的真正价值在于应用我们鼓励同学们结合自己的专业领域发掘应用场景•参与校内外优化建模竞赛持续学习资源•尝试解决身边的实际优化问题•学习小组加入课程学习小组，与同学共同探讨难题进阶讲座关注学院组织的运筹学前沿讲座科研项目有兴趣的同学可申请参与相关科研项目祝愿每位同学在运筹学的学习道路上取得成功！。