2运筹学之表格单纯型法.ppt

一般线性规划问题的求解

3.2初始基可行解的确定为了确定初始基可行解，要首先找出初始可行基，其方法如下。(1)直接观察(2)加松弛变量(3)加非负的人工变量(1)直接观察

从Pj(j=1,2,…,n)中一般能直接观察到存在一个初始可行基

(2)加松弛变量对所有约束条件是“≤”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对xj及aij(i=1,2,…,m;j=1,2,…,n)进行编号，则可得下列方程组x1,x2,…,xm为松弛变量于是含有m×m单位矩阵，以B作为可行基。

将(1-22)式每个等式移项得

令xm+1=xm+2=…=xn=0，由(1-23)式可得xi=bi(i=1,2,…,m)得到一个初始基可行解又因bi≥0(在1-3节中已做过规定)，所以得到一个初始基可行解X=(x1,x2,…,xm,,0，…，0)Tn-m个=(b1,b2,…,bm,,0，…，0)Tn-m个(3)加非负的人工变量对所有约束条件是“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。关于这个方法将在本章第5节中进一步讨论。

3.3最优性检验与解的判别

对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后(1-23)式变成

将代入目标

函数(1-20)式，整理后得

令

1最优解的判别定理

若为对应于基B的一个基可行解，且对于一切j=m+1,…,n，有σj≤0，则X(0)为最优解。称σj为检验数。

2.无穷多最优解判别定理

若为一个基可行解，对于一切j=m+1，…,n，有σj≤0，又存在某个非基变量的检验数σm+k=0，则线性规划问题有无穷多最优解。证:只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。因σm+k=0，由(1-27)知z=z0，故X(1)也是最优解。由2.2节的定理3可知X(0)，X(1)连线上所有点都是最优解。

3．无界解判别定理

若为一基可行解，有一个σm+k＞0，并且对i=1,2,…，m，有存在。那么该线性规划问题具有无界解(或称无最优解)。证:构造一个新的解X(1)，它的分量为因，所以对任意的λ＞0都是可行解，把x(1)代入目标函数内得z=z0+λσm+k因σm+k＞0，故当λ→+∞，则z→+∞，故该问题目标函数无界。以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一种情况如前所述，将其化为标准型。如果不化为标准型，只需在上述1，2点中把σj≤0改为σj≥0，第3点中将σm+k＞0改写为σm+k＜0即可。

3.4基变换

若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。1.换入变量的确定

由(1-27)式看到，当某些σj＞0时，xj增大，则目标函数值还可以增大。这时要将某个非基变量xj换到基变量中去(称为换入变量)。若有两个以上的σj＞0，那么选哪个非基变量作为换入变量呢?为了使目标函数值增加得快，从直观上一般选σj＞0中的大者，即2.换出变量的确定设P1，P2，…，Pm是一组线性独立的向量组，它们对应的基可行解是X(0)。将它代入约束方程组(1-21)得到新的基可行解。

由此得到由X(0)转换到X(1)的各分量的转换公式

这里是原基可行解X(0)的各分量；

是新基可行解X(1)的各分量；βi,m+t是换入向量Pm+t的对应原来一组基向量的坐标。现在的问题是，这个新解X(1)的m个非零分量对应的列向量是否性独立?事实上，因X(0)的第l个分量对应于X(1)的相应分量是零，即

将(1-32)式减(1-31)式得到

由此可见，X(1