运筹学单纯形法

运筹学单纯形法演示文稿目前一页\总数五十八页\编于五点1.线性规划问题的解(1)解的基本概念定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。目前二页\总数五十八页\编于五点基阵非基阵基向量非基向量基变量非基变量目前三页\总数五十八页\编于五点令则定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。目前四页\总数五十八页\编于五点定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。定义在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为非退化解，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题；若基本可行解中，有基变量为零，则称为退化解，该问题称为退化的线性规划问题。基本解中最多有m个非零分量。基本解的数目不超过个。目前五页\总数五十八页\编于五点非可行解解的集合：可行解基本解最优解基本可行解解空间目前六页\总数五十八页\编于五点(2)解的基本性质判别可行解为基可行解的准则定理1线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关.线性规划问题的基本定理:定理2和定理3定理2线性规划问题有可行解,则它必有基可行解.定理3若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.目前七页\总数五十八页\编于五点几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.目前八页\总数五十八页\编于五点2单纯形法例1MaxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(1)单纯形法的引入目前九页\总数五十八页\编于五点解：(1)、确定初始可行解B=(P3P4P5)=IZ=0+40X1+50X2X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2令X1=

X2=0X(1)=(0,0,30,60,24)TZ(1)=0目前十页\总数五十八页\编于五点(2)、判定解是否最优Z=0+40X1+50X2当X1从0↗或X2从0↗Z从0↗∴X(1)不是最优解目前十一页\总数五十八页\编于五点(3)、由一个基可行解→另一个基可行解。∵50>40选X2从0↗，X1=0X3=30-2X20X230/2

X4=60-2X20X260/2

X5=24-2X20X224/2

X2=min(30/2,60/2,24/2)=12X2：进基变量，

X5：出基变量。目前十二页\总数五十八页\编于五点B2=(P3P4P2)Z=0+40X1+50X2④X3+2X2=30-X1①X4+2X2=60-3X1

②2X2=24-X5③目前十三页\总数五十八页\编于五点③×1/2

，③代入④式，①－③，②－③Z=600+40X1-25X5X3=6-X1+X5X4=

36-3X1+X5X2=12-1/2X5令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=600目前十四页\总数五十八页\编于五点(2)'

判断∵40>0∴X(2)不是最优解。(3)'

选X1从0↗，X5=0X3=6-X10

X4=

36-3X10

X2=120

X1=min(6/1,36/3,&)=6X1进基，

X3出基。目前十五页\总数五十八页\编于五点B3=(P1P4P2)Z=840-40X3+15X5X1=6-X3+X5X4=

18+3X3-2X5X2=12-1/2X5令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=840目前十六页\总数五十八页\编于五点(2)"∵15>0∴X(3)不是(3)"

选X5从0↗，X3=0X1=6+X50

X4=

18-2X50

X2=12-1/2X5

0

X5=min(18/2,12/1/2)=9X5进基，

X4出基。目前十七页\总数五十八页\编于五点B4=(P1P5P2)Z=975-35/2X3-15/2X4X1=15+1/2X3-1/2X4X5=

9+3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=975目前十八页\总数五十八页\编于五点0(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2)X(3)Z=40X1+50X2目前十九页\总数五十八页\编于五点单纯形法小结：单纯形法是这样一种迭代算法——如下图…

当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。X1Z1保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增X2X3...XkZ2Z3...Zk

当Zk中非基变量的系数全为负值时，这时的基本可行解Xk

即是线性规划问题的最优解，迭代结束。目前二十页\总数五十八页\编于五点(2)线性规划的典则形式标准型目前二十一页\总数五十八页\编于五点目前二十二页\总数五十八页\编于五点(3)最优性判别定理在线性规划问题的典式中，设

X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若有

j0(j=m+1,m+2,…,n)则X(0)是线性规划问题的最优解，基B为最优基。证：设X为线性规划问题的一个可行解，必有

X0，当j0，则X

0Z*=CX(0)=Z(0)Z(0)+

X=CX

故X(0)为线性规划问题的最优解。目前二十三页\总数五十八页\编于五点在线性规划问题的典式中，设X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若有

j

0(j=m+1,m+2,…,n

)且j+k=0

则线性规划问题有无穷多个最优解。无穷多最优解判别定理在线性规划问题的典式中，设X(0)

为对应于基B的一个基可行解，若某一非基变量xj+k的检验数

j+k>0

且对应的列向量

P’m+k=(a1,m+k,a2,m+k,…,am,m+k)0则线性规划问题具有无界解，即无有限最优解。无界解判别定理目前二十四页\总数五十八页\编于五点(4)基可行解改进定理在线性规划问题的典式中，设

X(0)=(x1,x2,…,xm,0,…,0)为对应于基B的一个基可行解，若满足以下条件：某个非基变量的检验数

k>0(m+1kn);aik(i=1,2,…,m)不全小于或等于零，即至少有一个aik>0(1km);bi’>0(I=1,2,…,m),即X(0)为非退化的基可行解。则从X(0)出发，一定能找到一个新的基可行解X(1)，使得CX(1)>CX(0)

。目前二十五页\总数五十八页\编于五点(5)单纯形表

将线性规划问题典式中各变量及系数填写在一张表格中，该表即为单纯形表。cj

c1c2…cn00…0SCB基x1x2…xnxn+1xn+2…xn+m0000xn+1xn+2…xn+ma11a12…a1n1a21a22…a2n1……………am1am2…amn1b1

b2…

bm12…mzjj=cj–zj00…000…01

2…

nn+1

n+2…n+m0S目前二十六页\总数五十八页\编于五点单纯形方法的矩阵表示BNIbCBCN00IB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1b目前二十七页\总数五十八页\编于五点对应I式的单纯形表——I表(初始单纯形表)对应B式的单纯形表——B表迭代IB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1bBNIbCBCN00价值系数cjCBCN0Sθ基系数基XBXNXSCBXBIB-1NB-1B-1bzj检验数σjCB0CBB-1NCN-CBB-1NCBB-1-CBB-1S-CBB-1b当CN-CBB-1N≤0时，即为最优单纯形表价值系数cjCBCN0Sθ基系数基XBXNXS0XsBNIbzj检验数σj0CB0CN000S目前二十八页\总数五十八页\编于五点(1)、确定初始基域初始基本可行解,列出初始单纯形表(3)、若有j>0，Pj全

0，停止，没有有限最优解；否则转(4)(2)、对应于非基变量检验数j全小于零。

若是，停止，得到最优解；若否，转(3)。(6)单纯形法的迭代步骤目前二十九页\总数五十八页\编于五点θ=minaim+k>0=biaim+kbrarm+k定Xr为出基变量，arm+k为主元。由最小θ比值法求：Maxj=m+k→Xm+k进基变量j

0(4)、目前三十页\总数五十八页\编于五点转(2)a1m+k0a2m+k0ar,m+k1amm+k0初等行变换Pm+k=…………(5)、以arm+k为中心，换基迭代从步骤(2)-(5)的每一个循环，称为一次单纯形迭代.目前三十一页\总数五十八页\编于五点单纯形表计算步骤举例给定线性规划问题例1Maxz=50X1+30X24X1+3X2≤

120s.t2X1+X2

≤50X1，X2

≥0Maxz=50X1+30X24X1+3X2+X3=

120s.t2X1+X2+X4=50X1，X2

，X3

，X4

≥0目前三十二页\总数五十八页\编于五点cj503000SθcBxBx1x2x3x40x34310120120/40x4(2)1015050/2zjσj05003000000S0x30(1)1-2202050x111/201/22550zjσj002550025-251250S-125030x2011-22050x110-1/25/215zjσj5003005-515-151350S-1350初始基最优单纯形表B-1初始基可行解最优值初始单纯形表唯一最优解目前三十三页\总数五十八页\编于五点例2目前三十四页\总数五十八页\编于五点cj4080000SθcBxBx1x2x3x4x50x31210030150x43201060300x5020012412zjσj0400800000000Scj4080000SθcBxBx1x2x3x4x50x31010-1660x43001-1361280x201001/212Zjσj040800000040-40960S-960目前三十五页\总数五十八页\编于五点cj4080000SθcBxBx1x2x3x4x540x11010-160x400-31218980x201001/21224zjσj40080040-4000001200S-1200cj4080000SθcBxBx1x2x3x4x540x110-1/21/20150x500-3/21/21980x2013/4-1/4015/2zjσj40080040-400000SS-1200达到最优状态时，若存在非基变量为零，则为有无穷多最优解目前三十六页\总数五十八页\编于五点例3目前三十七页\总数五十八页\编于五点cj2100SθcBxBx1x2x3x40x31110550x41-10100zjσj020100000S0x3021-155/22x11-1010zjσj00-23002-20S1x2011/2-1/25/22x1101/21/25/2zjσj00003/2-3/21/2-1/215/2S-15/2Θ可以为零目前三十八页\总数五十八页\编于五点例4例5无法获得初始基和初始基可行解目前三十九页\总数五十八页\编于五点3求初始基的人工变量法求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解，以它作为迭代的起点。获得初始可行基及初始基可行解的途径主要有：(1)试算法；(2)人工变量法。在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵。目前四十页\总数五十八页\编于五点约束条件：

a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2

=b2

...am1x1+am2x2+…+amnxn+xn+m

=bm

x1，x2，…，xn,xn+1,…,xn+m

≥0s.t人工变量人工基目前四十一页\总数五十八页\编于五点等价否？目前四十二页\总数五十八页\编于五点大M法两阶段法目前四十三页\总数五十八页\编于五点大M法与二阶段法的一些说明由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。大M法实质上与原单纯型法一样，M可看成一个很大的常数人工变量被迭代出去后就不会再成为基变量当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解大M法手算很不方便，因此提出了二阶段法计算机中常用大M法二阶段法手算可能容易目前四十四页\总数五十八页\编于五点例6大M法目前四十五页\总数五十八页\编于五点cj3-1-100-M-MSθcBxBx1x2x3x4x5x6x70x41-2110001111-Mx6-4120-11033/2-Mx7-201000111zjσj6M-6M+3MM-1-3M3M-100M-M-M0-M0-4MS+4Mcj3-1-100-M-MSθcBxBx1x2x3x4x5x6x70x43-20100-110-Mx60100-11-211-1x3-20100011zjσj21-MM-1-1000M-M-M02M-1-3M+1-M-1S+M+1目前四十六页\总数五十八页\编于五点cj3-1-100-M-MSθcBxBx1x2x3x4x5x6x70x43001-22-5124-1x20100-11-21-1x3-20100011zjσj21-10-10001-1-1-M+11-M-1-2S+2cj3-1-100-M-MSθcBxBx1x2x3x4x5x6x73x11001/3-2/32/3-5/34-1x20100-11-21-1x30012/3-4/34/3-7/39zjσj30-10-101/3-1/31/3-1/3-1/3-M+1/3-2/3-M+2/32S-2最优解人工变量被迭代出去后就不会再成为基变量目前四十七页\总数五十八页\编于五点例4目前四十八页\总数五十八页\编于五点cj2400-MSθcBxBx1x2x3x4x5-Mx521-101840x4-210102zjσj-2M2+2M-M4+MM-M00-M0-8MS+8M2x111/2-1/201/2480x402-111105zjσj2013-11001-M-18S-82x110-1/4-1/41/43/24x201-1/21/21/25zjσj2040-5/25/23/2-3/25/2-M-5/226S-26未达到最优状态，但无法继续改进，即无有限最优解目前四十九页\总数五十八页\编于五点例5cj320-MB-1bθcBxBx1x2x3x4-Mx4-1-1-111σj-M+3-M+2-M0-M已达到最优状态，但基变量中的人工变量未退出，故无可行解目前五十页\总数五十八页\编于五点例6(2)两阶段法目前五十一页\总数五十八页\编于五点第一阶段cj00000-1-1B-1bθcBxBx1x2x3x4x5x6x70x41-2110001111-1x6-4120-11033/2-1x7-201000111σj-6130-100-4目前五十二页\总数五十八页\编于五点cj00000-1-1B-1bθcBxBx1x2x3x4x5x6x70x43-20100-