整数规划教学课件

整数规划教学课件目录整数规划简介整数规划模型类型定义、重要性及与线性规划的区别纯整数规划、混合整数规划、0-1整数规划求解整数规划的方法经典整数规划算法LP松弛与舍入法、枚举法、分支定界法、割平面法Gomory割平面法、分支定界法详解、算法比较整数规划应用案例软件工具与实操演示资本预算、生产计划、设施选址、运输与分配问题第一章整数规划简介什么是整数规划？整数规划是数学规划的一个重要分支，其特点是线性规划模型中部分或全部变量被限制为整数•用于解决实际中不可分割的决策问题，如机器台数、人员数量、生产批次等与线性规划的关键区别解空间非凸，求解复杂度显著提高整数规划的重要性现实问题的真实需求直接舍入的危害离散决策建模现实世界中很多决策变量必须是整数值，非整将线性规划的非整数解直接舍入可能导致不可支持是/否类型的离散决策，如项目是否投数解往往毫无意义行解或严重次优解资、工厂是否建设等线性规划与整数规划解空间对比线性规划解空间整数规划解空间•凸多面体区域•离散点集•连续可行域•非凸可行域•最优解通常在顶点上•最优解可能在任意整数点•多项式时间可解•NP难问题第二章整数规划模型类型纯整数规划（）Pure IntegerProgramming定义所有决策变量均被限制为整数值的规划问题数学表示典型应用场景•设备采购数量决策•生产批次安排•人员调度问题混合整数规划（）Mixed IntegerProgramming定义部分变量限制为整数，其余变量为连续变量的规划问题典型应用场景数学表示•生产计划（批次数为整数，产量可为小数）•物流配送（车辆数为整数，装载量可为小数）其中x表示整数变量，y表示连续变量整数规划（）0-1Binary IntegerProgramming定义所有整数变量仅取0或1的特殊整数规划典型应用场景数学表示项目选择问题（是否投资）设施选址问题（是否建设）变量含义背包问题（是否装入）•xj=1选择第j个选项/开启第j个设施•xj=0不选择第j个选项/关闭第j个设施第三章求解整数规划的方法整数规划是NP难问题，已发展出多种算法应对不同类型和规模的问题松弛与舍入法LP基本思路

1.忽略整数约束，将问题转化为线性规划（LP松弛）

2.求解松弛后的线性规划问题

3.对非整数解进行舍入，获得整数解优缺点分析优点简单易行，计算量小缺点舍入可能导致不可行解或严重次优解适用场景•快速获得初始解或上界•整数约束不太紧的问题•对精确度要求不高的场合枚举法基本思路

1.系统地列举所有可能的整数解

2.检查每个解的可行性

3.在所有可行解中选择最优值优缺点分析优点概念简单，确保找到全局最优解缺点计算量随问题规模指数增长具有n个变量、每个变量有k个可能取值的问题，需要检查kn个解，计算复杂度为Okn适用场景•极小规模问题•变量数量和取值范围有限•教学演示分支定界法（）Branch andBound基本思路

1.求解LP松弛问题

2.如果解是整数，则找到最优解

3.否则，选择一个非整数变量xi分支•添加约束xi≤xi*⌊⌋•添加约束xi≥xi*⌈⌉适用场景

4.递归求解子问题，利用界限剪枝•中小规模整数规划问题核心思想通过分治和剪枝系统地搜索整数解空间•混合整数规划•大部分实际应用场景优点能够有效处理大多数实际问题，是目前最常用的方法割平面法（）Cutting Plane基本思路

1.求解LP松弛问题

2.如果解是整数，则找到最优解否则，构造一个割平面约束，使其•能够切除当前非整数解•不切除任何整数可行解

4.添加割平面约束，重新求解

5.重复以上步骤直到获得整数解适用场景•纯整数规划问题•特殊结构问题（如单纯割平面很有效）优缺点收敛可能较慢，但与分支定界法结合使用效果显著分支定界法搜索树示意图分支定界法通过构建搜索树，系统地探索整数规划的解空间上图展示了一个典型的分支定界过程•根节点代表LP松弛问题•每个分支代表一个整数约束（如x1≤2或x1≥3）•带叉节点表示被剪枝的分支（因不可行或界限较差）•绿色节点表示找到的整数可行解•最终确定的最优解标记为红色通过界限估计和剪枝技术，分支定界法避免了完全枚举，大大提高了求解效率第四章经典整数规划算法详解深入探讨几种主要整数规划算法的具体步骤、实现细节及其比较分支定界法流程松弛求解变量分支LP忽略整数约束，求解线性规划问题选择一个非整数变量xi*，分别添加约束xi≤xi*和xi≥xi*，生成两⌊⌋⌈⌉个子问题界限计算与剪枝节点选择与搜索计算子问题的上界/下界，若某分支界限劣于已知可行解，则剪枝选择最有希望的节点继续搜索，可采用深度优先、宽度优先或最佳优先策略关键设计决策分支变量选择通常选择离整数最远的变量，或对目标函数影响最大的变量节点选择策略影响搜索效率，常用最佳界限优先或深度优先策略上下界计算更紧的界限可以提高剪枝效率，加速求解算法比较与适用场景算法优点缺点适用场景割平面法理论上有限步收敛收敛可能很慢纯整数规划，特殊结构问题分支定界法适用性广，实现简单最坏情况下为指数时间混合整数规划，一般问题分支切割法结合两种方法优点实现复杂大规模复杂问题拉格朗日松弛提供更紧的界限只给出界限，不直接给解特殊结构问题，如分解结构现代求解器趋势综合利用多种技术，包括预处理、启发式、割平面生成、分支策略和并行计算等第五章整数规划应用案例通过实际案例展示整数规划在各领域的应用，包括资本预算、生产计划、设施选址等资本预算问题问题描述公司有n个投资项目可选，每个项目i有预期收益ri和所需资金ci，总预算为B，目标是选择投资组合使总收益最大数学模型其中xi=1表示选择项目i，xi=0表示不选择扩展考虑•项目之间的依赖关系约束•风险因素控制•多期投资决策•资源除资金外的其他限制生产计划与固定成本问题问题描述公司生产m种产品，每种产品j有单位利润pj，生产量xj，但启动生产线有固定成本fj，受n种资源限制数学模型关键挑战其中yj=1表示启动产品j的生产线，Mj为充分大的常数•固定成本导致非线性，需通过0-1变量线性化•批量生产的经济规模与边际成本权衡•产品组合与资源配置平衡设施选址问题问题描述在n个候选地点中选择建设仓库或工厂，使m个客户点的服务成本最小化数学模型其中yi=1表示在i地建设设施，xij表示i地设施服务j客户的比例应用变体•覆盖型选址问题•容量限制型选址问题•竞争性选址问题•动态选址问题运输与分配问题12传统运输问题整数约束场景将m个供应点的货物运送到n个需求点，•运输批次必须是整数使总运输成本最小基本模型是线性规•运输车辆数量是整数划，但实际问题中通常涉及整数约束•运输路径选择（0-1决策）3车辆路径问题确定一组车辆的最优行驶路线，服务所有客户点并满足各种约束（如时间窗、车辆容量等）典型的NP难问题，需要整数规划求解运输与分配问题通常结合网络流理论和整数规划方法求解，是物流领域的核心优化问题设施选址示例分析上图展示了一个设施选址问题的典型场景从多个候选点中选择最佳仓库位置，以最小化总成本并确保客户需求得到满足关键决策因素•固定成本（建设、租赁）•竞争对手分布•运输成本（距离、时间）•扩展可能性•客户覆盖范围•地理限制•容量限制•政策法规通过整数规划模型，可以系统地评估这些因素，找到总成本最小的解决方案第六章软件工具与实操演示介绍求解整数规划的主流软件工具，并通过实例演示模型构建与求解过程常用整数规划软件商业软件开源软件编程语言接口CPLEX IBM公司开发，功能强大，求解GLPK GNU线性规划工具包Python PuLP,Pyomo,SciPy速度快CBC COIN-OR分支切割求解器MATLAB intlinprog函数Gurobi近年来表现优异的商业求解器SCIP混合整数规划求解器R lpSolve,ROI包OR-Tools Google开发的优化工具集Julia JuMP建模语言LINGO LINDOSystems开发，界面友好XPRESS FICO公司产品，整合多种优化技术选择合适的工具取决于问题规模、复杂度、预算和用户偏好大规模商业应用通常选择CPLEX或Gurobi，教学和研究可考虑开源工具实操演示用求解整数规划LINGO资本预算问题LINGO代码示例MODEL:!资本预算问题模型;SETS:项目/

1..5/:收益,成本,选择;ENDSETSDATA:收益=2015253010;成本=151025208;预算=50;ENDDATA!目标函数最大化总收益;MAX=@SUM项目i:收益i*选择i;!预算约束;@SUM项目i:成本i*选择i=预算;!整数约束;@FOR项目i:@BIN选择i;END求解步骤

1.启动LINGO，输入或导入模型

2.点击Solve按钮开始求解

3.观察求解过程和状态窗口

4.查看Solution Report获取详细结果

5.分析敏感性报告，进行决策支持课程总结与展望课程要点回顾未来发展趋势•整数规划是解决离散优化问题的核心工算法持续改进，处理超大规模问题具•主要类型包括纯整数规划、混合整数规划和0-1整数规划结合机器学习技术加速求解过程•分支定界法和割平面法是求解的基本方法云计算环境下的分布式求解•应用广泛，包括资本预算、生产计划、设施选址等•现代求解器结合多种技术，效率不断提更广泛的实际应用场景，如智慧城升市、精准医疗等希望同学们通过本课程，掌握整数规划的基本理论与方法，并能灵活运用到实际问题中去，为解决复杂决策问题贡献智慧。