(本科）第3章 线性规划的单纯形法教学ppt课件.ppt

(本科）第3章 线性规划的单纯形法教学ppt课件21世纪高等院校公共课精品教材管理运筹学管理运筹学董银红 付丽丽 编著东 北 财 经 大 学 出 版 社Dongbei University of Finance&Economics PressCONTENTS第3章 线性规划的单纯形法图解法只能求解比较简单的线性规划形式，利用计算机求解虽然能够解决大规模的线性规划问题，但是掩盖了实际的求解方法和过程。为了更深入地学习线性规划和开发新的算法，必须要对线性规划的求解机理有一定的了解。本章在对线性规划的模型有一定认识后，从代数形式上继续考察线性规划问题。首先，给出线性规划相关的一些概念和最优解的性质；然后，在此基础上提出单纯形原理；在对单纯形法进行完整描述后，本章将对单纯形法提出了进一步的说明。通过本章的学习，读者应该对线性规划的单纯形的思想和步骤有较为清晰的理解。CONTENTS3.1 线性规划的基本理论n 1.可行区域的几何机构 考虑标准的线性规划问题： 用 表示n维的欧式空间，这里 ， ， ， . 不妨设可行区域 ，因此线性方程组 相容，总可以把多余方程去掉，使剩下的等式约束的系数向量线性无关，故可设秩(A)=m,m0（j是非基变量的下标），则已获得最优解；算法终止。否则，在检验数zj-cj0的非基变量中，选取检验数zj-cj最小的非基变量xk进基。CONTENTS3.2 单纯形法原理第三步（确定离基变量）：检查进基变量xk在约束条件中的列向量Yk，如果Yk0，则目标函数无界，算法终止。否则根据右边常数b与Yk中正分量的最小比值 ，确定离基变量。第四步（进行行变换）：以yrk为主元进行行变换（称为以yrk为主元的旋转运算），使得单纯形表中：（1）进基变量xk在目标函数中的系数为0；（2）约束条件中主元yrk1，主元所在列的其他元素为0。转第二步。通过第二、三、四步迭代，直至获得最优解或确定目标函数无界。1min0iriki mikrkbbyyy CONTENTS3.3 关于单纯形法的进一步讨论3.3.1 人工变量法人工变量法通过人工变量法求解线性规划问题的基本步骤如下：（1）引进松弛变量，使约束条件成为等式；（2）如果约束条件的系数矩阵中不存在一个单位矩阵，则引进人工变量；（3）在原目标函数中，加上人工变量，每个人工变量的系数为一个足够大的正数M；（4）用单纯形表求解以上问题，如果这个问题的最优解中有人工变量是基变量，则原问题无可行解。如果最优解中所有人工变量都离基，则得到原问题的最优解。CONTENTS3.3 关于单纯形法的进一步讨论【例例3-33-3】用人工变量法求解下面的线性规划问题：max z=3x1-x2-x3 x1-2x2+x311s.t. -4x1+x2+2x33 -2 x1+x3=1 x1,x2,x30 CONTENTS3.3 关于单纯形法的进一步讨论3.3.2 两阶段法两阶段法两阶段法的第一阶段是先求解一个目标函数中只含有人工变量的线性规划问题，即令目标函数中其它变量的系数为零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。当第一阶段求解结果表明问题有可行解时，第二阶段是在原问题中去除人工变量，并从此可行解（第一阶段的最优解）出发，继续寻找问题的最优解。CONTENTS3.3 关于单纯形法的进一步讨论根据以上思路，我们用二阶段法来求解下面例题：max z=3x1-x2-x3 x1-2x2+x311s.t. -4x1+x2+2x33 -2 x1+x3=1 x1,x2,x30 CONTENTS3.3 关于单纯形法的进一步讨论3.3.3 单纯形法计算中的几个问题单纯形法计算中的几个问题 CONTENTS3.3 关于单纯形法的进一步讨论3.3.4 改进单纯形法改进单纯形法改进单纯形法是一种保持迭代所需要的最少数据，进行单纯形迭代的方法。根据这种算法编制的计算机程序，在运行时需要较少的内存空间。下面就来分析，如何在单纯形表中保持以上四种数据。设线性规划问题为：max z=CTXs.t. AXb X0 CONTENTS3.3 关于单纯形法的进一步讨论引进松弛变量Xs，并设B是包含在A中的一个基，则线性规划问题表示为：max z=CTXst BXB+NXN+IXs=b XB, XN, Xs0相应的单纯形表见表3-3。 CONTENTS3.3 关于单纯形法的进一步讨论消去目标函数中基变量的系数，并将约束矩阵中的基矩阵通过行变换变为单位矩阵，得到表3-4中的单纯形表。 CONTENTS3.3 关于单纯形法的进一步讨论【例例3-43-4】 用改进单纯形法求解以下问题：min z=-x1-2x2+x3-x4-4x5+2x6 x1+x2+x3+x4+x5+x66st 2x1-x2-2x3+x44 x3+x4+2x5+x64 x1,x2,x3,x4,x5,x60 CONTENTS3.3 关于单纯形法的进一步讨论从以上算例可以看出，改进单纯形法所需要保存的动态数据量大大少于一般的单纯形表，特别是当问题变量个数n大大超过约束个数m时，数据量的减少更为明显。由于改进单纯形表的规模仅为(m+1)(m+1)，因而旋转运算的计算量也大大少于一般的单纯形法。另外，改进单纯形法在计算zjcj时的计算量比一般单纯形法要大。但是对大多数线性规划实际问题，系数矩阵大多数是非零元素很少的稀疏矩阵，计算zjcj=WTajcj时，向量aj中非零元素的个数也很少。据统计，实际的大规模线性规划问题系数矩阵非零元素的密度一般是5%10%，这样改进单纯形法计算zjcj的乘法和加法次数就会明显少于单纯形法。 CONTENTS3.3 关于单纯形法的进一步讨论应该指出的是，尽管系数矩阵是稀疏矩阵，但一般单纯形法却不能享受这一优势，这是由于尽管基B是稀疏的，但B-1的密度就往往比B大得多，而单纯形表B-1A得密度就更大了。改进单纯形法能够享受稀疏矩阵的优势，是因为在每次迭代中都用原始数据。改进单纯形法每次迭代都用原始数据这一特点，也使得这种迭代方法的累积误差比较小。由于改进单纯形法有以上这些优点，大多数线性规划应用软件都采用改进单纯形法作为基本算法。