运筹学单纯形法计算步骤

1第一章线性规划与单纯形法第四节单纯形法的计算步骤为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。2第一章线性规划与单纯形法0........................................................111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxcZbxaxaxbxaxaxbxaxax单纯形表在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。3第一章线性规划与单纯形法0...1...10................10...10.......Z-211211212111121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxB基矩阵N非基阵基变量XB非基变量XNN0单纯形表4第一章线性规划与单纯形法121111212-Z.......01...01...........mmnmnmnxxxxxbaaaa1211,1111.....01...100...0mmmnmmmmmiimniiniiiiibbaabccaccacb单纯形表5xxxxmn1221000jcBCbBXjjzc检验数bbm''1xxm1ccm1单纯形表结构单纯形表—24/65/1minA0znmcccc21C已知6xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1单纯形表结构单纯形表A0z)0,,0,,,(1mbbX基可行解：7单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ10101'1'0)()(检验数令：令：有时不写此项求8单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ10101'1'0)()(检验数令：令：jcmjjaa1j求9单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zkmmkmaa,,1km求不妨设此为主列klmlkimkimiiabaab'''''0minl主行10单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zkmmkmaa,,1kmlkmla,主元11第一章线性规划与单纯形法用单纯形表求解例112345123142512345max2300028416..412,,,,0zxxxxxxxxxxstxxxxxxx12jcBCbBX1x3x2x4x5xjjzc3x4x5x表1：列初始单纯形表（单位矩阵对应的变量为基变量）23000000816121210040010040012300000(0,0,8,16,12)TzX13jcBCbBX1x3x2x4x5xjjzc3x4x5x230000008161212100400100400123000正检验数中最大者对应的列为主列4—3min最小的值对应的行为主行主元化为1主列单位向量换出换入2x5x表1：列初始单纯形表（单位矩阵对应的变量为基变量）14jcBCbBX1x3x2x4x5xjjzc3x4x2x2300000321631010-1/24001001001/40002-3/4正检验数中最大者对应的列为主列24—min最小的值对应的行为主行主元化为1主列单位向量换出换入1x3x1339(0,3,2,16,0)TzX表2：基变换（初等行变换，主列化为单位向量，主元为1）15jcBCbBX1x3x2x4x5xjjzc1x4x2x230002032831010-1/200-41201001/400-201/4—412min*2223313(2,3,0,8,0)TzX表3：基变换（初等行变换，主列化为单位向量，主元为1）1600-3/2-1/801001/4000-21/21011/2-1/80jcBCbBX1x3x2x4x5xjjzc1x5x2x23000203442min检验数=0**3243214(4,2,0,0,4)TzXX表4：最终单纯形表17用单纯形表求解LP问题例122121212max25156224..5,0zxxxxxstxxxx18解：化标准型123452121234155max20005156224..5,,0zxxxxxxxxstxxxxxxx19jcBCbBX1x3x2x4x5xjjzc3x4x5x210000001524505100620101100121000表1：列初始单纯形表（单位矩阵对应的变量为基变量）20210000150510002462010051100121000jcBCbBX1x3x2x4x5xjjzc3x4x5x—24/65/1min主元化为1主列单位向量换出换入1x4x正检验数中最大者对应的列为主列最小的值对应的行为主行表1：列初始单纯形表（单位矩阵对应的变量为基变量）2121000015051002412/601/600104/60-1/6101/30-1/30jcBCbBX1x3x2x4x5xjjzc3x1x5x15/524/26/4min0*52*2/6+0*4/61-2/3=检验数0确定主列最小确定主行主元表2：基变换（初等行变换，主列化为单位向量，主元为1）2221000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2jcBCbBX1x3x2x4x5xjjzc3x1x2xmin检验数=0**73152108.52227315(,,,0,0)222TzX表3：基变换（初等行变换，主列化为单位向量，主元为1）23210000150510002462010051100121000jcBCbBX1x3x2x4x5xjjzc3x4x5x思考:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列Page24单纯形法的解的情况单纯形法求解线性规划问题，解的情况也有四种：唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零无穷多解无界解无解：下界讨论Page25单纯形法的解的情况例2：第一步：转换为标准形式2146maxxxZ0,24233032..212121xxxxxxts43210046maxxxxxZ0,,24233032..41421321xxxxxxxxtsPage26单纯形法的计算步骤构造单纯形表cj6400CBxBbx1x2x3x4Ө0x3302310150x42432018σj64000x31405/31-2/38.46x1812/301/312σj000-221210046maxssxxZ0,,,24233032..2121221121ssxxsxxsxxtsPage27cjb6400CBxBx1x2x3x4Ө0x31405/31-2/38.46x1812/301/312σjη=48000-24x28.4010.6-0.46x12.410-0.40.6σj000-2Page28单纯形法解的情况(8,0,14,0)和(2.4,8.4,0,0)都是最优解。当有一个非基变量的检验数（imp）值为0时，线性规划问题有多重最优解任意最优解为λ(8,0,14,0)+(1-λ)(2.4,8.4,0,0)12108642024681012CD2146maxxxZ0,24233032..212121xxxxxxts(1)(2)Page29单纯形法的解的情况单纯形法求解线性规划问题，解的情况也有四种：唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零无穷多解：所有的检验数都小于等于0，至少有一个非基变量的检验数为0无界解无解：下界讨论Page30单纯形法解的情况例：转换为标准形式4,3,2,1,010565..433036max4213214321ixxxxxxxtsxxxxzi0,,,,,10565..00433036max21432124211321214321ssxxxxsxxxsxxxtsssxxxxzPage31cj3630-3-400CBxBbx1x2x3x4x5x6Ө0s1511-101050s210650-1015/3σj3630-3-4000s110/301/6-11/61-1/62036x15/315/60-1/601/6—σj00-320-6η=6012345612351246123412max363034005..6510,,,,,0zxxxxxxxxxxstxxxxxxxxssPage32cj3630-3-400CBxBbx1x2x3x4x5x6Ө0s110/301/6-11/61-1/62036x15/315/60-1/601/6—sacj36300-606σj00-320-6-4x42001-616-136x1511-1010σj0-280-12-4Page33单纯形法的基本思想最优解的判断若为一基本可行解，有一个，并且对一切，有,那么该线性规划问题有无界解。TmbbbX)0,,0,,,,(''2'1)0(0jimp0'kmiami,,1nnmmmmmmnnmmnnmmxaxabxxaxabxxaxabx'1'1''21'12'22'11'11'11Page34单纯形法解的情况X3可以增长到无穷大，所以线性规划问题有无界解Page35单纯形法的解的情况单纯形法求解线性规划问题，解的情况也有四种：唯一最优解：上面的情况，所有的检验数都小于等于0，并且非基变量的检验数都小于零无穷多解：所有的检验数都小于等于0，至少有一个非基变量的检验数为0无界解：如果某imp0，而且对应列中所有的系数都小于等于0，这时，变量可以增长到无穷大，线性规划问题有无界解无解：下节讨论