2.2单纯形法的表格解法

250分悬赏线性规划问题（单纯形法）~

一、线性规划单纯形法的概念

（一）线性规划单纯形解法的基本思路

若一个凸集仅包含有限个极点，则称此凸集为单纯形。
线性规划的可行域是单纯形（证明略，但可以从上节图解法的例子得到认同），进而线性规划的基可行解又与线性规划问题可行域的极点1-1对应（定理2.2.2）， 线性规划单纯形法就是基于线性规划可行域的这样的几何特征设计产生的。这个方法最初是在20世纪40年代由George Dantzig研究出来的。这个线性规划单纯形解法的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行域中对应的极点为出发点，根据最优准则判断这个基可行解是否是最优解，如果不是转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下降，这样重复进行有限次后，可找到最解或判断问题无最优解。

（二）单纯形法的最优准则

设：线性规划（LP）为：


min cx
s.t. Ax=b
x≥0


A为（LP）的约束方程组的m*n阶系数矩阵（设n≥m），A的秩为m；B是线性规划的一个基，不失普遍性，记





定义





则：称λ，或者λj,(j=1,2,…,n)为检验数。

若：λ≤0，即全部λi非正，
则：由B确定的基可行解是（LP）的最优解。
（参看附录2.3.1）


二、线性规划单纯形法的表格解法

较简单的线性规划可以采用单纯形法的表格形式，这样利用计算器就可求解。单纯形法的表格解法的基本思路是，对基可行解建立单纯形表，依据此表作最优解判断，以及从原基可行解向目标值更小的新可行解转换的计算。

对于由基阵B确定的基可行解，其单纯形表为表2.3.1形式。对于初始基可行解，其单纯形表的构建方法为：先建立表2.3.2形式的表格，然后应用“行变换”将表2.3.2中的前m列，即基变量对应的列





转换为





其中0是m元0向量：0=(0,0,…,0), 是m阶单位方阵。在这样的行变换下，表2.3.2将转换为表2.3.1


表2.3.1

检验数

基变量
cBB-1A-c cBB-1b
xB B-1A B-1b


表2.3.2

检验数

基变量
-cB -cN o
xB B N B-1b


（参看附录2.3.2）


（一）直接求解
对如下形式的较简单的线性规划可直接采用单纯形法的表格形式求解：


min cx
s.t. Ax≤b
x≥0


这种形式的线性规划标准化后，为


min cx+ox'
s.t. Ax+lx'=b
x≥0,x'≥0

其中x'=(x1',x2',…,xm')为松驰变量，而o=(0,0,…,0)T 。现在新的约束矩阵为





因为I是m*n的单位矩阵。所以我们就可用这个矩阵作基阵，松驰变量是基变量，立即得到一个初始基可行解，其目标函数值为0，而相应的初始单纯形表如表2.3.3所示。表中


θ=o=(0,0,…,0)T,


从而可开始单纯形表上求解的过程。


表2.3.3

检验数

基变量
-c θ o
A I b


下面我们通过一个实例看单纯形表解线性规划问题的一般步骤


例2.3.1 用直接法求解（LP）


max z=40x1+45x2+24x3
s.t. 2x1+3x2+x3≤100
3x1+3x2+2x3≤120
x1,x2,x3≥0


解：
第一步 先将原问题化为标准形式


min -z=-40x1-45x2-24x3
s.t. 2x1+3x2+x3+x4=100
3x1+3x2+2x3+x5=120
x1,x2,x3,x4,x5≥0


第二步 列出初始单纯形表




x1 x2 x3 x4 x5
40 45 24 0 0 0
x4 2 3 1 1 0 100
x5 3 3 2 0 1 120


此时，基可行解(0,0,0,100,120)T为，目标函数值为0.


第三步 检查检验数


故



λ=(40,45,24,0,0)≥0


因此基可行解不是最优解，要进行基的转换。

线性规划检验数的定义和最优解的单纯形法检验准则：
检验数定义为


若 基可行解对应的λ为检验数为非正向量，即


则 此可行解为最优解。
当大于零的检验数不止一个，理论上可任选一个正检验数对应非基变量为进基变量，一般情况选取最大正值的检验数对应的非基变量为进基变量，这样迭代常常会快一些。为此，我们选x2进基，因为





因此，x4为离基变量，则新的基变量为x2，x5。


第四步 建立新的基相应的单纯形表

建立单纯形表的方法：
在计算过程中，只要将A中基变量对应的列组成的子矩阵
通过行变换化成单位阵，基变量对应的检验数化成零即可。

如何从原来的表转到新的基相应的单纯形表呢？只要把A中x2相应的列向量通过初等变换化成单位向量即可。因此在上表中只要把x2对应的列





化成





我们称基变量x4所在行和非基变量x2所在列相交元素为变换轴心，用加＊表示，现在这数为3，将这行乘以（-1）加到第三行，乘以（-15）加到第一行，然后将这行行除以3，得一个新的单纯行表




x1 x2 x3 x4 x5
10 0 9 -15 0 -1500
x2 2/3 1 1/3 1/3 0 100/3
x5 1* 0 1 -1 1 20


这样我们作了一次转换，新的基可行解为(0,100/3,0,0,20),目标函数值为-1500。

现在再回到第三步。现在λ1=10,λ3=9均大于零，仍不是最优解，取x1进基；

因为：





所以，x5离基。




x1 x2 x3 x4 x5
0 0 -1 -5 -10 -1700
x2 0 1 -1/3 1 -2/3 20
x1 1 0 1 -1 1 20


现在所有检验数均小于等于零，这个基可行解（20，20，0，0，0）是最优解，原问题最优值1700.以后。

实际在表上作业时，求λk与xr的过程可不写，这些表可连在一起。

（二）单纯形法求解的基本步骤

首先我们需要对单纯形表作进一步的认识，注意到检验数：





可见，对应于基变量的λj=0(j=1,2,∧,m)，而且





再记





进而记





这样单纯形表2.3.1可呈现为表2.3.4的形式：


表2.3.4

x1 x2 … xm xm+1 … xn
检验数

基变量
0 0 … 0 λm+1 … λn f0
x1 1 0 … 0 y1m+1 … y1n
x2 0 1 … 0 y2m+1 … y2n
… … … … … … … … …
xm 0 0 … 1 ymm+1 … ymn


有了表2.3.4，单纯形表上解法的一般步骤为：

步一：把线性规划模型变成它的标准形式；

步二：确定初始基可行解，建立初始单纯形表；

步三：检查对应于非基变量的检验数λj,(j∈N)；若所有这些λj均小于零，则已得到最优解，停止计算，否则转入下一步；

步四：在所有的λj>0中，若有一个λk在单纯形表上对应的列向量的全部元素yik≤0(i=1,2,…,m)，则此问题无解，停止计算；否则转入下一步；

步五：根据max{λj>0|j∈N}=λk, 即确定λk对应的非基变量λk为进基变量；再根据





确定基变量xr为离基变量；

步六：基可行解的转换运算，即实施行变换，将单纯形表上xk对应的列向量变换为单位向量，其中包括将λk变换为0，而原yrk变换为1，称元素yrk为变换轴心。

（三）两阶段法

对一般的线性规划，往往不会象用直接法求解形为Ax≤b的线性规划那样，能够很容易找到初始基可行解，甚至连有无可行基都难以判定，这时就需要应用两阶段法来求解线性规划。

二阶段法就是把解线性规划问题划分为两个阶段，第一阶段求出原问题的一个基可行解或判断原问题可行域为空；第二阶段在得到的基可行解基础上求解原问题。方法如下：

第一阶段
人为地在原约束矩阵中增加一些变量使得到单位矩阵，增加的变量称为人工变量，目标函数是人工变量之和。具体而言，对于原线性规划标准化后的Ax=b,(b≥0)的形式，若A中不包括单位矩阵，则我们在每个方程后面加一个“人工变量”得到一个新的线性规划（LP）如下：





（当A中有一些单位向量时，人工变量可少于m个）

为书写方便我们记（LP0）为：





其中Em=(1,1,K,1),分量全为1的m元横向量，





这儿Im是可行基，又因为xa≥目标函数Emx有下界0，所以（LP0）一定有最优解。设最优解为：





则可能有三种情形：

(1)若：在最优解x0的基变量中，不存在人工变量，即人工变量xn+1,xn+2,…,xn+m都是非基变量。
则：x0的前n个分量(x10,x20,K,xn0)便是原线性规划问题的一个基可行解。可进入第二阶段。

(2)若：在最优解x0的基变量中，包括某些人工变量，并且最优值z>0。
则：原线性规划可行域为空，原线性规划无解。

这是因为，否则可设原规划有可行解(x1*,x2*,…,xn*),
则(x1*,x2*,…,xn*,0,…,0)是（LP0的可行解，其目标函数值
为0，这与最优值大于零矛盾。

(3)若：在最优解x0的基变量中，包括某些人工变量，但最优值z=0，即，此时为基变量的人工变量都取值为0。
则：设xn+1是一个人工变量的基变量，其在最优解的单纯形表中对应第S行，设J是非人工变量中非基变量的下标集。

① 如果单纯形表的第S行中，所有的ysk=0,(k∈J)此示原约束Ax=b中第S行为其余行的线性组合，即是个多余的约束，应当删去；

② 如果存在ysk≠0 (k∈J),
则无论ysk是正还是负，以它为变换轴心，xk进基，xn+1离基.如果新表中的基变量中还有人工变量，重复以上步骤，有限次可得到（1）的情形。


第二阶段

步1：以第一阶段最优解对应的单纯形表为基础，删去人工变量对应的列，并且将原规划（已标准化）的-c作为检验数，放在第一行，然后用用行变换将基变量对应的检验数消为零。

步2：以步1结束时建立单纯形表为原线性规划的初始单纯形表，求解原线性规划。

[例2.3.2] 用二阶段法求解（LP）：


min x1-2x2
s.t. x1+x2≥2
-x1+x2≥1
x2≤3
x1,x2≥0


解：
先标准化：


min x1-2x2
s.t. x1+x2-x3=2
-x1+x2-x4=1
x2+x5=3
x1,x2,x3,x4,x5≥0

第一阶段：
因为A中 对应单位向量





，故只要引进两个人工变量x6,x7即可


min x6+x7
s.t. x1+x2-x3+x6=2
-1+x2-x4+x7=1
x2+x5=3
x1,x2,K,x7≥0


在第一行放入检验数：





这等价于在第一行放-c，再用行变换使基变量的检验数为零。




x1 x2 x3 x4 x5 x6 x7
0 0 0 0 0 -1 -1 0
x6 1 1 -1 0 0 1 0 2
x7 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 0 0 3
0 2 -1 -1 0 0 0 3
x6 1 1 -1 0 0 1 0 2
x7 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 0 0 3
2 0 -1 1 0 0 -2 1
x6 2* 0 -1 1 0 1 -1 1
x2 -1 1 0 -1 0 0 1 1
x5 1 0 0 1 1 0 -1 2
0 0 0 0 0 0 -1 0
x1 1 0 -1/2 -1/2 0 1/2 -1/2 1/2
x2 0 1 -1/2 -1/2 0 1/2 1/2 3/2
x5 0 0 1/2 1/2 1 -1/2 -1/2 3/2


得到第一阶段最优解，人工变量不是基变量，最优值为0，则去掉x6,x7所在两列就是原问题基可行解。

第二阶段
仍将-c放在第一行，用行变换将基变量对应的检验数消为零。




x1 x2 x3 x4 x5
-1 2 0 0 0
x1 1 0 -1/2 1/2 0 1/2
x2 0 1 -1/2 -1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2
0 0 1/2 3/2 0 -5/2
x1 1 0 -1/2 1/2* 0 1/2
x2 0 1 -1/2 -1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2
-3 0 2 0 0 -4
x4 2 0 -2 2 0 1
x2 1 1 -1 0 0 2
x5 -1 0 1* 0 1 1
-1 0 0 0 -2 -6
x4 0 0 0 2 2 2
x2 0 1 0 0 1 3
x3 -1 0 1 0 1 1


现在检验数全小于等于零，得到原问题最优解x*=(0,3,1,2,0)T最优值-6。


[例2.3.1.3] 用二阶段法求解（LP）：


min -3x1+4x2
s.t. x1+x2≤4
2x1+3x2≥18
x1,x2≥0


标准化：


min -3x1+4x2
s.t. x1+x2+x3=4
2x1+3x2-x4=18
x1,x2,x3,x4≥0


第一阶段：


min x5
s.t. x1+x2+x3=4
2x1+3x2-x4+x5=18
x1,x2,x3,x4,x5≥0


为了少写一张表，也可在表最上方一行放 ，然后再用行变换使基变量的检验数为零。




0 0 0 0 -1
x1 x2 x3 x4 x5
2 +3 0 -1 0 18
x3 1 1* 1 1 0 4
x5 2 +3 0 -1 1 18
-1 0 -3 -1 0 6
x2 1 1 1 0 0 4
x5 -1 0 0 -1 1 16


已得到第一阶段最优解，但人工变量仍留在基里，并且最优值z=6>0故原问题可行域为空。原线性规划无解。

我这是从参考资料上弄下来的，有点乱，你最好自己点参考资料查看：
http://www.hebust.edu.cn/jpk/ycx/introduce/images/ksja.doc

单纯形法
§1.3.1 单纯形法的解题思路
由具体例题突出相关概念。
§1.3.2 单纯形法要点和单纯形表
1. 检验数的意义和计算公式


（1.19）
2.单纯形表
表1-5
cj c1 c2 … cm cm+1 … ck … cn
CB XB b x1 x2 … xm xm+1 … xk … xn
c1
c2
…
cm x1
x2
…
xm b1
b2
…
bm 1 0 … 0 a1m+1 … a1k … a1n
0 1 … 0 a2m+1 … a2k … a2n
… … … … … …
0 0 … 1 amm+1 … amk … amn
σj 0 0 … 0 … …

3. 单纯形法的基本法则
法则1 最优性判定法则
法则2 换入变量确定法则
设 ，则xk为换入变量。
法则3 换出变量确定法则
（1.21）
再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一定包含负分量，即不是可行解。
法则4 换基迭代运算法则

表1-6
cj 2 5 0 0 0 θ比
CB XB b x1 x2 x3 x4 x5
0
0
0 x3
x4
x5 8
20
12 1
5
0 2
2
[4] 1
0
0 0
1
0 0
0
1 8/2
20/2
12/4
σj 2 5 0 0 0
0
0
5 x3
x4
x2 2
14
3 [1]
5
0 0
0
1 1
0
0 0
1
0 -1/2
-1/2
1/4 2/1
14/5
—
σj 2 0 0 0 -5/4
2
0
5 x1
x4
x2 2
4
3 1
0
0 0
0
1 1
-5
0 0
1
0 -1/2
2
1/4
σj 0 0 -2 0 -1/4
最优解X*=（2，3，0，4，0）T，z*=2×2+5×3=19。
参考资料：http://www.hebust.edu.cn/jpk/ycx/introduce/images/ksja.doc

---

昌都地区18876659581： 用单纯形法求解线性规划问题,并列出单纯形表？
樊霍普芬： 单纯形法的一般解题步骤可归纳如下:①把线性规划问题的约束方程组表达成典范型方程组,找出基本可行解作为初始基本可行解.②若基本可行解不存在,即约束条件有矛盾,则问题无解.③若基本可行解存在,从初始基本可行解作为起点,根据最优性条件和可行性条件,引入非基变量取代某一基变量,找出目标函数值更优的另一基本可行解.④按步骤3进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善),即得到问题的最优解.⑤若迭代过程中发现问题的目标函数值无界,则终止迭代.按照上面说的,如果基本可行解不存在,问题无解了而且初始解就是“初始可行解”当然不可能是非可行解

昌都地区18876659581： 单纯形法 excel - ？
樊霍普芬： 首先要加载宏,选择里面的规划求解,添加. 选择规划求解,按照它说的方法一步一步选择下去,就OK了.

昌都地区18876659581： 物流运筹学单纯形法表格怎么计算 - ？
樊霍普芬： Rj=Cb*B^-*Aj-Cj.Rj表示:第j列的检验数.Cb表示A中基B对应的价值系数向量.B^-表示基矩阵B的逆.Aj表示A 的第j 列向量.Cj表示j列对应的价值系数.Rj

昌都地区18876659581： 求教单纯形法问题= = - ？
樊霍普芬： 先将原模型转换成标准型-(min z=-x1+2x2+0*x4); x1+3x2+4x3=12; 2x2-x3+x4=12; 加入一个松弛变量;然后就是求 min z=-x1+2x2+0x4; x1+3x2+4x3=12; 2x2-x3+x4=12; 再计算-min,就可以求出了,现在用单纯形法的表格形式来求解 min z=-x1+2x2+0x4; x1+3x2+4x3=12; 2x2-x3+x4=12; 因为上述的模型中没有单位向量,所以要增加人工变量,模型改变为 min z= -x1+2x2+0x4+Mx5+Mx6;

昌都地区18876659581： 请教运筹学的单纯形表法?! - ？
樊霍普芬： 学运筹学的前提是要掌握线性代数.那就先简单介绍一下做法吧: 1.将min 后面的部分的系数,取相反数(这一行数也称作为检验数) 2.接下来就是将检验数这一行下面的矩阵化到含有单位矩阵的形式,即含有1,0 3.每次化的时候要注意,化成...

昌都地区18876659581： 单纯形法的求解举例是什么? ？
樊霍普芬： 单纯形法单纯形法求解举例编辑约束方程的系数矩阵为:为单位矩阵且线性独立,为基变量,为非基变量

昌都地区18876659581： 单纯形法的单纯形法求解举例 - ？
樊霍普芬： 约束方程的系数矩阵为:为单位矩阵且线性独立, 为基变量, 为非基变量. 令非基变量取0,则 ,此时, =0.然后去找另一个基本可行解,即将非基变量换入基变量中,但保证其余的非负.如此循环下去,直到找到最优解为止. 从一个顶点...

昌都地区18876659581： 250分悬赏线性规划问题(单纯形法) - ？
樊霍普芬： 一、线性规划单纯形法的概念 (一)线性规划单纯形解法的基本思路 若一个凸集仅包含有限个极点,则称此凸集为单纯形.线性规划的可行域是单纯形(证明略,但可以从上节图解...

昌都地区18876659581： 求运筹学单纯形法最简单易记的方法看了好多天了 一直没能看懂单纯形法表格的迭代 、 不知道2次迭代中各行是怎么的出来的 但是换入与换出是看懂得 检验... - ？
樊霍普芬：[答案] 其实就是矩阵行变换,如不清楚请复习线性代数相关章节,运筹学中处处要用如 ( 2 3 3 2 4 2 1 2 3 )将其进行行变换,比如1.把第二行第一个元素变为1,用第二行各元素除以2,得 (2 3 3 1 2 1 1 2 3)2.把用第二行把第一列...

昌都地区18876659581： 用单纯形法求解线性规划 - ？
樊霍普芬： 360 9 4 1 0 0 ①200 4 5 0 1 0 ②300 3 【10】 0 0 1 ③ 1 将【10】所在行的数都除10,这样,【10】变成了【1】;③/102 再将4所在行的数减去(【1】所在行的数都乘4后数),这样,4就“划成”了0;①-4*③3 再将5所在行的数减去(【1】所在行的数都乘5后数),这样,5就“划成”了0. ②-5*③