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

(运筹学大作业)单纯性法与对偶单纯性法的比较由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“全运筹学单纯性法”。

对偶单纯形法与单纯形法对比分析

1．教学目标：

通过对偶单纯形法的学习，加深对对偶问题的理解

2．教学内容：

1）对偶单纯形法的思想来源 2）对偶单纯形法原理

3．教学进程：

1）讲述对偶单纯形法解法的来源：

所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。

2）为什么要引入对偶单纯形法：

单纯形法是解线性规划的主要方法，对偶单纯形法则提高了求解线性规划问题的效率，因为它具有以下优点：

（1）初始基解可以是非可行解, 当检验数都为负值时, 就可以进行基的变换, 不需加入人工变量, 从而简化计算；

（2）对于变量多于约束条件的线性规划问题,用对偶单纯形法可以减少计算量,在灵敏度分析及求解整数规划的割平面法中,有时适宜用对偶规划单纯形法。

由对偶问题的基本性质可以知道，线性规划的原问题及其对偶问题之间存在一组互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w。据此可知，用单纯形法求解线性规划问题时，在得到原问题的一个基可行解的同时，在检验数行得到对偶问题的一个基解，并且将两个解分别代入各自的目标函数时其值相等。

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

一.单纯形法和对偶单纯性法

单纯形法是求解线性规划的主要方法, 单纯形表则是单纯形法和对偶单纯形法的运算工具。设线性规划问题为

Max Zcjxj

j1nnm,)aijxjbi(i1,...s.t.j⑴

0(j1,....n),xj将其化为标准形式，得

Max Z= CX

AXXsb

s.t.

⑵

X,0Xs其中C(CB,CN)，CN性约束转换为XBB1X0(0,0,...,0)，A(B,N)，XB，则其对应的线

XN1XNB1Xs0，XBBbB1111XNB1Xs，代入目标函数得ZCBBb(CNCBB)XNCBB11XS，相应的一个基解

1为XBBb，XN0，XS0。显然，若Bb0，且(CNCBBN)0，1BbCBBXS0，则基解X为该线性规划的最优解, 此时检验数均大

0于零, 见表1。1

通过上面的分析, 我们知道单纯形表的检验数实际上是目标函数中基变量、非基变量的价值系数,又由对偶理论知道它们是相应对偶问题的一个(加一个负号)基解。那么表中b列的数字仅仅表示的是

XB的取值吗? 我们可以猜想B1b 很可能是对偶问题的检验数。这里首先给出问题(1)的对偶问题的一般形式

Min wbiy

i1immaijyicj(j1,...,n)

s.t.i

1⑶

y0(i1,....,m)i将问题（3）化为标准形式，得

Min wYB

YAYSC

s.t.

⑷

Y,YS0由C(CB,CN)，A(B,N)，Ys为松弛变量，Ys相应分解为YsB、YsN，其中YsB(ym1,ym1,....,y2m)0，YsN(y2m1,y2m2,....,y2n)0。得：

YBYsBCB

⑸

YNYsNCN

⑹ 由式⑸得到

YCBBYsBB

⑺ 通过令YsB0，由式(5)得对偶问题的基解YCBB111,代入式(6)得

11YsNCBBNCN,将式(7)对偶问题的目标函数得wCBBbYsBBb。1显然若目标函数达到最小,非基变量YsB的价值系数要求大于等于零,单纯形表b列Bb0, 即Bb0实际上是对偶问题的非基变量检验数。二．对偶单纯形法的算法步骤

(1)确定换出基的变量

设原问题为（1），对偶问题为（3）。由A(B,N),C(CB,CN)，不等式YAC则可分解为 YBCB,YNCN(8)进一步添加松弛变量有等式（5）、（6），对等式（5）两端同时左乘B有

YYsBBCBB(9)将YsBB移至等式右端得

YYsBBCBB(10)由不等式（8）得

CBYB0(11)CNYN0(12)将式（10）代入不等式（11）、（12）得

CBYBCBCBBBYsBBB0(13)

1111111111 CNYNCNCBBNYsBBN0(14)将（13）、（14）合并得

(CB,CN)Y(B,N)(CB,CN)(CBBYsBB)(B,N)0(15)整理得

CCBBAYsBBA0(16)其中CCBBA是单纯形表中X变量的检验数,记CCBBA(j)，(j=1,2,....,n),B111111111A(aij)mxn矩阵，显然，若Y为基可行解，而若

11'B1b0，则对偶问题的目标函数wCBBbYsBBb未取得最小值，取min(Bb)i|(Bb)i0(Bb)l，确定单纯形表的换出基变量xl，即（在单纯111形表中的）对偶问题相应的换入基变量

yml，令YsB其余分量为零，即可能取大，使对偶问题的目标YsB(ym1,ym2,...,y2m)(0,...,0,yml,...,0)，yml函数值下降，由Y为基可行解，则要求满足式（16），即对于任意的j，均有'jmk0，得min|0,0yyaaij'，从而确定单纯形'jjijmlmlaijal,mk'表中换入基变量xmk，同时确定对偶问题（在单纯形表中）换出基变量y。这

k与单纯形法确定换出基变量的规则是完全一样的。3）例题讲解

下面举例说明对偶单纯形法的算法步骤： 【例题】用对偶单纯形法求解线性规划问题：

min w15y24y5y

1236yy232

s.t.5y2yy1

123y1,y2,y30解：1）将问题改写为：

2）算法步骤

第一步：建立一个初始单纯形表，使表中检验行的j值全部大于或等于零，即对其对偶问题而言是一基本可行解。

约束条件两端乘-1，得：

根据原问题和对偶问题之间的对称关系，这时单纯形表中原基变量列数字

相当于对偶问题解的非基变量的检验数。第二步：由于对偶问题的求解是使目标函数达到最小值，所以最优判别准则是

当所有检验数大于或等于零时为最优（也即这时原问题是可行解）。

如果不满足这个条件，找出绝对值最大的负检验数，设为-bi，其对应的原问题的基变量xl即为对偶问题的换入变量。第三步：将j行数字与表中第l行对应的数字对比，令

CjCj min|，alk即为主元素，xk为对偶问题的换出变 |aij0aijalk 量。

第四步：用换入变量替换对偶问题中的换出变量（在单纯形表中反映为用替原问

题的基变量），得到一个新的单纯形表。

表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本

可行解，原问题基变量列数字列数字相当于对偶问题的检验数。

据此可以完成对这个对偶问题的求解。

4．总结。

1）对比单纯形法&对偶单纯形法单纯性法基本思想

2）对偶单纯形法优点

这里我们需要对单纯形法和对偶单纯形法做一个详细的对比： 1，单纯形法中的b对应于对偶单纯形法中的；

2，单纯形法中的作为检验数，对偶单纯形法中的b作为检验数； 3，单纯形法中的b0，对偶单纯形法中的0；

4，单纯形法中当0时得到最优解，对偶单纯形法中当b0时得到最优 解；

5，单纯形法的可行解为XBb，对偶单纯形法的可行解为YCBB；（由于松弛变量Xs对应的检验数为CBB，由于Xs与Y对应，又由于

CBB0，可得YCBB0）。11111

对于单纯形法和对偶单纯形法，我们建立了使用单纯形法解决线性规划问题的依据：

1，表中有单位矩阵I，当b0时用单纯形法；

2，表中有单位矩阵I，当0时用单纯形法；

3，两者都不满足时，使用人工变量法或两阶段法。

接下来需要说明在哪些场合下使用对偶单纯形法解决线性规划问题较为便

捷，我将通过下面的例子来说明：

min Z12x18x216x312x4

2x1x24x32

s.t.2x12x24x43

x1,x2,x3,x40

令ZZ，则问题可变为

max Z12x8x1216x312x4

2x1x24x3x52

s.t.2x12x24x4x63

xi0(i1~6)取B(P5,P6)为初始基，易见所有检验数j0，从而建立单纯形表，计 算结果如下：

本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算 量要多于对偶单纯形法。一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法。但是，对偶单纯形法并不是一种普遍算法，它有一 定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。当线性规

划问题具备下面条件时，可以用对偶单纯形法求解：

①问题标准化后，价值系数全非正；

②所有约束全是不等式。

总结上面的分析过程可知，对偶单纯形法本质上就是单纯形法,只不过在运用对偶单纯形法解线性规划时需要将单纯形表旋转一下。单纯形表中的b列Bb实际上是对偶问题的非基变量YsB 的检验数, 而原单纯形表的检验数为对偶问题的(负的)基解, 这样可以理解为通过旋转90°运用单纯形法求解线性规划。

1