线性规划模型的单纯形法.ppt

1、Chapter3 线性规划模型的单纯形法 (Simplex Method,线性规划问题解的相关概念及基本性质 单纯形法的基本思路 单纯形法基本原理 单纯形表法 单纯形法进一步讨论人工变量法,本章主要内容,本章教学目的、重点、难点,理解线性规划模型的可行解、基本解、基本可行解等概念和这些概念之间的关系； 熟悉单纯形法的基本思路和单纯形法的基本原理； 掌握掌握单纯形法求解线性规划问题的基本步骤； 掌握单纯形表法求出线性规划模型的基本最优解； 会用计算机软件求解线性规划问题，进一步理解单纯形法的基本原理,Chapter3 线性规划模型的单纯形法 (Simplex Method,线性规划模型解的相关概

2、念及基本性质,1. 线性规划问题解的相关概念,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值,可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（B0），称B是规划问题的一个基。设,称 B中每个列向量Pj ( j = 1 2 m) 为基向量。与基向量Pj 对应的变量xj 为基变量。除基变量以外的变量为非基变量,线性规划模型解的相关概念及基本性质,基本解：某一确定的基B，令非基变量等于零，由约束条件

3、方程解出基变量，称这组解为基B的基本解。在基本解中变量取非0值的个数不大于方程数m，基解的总数不超过 个； 基可行解：满足变量非负约束条件的基本解，简称基可行解。 可行基：对应于基可行解的基称为可行基。 基本最优解：使目标函数最优的基本可行解成为基本最优解,线性规划模型解的相关概念及基本性质,线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算,例3-1,通过下面例3-1来说明线性规划问题的基、对应的基本解、基本可行解的概念和计算,线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算与几何解释,线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算与几何解释,

4、线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算与几何解释,线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算与几何解释,线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算,线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算与几何解释,由于基本解为非负， 可见该基本解是基本可行解，基是可行基。该基本解对应于图3-1中的C点。该点是可行域的顶点,图3-1线性规划模型对应的基、基本解、基本可行解,线性规划模型解的相关概念及基本性质,2.基本解和基本可行解的计算与几何解释,线性规划模型解的相关概念及基本性质,3.线性规划问题解的基本性质,思考

5、： 通过前面的学习可知，若线性规划模型有最优解，必可在某个极点上达到，即在某个基可行解上取得最优解。因此，你会想到求解线性规化问题最简单的方法是？这种方法的缺陷,线性规划模型解的相关概念及基本性质,换一种思路：若从某一基可行解出发，每次总是寻找比上一个“更好”的基可行解，而不去计算不比上一个更好的基可行解，可以减少很大的计算量，怎么实现这种逐步改善的求解方法呢,线性规划模型解的相关概念及基本性质,需要解决以下几个问题： （1）如何得到一个初始的基可行解； （2）如何判断当前的基可行解是否达到最优解； （3）若当前解不是最优解，如何去寻找一个改善的基可行解,线性规划模型解的相关概念及基本性质,美

6、国数学家丹齐格提出的单纯形法解决了以上三个问题，单纯形法是求解线性规划问题的一种普遍有效方法,单纯形法的基本思路,单纯形法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解 （找出更大的目标函数值,最优解,是,否,循 环,核心是：变量迭代,结束,基本原理,单纯形法的基本原理,单纯形法的基本原理,1.初始基可行解的确定,单纯形法的基本原理,1.初始基可行解的确定,在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以

7、后详细讲述,单纯形法的基本原理,2.最优解的检验,1)检验数的意义,单纯形法的基本原理,2.最优解的检验,目标函数值,单纯形法的基本原理,2.最优解的检验,其中,单纯形法的基本原理,2.最优解的检验 (2)最优解的判断法则,单纯形法的基本原理,2.换基迭代 (1)换入变量（进基变量,2)换出变量（出基变量,单纯形法的基本原理,2.换基迭代,2)换出变量（出基变量,单纯形法的基本原理,2.换基迭代,2)换出变量（出基变量,通过初等变换将新的一组基变量用非基变量表示出，判断解的最优性,单纯形表法的计算步骤,单纯形表,单纯形法的计算步骤,例1 用单纯形法求下列线性规划的最优解,解：1）将问题化为标准

8、型，加入松驰变量x3、x4则标准型为,单纯形法的计算步骤,2）求出线性规划的初始基可行解，列出初始单纯形表,单纯形法的计算步骤,3）进行最优性检验,如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步,4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即： ，其对应的xk作为换入变量。 确定换出变量。根据下式计算并选择 ，选最小的对应基变量作为换出变量,单纯形法的计算步骤,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以

9、找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 5）重复3）、4）步直到计算结束为止,单纯形法的计算步骤,换入列,bi /ai2，ai20,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,基本最优解、最优值,单纯形法的计算步骤,例2 用单纯形法求解,解：将数学模型化为标准形式,不难看出x4、x5可作为初始基变量，列单纯形表计算,单纯形法的计算步骤,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1

10、,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,单纯形法的计算步骤,练习1 用单纯形法求解线性规划问题（无穷解的情况,单纯形法的计算步骤,练习2 用单纯形法求解线性规划问题（无界解的情况,单纯形法的计算步骤,关于单纯形法的补充说明,单纯形法的计算步骤,学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握单纯形表法的解题思路及求解步骤,思考： 如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将如何构造初始可行基,单纯形法的计算步骤,作业： P52

11、 3、4,单纯形法的进一步讨论人工变量法,人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法,单纯形法的进一步讨论人工变量法,人工变量法： 人工变量时为了获得初始基可行解，在约束条件化为等式后，认为的加入的虚拟变量，只有当他们同时为零，即在最终的单纯形表中它们全部变为非基变量，此时加入人工变量的等式约束才与原约束条件等价。因此

12、在最优解的基变量中不允许含有人工变量，这就要求在迭代过程中把人工变量从基变量中迭代出去，通常采用M法和两阶段法,单纯形法的进一步讨论人工变量法,人工变量、松弛变量和剩余变量是不同的，松弛变量、剩余变量可以取零值，也可以取正值。但是人工变量只能取零值，否则约束条件1、2就和原始的约束条件不等价了。为了使得人工变量为零，规定人工变量在目标函数中的系数为-M,M0,且为任意大的数。这样只要人工变量不为零，目标函数最大值就是一个任意小的数。为了使目标函数实现最大化人工变量要为零，所以只有在最终单纯形表中人工变量为非基变量，人工变量的值才能是0。为了构造初始可行基，强行将人工变量加到约束条件中去；又为了把人工变量从基变量中替换出来，就令人工变量在求最大值的目标函数中为-M,M0,这一方法称大M法,大M法,单纯形法的进一步讨论人工变量法,例3 用大M法解下列线性规划,解：首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵，无法建立初始单纯形表,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量，得到人工变量单纯形法数学模型,其中：M是一个很大的抽象