《运筹学大作业单纯性法与对偶单纯性法的比较.docVIP

对偶单纯形法与单纯形法对比分析 1．教学目标： 通过对偶单纯形法的学习，加深对对偶问题的理解 教学内容： 对偶单纯形法的思想来源 对偶单纯形法原理 教学进程： 讲述对偶单纯形法解法的来源： 所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基提出（1）（2Max ⑴ 将其化为标准形式，得 Max Z= s.t. ⑵ 其中，，，，则其对应的线性约束转换为，，代入目标函数得，相应的一个基解为，，。显然，若，且，，则基解为该线性规划的最优解, 此时检验数均大于零, 见表1。 通过上面的分析, 我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个( 加一个负号) 基解。那么表中b列的数字仅仅表示的是的取值吗? 我们可以猜想 很可能是对偶问题的检验数。这里首先给出问题(1) 的对偶问题的一般形式 Min s.t. ⑶ 将问题（3）化为标准形式，得 Min s.t. ⑷ 由，，为松弛变量，相应分解为、，其中，。得： ⑸ ⑹ 由式⑸得到 ⑺ 通过令，由式(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，得： 根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字 相当于对偶问题解的非基变量的检验数。 第二步：由于对偶问题的求解是使目标函数达到最小值，所以最优判别准则是 当所有检验数大于或等于零