纯形法(2表格形式).ppt

第五章 单纯形法,Singlex Method,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 从可行域中某一个顶点开始，判断此顶点是否是最优解， 如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。 直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 一、找出一个初始基本可行解(单位矩阵) 二、最优性检验(检验数 j) 三、基变换(换入变量与换出变量),第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 第1步:求初始基可行解,列出初始单纯形表。,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 第1步:求初始基可行解,列出初始单纯形表。,第1步:求初始基可行解,列出初始单纯形表。 例,5.2单纯形法的表格形式,5.2单纯形法的表格形式,第1步:求初始基可行解,列出初始单纯形表。 例,P3 ,P4 ,P5 是单位矩阵,构成一个基,对应变量x3 ,x4 ,x5是基变量.令非基变量x1 ,x2等于零,即找到一个初始基可行解,5.2单纯形法的表格形式,5.2单纯形法的表格形式,?,5.2单纯形法的表格形式,5.2单纯形法的表格形式,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 第1步:求初始基可行解,列出初始单纯形表。 第2步:最优性检验,第2步:最优性检验,5.2单纯形法的表格形式,最优解判别定理 对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数j 0，则这个基可行解是最优解。,5.2单纯形法的表格形式,第2步:最优性检验,5.2单纯形法的表格形式,如果表中所有检验数j 0，且基变量中不含有人工变量时，表中的基可行解，即为最优解,计算结束。 当表中存在j0，如果有Pj 0则问题为无界解，计算结束；否则转入下一步。,5.2单纯形法的表格形式,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 第1步:求初始基可行解,列出初始单纯形表。 第2步:最优性检验 第3步:从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表(简称 迭代 )。,第3步:迭代。 1.确定入基变量,5.2单纯形法的表格形式,由最优判别定理可知，当某个j 0时，非基变量 xj 变为基变量,不取零值可以使目标函数值增大。故要选基检验数大于0的非基变量换到基变量中去。 若有两个以上的j 0，则为了使目标函数增加得更大些，一般选其中的j 最大者的非基变量为入基变量.,5.2单纯形法的表格形式,第3步:迭代。 1.确定入基变量 2.确定出基变量,5.2单纯形法的表格形式,把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值， 把其中最小比值所在的约束方程中的原基变量确定为出基变量。 这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。,5.2单纯形法的表格形式,元数a21决定了从一个基可行解到相邻基可行解的转移去向，取名主元,第3步:迭代。 1.确定入基变量 2.确定出基变量 3.用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。,5.2单纯形法的表格形式,5.2单纯形法的表格形式,5.2单纯形法的表格形式,第3步:迭代。 3.用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。,5.2单纯形法的表格形式,新表中的基仍应是单位矩阵，为此在表中做行的初等变换 设主元为alk 将主元所在第i行的数字除以主元alk ； 将计算得到的第i行的数字乘上（- aik ），加到第i行数字上 重新计算各变量的检验系数,新表中的基仍应是单位矩阵，为此在表中做行的初等变换 设主元为alk 将主元所在第i行的数字除以主元alk ；,新表中的基仍应是单位矩阵，为此在表中做行的初等变换 设主元为alk 将主元所在第i行的数字除以主元alk ； 将计算得到的第i行的数字乘上（- aik ），加到第i行数字上,第3步:迭代。 1.确定入基变量 2.确定出基变量 3.用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。,5.2单纯形法的表格形式,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 第1步:求初始基可行解,列出初始单纯形表。 第2步:最优性检验 第3步:从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表(简称 迭代 )。 第4步：重复2，3两步直到计算结束为止,第2步:最优性检验,5.2单纯形法的表格形式,如果表中所有检验数j 0，且基变量中不含有人工变量时，表中的基可行解，即为最优解,计算结束。 当表中存在j0，如果有Pj 0则问题为无界解，计算结束；否则转入下一步。,第3步:迭代。 1.确定入基变量 2.确定出基变量 3.用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。,5.2单纯形法的表格形式,第3步:迭代。 1.确定入基变量 2.确定出基变量 3.用入基变量替换出基变量，得到一个新的基； 对应这个基可以找到一个新的基可行解； 并画出一个新的单纯形表。,5.2单纯形法的表格形式,5.2单纯形法的表格形式,表中所有检验数j 0，且基变量中不含有人工变量时，表中的基可行解，即为最优解,计算结束。,5.2单纯形法的表格形式,表中所有检验数j 0，且基变量中不含有人工变量时，表中的基可行解，即为最优解,计算结束。,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 5.3 单纯形法的进一步讨论 一、人工变量法,5.3 单纯形法的进一步讨论,一、人工变量法 在上述线性规划问题中，化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作初始基，使得求初始解和建立初始单纯形表都十分方便。 但是如果在化为标准形后，约束条件的系数矩阵中不存在单位矩阵怎么办？,5.3 单纯形法的进一步讨论,一、人工变量法 例：,5.3 单纯形法的进一步讨论,一、人工变量法 例：,添加两列单位向量P6，P7连同约束条件中的向量P5，构成单位矩阵 添加的P6，P7相当于在上述问题的约束条件中添加了变量a1，a2，此即为人工变量,由于约束条件在添加人工变量前已是等式，为使这些等式满足，因此在最优解中人工变量取值必须为零。 为此，令目标函数中人工变量的系数为任意大的负值，用“-M”代表。 “-M”称为罚因子，即只要人工变量大于零，目标函数就不可能最优,5.3 单纯形法的进一步讨论,从上表中可知其基本可行解： x1250， x2100， s10，s2125，s30， a10， a20 是本例题的最优解，其最优值为fz(800)800。因为第三次迭代的所有的检验数都小于等于零。,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 5.3 单纯形法的进一步讨论 一、人工变量法 二、无可行解,5.3 单纯形法的进一步讨论,二、无可行解 例：,5.3 单纯形法的进一步讨论,从迭代的检验数来看j都小于等于零，可知第二次迭代所得的基本可行解已经是最优解了。 其最优解为: x1 2，x2 0，x3 0，x4 0，x5 2， 其最大的目标函数为42M。 我们把最优解代入第2个约束方程 即有： 2x1 + 2x2 4 6。 并不满足原来的约束条件2，可知原线性规划问题无可行解，或者说其可行域为空集，当然更不可能有最优解了。,5.3 单纯形法的进一步讨论,二、无可行解,当线性规划问题中添加了人工变量。 单纯形表中的解因含有人工变量，故实质上是非可行解 则此线性规划无可行解,例1、用单纯形表求解下列线性规划问题。,5.3 单纯形法的进一步讨论,5.3 单纯形法的进一步讨论,从第二次迭代的检验数来看j都小于等于零，可知第二次迭代所得的基本可行解已经是最优解了。 其最优解为: x1 30，x2 6，s1 0，s2 0，s3 0，a1 4 0， 将最优解s3 0，a1 4代入第3个约束方程 得 x1+ x20 +4 40， 即有： x1+ x2 36 40。 并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行域为空集，当然更不可能有最优解了。,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 5.3 单纯形法的进一步讨论 一、人工变量法 二、无可行解 三、无界解,5.3 单纯形法的进一步讨论,三、无界解 在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取得任意的大。,x1,x2,100,300,300,100,200,200,x2 = 250,G,400,400,F,2.2线性规划的图解法,s.t. x2 250（G） x1 0 （H） x2 0,5.3 单纯形法的进一步讨论,三、无界解 在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取得任意的大。 例：,在单纯形表中识别线性规划问题是否无界的方法： 在某次迭代的单纯形表中，如果存在着一个大于零的检验数j ，并且该列的系数向量的每个元素aij(i=1, 2, ., m)都小于或等于零，则此线性规划问题是无界的； 一般地说此类问题的出现是由于建模的错误所引起的。,5.3 单纯形法的进一步讨论,三、无界解,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 5.3 单纯形法的进一步讨论 一、人工变量法 二、无可行解 三、无界解 四、无穷多最优解,5.3 单纯形法的进一步讨论,四、无穷多最优解,设用非基变量表示的目标函数为如下形式 其中，z0为常数项，J是所有非基变量的下标集。由于所有的xj的取值范围为大于等于零，当所有的j都小于等于零时， 可知 是一个小于等于零的数，要使 的值最大，显然只 有为零。我们把这些xj取为非基变量（即令这些xj的值为零），所求得的基可行解就使目标函数值最大为z0。,5.3 单纯形法的进一步讨论,就求得了两组最优解，分别为 x150，x2250，s10，s250，s30， x1100，x2200，s10，s20，s350， 而线性规划的最优值均为15000。 从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解。,四、无穷多最优解,5.3 单纯形法的进一步讨论,2.2线性规划的图解法,x1,x2,100,300,300,100,200,200,400,400,z =50x1+50x2,目标函数：max z = 50 x1 + 50x2 考查目标函数等值线,判断线性规划问题有无穷多最优解的方法： 对某个最优基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。,四、无穷多最优解,5.3 单纯形法的进一步讨论,第五章 单纯形法,5.1 单纯形法的基本思路和原理 5.2 单纯形法的表格形式 5.3 单纯形法的进一步讨论 一、人工变量法 二、无可行解 三、无界解 四、无穷多最优解 五、退化问题,在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。,五、退化问题,5.3 单纯形法的进一步讨论,得到最优解 x11， x20，x32， x41，x50，x60， 其最优值为5。,在单纯形法计算过程中，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这称之为退化。 退化的出现原因是模型中存在多余的约束,使多个基可行解对应同一顶点. 当存在退化问题时,就可能出现迭代计算的循环 (尽管可能性极其微小)。,五、退化问题,5.3 单纯形法的进一步讨论,勃兰特（Bland）法则。 首先我们把松弛变量（剩余变量）、人工变量都用 xj 表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则：,（1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。 （2）在存在两个和两个以上最小比值时，