管理运筹学课件 第七章：优化模型构建

1第七章：优化模型构建7.1引言同一现实问题往往有多种数学表达；变量定义改变，模型规模、约束结构和求解速度也会改变。学习目标：能选择变量视角、构造关键约束，并解释模型的管理含义。7.2多样的建模方式以单机器调度为主线，比较时间点、两两加工顺序和紧前加工顺序三种模型。7.3有效的约束业务逻辑→约束线性化→有效不等式。27.1建模的核心：把业务规则翻译为可求解结构模型质量首先取决于问题理解，而不是公式复杂度。每一步都要回答：变量代表什么？单位是什么？约束删除后会出现什么非法方案？课堂思考同一问题为什么会有不同模型？答案通常从变量视角开始。识别问题定义变量构造目标表达约束求解模型验证解释37.2单机器调度：统一问题，三种变量视角目标：最小化加权完工时间Σ(j)w(j)C(j)。共同规则：加工不可中断；机器同一时刻至多加工一个工件。三种视角何时开始？谁在谁之前？谁紧接着谁？符号含义管理解释建模提示p(j)工件j加工时间占用机器的持续时间单位必须统一w(j)工件j权重优先级/延误成本影响目标，不改变可行性C(j)工件j完工时间开始时刻+加工时间由变量视角决定表达T计划期上界最晚可能完成时刻常取Σ(j)p(j)47.2.1时间点决策：直接决定每个工件何时开始决策变量：xjt，xjt=1表示工件j在t时刻开始加工；否则xjt=0。若在t开始，则完工时刻为t+pj。

约束条件：

57.2.1容量约束必须覆盖整个加工区间正确约束：对每个时刻τ，统计所有满足t≤τ<t+p(j)的开始变量。Σ(j)Σ(t:t≤τ<t+p(j))x(j,t)≤1模型诊断只写Σ(j)x(j,τ)≤1为什么不够？它只禁止同时开始，不能禁止后续重叠。0123456工件A：t=0开始，p(A)=3工件B：t=1开始，p(B)=2A加工区间B加工区间两者开始时刻不同，但在[1,3)发生重叠67.2.1时间点模型：完整结构与适用条件变量规模约为nT。T越大，变量和容量约束越多；但时间相关业务规则最容易加入。适合：计划期较短，或需精细表达时窗/分时资源。

77.2.2加工顺序决策：用两两先后替代时间索引决策变量：xjk=1表示工件j在工件k之前加工；否则xjk=0。

87.2.2加工顺序决策：用两两先后替代时间索引完整模型变量视角时间点模型问：何时开始？顺序模型问：谁在谁之前？一旦先后关系完整，就可以恢复开始与完工时间。优势：变量规模不依赖计划期T。

9课堂练习用4个工件检验顺序模型任务1：分别写出时间点变量和两两先后变量。任务2：给出一个可行顺序，并计算加权完工时间。思考如何从x(j,k)的取值恢复完整加工顺序？工件加工时间p(j)权重w(j)A24B13C31D22107.2.3紧前关系：直接构造一条加工链决策变量x(j,k)=1：工件k紧接着工件j加工。最优解直接给出相邻关系，沿弧即可恢复完整顺序。虚拟工件0：加工链起点n+1：加工链终点0J3J1J4J2n+1117.2.3紧前关系：直接构造一条加工链决策变量x(j,k)=1：工件k紧接着工件j加工。最优解直接给出相邻关系，沿弧即可恢复完整顺序。0J3J1J4J2n+1

127.2.4三种模型没有绝对优劣，取决于数据结构选择原则：结合计划期、工件数量、时窗规则和求解测试。模型越直观不一定越快；约束越少也不一定越强。情境判断计划期短？工件多？停机时段复杂？模型核心变量规模特征主要优势主要局限时间点x(j,t)约nT个0-1变量时窗/分时资源直观T大时迅速膨胀两两顺序x(j,k)约n²个0-1变量不依赖时间离散需完整去闭环约束紧前关系x(j,k),C(j)约n²+n个变量直接恢复加工链依赖大M与上界质量13拓展总拖期目标可以嵌入三种建模方式共同目标：minΣ(j)v(j)。差别只在于每种模型如何表达C(j)。选择提示新增目标不会自动修复原模型的结构弱点。原模型C(j)表达保留结构新增拖期约束时间点Σ(t)[t+p(j)]x(j,t)唯一开始+区间容量v(j)≥C(j)-d(j)两两顺序p(j)+Σ(k)p(k)x(k,j)两两排序+去闭环v(j)≥C(j)-d(j)紧前关系直接使用C(j)度约束+大M时序v(j)≥C(j)-d(j)147.3有效的约束约束的三重作用①排除业务上不可执行的方案；②收紧可行域，提高模型强度；③改善求解效率和结果解释。7.3.1非直观约束：蕴含、互斥、同选、去闭环。7.3.2约束线性化：正部、乘积、分段函数。7.3.3有效不等式：不删整数可行解，只收紧松弛。157.3.1非直观约束：先检查真值，再写0-1表达写完后逐个枚举关键取值：哪些组合应允许？哪些组合必须排除？课堂练习若选C，则A、B恰好选一个；D只有在B被选时实施。业务逻辑0-1约束检查要点选1⇒必须选2x₁≤x₂x₁=1时强制x₂=1方案2和3同选同不选x₂=x₃两变量始终一致三个方案至多选两个x₁+x₂+x₃≤2排除全选方案1和2互斥x₁+x₂≤1不能同时为1至少选择一个方案Σ(j)x(j)≥1排除全不选167.3.2正部函数可用线性下界替代

177.3.20-1变量×连续变量：用边界构造线性包络已知：x∈{0,1}，0≤y≤M，需要表达z=xy。核心是分别验证x=0与x=1两种情形。z≥y-M(1-x)z≤y0≤z≤Mx边界提醒：若y可取负值，必须使用已知L、U构造四条包络。187.3.2分段函数与大M：严格不等式必须谨慎

197.3.3有效不等式收紧松弛，但不能删除整数可行解作用：减少分支节点、改善松弛界、帮助求解器更早剪枝。证明义务：新增不等式对原模型的全部整数可行解都成立。

20本章小结：

变量定义决定结构，约束质量决定可解性建模检查清单变量：对象、下标、单位、取值范围是否明确？目标：方向、权重和单位是否与管理目标一