第 13 章 线性规划：单纯形法

学习目标

读完本章，你应当能够：

1. 把任意线性规划（含不等式、自由变量、上界、极大化）改写成标准形 \(\min c^Tx,\ Ax=b,\ x\ge0\)，并写出它的对偶问题。
2. 从 KKT 条件出发理解弱对偶、强对偶（线性规划对偶定理）与互补松弛，并把对偶变量解释为约束的影子价格。
3. 说清"基本可行点 = 可行多面体的顶点"以及"有解就有顶点解"这两条几何事实，并由此理解为什么单纯形法只在顶点间搜索、为什么 LP 的最优解往往很稀疏。
4. 手算或编程执行单纯形法的一步：定价、选进基变量、比值检验、换基；会用两阶段法找初始基。
5. 了解实现中的关键工程问题：LU 分解及其更新、定价规则（Dantzig、部分定价、最陡边）、退化与循环。
6. 能读懂 scipy.optimize.linprog 的输出（目标值、对偶值 marginals），并用 LP 求解最小 CVaR 组合。

读前导读

这一章在解决什么问题

线性规划（LP）是"目标和约束全是线性"的优化问题。你在 CPA 管理会计里已经做过它的最简单版本：产能有限时，按"单位约束资源的边际贡献"给产品排序，决定生产组合。那个方法只适用于一个瓶颈资源；一旦机器工时、原材料、人工同时紧张，排序法就失灵了，需要 LP。本章讲 LP 的两件事：最优解长什么样（对偶与影子价格、顶点解）和怎么找到它（单纯形法）。

对偶理论是本章最值钱的部分。每个 LP 都有一个"孪生"问题：原问题问"怎样安排生产最赚钱"，对偶问题问"每单位瓶颈资源值多少钱"。两个问题的最优值相等（强对偶），对偶变量就是第 12 章讲过的影子价格。衍生品定价里的"无套利 ⇔ 存在正的状态价格"、超额复制价格，数学核心也正是 LP 对偶（练习 10）。

单纯形法的思路是"沿着可行区域的棱角走"。LP 的最优解总能在可行区域的某个角上找到，所以算法从一个角出发，每次挑一条让目标变好的棱走到相邻的角，直到没有更好的棱为止。这个"角上有解"的事实还解释了一个实务现象：LP 型组合（如最小 CVaR）通常只持有少数几只资产。

需要先想起来的数学

1. 矩阵乘法与线性方程组 \(Ax=b\)。 \(A\) 是 \(m\) 行 \(n\) 列，\(Ax=b\) 就是 \(m\) 个线性方程、\(n\) 个未知数。例如资源约束"产品 A 每件用 1 工时、B 每件用 1 工时，共 80 工时"写成 \((1,1)\binom{a}{b}=80\)。转置 \(A^T\) 是行列互换，\(c^Tx=\sum_ic_ix_i\) 是内积（逐项相乘再相加，比如"单价 × 数量"的总成本）。见 第 00 册第 06 章 线性代数速成。

2. 矩阵的逆、非奇异与秩。 方阵 \(B\) 非奇异指它可逆，等价于方程 \(Bx=b\) 有唯一解，等价于它的列线性无关。\(A\) 行满秩指 \(m\) 个方程彼此不重复、不矛盾（没有一条约束能由其他约束推出）。例：\(\begin{bmatrix}1&1\\1&2\end{bmatrix}\) 非奇异，\(\begin{bmatrix}1&1\\2&2\end{bmatrix}\) 奇异（第二行是第一行的 2 倍）。见 第 00 册第 06 章。

3. KKT 条件与影子价格。 本章直接套用第 12 章的结论：凸问题中 KKT 条件就是最优的充要条件，乘子是约束右端每放宽 1 单位、最优值的变化量。如果第 12 章的 12.3–12.4 节还不熟，建议先回看。

4. 凸集与多面体。 集合中任意两点的连线都还在集合内，叫凸集。有限个线性不等式和等式围成的区域叫多面体，它的"角"叫顶点。二维时就是一个凸多边形。\(\binom nm\) 是"从 \(n\) 个里选 \(m\) 个"的组合数，例如 \(\binom52=10\)。见 第 00 册第 05 章 多元微积分与优化。

怎么读这一章

核心必读是 13.2（标准形）、13.3（KKT、对偶、影子价格）、13.4 的定理 13.2–13.3 和"LP 解为什么很稀疏"、13.5（单纯形法一步的逻辑）和 13.8（代码）。建议先读 13.3 并把对偶的经济含义想清楚，再读 13.4–13.5。

第一次可以跳过或只看结论的是 13.4 的两个证明、13.6.1 的 LU 更新细节、13.6.2 的最陡边递推公式 (13.38) 和 13.6.4 的字典序策略。这些是求解器开发者关心的工程问题，作为使用者，你只需要知道"商业求解器已经处理好了，linprog(method="highs") 可以放心用"。13.8.3 的 CVaR 代码与读者的风险管理经验关系最紧密，值得逐行看懂。

13.1 为什么量化研究员需要线性规划

先说结论：线性规划（linear programming, LP）是最成熟、最可靠的优化工具。软件极其成熟，求解结果是全局最优，规模可以到百万变量。Dantzig 在 20 世纪 40 年代末提出单纯形法，这通常被视为现代优化学科的开端；七十多年后，管理、经济、金融、工程领域的大量模型仍然被写成线性形式交给单纯形软件求解。

即便真实问题是非线性的，线性模型也常有吸引力：一是软件可靠、保证找到全局最优；二是数据本身就有很大不确定性，一个精巧的非线性模型可能只是"精确地拟合了噪声"。

在量化交易里，下面这些问题本质上都是 LP：

• 最小化 CVaR（条件在险价值）的组合优化（Rockafellar–Uryasev 形式，本章 13.8 节实现）；
• 最小绝对偏差（MAD） 风险模型、\(\ell_1\) 跟踪误差最小化的指数复制（第 14 章实现）；
• 带线性交易成本和换手约束的再平衡：\(|w_i-w_i^0|\) 可以拆成买入、卖出两个非负变量；
• 资产定价中的无套利检验和超额复制价格：其数学核心是 LP 对偶（Farkas 引理）；
• 混合整数规划（最小交易手数、持仓数量上限）的分支定界，需要反复求解 LP 松弛。

本章讲单纯形法（simplex method），下一章讲内点法（interior-point methods）。两章共享同一套最优性与对偶理论，它们是第 16 章二次规划的直接前身。

13.2 标准形与转换技巧

线性规划的目标和约束都是线性的。可行集是若干半空间与超平面的交，称为多面体（polytope）：它是凸的、连通的，各个"面"都是平坦的多边形。目标函数的等值线是平面。最优解可能是唯一的一个顶点，也可能是整条边、整个面，甚至整个可行集（当目标与某个面平行时）。

本书统一使用标准形（standard form）：

其中 \(c,x\in\mathbb R^n\)，\(b\in\mathbb R^m\)，\(A\) 为 \(m\times n\) 矩阵。任何 LP 都能化成这个形式，常用技巧有四个：

1. 不等式 \(Ax\ge b\)：引入剩余变量（surplus variable） \(z\ge0\)，写成 \(Ax-z=b\)。
2. 不等式 \(Ax\le b\)：引入松弛变量（slack variable） \(y\ge0\)，写成 \(Ax+y=b\)；单个上界 \(x\le u\) 同理写成 \(x+w=u,\ w\ge0\)。
3. 自由变量（无符号限制）：拆成两部分 \(x=x^+-x^-\)，其中 \(x^+=\max(x,0)\ge0\)，\(x^-=\max(-x,0)\ge0\)。
4. 极大化：\(\max c^Tx\) 改为 \(\min(-c)^Tx\)。

例如 \(\min c^Tx\) s.t. \(Ax\ge b\)（\(x\) 自由）化为标准形：

量化提示：拆分 \(x=x^+-x^-\) 正是组合再平衡里"买入量 \(b_i\) 与卖出量 \(s_i\)"的建模方式：\(w_i-w_i^0=b_i-s_i\)，\(b_i,s_i\ge0\)，换手 \(\sum_i|w_i-w_i^0|\) 就变成线性的 \(\sum_i(b_i+s_i)\)。当目标中含有正的交易成本时，最优解自动满足 \(b_is_i=0\)（同时买又卖只会白交成本），所以这个拆分是精确的。

网络流（运输、配送）问题有特殊结构，存在极快的专用单纯形算法，本书不展开（参见 Ahuja–Magnanti–Orlin）。全章假设 \(m<n\)；若 \(m\ge n\)，\(Ax=b\) 要么有冗余行、要么不可行、要么只确定一个点，可以先用 QR 或 LU 分解化为行满秩。

13.3 最优性条件与对偶

13.3.1 KKT 条件

由第 12 章的理论，约束优化的一阶必要条件是 KKT 条件。LP 有两个特殊之处：

• 约束线性本身就是一种约束规范（第 12 章引理 12.8），所以不需要 LICQ；
• 问题是凸的，所以 KKT 条件不仅必要而且充分；Lagrange 函数的 Hessian 为零，二阶条件不提供额外信息。

把乘子分成 \(\pi\in\mathbb R^m\)（对应 \(Ax=b\)）和 \(s\in\mathbb R^n\)（对应 \(x\ge0\)），Lagrange 函数为

\(x^*\) 是解的充要条件是存在 \((\pi^*,s^*)\) 使

由于 \(x,s\) 都非负，(13.4e) 等价于 \(x^Ts=0\)。

满足 (13.4) 的三元组有一个漂亮的性质——原始目标等于对偶目标：

充分性的直接证明。任取可行点 \(\bar x\)（\(A\bar x=b,\ \bar x\ge0\)），

不等号来自 \(\bar x\ge0,\ s^*\ge0\)。更进一步，\(\bar x\) 也是最优解当且仅当 \(\bar x^Ts^*=0\)：若 \(s_i^*>0\)，所有最优解都必须有 \(\bar x_i=0\)。

推导拆解：(13.5) 和 (13.6) 用的是同一个三步技巧。第一步，用对偶可行 (13.4a) 把 \(c\) 替换成 \(A^T\pi^*+s^*\)。第二步，展开：\((A^T\pi^*)^Tx=\pi^{*T}(Ax)\)（转置的性质 \((A^T\pi)^Tx=\pi^TAx\)），再用原始可行 \(Ax=b\) 换成 \(\pi^{*T}b\)。第三步，剩下的 \(s^{*T}x\)：对最优点 \(x^*\)，它由互补松弛等于 0，得 (13.5)；对任意可行点 \(\bar x\)，它只能 \(\ge0\)，得 (13.6)。 读法：任何可行方案的成本 = 对偶给出的"资源总价值" \(b^T\pi^*\) + 一个非负的"浪费项" \(\bar x^Ts^*\)。最优方案就是浪费项为零的方案。

13.3.2 对偶问题

与 (13.1) 配对的**对偶问题（dual problem）**是

(13.1) 相应地称为原始问题（primal problem）。把 (13.7) 写成 \(\min -b^T\pi\) s.t. \(c-A^T\pi\ge0\)，以 \(x\) 为乘子，它的 KKT 条件是

令 \(s=c-A^T\pi\)，(13.8) 与 (13.4) 完全相同。于是得到一个对称的结论：**原始问题的最优乘子就是对偶问题的最优变量，对偶问题的最优乘子就是原始问题的最优变量。**对偶的对偶回到原始问题（把 (13.7) 化成标准形再求对偶即可验证）。

金融直觉：对偶问题可以读成"另一个人给资源定价"。原问题：你用 \(n\) 种"活动"（买入的证券、采购的原料）去满足 \(m\) 项要求 \(b\)，活动 \(i\) 单位成本 \(c_i\)，提供的要求量是 \(A\) 的第 \(i\) 列 \(A_i\)，目标是总成本最低。对偶问题：一个竞争者给每项要求标一个单价 \(\pi_j\)，想让 \(b^T\pi\)（你按他的价格付的总额）尽量高；但他的报价必须有竞争力，不能让任何一项活动比他更便宜，否则你会自己去做那项活动。"不比活动 \(i\) 贵"就是 \(A_i^T\pi\le c_i\)，合起来是 \(A^T\pi\le c\)。 强对偶说：竞争者能收到的最高总价，恰好等于你自己做的最低成本。复制定价是同一个结构：用市场上的证券最便宜地复制（或超额复制）一个支付，最低成本等于用状态价格给这个支付估值的最高值。状态价格就是对偶变量。

弱对偶（weak duality）：对任何原始可行 \(x\) 和对偶可行 \((\pi,s)\)，

所以任何对偶可行点的目标值都是原始最优值的下界。\(c^Tx-b^T\pi\) 称为对偶间隙（duality gap），在最优点为零。实务中，求解器正是用对偶间隙来判断"离最优还有多远"。

定理 13.1（线性规划对偶定理）

(i) 若 (13.1) 与 (13.7) 之一有有限最优解，则另一个也有，且两个最优值相等。

(ii) 若其中之一的目标无界，则另一个不可行。

证明思路。(i) 原始有解 ⇒ 由 KKT 定理存在 \((\pi,s)\) 满足 (13.4) ⇒ 由 (13.4) 与 (13.8) 等价，\(\pi\) 是对偶最优解，再由 \(x^Ts=0\) 与 (13.10) 得 \(c^Tx=b^T\pi\)。(ii) 若原始无下界，存在方向 \(d\) 满足 \(c^Td<0,\ Ad=0,\ d\ge0\)。如果对偶可行，即 \(A^T\pi\le c\)，左乘 \(d^T\ge0\) 得 \(0=d^TA^T\pi\le d^Tc<0\)，矛盾。∎

13.3.3 影子价格与敏感性分析

求出最优 \(x\) 对应的 \((\pi,s)\) 的过程常称敏感性分析（sensitivity analysis）。设右端 \(b\) 有小扰动 \(\Delta b\)。若问题非退化（13.4 节定义），扰动后 \(x,s\) 的零元位置不变，互补性给出 \(x^T\Delta s=\Delta x^Ts=\Delta x^T\Delta s=0\)。由对偶定理 \(c^T(x+\Delta x)=(b+\Delta b)^T(\pi+\Delta\pi)\)，再利用 \(c^Tx=b^T\pi\)、\(A\Delta x=\Delta b\)、\(A^T\Delta\pi=-\Delta s\)，可推出 \(c^T\Delta x=\Delta b^T\pi\)。取 \(\Delta b=\epsilon e_j\)：

即右端 \(b_j\) 每增加一个单位，最优目标变化 \(\pi_j\)。\(\pi_j\) 称为约束 \(j\) 的影子价格（shadow price）。

推导拆解：上面的推导可以更直接地写成一行。\(c^T\Delta x=(A^T\pi+s)^T\Delta x=\pi^T(A\Delta x)+s^T\Delta x=\pi^T\Delta b+s^T\Delta x\)。第一步用对偶可行 \(c=A^T\pi+s\)；第二步用扰动后仍可行 \(A(x+\Delta x)=b+\Delta b\)，即 \(A\Delta x=\Delta b\)。最后一项为零，是因为非退化时零元位置不变：\(s_i>0\) 的分量对应 \(x_i=0\)，扰动后 \(x_i\) 仍为 0，所以 \(\Delta x_i=0\)；而 \(s_i=0\) 的分量乘什么都是 0。

金融直觉：用一个管理会计的例子把影子价格算出来。工厂生产 A、B 两种产品，单位边际贡献 30 元和 40 元。A 每件耗 1 机器工时、1 千克原料；B 每件耗 1 工时、2 千克原料。本月有 80 工时、100 千克原料。问题是 \(\max30a+40b\) s.t. \(a+b\le80\)，\(a+2b\le100\)，\(a,b\ge0\)。 两个约束都用满时 \(a=60\)、\(b=20\)，边际贡献 2600 元，可以验证这是最优的角点（另外两个角 \((80,0)\)、\((0,50)\) 只有 2400 和 2000）。 影子价格 \(y_1\)（每工时）、\(y_2\)（每千克）由"在产产品的边际贡献 = 它消耗资源的影子价值"决定：A 给出 \(y_1+y_2=30\)，B 给出 \(y_1+2y_2=40\)，解得 \(y_1=20\)、\(y_2=10\)。验证对偶目标 \(80\times20+100\times10=2600\)，与原问题相等，正是强对偶。 再验证含义：工时增加到 81，重新解得 \(a=62\)、\(b=19\)，贡献 2620，恰好多 20 元。所以如果外租 1 小时机器的价格低于 20 元，就该租；原料市价若低于 10 元/千克，就该多采购。CPA 教材里"单位约束资源边际贡献"排序法只适用于单一瓶颈；两种资源同时紧张时，正确的机会成本就是这两个对偶变量。 这个例子是极大化问题；化成本章的 \(\min\) 标准形后，linprog 报告的 marginals 会是 \(-20\) 和 \(-10\)，符号相反、含义一致，见下文的符号提醒。

两点提醒。第一，这个线性关系只在局部成立：扰动大到让最优基改变时，\(\pi\) 会跳变，所以最优值关于 \(b\) 是分段线性的凸函数。第二，影子价格有符号约定：scipy 的 linprog 返回的 marginals 就是"最优目标对约束右端的导数"，对 \(A_{ub}x\le b_{ub}\) 形式的约束它是非正的。

量化提示：组合优化中的每一条约束（行业中性、因子暴露上限、个股流动性上限、收益目标）都有影子价格。它回答"这条约束让我付出了多少代价"。风控和投资经理争论某个限额时，影子价格是最有说服力的数字。

13.4 可行集的几何：基本可行点就是顶点

13.4.1 基本可行点

假设 \(A\) 行满秩（13.12）。实践中，求解器的预处理阶段会去掉冗余约束、消去部分变量，并通过加松弛、剩余、人工变量保证这一性质（习题 13.4 说明行秩亏时不存在基本可行点）。

定义（基本可行点，basic feasible point）：可行点 \(x\) 称为基本可行点，如果存在指标集 \(\mathcal B(x)\subset\{1,\dots,n\}\) 满足

• \(\mathcal B(x)\) 恰含 \(m\) 个指标；
• \(i\notin\mathcal B(x)\Rightarrow x_i=0\)；
• \(m\times m\) 矩阵 \(B=[A_i]_{i\in\mathcal B(x)}\) 非奇异（\(A_i\) 是 \(A\) 的第 \(i\) 列）。（13.13）

\(\mathcal B\) 称为基（basis），\(B\) 称为基矩阵。标准教材术语叫"基本可行解（basic feasible solution）"，原书为了与"解 = 问题的最优解"的用法一致而改称"基本可行点"。

白话解释：\(m\) 个方程、\(n\) 个未知数（\(n>m\)），方程组有无穷多解。基本可行点的做法是：挑 \(m\) 个变量当"基变量"，其余 \(n-m\) 个直接设为 0，剩下的 \(m\times m\) 方程组 \(Bx_B=b\) 有唯一解；若解出来全都 \(\ge0\)，就得到一个基本可行点。 用上面的工厂例子：加松弛变量后有 4 个变量 \((a,b,y_1,y_2)\)、2 个等式 \(a+b+y_1=80\)，\(a+2b+y_2=100\)。选基 \(\{a,b\}\)，令 \(y_1=y_2=0\)，解得 \((60,20)\)，就是两个资源都用满的那个角；选基 \(\{y_1,y_2\}\)，令 \(a=b=0\)，得 \(y=(80,100)\)，即"什么都不生产"的原点角。\(\binom42=6\) 种选法中，有的解出负数（不可行），剩下的正好对应可行多边形的 4 个顶点。

定理 13.2（线性规划基本定理）

(i) 若 (13.1) 有可行点，则有基本可行点；

(ii) 若 (13.1) 有解，则至少有一个解是基本最优点；

(iii) 若 (13.1) 可行且目标有下界，则有最优解。

证明 (i) 的思路。取所有可行点中非零分量最少的一个，设为 \(x_1,\dots,x_p>0\)，于是 \(\sum_{i\le p}A_ix_i=b\)。若 \(A_1,\dots,A_p\) 线性相关，例如 \(A_p=\sum_{i<p}A_iz_i\)（13.14），令

则 \(Ax(\epsilon)=b\) 对任意 \(\epsilon\) 成立，且 \(|\epsilon|\) 小时前 \(p\) 个分量仍为正。增大 \(\epsilon\) 直到某个分量首次变成零（这必然在 \(\epsilon\le x_p\) 时发生），就得到一个非零分量更少的可行点，矛盾。所以这些列线性无关，\(p\le m\)；若 \(p<m\)，由 \(A\) 行满秩可再补 \(m-p\) 列凑成非奇异的 \(B\)。(ii) 的论证类似：对非零分量最少的最优解，若列相关，则 \(x^*(\epsilon)\) 对正负小 \(\epsilon\) 都可行，最优性迫使 \(c^Tz=0\)，于是同样能构造非零更少的最优解。(iii) 由下一节单纯形法的有限终止性得到。∎

定理 13.3：(13.1) 的基本可行点恰好是可行多面体 \(\{x:Ax=b,\ x\ge0\}\) 的顶点（vertex）。这里"顶点"指不在集合内另外两点连线（内部）上的点。

证明思路。设 \(\mathcal B=\{1,\dots,m\}\)。若 \(x=\alpha y+(1-\alpha)z\)，\(\alpha\in(0,1)\)，\(y,z\) 可行，则 \(y_i=z_i=0\)（\(i>m\)，因为 \(x_i=0\) 且 \(y_i,z_i\ge0\)），又 \(Bx_B=By_B=Bz_B=b\)，\(B\) 非奇异，故 \(x=y=z\)，\(x\) 是顶点。反过来，若某顶点非零分量对应的列线性相关，则用 (13.15) 构造的 \(x(\pm\hat\epsilon)\) 都可行且 \(x\) 是它们的中点，矛盾。∎

代数（基本可行点）与几何（顶点）两种观点完全一致。结合定理 13.2(ii)：只要有解，就一定能在顶点中找到一个。这正是单纯形法只在顶点之间搜索的理论依据。

量化提示：LP 解为什么很稀疏。基本最优点至多有 \(m\) 个非零分量（\(m\) 是等式约束个数）。一个只有预算约束和少数风险约束的 LP 组合模型，其顶点解只会持有很少几只资产。这解释了为什么纯 LP 形式的组合（如最小 CVaR）往往给出集中的持仓；而均值–方差（QP，第 16 章）的解可以在可行域内部或边界的任意位置，持仓更分散。

定义 13.1（退化）：若存在一个基本可行点，其非零分量少于 \(m\) 个，则称该 LP 退化（degenerate）。此时某些基变量取值为零，后面会看到这会导致单纯形法"原地踏步"。

13.5 单纯形法

13.5.1 一步迭代的逻辑

单纯形法的迭代点都是基本可行点（顶点）。多数步从一个顶点沿边移到相邻顶点，基 \(\mathcal B\) 恰好换掉一个指标；多数（并非全部）步使 \(c^Tx\) 下降；问题无界时，某一步会沿一条可以无限延伸且使目标下降的边。

核心问题是：每步换入哪个指标、换出哪个指标。答案来自 KKT 条件。记非基指标集 \(\mathcal N=\{1,\dots,n\}\setminus\mathcal B\)（13.17），\(N=[A_i]_{i\in\mathcal N}\)，相应地把 \(x,s,c\) 分成 \(B\)、\(N\) 两部分。由 \(Bx_B+Nx_N=b\)，取

则原始可行性 (13.4b)(13.4c) 满足（假设 \(x_B\ge0\)）。取 \(s_B=0\) 满足互补性，把 (13.4a) 分块：

计算 \(s_N\) 称为定价（pricing），\(s_N\) 的分量称为非基变量的检验数 / 约简成本（reduced costs）。

金融直觉：检验数 \(s_q=c_q-A_q^T\pi\) 是"活动 \(q\) 的实际成本"减去"它所提供资源按当前影子价格算的价值"。这和 alpha 的逻辑一样：alpha = 实际收益 − 按 beta 和市场价格"应得"的收益。\(s_q<0\) 说明活动 \(q\) 比当前定价体系认为的更便宜，是一个被低估的机会，引入它就能降低总成本；所有 \(s_q\ge0\)，说明在当前影子价格下没有任何被低估的活动，当前方案已经最优。\(\pi=B^{-T}c_B\) 则是由"在用活动恰好不亏不赚"（\(s_B=0\)）倒推出来的资源价格，正如上面工厂例子用 A、B 两个在产产品倒推出工时和原料的影子价格。

KKT 条件中唯一还没保证的是 \(s\ge0\)：

• 若 \(s_N\ge0\)，则 \((x,\pi,s)\) 满足全部 KKT 条件，当前顶点最优，停止；
• 否则选某个 \(s_q<0\) 的 \(q\in\mathcal N\) 作为进基指标（entering index）。

让 \(x_q\) 从零增大、其余非基变量保持零。为保持 \(Ax=b\)，\(x_B\) 随之改变：

\(x_q\) 一直增大到某个基变量 \(x_p\) 降为零为止（\(p\) 称为出基指标，leaving index），或者发现没有任何基变量会降到零（问题无界）。几何上，这是沿可行多面体一条使目标下降的边走到下一个顶点。

白话解释：(13.22) 中的 \(t=B^{-1}A_q\) 是"每引入 1 单位 \(x_q\)，各个基变量要让出多少"。\(t_i>0\) 的基变量会随 \(x_q\) 增加而减少，它最多能撑到 \((x_B)_i/t_i\) 单位；所有这些上限中最小的那个就是 \(x_q\) 能增加的量，这就是 13.5.3 节第 5 步的比值检验。它像木桶的最短板：哪种资源最先耗尽，哪个基变量就退出。若所有 \(t_i\le0\)，增加 \(x_q\) 不消耗任何基变量，可以无限加下去，目标无限下降，问题无界。

13.5.2 目标下降量与有限终止

新的目标值为

由 \(c_B^TB^{-1}=\pi^T\)、\(A_q^T\pi=c_q-s_q\)，得

所以 \(s_q<0\) 且 \(x_q^+>0\) 时目标严格下降。\(s_q\) 就是"\(x_q\) 每增加一单位，目标变化多少"。

推导拆解：(13.23) 是把 \(x^+\) 的两部分代入目标：基变量部分 \(c_B^Tx_B^+=c_B^T(x_B-B^{-1}A_qx_q^+)\)，加上新进来的 \(c_qx_q^+\)。(13.24) 的化简分两步：先用 \(c_B^TB^{-1}=\pi^T\)（这就是 (13.20) 转置），把中间项写成 \(\pi^TA_qx_q^+\)；再用检验数定义 \(s_q=c_q-A_q^T\pi\)，即 \(\pi^TA_q=c_q-s_q\)，代入后 \(c_q\) 两项抵消，只剩 \(-s_qx_q^+\)。

定理 13.4：若 LP (13.1) 非退化且有下界，单纯形法在有限步内终止于基本最优点。

证明。非退化保证每步 \(x_q^+>0\)，目标严格下降，所以不会重访同一个基本可行点；每个 \(m\) 元指标子集至多对应一个基本可行点，基的总数不超过 \(\binom nm\)，所以迭代有限；而在非最优的基本可行点总能离开，故终止点最优。∎

13.5.3 Procedure 13.1：单纯形法一步

给定 \(\mathcal B,\mathcal N\)，\(x_B=B^{-1}b\ge0\)，\(x_N=0\)：

1. 解 \(B^T\pi=c_B\)；计算 \(s_N=c_N-N^T\pi\)（定价）；
2. 若 \(s_N\ge0\)，停止（已最优）；
3. 选 \(q\in\mathcal N\) 使 \(s_q<0\)（进基）；
4. 解 \(Bt=A_q\)；若 \(t\le0\)，停止（问题无界）；
5. 比值检验（ratio test）：\(x_q^+=\min_{i:\,t_i>0}(x_B)_i/t_i\)，取达到最小的基变量为出基指标 \(p\)；
6. 更新 \(x_B^+=x_B-t\,x_q^+\)，\(x_q=x_q^+\)；\(\mathcal B\) 中加入 \(q\)、移出 \(p\)。

还有三件事要解决：线性代数（如何高效求 \(\pi\) 和 \(t\)）、从多个负检验数中如何选进基指标、如何处理 \(x_q^+=0\) 的退化步。它们决定了实现的效率和可靠性。

13.6 实现要点

13.6.1 单纯形法中的线性代数

每步要解两个线性系统：

从不显式计算 \(B^{-1}\)，而是维护 \(B\) 的 LU 分解 \(LU=B\)（13.26，置换已并入 \(B\)）。解 \(Bt=A_q\) 只需两次三角回代：\(L\bar t=A_q\)，\(Ut=\bar t\)（13.27）；解 \(B^T\pi=c_B\) 类似：\(U^T\bar\pi=c_B\)，\(L^T\pi=\bar\pi\)。对大型稀疏 \(B\)，初次分解时要重排行列，兼顾数值稳定和 \(L,U\) 的稀疏性——Markowitz（1957）提出的选主元策略至今仍是许多稀疏 LU 的基础。（就是那位提出均值–方差组合理论的 Harry Markowitz。）

由于每步 \(B\) 只换一列，更新分解比重新分解便宜得多。思路是：出基列被进基列 \(A_q\) 替换后，\(L^{-1}B^+\) 除被替换的那一列（变为 \(L^{-1}A_q\)）外仍是上三角。把这一列循环移到最后、其后各列左移一位，对行做同样的置换 \(P_1\)，非上三角部分就集中到最后一行；再用一次稀疏 Gauss 消元消去它：

\(L_1\) 只有最后一行不同于单位阵。于是 \(B^+=L^+U^+\)，\(L^+=LP_1^TL_1\)，\(U^+=U_1P_1\)（13.31），这些乘积不需要显式算出，只需紧凑存储 \(L_1\) 的非零元、\(U_1\) 的最后一列与置换信息。这就是 Forrest–Tomlin 更新：存储少、数据移动少，缺点是 \(L_1\) 中的乘子可能很大而导致数值不稳定。Bartels–Golub 更新允许行交换使乘子不超过 1，稳定但可能产生填充；Saunders 的改进在初次分解时让 \(U\) 的左上块尽量是对角阵，兼顾效率与稳定。更新多次后存储和误差都会累积，所以实现中会定期重新分解（refactorization）。

13.6.2 定价规则：选哪个进基变量

通常有多个 \(s_q<0\)。理想的选择是让总迭代数最少，但这需要全局信息；实践中只能用短视但实用的规则，并在"选得好"与"选的代价"之间权衡。

• Dantzig 规则：计算全部 \(s_N\)，选最负的。由 (13.24)，它使"每单位 \(x_q\) 增量"的目标下降最大；但不保证整步下降大——可能 \(x_q\) 只能增加一点就碰到下一个顶点。
• 部分定价（partial pricing）：每次只计算 \(s_N\) 的一部分分量，从中选最负者，并轮换计算的部分。
• 多重定价（multiple pricing）：对最负的一小批（典型 10 个）候选，额外计算 \(t\) 和 \(x_q^+\)，选使 \(s_qx_q^+\) 最小者；随后若干步只在这批候选中迭代，相当于求解一个约简 LP。
• 最陡边（steepest edge）：选"沿边每走单位距离目标下降最多"的方向。主元步的总变化是 \(x^+=x+\eta_qx_q^+\)，其中

选使 \(c^T\eta_q/\|\eta_q\|=s_q/\|\eta_q\|\) 最小的 \(q\)。\(\gamma_i=\|\eta_i\|^2\) 可以用 Goldfarb–Reid 递推（基于 Sherman–Morrison 公式，见附录 A）高效更新：解两个额外系统 \(B^T\hat t=t\)、\(B^Tr=e_1\) 后，

最陡边比 Dantzig 规则每步多解一个系统，但实践中非常有效；Goldfarb–Forrest 的测试显示，在一些超大规模问题上它甚至优于内点法。

13.6.3 两阶段法：找初始基

单纯形法需要一个初始基本可行点，而找它本身和解 LP 一样难。**两阶段法（Phase I / Phase II）**的做法是：

Phase I：引入人工变量 \(z\in\mathbb R^m\)，

\(E\) 为对角阵，\(E_{jj}=1\)（\(b_j\ge0\)）或 \(-1\)（\(b_j<0\)）。初始点 \(x=0\)、\(z_j=|b_j|\) 是基本可行点，基矩阵就是 \(E\)。\(e^Tz\) 是对 \(Ax=b\) 的违反量之和，所以 (13.39) 的最优值为零当且仅当 (13.1) 可行。若 Phase I 结束时 \(e^Tz>0\)，原问题不可行。

Phase II：从 Phase I 的最优基出发，求解原目标。若最终基中还残留取值为零的人工变量，可以保留它们（并加上 \(0\le z\le0\) 的界），或在后处理中利用 \(A\) 行满秩补入原变量。

许多问题不需要全部 \(m\) 个人工变量：已经加入的松弛变量可以直接充当人工变量。

例 13.1：

加松弛 \(x_4,x_5\)：\(2x_1+x_2+x_3+x_4=2\)，\(x_1-x_2-x_3+x_5=-1\)。点 \(x=(0,0,0,2,0)\) 满足第一个约束但不满足第二个，所以只需为第二个约束加一个人工变量 \(z_2\)：

\((x,z_2)=((0,0,0,2,0),1)\) 是基本可行点，初始基矩阵 \(B=\begin{bmatrix}1&0\\0&-1\end{bmatrix}\)；\(x_4\) 充当第一个约束的人工变量。13.8 节的代码会把这个例子完整算完。

13.6.4 退化与循环

若某个基变量 \((x_B)_i=0\) 而 \(t_i>0\)，比值检验给出 \(x_q^+=0\)：一步也不能移动，称为退化步（degenerate step）。虽然 \(x\) 和目标都不变，但基变了，可能为后续下降铺路。危险在于：连续的退化步可能让基在若干步后回到原来的样子，无限循环下去，称为循环（cycling）。过去认为这很罕见，但在整数规划的 LP 松弛中越来越常见，所以实用代码必须有防循环机制。

白话解释：退化在几何上是"一个顶点被多于 \(m\) 条约束同时卡住"，好比三条以上的直线交于平面上同一点。此时同一个顶点对应多个不同的基，单纯形法可能在这些基之间换来换去，点不动、目标也不动。下面两种策略的共同思想是：把约束右端轻轻错开一点点，让重合的交点分开，平局就不复存在。实务中求解器已内置这类机制，读者知道"退化会拖慢甚至卡住单纯形法"即可。

扰动策略：把 \(b\) 扰动为 \(b(\epsilon)=b+E(\epsilon,\epsilon^2,\dots,\epsilon^m)^T\)（\(E\) 非奇异，\(\epsilon>0\) 很小）。可以证明比值检验此时不会出现平局：若两行比值对所有 \(\epsilon\) 都相等，则 \(B^{-1}E\) 的两行成比例，与非奇异矛盾。于是出基指标唯一、每步都走非零步长，从而避免循环。

字典序策略（lexicographic strategy）：不真的选 \(\epsilon\)，而是"假装扰动了"来打破平局：对比值并列的候选，按扰动项 \((B^{-1}E)_{i1},(B^{-1}E)_{i2},\dots\) 除以 \(t_i\) 的大小逐阶比较，选扰动后比值最小者出基。

13.7 单纯形法的定位与复杂度

含不等式约束的优化问题，其根本任务是判断哪些不等式在解处是活跃的。单纯形法属于有效集方法（active-set methods）：它显式维护"可能活跃"与"可能不活跃"两个指标集（LP 中 \(\mathcal N\) 是 \(x_i\ge0\) 可能活跃的指标，\(\mathcal B\) 是可能不活跃的指标），每步在两集合间交换一个指标。第 16 章二次规划的有效集方法、界约束优化、非线性规划的有效集算法都沿用这一策略。非线性情形下，单纯形法的某些便利不再成立：解处不一定有至少 \(n-m\) 个界活跃，专用线性代数不再适用，约简问题也未必能精确求解。但单纯形法是所有有效集方法的鼻祖。

复杂度。单纯形法在几乎所有实际问题上都很快，一般至多 \(2m\) 到 \(3m\) 次迭代。但 Klee 和 Minty 构造了一族 \(n\) 维问题，其可行多面体有 \(2^n\) 个顶点，单纯形法要访问每一个才到达最优——最坏情况下复杂度是指数的。这推动了对多项式算法的寻找：70 年代末 Khachiyan 的椭球法是多项式的，但实践中太慢；80 年代中 Karmarkar 提出从可行多面体内部逼近解的多项式算法，开启了内点法的研究热潮，这是下一章的内容。

13.8 量化实战

13.8.1 在哪里用

• 读懂求解器。实际工作中直接调用 HiGHS、Gurobi、CPLEX 或 scipy.optimize.linprog(method="highs")。本章帮助你理解输出：status 中的"不可行""无界"对应定理 13.1(ii) 和 Phase I 的结论；marginals 是对偶变量，即影子价格；highs-ds 是对偶单纯形，highs-ipm 是内点法。
• CVaR 组合。给定 \(S\) 个收益情景 \(r_s\in\mathbb R^n\)，置信水平 \(\beta\)，Rockafellar–Uryasev 证明 CVaR 最小化等价于

其中最优 \(\alpha\) 就是 VaR。这是一个 LP，变量个数 \(n+1+S\)。

推导拆解：这个 LP 是怎么来的。情景 \(s\) 下组合损失是 \(L_s=-r_s^Tw\)。CVaR 是"最差 \((1-\beta)\) 比例情景的平均损失"。Rockafellar–Uryasev 的公式是 \(\text{CVaR}=\min_\alpha\ \alpha+\frac1{(1-\beta)S}\sum_s[L_s-\alpha]^+\)，其中 \([z]^+=\max(z,0)\)。直观上，\(\alpha\) 是一条门槛线，\([L_s-\alpha]^+\) 只计入超过门槛的那部分损失；把门槛放在 VaR 处时，这个式子正好等于"VaR + 尾部平均超额损失"，即尾部平均损失。 \(\max\) 不是线性函数，处理办法是第 12 章 12.1.2 节的辅助变量技巧：引入 \(u_s\)，要求 \(u_s\ge L_s-\alpha\) 且 \(u_s\ge0\)。因为目标要把 \(\sum u_s\) 压低，最优时 \(u_s\) 会自动贴到两个下界中较大的那个，即 \(u_s=[L_s-\alpha]^+\)。这样非线性的 \(\max\) 就变成了线性约束。 对比方差：方差要用协方差矩阵、是二次函数，CVaR 只需要情景收益、可以写成 LP。这也是 CVaR 能直接处理厚尾、非对称历史情景的原因。

• 影子价格。收益目标约束的对偶值告诉你"每多要求一单位收益，CVaR 增加多少"，即有效前沿的斜率。

13.8.2 代码一：自己实现单纯形法，算完例 13.1

import numpy as np
from scipy.optimize import linprog

def simplex_phase2(A, b, c, basis, max_iter=100, verbose=True):
    """修订单纯形法（Procedure 13.1），标准形 min c^T x, Ax=b, x>=0。
    basis: 初始可行基的列下标列表（B 非奇异且 B^{-1}b >= 0）。"""
    m, n = A.shape
    basis = list(basis)
    for it in range(max_iter):
        B = A[:, basis]
        xB = np.linalg.solve(B, b)
        pi = np.linalg.solve(B.T, c[basis])            # 1. B^T pi = c_B
        nonbasis = [j for j in range(n) if j not in basis]
        sN = c[nonbasis] - A[:, nonbasis].T @ pi       #    定价：检验数
        if verbose:
            print(f"iter {it}: basis={basis}, obj={c[basis]@xB:.4f}, sN={np.round(sN,3)}")
        if np.all(sN >= -1e-12):                        # 2. 最优
            x = np.zeros(n); x[basis] = xB
            return x, pi, basis
        q = nonbasis[int(np.argmin(sN))]                # 3. Dantzig 规则
        t = np.linalg.solve(B, A[:, q])                 # 4. B t = A_q
        if np.all(t <= 1e-12):
            raise ValueError("unbounded")
        ratios = np.where(t > 1e-12, xB / np.where(t > 1e-12, t, 1), np.inf)
        p = int(np.argmin(ratios))                      # 5. 比值检验
        basis[p] = q                                    # 6. 换基
    raise RuntimeError("max_iter")

# 例 13.1：min 3x1+x2+x3, 2x1+x2+x3<=2, x1-x2-x3<=-1, x>=0
# 加松弛 x4,x5 → 等式；第二行两边乘 -1 使右端非负：-x1+x2+x3-x5 = 1
A = np.array([[2., 1, 1, 1, 0],
              [-1., 1, 1, 0, -1]])
b = np.array([2., 1])
c = np.array([3., 1, 1, 0, 0])
# Phase I：只需为第二行加一个人工变量 z（列 5）
A1 = np.hstack([A, [[0.], [1.]]]); c1 = np.r_[np.zeros(5), 1.]
print("== Phase I ==")
x1, _, basis = simplex_phase2(A1, b, c1, basis=[3, 5])
print("Phase I 结束: x =", np.round(x1, 4))
print("== Phase II ==")
x, pi, basis = simplex_phase2(A, b, c, basis=basis)
print("最优 x =", np.round(x, 4), " 目标 =", c @ x, " 对偶 pi =", np.round(pi, 4))

res = linprog(c=[3, 1, 1], A_ub=[[2, 1, 1], [1, -1, -1]], b_ub=[2, -1],
              bounds=[(0, None)] * 3, method="highs")
print("HiGHS: x =", res.x, " obj =", res.fun, " 不等式对偶 =", res.ineqlin.marginals)

输出：

== Phase I ==
iter 0: basis=[3, 5], obj=1.0000, sN=[ 1. -1. -1.  1.]
iter 1: basis=[3, 1], obj=0.0000, sN=[0. 0. 0. 1.]
Phase I 结束: x = [0. 1. 0. 1. 0. 0.]
== Phase II ==
iter 0: basis=[3, 1], obj=1.0000, sN=[4. 0. 1.]
最优 x = [0. 1. 0. 1. 0.]  目标 = 1.0  对偶 pi = [0. 1.]
HiGHS: x = [0. 1. 0.]  obj = 1.0  不等式对偶 = [-0. -1.]

解读：

• Phase I 一步就把人工变量赶出了基（\(x_2\) 进基），违反量变为零，原问题可行。
• Phase II 起点就已最优：检验数 \(s_N=(4,0,1)\) 全非负。其中 \(x_3\) 的检验数为 0，说明 \(x_3\) 进基不会改变目标——最优解不唯一（\(x_2\) 与 \(x_3\) 可以互换），这正是 13.2 节说的"解可能是一整条边"。
• 对偶 \(\pi=(0,1)\)：第一个约束不紧（\(x_4=1>0\)），影子价格为 0，符合互补松弛。代码里把第二行乘了 \(-1\)，所以 HiGHS 报告的对偶值是 \(-1\)：把原约束右端从 \(-1\) 放宽到 \(-0.9\)，最优目标会下降 \(0.1\)。符号约定不同，含义一致。

13.8.3 代码二：最小 CVaR 组合与影子价格

import numpy as np
from scipy.optimize import linprog

rng = np.random.default_rng(7)
n, S, beta = 30, 1000, 0.95
# 模拟日收益情景：单因子 + 厚尾特质项
mkt = 0.0003 + 0.012 * rng.standard_t(4, S) / np.sqrt(2)
betas = rng.uniform(0.5, 1.5, n)
R = np.outer(mkt, betas) + 0.015 * rng.standard_t(4, (S, n)) / np.sqrt(2) \
    + rng.uniform(0.0, 0.0008, n)
mu = R.mean(0)

def min_cvar(target):
    # 变量顺序: w (n), alpha (1), u (S)
    c = np.r_[np.zeros(n), 1.0, np.full(S, 1 / ((1 - beta) * S))]
    # u_s >= -R_s w - alpha  <=>  -R_s w - alpha - u_s <= 0
    A_ub = np.hstack([-R, -np.ones((S, 1)), -np.eye(S)])
    b_ub = np.zeros(S)
    # 收益目标 mu^T w >= target  <=>  -mu^T w <= -target
    A_ub = np.vstack([A_ub, np.r_[-mu, 0, np.zeros(S)]])
    b_ub = np.r_[b_ub, -target]
    A_eq = np.r_[np.ones(n), 0, np.zeros(S)][None, :]
    bounds = [(0, None)] * n + [(None, None)] + [(0, None)] * S
    return linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=[1.0],
                   bounds=bounds, method="highs")

for q in [0.5, 0.8, 0.9, 0.95]:
    tgt = np.quantile(mu, q)
    r = min_cvar(tgt)
    w = r.x[:n]
    print(f"q={q:.2f} 目标收益 {tgt*1e4:5.2f}bp | CVaR95 = {r.fun*100:.3f}% | "
          f"非零权重数 = {(w > 1e-6).sum():2d} | "
          f"收益约束影子价格 = {-r.ineqlin.marginals[-1]:.3f} | "
          f"预算约束对偶 = {r.eqlin.marginals[0]*100:.3f}%")

# 有限差分验证影子价格：目标收益提高 0.1bp，CVaR 增加多少
t0 = np.quantile(mu, 0.9); d = 1e-5
r0, r1 = min_cvar(t0), min_cvar(t0 + d)
print(f"有限差分 dCVaR/dtarget = {(r1.fun - r0.fun)/d:.3f}")

输出：

q=0.50 目标收益  0.10bp | CVaR95 = 2.050% | 非零权重数 = 12 | 收益约束影子价格 = 0.000 | 预算约束对偶 = 2.050%
q=0.80 目标收益  5.42bp | CVaR95 = 2.052% | 非零权重数 =  9 | 收益约束影子价格 = 0.862 | 预算约束对偶 = 2.006%
q=0.90 目标收益  7.16bp | CVaR95 = 2.090% | 非零权重数 =  9 | 收益约束影子价格 = 3.733 | 预算约束对偶 = 1.823%
q=0.95 目标收益  8.22bp | CVaR95 = 2.196% | 非零权重数 =  8 | 收益约束影子价格 = 17.917 | 预算约束对偶 = 0.724%
有限差分 dCVaR/dtarget = 3.772

解读：

1. 互补松弛：目标收益很低时收益约束不紧，影子价格恰为 0；约束变紧后影子价格为正，并随目标升高而急剧增大（0.86 → 3.73 → 17.9）。这就是 CVaR 有效前沿越来越陡的斜率。
2. 影子价格 = 前沿斜率：\(q=0.9\) 时对偶值 3.733，有限差分得 3.772，两者在局部一致；小的差别来自基在扰动下改变（13.3.3 节说的分段线性）。
3. 稀疏性：30 只资产中只持有 8–12 只。这是顶点解的典型特征（13.4 节）。如果你希望持仓分散，就需要额外的上限约束或改用二次目标。
4. 预算约束的对偶：在收益约束不紧时，它恰好等于 CVaR 本身。原因是 CVaR 关于权重是一次齐次的：把整个组合放大 \(1+\epsilon\) 倍，CVaR 也放大 \(1+\epsilon\) 倍。

本章小结

线性规划可以统一写成标准形 \(\min c^Tx,\ Ax=b,\ x\ge0\)。它的 KKT 条件由原始可行、对偶可行、互补松弛三部分组成，对 LP 既必要又充分。对偶问题 \(\max b^T\pi,\ A^T\pi\le c\) 与原始问题互为乘子；弱对偶给出下界，强对偶保证最优值相等，对偶变量就是约束的影子价格。几何上，基本可行点就是可行多面体的顶点，只要有解就有顶点解，所以单纯形法沿边在顶点间移动：定价求检验数、选负检验数进基、比值检验选出基，每步目标下降 \(-s_qx_q^+\)，非退化时有限终止。工业级实现依赖 LU 分解的更新、聪明的定价规则（最陡边）、两阶段法和防循环策略。单纯形法是有效集方法的原型，实践中很快，但最坏情况是指数复杂度，这引出了下一章的内点法。

练习

基础

1. 把问题 \(\max c^Tx+d^Ty\) s.t. \(A_1x=b_1\)，\(A_2x+B_2y\le b_2\)，\(l\le y\le u\)（\(x\) 无符号限制）化为标准形。 提示：\(x=x^+-x^-\)；\(y=l+y'\)，\(y'\ge0\)，\(y'+w=u-l\)；第二组约束加松弛。
2. 证明 \(\min c^Tx\) s.t. \(Ax\ge b,\ x\ge0\) 的对偶是 \(\max b^T\pi\) s.t. \(A^T\pi\le c,\ \pi\ge0\)。 提示：加剩余变量化成标准形后套用 (13.7)；或直接写 Lagrange 函数。
3. 对例 13.1，验证最优解不唯一：写出另一个基本最优点，并说明为什么检验数 \(s_3=0\) 预示了这一点。 提示：\(x=(0,0,1)\) 也满足约束且目标为 1。
4. 证明若 \(A\) 的行线性相关，则任何 \(m\) 列构成的 \(B\) 都奇异，因而不存在基本可行点。
5. 用 13.8.2 的代码求解 \(\min -x_1-x_2\) s.t. \(x_1-x_2\le1\)，\(-x_1+x_2\le1\)，\(x\ge0\)，观察程序如何报告无界，并说明此时对偶问题为什么不可行。

进阶

6. 解释为什么 LP 最优值作为右端 \(b\) 的函数是分段线性的凸函数。在 13.8.3 的 CVaR 例子中，把收益目标在 \([q_{0.8},q_{0.95}]\) 之间取 50 个值，画出 CVaR–目标收益曲线和影子价格曲线，验证影子价格是曲线的（右）导数，并找出基发生变化的位置。
7. 验证 Goldfarb–Reid 公式 (13.36)/(13.38)：利用 Sherman–Morrison 公式写出 \((B^+)^{-1}\)，再计算 \(\gamma_i^+=\|(B^+)^{-1}A_i\|^2+1\)。
8. 在 13.8.2 的实现里加入 Bland 规则（进基选下标最小的负检验数、出基在平局时选下标最小者），并在一个经典的循环例子（如 Beale 例子）上比较 Dantzig 规则与 Bland 规则。
9. 把 CVaR 模型加上换手约束 \(\sum_i|w_i-w_i^0|\le\tau\)（用 \(b_i,s_i\) 拆分），求不同 \(\tau\) 下的最小 CVaR 及换手约束的影子价格。 提示：新增 \(2n\) 个变量、\(n\) 个等式 \(w-b+s=w^0\) 和一个不等式。
10. 证明资产定价中的"无套利 ⇔ 存在正的状态价格"：设 \(D\) 为 \(S\times n\) 的资产到期支付矩阵、\(p\) 为价格向量，考虑 LP \(\min p^T\theta\) s.t. \(D\theta\ge0\)，用对偶定理推出结论。

原书推荐习题：13.2、13.3（标准形与对偶推导）、13.4（行满秩假设的作用）、13.5（最陡边递推）、13.1（预处理中冗余约束的检测）。原书第 13 章共 13.1–13.7 题。

原书对照

说明：原书 13.4 节描述 LU 更新时 \(p\)、\(q\) 的角色写反，本章按"出基列被进基列替换"叙述。原书正文页码 = PDF 页码减 19（已用 PDF 页眉核对，第 12–16 章均如此）。