2010生第五章单纯形法

1概念回顾2目标函数：max50x1+100x21

2

1约束条件：x

+x

+s

≤300，2x1+x2+s2≤400，x2+s3≤250.xj≥0

（j=1，2）,sj≥0

（j=1，2,3）

1

0

1

0

1

1

1

0

0

A

=(p1,

p2

,

p3,

p4

,

p5

)

=

2

1

0

1

0

0基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中

m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。初始可行基：由单位矩阵的各列向量所组成。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。

非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有

n－m个。3如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。把满足非负条件的一个基本解叫做基本可行解。初始基本可行解？？？可行解？？？单纯形法迭代原理4从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法——单纯形法迭代原理。5观察法:直接观察得到初始可行基≤约束条件:加入松弛变量即形成可行基。（下页）≥约束条件:加入非负人工变量,以后讨论.1、初始基可行解的确定

6

..........................................

x1,

x2

,...,

xn

‡

0xm

+

amm+1

xm+1

+...

+

amn

xn

=

bmx2

+

a2m+1

xm+1

+...

+

a2n

xn

=

b2+

a1m+1

xm+1

+...

+

a1n

xn

=

b1

x11、初始基可行解的确定不妨设程组可表示为x1,x2为,

松,弛x变m

量，则约束方X

=(b1

,b2

,...,bm

,0,0,...,0)是一初始基可行解。7有：(i

=1,2,...m)

..........................................

令：xm+1

=

...

=

xn

=

0xi

=

bixm

=

bm

-

amm+1

xm+1

-...

-

amn

xnx2

=

b2

-

a2m+1

xm+1

-...

-

a2n

xn

x1

=

b1

-

a1m+1

xm+1

-...

-

a1n

xn1、初始基可行解的确定单纯形法的表格形式8为了使单纯形法更加简洁明了，经常通过表格进行计算。9max

50x1+100x2+0·s1+0·s2+0·s3.x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250，x1,x2,s1,s2,s3≥0.把上面的数据填入如下的单纯形表格按照线性规划模型在表中填入相对应的值，如上表所示；在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。在s

j

=c

j

-z

j行中填入cj-zj所得的值，如

s

1

；迭代 基变次数

量cBx1x2s1s2s3b比值Bi/ai2501000000s1s2s300020111001250100300300/1010400400/1250/1zjδj=cj-zj0500100000000z=0=

50

-

0

=

5

0由于s

2>

s1

z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列；初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此确定s3为出基变量；>0

，因此确定x2为入基变量。出基变量所在行，入基变量所主1元00110以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，2由于主元在p

的第3

分量上，所以这个单位向量是素变成1。这样我们又得到的第1次迭代的单纯表如下所示。在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.3e

=(0,0,1

)T也就是主元迭代次数基变量cBx1x2s1s2s3b比值bi/aij50100000s101010-15050/1s202001-1150150/21x210001001250—zjs

j

=

c

j

-

z

j0100001002500050000-

1001112为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。从上表可以看出，第一次迭代的

s

1

，因此不是最优解。设x1从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50,s3=0,这时z=27500。由于检验数都≤0，因此所求得的基本可行解为最优解，z=27500为最优目标函数值。实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。=

50

>

0迭代次数基变量cBx1x2s1s2s3b比值bi/aij50100000x1501010-150s2000-211502x210001001250zj501005005027500s

j

=

c

j

-

z

j00-500-5013练习：用单纯形法的表格形式求解下列问题max

Z

=

4

x1

+

x

2

x1

+

3

x

2

£

7£

9s

.t

4

x1

+

2

x

2x1

,

x

2

‡

0第一步？？？练习：

s

.t

4

x1

+

2

x

2

+

s

2+

0

s1

+

0

s

2

x1

+

3

x

2

+

s1

=

7x1

,

x

2

,

s1

,

s

2

‡

0=

9化为标准型max

Z

=

4

x1

+

x

2迭代 基变次数

量cBx1x2s1s2b比值bi/aij41000s1s20014321001797/19/4zjδj=cj-zj0401000001415迭代基变x1x2s1s2比值次数量cBbbi/aij4100s1002.51-1/419/4x1410.501/49/41zj42019δj=cj-zj0-10-1解得：最优解为x1=9/4x2=0s1=19/4s2=016求目标函数值最小的线性规划的问题的单纯形表解法一、大M法以第二章的例2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。目标函数：约束条件：加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：x1

+

x2

-

s1

=

350,x1

-

s2

=125,2x1

+

x2

+

s3

=

600,x1

,

x2

,

s1

,

s2

,

s3

‡

0.m

in

f

=

2

x1

+

3

x

2

.x1

+

x

2

‡

350

,x1

‡

125,2

x1

+

x

2

£

600

,x1

,

x

2

‡

0

.找不到初始基本可行解！！！17求目标函数值最小的线性规划的问题的单纯形表解法引入人工变量，与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。规定人工变量在目标函数中的系数为－M，这里M为任意大的数。这样只要人工变量M＞0，所求的目标函数最大值就是一个任意小的数。为了使目标函数实现最大就必须把人工变量从基变量中换出。应用单纯形表格法求解。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则该问题无可行解。对于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个统一的解法，我们把所有求目标函数最小值的问

题化成求目标函数最大值的问题。具体做法只要把目标函数乘以（－1）。18§3

求目标函数值最小的线性规划的问题的单纯形表解法此例的数学模型如下所示：目标函数：maxz=－2x1－3x2－Ma1－Ma2.约束条件：x1+x2－s1+a1=350，x1－s2+a2=125，2x1+x2+s3=600，x1，x2，s1，s2，s3，a1，a2≥0.像这样，为了构造初始可行基得到初始可行解，把人工变量“强行”地加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为－M，这个方法叫做大M法，M叫做罚因子。求目标函数值最小的线性规划的问题的单纯形表解法面我们就用大M法来求解此题:下迭代次数基变量cBx1x2s1s2s3a1a2b比值-2-3000-M-M0a1-M11-10010350350/1a2-M100-1001125125/1s302100100600600/2zjs

j

=

c

j

-

z

j-2M-MMM0-M-M-475M-2+2M-3+M-M-M0001a1

-Mx2

-2s3

0zjs

j

=

c

j

-

z

j01-1001-1225225100-1001125-----010210-2350350/2-2-MM-M+20-M-M-2-225M-0-3+M-MM-2002-2M2502a1-M01/2-10-1/2105050/1/2x1-211/2001/200300300/1/2s2001/2011/20-1175175/1/2zj-2-1/2M-1M01/2M-1-M0-50M-01/2M-2-M0-

1/2M+10-M600s

j

=

c

j

-

z

j1920§3

求目标函数值最小的线性规划的问题的单纯形表解法从上表中可知检验数都小于零。已求得最优解为：x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最优值为f=-z=-(-800)=800。j

j

js

=

c

-

z迭代次数基变量cBx1x2s1s2s3a1a2b比值-2-3000-M-Mx2-301-20-120100x1-210101-102503s2000111-1-1125zj-2-3401-40-80000-40-1-M+4-M21求目标函数值最小的线性规划的问题的单纯形表解法二、两阶段法两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题：目标函数：max

z

=-a1

-a2

;约束条件：x1

+

x2

-

s1

+

a1

=

350,x1

-

s2

+

a2

=125,2x1

+

x2

+

s3

=

600,x1,

x2

,

s1

,

s2

,

s3

,

a1,

a2

‡

0.22求目标函数值最小的线性规划的问题的单纯形表解法注意：此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。求目标函数值最小的线性规划的问题的单纯形表解法迭代次数基变量cBx1x2s1s2s3a1a2b比值00000-1-10a1-111-10010350350/1a2-1100-1001125125/1s302100100600600/2zj-2-1110-1-1-47021-1-10001a1-101-1101-1225x10100-1001125s30010210-2350zj0-11-10-1122501-1100-

22x2001-11010225x10100-1001125s3000111-1-1125zj0000000000000-1-123求目标函数值最小的线性规划的问题的单纯形表解法迭代次数基变量cBx1x2s1s2s3b比值-2-30000x2-301-110225225/1x1-2100-10125s3001021125125/2zj-2-33-10-92500-3101x2-301-20-1100x1-210101250s2000111125zj-2-3401-80000-40-1从表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。2425几种特殊情况3

x1

+

10

x

2

£

150

,x1

£

30

,x1

+

x

2

‡

40

,x1

,

x

2

‡

0

.z

=

20

x1

+

30

x

2目标函数

max约束条件一、无可行解例1、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：m

ax

z

=

2

0

x1

+

3

0

x

2

-

M

a13

x1

+

1

0

x

2

+

s1

=

1

5

0

,x1

+

s

2

=

30

,x1

+

x

2

-

s3

+

a1

=

40

,x1

,

x

2

,

s1

,

s

2

,

s3

,

a1

‡

0

.填入单纯形表计算得：目标函数约束条件26几种特殊情况迭代基变量CBx1x2s1s2s3a1b比值次数2030000-Ms103101000150150/10s2010010030—0a1-M1100-114040/1zj-M-M00M-M-40Mcj-zj20+M30+M00-M0x2303/1011/100001515/(3/10)s201001003030/11a1-M7/100-1/100-112525/(7/10)zj9-7/10M303+M/100M-M450-25Mcj-zj11+7/10M0-3-M/100-M0x230011/10-3/100062x12010010030a1-M00-1/10-7/10-114zj20303+M/1011+7M/10M-M780-4Mcj-zj00-3-M/10-11-7M/10-M027几种特殊情况无法显示该图片。从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解

x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得x1+x2-0+4=40,即有：

x1+x2=36≤40.并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。二、无界解在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取

任意的大。下面我们用单纯形表来求第二

章中的例子。例2、用单纯形表求解下面线性规划问题。目标函数

m

ax

z

=

x1

+

x

2约束条件

x1

-

x

2

£

1,-

3

x1

+

2

x

2

£

6

,x1

,

x

2

‡

0

.82几种特殊情况迭代次数基变量CBx1x2s1s2b比值11000s1s2001-3-121001161—zjcj-zj0101000001x1s21010-1-1130119zjcj-zj10-121-1001填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：m

ax

z

=

x1

+

x

2x1

-

x

2

+

s1

=

1,2-

3

x1

+

2

x

2

+

s

=

6

,x1,

x

2

,

s1,

s

2

‡

0

.目标函数

约束条件

几种特殊情况移项可得：x1

=1+x2

-s1,s2

=

x2

-

3s1

+

9.x1

-

x2

+

s1

=1,-x2

+

3s1

+

s2

=

9.12x1

=

M

+1,x2

=

M

,s1

=

0,s2

=

M

+

9.不妨设x

=

M

,

s

=

0,可得一组解：显然这是线性规划的可行解，此时目标函数z

=

x1

+

x2

=

M

+1+

M

=

2M

+1.从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解

x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题a：12 =-1a,22 =-1,找不到大于零的a

22

来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：2930几种特殊情况由于M可以是任意大的正数，可知此目标函数值无界。上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数s

ij

，并且该列

的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零，则此线性规划问题

是无界的，一般地说此类问题的出现是由于建模的错误所引起的。三、无穷多最优解例3、用单纯形法表求解下面的线性规划问题。m

ax

z

=

5

0

x1

+

5

0

x

2x1

+

x

2

£

300

,2

x1

+

x

2

£

400

,x

2

£

250

,x1,

x

2

‡

0

.目标函数约束条件31几种特殊情况m

a

x

z

=

5

0

x1

+

5

0

x

2x1

+

x

2

+

s1

=

300

,解：此题我们用图解法已求了解，现在用单纯形表来求解。加入松弛变量s1

,s

2

,s

3，我们得到标准形：目标函数约束条件2

x1

+

x

2

+

s

2

=

400

,x

2

+

s

3

=

250

,x1,

x

2

,

s1

,

s

2

,

s

3

‡

0

.填入单纯形表计算得：32几种特殊情况迭代基变量CBx1x2s1s2s3b比值次数5050000s1011100300300/1s2021010400400/10s3001001250250/1zj000000cj-zj5050000s101010-15050/1s202001-1150150/21x25001001250—zj050005012500cj-zj500000x1501010-150—2s2000-2115050/1x25001001250250/1zj5050500015000cj-zj00-500033几种特殊情况这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数

s

1

,

s

2

,

s

4 等于零外，非基变量s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：迭代次数基变量CBx1x2s1s2s3b5050000x15010-110100s3000-211503x250012-10200zj5050500015000cj-zj00-500034几种特殊情况从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个最优解即Z1

=（50，250，0，50，0），Z2=（100，200，0，0，50），则此线段上的任一点，即可表示为αZ1+（1-α

）Z2，其中0≤α≤1。如图5-1所示：100200300100200300250Z1Z2图5-135几种特殊情况ss在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数为零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？不妨设出基变量为xk，则原最优单纯形表可表示如下：x

kc

k

x1c1

0

x

sc

sa

1

s

a

k

-

1

,

sa

k

,

sa

k

+

1

,

s

a

m

,

s0c

k

-

1

0

c

k

1

c

k

+

1

0

c

m

0

0jx

k

-

1x

kx

k

+

1

x

ms

=

c

j

-

z

jm从此表可知s

s

=0,即有c1

a

1

s

+c

2

a

2

s

+

+c

m

a

m

s

-c

s

=0，也就是c

s

=

c

i

a

i

s。i

=

1几种特殊情况通过迭代，我们得到了新的单纯形表，其中x

为基变量了，s而xk为非基变量了。我们可得到下表。

(k

-1)s

aks1aks

(k

+1)s

(

)(

)x1

c1

xk

-1

ck

-1xs

cs011100ksm

1i

is1

k

-1csksmi

=1csksksmmksa-a1sxk

xsck

cs0-c

a

+-c

aa-aa-axk

+1ck

+1axcaz

j

zk

csc

j

-

z

j

c

j

-

zk

0

-ams+i

is

ks

i

=1

i

=

k

+1

=a

-

c

a

+

-c

ak ks

+

ks

i

is

在此表中zk

=a

1361cs

=

ck

.即又可得到：c

j

-zk

=c

j

-zk

=0.si

isi

=1m把c

=

c

a

，

代入上式得：kks

ksz

=a

a[-cs

+

ck

aks

]+37几种特殊情况又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。四、退化问题在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。目标函数

约束条件

m

ax

z

=

2

x

+

3

x1

2x1

-

x

2

£

2,2

x1

+

x3

£

4

,x1

+

x

2

+

x3

£

3,x1

,

x

2

,

x3

‡

0

.3例4.用单纯形表，求解下列线性规划问题。解：加上松驰变量s1,s2,s3化为标准形式后，填入单纯形表计算得：38几种特殊情况迭代基变量CBx1x2x3s1s2s3b比值次数203/2000s10