线性规划对偶

对偶变量可以理解为给原约束定价：任何不超过原变量成本的合法价格组合，都形成原最小化问题的下界。强对偶说明在有限最优情形下，这套线性价格能够紧贴原目标；互补松弛进一步指出，只有紧约束和正变量会在最优证书中彼此承载。

顶点覆盖的对偶图像 ​

对非负顶点权重 $w_v\ge 0$，加权顶点覆盖的 LP 松弛为

其对偶给每条边一个非负变量 $y_e$：

原始变量表示是否购买顶点，对偶变量把预算装入边；每个顶点承受的相邻边总价不能超过其权重。任何合法装价都给出整数顶点覆盖成本的下界，因为整数可行域包含在 LP 松弛中。原始—对偶方法公理库原始—对偶方法Primal-dual method联合构造原始方案与对偶界，并通过可行性及计费关系证明最优或近似保证的算法框架。会提高这些边价直到顶点约束变紧，再据此构造覆盖；Dual Fitting公理库Dual Fittingdual fitting · 对偶拟合法从算法收费构造可能不可行的对偶解，再统一缩放为可行下界证书。则允许装价暂时超出容量，事后以统一因子缩放成可行证书。

边界与辨析 ​

LP 强对偶只连接连续松弛的两侧。若原问题要求 $x$ 取整数，对偶最优值仍只是松弛界；整数最优值与 LP 值之间可能存在整数性间隙公理库整数性间隙Integrality gap衡量整数最优值与其松弛最优值在最坏实例上的比值。。因此“原、对偶目标相等”能证明 LP 最优，不能自动证明某个取整方案最优。

全对偶整数性公理库全对偶整数性Total dual integrality · TDI要求每个整数目标都有整数的最优对偶证书，说明这一性质为何依赖不等式表示，以及整数右端如何传递原问题整数性。追加的是一个更具体的条件：每个整数目标在有限最优时都有整数对偶最优乘子。当右端也为整数，这些乘子使支持值成为整数，并推出原多面体的整数性。该条件属于所写的不等式系统，同一行约束缩放后可能失去它。

若原问题无界，则对偶必不可行；但原问题不可行时，对偶可能不可行，也可能无界，单看一侧状态不能任意反推另一侧。数值求解器报告的近似可行解还要把约束残差计入上下界，不能把一个很小的目标差单独当成精确证书。

拉格朗日对偶公理库拉格朗日对偶Lagrange duality通过拉格朗日函数构造原问题下界的对偶问题，并研究弱对偶、强对偶与最优性条件。可以从更一般的约束优化问题构造对偶函数，在线性情形会导出这里的 LP 对偶。组合优化中的原始—对偶与 dual fitting 以线性可行性、弱对偶和互补松弛构造成本证书。

锥规划的对偶与证书公理库锥规划的对偶与证书Conic programming certificates · Conic duality用对偶锥统一最优性与不可行性证书，并以二阶半正定规划区分零间隙、最优值可达和弱不可行。保留这里的弱对偶核验方式，但半正定锥的线性像可能不闭，因而会出现残差趋零却没有可行解、也没有普通严格不可行性证书的情形。

矩阵博弈极小极大定理公理库矩阵博弈极小极大定理Matrix game minimax theorem · Von Neumann minimax theorem · 有限零和博弈极小极大定理有限二人零和博弈允许独立混合后，行玩家的最大保证收益等于列玩家的最小收益上界，并由一对线性规划提供精确证书。把行玩家的最大保证与列玩家的最小上界写成一对 LP。两侧的概率归一化等式与自由价值变量互相对应；核验两份策略可行且界相等，就得到博弈价值的双侧证书。

弱对偶提供近似算法、网络流和组合优化中可核验的上下界，互补松弛则指导 primal–dual 构造与最优性检查。对整数问题，若一个整数可行解的值恰好等于某个 LP 对偶可行解的值，同一弱对偶链也直接证明整数最优。存在整数性间隙时，两界无法这样相遇；此时可借助舍入、dual fitting 或额外的组合结构控制损失。

分数团覆盖公理库分数团覆盖的零错误容量上界Fractional clique cover bound给混淆图的团赋覆盖权重，利用独立集每团至多一点和乘积团证书上界全部块长，并用原对偶精确计算C5的5/2。给出一个无需舍入的通信上界证书：团权重覆盖每个顶点，对偶给顶点赋质量并限制每个团总量。五边形两侧各取半权，目标都为 $5/2$，证明LP最优；再构造乘积团，才能把这份一次证书推广到任意块长的零错误码。

Kantorovich 对偶公理库Kantorovich 对偶性Kantorovich duality用满足两侧势之和不超过成本的对偶函数，构造可核验的输运最优性证书。把边缘约束的乘子解释成源侧与目标侧势，要求两势之和不超过每条路线的成本。可行计划和势若目标值相同，就给出无需枚举计划的输运最优性证书。