【摘要】：在以下的讨论中，假设线性规划原问题和对偶问题分别如式（2-5）和（2-6）所示，则原问题和对偶问题之间存在如下基本性质。这一性质说明互为对偶的线性规划问题，求极大值的线性规划的任意目标值都不会大于求极小值的线性规划的任意目标值。当原问题无可行解时，其对偶问题（原问题）或具有无界解或者无可行解。例如，下列一组问题两者都无可行解。
在以下的讨论中，假设线性规划原问题和对偶问题分别如式（2-5）和（2-6）所示，则原问题和对偶问题之间存在如下基本性质。
性质2-1对称性 对偶问题的对偶是原问题。
证明：设原问题是
根据对偶问题的对称变换关系，可得到它的对偶问题
它与下列线性规划问题等价
再根据对称变换关系写出它的对偶问题
它与下列线性规划问题等价
这一性质说明互为对偶的线性规划问题，求极大值的线性规划的任意目标值都不会大于求极小值的线性规划的任意目标值。原问题的任一可行解的目标值是对偶问题最优值的下界，对偶问题的任一可行解的目标值是原问题的最优值的上界。
性质2-3无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。
证明：由弱对偶性显然可以得到无界性这个性质。
这个问题的性质不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或者无可行解。例如，下列一组问题两者都无可行解。
性质2-4最优性 若X*是原问题的可行解，Y*是对偶问题的可行解，当CX* =Y*b时，X* 、Y*是最优解。
利用上述关系，可建立对偶问题的约束线性方程组，方程组的解即为最优解。
例2-3已知线性规划
解：对偶问题是
因为x1 ≠ 0 ，x2 ≠ 0，故所以对偶问题的第一、二个约束的松弛变量等于零，即
例2-4已知线性规划
解：对偶问题是
性质2-7设原问题是
它的对偶问题是
则原问题单纯形表的检验数行对应其对偶问题的一个基本解，其对应关系见表2-5。
表 2-5
例2-5已知线性规划
（1）用单纯形法求最优解；
（2）求出每步迭代对应对偶问题的基本解；
（3）从最优表中写出对偶问题的最优解；
表 2-6
续表 2-6
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
