10-3-线性规划
一句话概括
线性规划(linear programming, LP) 是在一组线性不等式约束下最大化或最小化一个线性目标函数的优化问题;它的可行域是一个凸多面体,而最优解必定在某个顶点取得,因此这个看似属于"最优化"的问题,本质上是线性代数的问题——顶点由约束矩阵的一组线性无关行决定,最优性与对偶性都可以用矩阵的秩、可逆子矩阵与内积来表述。
本篇覆盖:
- 线性规划的标准形与其等价变形
- 为什么它是线性代数问题(约束是超平面的交,目标函数是线性的)
- 可行域的几何:多面体、顶点、边(配两变量完整图示文字描述)
- 最优解一定在顶点取得的证明思路(凸性 + 梯度方向)
- 顶点 ↔ 基可行解: 个变量、 个约束时,顶点对应 个线性无关的紧约束
- 单纯形法的核心思想与一次完整迭代的表格
- 对偶问题:弱对偶、强对偶、互补松弛、影子价格
- 与线性代数其他部分的联系:、最优基 、
- 一个完整数值例题(枚举顶点 + 对偶验证)与 numpy / scipy 代码
一、定义
1.1 标准形
定义 10.3.1(线性规划的标准形,standard form)
设 ,,。线性规划的标准形为
其中 称为决策变量(decision variable), 是目标函数系数向量(cost vector), 是约束矩阵(constraint matrix), 是右端向量(right-hand side)。满足全部约束的 称为可行解(feasible solution),全部可行解构成的集合称为可行域(feasible region),记作 。
记号约定
本库统一:矩阵 、向量 、标量 。不等式 是逐分量的,即 ,不要误读为"向量的长度非负"(后者恒成立,是废话)。
1.2 其他常见形式与相互转化
| 形式名称 | 目标 | 主约束 | 变量范围 | 转化方法 |
|---|---|---|---|---|
| 标准形(本篇主用) | —— | |||
| 规范形(canonical) | 目标取负,约束两边乘 | |||
| 等式形(slack form) | 引入松弛变量 | |||
| 一般形 | 或 | 、、 混合 | 变量可正可负 | 逐条改造 |
四个转化法则(务必记牢,否则无法用软件求解):
- 目标反向:;
- 不等式反向:;
- 引入松弛变量(slack variable):。此时
- 自由变量(free variable):若 无符号限制,令 ,其中 。
二、为什么线性规划是线性代数问题
初学者常把 LP 归入"运筹学"。但从 Strang 的视角看,它的三个构件全部是线性的:
(1)每一条约束是一个闭半空间。 第 条约束 可以写成 ,其中 是 的第 行。等式 是 中一张超平面(hyperplane),其法向量正是 ;而不等式取的是这张超平面的一侧。因此 条约束给出 个闭半空间的交,可行域 就是这个交:
这正是本库反复出现的图像:方程组的解是超平面的交,不等式的解是半空间的交。
行图像 vs 列图像
第 2 章说过, 有两种读法。到了 LP,行图像是"半空间的交",列图像同样有用:( 是 的第 列), 意味着" 处于 的各列生成的锥(cone)中"。这一点在第 5 节的对偶与经济解释里会再出现。
(2)目标函数是线性的。 就是 与常向量 的内积。它的等值面 是一族互相平行的超平面,法向量是 ; 在任意点处的梯度恒为
(3)约束矩阵的秩决定一切。 后面会看到:顶点由 (及非负约束)中 个线性无关的紧约束行确定,最优基是一个 的可逆子矩阵 ,顶点坐标由 给出。、线性无关、可逆、基——全部是第 3 章的核心词汇。
用一张表总结这一"翻译":
| 最优化语言 | 线性代数语言 |
|---|---|
| 约束 | 半空间,边界是法向量为 的超平面 |
| 可行域 | 有限个半空间的交 = 凸多面体 |
| 目标 | 与固定向量 的内积;等值面是平行超平面族 |
| 顶点 | 个线性无关紧约束行的交点 = 基可行解 |
| 在顶点处最优 | 落在该顶点处活跃约束法向量生成的锥中 |
| 最优基 | 的 列(含松弛变量)组成的可逆子矩阵 |
| 顶点坐标 | |
| 对偶变量 | ,即 在活跃法向量下的坐标 |
三、几何直观:可行域是一个凸多面体
3.1 多面体、面、顶点、边
定义 10.3.2(凸集,convex set) 集合 称为凸集,若对任意 与任意 ,都有
也就是说, 中任意两点的整条线段仍在 中。
定义 10.3.3(多面体,polyhedron) 有限个闭半空间的交称为多面体。若它还是有界的,称为多胞体(polytope)。
定理 10.3.1(LP 可行域是凸集)
设 。则 是凸集。更一般地,任意多个凸集的交仍是凸集。
证明 设 ,,令 。
对第 条约束:
第一个不等号用了 、 以及 、(这一步要求权重非负,是凸性的关键)。
对非负约束同理:。故 。
定义 10.3.4(顶点,vertex / 极点,extreme point) 设 是凸集。 称为 的顶点,若 不能写成 中两个不同点的真凸组合,即不存在 与 使 。
几何上,顶点就是多面体的"尖角",是零维面;连接两个顶点的线段在多面体边界上的部分称为边(edge),是一维面。 中多面体是凸多边形,顶点就是它的角点; 中是凸多面体,顶点是角顶。
3.2 一个两变量例子的完整图示文字描述
考虑
绘图步骤(在 平面上):
- 画第一条边界线 :。过 与 。这条直线的法向量是 ,直线把平面分成两半,取包含原点的一侧(因为 )。用浅色阴影填充这一侧。
- 画第二条边界线 :。过 与 ,法向量 ,同样取含原点一侧。
- 画第三条边界线 :。过 与 ,法向量 ,取含原点一侧。
- 加非负约束:只保留第一象限。
- 三重阴影的公共区域就是可行域 。它是一块有界的凸五边形,顶点按逆时针依次为
- 画目标函数等值线:,法向量 。取 ,得到一族互相平行的直线,斜率都是 。
- 向外平移这族直线(沿 方向), 不断增大。当直线移到与多面体只有一个公共点(相切于一条边或正好顶住一个角)时停止。在图中, 的直线 恰好与可行域相切于点 ——即 与 的交点。
直观总结
把等值线想象成一把推土机的刀片,沿法向 的方向往外推;刀片离开可行域的最后一个接触点就是最优解。由于多边形是凸的,最后接触的必然是一个角点(或整条边)。
边界走向的补充说明(用于理解"沿边行走"):从 出发沿 轴向右,依次经过 、、、。注意 的坐标: 与 的交点是 ,此时 、,都满足;而从 到 这一段正是 ()的一部分,也就是说从 走到 期间第一条约束始终是紧的(取等号)。这就是下一节的"沿边行走"的原型。
四、最优解一定在顶点取得
定理 10.3.2(LP 基本定理)
设可行域 非空。若 LP 的目标函数在 上有最大值,则至少存在一个顶点取得该最大值。若 有顶点且目标有界,则最优值必在某个顶点处达到。
证明思路("往内部走一定不优")
这是 Strang 的标准论证,核心是凸性 + 梯度。
第一步:紧约束的刻画。 对 ,记活跃约束集(active set)
即所有取等号的约束。若 是 的顶点,则 中涉及的约束行(把 记作 )必然张成整个 ,即秩为 。反之亦然(这将在定理 10.3.3 中精确陈述)。
第二步:内部点不可能是唯一最优。 设 是 的相对内点(即活跃约束行秩小于 )。于是存在非零方向 与 ,使得对所有 都有 。(直觉: 没被"卡死",还能往至少一个方向自由移动。)关键是正反两个方向都能走,即 都是可行方向。
考虑目标函数的变化:
注意这是 的线性函数(不是二次的,也不是指数的),这是目标线性的直接后果。于是:
- 若 ,则取 与 同号,就有 ,即 ——沿着"梯度上升"的那一侧移动可以严格改进, 不是最优。
- 若 ,则两个方向的函数值都不变, 顶多是"平的"最优,可以沿 一直走到 的边界而保持最优值不变。
第三步:走到边界并归纳。 若是后一种情形,沿 一直走到 首次碰到某个新的约束( 存在,因为 有界/目标有界)。此时活跃约束集严格变大,秩增加至少 。重复第二步的论证:若仍未成为顶点,继续走。
第四步:终止。 活跃约束行的秩每次至少增加 ,上界是 ,故至多 步后到达一个活跃约束行秩为 的点,即顶点 ,且 。若 原本是最优解,则 ,故 也是最优解。
这一步为什么依赖凸性
证明中"沿 走一小段仍在 内"以及"一直走到边界"都要求 是凸的:线段整体在集合内,我们才能把方向上的可行区间取成一个区间 ,从而在端点处改进或保持。若可行域是月牙形、环状或其他非凸形状(非线性规划中的常见情形),局部最优点可以藏在内部,这个论证立刻失效。所以"最优解在顶点"不是线性函数单独的性质,而是"线性函数 + 凸可行域"的共同性质。
推论 10.3.1 若 LP 有最优解,则只需在有限个顶点中比较目标值即可。
推论 10.3.2 若 LP 有两个不同的最优顶点,则这两个顶点连线上的每一点都是最优解(由 的线性性:)。
五、性质与定理:顶点、基可行解与对偶
5.1 把不等式化成等式
引入松弛变量 ,原问题变成
记 ,。
定义 10.3.5(基,basis) 从 的 列中选出 个线性无关的列,构成可逆矩阵 ,称 为一个基矩阵(basis matrix)。 对应的变量称为基变量(basic variable),其余 个变量称为非基变量(nonbasic variable)。
定义 10.3.6(基解与基可行解) 令所有非基变量取 ,由 解得 ,得到的 称为基解(basic solution)。若还有 (即所有基变量非负),则称为基可行解(basic feasible solution, BFS)。
定理 10.3.3(基可行解 = 顶点)
是 的顶点 是基可行解。
证明( 方向) 设 是顶点。设其正分量为 ,对应 的列 。
设这些列线性相关,即存在不全为零的系数 使 。构造
(其余分量为 )。则 ,于是对任意 :
又因为 的正分量都 ,取 足够小可使 (这与定理 10.3.2 证明第二步"正反两个方向都能走"是同一件事)。于是 写成两个不同可行点的真凸组合,与"顶点"矛盾。
故 线性无关,从而 (列向量属于 )。再把这 列扩充为 个线性无关的列(第 3 章的基扩充定理,见 3-4-线性无关基与维数),得到基 ;非基变量取 ,则 正是对应的基解,且 ,故为基可行解。
证明( 方向) 设 是基可行解,基为 。非基变量全为 ,故 至少有 个分量为零;而 给出 个等式。
由于 的 列线性无关,且上界为 个变量、 个等式,基可行解处恰有 个基变量与 个取零的非基变量。若 且 ,考虑任意非基下标 ():,而 且 ,故必有 。于是 在非基分量上同为 ,而在基分量上由 的唯一可解性( 可逆!)推出 。故 , 不能写成两个不同点的真凸组合,是顶点。
关键数字
原问题有 个决策变量、 条主约束(不含非负约束)。在 中,一个顶点要由 个线性无关的紧约束确定:其中若干条来自 ,其余来自 (即 )。等价地,在松弛形式中有 个变量、 个等式,一个基解让 个变量取零——这两种说法是同一件事。
顶点的个数至多为 (从 列中选 列),是有限的。这正是"枚举顶点"算法的复杂度来源,也是单纯形法(不枚举全部、只沿边行走)的价值所在。
定义 10.3.7(退化,degeneracy) 若某个基可行解中正分量的个数少于 ,即有多于 个紧约束,则称该基可行解退化(degenerate)。退化时同一个顶点可能对应多个不同的基。
六、计算方法与步骤:单纯形法
6.1 核心思想
单纯形法(simplex method,Dantzig 1947)只做三件事:
- 找一个初始顶点(标准形中,若 ,则 、 就是基可行解,原点即为初始顶点);
- 判断当前顶点是否最优(看目标函数行的检验数,reduced cost,是否全部 );
- 若不然,选一条能让目标上升的边走过去,到达相邻顶点,回到第 2 步。
"相邻顶点"的几何含义:两个顶点相邻 它们共享 个紧约束,即它们由多面体的一条边相连。代数上就是换基:让一个非基变量进基(entering variable),让一个基变量离基(leaving variable),只改动一个下标。
6.2 表格形式的完整一次迭代
以第 3.2 节的问题为例,松弛形式为
初始基为 ,。
初始单纯形表(每行一个基变量,最后一行为目标行 ):
| 基变量 | 右端 RHS | 比值 列 | |||||
|---|---|---|---|---|---|---|---|
| 2 | 1 | 1 | 0 | 0 | 10 | ||
| 1 | 1 | 0 | 1 | 0 | 6 | ||
| 1 | 2 | 0 | 0 | 1 | 10 | ||
| 目标行 | 0 | 0 | 0 | —— |
迭代 1 的三个判断:
- 进基判断(最优性检验):目标行中系数为负的列,取最负者(Dantzig 规则)。这里 ,故 进基。几何含义:沿 轴正方向走能最快提高 。
- 离基判断(最小比值检验,minimum ratio test):在进基列中取正元素,用 RHS 除以它,取比值最小的那一行——这一行最先碰到新的约束,也就是沿边走到头了。比值为 ,最小是 ,故 离基。
- 主元(pivot):位于 列、 行的元素 。用初等行变换把它化为 ,并把该列其余元素化为 (这正是第 2 章的高斯—若尔当消元,见 2-3-用矩阵进行消元)。
第一次消元的结果(,,,目标行 目标行 ):
| 基变量 | RHS | 比值 列 | |||||
|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 5 | ||||
| 0 | 1 | 0 | 1 | ||||
| 0 | 0 | 1 | 5 | ||||
| 目标行 | 0 | 0 | 0 | —— |
此时顶点为 ,。
迭代 2:
- 进基:目标行中只有 的系数 ,故 进基。
- 离基:比值为 ,最小是 ,故 离基。
- 主元 ( 列、 行)。,,,目标行 目标行 。
最终(最优)单纯形表:
| 基变量 | RHS | |||||
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 4 | ||
| 0 | 1 | 2 | 0 | 2 | ||
| 0 | 0 | 1 | 1 | 2 | ||
| 目标行 | 0 | 0 | 1 | 1 | 0 |
目标行全部 ,已最优。读表:,,,,。
从最优表里读出对偶解
目标行中松弛变量的系数就是影子价格(shadow price): 的系数为 , 的系数为 , 的系数为 。含义见第十节「应用」:把 增加 ,最优值增加 ;把 增加 ,最优值不变(因为第三条约束本来就不紧)。请对照 6.2 节最终表的最右列与第九节的例题验算。
6.3 算法步骤总结
单纯形法操作步骤
输入:,,。
第 0 步(初始化):加入松弛变量,得 ,初始基 ,,。
第 1 步(最优性检验):在目标行(等价地:计算检验数 )中找负元素。若全部 ,当前基可行解最优,停止。
第 2 步(进基):选一个检验数为负的非基变量进基。
第 3 步(无界判定):若进基列所有元素都 ,沿这条边目标可以无限增大,问题无界(unbounded),停止。
第 4 步(离基):否则做最小比值检验,取比值最小的行,其基变量离基。
第 5 步(主元消元):对主元做初等行变换,使进基列成为单位列,更新表格,回到第 1 步。
两阶段法:若初始 中有负分量,原点不是可行解,需先引入人工变量并第一阶段极小化人工变量之和(得一个可行基),再做第二阶段(对原目标优化)。
七、对偶问题
7.1 对称形式的对偶
定理 10.3.4(LP 对偶定理,对称形式)
考虑一对问题
称 (P) 为原问题(primal),(D) 为对偶问题(dual)。注意两者的"转置对称性":,,,。并且 (D) 的对偶就是 (P)。
对偶对照表:
| 项目 | 原问题 (P) | 对偶问题 (D) |
|---|---|---|
| 目标 | ||
| 变量个数 | ||
| 约束个数 | ||
| 约束矩阵 | ||
| 约束类型 | ||
| 变量符号 | ||
| 第 个约束 | 对应一个 | 对应一个 |
| 最优值 | (强对偶) |
7.2 弱对偶定理
定理 10.3.5(弱对偶,weak duality)
若 是 (P) 的可行解, 是 (D) 的可行解,则
证明 由 (D) 的约束 ,两边左乘 (逐分量非负,这一步不能省):
左边 。由 (P) 的约束 ,两边左乘 :
串联两式即得 。
推论 10.3.3 (P) 的目标值永远不超过 (D) 的目标值。于是:
- 若 (P) 无界(),则 (D) 无可行解;
- 若 (D) 无界(),则 (P) 无可行解;
- 若 (P) 与 (D) 都可行,则两者都有最优解且最优值相等。
7.3 强对偶定理
定理 10.3.6(强对偶,strong duality)
若 (P) 与 (D) 中至少有一个有最优解,则另一个也有最优解,且
证明思路(由单纯形法给出) 设 (P) 的最优基为 ( 可逆),对应的目标系数子向量为 。在最优点,检验数全部满足
把与松弛变量对应的列( 中 的部分,对应系数 )单独取出,得
取其相反数,定义
验证 是 (D) 的可行解:对非基变量(包括所有松弛变量)有 ,其中 是 的第 列、 是该变量的目标系数。逐列读取这个条件:
- 对 的第 列(决策变量 ,):
- 对 的第 列(松弛变量 ,):
两条合起来恰好是 (D) 的约束 、。故 是 (D) 的可行解。
验证目标值相等:
最后一步用了 与非基变量为零。故 (D) 存在可行解 使目标值等于 (P) 的最优值;再由弱对偶 (D) 不可能更小,故 就是 (D) 的最优解且 。
强对偶的矩阵内容
上面的证明揭示了强对偶的全部线性代数机制:最优基 可逆 → 存在 → 是原问题最优解 → 是对偶最优解 → 两者目标值相差一个 的转置恒等式。对偶性不是额外的技巧,而是 与转置的产物。**
7.4 互补松弛条件
定理 10.3.7(互补松弛,complementary slackness)
设 是 (P) 的可行解, 是 (D) 的可行解。则 同时最优 下列两组成立:
含义(逐条对照):
| 情形 | 结论 | 直观解释 |
|---|---|---|
| 必有 ,即第 条原约束紧 | 有正影子价格的资源一定被用光 | |
| (第 条约束松) | 必有 | 还没用完的资源没有边际价值 |
| 必有 ,即第 条对偶约束紧 | 真正投产的产品,其"影子成本"恰好等于利润 | |
| (第 条对偶约束松) | 必有 | 影子成本高于利润的产品一律不生产 |
证明思路 由弱对偶的证明链
若 ,则两个不等号都取等号。而第一个不等号的差是
这是一个非负项之和(每项 且 )。和为零 每一项都为零,即第二组条件。同理第二个不等号的差给出第一组条件。
7.5 经济解释:影子价格
设原问题描述一个生产计划: 是各产品的产量, 是单位利润, 的第 行是第 种资源在各产品上的单耗, 是资源总量。则 是最大总利润。
对偶变量 的经济含义:若把第 种资源的可用量从 增加到 ,最优值变为 ,即
也就是说, 是第 种资源每增加一个单位所带来的利润增量——资源的影子价格(shadow price)/ 边际价值。经济学家据此判断"该不该花钱买更多这种资源":只要采购单价低于 ,买入就是划算的。
互补松弛在这里读起来非常自然:被用完的资源才有正的影子价格;没用完的资源影子价格为零。
对偶的对称美
原问题是"在资源约束下最大化利润",对偶问题是"给资源定价,使总资源成本最小,同时每种产品的影子成本不低于其利润"。两者最优值相等,意思是:最大利润 = 资源的最小总价值。这正是 Strang 强调的"对偶把行的问题和列的问题连起来"。
7.6 单纯形法的完整手算流程(一张表说清进基、离基与行变换)
单纯形表就是"把松弛形式的系数矩阵与目标行摞在一起"
设标准形为 ,,,。引入松弛变量后 。初始单纯形表是
逐项说明:
- 上面 行是约束(每行的基变量就是对应的松弛变量 ,因为初始基是单位矩阵 );
- 最后一行是目标行,系数取 (这样 行右端的数就是当前 值);
- 初始基可行解:,,。
执行一步迭代(四个动作,缺一不可):
动作 1(最优性检验):看目标行中 部分的系数。
- 若全部 ,当前解已最优,停止;
- 否则选出最负的那个系数对应的变量进基(Dantzig 规则;也可以用 Bland 规则选下标最小的负系数,保证不循环但通常更慢)。
动作 2(无界判定):若进基列在约束部分的所有元素都 ,则沿这条边目标可以无限增大,问题无界,停止。
动作 3(最小比值检验,选离基变量):只在进基列的正元素上做比值
达到最小值的行对应的基变量离基,该行、该列交叉的元素称为主元(pivot)。
动作 4(主元消元):对主元做初等行变换,使进基列变成单位列:
- 主元行 主元行 主元;
- 其余各行(含目标行) 该行 (该行在进基列的元素) 主元行。
这正是高斯—若尔当消元(见 2-3-用矩阵进行消元)——"表格更新"与"解线性方程组"是同一件事。
两个判据的物理含义:
- 进基决定"往哪个方向走"(目标函数上升最快的方向);
- 离基决定"走多远"(第一次碰到新的约束的那个距离)。
"何时该用表格法、何时该用修正单纯形法":
| 情形 | 推荐方法 | 理由 |
|---|---|---|
| 变量与约束都很少(教学、手算) | 表格法 | 每一步都能看清进基/离基,便于理解几何意义 |
| 约束数 远小于变量数 | 修正单纯形法 | 每步只解 与 两个方程组,工作量为 而非 |
| 稀疏大规模问题 | 修正单纯形法 + LU 更新 + 稀疏技术 | 的 LU 分解可以增量更新(见 [[11-1-数值稳定性与LU]]) |
| 需要多项式时间保证 | 内点法 | 单纯形法的最坏情况是指数级的 |
经济含义与几何含义的对照表(把三种语言一次对齐):
| 单纯形法的动作 | 几何含义 | 经济含义 |
|---|---|---|
| 检验数 | 沿这条边的方向,目标还能上升 | 产品 的"影子成本"低于其利润,值得投产 |
| 令 进基 | 沿多面体的一条边出发 | 决定开始生产产品 |
| 最小比值检验 | 走到这条边的另一端(第一次碰到新约束) | 某种资源先用完,产量到此为止 |
| 主元消元 | 换一组紧约束(换基) | 重新核算各资源的影子价格 |
| 目标行全 | 所有边的方向都不再上升(顶点最优) | 所有产品的影子成本都不低于利润,无可改进 |
7.7 对偶问题的构造规则与互补松弛(完整对照)
构造对偶的"三行口诀"
原约束与对偶变量同向,原变量与对偶约束反向。
| 原问题() | 对偶问题() |
|---|---|
| 第 条约束是 | 第 个变量 |
| 第 条约束是 | 第 个变量 自由 |
| 第 个变量 | 第 条对偶约束是 |
| 第 个变量 自由 | 第 条对偶约束是 |
| | |
| 约束矩阵 | 约束矩阵 |
记忆法:把"、、"与"、自由、"看成三档,原约束从松到紧,对偶变量的符号限制从松到紧"反着走"。只要记住" 配 、对偶变量 、对偶约束 "这一组基准,其余都用这条口诀推。
互补松弛的三组对应(重抄一遍,因为它是"最优性证书"的来源):
它在算法上的用途(三条):
- 给定 、 都是可行解时,用互补松弛可以直接判定它们是否同时最优(这就是例题 4 第 5 步的"反查");
- 解出一个问题的最优解后,另一个问题的最优解可以通过互补松弛"读"出来(不必再解第二遍);
- 它是原始—对偶内点法(primal-dual interior point method)的核心方程之一:现代 LP 求解器把"可行性 + 互补松弛"作为一组方程用牛顿法求解。
几何直观:为什么互补松弛必然成立?
回顾弱对偶的证明链:
两个不等号的"缝隙"分别是
每一项都非负(、,括号内也 ),所以"和为零"当且仅当"每一项都为零"。 而"两个缝隙都为零"正是 (强对偶)。
一句话总结互补松弛的几何图像
最优时,原问题与对偶问题的"两个缝隙"必须同时被堵死。 而缝隙是"逐项相加"的,所以每一项都必须为零——这就是互补松弛的全部内容。
从几何上看: 落在可行域的一个顶点上(若干约束取等),而 恰好只在那些取等的约束上取正值。"哪个约束被用光"与"哪个影子价格为正"是同一件事的两种说法。
八、与线性代数其他部分的联系
8.1 约束矩阵的秩
- 。若 ,说明 的行线性相关,某些约束是冗余的(redundant),去掉它们不改变可行域。第九节的例题中第三条约束 在最优解处不紧(),其影子价格为 ,正是"边际上冗余"的表现。
- 可行域 的仿射维数为 ,其中 是在某内点取等的约束行拼成的矩阵。这与第 3 章的秩—零化度定理 完全一致(见 3-5-四大子空间的维数)。
- 若 ,则 有无穷多解,可行域(若存在)不会是单点,但可能有顶点;若 且 且 可逆,则 只有一个解,可行域退化为一点。
8.2 最优基对应可逆子矩阵
在松弛形式 中, 是 的 个线性无关列组成的 可逆矩阵。关键公式一览:
这四行公式就是"修正单纯形法"(revised simplex method)的全部内容:每步只需解两个线性方程组 与 ,而不必维护整张单纯形表,其数值实现依赖 的 LU 分解与更新(见 11-1-数值稳定性与LU)。
与克莱姆法则的联系
的每个分量由克莱姆法则给出 ( 是把 的第 列换成 )。因此"顶点坐标是若干行列式之比",这与第 5 章的行列式—体积观点一脉相承: 正是这 个紧约束线性无关(法向量不共面、相交于唯一一点)的代数判据。见 5-3-克莱姆法则与体积。
8.3 顶点坐标由 给出:一个具体验算
取第 3.2 节例题的最优顶点 。在该点取等的主约束是 与 ,对应的法向量是 的第 行:
( 说明这两条紧约束线性无关, 确实是顶点而不是两条平行线或漏掉一条的产物。)
于是顶点坐标为
对偶最优解同样由 给出:
再验算另一个基:若误取第 1、3 条约束(,)作为基:
检查可行性:,违反第二条约束,故这是基解但非基可行解——它甚至不在 中。这个小例子清楚说明:" 可逆"只保证是基解,还要 且满足其余约束才是顶点。
九、例题
例题 1(两变量,完整求解:画图 + 枚举顶点 + 对偶验证)
题目 求解
第 1 步:写出矩阵形式。 这里 ,,
,故三条约束中至少有一条在几何上"多余"(三条直线在 中必有依赖关系)。
第 2 步:画可行域。 三条边界线 、、 与两个坐标轴围成的五边形,顶点按逆时针为 。
第 3 步:枚举顶点。 两变量时顶点来自"两条约束取等号"的组合,逐个求解并检验可行性:
| 组合 | 方程组 | 解 | 可行性检验 | 目标值 |
|---|---|---|---|---|
| (1) 与 | , ✓ | |||
| (1) 与 (2) | , | ✓ | ||
| (1) 与 (3) | , | ✗ | 不可行 | |
| (2) 与 (3) | , | ✓ | ||
| (2) 与 | ✗ | 不可行 | ||
| (3) 与 | ✓ | |||
| 与 | —— | 显然 ✓ |
第 4 步:比较。 可行顶点及其目标值:
最大值为
第 5 步:验证最优性(用梯度/锥条件)。 在 处取等的约束是 (1) 与 (2),其法向量为 与 。目标梯度 应落在两者生成的锥中:
两个系数都 ✓,说明沿任何让 (1) 或 (2) 变松的方向移动,目标都不会增加——这就是最优性。
第 6 步:写出对偶并验证强对偶。
取 代入检验:
强对偶成立。再由弱对偶知 就是 (D) 的最优解。
第 7 步:验证互补松弛。
原问题的松弛量:,,。
对偶约束的松弛量:,。
全部满足,与定理 10.3.7 一致。
结论汇总
,;,。第 1、2 种资源的影子价格都是 ,第 3 种资源的影子价格为 (因为第 3 条约束在最优解处还剩 个单位没用完)。
例题 2(用 numpy 枚举顶点 + 用 scipy 直接求解)
(a)只用 numpy:枚举所有顶点。
import itertools
import numpy as np
# max c^T x s.t. A x <= b, x >= 0
A = np.array([[2.0, 1.0],
[1.0, 1.0],
[1.0, 2.0]])
b = np.array([10.0, 6.0, 10.0])
c = np.array([3.0, 2.0])
def enumerate_vertices(A, b):
"""枚举 A x <= b, x >= 0 的全部顶点(只适合 n, m 都很小的教学例子)。"""
m, n = A.shape
# 把非负约束 x_j >= 0 写成行向量 e_j^T x <= 0,与非负号分离处理
rows = [A[i] for i in range(m)] + [np.eye(n)[:, j] for j in range(n)]
rhs = [b[i] for i in range(m)] + [0.0] * n
vertices = []
for i, j in itertools.combinations(range(m + n), 2):
B = np.array([rows[i], rows[j]])
if abs(np.linalg.det(B)) < 1e-9:
continue # 两条约束平行,无唯一交点
x = np.linalg.solve(B, np.array([rhs[i], rhs[j]]))
# 必须检验可行性:解出交点不等于它是可行域的顶点
if np.all(A @ x <= b + 1e-9) and np.all(x >= -1e-9):
if not any(np.allclose(x, v, atol=1e-8) for v in vertices):
vertices.append(x)
return vertices
V = enumerate_vertices(A, b)
for v in V:
print(f"顶点 ({v[0]:.8f}, {v[1]:.8f}) z = {c @ v:.8f}")
best = max(V, key=lambda v: c @ v)
print("最优解 x* =", best, " 最优值 z* =", c @ best)
# 用最优基 B 复核:x_B = B^{-1} b
B = np.array([[2.0, 1.0], [1.0, 1.0]])
print("det B =", np.linalg.det(B))
print("B^{-1} b =", np.linalg.inv(B) @ b[:2])
print("对偶解 y = (B^{-1})^T c_B =", np.linalg.inv(B).T @ c)
输出(已在本机 numpy 2.3.5 下实测):
顶点 (4.00000000, 2.00000000) z = 16.00000000
顶点 (5.00000000, 0.00000000) z = 15.00000000
顶点 (2.00000000, 4.00000000) z = 14.00000000
顶点 (0.00000000, 5.00000000) z = 10.00000000
顶点 (0.00000000, 0.00000000) z = 0.00000000
最优解 x* = [4. 2.] 最优值 z* = 16.0
det B = 1.0
B^{-1} b = [4. 2.]
对偶解 y = (B^{-1})^T c_B = [1. 1.]
与例题 1 的手算结果完全一致。
(b)用 scipy.optimize.linprog(需要 scipy)。
本示例需要 scipy:pip install scipy
import numpy as np
from scipy.optimize import linprog
# linprog 求解的是 min c^T x,所以最大化问题要把 c 取负
c = np.array([3.0, 2.0])
A_ub = np.array([[2.0, 1.0],
[1.0, 1.0],
[1.0, 2.0]])
b_ub = np.array([10.0, 6.0, 10.0])
res = linprog(-c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None), (0, None)], method="highs")
print("x* =", res.x)
print("z* =", -res.fun) # 记得把负号还回来
print("松弛量 slack =", res.ineqlin.residual)
print("影子价格 marginals =", res.ineqlin.marginals)
print("status =", res.status, res.message)
输出:
x* = [4. 2.]
z* = 16.0
松弛量 slack = [0. 0. 2.]
影子价格 marginals = [-1. -1. -0.]
status = 0 Optimization terminated successfully. (HiGHS Status 7: Optimal)
用 linprog 的三个细节
1.
linprog只做最小化,最大化必须传-c并把res.fun取负;2. 它的默认
bounds=(0, None)恰好就是 ,但若变量可为负,必须显式写bounds=[(None, None), ...](参见官方文档中的示例:未指定边界的变量被默认加上非负限制,是常见错误来源);3.
res.status是诊断工具:0成功;2问题不可行(infeasible);3问题无界(unbounded);4数值困难。4.
res.ineqlin.marginals给出对偶变量(影子价格)。注意 linprog 内部是 ,符号约定可能与手算的 版本相差一个负号,以你所用版本的文档为准。
例题 3(单纯形法完整手算:一张表说清进基/离基/主元消元)
题目
用单纯形法求解
要求:写出初始表、每一步的进基/离基判断与主元消元、最终最优表,并读出对偶变量;最后与"枚举顶点"的结果对照。
解
第 1 步:化成松弛形式(等式形式)。
引入松弛变量 :
初始基是 (对应 中的单位块),初始顶点是 ,。
第 2 步:写出初始单纯形表。
表格的约定:每行一个基变量;最后一行的"目标行"记录 的表达式 ,即系数取目标函数系数的相反数;最右列是右端项 。
| 基变量 | RHS | 比值 | |||||
|---|---|---|---|---|---|---|---|
| 目标行 | —— |
第 3 步:迭代 1。
(a) 进基判断(最优性检验):看目标行,找最负的系数(Dantzig 规则)。这里 ,所以
几何含义: 的系数 说明"沿 轴正方向走, 上升最快"(每单位 贡献 ,而每单位 只贡献 )。
(b) 离基判断(最小比值检验):在 列中取正元素,用同行的 RHS 除以它,取比值最小的那一行——那一行最先碰到新的约束,也就是"沿这条边走到了头"。
| 行 | 基变量 | 列元素 | RHS | 比值 |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 |
最小比值是 ,出现在第 1 行,所以
(注意:第 1 行与第 3 行的比值都是 ,出现并列。任选一个即可——这里选第 1 行,得到基 。
比值的几何含义:沿 轴()向上走, 与 会在同一个点 处同时被压到零(两条约束同时取等)。此时新顶点仍然是 ,但基变量变成了 ——并列时选不同的行,得到的是同一个顶点上的不同基。若某个基可行解中正分量的个数少于 (这里是退化),选错行就可能在原地换基;本题的新基 仍有 个非负分量,不是退化情形。)
主元 = 第 1 行、 列的元素 。
(c) 主元消元(高斯—若尔当消元:把主元化为 ,把该列其余元素化为 )。
- :
- :
- :
- 目标行 目标行 :
迭代 1 后的表:
| 基变量 | RHS | 比值 | |||||
|---|---|---|---|---|---|---|---|
| 负元素,不参与 | |||||||
| 目标行 | —— |
当前顶点:,。用原约束检验: ✓; ✓; ✓(第三条约束取等)。可行 ✓。
第 4 步:迭代 2。
(a) 进基:目标行中只有 的系数 ,所以 进基。
(b) 离基: 列的正元素是 (第 1 行)与 (第 2 行);第 3 行是 (负元素不参与比值检验,因为它意味着该约束"不会先被碰到")。比值:
最小是 ,在第 2 行 ⟹ 离基。主元 。
(c) 主元消元。
- :
- :
- :
- 目标行 目标行 :
最终(最优)表:
| 基变量 | RHS | |||||
|---|---|---|---|---|---|---|
| 目标行 |
目标行全部 ,已最优。 读表:
第 5 步:验证最优解。
代数核对残差:
第 6 步:从最优表读出对偶变量(影子价格)。
规则:目标行中松弛变量的系数就是对应的对偶变量 (前提是目标行采用""的写法,如本例)。
验证对偶可行性 :
(两个对偶约束都取等,这与 、 的互补松弛条件一致。)
验证强对偶:
用最优基 复核。最终表的基变量是 ,对应的原始列是 的第 列、第 列与 的第 列:
(手算 的方法:分块求逆。左上角 块 的逆是 ;再用第三行消去右上块的贡献,得到最后一行为 。)
于是
与表格的 RHS 列完全一致(顺序是 )。
( 的列顺序是 ,所以 。)与从表格读出的对偶变量完全一致。
第 7 步:与"枚举顶点"对照。
两变量问题的顶点来自"两条约束取等号"的组合,共 个候选:
| 取等的两条约束 | 交点 | 是否可行 | 值 |
|---|---|---|---|
| (1) 与 (2) | ✓ | ||
| (1) 与 (3) | ✓ | ||
| (1) 与 | ✓ | ||
| (1) 与 | ✗() | —— | |
| (2) 与 (3) | ✗() | —— | |
| (2) 与 | ✗() | —— | |
| (2) 与 | ✓ | ||
| (3) 与 | ✓ | ||
| (3) 与 | ✗() | —— | |
| 与 | ✓ |
个候选里只有 个可行顶点,最优是 , ✓——与单纯形法的结果一致。
本题最值得记住的四件事
1. 进基选"最负系数"、离基选"最小比值",两个规则各管一件事:前者管"方向",后者管"走多远";
2. 比值检验只看正元素。进基列中的负元素或零元素不参与——它们对应的约束不会先被碰到(负元素时那个变量增大反而让该约束更松);
3. 目标行的松弛变量系数就是对偶变量,这一步让"解一个 LP"和"求影子价格"同时完成;
4. 最优表里的 之类的负数出现在 、 列是正常的——它们是 的元素,不是错误(本例 的确含有 、)。
例题 4(对偶问题的构造 + 互补松弛 + 强对偶验证)
题目
沿用例题 3 的原问题
(1) 写出它的对偶问题 (D);(2) 求出 (D) 的最优解并验证强对偶;(3) 逐条验证互补松弛条件;
(4) 解释三个影子价格的经济含义;(5) 说明为什么 与 都是 (D) 的可行解但后者不是最优。
解
第 1 步:写出对偶问题。
原问题的矩阵形式:
按定理 10.3.4(对称形式的对偶: 配 配 ,,):
对照检查(防止写反方向): 的第一行 来自 的第一列( 的系数),对应" 的对偶约束" ✓;第二行 来自 的第二列( 的系数),对应 ✓。
第 2 步:求 (D) 的最优解。
由例题 3 第 6 步已算出(也由表格的目标行直接读出)
验证可行性:
目标值:
而原问题的最优值是 。两者相等:
强对偶成立,故 就是 (D) 的最优解(由弱对偶,任何 (D) 的可行解都有 ,而 恰好取到 ,所以它最优)。
第 3 步:逐条验证互补松弛。
互补松弛条件(定理 10.3.7)是两族方程:
(a) 原问题的松弛量(,用 ):
| 松弛量 | 乘积 | ||||
|---|---|---|---|---|---|
| 1 | ✓ | ||||
| 2 | ✓ | ||||
| 3 | ✓ |
(b) 对偶问题的松弛量():
| 松弛量 | 乘积 | ||||
|---|---|---|---|---|---|
| 1() | ✓ | ||||
| 2() | ✓ |
全部满足,与定理 10.3.7 一致。
用互补松弛的"逻辑"反向检查最优性(这是互补松弛最有用的地方):
- ⟹ 第 1 条原约束必须紧;(1) 确实取等 ✓;
- ⟹ 第 2 条原约束必须紧;(2) 确实取等 ✓;
- 第 3 条原约束松(松弛量 )⟹ 必有 ✓;
- 与 ⟹ 两条对偶约束都必须紧,两者都取等 ✓。
只要给出一个 (D) 的可行解 ,它的目标值 就是 的上界——这就是"最优性证书"。例如取 得 ,立刻断定原问题的最优值 ;而原问题已有可行解达到 ,双方夹逼即得最优。
第 4 步:三个影子价格的经济含义。
把原问题读成一个生产计划: 与 是两种产品的产量, 是单位利润,三条约束是三种资源的消耗上限:
| 资源 | 消耗系数 | 总量 | 影子价格 | 经济解读 |
|---|---|---|---|---|
| 资源 1 | 多进 1 单位资源 1,总利润增加约 | |||
| 资源 2 | 多进 1 单位资源 2,总利润增加约 | |||
| 资源 3 | 该资源没有用完(还剩 ),边际价值为零 |
采购决策:若资源 1 的市场价低于 、资源 2 的市场价低于 ,买入就划算;资源 3 已经过剩,再多给也不要()。
资源 2 的影子价格为什么这么低?因为它虽然和资源 1 的"总量"一样(都是 ),但它在两种产品上的消耗系数是 ,在最优解处它被"卡"得更早、对总利润的边际贡献更小——这是"边际价值"而不是"总价值",容易和资源总量混淆。
第 5 步:为什么 可行但不最优?
验证可行性:
目标值:
所以 是可行解,但不是最优解——它的目标值 比最优值 大。
找出它"卡"在哪一条互补松弛条件上: 的分量中 、,按互补松弛,第 2 条与第 3 条原约束都必须紧。也就是说 必须同时满足
解这个方程组:
检验它是否满足第 1 条约束:
所以不存在与 互补的可行 ⟹ 不可能是最优解 ✓。
这个"反查"过程就是互补松弛的威力:给定一个对偶可行解,不用重新解原问题,只要看它"要求哪些原约束取等",就能判断它是否可能是最优的。反过来也成立:给定一个原可行解,看它要求哪些对偶约束取等,就能判断它是否最优。
互补松弛的"三句话"记忆法
1. 正影子价格的资源一定被用光( 第 条约束紧);
2. 没用完的资源影子价格为零(第 条约束松 );
3. 真正投产的产品,其影子成本恰好等于利润()。
这三句话把"经济直觉"变成了可以逐条验算的方程——这正是线性代数与经济学在这里的交汇点。
例题 5(几何直观:顶点枚举 vs 单纯形路径的完整对比)
题目
仍取例题 3 的问题:(1) 完整枚举可行域的全部顶点并算出各顶点的目标值;(2) 画出(文字描述)单纯形法走过的路径;(3) 比较两种方法的"检验次数";(4) 说明当变量与约束增多时,为什么必须用单纯形法而不能枚举。
解
第 1 步:画出可行域。
三条边界线:
- :,过 与 ,法向量 ;
- :,过 与 ,法向量 ;
- :,过 与 ,法向量 。
加上 、,取含原点的半平面交。文字描述可行域:它是第一象限里由 轴、 轴、(从 到 这一段)、(从 到 这一段)围成的四边形,顶点依次为
注意 完全在可行域之外"擦过":它与 交于 、与 交于 ,而后者不在可行域内(因为它违反 )。所以 对可行域的形状没有影响——这就是例题 3 中最优表里 (第三条约束不紧)的几何原因。
第 2 步:枚举全部顶点。
两变量时,顶点来自"两条约束取等号",候选共 个(含非负约束 、):
| # | 取等的两条 | 交点 | 可行性检验 | |
|---|---|---|---|---|
| 1 | (1) 与 (2) | 紧 ✓,: ✓ | ||
| 2 | (1) 与 (3) | : ✓ | ||
| 3 | (1) 与 | 同上(同一个顶点) | ||
| 4 | (1) 与 | : ✗ | 不可行 | |
| 5 | (2) 与 (3) | : ✗ | 不可行 | |
| 6 | (2) 与 | : ✗ | 不可行 | |
| 7 | (2) 与 | : ✓,: ✓ | ||
| 8 | (3) 与 | 同上(同一个顶点) | ||
| 9 | (3) 与 | : ✗ | 不可行 | |
| 10 | 与 | 显然 ✓ |
个候选中只有 个不同的可行顶点(、、、,其中 被算了三次——因为它在三条约束的交点上)。
比较目标值:
第 3 步:单纯形法走过的路径(几何版本)。
| 步 | 基变量 | 顶点 | 走到哪条边上 | 进基/离基 | |
|---|---|---|---|---|---|
| 0 | 起点(原点) | —— | |||
| 1 | 沿 向上走,直到碰到 与 | 进、 离 | |||
| 2 | 沿 ( 取等)向右上走,直到碰到 | 进、 离 | |||
| 3 | 目标行全 | 停止 | —— | 最优 |
路径读法:
每一步都是"沿一条边走到相邻顶点",而且每走一步目标值都严格增大()——这就是单纯形法的单调性。
第 4 步:两种方法的检验次数对比。
| 方法 | 需要检验的候选点数 | 说明 |
|---|---|---|
| 枚举顶点 | 个候选交点(),实际可行 个 | 每个候选都要解一个 方程组并检验可行性 |
| 单纯形法 | 次迭代 | 每次只解一个"进基/离基"判断 + 一次行变换 |
一般情形下的规模对比( 个变量、 条主约束):
举几个数字感受一下( 时):
时枚举法需要检验 个顶点——即便每秒能检验 个,也要 年。 而单纯形法只需约一百次迭代。这就是"不枚举全部顶点、只沿边行走"的价值所在。
但不要以为单纯形法永远快
单纯形法的最坏情况复杂度是指数级的(Klee–Minty 立方体是经典反例: 个变量、 条约束的问题可以让单纯形法走遍 个顶点)。只是实际问题上它几乎总是多项式级的。
若需要理论上的多项式时间,要用内点法(Karmarkar 1984 起):它不沿边行走,而是沿可行域内部的一条"中心路径"逼近最优点,每一步解一个形如 的对称正定方程组——这正是第 6 章正定矩阵与第 11 章数值方法的直接应用(见 11-3-迭代方法与预条件)。
两种方法的几何图像对比:
- 单纯形法:沿多面体的边界从一个顶点跳到相邻顶点("贴着墙走");
- 内点法:从可行域内部穿过("在屋子里走"),每一小步都解一个线性方程组。
例题 6:用 numpy 完整验证单纯形法、对偶与互补松弛
题目
用 numpy 对例题 3 的问题完成五件事:(1) 用单纯形表逐步迭代并打印每一步的表格;(2) 枚举全部顶点并与单纯形法的结果对照;(3) 用最优基 计算 与 ;(4) 验证强对偶 ;(5) 逐条验证互补松弛条件。
本示例只需 numpy(numpy.linalg 已提供 solve、inv、det、matrix_rank),无需额外安装。下面所有输出均为实测结果。
import itertools
import numpy as np
np.set_printoptions(precision=6, suppress=True)
# ---------------- 数据:max 2x+3y, s.t. Ax <= b, x >= 0 ----------------
A = np.array([[1.0, 2.0],
[2.0, 1.0],
[1.0, 3.0]])
b = np.array([4.0, 4.0, 6.0])
c = np.array([2.0, 3.0])
m, n = A.shape
N = np.hstack([A, np.eye(m)]) # 松弛形式的系数矩阵 [A | I]
# ---------------- (1) 单纯形表逐步迭代 ----------------
def show(T, basis, tag):
print("--- %s ---" % tag)
print(" " + "".join("%9s" % s for s in ["x", "y", "s1", "s2", "s3", "RHS"]))
for i, r in enumerate(T[:m]):
print(" %-5s" % basis[i] + "".join("%9.4f" % v for v in r))
print(" %-5s" % "z" + "".join("%9.4f" % v for v in T[m]))
T = np.vstack([np.hstack([N, b.reshape(-1, 1)]),
np.hstack([-c, np.zeros(m + 1)])])
basis = ["s1", "s2", "s3"]
show(T, basis, "初始表")
while True:
# 进基:目标行中最负的系数
j = int(np.argmin(T[m, :m + n]))
if T[m, j] >= -1e-12:
break # 全部 >= 0,最优
# 最小比值检验(只看正元素)
col = T[:m, j]
ratios = np.where(col > 1e-12, T[:m, m + n] / np.where(col > 1e-12, col, 1), np.inf)
i = int(np.argmin(ratios))
if not np.isfinite(ratios[i]):
print("无界!"); break
print("进基 %s(检验数 %.4f),离基 %s(比值 %.4f),主元 %.4f"
% (["x", "y", "s1", "s2", "s3"][j], T[m, j], basis[i], ratios[i], T[i, j]))
T[i] = T[i] / T[i, j]
for k in range(m + 1):
if k != i:
T[k] = T[k] - T[k, j] * T[i]
basis[i] = ["x", "y", "s1", "s2", "s3"][j]
show(T, basis, "迭代后")
print("最优基变量:", basis, " 对应值:", T[:m, m + n])
print("最优值 z* =", T[m, m + n])
# ---------------- (2) 枚举全部顶点 ----------------
rows = [A[i] for i in range(m)] + [np.eye(n)[:, j] for j in range(n)]
rhs = [b[i] for i in range(m)] + [0.0] * n
names = ["(1)", "(2)", "(3)", "x=0", "y=0"]
print("--- 顶点枚举 ---")
for i, j in itertools.combinations(range(m + n), 2):
Bm = np.array([rows[i], rows[j]])
if abs(np.linalg.det(Bm)) < 1e-12:
continue
sol = np.linalg.solve(Bm, np.array([rhs[i], rhs[j]]))
ok = bool(np.all(A @ sol <= b + 1e-9) and np.all(sol >= -1e-9))
print(" %-5s ∩ %-5s -> (%9.6f, %9.6f) 可行=%-5s z=%9.6f"
% (names[i], names[j], sol[0], sol[1], ok, c @ sol))
# ---------------- (3) 最优基 B 与对偶解 ----------------
xs = np.array([4 / 3, 4 / 3])
B = np.array([[2.0, 1.0, 0.0], # 基变量顺序 (y, x, s3) 对应的列
[1.0, 2.0, 0.0],
[3.0, 1.0, 1.0]])
cB = np.array([3.0, 2.0, 0.0])
print("--- 最优基 ---")
print("det B =", round(np.linalg.det(B), 8))
print("B^{-1} b =", np.linalg.inv(B) @ b, "(顺序 y, x, s3)")
y = np.linalg.inv(B).T @ cB
print("y = (B^{-1})^T cB =", y)
# ---------------- (4) 强对偶 ----------------
z_star = c @ xs
w_star = b @ y
print("--- 强对偶 ---")
print("z* = %.8f w* = %.8f 相等 = %s" % (z_star, w_star, np.isclose(z_star, w_star)))
print("对偶可行性 A^T y >= c :", np.round(A.T @ y, 8), ">=", c, "->", bool(np.all(A.T @ y >= c - 1e-12)))
# ---------------- (5) 互补松弛 ----------------
print("--- 互补松弛 ---")
slack_primal = b - A @ xs
print("原问题松弛量 b - A x =", np.round(slack_primal, 8))
print("y_i * slack_i =", np.round(y * slack_primal, 12), "(应全为 0)")
slack_dual = A.T @ y - c
print("对偶松弛量 A^T y - c =", np.round(slack_dual, 8))
print("x_j * (A^T y - c)_j =", np.round(xs * slack_dual, 12), "(应全为 0)")
输出(实测):
--- 初始表 ---
x y s1 s2 s3 RHS
s1 1.0000 2.0000 1.0000 0.0000 0.0000 4.0000
s2 2.0000 1.0000 0.0000 1.0000 0.0000 4.0000
s3 1.0000 3.0000 0.0000 0.0000 1.0000 6.0000
z -2.0000 -3.0000 0.0000 0.0000 0.0000 0.0000
进基 y(检验数 -3.0000),离基 s1(比值 2.0000),主元 2.0000
--- 迭代后 ---
x y s1 s2 s3 RHS
y 0.5000 1.0000 0.5000 0.0000 0.0000 2.0000
s2 1.5000 0.0000 -0.5000 1.0000 0.0000 2.0000
s3 -0.5000 0.0000 -1.5000 0.0000 1.0000 0.0000
z -0.5000 0.0000 1.5000 0.0000 0.0000 6.0000
进基 x(检验数 -0.5000),离基 s2(比值 1.3333),主元 1.5000
--- 迭代后 ---
x y s1 s2 s3 RHS
y 0.0000 1.0000 0.6667 -0.3333 0.0000 1.3333
x 1.0000 0.0000 -0.3333 0.6667 0.0000 1.3333
s3 0.0000 0.0000 -1.6667 0.3333 1.0000 0.6667
z 0.0000 0.0000 1.3333 0.3333 0.0000 6.6667
最优基变量: ['y', 'x', 's3'] 对应值: [1.333333 1.333333 0.666667]
最优值 z* = 6.666666666666667
--- 顶点枚举 ---
(1) ∩ (2) -> ( 1.333333, 1.333333) 可行=True z= 6.666667
(1) ∩ (3) -> ( 0.000000, 2.000000) 可行=True z= 6.000000
(1) ∩ x=0 -> ( 0.000000, 2.000000) 可行=True z= 6.000000
(1) ∩ y=0 -> ( 4.000000, 0.000000) 可行=False z= 8.000000
(2) ∩ (3) -> ( 1.200000, 1.600000) 可行=False z= 7.200000
(2) ∩ x=0 -> ( 0.000000, 4.000000) 可行=False z=12.000000
(2) ∩ y=0 -> ( 2.000000, 0.000000) 可行=True z= 4.000000
(3) ∩ x=0 -> ( 0.000000, 2.000000) 可行=True z= 6.000000
(3) ∩ y=0 -> ( 6.000000, 0.000000) 可行=False z=12.000000
x=0 ∩ y=0 -> ( 0.000000, 0.000000) 可行=True z= 0.000000
--- 最优基 ---
det B = 3.0
B^{-1} b = [1.333333 1.333333 0.666667] (顺序 y, x, s3)
y = (B^{-1})^T cB = [1.333333 0.333333 0. ]
--- 强对偶 ---
z* = 6.66666667 w* = 6.66666667 相等 = True
对偶可行性 A^T y >= c : [2. 3.] >= [2. 3.] -> True
--- 互补松弛 ---
原问题松弛量 b - A x = [0. 0. 0.66666667]
y_i * slack_i = [0. 0. 0.] (应全为 0)
对偶松弛量 A^T y - c = [0. 0.]
x_j * (A^T y - c)_j = [0. 0.] (应全为 0)
逐项解读:
- 单纯形表的两步迭代与例题 3 的手算完全一致:第一步 进、 离(主元 ),第二步 进、 离(主元 ),最终表的目标行全非负, ✓;
- 顶点枚举给出 个候选, 个可行(其中 重复三次),最优仍是 , ✓;
- 与表格 RHS 列完全一致(顺序为 ): ✓;
- 与表格目标行的松弛变量系数完全一致 ✓;
- 强对偶: ✓;
- 互补松弛:两个乘积向量都全为零 ✓。
这段代码最值得复用的两个技巧
1.
ratios = np.where(col > 1e-12, RHS / col, np.inf):用np.where一次性完成"只看正元素"的最小比值检验。若直接除,负元素会给出负比值,导致选错离基变量——这是手写单纯形法最常见的 bug。2. 用
B^{-1}\mathbf{b}与(B^{-1})^{\mathrm{T}}\mathbf{c}_B复核表格:这两行公式把"单纯形表"与"基矩阵的逆"连起来(第 8.2 节),是检查表格算出错的最快手段。若表格的 RHS 列与 不一致,说明行变换出错了。
例题 7(证明题):互补松弛定理的完整证明与"最优性证书"用法
题目
设原问题 (P) 与对偶问题 (D) 为
设 是 (P) 的可行解, 是 (D) 的可行解。证明:
并用它说明"如何用一组对偶可行解来证明某个原可行解已经最优"。
证明
第 1 步:写出弱对偶的两个不等号。
由 (D) 的约束 ,两边左乘 (逐分量非负,这一步是全部证明的关键,不能省):
由 (P) 的约束 ,两边左乘 :
合并 (1)(2):
第 2 步:把两个不等号改写成"非负项之和"。
(1) 的左右之差:
(2) 的左右之差:
两项都非负:由可行性,每个 、,而 、。所以 (4)(5) 都是非负项之和。
第 3 步( 方向):由互补松弛推出同时最优。
设两族方程都成立,即 (4)(5) 每一个求和项都为零,于是两个差都为零:
串联得 。而由弱对偶 (3),任何原可行解的目标值都不超过任何对偶可行解的目标值,既然 、 的目标值相等,它们就分别是两个问题的最优解。
第 4 步( 方向):由同时最优推出互补松弛。
设 、 同时最优,即 (这要用到强对偶定理 10.3.6,或直接假设两者最优值相等)。于是 (3) 中"两头相等、中间夹着",故两个不等号都取等号:
第一个等号 ⟹ (4) 的和为 ⟹ 每个非负项为零 ⟹ 对一切 成立;
第二个等号 ⟹ (5) 的和为 ⟹ 对一切 成立。
两族条件都得证。
第 5 步:这个定理为什么是"最优性证书"?
逻辑结构:、 同时最优 互补松弛成立。而验证互补松弛只需要一次矩阵乘向量( 与 )加上逐项相乘——远比重新解一遍 LP 便宜。
具体用法(三步证书法):
- 拿到一个原问题的可行解 (例如由某个启发式算法给出),记下 ;
- 想办法找一个对偶可行解 使 (等价地:验证互补松弛成立);
- 一旦找到, 就是最优解——不需要再迭代下去了。
用例题 3 的数值走一遍:,。取 :
证书通过, 最优,证明完毕——全程没有解任何线性方程组,只算了两次内积。
三步证书法在算法里的地位:
| 场景 | 证书的作用 |
|---|---|
| 单纯形法早停 | 目标行全非负时,目标行的松弛变量系数直接给出证书 , 自动成立 |
| 分支定界(整数规划) | 每个子问题的最优值作为"上界证书",用于剪枝 |
| 原始—对偶内点法 | 把互补松弛方程作为待解的方程组之一,用牛顿法同时逼近 与 |
| 组合优化(最大流—最小割) | 最大流的值 最小割的容量:割就是一个 - 的对偶可行解(见 [[10-1-图与网络]]) |
证明里唯一"有技术含量"的一步
"左乘 不改变不等号方向"——这一步依赖 。
去掉 会怎样? 若某个 ,左乘后不等号会翻转,弱对偶立刻失效, 不再成立,整套对偶理论(强对偶、互补松弛、影子价格)全部崩掉。
所以"变量非负"不是技术性的小假设,而是整个对偶理论的支柱。 这也解释了为什么第 1.2 节的四个转化法则里,把"自由变量"拆成 (两个非负变量)这一步如此重要——它把问题重新拉回到"对偶理论能生效"的世界里。
十、应用
| 领域 | 决策变量 | 目标 | 典型约束 |
|---|---|---|---|
| 生产计划 | 各产品产量 | 总利润最大 | 原料、工时、机器产能 |
| 运输问题 | 各线路运量 | 总运费最小 | 供需平衡、线路容量 |
| 配料 / 饲料 | 各原料用量 | 成本最小 | 营养成分下限 |
| 投资组合(LP 近似) | 各资产权重 | 期望收益最大 | 预算、单资产上限、行业敞口 |
| 网络流 | 各边流量 | 流量最大 | 容量、流量守恒() |
| 图像 / 信号( 问题) | 稀疏系数 | 最小 | 拟合误差约束 |
| 博弈论 | 混合策略概率 | 保证收益最大 | 概率和为 、非负 |
与图论的联系(本库第 10 章内部):网络最大流问题的约束矩阵就是关联矩阵 (incidence matrix)的变体,流量守恒写成 ,容量约束写成 。最大流—最小割定理正是 LP 强对偶定理在图上的特殊形式:最大流量 最小割容量,而"割"就是对偶变量取 的最优解。见 10-1-图与网络。
与数值线性代数的联系:现代 LP 求解器大多使用内点法(interior point method),它沿中心路径走,其每一步要解形如 的对称正定方程组——正是第 6 章的正定矩阵与第 11 章的数值方法;而单纯形法每步更新 的 LU 分解。见 11-3-迭代方法与预条件。
与最小二乘的对照:最小二乘无约束、目标二次(),解由法方程给出,是内部点;LP 有约束、目标线性,解在顶点。两者都用到投影/正交的直觉,但最优解的几何位置截然不同。
十一、易错点
八个高频错误
1. 以为最优解在可行域内部。 只要目标函数非平凡()且可行域有顶点,最优解一定可以取在顶点。若你手算得到的最优点所有约束都严格满足(全是严格不等式),那它不可能是最优解——除非目标函数在该区域是常数(例如 ,或者你沿着一条与等值线平行的边移动,此时最优解集包含整条边,但端点仍是顶点)。
2. 忘记非负约束。 是标准形的组成部分,不是可选项。漏掉它会导致:
- 可行域不再是多面体(可能变成无界区域);
- 顶点个数与位置全部改变;
- 顶点不再是" 个紧约束的交"(少了 这一族约束)。
反过来,软件里也要小心:
linprog默认所有变量 ,若某个变量本应可取负值而不显式放开边界,得到的是另一个问题的解。3. 对偶写反方向。 记忆口诀:原约束与对偶变量同向,原变量与对偶约束反向。 即
- 原问题 配 ,则原约束 对应对偶变量 ,原变量 对应对偶约束 ;
- 若原问题是 配 ,则对偶是 配 ,方向全部翻转。
常见的错法是把对偶约束也写成 ,这样强弱对偶的证明立刻失效( 乘上去不等号方向就不对了)。
4. 混淆"无界"与"不可行"。 两者完全不同:
- 不可行(infeasible):,可行解都不存在,谈不上最优;
- 无界(unbounded): 但目标函数在 上无上界,最优值 。
由弱对偶:原问题无界 对偶不可行;原问题不可行 对偶无界或不可行(注意"或"!)。单纯形法里,进基列整列非正正是无界的信号——沿这条边永远不会碰到新约束。
5. 解出交点却不检验可行性。 例题 1 中 与 都是"两条约束的交点",但都不是可行解。"是基解"与"是顶点"之间差一个 (以及满足其余约束)。
6. 忘记松弛变量占用变量个数。 松弛形式下变量总数是 ,基的大小是 ,非基变量个数是 。若把 与 弄混," 个紧约束确定顶点"这句话就会用错。
7. 把退化当成错误。 退化(多个约束交于同一顶点)会让单纯形法换基但顶点不变,理论上可能出现循环(cycling)。实践中极小概率发生;理论上有 Bland 规则或字典序规则保证有限步终止。
8. 忽略整数性。 LP 的解可能不是整数(如 )。若业务要求整数解,必须用整数规划(integer programming),它是 NP 难的,不能简单地对 LP 解四舍五入(舍入后可能不可行,也可能远非最优)。
更多易错点(单纯形法手算专题)
单纯形法手算的七个专属陷阱
1. 最小比值检验里用了零元素或负元素。 只对进基列的正元素做比值。零元素会让比值"无穷大"(那一行永远不会先被碰到),负元素会让比值变负(选了它就会破坏可行性)。这是手算单纯形法第一大错源:一旦用错,下一次迭代就会出现负的 RHS,解立刻不可行。
2. 目标行的符号约定前后不一致。 常见两种写法:
- 写法 A(本篇例题 3 采用):目标行写 ,则"负系数进基"、"全部 时最优";
- 写法 B:目标行写 ,则"正系数进基"、"全部 时最优"。
两种写法都正确,但绝不能混用。 混用的后果是"永远不停止"或"在第一步就宣布最优"。
3. 主元消元时忘了更新目标行。 四个动作里最容易漏的是"目标行也要做行变换"。若只更新约束行,检验数就全错了。判断方法:更新后基变量对应的目标行系数必须全为 (因为基变量的检验数为 )。
4. 把"目标行的松弛变量系数"读成"松弛变量的值"。 这两件事完全不同:
- 松弛变量的值在最优表的 RHS 列(本例 );
- 目标行的松弛变量系数是对偶变量(影子价格)(本例 ,,)。
读错这一处,影子价格全部作废。
5. 出现并列比值时以为"选哪个都一样"。 并列比值意味着同一个顶点对应多个基(共 个紧约束交于一点)。选不同的行会得到不同的基,下一步的迭代路径可能不同,但只要规则一致,最终仍会走到同一个最优值。真正的风险是退化情形下的循环(cycling)——理论上可能原地打转;实践中概率极低,需要时用 Bland 规则(选下标最小的负检验数进基、下标最小的比值行离基)保证有限步终止。
6. 忘记"变量非负"约束也占用一个候选顶点。 枚举顶点时,候选来自"任意 条紧约束",其中紧约束既包括主约束 ,也包括非负约束 。漏掉非负约束会少枚举一半以上的顶点。 两变量时共 个候选(本例 个)。
7. 把"无界"与"不可行"与服务"迭代不收敛"混为一谈。 三种终止状态要分清:
| 状态 | 判据 | 几何含义 |
|---|---|---|
| 最优 | 目标行全部非负 | 所有边的方向都不再上升 |
| 无界 | 进基列所有元素 | 沿这条边可以无限走,永远碰不到新约束 |
| 不可行 | 初始就没有基可行解(需两阶段法) | 可行域为空,谈不上最优 |
若进基列所有元素 而你又"硬做比值检验",就会得到一个空集或负比值——此时应该停下来写"无界"。
补充练习(单纯形法、对偶与几何直观)
补充练习 7(基础) 用单纯形法求 ,约束为
要求:写出初始表、每一步的进基/离基判断与主元消元(至少两步),给出最优解与最优值,并写出对偶问题与它的最优解。
补充练习 8(基础) 判断下列 LP 属于哪种情形(最优 / 无界 / 不可行),并说明判据:
补充练习 9(进阶) 对例题 3 的问题,把 从 增加到 ,用影子价格估计最优值的变化,再用互补松弛判断最优基是否改变(提示:先看 是否仍然非负);若把 从 增加到 ,最优值是否改变?为什么?
补充练习 10(进阶) 设
证明:若 (P) 无界,则 (D) 无可行解(提示:用弱对偶——若 (D) 有可行解 ,则对 (P) 的任意可行解 都有 ,即目标函数被有限数界住)。
补充练习 11(思考) 考虑两变量 LP:,,。
(1) 求出可行域的全部顶点与最优解;
(2) 说明最优解不唯一(整个可行域都是最优解),并解释这与"目标函数与某条约束的边界平行"的关系;
(3) 若用单纯形法求解,会在哪一步停止?目标行会是什么样子?(提示:进基变量的检验数可能是 。)
补充练习 12(思考) 用 、 的简单例子说明: 个" 条紧约束组合"中,为什么只有一部分是可行的顶点(提示:从"解出的交点必须满足其余所有约束"这个角度回答,并指出"基解"与"基可行解"的差别)。
十二、练习题
基础题 1 把下列问题化为标准形(,,):
基础题 2 求可行域 的全部顶点,并求 与 的最优解。
进阶题 3 对第 3.2 节的问题写出对偶问题,验证 可行,并用互补松弛条件说明为什么 。
进阶题 4 设 ,,。写出原问题与对偶问题,用枚举顶点法求两者最优解,并验证强对偶与互补松弛。提示:可行域是 平面上三条直线所围的区域。
思考题 5 证明:若 与 的某一行 方向相同(即 ,),则最优解可在使第 条约束取等的面上取得,且该面的任意顶点都是最优解(最优解集含一整条边)。据此解释"等值线与某条边平行"时最优解不唯一的现象。
思考题 6 说明为什么 LP 的最优值 作为 的函数是凹的(对 问题)且分段线性的,并解释其"折点"对应基的变化(即 的跳变)。
十三、常见问题 FAQ
Q1:为什么说线性规划"是"线性代数问题?它看起来只是在做优化。
因为它只有三种运算:矩阵乘向量(、)、比较()、以及可逆矩阵求解()。所有几何对象——超平面、法向量、锥、基、秩、转置——都是第 1–5 章的词汇。Strang 把 LP 放在第 10 章,正是因为它把"行的图像(半空间的交)"与"列的图像( 落在列的锥中)"这两条主线重新汇合了一次。见 2-1-向量与线性方程组。
Q2:单纯形法会不会枚举指数多个顶点?
不会。它的最坏情况复杂度是指数级的(Klee–Minty 立方体是经典反例),但每一次迭代只走到一个相邻顶点,而相邻顶点之间只差一个紧约束。实际中迭代次数通常是 的小倍数(经验上 到 量级)。若需要多项式时间,用内点法(Karmarkar 1984 起)。
Q3:对偶问题有什么用?原问题不是已经能解了吗?
四个用途:
- 提供最优性证书:只要给出一个可行对偶解,其目标值就是原问题最优值的上界,可以用来证明某个原可行解已经最优(这正是单纯形法早停的判据);
- 解释影子价格:对偶变量就是资源边际价值,是经济与管理决策的直接依据;
- 计算更方便:有时对偶问题的规模小得多( 时对偶只有 个变量),或结构更好(例如对偶可能就是最大流/最小割);
- 敏感性分析:,直接回答"再多一点资源值多少"。
Q4:为什么法向量变换要用 ?这和 LP 有关系吗?
那两个问题在本篇之外(属于本篇的姊妹篇 10-5-图形学与密码学)。但思维模式相同:凡是要"保持某种几何关系不变"的变换,都要用逆矩阵或逆转置。LP 里保持的是" 落在活跃约束法向量的锥中",图形学里保持的是"法向量与切向量正交",两者都是"用 或 把关系搬到新坐标系"。
本篇小结
一、核心结论(十二句话)
- LP 的标准形:,,。四个转化法则(目标反向、不等式反向、引入松弛变量、自由变量拆分)必须记牢。
- LP 是线性代数问题:每条约束是闭半空间(边界是法向量为 的超平面),可行域是半空间的交,即凸多面体;目标 是与固定向量的内积。
- 最优解一定在顶点取得:证明的核心是"线性函数 + 凸可行域"——沿可行方向走到边界,活跃约束的秩每次至少加 ,至多 步到达顶点。
- 顶点 基可行解:顶点由 个线性无关的紧约束确定;松弛形式下有 个变量、 个等式,一个基解让 个变量取零。顶点个数至多 。
- 单纯形法只做三件事:找初始顶点、判断最优(检验数全 )、沿边走到相邻顶点(换基)。"相邻顶点"就是"只差一个紧约束"。
- 进基选最负检验数,离基选最小比值(只看正元素),主元消元就是高斯—若尔当消元。 目标行的松弛变量系数就是对偶变量。
- 无界的判据:进基列的所有元素 (沿这条边永远碰不到新约束)。
- 对偶的对称美:,,,;原约束与对偶变量同向,原变量与对偶约束反向。
- 弱对偶 ,证明只用了"左乘非负向量不改变不等号方向"。它给出最优性证书(对偶可行解的目标值是原问题最优值的上界)。
- 强对偶 ,证明完全由最优基 给出:
- 互补松弛: 与 。正影子价格的资源一定用光;没用完的资源影子价格为零。
- 几何直观:单纯形法沿多面体的边界走(顶点 → 相邻顶点);内点法从内部穿过(每步解一个对称正定方程组)。
二、易混概念对照表
| 容易混淆的一对 | 它们分别是什么 | 一句话区分 |
|---|---|---|
| 基解 与 基可行解 | 任意符号 vs 还要求 | 前者只是线性方程组的解,后者才在多面体里 |
| 可行 与 有界 | vs 目标在 上有界 | 不可行 ⟹ 谈不上最优;可行但无界 ⟹ 最优值 |
| 无界 与 不可行 | 进基列全 vs 初始就没有基可行解 | 前者沿边无限走,后者根本没有边可走 |
| 检验数为 与 检验数为负 | 最优解不唯一(整条边都最优)vs 还能改进 | 意味着"沿这条边目标不变" |
| 退化 与 并列比值 | 正分量个数 vs 一次比值检验出现并列 | 前者是基可行解的性质,后者是换基时的现象 |
| 影子价格 与 资源总量 | (边际价值)vs | 资源多不等于边际价值高 |
| 中的"" 与 中的"" | 对偶约束 vs 原约束 | 方向相反;记口诀"原约束与对偶变量同向,原变量与对偶约束反向" |
| 松弛变量 与 剩余变量 | ( 情形)vs ( 情形) | 加法对应"没用完的量",减法对应"超出的量" |
| 自由变量 与 非负变量 | 无符号限制 vs | 自由变量必须拆成 ,否则对偶理论失效 |
| 单纯形法 与 内点法 | 沿边界走(顶点序列)vs 沿内部走(中心路径) | 前者实用极快但最坏情况指数级;后者有多项式时间保证 |
| 枚举顶点 与 单纯形法 | 个候选 vs 约 次迭代 | 时前者 ,后者约一百步 |
| 强对偶 与 互补松弛 | 两个最优值相等 vs 两个最优解的"零乘积"刻画 | 前者说"值相等",后者说"解长什么样" |
三、三句话记住全篇
用一张卡片背下本篇:
- 几何:可行域是多面体,最优解在顶点;单纯形法沿边走;
- 代数:顶点 可逆子矩阵 ;最优性 检验数 ;
- 对偶: 既是影子价格,也是互补松弛里的那组数;最大利润 资源的最小总价值。
相关笔记
- 3-4-线性无关基与维数 —— 本篇的"基"就是这里的基: 个线性无关的紧约束行构成顶点, 是 的可逆子矩阵。
- 5-3-克莱姆法则与体积 —— 顶点坐标 , 即紧约束线性无关。
- 10-1-图与网络 —— 网络最大流是 LP 的特例,最大流—最小割定理就是强弱对偶在图上的形态。
- 11-3-迭代方法与预条件 —— 内点法每步要解对称正定方程组,是第 11 章的直接应用。
- 10-4-傅里叶级数与函数空间 —— 同样是"把几何直觉推广"的一篇:那里把向量推广到函数,这里把线性方程组推广到线性不等式组。
参考来源
- Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley-Cambridge Press, 2016, Section 10.4 "Linear Programming"(原问题与对偶、影子价格、单纯形法的几何)。
- Introduction to Linear Algebra, 5th Edition 官方站点(教材目录与章节 PDF 索引)。
- MIT 18.06 Linear Algebra, Spring 2010(公开课主页,含讲稿与习题)。
- MIT 18.06 Video Lectures(第 35 讲为线性规划,第 24 讲含 Fourier/Markov 的对照)。
- scipy.optimize.linprog 文档(求解接口、
status状态码、marginals影子价格与bounds默认值)。 - numpy.linalg.matrix_rank 文档(判断紧约束是否线性无关、识别冗余约束)。