单纯形法_正单纯形法

单纯形法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“正单纯形法”。

2.2 单纯形法

考虑标准最大化线性规划问题的(1.15)

max

cxjj1nj

naijxjbi s.t.j1xj0i1,2,...,mj1,2,...,n

我们首先对它的第i个约束条件引入松弛变量si,i1,2,...,m,并且以表示目标函数值,则获得标准型(1.15)的等价线性规划,也称为标准型(1.15)的标准格式:

maxcj1njxj

nsibiaijxj,i1,2,...,mj1xj0,j1,2,...,n

s.t.

(2.10)si0,i1,2,...,m从例2.1线性规划问题的求解过程中可以看到,随着迭代的继续,决策变量和松弛变量相互交织,成为一体,所以为了便于分析,令xnisii1,2,...,m,并引入以下标记:(x1,x2,...,xn,s1,s2,...,sm)(x1,x2,...xn,xn1,...,xnm)

那么,我们将(2.10)改写为:

maxcjxj

j1nnxbiaijxj,i1,2,...,m

(2.11)s.t.nij1xj0,j1,2,...,n,n1,...,nm式(2.11)就是标准型线性规划问题(1.15)的标准格式或初始单纯形,显然若令xj0,j1,2,...,n,则有xnibi,i1,2,...,m,则x0(0,...,0,b1,b2,...,bm)构成了标准型线性规划问题(1.15)的初始基可行解。随着搜索最优解过程的继续,单纯形迭代算法将从单纯形的一个顶点转移到另一个顶点上,或是从一个基可行解到另一个基可行解。但是对于任何一个单纯形来说,它都具有m个基变量和n个非基变量。为了便于分析,我们以B记录基变量下标集合,以N记录非基变量下标集合。对应于初始单纯形,决策变量和松弛变量的下标集合为: {1,2,...,n,n1,...,nm}

所以,初始单纯形的基变量的下标集合为: B{n1,...,nm}

非基变量的下标集合为: N{1,2,...,n}

在这之后,B和N随单纯形的迭代发生变化,假设,经过若干次迭代之后,最新单纯形具有如下形式:

cjxj

jNxibiaijxj

iB,jN

(2.12)

jN我们注意到,在单纯形法的每一步迭代中,都一定出现某一个基变量变为非基变量,同时某一个非基变量变为基变量。如果一个变量是从非基变量进入到基变量中,则称它为换入基变量,或换入变量;另一方面,如果一个变量是从基变量转换到非基变量,则称它为换出基变量或换出变量。

2.2.1换入变量和换出变量的确定准则

为了能够进行下一步迭代,单纯形法要求从非基变量xj,jN中选择某个决策或松弛变量作为换入变量,选择换入变量的基本条件是增加换入变量的值能够保证增加目标函数值,这就要求换入变量在目标函数中的系数cj,jN为正数。以E表示目标函数系数为正数的非基变量下标集合,即

E{j:cj0,jN}

对于单纯形(2.12)来说,如果E是空集合,那么对应的基可行解就是最优解。如果E含有多个

cj:jE},非基变量cj0,我们通常选择绝对值最大的cj,即选择k使其满足ckmax{xk就是换入变量。

另一方面,在选定了换入变量之后,单纯形法还需要从基变量xi,iB中选择一个换出变量,挑选换出变量的基本准则是必须保持当前所有基变量的取值大于等于零,即xi0,iB。在确定了某个非基变量xk作为换入变量之后,增加xk的值将会同时影响所有基变量的取值。根据单纯形(2.12),如果令xj0,jk,jN,则有:

xibiaikxk

iB

由于变量的非负符号限制,有xi0,iB,那么有:

biaikxk0

iB

(2.13)

我们首先假设bi0,aik0,iB,当xk取值不断增大时,为使基变量xi,iB保持非负符号限制,xk取值的范围必须符合下述条件:

0xkbi

iB aik所有bi,iB都是换入变量xk取值的上限,因为这样的上限有m个,所以xk必须小于aik{bi,iB}当中最小的一个,即: aikxkmin{iB;aik0bi}

(2.14)aik以L表示满足{aik0:iB}的下标集合,那么,选择换出变量的规则是选择lL,满足下述等式:

blbmin{i}。alkaiklL那么对应下标l的基变量xl就是换出变量,称alk为单纯形迭代的主元素。如果出现aik0,iB,我们需要从另一个角度来研究如何确定换出变量的方法,为此我们首先将(2.7)式改写为:

1aik

iB xkbi在这种情况下,我们没有要求aik必须大于0,换入变量xk的倒数的取值范围为:

aikxk

iB bi确定换出变量的方法是在基变量下标集合中选择l使得下面等式成立:

alkamax{ik}

(2.15)blbiiB对应下标l的基变量xl就是换出变量。我们注意到上述两种确定换出变量方法之间的差异:在第二种方法下,没有aik0,iB的要求。在选定了换入变量xk和换出变量xl之后,就唯一确定了本次迭代的主元素alk,并可以利用它对单纯形进行高斯变换,在完成高斯变换之后,就可得到一个新的单纯形,通常我们把整个高斯变换称为主元素消元法。

2.2.2单纯型法的最优性检验与解的判别

从线性规划的几何解法中,我们通过图型直观了解到对于两个决策变量的线性规划问题,其求解结果可能出现唯一最优解,多重最优解,无界解,以及无可行解等情况。这些结论也同样适合具有多个决策变量的线性规划问题。为了方便分析,我们利用单纯形(2.12)来建立标准型线性规划问题(1.5)解的判别准则: 设非基变量为零,即:xj0,jN,则可获得基解:xibi,iB,那么基可行解为:x(0,...,0,b1,b2,...,bm),目标函数值为:,那么:(1)唯一最优解的判别准则:如果对于任意jN都有cj0,则问题(1.5)具有唯一最优解x,最优目标函数值为。

(2)多重最优解的判别方法:如果对于任意jN都有cj0,并且又存在某个kN使得ck0,则问题(1.5)具有多重或无穷多最优解,最优目标函数值为。

(3)无界解的判别方法:如果存在某个kN使ck0,并且对任意iB,都有aik0,那么,线性规划问题(1.5)的最优解无界,或具有无界解。