第三章线性规划模型的单纯形法

第三章线性规划模型的单纯形法第1页，课件共49页，创作于2023年2月本章教学目的、重点、难点：

理解线性规划模型的可行解、基本解、基本可行解等概念和这些概念之间的关系；熟悉单纯形法的基本思路和单纯形法的基本原理；掌握掌握单纯形法求解线性规划问题的基本步骤；掌握单纯形表法求出线性规划模型的基本最优解；会用计算机软件求解线性规划问题，进一步理解单纯形法的基本原理Chapter3线性规划模型的单纯形法

(SimplexMethod)第2页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质1.线性规划问题解的相关概念线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。第3页，课件共49页，创作于2023年2月

可行解：满足约束条件②、③的解为可行解。所有可行解的集合为可行域。

最优解：使目标函数达到最大值的可行解。

基：设A为约束条件②的m×n阶系数矩阵(m<n)，其秩为m，B是矩阵A中m阶满秩子矩阵（∣B∣≠0），称B是规划问题的一个基。设：称B中每个列向量Pj(j=12……m)

为基向量。与基向量Pj

对应的变量xj

为基变量。除基变量以外的变量为非基变量。线性规划模型解的相关概念及基本性质第4页，课件共49页，创作于2023年2月

基本解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基B的基本解。在基本解中变量取非0值的个数不大于方程数m，基解的总数不超过个；

基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。

基本最优解：使目标函数最优的基本可行解成为基本最优解；线性规划模型解的相关概念及基本性质第5页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算例3-1通过下面例3-1来说明线性规划问题的基、对应的基本解、基本可行解的概念和计算.

第6页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释第7页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释第8页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释第9页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释第10页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算第11页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释由于基本解为非负，可见该基本解是基本可行解，基是可行基。该基本解对应于图3-1中的C点。该点是可行域的顶点图3-1线性规划模型对应的基、基本解、基本可行解第12页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释第13页，课件共49页，创作于2023年2月线性规划模型解的相关概念及基本性质

3.线性规划问题解的基本性质第14页，课件共49页，创作于2023年2月思考：通过前面的学习可知，若线性规划模型有最优解，必可在某个极点上达到，即在某个基可行解上取得最优解。因此，你会想到求解线性规化问题最简单的方法是？这种方法的缺陷？线性规划模型解的相关概念及基本性质第15页，课件共49页，创作于2023年2月换一种思路：若从某一基可行解出发，每次总是寻找比上一个“更好”的基可行解，而不去计算不比上一个更好的基可行解，可以减少很大的计算量，怎么实现这种逐步改善的求解方法呢？线性规划模型解的相关概念及基本性质第16页，课件共49页，创作于2023年2月需要解决以下几个问题：（1）如何得到一个初始的基可行解；（2）如何判断当前的基可行解是否达到最优解；（3）若当前解不是最优解，如何去寻找一个改善的基可行解？线性规划模型解的相关概念及基本性质美国数学家丹齐格提出的单纯形法解决了以上三个问题，单纯形法是求解线性规划问题的一种普遍有效方法。第17页，课件共49页，创作于2023年2月单纯形法的基本思路单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束第18页，课件共49页，创作于2023年2月基本原理单纯形法的基本原理初始基可行解的确定最优解的检验换基迭代

最优性检验的依据---检验数最优解判定定理入基变量的确定出基变量的确定第19页，课件共49页，创作于2023年2月单纯形法的基本原理1.初始基可行解的确定B为可行基，由B得到的解为初始基可行解。

第20页，课件共49页，创作于2023年2月单纯形法的基本原理1.初始基可行解的确定

在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。第21页，课件共49页，创作于2023年2月单纯形法的基本原理2.最优解的检验(1)检验数的意义第22页，课件共49页，创作于2023年2月单纯形法的基本原理2.最优解的检验假设

；则有基可行解：

目标函数值：

为了判断是否为最优解，首先把基变量、目标函数用非基变量表示：第23页，课件共49页，创作于2023年2月单纯形法的基本原理2.最优解的检验其中：第24页，课件共49页，创作于2023年2月单纯形法的基本原理2.最优解的检验

(2)最优解的判断法则：若对基可行解，若所有检验数，则为最优解；换个角度，由于每个非基变量检验数非正，引入任意非基变量都不能使Z值上升,故为最优解。若存在某个，则不是最优解，计算过程继续。第25页，课件共49页，创作于2023年2月单纯形法的基本原理2.换基迭代

(1)换入变量（进基变量）(2)换出变量（出基变量）第26页，课件共49页，创作于2023年2月单纯形法的基本原理2.换基迭代(2)换出变量（出基变量）第27页，课件共49页，创作于2023年2月单纯形法的基本原理2.换基迭代(2)换出变量（出基变量）通过初等变换将新的一组基变量用非基变量表示出，判断解的最优性。第28页，课件共49页，创作于2023年2月单纯形表法的计算步骤单纯形表第29页，课件共49页，创作于2023年2月单纯形法的计算步骤例1用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:第30页，课件共49页，创作于2023年2月单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400θicB基bx1x2x3x40x34021100x43013013400检验数第31页，课件共49页，创作于2023年2月单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择θ

，选最小的θ对应基变量作为换出变量。 第32页，课件共49页，创作于2023年2月单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。 第33页，课件共49页，创作于2023年2月单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2换入列bi/ai2，ai2>04010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/5－2/5400－1－1基本最优解、最优值第34页，课件共49页，创作于2023年2月单纯形法的计算步骤例2用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。第35页，课件共49页，创作于2023年2月单纯形法的计算步骤cj12100θicB基变量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第36页，课件共49页，创作于2023年2月单纯形法的计算步骤练习1用单纯形法求解线性规划问题（无穷解的情况）:第37页，课件共49页，创作于2023年2月单纯形法的计算步骤练习2用单纯形法求解线性规划问题（无界解的情况）:第38页，课件共49页，创作于2023年2月单纯形法的计算步骤

关于单纯形法的补充说明：第39页，课件共49页，创作于2023年2月单纯形法的计算步骤 学习要点：

1.线性规划解的概念以及3个基本定理

2.熟练掌握单纯形表法的解题思路及求解步骤第40页，课件共49页，创作于2023年2月 思考：如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将如何构造初始可行基？单纯形法的计算步骤 作业：

P523、4第41页，课件共49页，创作于2023年2月单纯形法的进一步讨论－人工变量法人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。第42页，课件共49页，创作于2023年2月单纯形法的进一步讨论－人工变量法人工变量法：

人工变量时为了获得初始基可行解，在约束条件化为等式后，认为的加入的虚拟变量，只有当他们同时为零，即在最终的单纯形表中它们全部变为非基变量，此时加入人工变量的等式约束才与原约束条件等价。因此在最优解的基变量中不允许含有人工变量，这就要求在迭代过程中把人工变量从基变量中迭代出去，通常采用M法和两阶段法第43页，课件共49页，创作于2023年2月单纯形法的进一步讨论－人工变量法人工变量、松弛变量和剩余变量是不同的，松弛变量、剩余变量可以取零值，也可以取正值。但是人工变量只能取零值，否则约束条件1、2就和原始的约束条件不等价了。为了使得人工变量为零，规定人工变量在目标函数中的系数为-M,M>0,且为任意大的数。这样只要人工变量不为零，目标函数最大值就是一个任意小的数。为了使目标函数实现最大化人工变量要为零，所以只有在最终单纯形表中人工变量为非基变量，人工变量的值才能是0。为了构造初始可行基，强行将人工变量加到约束条件中去；又为了把人工变量从基变量中替换出来，就令人工变量在求最大值的目标函数中为-M,M>0,这一方法称大M法。大M法：第44页，课件共49页，创作于2023年2月单纯形法的进一步讨论－人工变量法例3用大M法解下列线性规划解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。第45页，课件共49页，创作于2023年2月单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给