(运筹学大作业)单纯性法与对偶单纯性法比较

wordword⑺通过令，由式(5)得对偶问题的基解,代入式(6)得,将式(7)对偶问题的目标函数得。显然假如目标函数达到最小,非基变量的价值系数要求大于等于零,单纯形表b列,即实际上是对偶问题的非基变量检验数。二．对偶单纯形法的算法步骤(1)确定换出基的变量设原问题为〔1〕，对偶问题为〔3〕。由，不等式如此可分解为(8)进一步添加松弛变量有等式〔5〕、〔6〕，对等式〔5〕两端同时左乘有(9)将移至等式右端得(10)由不等式〔8〕得(11)(12)将式〔10〕代入不等式〔11〕、〔12〕得(13)(14)将〔13〕、〔14〕合并得(15)整理得(16)其中是单纯形表中X变量的检验数,记，(j=1,2,,n),矩阵，显然，假如Y为基可行解，而假如，如此对偶问题的目标函数未取得最小值，取，确定单纯形表的换出基变量，即〔在单纯形表中的〕对偶问题相应的换入基变量，令其余分量为零，即，可能取大，使对偶问题的目标函数值下降，由Y为基可行解，如此要求满足式〔16〕，即对于任意的j，均有，得，从而确定单纯形表中换入基变量，同时确定对偶问题〔在单纯形表中〕换出基变量。这与单纯形法确定换出基变量的规如此是完全一样的。3〕例题讲解下面举例说明对偶单纯形法的算法步骤：【例题】用对偶单纯形法求解线性规划问题：min解：1〕将问题改写为：算法步骤第一步：建立一个初始单纯形表，使表中检验行的值全部大于或等于零，即对其对偶问题而言是一根本可行解。约束条件两端乘-1，得：根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字相当于对偶问题解的非基变量的检验数。第二步：由于对偶问题的求解是使目标函数达到最小值，所以最优判别准如此是当所有检验数大于或等于零时为最优〔也即这时原问题是可行解〕。如果不满足这个条件，找出绝对值最大的负检验数，设为，其对应的原问题的基变量即为对偶问题的换入变量。第三步：将行数字与表中第行对应的数字比照，令，即为主元素，为对偶问题的换出变量。第四步：用换入变量替换对偶问题中的换出变量〔在单纯形表中反映为用替原问题的基变量〕，得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持根本可行解，原问题基变量列数字列数字相当于对偶问题的检验数。据此可以完成对这个对偶问题的求解。总结。比照单纯形法&对偶单纯形法单纯性法根本思想对偶单纯形法优点这里我们需要对单纯形法和对偶单纯形法做一个详细的比照：1，单纯形法中的b对应于对偶单纯形法中的；2，单纯形法中的作为检验数，对偶单纯形法中的b作为检验数；3，单纯形法中的，对偶单纯形法中的；4，单纯形法中当时得到最优解，对偶单纯形法中当时得到最优解；5，单纯形法的可行解为，对偶单纯形法的可行解为；〔由于松弛变量对应的检验数为，由于与对应，又由于，可得〕。对于单纯形法和对偶单纯形法，我们建立了使用单纯形法解决线性规划问题的依据：1，表中有单位矩阵，当时用单纯形法；2，表中有单位矩阵，当时用单纯形法；3，两者都不满足时，使用人工变量法或两阶段法。接下来需要说明在哪些场合下使用对偶单纯形法解决线性规划问题较为便捷，我将通过下面的例子来说明：min令，如此问题可变为max取为初始基，易见所有检验数，从而建立单纯形表，计算结果如下：本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用对偶单纯形法求解：①问题标准化后，价值系数全非正；②所有约束全是不等式。总结上面的分析过程可知，对偶单纯形法本质上就是单纯形法,只不过在运用对偶单纯形法解线性规划时需要将单