对偶单纯形法

《对偶单纯形法》由会员分享，可在线阅读，更多相关《对偶单纯形法（16页珍藏版）》请在金锄头文库上搜索。

对偶单纯形法：利用对偶理论得到的一个求解线性规划问题的方法对偶单纯形法是根据对偶问题求解的特点和对称 性设计出的一种解法。在单纯形法迭代时，在b 列中得到的是原问题的 基可行解，而在检验数得到的是对偶问题的基解，通 过逐步迭代，当在检验数行得到对偶问题的解也是基 可行解时，已得到最优解，即原问题与对偶问题都是 最优解。根据对偶问题的对称性：若保持对偶问题的解是 基可行解，即cj-CBB-1Pj0,而原问题在非可行解的基 础上，通过逐步迭代达到基可行解，这样也得到了最 优解。基本解X（0）为基本可行 解的条件？B-1b0X（0）为最优解的 条件？原原问题最优解条件令Y=CBB-1，代入原问题最优解条件，YAC对偶单纯形法的基本思路：保证对偶问题的可行性，逐 步改进原问题的可行性，求 解原问题。 对偶单纯形法的基本思路：2. 确定出基变量按 ,对应的基变量xl为出 基变量。对偶单纯形法步骤：1. 列出初始单纯形表，检查b 列的数字若都为非负， 则已得到最优解，停止计算，若b列的数字中至少 有一个负分量，转第二步。3. 确定入基变量在单纯形表中检查xl所在行的各系数alj(j=1,2, ,n),若 所有alj 0，则无可行解，停止计算，若存在alj 0不可行单纯形法对偶单纯形法？大M法：两阶段法单纯形法单纯形法