对偶单纯形法.ppt

对偶单纯形法：利用对偶理论得到的一个 求解线性规划问题的方法 对偶单纯形法是根据对偶问题求解的特点和对称对偶单纯形法是根据对偶问题求解的特点和对称性设计出的一种解法性设计出的一种解法 在单纯形法迭代时，在在单纯形法迭代时，在b 列中得到的是原问题的列中得到的是原问题的基可行解，而在检验数得到的是对偶问题的基解，通基可行解，而在检验数得到的是对偶问题的基解，通过逐步迭代，当在检验数行得到对偶问题的解也是基过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，已得到最优解，即原问题与对偶问题都是可行解时，已得到最优解，即原问题与对偶问题都是最优解 根据对偶问题的对称性：若保持对偶问题的解是根据对偶问题的对称性：若保持对偶问题的解是基可行解，即基可行解，即cj-CBB-1Pj≤0,而原问题在非可行解的基而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最础上，通过逐步迭代达到基可行解，这样也得到了最优解基本解基本解X（（0））为基本可行为基本可行解的条件？解的条件？B-1b≥0X（（0））为为最优解的最优解的条件？条件？原原原问题最优解条件原问题最优解条件令令Y=CBB-1，，代入原问题最优解条件，代入原问题最优解条件，→YA≥C对偶单纯形法的基本思路：保证对偶问题的可行性，逐保证对偶问题的可行性，逐步改进原问题的可行性，求步改进原问题的可行性，求解原问题。

解原问题 对偶单纯形法的基本思路：2. 确定出基变量确定出基变量 按按 ,对应的基变量对应的基变量xl为为出基变量出基变量对偶单纯形法步骤：对偶单纯形法步骤：1.列出初始单纯形表，检查列出初始单纯形表，检查b 列的数字若都为非负，列的数字若都为非负，则已得到最优解，停止计算，若则已得到最优解，停止计算，若b列的数字中至少列的数字中至少有一个负分量，转第二步有一个负分量，转第二步3.确定入基变量确定入基变量4. 在单纯形表中检查在单纯形表中检查xl所在行的各系数所在行的各系数alj(j=1,2, …,n),若所有若所有alj ≥0，则无可行解，停止计算，若存在，则无可行解，停止计算，若存在alj <0，计算，计算按按  规则所对应的列的非基变量规则所对应的列的非基变量xk为入基变量，保证为入基变量，保证得到的新基解所对应的对偶问题的解仍为可行解得到的新基解所对应的对偶问题的解仍为可行解4.以以 alk为主元素，进行迭代运算，得到新基解的单为主元素，进行迭代运算，得到新基解的单5. 纯形表，重复纯形表，重复1—4的步骤，直至的步骤，直至b 列中所有元素均列中所有元素均为非负数为止。

为非负数为止例例2--5】】用对偶单纯形法求解用对偶单纯形法求解解解:化成下列模型化成下列模型以以x4,x5为基变量可得问题的一基解为基变量可得问题的一基解,其单纯形表下：其单纯形表下：cj-2 -3 -4 0 0CBXBb x1 x2 x3 x4 x5 00x4x5-3-4-1 -2 -1 1 0-2 1 -3 0 1 σj-2 -3 -4 0 0原问题符合原问题符合解的最优性解的最优性条件条件.先先选出基变量选出基变量后选进基变量后选进基变量cj-2 -3 -4 0 0CBXBb x1 x2 x3 x4 x5 0-2x4x1-120 -5/2 1/2 1 -1/21 -1/2 3/2 0 -1/2 σj0 -4 -1 0 -1但不可行但不可行.cj-2 -3 -4 0 0CBXBb x1 x2 x3 x4 x5 -3-2x2x12/511/5 0 1 -1/5 -2/5 1/5 1 0 7/5 -1/5 -2/5 σj0 0 -9/5 -8/5 -1/5最优解最优解X*=(11/5,2/5,0,0,0)TZ*=28/5cj-2 -3 -4 0 0CBXBb x1 x2 x3 x4 x5 0-2x4x1-120 -5/2 1/2 1 -1/21 -1/2 3/2 0 -1/2 σj0 -4 -1 0 -1单纯形法（原始单纯形法）的两个条件：1、问题为标准型2、有初始基本可行解用单纯形法求解对偶单纯形法的优点：对偶单纯形法的优点：1、不需要人工变量；、不需要人工变量；2、当变量多于约束时，用对偶单、当变量多于约束时，用对偶单纯形法可减少迭代次数；纯形法可减少迭代次数；3、在灵敏度分析中，有时需要用对、在灵敏度分析中，有时需要用对偶单纯形法处理简化。

偶单纯形法处理简化注意：对偶单纯形法仅限于初始基B对应 的标准形式中目标函数的系数（检 验数）均≤0的情形可用对偶单纯形法如何用？求解线性规划问题的方法与步骤：1、 把原问题化为标准型2、找初始基，转第3步，转第4步3、对问题的约束条件关于基B求基解，用单纯形法，对偶单纯形法，转第4步4、增加人工变量，用大M法或两阶段法求解对应B1的基本解：可用对偶单纯形法求解检验数全部≤0不可行对应B2的基本解用单纯形法求解可行对应B的基本解：存在检验数>0不可行单纯形法×对偶单纯形法？×大M法：两阶段法单纯形法单纯形法。