线性规划中的对偶性

线性规划（LP）是一种在要求由线性关系表示的数学模型中获得最佳结果的方法。这是一种用于优化的技术，目标是在一组线性约束下最小化或最大化线性目标函数。线性规划的一个重要方面是对偶性的概念，它提供了对优化函数行为的深入洞察。

对偶主义的基本原理

在线性规划中，对于每个优化问题，都会存在一个相应的对偶问题。如果原始问题称为'原问题'，则其对应的称为'对偶问题'。对偶性提供了一种强有力的观点——通过检查另一个问题的解决方案可以找到一个问题的最优解。

关于线性规划中的对偶性，有两条主要结论：

• 弱对偶性：在任何可行解下，对偶性的目标函数值总是大于或等于原始目标函数在任何可行解下的值。
• 强对偶性：如果原问题和对偶问题都有最优解，那么原问题的目标函数的最优值等于对偶问题的目标函数的最优值。

原问题和对偶问题

原问题

最大化：c 1 x 1 + c 2 x 2 + ... + c n x n
约束条件：a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1
             a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2
             ,
             a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m

             x 1 , x 2 , ..., x n ≥ 0

对偶问题

最小化：b 1 y 1 + b 2 y 2 + ... + b m y m
约束条件：a 11 y 1 + a 21 y 2 + ... + a m1 y m ≥ c 1
             a 12 y 1 + a 22 y 2 + ... + a m2 y m ≥ c 2
             ,
             a 1n y 1 + a 2n y 2 + ... + a mn y m ≥ c n

             y 1 , y 2 , ..., y m ≥ 0

解释和经济意义

在原问题中，目标是在满足资源限制所施加的约束条件的同时，确定可以获得的最大收益（或利润）。每个决策变量代表一个可能的活动或策略，约束条件代表这些活动所需资源的限制。

另一方面，对偶性问题则寻求满足或超过期望总利润所需的最低成本。在这里，决策变量可以解释为影子价格——最小化原始优化问题中每个约束条件的价格。对偶性提供了一种平衡的价格体系。

几何解释

考虑一个二维空间以便于可视化。对于原问题和对偶问题，解决方案位于其可行区域的顶点（角落）。相应的原问题和对偶不等式定义了几何区域，其交点可能同时包含原问题和对偶问题的最优解。

互补松弛原理

连接原问题和对偶问题表述的一个核心组成部分是互补松弛的概念。它由在原问题及其对偶有最优解时必须满足的条件组成。对于每一对原问题和对偶问题的约束条件，必须满足互补松弛条件：

如果 x j > 0，则第 j 对偶条件是严格的；
如果二元约束条件 i 被放松，则 第 i 个 基本变量为零。

因此，如果在原问题中任何约束条件被放松，则对偶中的对应变量在最优解时必须有零值，反之亦然。

对偶性示例

示例基本问题

最大化 z = 2x 1 + 3x 2
约束条件
             x 1 + 2x 2 ≤ 10
             2x 1 + x 2 ≤ 8
             x 1 , x 2 ≥ 0

相容对偶问题

最小化 w = 10y 1 + 8y 2
约束条件
             y 1 + 2y 2 ≥ 2
             2y 1 + y 2 ≥ 3
             y 1 , y 2 ≥ 0

应用和意义

对偶性的概念不仅是理论性的，而且具有重要的实际意义。它允许我们从另一个可能更简单的问题的解决方案中推导出一个问题的解决方案。对偶性在经济学、工程学、军事科学以及运输领域中均有应用。

例如，在经济学中，对偶问题提供了有关价格优化和资源分配的信息。对偶解表明应为额外资源付出什么样的价值，为决策者提供有价值的定价信息。

结论

线性规划中的对偶性弥合了不同优化方法之间的差距，让人深入理解并提高解决复杂问题的效率。无论是出于学术兴趣还是实际解决方案，理解对偶性概念对于充分利用线性规划技术都是重要的。

评论