,并且目标函数各项系数都不小于零。所以在转化成标准型后各项系数不大于零,从而以松弛变量为基列出的单纯形表满足检验数都不大于零,是其对偶问题的一个可行解。如果原问题的标准形式中各项系数不都小于零,则不容易找到对偶问题的一个初始可行解,就不适合使用对偶单纯形法求解。所以对偶单纯形法适用于不易找到原方程的可行解而容易找到其对偶问题的可行解的线性规划问题。 2. 我们知道,约束方程的数量对单纯形法的计算过程要远远大于变量个数的影响。如果 m>n , 那么对偶问题有 n 个约束方程, 而原问题有 m 个约束方程,所以对偶问题有更少的约束方程数量,那么通过对偶单纯形法的运用比起直接只用单纯形法将会显著的减少计算量。 3. 弱对偶性和强对偶性是对偶理论的关键原理。对偶问题可以用来对原问题的计划方案进行评价。我们可以用一个对偶问题的可行解和目前原问题的计划方案进行比较,如果两个目标函数值相等或比较接近,则可以说明原问题的计划方案已经是可以看做最优了。 4. 对偶理论在灵敏度分析和影子价格计算中有着重要的作用。七、单纯形法和对偶单纯形法的基本思想比较通过以上的分析可知, 对偶单纯形法其实相当于单纯形法的一种变形, 8 只不过在运用对偶单纯形法解线性规划时需要将单纯形表旋转一下。单纯形表中的 b 列实际上是对偶问题的非基变量的检验数, 而原单纯形表的检验数为对偶问题的基解, 这样可以理解为通过旋转 90 ° 运用单纯形法求解线性规划。从求解思路上来说,单纯形法是首先保证基解是原问题的基可行解( bi 不小于零), 然后通过变量的换入换出增大目标函数值, 直到其同时成为对偶问题的可行解,根据强对偶性原理,可知这个解就是最优解。而对偶单纯形法则是首先保证基解是对偶问题的可行解( 检验数都不大于零), 然后逐步减小对偶标准化的目标函数值, 使其成为原问题的可行解。两种方法殊途同归, 其本质是一样的。
全文预览
