单纯形法矩阵变换

◼1.5 求解线性规划问题的单纯形法➢LP问题的几何意义➢单纯形法的经济解释➢单纯形法的计算步骤❖基本概念为凸集。

则称若设K K XXK XK X),10( )1( ,,)2()1()2()1(≤≤∈−+∈∈ααα 1、凸集：在某个点集K 中任给出两点，若连接这两点的线段上的一切点也在此点集中。

即2、顶点：不能用不同的两点的线性组合表示的点。

➢LP 问题的几何意义❖基本定理➢LP问题的可行域是凸集。

➢可行解X=(x,x2,…,x m,0,…,0)T是基本可行解的充要条件是X1的非零分量所对应的系数列向量是线性无关的➢基本可行解对应可行域的顶点➢有可行解必有基本可行解，即凸集非空、有顶点➢最优解一定在可行域的顶点上得到（必定在基本可行解中）例设有一家具厂用木材和钢材生产A,B,C 三种家具，生产一件家具所需的材料、每件家具可获得的利润以及每月可供的木材和钢材数量如下表，问此家具厂应如何安排各种家具的生产量才能使企业获得最大的利润？产品木材钢材单位产品获利（元）A B C3 21 14 4415材料可供量8000 3000解：设A,B,C 三件家具的产量(件数)分别为x 1,x 2,x 3，有：⎪⎩⎪⎨⎧=≥≤++≤++++=3,2,1,0300042800043..54321321321j x x x x x x x t s x x x MaxZ j➢单纯形法的经济解释模型的标准型为：⎪⎩⎪⎨⎧=≥=+++=+++⋅+⋅+++=5,4,3,2,1,0300042800043..00545321432154321j x x x x x x x x x t s x x x x x MaxZ j系数矩阵和基：⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡=10011041201413B A 取则：x 4, x 5为初始基变量; x 1, x 2x 3为非基变量，变换标准型的约束条件：⎩⎨⎧−−−=−−−=32153214423000438000x x x x x x x x 代入目标函数：Z = 0 + 4x 1+ x 2+ 5x 3令非基变量等于0，基变量x 4=8000, x 5=3000)3000,8000,0,0,0()0(==Z XT初始基本可行解经济解释观察目标函数：321540x x x Z +++=选x 3入基，x 1, x 2仍为非基变量且为0，代入上方程组：75043000,48000min 04300004800033534=⎭⎬⎫⎩⎨⎧=⎩⎨⎧≥−=≥−=x x x x x 则：则：基变量为x 4, x 3;非基变量为x 1, x 2x 5，变换标准型的约束条件：⎪⎩⎪⎨⎧−−−=+−=⇒⎩⎨⎧−−−=−−=+521351452132143414121430005000230004380004x x x x xx x x x x x x x x x 代入目标函数：Z = 3750 + 1.5x 1－0.25x 2－1.25x 5 令非基变量等于0，基变量x 3=750,x 4=50003750)0,5000,750,0,0()1(==Z XT基本可行解当x 3=750时，x 5=0即为非基变量，x 4=5000观察目标函数：5214541233750x x x Z −−+=选x 1入基，x 2, x 5仍为非基变量，且为0，代入上方程组：{}15002*750,5000min 0217500500011314==⎪⎩⎪⎨⎧≥−=≥−=x x x x x 则：则：基变量为x 1, x 4; 非基变量为x 2, x 3x 5，变换标准型的约束条件：⎪⎪⎩⎪⎪⎨⎧−−−=+++=⇒⎩⎨⎧−−−=−−=+5321532453213241212211500232213500430002480003xx x x x x x x x x x x x x x x 代入目标函数：Z = 6000 －x 2－3x 3－2x 5 令非基变量等于0，基变量x 1=1500, x 4=35006000)0,3500,0,0,1500()2(==Z XT最优解当x 1=1500时，x 3=0即为非基变量，x 4=3500将问题化标准型，求出初始基本可行解，建立初始单纯形表是否最优？是否无解？最优解YNY无解N确定换入变量、换出变量，迭代，得到一个新的基本可行解➢单纯形法的计算步骤例线性规划问题的标准型：⎪⎩⎪⎨⎧=≥=+++=+++⋅+⋅+++=5,4,3,2,1,0300042800043..00545321432154321j x x x x x x x x x t s x x x x x MaxZ j初始单纯形表：∑='=mi iji j a c Z 1c j → 41 5 0 0 C ’ B X B b x 1 x2 x3 x4 x5 0 0X 4 X 5 8000 30003 2 1 14 4 1 0 0 1 Z j C j – Z j0 40 10 50 00 0初始解为X=(0,0,0,8000,3000)Z=0检验数表达式推导：∑∑∑∑∑∑∑∑∑∑+=+====+=+=+==+=−+='−+'=+−'=+'=−=nm j jj jnm j jm i ij i j mi i imi nm j jjnm j j iji inm j j jmi i i nm j jiji i x z cZ x a c c b cx cx ab cx cx c Z m i x ab x 10111111111)()()(),,2,1(＝代入目标函数式： ➢判别式：MaxZ: c j –z j ≤ 0 (对于所有的非基变量）问题达到最优；换入变量的确定：{}入基K K K j j x Z c Z c Max ⇒−=>−0换出变量的确定：出基L LKLik ik i x a b a a b Min ⇒=⎭⎬⎫⎩⎨⎧>=0,θ系数矩阵的变换：按照增广矩阵的变换规则，将基变量的系数矩阵转化为单位矩阵，非基矩阵和资源向量作相应的变化。

单纯形法的矩阵描述
考虑将单纯形法的求解过程⽤矩阵进⾏描述，对于已经引⼊松弛变量的 LP 问题，其约束条件
BX B+NX N=b
⽬标函数
C B X B+C N X N=z
联⽴消去X B得
z=C B B−1b+(C N−C B B−1N)X N
其中C N−C B B−1N就是所谓的检验数σ。

因此，单纯形表可以描述为
基变量X B⾮基变量X N右侧 RHS
系数矩阵I B−1N B−1b
检验数0C N−C B B−1N−C B B−1b
任意时刻各个部分的核⼼是某个已知矩阵的部分左乘⼀个B−1，因此求解的核⼼在于快速地维护B−1。

以下我们设P k是x k对应的原始系数矩阵的那⼀列。

我们有递推式
B−1i=E i B−1i−1
其中E i是把⼀个单位矩阵中，第j列替换为ξi后的结果，其中j表⽰本次新换⼊的基在B i中对应第j列，ξi由本次换⼊变量在换⼊前B−1i−1N i−1中对应的列 (a1,a2,...,a m) 变换得到，设l是换出变量对应的⾏，则
ξi=(−a1
a l
,...,
1
a l
,...,−
a m
a l
)
于是，
B−1i=(e1,...,e j−1,ξi,e j+1,...,e m)B−1i−1换⼊变量求解根据检验数
σi=C N
i −C B
i
B−1i N i
中找最⼩值下标即可得到，换出变量根据θ法则求θ=min
即可得到。

Loading [MathJax]/jax/element/mml/optable/BasicLatin.js。

第二章单纯形法2.1 单纯形法原理（大M法）例3 min z＝4x1＋3x2＋8x3x1＋x3≥2x2＋2x3≥5x j≥0（j=1，2，3）一、构造初始可行基（m×m单位阵）每个约束都有一个系数为+1的独有变量（基变量）1．引入附加变量，化为标准型（首先变为b≥0）x1＋x3－x4＝2x2＋2x3－x5＝5x j≥0（j=1，2，...,5）（x4、x5为附加变量）min z＝4x1＋3x2＋8x3＋0x4＋0x5假设化为标准型后,仍无初始可行基2. 若约束中附加变量系数为-1或原约束为等式，必须引入人工变量x1＋x3－x4＋x6＝2 ① (基变量为x6)x2＋2x3－x5＋x7＝5 ② (基变量为x7)x j≥0（j=1，2，...,7）（x6、x7为人工变量）人工变量>0时，约束被篡改3. 目标函数中附加变量系数为0，而人工变量系数为Mmin z＝4x1＋3x2＋8x3＋0x4＋0x5＋M x6＋M x7③M——罚因子（很大正数）大M法——罚函数法二、求出一个基本可行解1. 用非基变量表示基变量和目标函数由①：x6＝2－x1－x3＋x4④由②：x7＝5－x2－2x3＋x5⑤将④、⑤代入③：z＝(4-M)x1＋(3-M)x2＋(8-3M)x3＋M x4＋M x5＋7M ⑥检验数σj= ⑥式中各非基变量x j的系数，z＝z0＋∑σ∈Jj jj x（J为非基变量下标的集合）基变量的检验数＝02、求出一个基本可行解及相应z值令各非基变量为0，x1＝x2＝x3＝x4＝x5＝0由④、⑤、⑥得x6＝2，x7＝5，z＝7M三、最优性检验（求min）1．最优性检验的依据——检验数σｊ2．最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数σｊ≥0，且人工变量为0，则这个基本可行解是最优解。

例3中，σ１＜0，σ２＜0，σ３＜0，需继续迭代3．无穷多组最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数σｊ≥0，又有某个非基变量检验数为0，且人工变量为0，则线性规划问题有无穷多组最优解。