运筹学对偶问题ppt课件.ppt

第四章对偶问题一、对偶问题的一般形式则以下线性规划问题：如果采用向量、矩阵来表示可以将以上关系列成以下对偶表：例解：∴对偶规划问题为比较两个条件：例对称化则，原问题变为则（A’）的对偶问题如下：对比结果调整令y1=y1’，y2=-y2’，y3=y4’-y3’则得到以下对偶问题合并比较原问题与对偶问题的相应关系例：写出下列问题的对偶形式：解：例：写出下列问题的对偶问题解：二、对偶问题的经济意义：例：某产品计划问题的线性规划数学模型为分析分析分析这样，就得到另一个线性规划模型：比较第二节对偶理论定理1（对称性定理）定理2（弱对偶定理）定理3（最优性定理）定理4（无界性定理）以上三个定理可以这样记忆定理5（强对偶定理）定理6（存在性定理）第三节对偶单纯形法例解：minmax观察A矩阵解步骤1步骤2步骤3：换基迭代（2）计算θj：（3）找主元列（4）找主元素（5）迭代计算结果找主元行、确定调出变量、计算zj-cj计算θj、确定调入变量继续换基迭代：继续换基迭代：继续换基迭代：得到最优解：五、对偶单纯形法的求解思路：检验数也可以用向量形式写出：

（这里只写出非基变量的检验数向量）
从可以很容易得推出，这说明原问题的最优基正是对偶问题的可行基。换言之，当原问题的基B即是原问题的可行基又是对偶问题的可行基时，B就是最优基。因此，单纯性法求解过程正是在保持原始可行（解答列基变量取值均非负）的条件下，通过迭代逐步实现对偶可行性。在对偶关系中，由于价值系数C和约束条件右端常数系数b互换位置，因此可以设想，能否在保持检验数Cj-Zj非正的条件下，逐步消除基本解中的负分量，使之成为可行解。这样，该基本解就是基本最优解。
对偶单纯形法正是基于这种思想而产生的，其基本思想就是在保持对偶可行性的条件下，通过逐步迭代实现原始可行性。所以，对偶单纯形法的使用条件是：
①b列中至少有一个bi<0；
②原问题A的检验数Cj-Zj≤0；