资源描述：
《最优化课程论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、求解线性规划的单纯形法摘要：线性规划就是用数学为工具，来研究一定限制条件下，如何实现某一线性目标最优化。单纯形法是求解线性规划的主要算法，文章从单纯形法的思想出发，详细论述了单纯形法的主体步骤，并借助单纯形表通过例题加以说明。求解思路是：通过添加人工变量使得标准化后的系数矩阵一定含有单位矩阵，从而得到一组基变量和初始基木可行解。由于人工变量是人为添加的，为了不改变原问题，在目标函数中消去人工变量，并将人工变量由初始的基变量化成非基变量，使之取值为零，然后用普通单纯形法求解。关键词:线性规划;单纯形法;单纯形表;步骤1.迭代原理从一个
2、初始的基本可行解出发，经过判断，如果是最优解，则结束；否则经过基变换得到另一个目标函数值改善的基木可行解，如此一肓进行下去，肓到找到最优解。2.迭代步骤第1步：求初始基可行解，列出初始单纯形表。第2步：最优性检验。第3步：从一个基本可行解转换到相邻的目标函数值更大的基木可行解，列出新的单纯形表。第4步：重复第2、3步，一直到计算结束为止。2.1确定初始基本可行解由于可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。确定方法：若系数矩阵A中含单位矩阵I,则取BO=I；若A中不含I,则可用人工变量法构造
3、一个I。2.2最优性检验用口标来检验解的优劣。在A屮取定一个基矩阵B,则决策向量X可分块为!〃，相应的价格向量C也分块为(CBCN),把这个分块矩阵的形式乘岀来，就是Z=CX=(CBCN)!〃=CBXB+CNXN,不妨设B表示A中的前m列，则可记A=(BN),其中N为非基矩阵，约朿中的AX=b可表示为(BN))!〃=b,即XB=B-lb-B-lNXN经整理得Z=CB(B-lb-B-INXN)+CNXN,=CBB-lb+(CN—CBB—IN)XN在这个式子屮不难分析出，后边一项XN的系数CN—CBB—1N,当这个向量均为W0分量时，这
4、时只有当XN取0时，使Z值最大，也就是当XN统统取0时的这个基本可行解是最优的，而当这个系数向量其中有某分量是>0的时候，我们可以分析得到，当前XN统统取0的这个基木可行解不是最优，因此，我们可以用XN的系数向量CN-CBB—17的符号来判断当前基可行解是不是最优，把这个系数向量叫做检验数向量，记为8,当5W0时，当前解为最优解。最优性检验的方法：(1)计算每个变量xj的检验数5j=Cj-CBB-lPj,其中Pj为A中的第j列；(2)若所有5jW0,贝U当前解为最优；否则，如果至少有一个5j>0,当前解不是最优，转入第三步。2.3寻
5、找更好的基本可行解由于基本可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1,因此，本步骤也可称为基变换。在基变换的过程中要遵循这样的原则：保证改善目标，再者保证基变换后的解可行。具体变换的方法就是将系数矩阵A=(P1,P2,……Pi……Pk……Pn)中非基向量部分的某一列和基向量中的某一列互换，而且每次只换一列，在基向量的行列中出去一个进一个，这个基变换的过程就是确定进基出基。具休方法：首先决定进基，令正检验数中最大的那个所对应的Pk进基；然后决定出基，令检验比9i中最小的对应的行Ps出基，其中。i
6、=(B-lb)i/(B-lPk)i,(B-lPk)i>0,也就是对应分量之比。在用单纯形法求解线性规划问题Z前，有一个预备步骤就是将模型变为标准型，虽然可以由基本的计算求出线性规划问题的最优解，但是为了更加简单、清楚，这个算法的过程我们通过表格的形式来实现，即所谓的单纯形表。例：用单纯形法求解下面线性规划问题(以max为例)maxZ=7Xl+12x2s.t.:9x1+4x2^3604x1+5x2^2003x1+10x2^300xl,x220解：化为标准型：maxZ=7X1+12X2+0X3+0X4+0X5s.t.:9xl+4x2+x
7、3=3604xl+5x2+x4=2003xl+10x2+x5=300xl,x2,x3,x4,x520单纯形表：712000XBcBB-1bx.卷x?x$0X303609410090X.<02004501040X503003[10]001308712000第一个基是I,初始表填完后，第一个基木可行解X=(0,0,360,200,300)T,这个解是否为最优呢？要计算检验数进行检验。以第一个检验数§1为例来加以说明81=C1-CBB—1P1=7-(0,0,0)(943)1=7同理求出其余几个检验数分别为12、0、0、0。如果检验数的符号
8、均W0,则当前这个基本可行解最优，否则不是最优。我们看到这张表不是最优，还需继续进行。那么继续进行就需转到第三个步骤基变换，主要是确定进基和出基，确定进基是在正检验数中选择最大的那个，我们这道题是12,这个12所对应的向量是P2,对应
