单纯形法计算步骤

第四节单纯形法的计算步骤为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。0........................................................111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxcZbxaxaxbxaxaxbxaxax单纯形表0...1...10................10...10.......Z-211211212111121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxE单位阵N非基阵基变量XB非基变量XNN0单纯形表xxxxmn1221000jcBCbBXjjzc检验数bbm''1xxm1ccm1单纯形表结构单纯形表—24/65/1minA0znmcccc21C已知xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1单纯形表结构单纯形表A0z)0,,0,,,(1mbbX基可行解：单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ10101'1'0)()(检验数令：令：有时不写此项求单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ10101'1'0)()(检验数令：令：jcmjjaa1j求单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zkmmkmaa,,1km求不妨设此为主列klmlkimkimiiabaab'''''0minl主行单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zkmmkmaa,,1kmlkmla,主元用单纯形表求解LP问题0,524261552max212121221xxxxxxxxxz例、用单纯形表求解LP问题解：化标准型0,,524261550002max515214213254321xxxxxxxxxxxxxxxz210000150510002462010051100121000jcBCbBX1x3x2x4x5xjjzc3x4x5x—24/65/1min主元化为1主列单位向量换出换入1x4x表1：列初始单纯形表（单位矩阵对应的变量为基变量）正检验数中最大者对应的列为主列最小的值对应的行为主行21000015051002412/601/600104/60-1/6101/30-1/30jcBCbBX1x3x2x4x5xjjzc3x1x5x15/524/26/4min0*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jcBCbBX1x3x2x4x5xjjzc3x1x2xmin检验数=0最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.52*7/21*3/2+0*15/28.5表3：换基（初等行变换，主列化为单位向量，主元为1）210000150510002462010051100121000jcBCbBX1x3x2x4x5xjjzc3x4x5x练习:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列