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

本章教学目的、重点、难点：理解线性规划模型的可行解、基本解、基本可行解等概念和这些概念之间的关系；熟悉单纯形法的基本思路和单纯形法的基本原理；掌握掌握单纯形法求解线性规划问题的基本步骤；掌握单纯形表法求出线性规划模型的基本最优解；会用计算机软件求解线性规划问题，进一步理解单纯形法的基本原理Chapter3线性规划模型的单纯形法(SimplexMethod)Page2线性规划模型解的相关概念及基本性质1.线性规划问题解的相关概念线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。)3(0)2(st.)1(maxXbAXCXzPage3可行解：满足约束条件②、③的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件②的m×n阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（∣B∣≠0），称B是规划问题的一个基。设：)(11111mmmmmppaaaaB称B中每个列向量Pj(j=12……m)为基向量。与基向量Pj对应的变量xj为基变量。除基变量以外的变量为非基变量。线性规划模型解的相关概念及基本性质Page4基本解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基B的基本解。在基本解中变量取非0值的个数不大于方程数m，基解的总数不超过个；基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。基本最优解：使目标函数最优的基本可行解成为基本最优解；线性规划模型解的相关概念及基本性质mnCPage5线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算例3-112121212max2328416st.412,0zxxxxxxxx通过下面例3-1来说明线性规划问题的基、对应的基本解、基本可行解的概念和计算.Page6解首先将该模型化为标准型0,,,,12416482st.00032max54321524132154321xxxxxxxxxxxxxxxxxz100400100400121A，12168b，00032c线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释Page7线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释在矩阵A中5,3nm，根据基的定义，就要在约束矩阵中找3行3列的矩阵且该矩阵的行列式值不为0，按照排列组合在A中共有1035C个3阶矩阵。分别是，5431054295328432754165315431452132123211P,P,PB,P,P,PBP,P,PB,P,P,PB,P,P,PB,P,P,PBP,P,PB,P,P,PB,P,P,PB,P,P,PB4Page8线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释因为，所以1B是基，321,,xxx是基变量，54,xx是非基变量。求该基对应的基本解，其方法有两种，一是解约束条件组成的方程组并令非基变量为零，二是求1B逆矩阵直接代入公式bB11中就可以求出基变量的值，非基变量的值为零，结合起来就是基解。0160400041211BPage9线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释在约束条件组成的方程组中令非基变量54,xx均为0，得1241648221321xxxxx从而基本解为0,0,2,3,4,,,,T54321xxxxx由于基本可行解中含有负分量，可见该基本解不是基本可行解，基1B不是可行基，该基本解对应于图3-1中的D点，该点是约束条件的交点。Page10线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算04|2B，因此2B是基。421,,xxx是基变量，53,xx是非基变量，在约束条件组成的方程组中令非基变量54,xx为0，得1241648224121xxxxx从而基本解为0,8,0,3,2,,,,T54321xxxxxPage11线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释由于基本解为非负，可见该基本解是基本可行解，基是可行基。该基本解对应于图3-1中的C点。该点是可行域的顶点图3-1线性规划模型对应的基、基本解、基本可行解Page12线性规划模型解的相关概念及基本性质2.基本解和基本可行解的计算与几何解释同理对于其它矩阵可以判断是否为基，如果是基可以求基本解并进一步判断是否为基本可行解。对于基本解和基本可行解可以给出对应于图3-1中的交点，可以看出基本解对应于约束条件的交点，基本可行解对应于可行域的顶点，因此，从图3-1可知交点有8个，基本解就有8个，而可行域顶点有5个，则基本可行解就有5个。显然基本可行解一定是基本解，而基本解不一定是基本可行解；可行域的顶点一定是约束条件的交点，而约束条件的交点不一定是可行域的顶点，这就是基本解和基本可行解的几何解释。Page13线性规划模型解的相关概念及基本性质3.线性规划问题解的基本性质定理1若线性规划问题存在可行域，则其可行域D是凸集。定理2线性规划问题的可行解T21,,,nxxxX为基可行解的充要条件是X的正分量所对应的系数列向量组线性无关。定理3X是基本可行解的充分必要条件是X是可行域D的顶点定理4一个标准的线性规划问题，若有可行解，则至少有一个基本可行解。定理5一个标准的线性规划问题，若有有限的最优值，则一定存在一个基本可行解是最优解。Page14思考：通过前面的学习可知，若线性规划模型有最优解，必可在某个极点上达到，即在某个基可行解上取得最优解。因此，你会想到求解线性规化问题最简单的方法是？这种方法的缺陷？线性规划模型解的相关概念及基本性质Page15换一种思路：若从某一基可行解出发，每次总是寻找比上一个“更好”的基可行解，而不去计算不比上一个更好的基可行解，可以减少很大的计算量，怎么实现这种逐步改善的求解方法呢？线性规划模型解的相关概念及基本性质Page16需要解决以下几个问题：（1）如何得到一个初始的基可行解；（2）如何判断当前的基可行解是否达到最优解；（3）若当前解不是最优解，如何去寻找一个改善的基可行解？线性规划模型解的相关概念及基本性质美国数学家丹齐格提出的单纯形法解决了以上三个问题，单纯形法是求解线性规划问题的一种普遍有效方法。Page17单纯形法的基本思路单纯形法的思路找出一个初始可行解是否最优转移到另一个基本可行解（找出更大的目标函数值）最优解是否循环核心是：变量迭代结束基本原理单纯形法的基本原理初始基可行解的确定最优解的检验换基迭代最优性检验的依据---检验数j最优解判定定理入基变量的确定出基变量的确定Page19单纯形法的基本原理1.初始基可行解的确定)3(0)2(st.)1(maxXbAXCXznpppA,,,21mpppB,,,21100010001BB为可行基，由B得到的解TbBX)0,(1为初始基可行解。Page20单纯形法的基本原理1.初始基可行解的确定在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。Page21单纯形法的基本原理2.最优解的检验(1)检验数的意义0,,,..max211212211111nmnmjjmjmnmjjjnmjjjnjjjxxxbxaxbxaxbxaxtsxcZPage22单纯形法的基本原理2.最优解的检验TmbbbX)0,,0,,,,(2110),,2,1(mibi假设；则有基可行解：目标函数值：;11imiibcZ为了判断是否为最优解，首先把基变量、目标函数1X用非基变量表示：nmjjijiimixabx1,,2,1Page23单纯形法的基本原理2.最优解的检验nmjjjnmjjmiijijmiiinmjjjminmjjijiinmjjjmiiixZxaccbcxcxabcxcxcz1111111111)()(其中：miijijjacc1Page24单纯形法的基本原理2.最优解的检验(2)最优解的判断法则：1X0j1X若对基可行解，若所有检验数，则为最优解；换个角度，由于每个非基变量检验数非正，引入任意非基变量都不能使Z值上升,故为最优解。1X0j1X若存在某个，则不是最优解，计算过程继续。Page25单纯形法的基本原理2.换基迭代(1)换入变量（进基变量）(2)换出变量（出基变量）Page26单纯形法的基本原理2.换基迭代(2)换出变量（出基变量）mkmkmkkkkbxaxbxaxbxax222111ikikiikkikabxxaxia必须有为保证的值实际上没限制；个方程对则其中第,0,0,0Page27单纯形法的基本原理2.换基迭代(2)换出变量（出基变量）通过初等变换将新的一组基变量用非基变量表示出，判断解的最优性。Page28单纯形表法的计算步骤单纯形表jcnmmcccc11BcBXbmcc1mxx1mbb1nmmxxxx11im1mnmmnmaaaa1,11,1100100ijijjaccj0kjkjiiaab其中：Page29单纯形法的计算步骤例1用单纯形法求下列线性规划的最优解0,30340243max21212121xxxxxxxxZ解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:0,,,30340243max432142132121xxxxxxxxxxxxZPage30单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400θicB基bx1x2x3x40x34021100x430130134003)1020(3)(21411311acacc检验数jPage31单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。0j4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表①确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。②确定换出变量。根据下式计算并选择θ，选最小的θ对应基变量作为换出变量。0j}0|max{jjk0minikikiLaabPage32单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。Page33单纯形法的计算步骤cj3400θicB基变量bx1x2x3x40x34021100x430130134000x34x23x14x2jjj换入列bi/ai2，ai204010换出行将3化为15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到1