2015单纯形算法.ppt

1.3 单纯形算法 线性规划问题解的基本概念 单纯形解法 解的最优性检验 表解形式的单纯形法 单纯形解法的一些问题及其处理方法 单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格提出。 尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。 1.3 单纯形算法 从某个角顶可行解开始---起步 向目标函数值更好的邻近可行顶点移动 判断此顶点是否为最优解：检查它是否比它的临近顶点的目标函数值都好，若是，则是最优解；若不是，则重复上述第二步。 1.3 单纯形算法 由于基可行解是由一个可行基决定的，因此，确定初始基可行解 相当于确定一个初始可行基 。 方法：若A中含有I，则 =I; 若A中不含I，可用人工变量法构造一个I 问题：若 =I，则 =?。 例1.1中的 =? 1.3 单纯形算法 1.3 单纯形算法 （最优解判定定理）若X(0)=(b1’,b2’, …,bm’,0, …,0)T，对应于基B的基本可行解，且对于一切j=m+1, …,n，有σj≤0，则X(0)为线性规划问题的最优解。 （无穷多最优解判别定理）若X(0)=(b1’,b2’, …,bm’,0, …,0)T为对应于基B的基本可行解，且对于一切j=m+1, …,n，有σj≤0，又存在某个非基变量的检验数σm+k=0，则线性规划问题有无穷多最优解。 （无界解判定定理）若X(0)=(b1’,b2’, …,bm’,0, …,0)T为对应于基B的基本可行解，有一个σm+k0而对于i=1,2, …,m有a’i,m+k ≤0则线性规划问题为无界解。 1.3 单纯形算法 在确定换入变量xj与换出变量xl后，要把xj和 xl位置对换，也即把xj所对应的列向量变成单位向量。只需对系数矩阵的增广矩阵进行行变换即可，称alj为旋转元（也称为主元）。也就是以主元行为基准，将主元变成1，主元列变成单位向量。同时在XB列中将xl换成xj，在CB列中将Cl换成Cj 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 4、根据σj=max﹛σk∣σk0，k∈IN﹜（ IN 为非基变量指标集），确定xj为换入变量（即新基的基变量），再根据 5、以alj为主元素进行基变换，在表中用[ ]把alj表示出来，利用矩阵初等行变换，以主元行为基准，将主元素alj变成1，主元列变成单位向量。同时在XB列中将xl换成xj，在CB列中将Cl换成Cj。 6、得到新的单纯形表，重复以上步骤，直至得到最优解为止。 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 1.3 单纯形算法 单纯形解法中的一些问题及其处理方法 换入变量的选择问题 检验数最大原则 下标最小原则 换出变量的选择问题 比值最小原则 下标最大原则 无换出变量的情况—无界解 非基变量检验数有等于零—多个最优解的情况 1.3 单纯形算法 （3）旋转运算（迭代运算） Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. （3）旋转运算（迭代运算） 以表中元素 alj 进行基变换：将第 l 行每个元素除以alj， 再将第l行每个元素乘以 -aij/alj 加到第 i 行（i＝1，2，…， m，i≠l），将第 l 行每个元素乘以 -σj/alj 加到检验数行。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 总结单纯形法的具体步骤： 1、将线性规划问题标准化，确定初始可行基，建立初始单纯形表。据此可写出初始基本可行解和相应的目标函数值。 2、检查检验数行中对应于非基变量的各个检验数σk，若所有的σk≤0，则由最优性判别准则，现行表的基本可行解就是最优解，停止计算，否则转入下一步。 3、在所有σk＞0中，如果有一个σj对应的系数列向量pj≤0(也就是与它同列的各个aij≤0)，则此问题没有有限最优解，停止计算，否则转入下一步。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Clie