形式陈述

原始—对偶方法同时维护原问题与对偶问题的部分可行解，并利用弱对偶与互补松弛逐步缩小对偶间隙。在线性规划中，若原始和对偶均可行且目标相等，则两者都最优。组合算法常把违反互补条件的边或约束作为下一步更新对象；具体更新必须保持所需可行性不变量。

直觉

原始解给出可实现方案，对偶解给出任何方案都不能突破的界；两者相遇时就得到可验证的最优性。

例子与边界

匈牙利算法维护顶点势与紧边匹配；最短路和最小费用流也可用势函数解释。仅写出一个对偶变量并不构成算法，必须说明如何更新和为何终止。对整数规划，线性对偶相等通常只证明松弛最优，不能自动证明整数解最优。

推论与应用

该框架统一匹配、覆盖、流和近似算法，常能同时产生解、下界和近似比证明。

参考资料

• Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th ed., Springer, 2018，Chs. 4–11。
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。