线性规划的对偶问题和灵敏度分析

对偶理论是线性规划理论的发展和深化，也是线性规划的一个特性。它使线性规划理论更加丰富，应用领域更加广泛。对于任何求极大值的线性规划问题，都有一个与之对应的求极小值问题，其有关约束条件的系数矩阵具有相同的数据，但形式上互为转置，且目标函数与约束方程右端常数项互换，目标函数值相等。这就是线性规划的对偶问题。

可用一个简单例子来说明，例如，四边形的周长L一定，什么样形状的四边形面积最大?答案是正方形面积最大。其对偶问题为，四边形面积一定，什么样的四边形周长最短?答案仍然是四边形。可见前一问题的约束条件，即为后一问题的目标函数，反之亦然。

线性规划问题中，均假定各系数a_i，j，b_i，c_j是确定的常数，实际上这些系数往往不可能很精确，而且随着客观条件变化而改变。例如地下水资源管理中，当水位、水量或水质等约束条件改变时，b_i也随之改变；当市场情况或供求关系发生变化时，c_j也会改变；而开采工艺或水文地质条件的改变，同样也可引起a_i，j的改变。因此，规划者需要知道，某些系数改变后，现行的最优解是否改变?或者说，这些系数在多大范围内变化，其规划问题的最优解不变?以及当最优解发生变化时，如何用最简便的方法找出新的最优解?这些就是灵敏度分析所要研究和回答的问题。

对偶原理是进行灵敏度分析的理论依据。灵敏度分析的内容，应包括系数c_j、b_i、a_i，j变化及新增加变量和新增加约束条件对最优解的影响。但对地下水资源管理而言，主要分析c_j和b_i变化。

由于线性规划原问题与对偶问题之间互为对偶，所以，求极大值原问题的最优状况，等价于对偶问题的可行状况；而原问题的可行状况，就是对偶问题最优状况的负值。

从对偶特性可知，对c_j和b_i进行灵敏度分析的两条重要依据：①只要满足原问题的最优状况或对偶问题的可行状况，其最优解不变。以此可分析c_j变化对最优解的影响。②只要原问题保持可行状况或对偶问题最优状况，其最优解不变，以此可分析b_i变化对最优解的影响^{［105～106］}。