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

《(运筹学大作业)单纯性法与对偶单纯性法的比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、对偶单纯形法与单纯形法对比分析1．教学目标：通过对偶单纯形法的学习，加深对对偶问题的理解2．教学内容：1）对偶单纯形法的思想来源2）对偶单纯形法原理3．教学进程：1）讲述对偶单纯形法解法的来源：所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。2）为什么要引入对偶单纯形法：单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效率，因为它具有以下优点：（1）初始基解可以是非可行解,当检验数都为

2、负值时,就可以进行基的变换,不需加入人工变量,从而简化计算；（2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。据此可知，用单纯形法求解线性规划问题时

3、，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。我们知道，单纯形法计算的基本思路是保持原问题为可行解（这时一般其对偶问题为非可行解）的基础上，通过迭代，增大目标函数，当其对偶问题的解也为可行解时，就达到了目标函数的最优值。那么对偶单纯形法的基本思想可以理解为保持对偶问题为可行解（这时一般原问题为非可行解）的基础上，通过迭代，减小目标函数，当原问题也达到可行解时，即达到了目标函数的最优值。其实对偶单纯形法本质上就是单纯形法,只不过在运用时需要将单纯形表旋转一下而已

4、。一.单纯形法和对偶单纯性法单纯形法是求解线性规划的主要方法,单纯形表则是单纯形法和对偶单纯形法的运算工具。设线性规划问题为Max⑴将其化为标准形式，得MaxZ=s.t.⑵其中，，，，则其对应的线性约束转换为，，代入目标函数得，相应的一个基解为，，。显然，若，且，，则基解为该线性规划的最优解,此时检验数均大于零,见表1。通过上面的分析,我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个(加一个负号)基解。那么表中b列的数字仅仅表示的是的取值吗?我们可以猜想很可能是对偶问

5、题的检验数。这里首先给出问题(1)的对偶问题的一般形式Mins.t.⑶将问题（3）化为标准形式，得Mins.t.⑷由，，为松弛变量，相应分解为、，其中，。得：⑸⑹由式⑸得到⑺通过令，由式(5)得对偶问题的基解,代入式(6)得,将式(7)对偶问题的目标函数得。显然若目标函数达到最小,非基变量的价值系数要求大于等于零,单纯形表b列,即实际上是对偶问题的非基变量检验数。二．对偶单纯形法的算法步骤(1)确定换出基的变量设原问题为（1），对偶问题为（3）。由，不等式则可分解为(8)进一步添加松弛变量有等式（5）、（6），对等式（5）两端同

6、时左乘有(9)将移至等式右端得(10)由不等式（8）得(11)(12)将式（10）代入不等式（11）、（12）得(13)(14)将（13）、（14）合并得(15)整理得(16)其中是单纯形表中X变量的检验数,记，(j=1,2,....,n),矩阵，显然，若Y为基可行解，而若，则对偶问题的目标函数未取得最小值，取，确定单纯形表的换出基变量，即（在单纯形表中的）对偶问题相应的换入基变量，令其余分量为零，即，可能取大，使对偶问题的目标函数值下降，由Y为基可行解，则要求满足式（16），即对于任意的j，均有，得，从而确定单纯形表中换入基变

7、量，同时确定对偶问题（在单纯形表中）换出基变量。这与单纯形法确定换出基变量的规则是完全一样的。3）例题讲解下面举例说明对偶单纯形法的算法步骤：【例题】用对偶单纯形法求解线性规划问题：min解：1）将问题改写为：2）算法步骤第一步：建立一个初始单纯形表，使表中检验行的值全部大于或等于零，即对其对偶问题而言是一基本可行解。约束条件两端乘-1，得：根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字相当于对偶问题解的非基变量的检验数。第二步：由于对偶问题的求解是使目标函数达到最小值，所以最优判别准则是当所有检验数大于或等于

8、零时为最优（也即这时原问题是可行解）。如果不满足这个条件，找出绝对值最大的负检验数，设为，其对应的原问题的基变量即为对偶问题的换入变量。第三步：将行数字与表中第行对应的数字对比，令，即为主元素，为对偶问题的换出变量。第四步：用换入变量替换对偶问题中的换出变量（在