chap2单纯形法.ppt

第二章 单纯形法2.1单纯形法原理 若LP问题有最优解的话，定在可行域的某顶点处达到，又，一个顶点对应一个基本可行解，一个自然的想法是：找出所有的基本可行解。 因基本可行解的个数有限，通过“枚举法”，从理论上讲总能找出所有的基本可行解。而事实上随着m，n的增大，解的个数迅速增大，致使此路行不通。 换一种思路：若从某一基本可行解（今后称之为初始基本可行解）出发，每次总是寻找比上一个更“好”的基本可行解，逐步改善，直至最优。这需要解决以下三个问题： 1.如何找到一个初始的基本可行解。 2.如何判别当前的基本可行解是否已达到了最优解。 3.若当前解不是最优解，如何去寻找一个改善了的基本可行解。 单纯形法步骤 一、构造初始可行基 1、引入附加变量，化为标准型 2、必要时引入人工变量 3、目标函数中，附加变量系数为0，人工变量则为M 二、求基本可行解 1、用非基变量表示基变量和目标函数式 2、求出一个基本可行解及相应Z值 三、最优性检验 依据:检验数及判别定理 四、基变换 1、换入基的确定：负值中最小的 2、换出基的确定：最小非负比值规则 返回步骤二 2.2 单纯形法的表格形式书例 两阶段法的第一阶段实现求解一个目标中只包含人工变量的LP问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束不变的情况下求这个目标函数极小化的解。 显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原LP问题无可行解。 第二阶段：求解原线性规划问题的最优解。 以第一阶段的最终单纯形表为基础，去掉人工变量，目标函数换为原问题的目标函数，得到第二阶段的初始表，继续迭代求解。 书例：表格形式 2.4 退化问题 退化问题：按最小比值θ来确定换出基变量时，有时出现两个以上相同的最小比值，从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。 循环问题：退化解出现的原因是模型中存在多余的约束，使多个基可行解对应同一个顶点。当存在退化解时，就有可能出现迭代计算的循环。即从一个可行基经有限次迭代后又回到原来的可行基。尽管可能性及其微小（直到目前为止，还没有见到一个实际应用问题产生循环的例子），但在理论上讲是存在的。 E.Beale曾给出一个循环的例子 这个例子用单纯形法经过6次迭代后，又回到了初始状态。得不到最优解。有兴趣的同学可自行用单纯形法验证本题产生的循环现象。而实际上本题有最优解。 解决方法：摄动法；勃兰特法。 摄动法 理论依据：使向量b摄动，即令 当 取某些数时，摄动问题是非退化问题，还可通过求解该摄动问题达到求解原问题的目的。 实际操作：确定换出变量的步骤。 勃兰特方法 法则一：极小化问题中，如有几个检验数是负的，选其中下标最小的非基变量作为换入变量。 法则二：极小化问题中，根据最小非负比值规则确定换出变量时，如有几个比值同时达到最小比值，选其中下标最小的基变量作为换出变量。 2.5 改进单纯形法 单纯形法计算的特点是每迭代一次，就要把整个单纯形法重新计算一遍。从计算机的角度来讲，单纯形法并不是一种经济高效的方法。首先是要占用大量的存贮空间，其次，由于每次计算都利用上一次的单纯形表，当计算次数较多时，容易造成误差的积累，直接影响计算精度和收敛速度。 改进单纯形法的基本计算步骤和单纯形法基本相同，但在上述两方面有所改进。 在单纯形法的迭代过程中，我们实际需要的只有以下各项： 1、检验数 ,以判断是否最优或确定换入变量。 2、换入变量所在列的各元素 和基变量的值 ，根据 决定换出变量。 Min S = CX s.t. AX=b X ≥ 0 在单纯形法的矩阵形式中我们可以发现，单纯形表中的其它数字可利用和原始系数进行运算直接得到： 这就是改进单纯形法的出发点。 令向量Y表示 ，即 称其为单纯形乘子。 求解步骤 1、第0次迭代：初始可行基 检验数 如不是最优解，确定换入基，换出基。 2、计算 ：三种方法 3、计算第i＋1次迭代的常数列和检验数 4、最优性检验：如最优，结束。否则下一步。 5、计算第i＋1次迭代中的换入列 6、确定第i＋1次迭代中换出基的下标，返回步2。 逆的乘积形式 的计算方法 已知： ；第i