《运筹学》课件 第2章 单纯形法

第二章单纯形法第2章内容提要2.1单纯形法的一般原理2.2单纯形法的计算步骤2.3表格单纯形法2.4人工变量问题2.5解的讨论线性规划单纯形法

单纯形法(SimplexMethod)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法单纯形法线性规划问题的几何意义：凸集：没有凹入部分，内部没有空洞。实习圆、实心球体、实心立方体都是凸集；两个凸集的交集是凸集。若线性规划问题存在可行域，则可行域是凸集。线性规划问题的基可行解对应可行域的顶点。若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。2.1纯形法的一般原理考虑线形规划问题：

maxZ＝CXAX＝bX≥0如果有可行域D＝{X∈Rn|AX=b,X≥0}非空有界，则D上的最优目标函数值Z＝CX一定可以在D的顶点达到。单纯形法的基本思路根据线性规划问题的标准型，从可行域中某个基可行解一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，问题就得到最优解。因此得到5个步骤：初始解

判优

判无界

换基

迭代确定初始的基本可行解确定初始的基本可行解＝确定初始的可行基初始的可行基确定——对应初始基本可行解确定最优解判别不妨假设

A=（B,N）（B为一个基）相应地有

Xt=(XB,XN)t

C=(CB,CN)

由式

maxZ＝CXAX＝bX≥0Z=

(CB,CN)(XB,XN)t=CBXB+

CNXNAX＝（B,N)(XB,XN)t=B

XB+N

XN=b因为B为一个基,det(B)>0有XB=B-1b-B-1NXN（2.1）Z=CBB-1b+(CN-

CBB-1N)

XN（2.2）令XN＝0，则基变量XB＝B-1bX

=(XB,XN)=（B-1b,0）T为基础解，其目标函数值为Z=

CBB-1b只要XB=B-1b>=0,Xt=（B-1b,0）>=0X为基础可行解,B就是可行基。对公式Z=CBB-1b+(CN-CBB-1N)

XN

（2.2）若满足CN-

CBB-1N<=0或CBB-1N-CN>=0

则对任意的x>=0有

Z=CX<=CBB-1b即对应可行基B的可行解x为最优解。σN＝(CN-CBB-1N)为非基变量XN的检验向量

定理（最优解判别准则）对于可行基B,若

CBB-1A-C>=0则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。

CBB-1A-C为检验数。由于基变量的检验数：CBB-1B-CB=0CBB-1A-C=（0，CBB-1N-CN）2.2单纯形法的求解步骤1、确定初始基可行解basicfeasiblesolution

先找出初始可行基，确定初始基可行解，建立初始单纯形表initialsimplextableau。若能从列向量中直接观察到存在m个线性无关的单位向量，经过重新安排次序便可得到一个可行基。对约束条件都是≤，则加入的松驰变量就构成初始基。对约束条件都是≥，且不存在单位矩阵的等式约束，就要采用人造基的方法：大M法、对偶单纯法。单纯形法的求解步骤2：判优2、检验数判别得到初始基可行解后，要检验其是否为最优解：若是，问题解决；否则继续下一步。最优性判别定理：若所有检验数都

j≤0，则找到最优解。单纯形法的求解步骤3：判无界3、判断是否无界在

j>0,j=m+1,…,n中，若有某个

k对应xk的系数列向量Pk≤0

，则此问题无界，停止计算；否则转入下一步。即在单纯形表中的某xk检验数

k>0

，而该列系数全小于0，则无界。单纯形法的求解步骤4：换基4、确定换入变量和换出变量换入变量=进基变量=EnteringVariable根据max(

j>0)=

k，确定xk为换入变量换出变量=出基变量=LeavingVariable按

规则计算，可确定xl为换出变量。单纯形法的求解步骤5：迭代

5、迭代以alk为主元素（pivotnumber）进行迭代，得到新的单纯形表。迭代又称旋转运算，或高斯消去法。单纯形法的求解步骤重复步骤2~5，直到终止。判优

换基

迭代判优

换基

迭代判优

换基

迭代判优

最优解换入变量的确定——最大增加原则假设检验向量σN＝(CN-CBB-1N)=(σm+1,σm+2,…,σn),若其中有两个以上的检验数为正，选取最大正检验数所对应的非基变量为换入变量。若：max{σj|σj>0,m+1≤j≤n}=σm+K

则选取对应的xm+k为换入变量。基本可行解的改进换出变量的确定——最小比值原则基本可行解的改进例：maxZ=5x1+2x2+3x3-x4+x5x1+2x2+2x3+x4=83x1+4x2+x3+x5=7x1,x2,x3,x4,x5≥0

其中用初等变换求改进了的基本可行解在系数矩阵A中存在一个单位矩阵B＝（p4,p5）取x4,x5为基变量，x1,x2,x3为非基变量，在这一情况下：（1）确定初始基本可行解令XN=0,XB=B-1b=b=基本可行解X=(0,0,0,8,7)T目标函数值：（2）检验X=(0,0,0,8,7)T是否最优：由最优解判别定理，非基变量检验数σ1＝3>0，σ3＝4>0,所以X=(0,0,0,8,7)T不是最优解①选取换入变量：因为max{3,4}=4,

按最大增加原则，取x3为换入变量②选取换出变量

因为：

所以取θ＝min(8/2,7/1)=4,

由最小取值原则选取x4为换出变量

（3）基本可行解X=(0,0,0,8,7)T的改进（4）求改进的基本可行解X’：再转向步骤（2）（2）检验X’=(0,0,4,0,3)T是否最优：由最优解判别定理，非基变量检验数σ1＝1>0，所以X‘=(0,0,4,0,3)T不是最优解①选取换入变量：因为σ1＝1>0,

按最大增加原则，取x1为换入变量②选取换出变量

因为：

所以取θ＝min(4/(1/2),3/(5/2))=6/5,

由最小取值原则选取x5为换出变量

（3）基本可行解X’=(0,0,4,0,3)T的改进（4）求改进的基本可行解X’’：再转向步骤（2）（2）检验X’’=(6/5,0,17/5,0,0)T是否最优：由最优解判别定理，非基变量检验数σ2,σ4,σ5

都小于0，所以X‘‘=(6/5,0,17/5,0,0)T是最优解表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。

一、单纯形法表CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1n

1CB2xB2b2a21a22…a2j…a2n

2………………………CBnxBnbmam1am2…amj…amn

m检验数j-Z

1

2…

j…

n2.3表格单纯形法①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数

j=Cj-CBPj′，若所有

j≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个

k所对应的系数列向量Pk′≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max{

j｜

j＞0}=

k原则，确定xk为换入变量(进基变量)，再按

规则计算：

=min{bi′/aik′|aik′＞0}=bl′/aik′

确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik′为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0，转第③步。二、单纯形法的计算步骤

例、某航空食品公司利用甲、乙、丙三种原料生产A1、A2、A3和A4四种食品，每月可供应该公司的原料及每种食品可获利情况如下表所示，试求该食品公司每月应如何安排生产计划，才能使总利润最大。

1500300025002000利润（元/吨）2000121丙3003110乙5002211甲每月原料供应量（吨）A4A3A2A1

消耗食品原料解：此问题的线性规划模型为MaxZ=2000x1+2500x2+3000x3+1500x4(1)

x1+x2+2x3+2x4

500(2)x2+x3+3x4

300(3)x1+2x2+x3

200(4)xi

0(i=1,2,3,4)(5)

x1+x2+2x3+2x4+

x5

=

500(2‘)x2+x3+3x4+

x6

=300(3’)x1+2x2+x3 +

x7

=200(4‘)xi

0(i=1,2,…,7)(5’)化为标准型：MaxZ=2000x1+2500x2+3000x3+1500x4(1)s.t.s.t.cBxBbx1x2x3x4x5x6x72000250030001500000x5x6x700050030020010111221123010001000102000250030001500000-z

3000

2503002002001初始单纯形表0-1-1-11000-3-1-2x330001100重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算

cBxBbx1x2x3x4x5x6x72000250030001500000x5x600200121230100010-1-1000-3500150000-3000-z

0

5033.3--1第2单纯形表0-1-11000-3-1-2x3300011001x415001/3-1/3-1/333.30-2/3033.3-1/3-1/3-7/3-4/30-500-2500-500-3000-650000检验数全非正,已经取得最优解,最优解为:X*=(0,0,200,33.3)TZ*=650000计算

非基变量检验数为检验数判别最终单纯形表FinalSimplextableau0

maxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

三、单纯形法计算举例Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9检验数j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解:X*=(4,6,4,0,0)T，Z*=42最优基

Cj35000比值CBXBbx1x2x3x4x50x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1x3x2x1最优基的逆

最优基和最优基的逆2.4人工变量问题用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。一、人工变量

采用人造基的办法：人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。处理方法有两种：大M法两阶段法大M法人工变量开始作为基变量，最后要换出来，全部成为非基变量，问题才有解。假设人工变量在目标函数中的价值系数为-M，M为很大的正数；只要基变量中还存在人工变量，目标函数就不能实现极大化。大M法：引入人工变量xn+i

≥0（i=1,…,m）及充分大正数M

。得到：Maxz=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m

s.t.a11x1+a12x2+…+a1nxn

+xn+1

=b1a21x1+a22x2+…+a2nxn+xn+2=b2...am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn

，xn+1，…，xn+m

≥0显然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解。对应的基是单位矩阵。

结论：若得到的最优解满足

xn+i=0

i=1,…,m

则是原问题的最优解；否则，原问题无可行解。例现有线性规划问题MinZ=-3x1+x2+x3(1)

x1-2x2+x3

11(2)

-4x1+x2+2x3

3(3)

-2x1+x3=1(4)xi

0(i=1,2,3)(5)

x1-2x2+x3+x4

=

11(2‘)

-4x1+x2+2x3

-

x5

+

x6

=3(3’)

-2x1+x3 +

x7

=1(4‘)xi

0(i=1,2,…,7)(5’)解：化为标准型MaxZ’=3x1-

x2

-

x3+0

x4

+0

x5

-

M

x6-

M

x7

(1’)s.t.s.t.大M法求解cBxBbx1x2x3x4x5x6x73-1-100-M-Mx4x6x70-M-M11311-4-2-2101211000-1001000103-6MM-13M-10-M00-z

3M-1

113/2111初始单纯形表010-210-23-1x3-1110重新计算检验数，结果如下页检验数判别换基迭代非基变量检验数为计算

cBxBbx1x2x3x4x5x6x73-1-100-M-Mx4x60-M1-20100-10010-21-M00

--1--1第2单纯形表010103-1x3-11100x2-111-20-2112-50201-3MM-1计算

检验数判别0-11-M-M-11第3单纯形表大M法求解10检验数全非正,已经取得最优解,最优解为:X*=(4,1,9)TZ*=-2（z取极小值-2）cBxBbx1x2x3x4x5x6x73-1-100-M-Mx401-2010-101-2-10

4----1010103x3-110x2-1110-2112-5020计算

检验数判别011-M-M-11第3单纯形表41/3x13-2/32/3-5/30902/3-4/34/3-7/30-1/3-1/31/3-M2/3-M检验数判别-z‘-2最终单纯形表非基变量检验数为

大M法求解0没有单位矩阵，不符合构造初始基的条件，需加入人工变量。人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。大M法

练习

maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：

maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-2101-10M3+4M-1-2-2M00x4x5-M-M24Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24检验数j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1检验数j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2

两阶段法：

引入人工变量xn+i

≥0，i=1,…,m；构造:

Max

z=-xn+1

-xn+2

-…-xn+m

s.t.

a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2

...

am1x1+am2x2+…+amnxn+xn+m

=bmx1,x2...

xn,xn+1,…,xn+m

≥0

第一阶段求解上述问题：

显然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解,它对应的基是单位矩阵。

结论：若得到的最优解满足xn+i=0

i=1,…,m

则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。例（LP）Maxz=5x1

+2x2

+3x3

-x4

s.t.x1+

2x2+

3x3=152x1

+x2

+5x3=20

x1

+2x2

+4x3

+x4

=26

x1

,x2

,x3

,x4

≥0

第一阶段问题（LP-1）

Max

z=-x5

-x6

s.t.

x1+2x2

+3x3

+x5

=152x1

+x2

+5x3

+x6=20

x1

+2x2+4x3

+x4

=26x1,x2,x3,x4,x5,x6

≥0两阶段法：第一阶段(LP-1）得到原问题的基本可行解:(0，15/7，25/7，52/7)T

第二阶段把基本可行解填入表中

得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3毛泽东同志关于做群众工作的经典著作中有这样一个论断：“我们的任务是过河，但是没有桥或没有船，就不能过。不解决桥或船的问题，过河就是一句空话。”所谓“桥”和“船”，其实就是方式方法。这里的大M法和两阶段法就是找到桥和船的方法。思政探讨例求解下列线形规划问题：2.5单纯形表与线形规划解的讨论无可行解引入人工变量x7,x8,并利用大M法求解：

maxZ’=-3x1-2x2-x3-Mx7-Mx8x1+x2+x3+x4=6x1-x3-x5+x7=4x2-x3-x6+x8=3xj≥0,j=1,2,3,4,5,6在第三张