课程目标
- 能陈述对偶单纯形法的适用条件：检验数全部 \(\sigma_j \ge 0\)（min 型）而基解 \(\mathbf{b}\) 存在负分量；
- 能用表格手工执行完整的对偶单纯形迭代（先选出基行，再按最大比值选入基列），并判定无可行解情形；
- 能解释该方法与原始单纯形法的对偶关系，以及迭代中目标值（对偶下界）的单调性；
- 能在新增约束的灵敏度分析场景中，从旧最优表热启动求解，避免从头重解。
毕业要求 2-1 扎实数学基础 毕业要求 3-2 建模与求解 毕业要求 4-1 算法论证
前测：先修诊断
Q1（对偶理论）：对 min 型问题，某基 \(\mathbf{B}\) 对应检验数 \(\sigma_j = c_j - z_j\)。判定「当前基是对偶可行」的条件是？
Q2（单纯形法）：原始单纯形法迭代中，表格右端 \(\mathbf{b} = \mathbf{B}^{-1}\mathbf{b}_0\) 始终保持什么性质？
先修回顾路径
回顾卡片：min 型单纯形表三要素——①基变量列 \(\mathbf{x}_B=\mathbf{B}^{-1}\mathbf{b}_0\)；②检验数行 \(\sigma_j=c_j-\mathbf{c}_B^T\mathbf{B}^{-1}\mathbf{A}_j\)；③最优 ⇔ \(\sigma_j\ge 0\ \forall j\) 且 \(b_i\ge 0\)。建议先复习教材对偶理论小节（强对偶定理 + 互补松弛），点击下方按钮继续，本课不阻断你。
脚手架路径
额外分步例题：先用 1 轮迷你迭代熟悉「先选行、后选列」：\(\mathbf{b}=(-2,0)^T\)，出基行只能选第 1 行；该行 \(a_{11}=-1,\ a_{12}=-4\)，比值 \(\theta_1=\sigma_1/(-1),\ \theta_2=\sigma_2/(-4)\)（均为负数），取最大者入基。下面模块三的迭代器请逐格点「下一步」，每步先自己预测再核对。
挑战路径
高 Bloom 任务：①证明：对偶单纯形中若出基行 \(\bar{a}_{rj}\ge 0\ \forall j\) 而 \(\bar b_r<0\)，则原问题无可行解（提示：该行乘 \(-1\) 后与 \(\mathbf{x}\ge 0\) 矛盾，或从对偶无界论证）；②探究：Klee–Minty 型反例下对偶单纯形与原始单纯形的迭代次数关系；③读完综合任务后，尝试用对偶可行基直接写出对偶问题最优解 \(\mathbf{y}^*\)。
模块一：为什么需要对偶单纯形法
And：你已经会用原始单纯形法求解：从一个原始可行基（\(\mathbf{b}\ge 0\)）出发，保持可行性，沿可行域顶点走到最优。
But：两种常见情况让这个起点消失——①化标准形后剩余变量作基，\(\mathbf{b}\) 出现负分量，初始解不可行；②方案执行前临时新增约束（如产能上限），原最优解失效，\(\mathbf{b}\) 变负而检验数仍 \(\sigma\ge 0\)。此时原始单纯形无从起步，从头重解又太浪费。
Therefore：换一个「保持对象」：既然检验数行已是对偶可行的，就全程保持 \(\sigma\ge 0\)，转而逐步消除 \(\mathbf{b}\) 的负分量——这就是对偶单纯形法。
两种方法对比
| （原始）单纯形法 | 对偶单纯形法 | |
|---|---|---|
| 初始状态 | \(\mathbf{b}\ge 0\)（可行），\(\sigma\) 任意 | \(\sigma\ge 0\)（对偶可行），\(\mathbf{b}\) 可有负分量 |
| 保持量 | 原始可行性 \(b_i\ge 0\) | 对偶可行性 \(\sigma_j\ge 0\) |
| 选择顺序 | 先选列（入基），再按 \(\theta\) 选行（出基） | 先选行（出基），再按 \(\theta\) 选列（入基） |
| 终止条件 | \(\sigma_j\ge 0\ \forall j\) | \(b_i\ge 0\ \forall i\) |
| 目标值含义 | 原始目标 \(w\)，单调下降（min） | 对偶目标 \(w_D=\mathbf{y}^T\mathbf{b}_0\)，单调上升，从下方逼近 \(w^*\) |
模块二：迭代规则
对偶单纯形法（min 型）：设标准形 \(\min\ \mathbf{c}^T\mathbf{x},\ \mathbf{A}\mathbf{x}=\mathbf{b}_0,\ \mathbf{x}\ge 0\)。若当前基满足 \(\sigma_j\ge 0\ \forall j\) 但 \(\exists\, r:\ \bar b_r<0\)，按下述规则迭代，全程保持对偶可行，直至 \(\bar{\mathbf{b}}\ge 0\)。
无可行解判定。若某次迭代中 \(\bar b_r<0\) 而该行 \(\bar a_{rj}\ge 0\ \forall j\)，则原问题无可行解。
证明（点击展开，两种视角）
收敛性。对偶单纯形法每次迭代产生对偶可行基，其目标值 \(w_D=\mathbf{y}^T\mathbf{b}_0\) 单调不减且有上界 \(w^*\)（弱对偶性）；基的数量有限，配合 Bland 类避免循环规则，算法有限步终止。
模块三：完整例题与交互式迭代
例题
加剩余变量 \(x_3, x_4\)，两个约束各乘 \(-1\) 使 \(-x_1-x_2+x_3=-5\)、\(-x_1-2x_2+x_4=-8\)。取 \(\{x_3,x_4\}\) 为初始基：\(\bar{\mathbf{b}}=(-5,-8)^T<0\) 原始不可行，但 \(\boldsymbol{\sigma}=(2,3,0,0)^T\ge 0\) 对偶可行——正是对偶单纯形的用武之地。
互动：对偶单纯形迭代器（表格 × 几何联动）
改变：迭代步；保持不变：例题与迭代规则；测量：出基/入基选择、对偶目标值 \(w_D\)、几何路径。先预测每步的出基行与入基列，再点「下一步」核对。
练习（应用层）：在例题表 2 中（基 \(\{x_3,x_2\}\)，\(\bar{\mathbf{b}}=(-1,4)^T\)，\(\boldsymbol{\sigma}=(\tfrac12,0,0,\tfrac32)^T\)，第 1 行 \((-\tfrac12,\ 0,\ 1,\ -\tfrac12)\)），应对哪些列计算比值 \(\theta_j\)？
模块四：几何与对偶视角
原始空间里发生了什么
迭代器右侧的几何图显示：初始基解 \((0,0)\) 是不可行点；第一轮后基解 \((0,4)\) 仍违反第一条约束；第二轮才落到可行域顶点 \((2,3)\)——恰好是最优解。与原始单纯形「在可行域边界上行走」不同，对偶单纯形是从可行域外逐步走进最优顶点。
严格地说，每步迭代的检验数都对应一个对偶可行解 \(\mathbf{y}\)：非基剩余变量检验数给出 \(\mathbf{y}=(\sigma_3,\sigma_4)\) 的对偶读数，对偶目标值 \(w_D=\mathbf{y}^T\mathbf{b}_0\) 沿 \(0\to 12\to 13\) 单调上升——它是对偶问题的「可行迭代」，这与原始单纯形 \(w\) 单调下降形成完美镜像。
综合任务：新增约束的热启动
场景：例题的最优方案 \(x^*=(2,3)\) 已排产。执行前工厂临时新增产能约束 \(x_1 \le 1\)，原方案失效。要求：从旧最优表出发，用对偶单纯形法热启动求新最优，禁止从头重解。
提示（旧最优表，基 \(\{x_1,x_2\}\)）：
| 基 | \(x_1\) | \(x_2\) | \(x_3\) | \(x_4\) | \(\bar{\mathbf{b}}\) |
|---|---|---|---|---|---|
| \(x_1\) | 1 | 0 | −2 | 1 | 2 |
| \(x_2\) | 0 | 1 | 1 | −1 | 3 |
| \(\sigma\) | 0 | 0 | 1 | 1 | \(w=13\) |
脚手架三档（按自身情况选择）：
- L1 全脚手架：新约束 \(x_1+x_5=1\) 加入后，用 \(x_1\) 行消去 \(x_1\) 得第 3 行 \((0,0,2,-1,1\mid -1)\)；你只需完成一次出基/入基选择（答案：出基 \(x_5\)，比值 \(\theta(x_4)=\sigma_4/\bar a_{34}=1/(-1)=-1\)，取最大者 \(x_4\) 入基）并完成旋转，得 \(x^*=(1,4),\ w^*=14\)。
- L2 半脚手架：只给你「新行 \(\bar{\mathbf{b}}\) 为负且 \(\sigma_5=0\) 仍对偶可行」，其余自行推导。
- L3 无脚手架：仅给场景与新增约束，独立完成消元、迭代与最优性验证，并说明为什么旧最优表上热启动是合法的（检验数行未变）。
自检（分析层）：热启动后新问题的最优值 \(w^*=14\) 与旧值 \(13\) 的关系说明什么？
后测
Q1（理解）：对偶单纯形法全程保持的性质是？
Q2（应用）：某次迭代，出基行元素为 \((-2,\ 0,\ -3)\)（依次对应非基变量 \(x_1,x_2,x_3\)），检验数 \(\sigma_1=4,\ \sigma_2=1,\ \sigma_3=9\)。入基列应选？
Q3（分析）：迭代中出现 \(\bar b_r=-2<0\) 且该行 \(\bar a_{rj}\ge 0\ \forall j\)，结论是？
拓展资源
- 教材《最优化方法》对应章节：对偶单纯形法与灵敏度分析（按课程教学大纲指定章节复习）。
- Vanderbei, R. J. Linear Programming: Foundations and Extensions — The Dual Simplex Method 一节（英文进阶视角）。
- 进阶探究：原始–对偶算法框架；内点法中同样利用「原始–对偶同时迭代」思想（与 KKT 条件衔接）。
课程知识图谱
授课教师
教师：关老师（数学学院） 答疑方式：课后答疑 + 课程群提问；本页 AI 助教可先解答常见疑问。