1、第三节第三节 单纯形法的计算步骤单纯形法的计算步骤 为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。单纯形表单纯形表E单位阵N非基阵基变量XB非基变量XN0 单纯形表单纯形表 2 1 0 0 0 检验数单纯形表结构 单纯形表单纯形表 24/65/1C已知 2 1 0 0 0 24/65/1C检验数单纯形表结构 单纯形表单纯形表基可行解：单纯形表结构 单纯形
2、表单纯形表 2 1 0 0 0 24/65/1C检验数有时不有时不写此项写此项求求求求单纯形表结构 单纯形表单纯形表 2 1 0 0 0 24/65/1C检验数求求单纯形表结构 单纯形表单纯形表 2 1 0 0 0 24/65/1C检验数求求不妨设此不妨设此为主列为主列主行主行单纯形表结构 单纯形表单纯形表 2 1 0 0 0 24/65/1C检验数主元主元用单纯形表求解LP问题例、用单纯形表求解例、用单纯形表求解LPLP问题问题解：化标准型 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 24/65/1主元化为1
3、主列单位向量 换出 换入表表1：列初始单纯形表：列初始单纯形表 （单位矩阵对应的变量为基变量）（单位矩阵对应的变量为基变量）正检验数中最大者对正检验数中最大者对应的列为主列应的列为主列最小的值对应最小的值对应最小的值对应最小的值对应的行为主行的行为主行的行为主行的行为主行 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1/6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 15/524/26/4 0*5 2*2/6 +0*4/61-2/3=表表2：换基：换基 （初等行变换，主列化为单位向量，主元为（初等行变换，主列化为单位向量，主元为1）检验
4、数检验数0确定主列确定主列 最小最小确定主列确定主列主元主元 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 检验数0且且aik(i=1，2,m)，则线性则线性规划具有无界解规划具有无界解；(c)若存在若存在 0且且aik(i=1,m)不全非正，则进行换基不全非正，则进行换基；3.换基：换基：(a)选进基变量：设选进基变量：设 =max|0,选第选第k列所对应列所对应的变量的变量xk为进基变量为进基变量。第第个个比比值值最最小小，选选最最小小比比值值对对应应行行
5、的的基基变变量量为为出出基基变量，若有相同最小比值，则任选一个变量，若有相同最小比值，则任选一个aLk为主元素为主元素。(c)求求新新的的基基可可行行解解：用用初初等等行行变变换换方方法法将将aLk化化为为,第第 k 列列其其它它元元素素化化为为零零（包包括括检检验验数数行行）得得到到新新的的可可行基及基本可行解，再判断是否得到最优解。行基及基本可行解，再判断是否得到最优解。(b)选出基变量选出基变量 ：求最小比值：求最小比值前面所讲的单纯形法，都是针对求最大值问题。对于求最小值问题，可以转换为最大值问题求解。书中所列直接求解最小值问题，请大家自学P35。2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 练习练习:一般主列选择正检验数中最大者对应的一般主列选择正检验数中最大者对应的列列,也可选择其它正检验数的列也可选择其它正检验数的列.以第以第2列列为主列为主列,用单纯形法求解。用单纯形法求解。正检验数对应正检验数对应的列为主列的列为主列第三节第三节 单纯形法的计算步骤单纯形法的计算步骤
