最优化课程论文.doc

求解线性规划的单纯形法摘要：线性规划就是用数学为工具来研究一定限制条件下如何实现某一线性目标最优化。单纯形法是求解线性规划的主要算法文章从单纯形法的思想出发详细论述了单纯形法的主体步骤并借助单纯形表通过例题加以说明。求解思路是：通过添加人工变量使得标准化后的系数矩阵一定含有单位矩阵从而得到一组基变量和初始基本可行解。由于人工变量是人为添加的为了不改变原问题在目标函数中消去人工变量并将人工变量由初始的基变量化成非基变量使之取值为零然后用普通单纯形法求解。关键词：线性规划；单纯形法；单纯形表；步骤1.迭代原理从一个初始的基本可行解出发经过判断如果是最优解则结束；否则经过基变换得到另一个目标函数值改善的基本可行解如此一直进行下去直到找到最优解。2．迭代步骤第1步：求初始基可行解列出初始单纯形表。第2步：最优性检验。第3步：从一个基本可行解转换到相邻的目标函数值更大的基本可行解列出新的单纯形表。第4步：重复第2、3步一直到计算结束为止。2.1确定初始基本可行解由于可行解是由一个可行基决定的因此确定初始基可行解X0相当于确定一个初始可行基B0。确定方法：若系数矩阵A中含单位矩阵I则取B0＝I；若A中不含I则可用人工变量法构造一个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－1b－B－1NXN经整理得Z＝CB（B－1b－B－1NXN）＋CNXN＝CBB－1b＋（CN－CBB－1N）XN在这个式子中不难分析出后边一项XN的系数CN－CBB－1N当这个向量均为≤0分量时这时只有当XN取0时使Z值最大也就是当XN统统取0时的这个基本可行解是最优的而当这个系数向量其中有某分量是＞0的时候我们可以分析得到当前XN统统取0的这个基本可行解不是最优因此我们可以用XN的系数向量CN－CBB－1N的符号来判断当前基可行解是不是最优把这个系数向量叫做检验数向量记为δ当δ≤0时当前解为最优解。最优性检验的方法：（1）计算每个变量xj的检验数δj＝Cj－CBB－1Pj其中Pj为A中的第j列；（2）若所有δj≤0则当前解为最优；否则如果至少有一个δj＞0当前解不是最优转入第三步。2.3寻找更好的基本可行解由于基本可行解与基对应即寻找一个新的基可行解相当于从上一个基B0变换为下一个新的基B1因此本步骤也可称为基变换。在基变换的过程中要遵循这样的原则：保证改善目标再者保证基变换后的解可行。具体变换的方法就是将系数矩阵A＝(P1P2……Pi……Pk……Pn）中非基向量部分的某一列和基向量中的某一列互换而且每次只换一列在基向量的行列中出去一个进一个这个基变换的过程就是确定进基出基。具体方法：首先决定进基令正检验数中最大的那个所对应的Pk进基；然后决定出基令检验比θi中最小的对应的行Ps出基其中θi＝(B-1b)i/(B-1Pk)i(B-1Pk)i＞0也就是对应分量之比。在用单纯形法求解线性规划问题之前有一个预备步骤就是将模型变为标准型虽然可以由基本的计算求出线性规划问题的最优解但是为了更加简单、清楚这个算法的过程我们通过表格的形式来实现即所谓的单纯形表。例:用单纯形法求解下面线性规划问题（以max为例）maxZ＝7X1＋12x2s.t.：9x1＋4x2≤3604x1＋5x2≤2003x1＋10x2≤300x1x2≥0解：化为标准型：maxZ＝7X1＋12X2＋0X3＋0X4＋0X5s.t.：9x1＋4x2＋x3＝3604x1＋5x2＋x4＝2003x1＋10x2＋x5＝300x1x2x3x4x5≥0单纯形表：第一个基是I初始表填完后第一个基本可行解X＝(00360200300）T这个解是否为最优呢？要计算检验数进行检验。以第一个检验数δ1为例来加以说明δ1＝C1－CBB－1P1＝7－（000）(943)T＝7同理求出其余几个检验数分别为12、0、0、0。如果检验数的符号均≤0则当前这个基本可行解最优否则不是最优。我们看到这张表不是最优还需继续进行。那么继续进行就需转到第三个步骤基变换主要是确定进基和出基确定进基是在正检验数中选择最大的那个我们这道题是12这个12所对应的向量是P2对应的变量x2就进基它刚才是非基变量确定了进基之后就可以计算检验比θ就是用B－1b比上已决定进基的列B－1P2也就是每个分量对应之比