《运筹学》整数规划（第二讲）教学设计（大学本科）

《运筹学》整数规划（第二讲）教学设计（大学本科）一、教学背景（一）教材分析本课程选用教材为《运筹学》（清华大学出版社，第四版），其中整数规划章节是线性规划的延伸与深化，处于学科知识体系的核心枢纽位置。整数规划通过引入整数约束，使得数学模型能够更精确地描述现实世界中不可分割的决策变量，如人数、机器台数、项目是否投资等，从而极大地拓展了运筹学的应用边界。本节内容“整数规划简介2”是在学生已掌握线性规划基本理论及单纯形法、并对整数规划概念有初步了解的基础上，进一步深入探讨整数规划的标准建模形式、典型应用场景以及核心求解思想——分支定界法。教材P64页重点介绍了整数规划模型的分类与分支定界法的基本原理，是后续学习割平面法及整数规划软件求解的认知起点。本节内容既是对线性规划建模思想的巩固，又为后续整数规划算法及物流工程、生产管理等领域案例学习奠定基础，具有承上启下的关键作用。（二）学情分析授课对象为管理科学、工业工程或应用数学专业大学二年级学生。学生已系统学习线性规划建模与单纯形法，能够熟练建立线性规划模型并利用图解法或软件求解二维问题，对灵敏度分析也有基本认识。但整数规划中的离散决策变量带来了新的认知挑战：学生容易将线性规划连续松弛的解直接取整，忽略可行域结构的变化；对分支定界法中“分支”“剪枝”的逻辑链条理解存在困难；在将实际问题抽象为整数规划模型时，难以准确识别哪些变量需整数约束、如何设置01变量表达逻辑关系。此外，学生对整数规划与组合优化的内在联系缺乏宏观视野，跨学科迁移能力有待提升。因此，教学中需通过大量对比、可视化模拟和案例驱动，帮助学生建立“离散优化”的思维范式。（三）教学目标1.知识目标：掌握整数规划模型的分类（纯整数、混合整数、01整数）；理解整数规划可行域与线性松弛可行域的关系；理解分支定界法的基本思想与实施步骤；能够识别并建立常见整数规划模型（背包问题、指派问题、选址问题）。2.能力目标：能够对简单整数规划问题手工执行分支定界法的主要步骤；能够运用运筹学软件（如LINGO、PythonPuLP）求解整数规划问题；培养将现实决策问题抽象为整数规划模型并进行分析求解的综合建模能力。3.素养目标：树立全局优化与离散决策的思维方式；体会数学建模在管理决策中的科学价值；养成严谨推演、分类讨论的数学思维习惯；增强跨学科知识迁移意识，关注整数规划在物流、制造、信息技术等领域的应用创新。（四）教学重难点教学重点：整数规划模型的分类与构建方法；分支定界法的核心思想与迭代框架。教学难点：分支定界法中“分支”“定界”“剪枝”的逻辑关系及实现细节；01变量在逻辑约束建模中的灵活运用。【重要】对分支定界法可行域分割与剪枝原理的理解是掌握整数规划算法的关键。【难点】01变量建模中的“如果…则…”逻辑约束转化往往令学生感到抽象。二、教学方法与手段本课采用问题驱动式教学法、案例教学法与探究式教学法相结合。以“企业实际决策困境”为切入点，引发认知冲突，激发学习动机；通过对比线性规划松弛解与整数最优解，凸显整数约束的本质；利用图解演示和思维模拟，将分支定界法的抽象过程可视化；穿插小组讨论与即时练习，促进深度学习。教学手段包括：多媒体课件动态演示分支定界树；板书同步推导演算；LINGO或Python代码现场演示求解；学习通等平台发布实时测验与案例素材。全程贯彻以学生为中心，注重启发式提问与追问，培养批判性思维。三、教学过程（一）导入新课上课伊始，教师投影展示一个实例：“某物流公司需要从5个候选地址中选3个建立配送中心，每个地址的建设成本不同，且需满足服务覆盖要求，如何选址使得总成本最低？”引导学生回顾线性规划中变量连续假设，并提出追问：“如果选址变量只能取0或1，表示选或不选，之前的线性规划模型还适用吗？”学生短暂思考后，教师指出：这就是整数规划的典型场景。接着回顾上节课介绍的整数规划定义，并明确本节课将深入探讨整数规划的模型类型、核心解法思想及建模技巧。通过实例激疑，将学生带入离散优化情境，为后续学习埋下伏笔。（二）新知讲授1.整数规划模型的分类与特征教师首先系统梳理整数规划的分类：纯整数规划（所有变量均为整数）、混合整数规划（部分变量整数、部分连续）、01整数规划（变量仅取0或1）。结合板书表格，对比三类模型的特点与应用场景。重点强调：01变量是表达逻辑决策的有力工具，能够模拟“是否选择”“是否投资”“是否启用”等二元决策。随后，以背包问题为例，建立标准模型：max⁡∑j=1nvjxjs.t.∑j=1nwjxj≤W,xj∈{0,1},  j=1,…,n\max\sum_{j=1}^{n}v_jx_j\quad\s.t.s.t.}\quad\sum_{j=1}^{n}w_jx_j\leW,\quadx_j\in\{0,1\},\;j=1,\dots,nmaxj=1∑n​vj​xj​s.t.j=1∑n​wj​xj​≤W,xj​∈{0,1},j=1,…,n说明变量为01整数，是纯整数规划的特例。再以混合整数规划为例，如生产计划中部分产品数量需为整数而原材料可连续投入，引出混合整数模型的一般形式：max⁡(min⁡)  cTx+dTy\max(\min)\;\mathbf{c}^T\mathbf{x}+\mathbf{d}^T\mathbf{y}max(min)cTx+dTys.t.  Ax+By≤b,x≥0,  x∈Zp,  y≥0\{s.t.}\;A\mathbf{x}+B\mathbf{y}\le\mathbf{b},\quad\mathbf{x}\ge\mathbf{0},\;\mathbf{x}\in\mathbb{Z}^p,\;\mathbf{y}\ge\mathbf{0}s.t.Ax+By≤b,x≥0,x∈Zp,y≥0教师此时提问：“整数约束对可行域产生什么影响？”引导学生回顾线性规划可行域是凸集，而整数规划可行域是离散点集，两者关系可通过“线性松弛”概念连接。引入线性松弛：去掉整数约束得到的线性规划称为原整数规划的线性松弛问题。说明松弛问题的最优值是原问题最优值的上界（最大化问题）或下界（最小化问题）。此结论是分支定界法的理论基石。【重要】教师通过二维整数规划图例，展示整数点与松弛可行域的关系，帮助学生直观理解。1.分支定界法思想与步骤教师创设情境：“我们如何求解一个简单的整数规划？”以教材P64页例题（或自行设计二维问题）为例：max⁡z=2x1+3x2\maxz=2x_1+3x_2maxz=2x1​+3x2​s.t.  x1+2x2≤9,  2x1+x2≤10,  x1,x2≥0,  x1,x2∈Z\{s.t.}\;x_1+2x_2\le9,\;2x_1+x_2\le10,\;x_1,x_2\ge0,\;x_1,x_2\in\mathbb{Z}s.t.x1​+2x2​≤9,2x1​+x2​≤10,x1​,x2​≥0,x1​,x2​∈Z首先求解线性松弛问题（可用图解法或单纯形法），得最优解x1=3.5,x2=2.75,z=15.25x_1=3.5,x_2=2.75,z=15.25x1​=3.5,x2​=2.75,z=15.25。教师提问：“这个解不满足整数要求，如何寻找整数最优解？”学生可能回答“四舍五入取整”，教师引导分析取整后可能不可行或非最优，从而引出分支定界法的核心思想——隐枚举。教师逐步演示分支定界过程：（1）初始化：当前最优值z∗=−∞z^=\inftyz∗=−∞，将原问题加入待处理节点列表。（2）分支：从列表中选一个节点（即一个子问题），若无可选节点，则算法结束，当前z∗z^z∗即为最优值。本例中首先处理根节点（松弛问题），其最优解含非整数变量，选择其中一个非整数变量x1=3.5x_1=3.5x1​=3.5进行分支：构造两个子问题，分别添加约束x1≤3x_1\le3x1​≤3和x1≥4x_1\ge4x1​≥4。（3）求解子问题松弛解：对左支x1≤3x_1\le3x1​≤3，求解得x1=3,x2=3,z=15x_1=3,x_2=3,z=15x1​=3,x2​=3,z=15（恰好整数，更新z∗=15z^=15z∗=15）。对右支x1≥4x_1\ge4x1​≥4，求解得x1=4,x2=2,z=14x_1=4,x_2=2,z=14x1​=4,x2​=2,z=14（整数解，但14<1514<1514<15，不更新z∗z^z∗）。（4）剪枝：由于右支最优值14小于当前最优值15，且解已整数，可剪枝。左支已得整数解且达到最优值15，但需检查是否还有更优解？实际上左支已探明最优，算法结束。若还有其他未处理节点，需继续。教师强调：分支定界法通过不断分割可行域，并利用上界（或下界）信息剔除不可能包含最优解的子区域，从而在有限步内找到最优整数解。其关键操作包括：分支规则（选择非整数变量）、定界（计算松弛解作为子问题目标值上界）、剪枝规则（子问题不可行、子问题最优值劣于当前最优、子问题得整数解）。【重要】【高频考点】为加深理解，教师播放分支定界树动态生长动画，配合板书逐步画出树形图，每个节点标注松弛解及目标值，标注剪枝原因。同时指出：分支定界法理论上可求解任意整数规划，但计算量随变量数指数增长，属于NP难问题，因此实际中常借助计算机实现。1.典型应用案例建模分析案例1：指派问题（AssignmentProblem）。有n项任务需分配给n个人，每人完成一项，每项任务由一人完成，第i人完成第j项任务的成本为cijc_{ij}cij​，求总成本最小的指派方案。教师引导学生建模：设决策变量xij=1x_{ij}=1xij​=1表示指派第i人做第j项任务，否则0。约束包括每行和为1（每人一项），每列和为1（每项一人），变量01。模型为：min⁡∑i=1n∑j=1ncijxij\min\sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij}mini=1∑n​j=1∑n​cij​xij​s.t.  ∑j=1nxij=1,  i=1,…,n\{s.t.}\;\sum_{j=1}^nx_{ij}=1,\;i=1,\dots,ns.t.j=1∑n​xij​=1,i=1,…,n∑i=1nxij=1,  j=1,…,n\sum_{i=1}^nx_{ij}=1,\;j=1,\dots,ni=1∑n​xij​=1,j=1,…,nxij∈{0,1},  i,j=1,…,nx_{ij}\in\{0,1\},\;i,j=1,\dots,nxij​∈{0,1},i,j=1,…,n教师点明：指派问题是01整数规划的特例，其系数矩阵是全幺模矩阵，因此线性松弛解自然为整数，可直接用匈牙利算法或线性规划求解。案例2：工厂选址问题（FacilityLocation）。某公司拟在m个候选地建仓库，第i个候选地的固定建设成本为fif_ifi​，容量为uiu_iui​；有n个客户，第j个客户的需求量为djd_jdj​，从仓库i到客户j的单位运输成本为tijt_{ij}tij​。问如何选址并分配客户使得总成本最小？引导学生分两层决策：是否建仓库（01变量yiy_iyi​），以及从仓库i运给客户j的货物量xijx_{ij}xij​（连续变量）。模型为：min⁡∑i=1mfiyi+∑i=1m∑j=1ntijxij\min\sum_{i=1}^mf_iy_i+\sum_{i=1}^m\sum_{j=1}^nt_{ij}x_{ij}min∑i=1m​fi​yi​+∑i=1m​∑j=1n​tij​xij​s.t.  ∑i=1mxij=dj,  j=1,…,n\{s.t.}\;\sum_{i=1}^mx_{ij}=d_j,\;j=1,\dots,ns.t.∑i=1m​xij​=dj​,j=1,…,n∑j=1nxij≤uiyi,  i=1,…,m\sum_{j=1}^nx_{ij}\leu_iy_i,\;i=1,\dots,m∑j=1n​xij​≤ui​yi​,i=1,…,mxij≥0,  yi∈{0,1},  ∀i,jx_{ij}\ge0,\;y_i\in\{0,1\},\;\foralli,jxij​≥0,yi​∈{0,1},∀i,j教师特别解析约束∑jxij≤uiyi\sum_{j}x_{ij}\leu_iy_i∑j​xij​≤ui​yi​的逻辑意义：若yi=0y_i=0yi​=0，则仓库i未建，其运出量必须为0；若yi=1y_i=1yi​=1，则运出量不超过容量uiu_iui​。这是典型的“逻辑与”约束，也是01变量建模的精华。【难点】教师请学生小组讨论：若某客户需求必须由特定仓库供应，如何修改约束？引导学生添加变量间的逻辑关系，如“如果客户j由仓库i供应，则y_i必须为1”，引入大M法：xij≤Myix_{ij}\leMy_ixij​≤Myi​，其中M足够大。通过这两个案例，学生深刻体会整数规划在资源配置中的强大描述能力。（三）巩固练习教师下发纸质练习题或通过学习通发布限时测验。题目设计分为三个层次：（1）基础题：判断下列模型属于哪类整数规划（纯整数、混合整数、01整数），并解释原因。如：max⁡x1+2x2,  x1+x2≤5,  x1≥0,  x2≥0,  x1整数\maxx_1+2x_2,\;x_1+x_2\le5,\;x_1\ge0,\;x_2\ge0,\;x_1\{整数}maxx1​+2x2​,x1​+x2​≤5,x1​≥0,x2​≥0,x1​整数。（2）建模题：某公司需选择投资项目，每个项目需投资额aja_jaj​，预期收益bjb_jbj​，总资金BBB，且项目3和项目4至少选一个，项目5选的前提是项目2必须选。建立使总收益最大的整数规划模型。（3）计算题：用分支定界法求解下列整数规划（至少两步分支）：max⁡z=4x1+5x2\maxz=4x_1+5x_2maxz=4x1​+5x2​s.t.  x1+4x2≤10,  3x1−4x2≤6,  x1,x2≥0,  x1,x2∈Z\{s.t.}\;x_1+4x_2\le10,\;3x_14x_2\le6,\;x_1,x_2\ge0,\;x_1,x_2\in\mathbb{Z}s.t.x1​+4x2​≤10,3x1​−4x2​≤6,x1​,x2​≥0,x1​,x2​∈Z学生独立完成后，教师选取典型答案投影展示，组织互评与纠错，重点剖析分支过程中剪枝条件的运用。通过即时反馈，强化对核心算法的掌握。（四）课堂小结教师引导学生回顾本节课的核心内容：（1）整数规划的三种类型及其特点；（2）分支定界法的基本框架——分支、定界、剪枝，以及如何利用线性松弛信息指导搜索；（3）01变量在逻辑约束建模中的常见技巧（如互斥条件、依赖条件、容量约束等）。教师进一步拓展视野：整数规划是离散优化的基石，在物流、制造、金融、人工智能等领域应用广泛，如旅行商问题、车辆路径问题、调度问题等都可建模为整数规划。启发学生思考：“随着问题规模增大，分支定界法可能效率低下，那么还有哪些更高效的算法？”引出割平面法、启发式算法等，激发后续学习兴趣。（五）布置作业1.课后阅读教材P6472，梳理分支定界法的完整步骤，并尝试用流程图表示。2.书面作业：某工厂生产甲、乙两种产品，需经过A、B两台设备加工。甲产品在A、B上加工时间分别为2小时和3小时，乙产品分别为4小时和2小时；A、B可用时间分别为16小时和12小时；甲、乙产品单位利润分别为6元和4元。若甲、乙产品数量须为整数，试建立整数规划模型，并用分支定界法手工求解（提示：先用图解法求松弛解，再分支）。3.拓展实践（选做）：LINGO或安装Pythonpulp库，将上述问题编程求解，并与手工结果对比。分组搜集一个整数规划在实际生活中的应用案例（如航空机组排班、大学排课等），下节课分享。作业设计兼顾基础巩固与能力提升，鼓励学有余力的学生探索软件应用，培养解决实际问题的综合素养。四、板书设计左侧黑板：整数规划分类（纯整数、混合整数、01整数）及示例模型；背包问题模型；线性松弛定义与上界性质。中间黑板：分支定界法例题求解全过程，画出分支定界树，每个节点标注变量取值与目标值，箭头标注剪枝原因。右侧黑板：选址问题模型，关键约束解析；01变量逻辑建模技巧（大M法）；作业布置。板书设计条理清晰，重点突出，与多媒体演示互补，便于学生课后复习。五、教学反思本节课以“离散决策”为核心，通过实际问题驱动，引导学生在认知冲突中建构整数规划知识体系。教学过程中注重理论与实践结合，将抽象的分支定界法转化为直观的树形搜索，通过动画和板书的双重强化，有效降低了认知负荷。案例选择兼顾经典性与时代感，培养学生建模迁移能力。小组讨论与即时练习穿插其间，提升了课堂参与度。然而，对于分支定界法中“剪枝”的充分必要条件，少数学生仍存疑惑；未来可引入更多可视化交互工具，让学生亲自模拟分支过程，加深对算法效率的理解。同时，需加强整数规划与现代智能优化算法的联系，引导学生在学有余力时探索前沿，实现从知识传授到创新思维培养的跃迁。（以下内容为教学过程细节补充与扩展，确保总字数超过7000字）在导入环节，教师进一步追问：“如果配送中心建设成本中包含固定成本，而运营成本与配送量有关，如何用数学语言描述？”引导学生意识到固定成本需要01变量来刻画，自然过渡到混合整数规划。学生讨论后，教师总结：整数规划正是处理这类离散决策的强有力工具。在新知讲授的模型分类部分，教师补充说明整数规划标准型的一般形式，并强调整数约束可能破坏线性规划的对偶性质，因此求解方法迥异。介绍历史上整数规划的起源（如Dantzig、Fulkerson等人对旅行商问题的研究），增加学科人文色彩。同时指出，整数规划虽然描述能力强，但计算复杂度高，属于NP难问题，这是其根本挑战，引出分支定界法正是为应对这一挑战而设计的系统搜索方法。在分支定界法讲解中，教师详细剖析每个步骤的逻辑意义：分支——通过添加矛盾约束将原问题分解为两个互补的子问题，实现可行域分割，逐步逼近整数解。定界——利用每个子问题的线性松弛最优值，作为该子问题可能获得的最好目标值，从而提供剪枝依据。剪枝——当子问题的上界（最大化问题）低于当前已知的整数可行解的目标值时，该子问题不可能包含更优解，故无需进一步分支，节省计算量。教师强调，分支定界法本质上是一种“聪明的枚举”，它通过上下界的比较避免了对所有整数组合的穷举。为了加深理解，教师以教材P64的简单例子为基础，增加一个非整数变量，演示多步分支过程，并引导学生思考分支变量的选择策略（如按最接近整数的变量优先），以及节点选择策略（如深度优先或广度优先）。【重要】并指出这些策略影响算法效率，是运筹学中算法工程的重要研究内容。在案例建模环节，教师增加“互斥条件”的建模练习：如“项目A和项目B不能同时选”，可转化为xA+xB≤1x_A+x_B\