单纯形法(1基本思路和原理).ppt

第五章 单纯形法,Singlex Method,第五章 单纯形法,由美国数学家丹捷格()提出的，得到最广泛应用的线性规划的代数算法单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解.,我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。,第五章 单纯形法,5.1 单纯形法的基本思路和原理,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),可行解：满足上述约束条件（），（）的解，称为线性规划问题的可行解全部可行解的集合称为可行域,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),最优解：使目标函数（）达到最大值的可行解称为最优解,5.1 单纯形法的基本思路和原理,基：设为约束方程组（）的mn阶系数矩阵，（设nm），其秩为m，是矩阵中的一个mm的满秩子矩阵，称是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量，与基向量j对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。,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。,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,中的每一个列向量p3,p4,p5 是基向量，与其对应的变量s1,s2,s3是基变量。除了基变量以外的变量x1,x2是非基变量。,5.1 单纯形法的基本思路和原理,可以看到 s1,s2,s3的系数列向量,这是由三个五元线性方程组成的方程组，它的系数矩阵为:,是线性独立的,这些向量构成一个基,5.1 单纯形法的基本思路和原理,基：设为约束方程组（）的mn阶系数矩阵，（设nm），其秩为m，是矩阵中的一个mm的满秩子矩阵，称是线性规划问题的一个基不失一般性，设,中的每一个列向量j（j，m）称为基向量，与基向量j对应的变量xj称为基变量。线性规划中除了基变量以外的变量称为非基变量。,在此例题中：都是该线性规划的一个基。,这些基都是由3个线性无关的系数列向量组成的,对应的基变量分别为 x1,x2,s1;s1,s2,s3;x2,s1,s2。,5.1 单纯形法的基本思路和原理,基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。,我们找到A 的一个基:,令这个基的非基变量 x1,s2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,即:,求解,即可得到基变量的唯一一组解:x2=400,s1=-100,s3=-150加上非基变量:x1=0,s2=0,得到此线性规划的一个基解.,x1=0,x2=400s1=-100s2=0s3=-150,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,即:,求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.,x1=0,x2=0,s1=300s2=400s3=250,5.1 单纯形法的基本思路和原理,基解：在约束方程组（E）中，令所有的非基变量：又因为有，根据克莱姆法则，由m个约束方程可以解出m个基变量的唯一解。将这个解加上非基变量取0的值有，称X为线性规划问题的基解。,5.1 单纯形法的基本思路和原理,线性规划问题,(),(),(),(i=1,，m),(j=1,，n),基可行解：满足变量非负约束条件(G)的基解称为基可行解。可行基：对应于基可行解的基称为可行基。,我们找到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,即:,求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.,x1=0,x2=0,s1=300s2=400s3=250,x1=0,x2=0,s1=300s2=400s3=250,均为基解,x1=0,x2=400,s1=-100,s2=0,s3=-150,基可行解,不是基可行解,均为基,可行基,不是可行基,由于在这个基解中s1100，s3150，不满足该线性规划最后一个变量非负的约束条件，显然不是此线性规划的可行解，一个基解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。,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 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,得到基解:,x1=0,x2=0,x3=5x4=10 x5=4,代入目标方程式:max z=2 x1+3 x2+x3,得到 Z=5,5.1 单纯形法的基本思路和原理,我们找到A 的一个基:,令这个基的非基变量 x1,x5 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,得到基解:,x1=0,x2=4,x3=5x4=2x5=0,代入目标方程式:max z=2 x1+3 x2+x3,得到 Z=17,即:,5.1 单纯形法的基本思路和原理,5.1 单纯形法的基本思路和原理,单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,5.1 单纯形法的基本思路和原理,定理:线性规划问题的基可行解 X 对应线性规划问题可行域的顶点.找顶点就是找基可行解,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解 在第二章的例1中我们得到以下数学模型：,例1.目标函数：max z=50 x1+100 x2 约束条件：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 单纯形法的基本思路和原理,我们找到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 大于等于零，如果能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序无关紧要的）那么显然所求得的基解一定是基可行解.,一、找出一个初始基可行解,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,即:,求解,即可得到基变量的唯一一组解:s1=300,s2=-400,s3=250加上非基变量:x1=0,x2=0,得到此线性规划的一个基解.,x1=0,x2=0,s1=300s2=400s3=250,我们找到A 的一个基:,令这个基的非基变量 x1,x2 为零,这时约束方程就变为基变量的约束方程:,矩阵方程 AX=b,得到基解:,x1=0,x2=0,x3=5x4=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 x2+s3=250 x1,x2,s1,s2,s30。,5.1 单纯形法的基本思路和原理,1、最优性检验的依据检验数 j 一般来说目标函数中既包括基变量，又包括非基变量,现在我们要求只用非基变量来表示目标函数.在约束等式中通过移项等处理就,用非基变量来表示基变量，用非基变量的表示式代替目标函数中基变量，目标函数中只含有非基变量.此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为i。,5.1 单纯形法的基本思路和原理,分析 max z=50 x1+100 x2 x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s30。,本例题中,由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。可知150，2100，30，40，50。,5.1 单纯形法的基本思路和原理,本例题中,由于初始可行解中x1，x2为非基变量，而x3为基变量,应该在约束等式中通过移项处理,用非基变量来表示基变量,得到x3=5-x1,代入目标函数得到z=5+x1+3x2 可知11，23，30，40，50。,max z=2 x1+3 x2+x3 x1+x3=5 x1+2x2+x4=10 x2+x5=4 x1-5 0,5.1 单纯形法的基本思路和原理,二、最优性检验,1、最优性检验的依据检验数 j2、最优解判别定理 对于求最大目标函数的问题中，对于某个基可行解，如果所有检验数j 0，则这个基可行解是最优解。,5.1 单纯形法的基本思路和原理,2、最优解判别定理,设用非基变量表示的目标函数为如下形式其中，z0为常数项，J是所有非基变量的下标集。由于所有的xj的取值范围为大于等于零，当所有的j都小于等于零时，可知 是一个小于等于零的数，要使 的值最大，显然只 有为零。我们把这些xj取为非基变量（即令这些xj的值为零），所求得的基可行解就使目标函数值最大为z0。,在本例题中由于150，2100，都大于零，显然这个基可行解不是最优解，所以需要找更好的基可行解。,分析 max z=50 x1+100 x2 x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s30。,5.1 单纯形法的基本思路和原理,5.1 单纯形法的基本思路和原理,本例题中,由于初始可行解中x1，x2为非基变量，而x3为基变量,应该在约束等式中通过移项处理,用非基变量来表示基变量,得到x3=5-x1,代入目标函数得到z=5+x1+3x2 可知11，23，30，40，50。,max z=2 x1+3 x2+x3 x1+x3=5 x1+2x2+x4=10 x2+x5=4 x1-5 0,x1=0,x2=0,x3=5x4=10 x5=4,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解二、最优性检验 三、基变换,定义:两个基之间变换且仅变换一个基变量,则称为相邻,x1 x2 s1 s2 s3,s1 s2 s3,x2 s1 s3,三、基变换 通过检验，可知该初始基可行解不是最优解。以下介绍如何进行基变换找到另一个新的可行解，具体的做法是从可行基中换一个列向量，得到一个新的可行基.使得求解得到的新的基可行解，使得其目标函数值更优。为了换基就要确定换入变量与换出变量。,1、入基变量的确定由最优判别定理可知，当某个j 0时，非基变量xj变为基变量不取零值可以使目标函数值增大,故要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的j 0，则为了使目标函数增加得更大些，一般选其中的j 最大者的非基变量为入基变量，,5.1 单纯形法的基本思路和原理,分析 max z=50 x1+100 x2 x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s30。,可知150，2100，30，40，50。,在本例题中2100是检验数中最大的正数，故选 x2为入基变量。,5.1 单纯形法的基本思路和原理,用非基变量来表示基变量,得到x3=5-x1,代入目标函数得到:z=5+x1+3x2 可知11，23，30，40，50。,max z=2 x1+3 x2+x3 x1+x3=5 x1+2x2+x4=10 x2+x5=4 x1-5 0,在本例题中23是检验数中最大的正数，故选 x2为入基变量。,2、出基变量的确定 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？如果我们确定s1为出基变量，则新的基变量为x2，s2，s3，因为非基变量x1s10，则从下式求得基解：x10，x2300，s10，s2100，s350。显然这不是基可行解，所以s1不能作为出基变量。,如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1s30，我们也可以从下式：求出基解：x10，x2250，s150，s2150，s30。因为此解满足非负条件，是基可行解，故s3可以确定为出基变量。能否在求出基解以前来确定出基变量呢？,确定出基变量的方法如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。,在本例题中约束方程为 在第二步中已经知道x2为入基变量，把约束方程中的x2为正的系数除对应的常量，得,确定出基变量的方法如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解二、最优性检验 三、基变换,x1 x2 s1 s2 s3,s1 s2 s3,x2 s1 s2,其中b3/a32的值最小，所以可以知道在原基变量中系数向量为e3=(0,0,1)T的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。令非基变量为零，得：求解得到新的基可行解：x10，x2250，s150，s2150，s30。目标函数值为点 50 x1+100 x22500,5.1 单纯形法的基本思路和原理,一、找出一个初始基可行解二、最优性检验 三、基变换,5.1 单纯形法的基本思路和原理,max z=2 x1+3 x2+x3 x1+x3=5 x1+2x2+x4=10 x2+x5=4 x1-5 0,在本例题中23是检验数中最大的正数，故选 x2为入基变量。把约束方程中的x2为正的系数除对应的常量，得,其中b3/a32的值最小，所以可以知道在原基变量中系数向量为p5=(0,0,1)T的基变量x5为出基变量，这样可知x2，x3，x4为基变量，x1，x5为非基变量。令非基变量为零，得：求解得到新的基可行解：x10，x24，x35，x42，x50。目标函数值为 3x2+x317,x3=5 2x2+x4=10 x2=4,max z=2 x1+3 x2+x3 x1+x3=5 x1+2x2+x4=10 x2+x5=4 x1-5 0,