资源描述：
《运筹学——单纯形方法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、单纯形方法线性规划基本定理.给定线性规划的标准形式如下：maxcTx(1)s.t.Ax=b,x³0,(2)其中A是秩为m的m´n阶矩阵,b³0.i)如果存在可行解,则存在基可行解;ii)如果存在最优解,则存在最优的基可行解.这个定理将求解线性规划的任务变成为搜索基可行解。因为对有n个变量和m个约束问题，基可行解最多不超过下面的数：nm=n!m!n-m!定理(顶点和基解等价).设K是包括所有满足(2)的n维向量x的凸多面体。则向量x是凸多面体K的一个顶点当且仅当x是一个基可行解。线性规划中的问题根据线性规划基本定理，解线
2、性规划只需要在约束凸多面体的所有顶点上寻找最优解。因此，我们需要考虑的问题有：1.怎样找到一个基可行解？2.判别基可行解是否最优解。3.从非最优的基可行解找到另一个基可行解，使目标函数值增大。4.如果问题无最优解，能发现一族可行解，使目标函数无上限。对于我们前面提出的四个问题，单纯形方法能解决其中的问题2-4。换句话说，单纯形方法要求一个已知的基可行解。当从非最优的基可行解找到另一个基可行解时，为了保证目标函数值增大，单纯形方法还要求如下的假定，这引入了下面的概念：退化解和非退化解：设x0=[B-1b,0]是一个基可行
3、解，如果有基变量的取值是0，即B-1b中有分量等于零，则称基可行解x0是退化的。否则，称x0是非退化的。非退化假定：假设线性规划的每个基可行解都是非退化的。6给定线性规划的标准形式如下：maxcTx(1)(LP)s.t.Ax=b,(2)x³0,(3)其中A是行满秩的m´n阶矩阵,b³0.单纯形方法是在已知一个基可行解的情况下，寻找线性规划的最优基可行解的算法。强调一下：单纯形方法就是在已知一个基可行解的情况下，寻找线性规划的最优基可行解。单纯性方法直接能解决问题2-4。而问题1可以使用辅助线性规划来解决。我们首先来解决
4、问题2。对线性规划(LP)，假设知道一个基可行解x0。因此，就有一个可行基B，假设B由约束系数矩阵A的前面m列构成，对应的基变量用xB表示，xD表示非基变量。这样，我们就可以将决策变量x，价值系数c和约束矩阵A分块成x=[xB,xD]，c=[cB,cD]和A=[B,D]。于是，线性规划可以被写成下面的形式：maxcBTxB+cDTxDs.t.BxB+DxD=b,(4)xB,xD³0.基可行解x0就是在约束方程(4)中令非基变量xD=0得到的结果。因为基B是可逆矩阵，所以有xB0=B-1b。单纯形方法怎么判断基可行解x0
5、=[B-1b,0]是否是最优的基可行解呢？我们从约束方程(4)解出所有的基变量xB，用非基变量xD表示，得到xB=B-1b-B-1DxD,(5)把由(5)表示的基变量代入到目标函数中，就有z=cBTxB+cDTxD=cBT(B-1b-B-1DxD)+cDTxD整理后得到z=cBTB-1b+(cDT-cBTB-1D)xD当非基变量xD=0时，得到z(x0)=cBTB-1b。我们令s=(sm+1,…,sn)=cDT-cBTB-1D。这里s是行向量，并且正好是用非基变量表示的目标函数中所有变量的系数。而目标函数可以写成6我们
6、看到，如果有某个sj>0，取非基变量xj>0，则目标函数值=z(x0)+sjxj>z(x0)。这样得到的一个x还是可行解吗？在非退化假定下，我们可以从方程(5)中得到这样的一个可行解。我们回头看看方程(5)xB=B-1b-B-1DxD,(5)因为基可行解都是非退化的，所以B-1b>0。当xj>0充分小时，可以保证xB>0。因此，可以得到一个可行解x具有非基变量xj>0。从而有z(x)=z(x0)+sjxj>z(x0)。由于当sj>0时，存在可行解x使得目标函数值比在基可行解x0处的目标函数值更大，所以x0不是最优解。这
7、样，我们得到单纯形方法的最优性判据。最优性判据：如果存在sj>0(m+1£j£n)，则基可行解x0不是最优解；如果s£0，则x0是最优解；其中s=(sm+1,…,sn)=cDT-cBTB-1D。因为根据sj(j=m+1,…,n)的符号可以判别基可行解x0是否是最优解，所以，人们称sj为检验数。现在“判别基可行解x0是否是最优解”的问题2已经被解决。通过检查检验数sj(j=m+1,…,n)的符号，可以确定x0是否是最优解。我们还看到，当x0不是最优解时，在非退化假定下，可以从基可行解x0找到一个可行解x使目标函数值增加。
8、那么，可以从基可行解x0找到另一个基可行解x1使目标函数值增加吗？回答是肯定的。现在，我们回头看看方程(5)的两种表示形式：xB=B-1b-B-1DxD,(5-1)和xB+B-1DxD=B-1b.(5-2)令G=B-1D=(gij)=(g·m+1,…,g·n)是m´(n-m)矩阵。则方程(5-2)可以写成xB+GxD=B-1b或x
