《第二章单纯形法1基本思路和原理课件》由会员分享，可在线阅读，更多相关《第二章单纯形法1基本思路和原理课件（60页珍藏版）》请在金锄头文库上搜索。
1、第二章 单纯形法,Singlex Method,第二章 单纯形法,由美国数学家丹捷格(G.B.Dantzig)提出的，得到最广泛应用的线性规划的代数算法单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解.,我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。,第五章 单纯形法,5.1 单纯形法的基本思路和原理,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),可行解：
2、满足上述约束条件（），（）的解 ， 称为线性规划问题的可行解全部可行解的集合称为可行域,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),最优解： 使目标函数（）达到最大值的可行解称为最优解,5.1 单纯形法的基本思路和原理,基： 设为约束方程组（）的mn阶系数矩阵，（设nm）， 其秩为m，是矩阵中的一个mm的满秩子矩阵，称 是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量，与基向 量j对应的变量xj称为基变量。线性规划中除了基变量以外的变 量称为非基变量。,5.1 单纯形法的基本思路和原理,标准形式为: 目标函数
3、：max z = 50 x1+100 x2+0s1+0s2+0s3 约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,中的每一个列向量p3, p4, p5 是基向量，与其对应的变量s1, s2, s3是基变量。除了基变量以外的变量x1, x2是非基变量。,5.1 单纯形法的基本思路和原理,可以看到 s1, s2, s3的系数列向量,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,是线性独立的,这些向量构成一个基,5.1 单纯形法的基
4、本思路和原理,基： 设为约束方程组（）的mn阶系数矩阵，（设nm）， 其秩为m，是矩阵中的一个mm的满秩子矩阵，称 是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量，与基向 量j对应的变量xj称为基变量。线性规划中除了基变量以外的变 量称为非基变量。,在此例题中： 都是该线性规划的一个基。,这些基都是由3个线性无关的系数列向量组成的,对应的基变量 分别为 x1 , x2 , s1 ; s1, s2, s3; x2 ,s1,s3。,5.1 单纯形法的基本思路和原理,基解： 在约束方程组（E）中，令所有的非基变量： 又因为有 ，根据克莱姆法则，由m个约束方程可以解 出m
5、个基变量的唯一解 。将这个解加上非 基变量取0的值有 ，称X为线性规划问 题的基解。,我们找到A 的一个基:,令这个基的非基变量 x1, s2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.,x1=0, x2=400 s1=-100 s2=0 s3=-150,我们找到A 的一个基:,令这个基的非基变量 x1, s2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解
6、,即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.,x1=0, x2=0, s1=300 s2=400 s3=250,5.1 单纯形法的基本思路和原理,基解： 在约束方程组（E）中，令所有的非基变量： 又因为有 ，根据克莱姆法则，由m个约束方程可以解 出m个基变量的唯一解 。将这个解加上非 基变量取0的值有 ，称X为线性规划问 题的基解。,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),基可行解： 满足变量非负约束条件 ( G ) 的基
7、解称为基可行解。 可行基： 对应于基可行解的基称为可行基。,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.,x1= 0, x2= 400, s1= -100, s2= 0, s3= -150,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到
8、基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.,x1=0, x2=0, s1=300 s2=400 s3=250,x1=0, x2=0, s1=300 s2=400 s3=250,均为基解,x1= 0, x2= 400, s1= -100, s2= 0, s3= -150,基可行解,不是基可行解,均为基,可行基,不是可行基,由于在这个基解中s1100，s3150，不满足该线性规划最后一个变量非负的约束条件，显然不是此线性规划的可行解，一个基解可以是可行解，也可以是非可行解，它们之间的主要区别在于
9、其所有变量的解是否满足非负的条件。,5.1 单纯形法的基本思路和原理,5.1 单纯形法的基本思路和原理,定理: 线性规划问题的基可行解 X 对应线性规划问题可行域的顶点. 在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基可行解，第一个找到的可行域的顶点叫做初始基可行解。,5.1 单纯形法的基本思路和原理,例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解：,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,矩阵方程:,我们找到A 的一个基:,令这个基的非
10、基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,得到基解:,x1=0, x2=0, x3=5 x4=10 x5=4,代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 Z = 5,5.1 单纯形法的基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, x5 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,得到基解:,x1=0, x2=4, x3=5 x4=2 x5=0,代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 Z = 17,即:,5.1 单纯形法的基本思
11、路和原理,5.1 单纯形法的基本思路和原理,单纯形法的基本思路： 从可行域中某一个顶点开始，判断此顶点是否是最优解， 如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。 直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,5.1 单纯形法的基本思路和原理,定理: 线性规划问题的基可行解 X 对应线性规划问题 可行域的顶点. 找顶点就是找基可行解,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 在第二章的例1中我们得到以下数学模型：,例1.目标函数： max z = 50 x1 + 100 x2 约束条件：
12、 s.t. x1 + x2 300 2x1 +x2 400 x2 250 x1 ， x2 0,5.1 单纯形法的基本思路和原理,标准形式为: 目标函数：max z = 50 x1+100 x2+0s1+0s2+0s3 约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s30。,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,一般说来判断一个基是否是可行基，只有在求出其基解后，当其基解所有变量的值都是大于等于零，才能判定这个解是基可行解，这个基是可行基。,一、找出一个初始基可行解,5.1 单纯形法
13、的基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1, s2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.,x1= 0, x2= 400, s1= -100, s2= 0, s3= -150,5.1 单纯形法的基本思路和原理,由于在线性规划的标准型中要求 bj 大于等于零，如果能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序无关紧要的）那么显
14、然所求得的基解一定是基可行解.,一、找出一个初始基可行解,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,即:,求解,即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.,x1=0, x2=0, s1=300 s2=400 s3=250,我们找到A 的一个基:,令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 的约束方程:,矩阵方程 AX = b,得到基解:,x1=0, x2=0, x3=5 x
15、4=10 x5=4,代入目标方程式: max z = 2 x1 + 3 x2 + x3, 得到 Z = 5,这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。 实际上这个基可行解中的各个变量或等于某个 bj 或等于零。,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解,5.1 单纯形法的基本思路和原理,单纯形法的基本思路： 从可行域中某一个顶点开始，判断此顶点是否是最优解， 如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。 直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 二、最优性检验,所谓最优性检验就是判断已求得的基可行解是否是最优解。,5.1 单纯形法的基本思路和原理,二、最优性检验,1、最优性检验的依据检验数 j 一般来说目标函数中既包括基变量，又包括非基变量,现在我们要求只用非基变量来表示目标函数.,max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5 x1 +2x2 +x4 =10 x2 +x5=4 x1-5 0,max z = 50 x1+100 x2 x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x
