4、线性规划基础：线性规划的标准形式、单纯形法原理、在组合构建中的简单应用
线性规划（Linear Programming, LP）是运筹学中发展最成熟、应用最广泛的优化工具之一。在组合构建场景中，无论是资产配置、行业轮动还是风险平价，其核心往往是在一组线性约束下寻找某个线性目标函数的最优值。本章从线性规划的标准形式出发，剖析单纯形法的几何与代数原理，并展示其在投资组合构建中的典型应用路径。
4.1 线性规划的标准形式与转换规则
线性规划的标准形式是算法实现与理论分析的统一语言。任何线性规划问题都可以通过代数变换转化为标准形式，从而直接调用成熟的求解器（如CPLEX、Gurobi、SciPy linprog）。标准形式定义如下：
minimize c₁x₁ + c₂x₂ + ... + cₙxₙ
subject to a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ = b₁
a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ = b₂
...
aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ = bₘ
x₁, x₂, ..., xₙ ≥ 0其中 c 为目标系数向量，A 为 m×n 约束矩阵，b 为右端项向量，且要求 b ≥ 0。标准形式的核心特征包括：目标函数为最小化、所有约束为等式、所有变量非负。
4.1.1 非标准形式的转换方法
| 原始形式 | 转换操作 | 标准形式结果 |
|---|---|---|
| 最大化目标 max cᵀx | 目标函数乘以 -1 | min -cᵀx |
| 不等式约束 aᵢᵀx ≤ bᵢ | 引入松弛变量 sᵢ ≥ 0 | aᵢᵀx + sᵢ = bᵢ |
| 不等式约束 aᵢᵀx ≥ bᵢ | 引入剩余变量 sᵢ ≥ 0 | aᵢᵀx - sᵢ = bᵢ |
| 变量 xⱼ 无符号限制 | 令 xⱼ = xⱼ⁺ - xⱼ⁻ | xⱼ⁺ ≥ 0, xⱼ⁻ ≥ 0 |
| 右端项 bᵢ < 0 | 约束两边乘以 -1 | -aᵢᵀx = -bᵢ ≥ 0 |
4.2 单纯形法原理：从几何直觉到代数实现
单纯形法的核心思想是：线性规划的最优解一定出现在可行域的顶点（极点）上。可行域是由约束条件围成的凸多面体，顶点数量有限但可能极大（组合爆炸）。单纯形法从一个初始顶点出发，沿着可行域的边移动到相邻顶点，每一步都使目标函数值改善，直到达到最优。
4.2.1 单纯形法的代数机制
- 初始可行基：从标准形式中选取 m 个线性无关的列向量构成基矩阵 B，对应基变量 x_B = B⁻¹b。若 b ≥ 0，则得到初始基本可行解。
- 检验数计算：对每个非基变量 xⱼ，计算检验数 σⱼ = cⱼ - c_BᵀB⁻¹Aⱼ。若所有 σⱼ ≥ 0，当前解已是最优。
- 入基与出基：选择检验数最小的负值对应的非基变量入基（最大改善原则），再通过最小比值法则确定出基变量，保证可行性。
- 旋转运算：对增广矩阵进行高斯消元，更新基矩阵的逆和所有变量的值，完成一次迭代。
4.2.2 退化与循环问题
当基本可行解中存在基变量取值为 0 时，称为退化。退化可能导致目标函数值在多次迭代中不改善，甚至出现循环（理论上存在，实际极少见）。工程中通常采用 Bland 规则（按最小下标选择入基/出基变量）或摄动法来避免循环。
4.3 线性规划在组合构建中的简单应用
组合构建问题天然适合线性规划建模。以经典的“均值-方差”框架为基础，我们可以将组合优化问题转化为线性规划形式，从而利用成熟的单纯形法求解器高效获得最优权重。
4.3.1 组合构建的线性规划建模
考虑一个包含 n 个资产的组合，设 wᵢ 为资产 i 的权重，rᵢ 为预期收益率。一个典型的线性规划组合构建问题可以表述为：
最大化 Σ rᵢwᵢ
约束条件 Σ wᵢ = 1 （预算约束）
wᵢ ≥ 0 （禁止做空）
Σ βᵢwᵢ ≤ β_max （行业/风格暴露约束）
Σ |wᵢ - wᵢ⁰| ≤ T （换手率限制）其中 wᵢ⁰ 为初始权重，T 为最大换手率。换手率约束中的值项可以通过引入辅助变量转化为线性形式：令 uᵢ ≥ wᵢ - wᵢ⁰，vᵢ ≥ wᵢ⁰ - wᵢ，则 |wᵢ - wᵢ⁰| = uᵢ + vᵢ，且 uᵢ, vᵢ ≥ 0。
4.3.2 案例拆解：行业中性化组合构建
背景与约束：某资产管理公司管理一只行业中性化股票组合，基准为沪深300指数。投资经理需要在保持行业暴露与基准一致的前提下，最大化组合的预期超额收益。组合包含 50 只股票，分属 10 个行业。
关键输入数据：
- 每只股票的预期超额收益 αᵢ（由多因子模型估计）
- 每只股票所属行业 j(i)
- 基准中每个行业的权重 hⱼ
- 单只股票最大权重限制：5%
- 行业偏离限制：|行业权重 - 基准行业权重| ≤ 1%
线性规划模型：
最大化 Σ αᵢwᵢ
约束条件 Σ wᵢ = 1
wᵢ ≥ 0, wᵢ ≤ 0.05
Σ_{i∈行业j} wᵢ - hⱼ ≤ 0.01 （行业超配上限）
hⱼ - Σ_{i∈行业j} wᵢ ≤ 0.01 （行业低配上限）求解过程与结果：使用 Python 的 SciPy 库调用单纯形法求解器（linprog 方法='highs'），将上述模型转化为标准形式后求解。求解结果如下：
| 指标 | 基准组合 | 优化组合 | 变化 |
|---|---|---|---|
| 预期超额收益（年化） | 0% | 3.2% | +3.2% |
| 行业偏离（最大） | 0% | 0.98% | 接近上限 |
| 单票最大权重 | 2.1% | 4.8% | 接近上限 |
| 有效股票数量 | 50 | 38 | 集中度提升 |
分析判断过程：求解器在 12 次迭代后收敛，最优解中 12 只股票权重为 0（被剔除），其余 38 只股票中 5 只触及 5% 的上限。行业约束方面，有 3 个行业触及偏离上限，说明这些行业的股票 α 较高，但受限于中性化要求无法进一步超配。
风险与代价：行业中性化约束显著限制了组合的进攻性。若放宽行业偏离限制至 ±2%，预期超额收益可提升至 4.1%，但行业风险敞口相应增大。此外，单纯形法求解的线性规划假设目标函数和约束均为线性，实际中交易成本、冲击成本等非线性因素需要额外处理。
4.4 灵敏度分析与实际应用要点
单纯形法的一个显著优势是能够提供灵敏度分析信息。在组合构建中，这表现为：
- 影子价格：约束条件的对偶变量值，表示放松该约束一个单位对目标函数的边际改善。例如，行业偏离限制的影子价格为 0.8%，意味着若将偏离上限从 1% 放宽到 1.1%，预期超额收益可增加约 0.008%。
- 目标系数灵敏度：每个资产的 αᵢ 在多大范围内变化时，最优组合不变。这有助于判断 α 估计误差对组合的影响。
- 右端项灵敏度：约束右端值（如预算、权重上限）的变化范围，超出范围后最优基将改变。
4.4.1 组合构建中的工程实践建议
- 矩阵稀疏性：组合构建的约束矩阵通常非常稀疏（每个约束只涉及少量变量），应使用稀疏矩阵存储和求解器。
- 数值稳定性：当资产数量超过 1000 时，约束矩阵的条件数可能很大，建议先对数据进行标准化处理。
- 求解器选择：商业求解器（Gurobi、CPLEX）在数值稳定性和速度上优于开源求解器，但开源方案（HiGHS、GLPK）在中小规模问题上表现足够。
- 模型验证：求解后应检查 KKT 条件（对偶可行性、互补松弛性）以验证解的正确性。