线性规划：运筹学的基石
线性规划（LP）是考研运筹学专业课中出现频率最高、变体最丰富的模块。其标准形式为：
max cᵀx
s.t. Ax ≤ b
x ≥ 0
核心考点：
• 单纯形法迭代（进基变量选择、出基变量确定、检验数计算）
• 对偶模型构建（对称性：原问题≤→对偶变量≥0）
• 灵敏度分析（目标系数cᵢ变化范围、资源约束bⱼ变化对最优解影响）
【2023·华中科技大学】某工厂生产甲、乙两种产品，单位利润分别为300元与500元。生产一件甲需A工序2小时、B工序1小时；乙需A工序1小时、B工序3小时。A工序日可用工时100，B工序80。求最大日利润。
解题模板：
1. 建模：设x₁,x₂为产量
max Z=300x₁+500x₂
s.t. 2x₁+x₂≤100（A）
x₁+3x₂≤80（B）
x₁,x₂≥0
2. 标准化：加松弛变量x₃,x₄
3. 单纯形表：迭代至所有σⱼ≤0
4. 结果：x₁=26, x₂=18, Z=16800元
5. 灵敏度：A工序工时在[80,120]内最优基不变
【易错点】：检验数σⱼ=cⱼ−zⱼ，zⱼ=∑c_Bᵢaᵢⱼ。若出现σⱼ=0且对应变量非基，说明存在多重最优解！
整数规划：现实约束的精准刻画
整数规划（IP）是LP的扩展，要求部分或全部变量为整数。常见类型：
• 纯整数规划（所有变量∈ℤ）
• 混合整数规划（部分变量∈ℤ）
• 0-1规划（xᵢ∈{0,1}，用于逻辑建模）
核心算法：分支定界法（Branch & Bound）——通过LP松弛获得上界，分支缩小可行域，剪枝淘汰劣解。
【2021·同济大学】某项目有4个可选子项目，投资与收益如下（单位：万元）：
| 项目 | 投资 | 收益 |
||||
| 1 | 21 | 40 |
| 2 | 30 | 50 |
| 3 | 12 | 20 |
| 4 | 15 | 30 |
总投资额≤45万元，求最大收益。
解题步骤：
1. 建模：max Z=40x₁+50x₂+20x₃+30x₄
s.t. 21x₁+30x₂+12x₃+15x₄≤45
xᵢ∈{0,1}
2. LP松弛：得x₁=1,x₂=0.5,x₃=0,x₄=0 → Z=65（上界）
3. 分支：x₂=0 或 x₂=1
4. 剪枝：x₂=1时投资超限（30>45），剪枝；x₂=0时解为x₁=1,x₃=1,x₄=0,Z=60
5. 最优解：选项目1+3，收益60万元
【技巧】：0-1规划中，“若选项目1则必须选项目2” → x₁≤x₂；“项目3与4互斥” → x₃+x₄≤1
网络分析：流动系统的优化艺术
网络模型将问题抽象为节点与边的集合，适用于路径、流量、连接等场景。核心算法：
• 最短路：Dijkstra（非负权）、Bellman-Ford（含负权）
• 最大流：Ford-Fulkerson法（增广链）、Edmonds-Karp（BFS找增广路）
• 最小生成树：Kruskal（边排序）、Prim（点扩展）
【2020·北京交通大学】下图运输网络，弧旁数字为容量，求从s到t的最大流：
s→A(3), s→B(2), A→B(1), A→t(2), B→t(3)
Edmonds-Karp流程：
1. 初始化：f=0
2. BFS找增广路：s→A→t，瓶颈=min(3,2)=2 → f=2
3. 残量网络更新：sA=1, At=0；反向边As=2, tA=2
4. BFS：s→B→t，瓶颈=min(2,3)=2 → f=4
5. 残量：sB=0, Bt=1；Bs=2, tB=2
6. BFS：s→A→B→t，瓶颈=min(1,1,1)=1 → f=5
7. 无新路径 → 最大流=5
【重要定理】：最大流最小割定理——最大流值=最小割容量。割(S,T)将顶点分为两部分，割容量=∑c(u,v)（u∈S,v∈T）。
动态规划：多阶段决策的黄金法则
动态规划（DP）通过“状态+决策+递推”解决具有最优子结构与无后效性的问题。关键三要素：
① 阶段（k=1,2,...,n）
② 状态（sₖ：第k阶段初始条件）
③ 决策（uₖ：从sₖ到sₖ₊₁的选择）
【2022·上海财经大学】某企业有3台设备分配给4个车间，各车间收益如下表（单位：万元）：
| 车间 | 0台 | 1台 | 2台 | 3台 |
||--|--|--|--|
| 1 | 0 | 3 | 7 | 9 |
| 2 | 0 | 4 | 6 | 8 |
| 3 | 0 | 5 | 8 | 10 |
| 4 | 0 | 6 | 9 | 11 |
求最大总收益。
DP建模：
- 阶段k：车间号（1→4）
- 状态sₖ：分配给k~4车间的设备数
- 状态转移：fₖ(sₖ)=max{gₖ(xₖ)+fₖ₊₁(sₖ−xₖ)}
- 边界：f₅(s₅)=0
逆序计算：
k=4：f₄(0)=0, f₄(1)=6, f₄(2)=9, f₄(3)=11
k=3：f₃(0)=0, f₃(1)=max{5+6}=11, f₃(2)=max{5+9,8+6}=14, ...
k=2：f₂(3)=max{4+14,6+11,8+6}=18
k=1：f₁(3)=max{3+18,7+14,9+11}=22
→ 最优分配：车间1分1台、车间2分0台、车间3分2台、车间4分0台，收益22万元
【高频变体】：背包问题（0-1/完全）、最长路、资源分配、生产存储问题
目标规划：多目标决策的平衡术
目标规划（GP）允许存在多个冲突目标，并通过偏差变量d⁺/d⁻量化偏离程度。其标准形式：
min Z=∑pₖ(d⁺ₖ+d⁻ₖ)
s.t. ∑aᵢⱼxⱼ + d⁻ₖ − d⁺ₖ = bₖ
xⱼ,d⁺ₖ,d⁻ₖ≥0
其中pₖ为优先级（p₁≫p₂≫p₃），确保高优先级目标优先满足。
【2019·西安电子科技大学】某厂生产A/B产品，目标：
P₁：利润≥1200元
P₂：工时≤120小时
P₃：A产量≥B产量
已知：A利润30元/件，B利润20元/件；A工时2h/件，B工时1h/件。
建模：
min Z=p₁d₁⁻ + p₂d₂⁺ + p₃d₃⁻
s.t. 30x₁+20x₂ + d₁⁻ − d₁⁺ = 1200
2x₁+x₂ + d₂⁻ − d₂⁺ = 120
x₁ − x₂ + d₃⁻ − d₃⁺ = 0
x₁,x₂,dᵢ⁺,dᵢ⁻≥0
求解：先满足P₁（d₁⁻=0），得2x₁+x₂≤120；再满足P₂（d₂⁺=0），得x₁=20,x₂=40；最后P₃：d₃⁻=20（A比B少20件）。若允许调整，可牺牲部分利润（d₁⁻>0）换取P₃满足。
【关键理解】：目标规划不追求“最优”，而追求“满意解”，其解可能是帕累托最优的折中点。
综合建模与证明题：区分高下的分水岭
近年顶尖院校（如清华、浙大）加大证明题与综合题比重，常见题型：
• 对偶理论证明（如“若原问题无界，则对偶问题无可行解”）
• 灵敏度分析推导（如“当c₁在何范围内，最优解不变？”）
• 多模块融合建模（如“结合网络流与整数规划设计应急物资调度方案”）
【2024·浙江大学】证明：若线性规划问题有最优解，则其对偶问题也有最优解，且目标函数值相等。
标准证明流程：
1. 设原问题最优解为x，检验数σⱼ=cⱼ−c_B B⁻¹aⱼ≤0（最优性）
2. 令y = c_B B⁻¹，则y为对偶问题可行解（因σⱼ≤0 ⇒ Aᵀy≥c）
3. 对偶目标值z=c_B x_B = y B x_B = y b（因B x_B = b）
4. 故对偶问题存在可行解y，且目标值等于原问题最优值
→ 由对偶理论，对偶问题有最优解，且z=w。
【备考建议】：背熟6大经典定理的证明框架，结合真题模拟推演，确保逻辑链无漏洞。
基础要求：
• 线性代数：矩阵运算、秩、线性方程组求解（单纯形法依赖基变换）
• 微积分：导数、偏导、极值判断（KKT条件基础）
• 概率论：仅部分院校涉及（排队论、存储论）
现实数据：2023年调研显示，数学专业考生平均分78.6，经管类考生72.1，工科类（机械/土木）68.3——差异主要源于建模思维而非纯数学能力。通过系统训练，非数学专业完全可达到75+。
入门路径：
① 第1周：掌握LP建模（从“生产计划”“ diet problem”等经典案例入手）
② 第2周：手算单纯形法（至少完成3道完整迭代）
③ 第3周：对比对偶模型（原问题与对偶问题写法互译）
④ 第4周：网络模型专项（画图→标容量→手动求解）
推荐工具：Excel规划求解（验证结果）、LINGO（建模练习）、运筹学在线模拟器（如NEOS Server）
政策差异：
• 多数院校允许使用普通计算器（不可编程、无存储功能）
• 清华、上交等校禁止计算器，要求手算（单纯形表、标号法）
• 财经类院校（如央财）允许带 Scientific Calculator
应对策略：
- 目标院校若禁计算器：强化手算熟练度（每日1道单纯形表）
- 允许计算器：练习“快速输入+关键步骤验算”（避免输入错误）
- 共同原则：草稿纸分区书写（建模/计算/验算），避免混乱