单纯形法(表格形式)

第五章 单纯形法Singlex Method第五章 单纯形法n 5.1 单纯形法的基本思路和原理n 5.2 单纯形法的表格形式n 从可行域中某一个顶点开始，判断此顶点是否是最优解，n 如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。n 直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。第五章 单纯形法n 5.1 单纯形法的基本思路和原理n 5.2 单纯形法的表格形式n 一、找出一个初始基本可行解 (单位矩阵 )n 二、最优性检验 (检验数 j)n 三、基变换 (换入变量与换出变量 )第五章 单纯形法n 5.1 单纯形法的基本思路和原理n 5.2 单纯形法的表格形式n 第 1步 :求初始基可行解 ,列出初始单纯形表。第五章 单纯形法n 5.1 单纯形法的基本思路和原理n 5.2 单纯形法的表格形式n 第 1步 :求初始基可行解 ,列出初始单纯形表。n 第 1步 :求初始基可行解 ,列出初始单纯形表。例5.2单纯形法的表格形式5.2单纯形法的表格形式n 第 1步 :求初始基可行解 ,列出初始单纯形表。例P3 ,P4 ,P5 是单位矩阵 ,构成一个基 ,对应变量 x3 ,x4 ,x5是基变量.令非基变量 x1 ,x2等于零 ,即找到一个初始基可行解5.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 05.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0?5.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 05.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0第五章 单纯形法n 5.1 单纯形法的基本思路和原理n 5.2 单纯形法的表格形式n 第 1步 :求初始基可行解 ,列出初始单纯形表。n 第 2步 :最优性检验n 第 2步 :最优性检验5.2单纯形法的表格形式最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 j 0，则这个基可行解是最优解。5.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0n 第 2步 :最优性检验5.2单纯形法的表格形式如果表中所有检验数 j 0，且基变量中不含有人工变量时，表中的基可行解，即为最优解 ,计算结束。当表中存在 j 0，如果有 Pj 0则问题为无界解， 计算结束 ； 否则转入下一步。5.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0第五章 单纯形法n 5.1 单纯形法的基本思路和原理n 5.2 单纯形法的表格形式n 第 1步 :求初始基可行解 ,列出初始单纯形表。n 第 2步 :最优性检验n 第 3步 :从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表 (简称 迭代 )。n 第 3步 :迭代 。n 1.确定入基变量5.2单纯形法的表格形式由最优判别定理可知，当某个 j 0时，非基变量 xj 变为基变量 ,不取零值可以使目标函数值增大。故 要选基检验数大于 0的非基变量换到基变量中去。若有两个以上的 j 0， 则为了使目标函数增加得更大些，一般选其中的 j 最大者的非基变量为入基变量 .5.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0n 第 3步 :迭代 。n 1.确定入基变量n 2.确定出基变量5.2单纯形法的表格形式把已确定的入基变量在各约束方程中的 正的系数 除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的 bj 值都大于等于零。5.2单纯形法的表格形式迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0元数 a21决定了从一个基可行解到相邻基可行解的转移去向，取名 主元n 第 3步 :迭代 。n 1.确定入基变量n 2.确定出基变量n 3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。5.2单纯形法的表格形式5.2单纯形法的表格形式5.2单纯形法的表格形式n 第 3步 :迭代 。n 3.用入基变量替换出基变量，得到一个新的基；对应这个基可以找到一个新的基可行解；并画出一个新的单纯形表。5.2单纯形法的表格形式新表中的基仍应是单位矩阵，为此在表中做 行的初等变换设主元为 alka. 将主元所在第 i行的数字除以主元 alk ；b. 将计算得到的第 i行的数字乘上（ - aik ），加到第 i行数字上c. 重新计算各变量的检验系数迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 01 x3 0 0 5 1 0 0 15 3x1 2 1 1/3 0 1/6 0 4 12x5 0 0 2/3 0 -1/6 1 1 3/2zj 2 2/3 0 1/3 0 Z=8j= cj -zj 0 1/3 0 -1/3 0新表中的基仍应是单位矩阵，为此在表中做 行的初等变换设主元为 alka. 将主元所在第 i行的数字除以主元 alk ；迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 01 x3 0 0 5 1 0 0 15 3x1 2 1 1/3 0 1/6 0 4 12x5 0 0 2/3 0 -1/6 1 1 3/2zj 2 2/3 0 1/3 0 Z=8j= cj -zj 0 1/3 0 -1/3 0新表中的基仍应是单位矩阵，为此在表中做 行的初等变换设主元为 alka. 将主元所在第 i行的数字除以主元 alk ；b. 将计算得到的第 i行的数字乘上（ - aik ），加到第 i行数字上迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 00 x3 0 0 5 1 0 0 15 -x4 0 6 2 0 1 0 24 24/6x5 0 1 1 0 0 1 5 5zj 0 0 0 0 0 Z=0j= cj -zj 2 1 0 0 0迭代次数 基 CBx1 x2 x3 x4 x5 b 比 值2 1 0 0 01 x3 0 0 5 1 0 0 15 3x1 2 1 1/3 0 1/6 0 4 12x5 0 0 2/3 0 -1/6 1 1 3/2zj 2 2/3 0 1/3 0 Z=8j= cj -zj 0 1/3 0 -1/3 0n 第 3步 :迭代 。n 1.确定入基变量n 2.确定出基变量n 3.用入基变量替换出基变量，得到一