单纯形法(2)

二、加松弛变量

对所有约束条件为“≤”形式的不等式，利用化标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对

x1及

aij(i?1,2,...,m,j?1,2,...,n)进行编号，则可得下列方程组(x1,x2,...,xm

为松弛变量）：

?x1? a1,m?1xm?1???a1,nxn?b1??x2? a2,m?1xm?1???a2,nxn?b2 ??? ? ? ? ? ? ? ? ?xm? am,m?1xm?1???am,nxn?bm (1-11)

???xj ?0,j?1,2,?,n 于是，（1-11）中含有一个m×m阶单位矩阵，初始可行基B即可取该单位矩阵

?1??0B?(P,P,?,P)?12n????0?将（1-11）中的每个等式移项得

01?0????0??0????1??

?x1?b1?( a1,m?1xm?1???a1,nxn)??x2?b2?( a2,m?1xm?1???a2,nxn) ?? ? ? ? ? ? ? ? ? ?xm ?bm ?( am,m?1xm?1???am,nxn) (1-12)

???xj ?0,j?1,2,?,n 令xm?1???xn?0，由(1-12)式可得

xi?bi (i?1,2,...,m)

又因bi?0，所以得到一个初始基可行解

x?(x1,x2,...,xm,0,...,0)T ?(b1,b2,...,bm,0,...,0) 6

T n?m个0

三、加非负的人工变量

对所有约束条件为“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人造基方法:

-即对等式约束，减去一个非负的剩余变量，再加上一个非负的人工变量； -对于不等式约束，再加上一个非负的人工变量

这样，总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。

2.3 最优性检验

根据最优性准则判断当前解是否为最优解：

经过若干次迭代后的当前解，其基变量用非基变量表示的规范式的一般形式为:

'x?b?a? iijxj,i?1,2,3,?,m. (1-14)

j?m?1'in将（1-14）代入目标函数中可得目标函数用非基变量表示的规范式为：

z ? ?cixi ??cjxji?1mj?m?1nmn

??ci(b??axj)??cjxji?1mj?m?1nj?m?1'i'ijn (1-15)

??cb???caxj??cjxj i?1mi?1j?m?1nj?m?1' ??cb??(cj??ciaij)xji?1j?m?1i?1mm'ii'iim'iijnm记z0??cb,z??ca,j?m?1,?,n，

'iij'iiji?1i?1则有 z?z0??(cj?zj)xj (1-16)

j?m?1m'?cj??ciaij?cj?zj

i?1n再记 ?j得

z?z0???jxj. (1-17)

j?m?1n定理1 设（1-14）式及（1-17）式是最大化线性规划问题关于当前解的基本可行解x的两个规范式。若关于非基变量的所有检验数?j前基本可行解x就是最优解。将?j**?0(j?jN)成立，则当

?0(j?jN)称为最大化问题的最有性准则。

7

2.4 基变换

若初始基可行解x解。具体做法是：

从原可行解基中换一个列向量(当然要保证线性无关)，得到一个新的可行基，称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。 一、换入变量的确定

由(1-18)式可知，当某些?i(0)不是最优解及不能判别无界时，需要找一个新的基可行

?0时，若xi增大，则目标函数值还可以增大。

这时需要将某个非基变量xi换到基变量中去(称为换入变量)。 若有两个以上的?i?0，为了使目标函数值增加得快，从直观上看应选

j?i?0中的较大者，即由max(?j?0)??k 知,应选择xk为换入变量。

二、换出变量的确定 设p1,p2,...,pm是一组线性无关的向量组，它们对应的基可行解是x(0)，将它

?m代入约束方程组(1-10)得到

i?1xi(0)pi?b (1-18)

其他的向量

pm?1,pm?2,...,pm?t,...,pn都可以用p1,p2,...,pm线性表示。若

确定非基变量xm?t为换入变量，必然可以找到一组不全为0的数?i,m?t (i=1,2,?,m)使得

mmPm?t???i,m?tPi 或 Pm?t???i,m?tPi?0 (1-19)

i?1i?1在(1-19)式两边同乘一个正数θ，然后将它加到(1-18)式上，得到

i?1m?xm(0)im???b 或 P??P??P??im?ti,m?ti???i?1(1-20)

i?1?(xi(0)???i,m?t)Pi??Pm?t?b 当θ取适当值时，就能得到满足约束条件的一个可行解（即非零分量的数目不大于m个）。就应使(xi(0)???i,m?t),i?1,2,?,m.中的某一个为零，并保证其

8

余分量为非负。即取θ为：

??min(ixi(0)?i,m?t|?i,m?t?0) ?xl(0)?l,m?t

这时的xl为换出变量。按最小比值确定θ值，这种方法称为最小比值规则。

将

xl(0)?l,m?tx(1)带入到X中，便可得到新的可行解。新的可行解为：

(0)(0)?(0)xi(0)?xx(0)il????1,m?t,?,0,xm???m,m?t,?,0,,?,0? ?xl????l,m?t?l,m?tl,m?t??由此得到由x(0)转换到x(1)的各分量的转换公式：

?(0)xi(0)??i,m?t i?m?t?xi??l,m?t?lxi??(0) ?xl i?m?t ??l,m?t?这里xi(0)是原基可行解x(0)的分量；xi是新可行解x(1)的各分量;

(1)?i,m?t是换入向量pm?t对应原来一组基向量的坐标。

该新可行解x(1)也是基可行解。下面我们来证明这个新可行解x(1)的m个非零分量对应的列向量是线性无关的。事实上，因为x(0))的第l个分量对应于x(1)的相应分量是零，即xl则（

(0)???l,m?t?0 .其中xl(0),?均不为零，根据最小比值规xl中的m个非零分量对应的个列向量是

?l,m?t?0），

pj(j?1,2,...,m,j?l)和pm?t。 若这组向量不是线性无关，则一定可以找

到不全为零的数?j，使得

Pm?t成立。又因为

9

??ajPj, j?l (1-21)

j?1m Pm?t将(1-22)式减(1-21)式得到

???j,m?tPj (1-21)

j?1m j?1j?l?(?j,m?t?aj)Pj??l,m?tPl?0m

由于上式中至少有?i,m?t?0，所以上式表明p1,p2,...,pm是线性相关的，这

xl中的m个非零分量对应的个列向量是

与假设相矛盾。由此可得，

pj(j?1,2,...,m,j?l)和pm?t是线性无关的，即经过基变换得到的解是基

可行解。此外，由式（1-17）可导出经过基变换得到的新解的目标函数值为：

z1(1)?z0??m?txm?t?z0??m?t??z0

因此，该新基可行解X(1)也是一个改进了的基本可行解。

做题时我们会发现每次选用迭代的可行基矩阵都是单位矩阵，我们不妨设

''''Tpm?(a,a,?,a)?t1,m?t2,m?tm,m?t'则，pm?t?1??0??0???1,m?t???0??1??0???m2,m?t? '??????????i,m?tpi? ?1,m?t ??2,m?t ????n,m?t ?????????????i?1?????????001???????m,m?t?即

'pm?t的表出系数为

所有的

?i,m?t?ai',m?t, i ?1,2,?,m.'pm?t的分量。同时，当可行基为单位矩阵时，当前基本可行解的基变量取值为：

xi(0)?bi' i?1,2,...,m

即当前基变量的取值为约束方程右端项的值。故最小比值准则式子为：

'?xi(0)??bi'?b'l?????min?|??0?min|a?0?i,m?ti,m?t??a'i??i?a'l,m?t?i,m?t??i,m?t?

这不仅简化了计算，而且还提供了以表格形式连续完成用单纯形法求解线性规划问

题各个步骤的可能性。

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库单纯形法(2)在线全文阅读。