单纯形法计算步骤.ppt

《单纯形法计算步骤.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第四节单纯形法的计算步骤为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。单纯形表E单位阵N非基阵基变量XB非基变量XN0单纯形表21000检验数单纯形表结构单纯形表—24/65/1C已知21000—24/65/1C检验数单纯形表结构单纯形表基可行解：单纯形表结构单纯形表21000

2、—24/65/1C检验数有时不写此项求单纯形表结构单纯形表21000—24/65/1C检验数求单纯形表结构单纯形表21000—24/65/1C检验数求不妨设此为主列主行单纯形表结构单纯形表21000—24/65/1C检验数主元用单纯形表求解LP问题例、用单纯形表求解LP问题解：化标准型210000150510002462010051100121000—24/65/1主元化为1主列单位向量换出换入表1：列初始单纯形表（单位矩阵对应的变量为基变量）正检验数中最大者对应的列为主列最小的值对应的行为主行21000015051

3、002412/601/600104/60-1/6101/30-1/3015/524/26/40*52*2/6+0*4/61-2/3=表2：换基（初等行变换，主列化为单位向量，主元为1）检验数>0确定主列最小确定主列主元21000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2检验数<=0最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.52*7/21*3/2+0*15/28.5表3：换基（初等行变换，主列化为单位向量，主元为1）210000

4、150510002462010051100121000练习:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列