运筹学单纯形法计算步骤

《运筹学单纯形法计算步骤》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、）2300000321631010-1/24001001001/40002-3/4正检验数中最大者对应的列为主列24—最小的值对应的行为主行主元化为1主列单位向量换出换入表2：基变换（初等行变换，主列化为单位向量，主元为1）230002032831010-1/200-41201001/400-201/4—412表3：基变换（初等行变换，主列化为单位向量，主元为1）00-3/2-1/801001/4000-21/21011/2-1/8023000203442检验数<=0表4：最终单纯形表用单纯形表求解LP问题例解：化标准型2100000015

4、24505100620101100121000表1：列初始单纯形表（单位矩阵对应的变量为基变量）210000150510002462010051100121000—24/65/1主元化为1主列单位向量换出换入正检验数中最大者对应的列为主列最小的值对应的行为主行表1：列初始单纯形表（单位矩阵对应的变量为基变量）21000015051002412/601/600104/60-1/6101/30-1/3015/524/26/40*52*2/6+0*4/61-2/3=检验数>0确定主列最小确定主行主元表2：基变换（初等行变换，主列化为单位向量，主元

5、为1）21000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2检验数<=0表3：基变换（初等行变换，主列化为单位向量，主元为1）210000150510002462010051100121000思考:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列单纯形法的解的情况单纯形法求解线性规划问题，解的情况也有四种：唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零无穷多解无界解无解：下界

6、讨论单纯形法的解的情况例2：第一步：转换为标准形式单纯形法的计算步骤构造单纯形表cj6400CBxBbx1x2x3x4Ө0x3302310150x42432018σj64000x31405/31-2/38.46x1812/301/312σj000-2cjb6400CBxBx1x2x3x4Ө0x31405/31-2/38.46x1812/301/312σjη=48000-24x28.4010.6-0.46x12.410-0.40.6σj000-2单纯形法解的情况(8,0,14,0)和(2.4,8.4,0,0)都是最优解。当有一个非基变量的检验

7、数（imp）值为0时，线性规划问题有多重最优解任意最优解为λ(8,0,14,0)+(1-λ)(2.4,8.4,0,0)12108642024681012CD(1)(2)单纯形法的解的情况单纯形法求解线性规划问题，解的情况也有四种：唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零无穷多解：所有的检验数都小于等于0，至少有一个非基变量的检验数为0无界解无解：下界讨论单纯形法解的情况例：转换为标准形式cj3630-3-400CBxBbx1x2x3x4x5x6Ө0s1511-101050s210650-1015/3σj

8、3630-3-4000s110/301/6-11/61-1/62036x15/315/60-1/601/6—σj00-320-6η=60cj3630-3-400CBxBbx1x2