第二节 对偶单纯形法

对偶单纯形法不是用单纯形法求解对偶问题，而是借助于对偶关系和对偶理论，用单纯形法求解原问题．2.3对偶单纯形法单纯形法换基迭代的前提是所选基必须是可行基，即其对应的解必须是基本可行解．而对偶单纯形法允许从非基本可行解开始进行换基迭代．123456xxxxxxS4x0010132001132006x10100105x50101010目标0前提单纯形法123456xxxxxxS4x0010-1-3-2001132006x10100105x-50-1-21010前提0目标对偶单纯形法定理3.4若原始问题的最优解存在，则用单纯形法求解时，其对偶问题的最优解可同时在最优单纯形表上得到，且顺次等于松弛变量或剩余变量对应的检验数的相反数．回顾12max24Sxx1228xx126xx14x23x12,0xx对偶问题1234minW6843yyyy1232yyy12424yyy140y16000-200S1210010-2x23010001x31001-101x52000-112x1234yyyy56yy因此，对偶单纯形法换基迭代的前提是保证对偶问题基本解的可行性．原始问题的单纯形表的检验数行非正意味着对偶问题基本解的可行性．例1用对偶单纯形法求解线性规划问题123min23Sxxx1231232312342820xxxxxxxxxxx、、123min23Sxxx12312323166452+=42=82+0++=xxxxxxxxxxxxxx，，，解将原问题化为如下形式，写出增广矩阵-11-1100-41120108-101001-2S6x4x0-1-2-30005x-4-11-11008112010-20-11001-11-1100-41120108-101001-2123min23Sxxx初始基：0456(,,)BPPP100010001初始单纯形表S6x4x0-1-2-30005x-4-11-11008112010-20-11001初始单纯形表在“b”列找出最小的负数，用它所在行的所有负数去除对应的检验数，通过最小比值法则确定轴心项，进行换基迭代.S6x1x40-3-2-1005x41-11-1004021110-20-11001第二单纯形表S6x1x40-3-2-1005x41-11-1004021110-20-11001第二单纯形表重复上述过程，继续换基迭代.S2x1x1000-5-10-35x6100-10-1000311-2201-100-1第三单纯形表S2x1x1000-5-10-35x6100-10-1000311-2201-100-1第三单纯形表“b”列元素全都非负，第三单纯形表即最优单纯形表.得原问题的最优解为1236,2,0;xxx最优值为10.S对偶单纯形法是在原问题的非基本可行解下进行换基迭代的，其前提是保证对偶问题的可行性，即保证单纯形表中所有检验数非正．总之，在单纯形表中，只要能保证原问题或对偶问题的任一可行性，即可进行换基迭代，直到找出最优解．例2用对偶单纯形法求解线性规划问题123min234wxxx123123123232340xxxxxxxxx、、解将原问题化为如下形式，写出增广矩阵121103213014123min234wxxx1231231545232340xxxxxxxxxx、、w4x0-2-3-4005x-3-1-2-110-4-21-301选取初始基：045(,)BPP1001初始单纯形表121103213014123min234wxxx得初始单纯形表w4x0-2-3-4005x-3-1-2-110-4-21-301初始单纯形表w4x-40-4-10-11x-10-52121-12第二单纯形表21-12320-12换基迭代,得第二单纯形表继续换基迭代，得第三单纯形表w4x-40-4-10-11x-10-52121-12第二单纯形表21-12320-12第三单纯形表w2x1x3-500-95-85-1552501-15-25151151075-15-25第三单纯形表即最优单纯形表，得原问题的最优解为123115,25,0;xxx最优值为35.5w第三单纯形表w2x1x3-500-95-85-1552501-15-25151151075-15-25本节作业77页3.2用对偶单纯形法求解线性规划问题（1）、（3）