26篇用流提供一个可行值，用割限制所有流的最大值；27篇用匹配和点覆盖形成同样大小的两份证书。线性规划把这种“可行方案与界相遇”的结构推广到线性不等式：原问题给出方案，对偶问题给出界，两边可行且目标相等，就足以证明最优。

本篇只核对小型问题的精确证书，不实现通用线性规划求解器。求出候选解与验证候选解是两个任务；有一个通过检查的证书，并不意味着已经实现了搜索它的算法。

从约束到原问题

考虑非负变量x、y，最大化3x+2y，约束为

x+y≤4,2x+y≤5,x,y≥0.x+y\le 4,\qquad 2x+y\le 5,\qquad x,y\ge 0.

输入包括约束系数、右端常数、目标系数，以及待核对的原始和对偶候选。输出是候选是否可行、各自目标值和二者差距。变量在本节允许取实数，没有整数要求。

一般形式写为最大化cᵀx，满足Ax≤b、x≥0。设A有m行n列，m是约束条数，n是变量数。向量不等式逐项成立，转置只是交换行列，使Aᵀu按变量汇总各条约束的系数。

选择点(x,y)=(1,3)，两条约束左侧分别为4和5，目标值为9。它证明最优值至少为9；若要证明等于9，还需要约束所有其他可行点的上界。

非负约束权重给出对偶

将第一条约束乘非负权重u，第二条乘非负权重v再相加，得到

(u+2v)x+(u+v)y≤4u+5v.(u+2v)x+(u+v)y\le 4u+5v.

只要u+2v≥3且u+v≥2，结合x,y≥0，就能推出3x+2y≤4u+5v。任何满足这些条件的(u,v)都给出原问题的一个上界。让这个上界尽量小，得到对偶问题：最小化4u+5v，满足u+2v≥3、u+v≥2、u,v≥0。

取(u,v)=(1,1)，上界为9。原始可行点达到9，对偶又证明所有原始可行点不超过9，因此双方同时最优。这个例子也可以直接把原来的两条不等式相加，得到3x+2y≤9；不需要数值优化器才能完成证明。

一般形式的对偶是最小化bᵀu，满足Aᵀu≥c、u≥0。对于任意双方可行的x、u，

cTx≤uTAx≤uTb.c^Tx\le u^TAx\le u^Tb.

第一步使用x≥0和Aᵀu≥c，第二步使用u≥0和Ax≤b。这是弱对偶证明。每个非负条件都有作用，随意允许负乘数会改变不等式方向，不能继续使用这套原对偶形式。

目标相等必须连同可行性检查

在同一个例子里，(x,y)=(3,0)的目标也是9，但第二条约束左侧为6，大于5。它与正确对偶目标相等，却不是合法方案。另一个对偶候选(u,v)=(9/4,0)目标同样为9，但u+2v=9/4小于3，不是合法上界证书。

所以检查器先检查符号与所有不等式，再比较目标。只接收两个相等数字会接受上述错误。可行但不最优也要区分：原点目标0与对偶(1,1)的目标9都合法，只能得出最优值位于[0,9]，不能得出原点最优。

强对偶与互补松弛各自说明什么

有限维线性规划的强对偶定理说明：若一边可行并具有有限最优值，另一边也存在同值最优解。它保证这种等值证书存在。本篇展示的具体证书一旦通过可行性和等值检查，仅靠弱对偶就已经证明最优，不需要再用实验验证强对偶定理。

若原问题可行且无界，对偶不可能可行，否则弱对偶会给出有限上界。但“原问题不可行”不能自动推出“对偶无界”，两边也可能同时不可行。终止状态与数学条件必须分开表述。

对双方可行候选，目标差距可拆成

bTu−cTx=uT(b−Ax)+xT(ATu−c).b^Tu-c^Tx=u^T(b-Ax)+x^T(A^Tu-c).

右侧各项都非负。因此差距为零，当且仅当每一项为零，即u_i(b−Ax)_i=0和x_j(Aᵀu−c)_j=0。这就是互补松弛：某条原始约束若严格有余量，其对偶乘数只能为零；某个原始变量为正，其对应对偶约束必须取等号。

例子中两个原始约束都取等号，两个对偶约束也取等号，四个乘积都为零。这里“等价于最优”的说法始终以双方可行为前提，不能把乘积等于零单独当作万能检查器。

分数最优不能直接交付给整数问题

27篇三角形的最小点覆盖需要2个顶点。若把是否选点的0/1变量改为非负实数，得到最小化x₁+x₂+x₃，约束x₁+x₂≥1、x₂+x₃≥1、x₁+x₃≥1。

三条约束相加得到2(x₁+x₂+x₃)≥3，因而目标至少为3/2。令每个变量等于1/2就达到3/2。该松弛的对偶是分数匹配：为三条边分别赋非负权，每个顶点关联的边权和至多1，最大化边权总和。三条边各取1/2也得到3/2，两边仍然符合LP强对偶。

整数覆盖最优值2与松弛值3/2之间的差距，发生在两个不同的可行域之间。此例的整数／分数比值是4/3，不能把它当作所有图的统一差距结论，也不能称为原LP与其对偶不等值。

把三个1/2都向下取整，会得到不覆盖任何边的零向量；都向上取整，得到3个顶点，虽可行却不是最优。舍入需要自己的可行性与近似保证，求出分数解不会自动解决整数约束。

精确证书检查的范围与成本

教学脚本使用Python标准库Fraction表示上述有理数，避免把容差内相等混同于严格相等。从仓库根目录运行：

1
python3 examples/advanced-algorithms/check_lp_certificates.py

对一个给定稠密m×n系统，核对Ax、Aᵀu、目标和互补积需要O(mn+m+n)次算术操作；只累加每行每列时，除输入外可用O(m+n)空间。精确分数的分子分母位数会影响每次运算成本，因此这个算术计数不是完整的位复杂度界。本篇脚本固定在所列小例子，没有实现一般输入接口，也没有给出寻找最优证书的时间界。

本次实际运行核对一对目标均为9的最优证书、4个互补积、一对可行但非最优候选，并拒绝两对目标相等但一侧不可行的候选。另在有限半整数网格上核对2244对可行候选的弱对偶关系。三角形分数双方值均为3/2，独立枚举8个0/1子集得到整数最优2。真实输出位于examples/advanced-algorithms/results/lp_certificates.json。

网格检查只验证脚本在这些输入上的行为；弱对偶的一般依据是前面的不等式推导。精确算术也不保证建模正确：漏掉一条业务约束时，证书最多证明被实际写下来的数学问题。

练习

  1. 为原问题的可行点(0,4)计算目标与对偶(1,1)之间的差距，再用两组互补积解释差距来自哪里。它是否能通过等值证书检查？
  2. 对三角形分数覆盖，逐项验证分数匹配的对偶约束。说明为何逐项舍入不能作为一般整数最优性证明，并构造一个“目标相等但不可行”的错误证书。

参考资料