对偶单纯形法VIP免费

对偶单纯形法：利用对偶理论得到的一个求解线性规划问题的方法对偶单纯形法是根据对偶问题求解的特点和对称性设计出的一种解法。在单纯形法迭代时，在b列中得到的是原问题的基可行解，而在检验数得到的是对偶问题的基解，通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，已得到最优解，即原问题与对偶问题都是最优解。根据对偶问题的对称性：若保持对偶问题的解是基可行解，即cj-CBB-1Pj≤0,而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。0XbAXCXZmax010bBX)(基本解X（0）为基本可行解的条件？B-1b≥0X（0）为最优解的条件？01ABCCB原原问题最优解条件令Y=CBB-1，代入原问题最优解条件，→YA≥C无符号限制YCYAYbminmPPPB21取基对偶单纯形法的基本思路：保证对偶问题的可行性，逐步改进原问题的可行性，求解原问题。0,11bBX取基本解010，）得到最优解为（bBXP时且01bB，当01ABCCB）的最优解为（且由对偶理论知，DBCYB10的方向迭代，向01bB）的可行解的前提下，是（即DBCYB1001ABCCB在保证）同时得到可行解时）和（即（DP对偶单纯形法的基本思路：）的可行解方向迭代即向（P2.确定出基变量按,对应的基变量xl为出基变量。liibBbBbB1110min对偶单纯形法步骤：1.列出初始单纯形表，检查b列的数字若都为非负，则已得到最优解，停止计算，若b列的数字中至少有一个负分量，转第二步。3.确定入基变量在单纯形表中检查xl所在行的各系数alj(j=1,2,…,n),若所有alj≥0，则无可行解，停止计算，若存在alj<0，计算rkkkrjrjjjazcaazc0min按规则所对应的列的非基变量xk为入基变量，保证得到的新基解所对应的对偶问题的解仍为可行解。4.以alk为主元素，进行迭代运算，得到新基解的单纯形表，重复1—4的步骤，直至b列中所有元素均为非负数为止。【例2--5】用对偶单纯形法求解3,2,1043232432min321321321jxxxxxxxxxxj解:化成下列模型5,,1043232432max53214321321jxxxxxxxxxxxxzj以x4,x5为基变量可得问题的一基解,其单纯形表下：cj-2-3-400CBXBbx1x2x3x4x500x4x5-3-4-1-2-110-21-301σj-2-3-400原问题符合解的最优性条件.先选出基变量后选进基变量134,22mincj-2-3-400CBXBbx1x2x3x4x50-2x4x1-120-5/21/21-1/21-1/23/20-1/2σj0-4-10-158211,254min但不可行.cj-2-3-400CBXBbx1x2x3x4x5-3-2x2x12/511/501-1/5-2/51/5107/5-1/5-2/5σj00-9/5-8/5-1/5最优解X*=(11/5,2/5,0,0,0)TZ*=28/5cj-2-3-400CBXBbx1x2x3x4x50-2x4x1-120-5/21/21-1/21-1/23/20-1/2σj0-4-10-1单纯形法（原始单纯形法）的两个条件：1、问题为标准型2、有初始基本可行解0,3263433.2min2121212121xxxxxxxxtsxxZ求0,,,,3263433.2max5432152142132121xxxxxxxxxxxxxxtsxxZ标准型为0,,,,3263433.2max5432152174216321762176xxxxxxxxxxxxxxxxtsMxMxxxZxx，引进人工变量用单纯形法求解对偶单纯形法的优点：对偶单纯形法的优点：1、不需要人工变量；2、当变量多于约束时，用对偶单纯形法可减少迭代次数；3、在灵敏度分析中，有时需要用对偶单纯形法处理简化。注意：对偶单纯形法仅限于初始基B对应的标准形式中目标函数的系数（检验数）均≤0的情形。nnxcxcxcz2211min:形如mnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111.0,,21nxxxnnxcxcxcz2211max:标准型mmnnmnmmnnnnnnbxxaxaxabxxaxaxabxxaxaxats2211222222121111212111.),,2,1(0njcj若可用对偶单纯形法...