物流运筹学郝海熊德国chap2-线性规划3-22单纯形法

2.2单纯形法单纯形法是解决线性规划问题的根本方法，其原理出自线性代数的矩阵理论，是可按现代计算机标准程序求解线性规划模型的一般方法，分为代数形式的单纯形法和表格形式的单纯形法。前者提供根本算法所依据的逻辑规那么，适用于在电子计算机上进行求解运算；后者将变量和数据列成表格，是本章采用的方法。2.2.1线性规划的有关概念

设线性规划的标准型为其中A是m×n矩阵，且秩r(A)=m，亦即A中至少有一个满秩m×m子矩阵。

解满足系统约束条件的决策向量X=(x1,x2,…,xn)T称为线性规划的解。

可行解满足符号约束条件的解X=(x1,x2,…,xn)T称为线性规划的可行解。

1/29/202412.2单纯形法可行域全体可行解的集合称为线性规划的可行域，一般记作D={X|AX=b,X≥0}。最优解使目标函数到达最小值〔或最大值〕的可行解X*=(x1*,x2*,…,xn*)T称为线性规划的最优解。最优值最优解的目标函数值称为线性规划的最优值。

基假设A中m×m子矩阵B满足r(B)=m,那么称B是线性规划问题的一个基。也就是说，矩阵B是由A的m个线性无关列向量所构成，不妨设为：称Pj(j=1,2,…,m)为基向量。1/29/202422.2单纯形法

基变量、非基变量与其基向量Pj(j=1,2,…,m)相对应的变量Xj(j=1,2,…,m)为基变量，其他决策变量称为非基变量。根本解记基变量为XB=(x1,x2,…,xn)T，非基变量为XN=

(xm+1,xm+2,…,xn)T，称满足方程

组的解XB=B-1b且XN=0为根本解。根本可行解假设根本解XB=

B-1b≥0，那么称该解为根本可行解，也称为基可行解，B为可行基。注与基有关的概念都是相

对的。1/29/20243【例2.8】求出下面线性规划的所有根本解,并指出那些是基可行解.2.2单纯形法解将线性规划模型化为标准型：其中系数矩阵1/29/20244由于X1≥0，所以也

是根本可行解。2.2单纯形法即B1是一个基，

相应的线性规划根本解为X1=(15/4,3/4,0,0)，求其他根本解的过程见下表。1/29/202452.2单纯形法根本解与根本可行解表基基向量基变量非基变量基本解基可行解X1=(15/4,3/4,0,0)是X2=(4,0,3,0)是X3=(5,0,0,-6)不是X4=(0,12,-45,0)不是X5=(0,3,0,18)是

X1=(0,0,15,24)是

一般来说，如果线性规划具有n个变量m个约束，则基本解的数量小于或等于，当然基可行解的数量更不会超过个。1/29/202462.2单纯形法2.2.2单纯形法的理论根底根本概念

凸集设D是n维欧氏空间的一个点集，若任意两点

的连线上的一切点（即集合D中任意两个点其连线上的所有点也都是集合D中的点）；则称D为凸集。

从直观上说，凸集没有凹入部分，其内部没有孔洞。凸组合设是n维欧氏空间中的k个点，若存在，且使

，则称x为的凸组合。

顶点设D是凸集，若且x不能用D中不同的两点

的线性组合表示为，则称x为D的一个顶点（或极点）。

S1S2S31/29/202472.2单纯形法根本定理定理2.1假设线性规划问题存在可行域，那么可行域是凸集。定理2.2线性规划可行域D中的点X是顶点的充要条件为X是基可行解。定理2.3假设线性规划有最优解，那么最优解一定可以在可行域的顶点上得到。【例2.9】指出例2.8中的线性规划根本解与其可行域顶点的对应关系。解见下表的说明及图示。1/29/202482.2单纯形法根本解与其对应的顶点基

变量基本解基可行解顶点X1=(15/4,3/4,0,0)是X2=(4,0,3,0)是X3=(5,0,0,-6)不是X4=(0,12,-45,0)不是X5=(0,3,0,18)是

X1=(0,0,15,24)是1/29/202492.2单纯形法但当m,n较大时，计算工作繁琐庞大，这种方法还是行不通的，所以还要继续讨论如何有效地找到最优解的方法，这就是下面介绍的单纯形法。线性规划问题的所有解构成的集合是凸集，凸集的每一个顶点对应一个基可行解，由于基可行解的个数是有限的（它不大于个），所以顶点的个数也是有限的。若线性规划问题有最优解，必在可行域某顶点上得到，可采用“枚举法”找出所有基可行解，然后一一进行比较，最终就可能找到最优解。2.2.3单纯形法的计算步骤单纯形法是从可行域的一个基可行解出发〔顶点〕，判断该解是否为最优解，如果不是就转移到另一个较好的基可行解，如果目标函数到达最优，那么已得到最优解，否那么，继续转移到其它较好的基可行解。由于基可行解〔顶点〕的数目是有限的，所以经过有限次数的迭代转换后就能求出最优解，如以下图所示。1/29/202410否是否是2.2单纯形法确定初始基可行解判

断解是否最

优是

否有无界

解搜索使目标函数

改善的基可行解结束单纯形法求解步骤流程图定理2.4定理2.5定理2.6初始基可行解确实定1〕假设给定问题标准化后〔且b≥0〕，系数矩阵A中存在m个线性无关的单位列向量，那么以这m个单位列向量构成的单位矩阵B作为初始基，那么XB=B-1b=b≥0，其他xj=0就是初始基可行解。【例2.10】求下面问题的初始

基可行解1/29/2024112.2单纯形法解将线性规划标准化，添加松弛变量x3,x4，得由于有两个单位列向量,可取为初始基，则

就是初始基可行解。

1/29/2024122.2单纯形法2〕假设给定问题标准化后(b≥0)系数矩阵中不存在m个线性无关的单位列向量，那么在某些约束左端加一个非负的人工变量构建一些单位列向量，人工创造一个单位矩阵，参见后面的大M法。

单纯形法的求解定理

线性规划的标准型为不妨设B=(P1,P2,…,Pm)是其中一个基，将有关矩阵和向量分块，记A=(B,N),C=(CB,CN),X=(XB,XN)T为求线性规划的根本最优解，先要求线性规划的根本可行解，这样就需将约束中的基变量用非基变量表示出来。其中A是m×n矩阵，且r(A)=m。1/29/2024132.2单纯形法用B-1左乘约束方程AX=b的两端，得：

将其代入目标函数得:称为非基变量xj的检验数，记为表示该变量增加或减少一个单位所引起目标函数值的变化，它可以用来判断xj将变成基变量后能否改进目标函数值1/29/2024142.2单纯形法上面过程也可以通过线性方程组消元实现:线性方程组其变量为整理得方程组为便于求解，其增广矩阵见下表常数项zXBXNb0BN(1)0-1CBCN(2)用B-1左乘方程组(1)的两端,将XB的系数化为单位矩阵,得下表常数项zXBXNB-1b0B-1B=EB-1N(3)0-1CBCN1/29/202415常数项zXBXNB-1b0B-1B=EB-1N(3)0-1CBCN(2)2.2单纯形法将方程组(3)左乘-CB加到方程(2)两边，得下表常数项zXBXNB-1b0B-1B=EB-1N-CBB-1b-1CB-CBB-1B=OCN-CBB-1N(4)注意(4)中基变量XB、非基变量XN的系数，他们形式结构相似，当前者CB-CBB-1B=O时，后者CN-CBB-1N即为检验数的矩阵形式，也就是说，用消元法将目标函数中基变量的系数化为零的同时，就会得到非基变量的检验数。事实上，CB-CBB-1B也可看成基向量的检验数，应用消元法后，当基向量的检验数变为零时，非基变量的系数CN-CBB-1N就是其检验数。1/29/2024162.2单纯形法线性规划单纯形法求解有下述定理：

定理2.4（最优解判定定理）对某基可行解XB=B-1b其他xj=0，若所有的，则该解为最优解。定理2.5（无界解判定定理）若对某可行基B,存在

且，则该线性规划问题有无界解。

定理2.6〔换基迭代定理〕1）给定某可行基B,对矩阵A的行列来说,通过下面步骤：

①确定进基变量：，选择k列的非基变量xk为进基变量；

②按最小比值原则确定出基变量：

（最小值不唯一时任选一个行标l作为），其中(B-1b)i表示向量B-1b的第i个元素，选择l行对应的基变量xl为出基变量，那么Pk替换B中出基变量所在的列后就能得到一个新的可行基。

1/29/2024172.2单纯形法2）对线性方程组AX=b的增广矩阵实施初等行变换：

①第l行元素同除以主元alk，使主元变为1；

②使主元所在列的其它元素变为0，这样就得到可行基

对应的基可行解，并且所对应的目标函数值增加。

单纯形表为便于表达单纯形法的计算过程，上述计算过程可以在单纯形表上完成。每个可行基B都可构造出一个单纯形表，一般将其化为单位矩阵后再列出单纯形表，见下表

1/29/2024182.2单纯形法CBXBB-1bc1c2…cmcm+1…cnθx1x2…xmxm+1…xnc1x1b110…0a1m+1…a1nc2X2b201…0a2m+1…a2n……………………………cmxmbm00…1amm+1…amm检验数σ00…0σm+1…σn表中：XB一列记录基变量；CB一列跟踪基变量对应的价值系数；B-1b为基可行解；其余各列为B-1Pj(j=1,2,…,n)，最后一行是每个变量对应的检验数。大方框中元素就是增广矩阵，这样求解线性规划就可以在单纯形表中实现，单纯形表包含了线性规划求解的全部信息。1/29/2024192.2单纯形法【例2.11】用单纯形法求例2.8的最优解b2100x1x2x3x4153510246201BXBNXN153510246201EB-1NB-1b填入下面初始单纯形表：1/29/2024202.2单纯形法CBXBB-1b2100θx1x2x3x4153510246201检验数σx3x4002154[]检验数σx3x102411/301/63041-1/21/3-1/33/412[]检验数σ

x2x1123/4011/4-1/815/410-1/125/24-1/24-7/24X*=(15/4,3/4)z*=33/41/29/2024212.2单纯形法【例2.13】用单纯形法求解线性规划解将线性规划标准化，得1/29/2024222.2单纯形法CBXBB-1b24000θx1x2x3x4x54-12100101201021-1001检验数σ检验数σx3x4x50002425-[]x2x4x54002-1/211/200620-11041/201/2014-2-38[]1/29/2024232.2单纯形法CBXBB-1b24000θx1x2x3x4x54x22-1/211/200-0x4620-11030x541/201/2018检验数σ4-2检验数σ[]x2x1x54207/2011/41/40310-1/21/205/2003/4-1/410-2X1*=(3,7/2,0,0,5/2)

z*=2014-10/3[]值得注意的是，在最终单纯形表中，除基变量的检验数为零外，非基变量x3的检验数也为零，意味着假设让x3取值变化不会使目标函数值有所改变。这时如果让x3进基并继续迭代，就会得到另一个根本可行解。1/29/2024242.2单纯形法CBXBB-1b24000θx1x2x3x4x54x27/2011/41/40142x1310-1/21/20-0x55/2003/4-1/4110/3检验数σ0-2检验数σ[]x2x1x34208/30101/3-1/314/31001/32/310/3001-1/34/30-2X2*=(14/3,8/3,10/3,0,0)

z*=20根据最优解的定义，使目标函数到达最大值的任一可行解都是一个最优解。所以该线性规划有多个最优解，其最优解的一般表达式为这种情况为线性规划问题具有多重最优解。一般说来，但凡在最优单纯形表中出现检验数为零的非基变量，就存在多个最优解。1/29/2024252.2单纯形法2.2.4单纯形法的进一步讨论单纯形法的求解根底是能够找到线性规划的可行解，如何找到这个可行解呢？这里学习构造初始可行解的大M法

大M法在用单纯形法求解线性规划问题时，首先要确定一个初始可行基〔一般是单位矩阵〕。假设其系数矩阵中已有一个单位矩阵，那么可以作为初始可行基；假设不存在单位矩阵，那么可以采用在每个约束等式中人为地添加一个非负变量〔称为人工变量〕的方法，来构造另外一个线性规划问题，下面通过实例说明如何使用大M法。【例2.14】求解线性规划1/29/2024262.2单纯形法解将线性规划标准化，得它的系数矩阵为在第二、三个约束方程的左边添加人工变量x6,x7≥0

，就构成一个系数矩阵中含有单位矩阵的新的线性规划问题:

矩阵中A有一个单位矩阵列，但不含有单位矩阵。1/29/2024272.2单纯形法

只有当所添加的人工变量取值为0时，该线性规划才和原规划等价。为此，在目标函数中对人工变量的价值系数进行惩罚，使其在求解过程中取值为零，最好为非基变量，所以在求max问题中，人工变量在目标函数中的系数均为-M；在min问题中，人工变量在目标函数中的系数均为M，这里M是一个任意大的正数。大M法也叫罚系数法，利用大M法的关键在于如何能够尽快将人工变量替换出基。

添加人工变量后构成的新的线性规划为:-Mx6-Mx71/29/2024282.2单纯形法添加人工变量后构成的新的线性规划为:-Mx6-Mx7这样，就可以将人工变量视为基变量，得到一个初始基可行解，就可用单纯形法进行迭代计算。如果假设经假设干次迭代，人工变量被全部替换出了基，那么原问题的约束条件得到恢复，同时也有了一个根本可行解，原规划单纯形求解的初始条件就已具备，可继续采用单纯形表求解。1/29/2024292.2单纯形法CBXBB-1b3-1-100-M-Mθx1x2x3x4x5x6x7111-2110003-4120-1101-2010001检验数σ检验数σx4x6x70-M-M3-6MM-13M-1-M111.51x4x6x30[]-M-11-2010001103-20100-110100-11-21M-1-M1-2M-1-[]1/29/2024302.2单纯形法CBXBB-1b3-1-100-M-Mθx1x2x3x4x5x6x70x4103-20100-1--Mx