应用运筹学Ⅰ

课程概览

应用运筹学把业务问题表达为可计算的优化模型：先识别决策对象、目标、资源约束与变量边界，再选择线性规划、整数规划、网络算法或动态规划求解。课程材料从线性规划建模开始，经过图解法、单纯形法、对偶与网络优化，进入整数规划、分支定界和动态规划，最后用库存、排产、仓储、区域分配等项目讨论模型落地。

课程反复强调，求解器返回最优状态不等于业务模型正确。数据含义、单位、变量类型、约束完整性、整数可执行性、敏感性和管理解释都必须单独核验。

知识地图

模块	核心问题	课程材料支持的要点
线性规划	在资源有限时如何配置生产、采购或交付量？	决策变量、目标函数、约束、非负性；矩阵表示、标准型、图解法
单纯形法	如何在高维可行域中迭代寻找更优顶点？	基本解、基本可行解、入基、出基、最小比值检验、枢轴；大 `M` 法与两阶段法
对偶与敏感性	原问题的资源约束如何转化为价值判断？	对偶、弱对偶、强对偶、互补松弛、影子价格、机会成本；项目级敏感性分析
运输、指派与网络	如何把供给、需求、容量、距离和成本放进网络？	最小费用流、最短路径、最大流、最小生成树；销售区域指派与仓储网络
整数规划与分支定界	如何表达不可拆分的选择、启用和访问顺序？	0-1 变量、固定费用、集合模型、TSP 子回路消除、线性松弛、剪枝、割平面
动态规划	如何处理按时间或阶段推进、状态会变化的问题？	阶段、状态、决策、转移、价值函数、边界条件、Bellman 递推；确定性与随机性

核心模型与算法

线性规划建模

课程采用的标准型是

[ \max\; c^{\mathsf T}x ] [ \text{s.t.}\quad Ax=b,\qquad x\ge0。 ]

实际业务模型可以使用不等式。例如，资源配置常写为

\[ \max\; c^{\mathsf T}x, \qquad Ax\le b, \qquad x\ge0。 \]

建模顺序是：理解业务问题，定义决策变量，确定最大化或最小化目标，加入产能、预算、需求或成分约束，再检查变量边界和单位。Ax\le b 可引入松弛变量 s\ge0 改写为 Ax+s=b；Ax\ge b 可引入剩余变量改写为 Ax-s=b。自由变量可写成两个非负变量之差。

二维模型可以通过可行域和目标等值线理解。课程例题

\[ \max Z=3x_1+5x_2 \]

在

\[ x_1\le4,\qquad 2x_2\le12,\qquad 3x_1+2x_2\le18,\qquad x_1,x_2\ge0 \]

下得到课堂记录的最优顶点 (2,6)，目标值 Z^*=36。这个数值只属于该例题，不代表一般结论。

单纯形法

线性规划转为等式形式后，令非基变量为 0，由基变量解出基本解；若所有变量满足非负性，则为基本可行解。单纯形法在相邻基本可行解之间移动：

选择可改善目标的非基变量入基。
对入基列中保持可行所需的正系数进行最小比值检验。
选择首先降到 0 的基变量出基。
以枢轴元素做行变换，更新基。
目标行没有改善方向时停止。

目标行的正负判断取决于表格写法，不能脱离所用约定机械套用。等式或大于等于约束通常需要人工变量建立初始基。大 M 法在目标中惩罚人工变量；两阶段法先最小化人工变量总和，再恢复原目标。第一阶段最优值大于 0，说明原问题不可行。退化、循环、多重最优、不可行和无界是需要单独识别的情形。

对偶、影子价格与敏感性

对原问题

\[ \max\{c^{\mathsf T}x:Ax\le b,\ x\ge0\} \]

课程给出的对偶是

\[ \min\{b^{\mathsf T}y:A^{\mathsf T}y\ge c,\ y\ge0\}。 \]

原问题的约束对应对偶变量，原问题的变量对应对偶约束，系数矩阵转置，右端常数进入对偶目标。若 x 和 y 分别是原、对偶可行解，则弱对偶给出

\[ c^{\mathsf T}x\le b^{\mathsf T}y。 \]

在线性规划存在有限最优解时，强对偶说明两边在最优解处相等。互补松弛条件包括

\[ y_i\bigl(b_i-a_i^{\mathsf T}x\bigr)=0, \qquad x_j\bigl((A^{\mathsf T}y)_j-c_j\bigr)=0。 \]

对偶变量可解释为资源的影子价格：在其他条件不变且仍处于适用范围内，资源右端增加一个单位对最优目标的局部边际影响。资源有松弛时，对应影子价格为 0；产品的资源机会成本高于单位收益时，该产品变量可能为 0。

材料还支持项目级敏感性分析：改变运输成本、开仓成本、库存成本、服务率或扰动上限，观察方案和目标的变化；用 epsilon-constraint 把一个目标转为约束，逐步形成折衷方案。现有笔记没有完整呈现单纯形表的正式允许变化范围，因此不把项目趋势扩写成一般的后最优性定理。

运输、指派与网络优化

网络由节点和弧组成，弧可以携带距离、时间、容量或单位运输成本。最小费用流的通用形式是

\[ \min\sum_{(i,j)\in A}c_{ij}x_{ij} \]

并满足节点平衡

\[ \sum_{j:(i,j)\in A}x_{ij}- \sum_{j:(j,i)\in A}x_{ji}=b_i， \]

以及弧容量上下界。b_i 的正负含义按供给、需求的符号约定解释。

课程覆盖四类网络问题：

最小生成树：以最小总权重连接全部节点且不成圈；含 n 个节点的树有 n-1 条边。
最短路径：从指定起点到终点最小化距离、时间或成本。
最大流：在 0\le x_{ij}\le u_{ij} 和中间节点流量守恒下最大化源点到汇点的流量；增广链上的瓶颈容量决定每次增流量，残量网络中的反向弧允许撤销或重排既有流量。
最小费用流：在供需、流量平衡和容量约束下，以最低单位运输成本发送流量。

指派模型把不可拆分的对象分给人员或设施。例如销售区域项目中，x_{bs}=1 表示 break b 分配给销售代表 s，每个 break 满足

\[ \sum_s x_{bs}=1。 \]

工作量平衡可写成

\[ 0.8\le\sum_b w_bx_{bs}\le1.2。 \]

这是课堂项目的业务约束；运输、仓储和区域指派的具体规模与数值不能脱离项目数据推广。

整数规划与分支定界

整数规划用整数或二元变量表达不可拆分的决策。固定费用模型可写为

\[ \min\;cx+Ky, \qquad x\le My, \qquad x\ge0, \qquad y\in\{0,1\}。 \]

y=0 时禁止使用 x，y=1 时才开放数量上限。M 应来自业务容量或其他紧上界，不能随意取极大值。集合覆盖、集合包装和集合划分分别对应“至少一次”“至多一次”和“恰好一次”的覆盖要求。TSP 的入度、出度约束还不足以排除多个子回路，需要子回路消除约束、延迟约束或 MTZ 约束。

对最大化整数规划，去掉整数限制得到的线性松弛提供上界；当前最好整数可行解提供下界。对非整数变量 a=3.5 分支为

\[ a\le3\qquad\text{或}\qquad a\ge4。 \]

若节点上界不超过当前下界，执行界剪枝；松弛不可行时执行不可行剪枝；松弛解已整数时更新当前最佳解或关闭节点。预处理、强化约束和割平面可以缩小松弛区域，实际求解器常将它们与分支定界结合成分支切割法。

动态规划

动态规划适用于按阶段推进、状态随决策转移的问题。一个状态应包含继续决策所需的充分信息，使后续价值不依赖完整历史。确定性状态转移可写为

\[ s_{n+1}=T_n(s_n,x_n)。 \]

若从第 n 阶段起最小化未来总成本，Bellman 方程为

\[ F_n(s)=\min_{x\in X_n(s)} \left\{c_n(s,x)+F_{n+1}\bigl(T_n(s,x)\bigr)\right\}。 \]

递推需要边界条件，例如

\[ F_{N+1}(s)=0。 \]

求解时划分阶段，定义状态和可行决策，写出状态转移与边界条件，从末期逆向计算，再按保存的最优决策正向回溯。随机动态规划把未来价值替换为按转移概率加权的期望价值。课程赌博例子以当前资金为状态、下注额为决策，以最终达到目标资金的概率为价值，而不是直接比较随机资金数。

课堂案例与证据边界

案例	笔记明确记录的内容	证据边界
不锈钢配料	用原料采购量、成分要求和价格建立成本最小化模型	记录了部分比例和价格示例，没有完整数据表；不补写未出现的最优采购量
二维线性规划	三条资源约束、可行域、最优点 `(2,6)` 和 `Z^*=36`	只证明该课堂例题的结果，不外推为算法性能结论
BOM 与多周期排产	物料消耗、库存平衡、生产提前期、欠交和延期交付惩罚	变量关系有记录；不同企业的物料表、产能和成本需另取数据
彩票稳健定价	用最大赔付 `z`、发行上限和对偶变量讨论最坏利润与隐含概率	这是课堂建模案例，不对现实彩票规则或概率作外部判断
网络优化	公园道路、管道输水、地图路线和物资运输的网络抽象	例子用于说明模型类别，未提供可复算的完整网络数据
整数规划	切割下料、固定费用选址、集合模型、TSP 和分支定界树	重点是建模结构与求解逻辑，不把示意树当作实际求解记录
动态规划	资源分配、分层路径、机器负荷和赌博概率递推	课程给出了赌博例子的状态与概率；其他例子的完整参数未齐备
课程项目	主动缺货、销售区域、仓储网络、生产排程及敏感性结果	成本、距离、服务率、库存和加班数值均依赖项目版本，不能混用或普遍化

面向 AI 产品经理的应用

课程模型可迁移到 AI 产品的资源与运营决策，但以下应用是基于课堂方法的业务延伸，不是某一讲的逐字记录：

需求与资源配置：把算力、预算、标注量、席位或服务容量定义为资源，把质量、覆盖率、成本或利润写成目标和约束。
版本发布与运营排程：用多周期库存和提前期思路安排模型训练、评测、发布、回滚资源，显式记录期初状态、到货、需求和延期任务。
服务区域与网络设计：用指派、最短路径、最小费用流和仓储网络模型处理客户分群、服务节点、数据流和交付路径。
不可拆分的产品选择：用 0-1 变量表示是否启用某模型、供应商、功能或区域；固定费用与 Big-M 约束连接启用决策和连续用量。
多目标产品决策：把成本、服务水平、延迟、覆盖率或关系扰动通过权重、约束法和有效前沿呈现给决策者，而不是只报告一个目标值。
LLM 辅助建模：课程记录的流程包括读取数据、整理变量和约束、生成求解代码、解释结果与制作交付物。人必须运行代码，检查求解状态、单位、边界、约束和极端情形，不能把格式正确的模型或 API 当作已验证结果。

来源覆盖与材料限制

本页综合 15 份按日期命名的 Markdown 课堂笔记，覆盖 2026-03-02 至 2026-06-22：

2026-03-02：材料主要是设备、选课和课堂管理，无法确认运筹学定义、公式或例题。
2026-03-09 至 2026-03-30：覆盖建模、线性规划标准型、线性化、图解法、单纯形表、人工变量、大 M 法和两阶段法。
2026-04-13 至 2026-04-27：覆盖对偶、弱对偶、强对偶、互补松弛和网络优化。
2026-05-11 至 2026-06-01：覆盖整数规划、0-1 逻辑、TSP、求解器流程、分支定界、预处理、割平面和动态规划导入。
2026-05-18：字幕和课件材料不足，无法确认本讲主题与公式。
2026-06-08 至 2026-06-22：覆盖确定性与随机动态规划、LLM 辅助运筹项目，以及库存、区域分配、仓储和排产项目。

材料限制决定了本页不做以下推断：

未列日期是否授课、授课主题和讲授顺序；
课堂笔记之外的教材章节、完整考纲或求解器 API；
由部分字幕数值推导出的完整项目数据、最优方案或普遍行业结论；
把 2026-06-15 提及的非线性规划、EOQ、连续选址、研发投入和投资组合作为本页六个主模块的完整延伸。该讲明确以形式和案例介绍为主，未展开完整非线性规划算法。

因此，本页是一份基于现有课堂材料的课程级知识地图，不替代完整讲义、原始课件、教材或可复现实验数据。

发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：AI-PM Wiki Team
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用