第三讲线性规划的二阶段法Max

1、第一章第一章 线性规划及其扩展线性规划及其扩展 第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论 线性规划的人工变量法线性规划的人工变量法目前有两种方法：目前有两种方法：大大M M法法和和二阶段法二阶段法。人人工工变变量量法法在讨论单纯形法时，我们在讨论单纯形法时，我们总是假定总是假定AXAXb b的系数矩阵的系数矩阵A A的秩的秩r(A)=mn,r(A)=mn,或者已有一个可行基。或者已有一个可行基。但是，在许多但是，在许多问题中，初始可行基是不容易找到的，或者问题中，初始可行基是不容易找到的，或者A A不满秩。不满秩。这样单纯形法就很难进行。这样单纯形法就很难进行。所以，我们要探讨如何

2、寻找第一个可行基？所以，我们要探讨如何寻找第一个可行基？11 112 211121 122 22221 12 201,2,01,2,n nn nmmmn nmmjia xa xa xyba xaxaxybaxaxaxybxjnyim大大M M法（法（1 1）12111 112211121 12222221 122max(1). .01,2,01,2,njjmjnnnnmmmnnmmjizc xMyMyMya xa xa xybLPa xa xa xybs taxaxaxybxjnyim把原问题化为下列形式：其中把原问题化为下列形式：其中M M是任意大的正数是任意大的正数大大M M法（法（2 2

3、）关于大关于大M M法的几点注释：法的几点注释：(1)在引入人工变量之前，约束条件已是等式，为了这些等式得到满足，因此在最优解中人工变量取值必须为零；为此在目标函数中人工变量的取值为充分小的负数，用“-M”代表；(2)若在单纯形表中有j0，且存在非零人工变量，则原问题无可行解；若基变量中不再含有非零的人工变量，这表示原问题有解；(3)引入的人工变量个数越少越好，只要出现单位矩阵作为基阵即可。大大M M法举例（法举例（1 1）1312312323min 3421(1). .390,1,2,3jzxxxxxxxxLPstxxxj131234123523max3421.390,1,2,3,4,5jz

4、xxxxxxxxxxstxxxj例例解：将原问题化为标准形为：大大M M法举例（法举例（2 2）1323123412352233max3421.390,1,2,3,4,5,0,2,3jizxxMyMyxxxxxxxxystxxyxjyi引入的人工变量个数越少越好引入人工变量y2,y30,由大M法得辅助问题为辅助问题为：其中大M为任意大的正数得上述辅助问题的单纯形初表为：大大M法举例（法举例（3） T(B1)XB b x1 x2 x3 x4 x5 y2 y3x4 y2 y3419 -z10M 1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0 1-2M-3 4M

5、 1 0 -M 0 0 T(B2)x4 x2 y3 -z3 3 0 2 1 1 -1 0 1 -2 1 -1 0 -1 1 0 6 6 0 4 0 3 -3 1 6M6M-30 4M+1 03M -4M0人工变量优先出基人工变量优先出基大大M法举例（法举例（4） T(B3)XB b x1 x2 x3 x4 x5 y2 y3x4 x2 x1031 -z 30 0 0 1 -1/2 1/2 -1/2 0 1 1/3 0 0 0 1/31 0 2/3 0 1/2 -1/2 1/60 0 3 0 3/2 -M-3/2 -M+1/2 T(B4)x4 x2 x3 -z00 0 0 1 -1/2 1/2 -

6、1/2 5/2-1/2 1 0 0 -1/4 1/4 1/4 3/23/2 0 1 0 3/4 -3/4 1/4 -3/2-9/20 0 0-3/4-M+3/4 -M-1/4大大M法举例（法举例（5）原线性规划问题的最优解为*5 30,0,0,0,0,2 2TX*32z 最优值为：因为在单纯形表T(B4)中，非基变量检验数均小于等于零，且人工变量均为非基变量，取值为零，故原线性规划问题达到最优。线性规划的二阶段法线性规划的二阶段法(1)原线性规划问题为原线性规划问题为第一阶段第一阶段:y y1 1， y y2 2， y ym m称为人工变量称为人工变量构造原构造原(LP)的辅助问题的辅助问题m

7、ax(). .0zCXLPAXbs tX1211 112211121 12222221 122in(1). .01,2,01,2,mnnnnmmmnnmmjimwyyya xa xa xyba xa xa xybLPsta xaxaxybxjnyim线性规划的二阶段法线性规划的二阶段法(2)原原(LP)的辅助问题的标准形式为：的辅助问题的标准形式为：1211 112211121 12222221 122max(1). .01,2,01,2,mnnnnmmmnnmmjiwwyyya xa xa xyba xa xa xybLPsta xaxaxybxjnyim 辅助问题必有最优解辅助问题必有最优

8、解线性规划的二阶段法线性规划的二阶段法(初始单纯形表初始单纯形表1)1.00.0.10.0.01.212222111211mnmmnnaaaaaaaaaA).(21mnnnPPPB(0 0.011. 1)C (11.1)BCTmbbbb).(21辅助问题的标准形式辅助问题的标准形式的系数矩阵为：的系数矩阵为：线性规划的二阶段法线性规划的二阶段法(初始单纯形表初始单纯形表2)用单纯形法求解用单纯形法求解,最终得到辅助问题的最优单纯形表最终得到辅助问题的最优单纯形表T(B*)二阶段法的计算步骤二阶段法的计算步骤:第二步第二步 若若 w*0,则原线性规划无可行解则原线性规划无可行解,停止求解停止求解

9、,否则转第三步否则转第三步.第一步第一步 用单纯形法求辅助问题的最优单纯形表用单纯形法求辅助问题的最优单纯形表T(B*)和和最优值最优值w*. 第三步第三步 T(B*)中基变量中不含人工变量中基变量中不含人工变量y,则把则把T(B*)中人中人工变量所在列划去工变量所在列划去,把检验数行用原规划的目标函把检验数行用原规划的目标函数的系数替代再把基变量的检验数化为数的系数替代再把基变量的检验数化为0,即得原即得原规划的一个可行基的单纯形表规划的一个可行基的单纯形表.再用单纯形法迭再用单纯形法迭代代,直到终止直到终止.否则转第四步否则转第四步. 第四步第四步 w*=0,T(B*)中基变量中含有人工变

10、量中基变量中含有人工变量yr,若若yr所在所在行的对应的行的对应的X系数全为系数全为0 ,则划去则划去T(B*)中中yr所在行所在行和所在的列和所在的列,转第三步转第三步。否则以某变量。否则以某变量xS的系数的系数brs 0为轴心项进行换基迭代为轴心项进行换基迭代后转第三步后转第三步。 线性规划的二阶段法举例（线性规划的二阶段法举例（1）例例1. 用二阶段法求解下列用二阶段法求解下列(LP)问题问题 1231231323123in-3-2-64. .3,0mzxxxxxxxxs txxxxx1231234135236max3264. .30(1,.,6)jzzxxxxxxxxxxs txxxx

11、j 解解: 化原问题为标准形式化原问题为标准形式 23123413522363in64. .30(1,.,6),0jimwyyxxxxxxxys txxxyxjy则第一阶段的辅助问题为则第一阶段的辅助问题为 线性规划的二阶段法举例（线性规划的二阶段法举例（1-2） 23123413522363max64. .30(1,.,6),0jiwwyyxxxxxxxys txxxyxjy 辅助问题的标准形式为辅助问题的标准形式为 线性规划的二阶段法举例（例线性规划的二阶段法举例（例1-3）则辅助问题的单纯表则辅助问题的单纯表 T(B1)XB b x1 x2 x3 x4 x5 x6 y2 y3x4 y2

12、y3643 w 7 1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 1 1 -2 0 -1 -1 0 0 T(B2)x4 x1 y3 w2 0 1 2 1 1 0 -1 04 1 0 -1 0 -1 0 1 03 0 1 -1 0 0 -1 0 1 301 -1 0 0-1 -1 0二阶段法举例（例二阶段法举例（例1-4） T(B2)x4 XB b x1 x2 x3 x4 x5 x6 y2 y3x1 y3 w2 0 1 2 1 1 0 -1 04 1 0 -1 0 -1 0 1 03 0 1 -1 0 0 -1 0 1 30 1 -1 0

13、0 -1-10 x2 T(B3)x1y3w2 0 1 2 1 1 0 -1 04 1 0 -1 0 -1 0 1 01 0 0 -3 -1 -1 -1 1 1 1 0 0 -3 -1 -1 -1 0 0 因为辅助问题的因为辅助问题的最优值最优值W*=10，则原问题无可行解，则原问题无可行解。线性规划的二阶段法线性规划的二阶段法 例例2-1例例2 用二阶段法解用二阶段法解线性规划线性规划 121121234223331324ax-4 -32( ). .30,1,2,3,4jmzxxxxxxlpstxxxj解解: 引进人工变量引进人工变量y20，建立第一阶段的辅助问题为建立第一阶段的辅助问题为 2

14、1121234223133132242min2( ).30,1,2,3,4;0jw yxxxxlpstxxyxjy线性规划的二阶段法举例（例线性规划的二阶段法举例（例2-2） 辅助问题的标准形式为辅助问题的标准形式为 2112123422333132242max2. .30,1,2,3,4;0jwwyxxxxstxxyxjy 则第一阶段的初始单纯形表则第一阶段的初始单纯形表 为为T（B1） XB b x1 x2 x3 x4 y2 x2 y2 2 31/2 1 1/2 -2/3 0 3/2 0 3/4 0 1 w 33/2 0 3/4 0 0例例2-3 T(B1) x2 x1w 1 0 1 1/

15、4 -2/3 -1/321 0 1/2 0 2/3 00000 T(B2)-1例例2-4得得w*=0，且基变量中不含有人工变量，则划去，且基变量中不含有人工变量，则划去T(B2)中中y2所在列所在列,把检验数行用原问题的目标函数的系数替代再把把检验数行用原问题的目标函数的系数替代再把基变量的检验数化为基变量的检验数化为0,即得第二阶段的初始单纯形表即得第二阶段的初始单纯形表. T(B2)c-4-300 XB b x1 x2 x3 x4 y2 x2 x1 1 20 1 1/4 -2/3 -1/3 1 0 1/2 0 2/3 w 00 0 0 0 -1-z 11 0 0 11/4 -2 例例2-5

16、则原问题的一个初始单纯形表如下则原问题的一个初始单纯形表如下x2 x1 12 0 1 1/4 -2/3 1 0 1/2 0 -z 0 0 11/4 -2 XBb x1 x2 x3 x4 x2 x3 -z 110-1/2 1 0 -2/3 4 2 0 1 0 0-11/2 0 0 -2 原问题最优解原问题最优解X*=(0,0,4,0)T原问题最优值为原问题最优值为z*=0例例3-1例例3 用二阶段法解下用二阶段法解下列线性规划列线性规划 12123124134min212( ).210,1,2,3,4jzxxxxxxxxlpstxxxxj解解: 该问题的标准形式为：该问题的标准形式为：12123

17、124134max212( 1). .210,1,2,3,4jzzxxxxxxxxlpstxxxxj 线性规划的二阶段法举例（例线性规划的二阶段法举例（例3-2）123123112421343max12. .210,1,2,3,4,0,1,2,3jjwwyyyxxxyxxxystxxxyxjyj 辅助问题的标准形式为辅助问题的标准形式为 则第一阶段的单纯形初表为则第一阶段的单纯形初表为T（B1）123123112421343min12(2). .210,1,2,3,4,0,1,2,3jjwyyyxxxyxxxylpstxxxyxjyj引进引进人工变量人工变量y1,y2,y3，建立第一阶段的辅助

18、问题为：建立第一阶段的辅助问题为：例例3-3 XB b x1 x2 x3 x4 y1 y2 y3 y1 y2 y3 1 2 1-1 1 1 0 1 0 0 1 1 0 1 0 1 0 2 0 -1 1 0 0 1 w 4 2 2 0 2 0 0 0 T(B1)y1 y2w3/2 0 1 1/2 1/2 1 0 1/23/20 1 1/2 1/2 0 1 -1/2 3021 10 T(B2)0 x11/2 1 0 -1/2 1/2 0 0 1/2 -1例例3-4 XB bx1 x2 x3 x4 y1 y2 y3 y1 y2 x1 3/2 3/2 1/2 0 1 1/2 1/2 1 0 1/2 0

19、 1 1/2 1/2 0 1 -1/2 1 0 -1/2 1/2 0 0 1/2 w 3 0 2 1 1 0 0 -1 T(B2)x2 y2w3/2 0 1 1/2 1/2 1 0 1/200 0 0 0 -1 1 -1 0000 00 T(B3)0 x11/21 0 -1/2 1/2 0 0 1/2 -2例例3-5x2 y2w3/2 0 1 1/2 1/2 1 0 1/200 0 0 0 -1 1 -1 000 0 00 T(B3)0 x11/21 0 -1/2 1/2 0 0 1/2 -2 c 2 100得得w*=0，T(B3)中基变量中含有人工变量中基变量中含有人工变量y2,且且y2所在行的所在行的对应的对应的X系数全为系数全为0 ,则划去则划去T(B3)中中y2所在行，此时，基变所在行，此时，基变量中不再含有人工变量，则划去量中不再含有人工变量，则划去T(B3)中人工变量所在列中人工变量所在列,把检验数行用原问题的标准形式的目