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

1、第一章 线性规划及其扩展,第5节 单纯形法的进一步讨论,线性规划的人工变量法,目前有两种方法：大M法和二阶段法。,人工变量法,在讨论单纯形法时，我们总是假定AXb的系数矩阵A的秩r(A)=mn,或者已有一个可行基。但是，在许多问题中，初始可行基是不容易找到的，或者A不满秩。这样单纯形法就很难进行。,所以，我们要探讨如何寻找第一个可行基？,大M法（1）,把原问题化为下列形式：其中M是任意大的正数,大M法（2）,关于大M法的几点注释：,(1)在引入人工变量之前，约束条件已是等式，为了这些等式得到满足，因此在最优解中人工变量取值必须为零；为此在目标函数中人工变量的取值为充分小的负数，用“-M”代表；

2、,(2)若在单纯形表中有j0，且存在非零人工变量，则原问题无可行解；若基变量中不再含有非零的人工变量，这表示原问题有解；,(3)引入的人工变量个数越少越好，只要出现单位矩阵作为基阵即可。,大M法举例（1）,例,解：将原问题化为标准形为：,大M法举例（2）,引入的人工变量个数越少越好,引入人工变量y2,y30,由大M法得辅助问题为：,其中大M为任意大的正数,得上述辅助问题的单纯形初表为：,大M法举例（3）,T(B1),XB,b,x1 x2 x3 x4 x5 y2 y3,x4 y2 y3,41 9,-z,10M,1 1 1 1 0 0 0 -2 1 -1 0 -1 1 0 0 3 1 0 0 0

3、1,-2M-3 4M 1 0 -M 0 0,T(B2),x4,x2,y3,-z,3,3 0 2 1 1 -1 0,1,-2 1 -1 0 -1 1 0,6,6 0 4 0 3 -3 1,6M,6M-3,0,4M+1,0,3M,-4M,0,人工变量优先出基,大M法举例（4）,T(B3),XB,b,x1 x2 x3 x4 x5 y2 y3,x4 x2 x1,03 1,-z,3,0 0 0 1 -1/2 1/2 -1/2 0 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6,0 0 3 0 3/2 -M-3/2 -M+1/2,T(B4),x4,x2,x3,-z,0,0 0

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

5、始单纯形表1),辅助问题的标准形式的系数矩阵为：,线性规划的二阶段法(初始单纯形表2),用单纯形法求解,最终得到辅助问题的最优单纯形表T(B*),二阶段法的计算步骤:,第二步 若 w*0,则原线性规划无可行解,停止求解, 否则转第三步.,第一步 用单纯形法求辅助问题的最优单纯形表T(B*) 和最优值w*.,第三步 T(B*)中基变量中不含人工变量y,则把T(B*)中人 工变量所在列划去,把检验数行用原规划的目标函 数的系数替代再把基变量的检验数化为0,即得原 规划的一个可行基的单纯形表.再用单纯形法迭 代,直到终止.否则转第四步.,第四步 w*=0,T(B*)中基变量中含有人工变量yr,若yr

6、所在 行的对应的X系数全为0 ,则划去T(B*)中yr所在行 和所在的列,转第三步。否则以某变量xS的系数 brs0为轴心项进行换基迭代后转第三步。,线性规划的二阶段法举例（1）,例1. 用二阶段法求解下列(LP)问题,解:,化原问题为标准形式,则第一阶段的辅助问题为,线性规划的二阶段法举例（1-2）,辅助问题的标准形式为,线性规划的二阶段法举例（例1-3）,则辅助问题的单纯表,T(B1),XB,b,x1 x2 x3 x4 x5 x6 y2 y3,x4 y2 y3,64 3,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

7、-2 0 -1 -1 0 0,T(B2),x4,x1,y3,w,2,0 1 2 1 1 0 -1 0,4,1 0 -1 0 -1 0 1 0,3,0 1 -1 0 0 -1 0 1,3,0,1,-1,0,0,-1,-1,0,二阶段法举例（例1-4）,T(B2),x4,XB,b,x1 x2 x3 x4 x5 x6 y2 y3,x1,y3,w,2,0 1 2 1 1 0 -1 0,4,1 0 -1 0 -1 0 1 0,3,0 1 -1 0 0 -1 0 1,3,0,1,-1,0,0,-1,-1,0,x2,T(B3),x1,y3,w,2,0 1 2 1 1 0 -1 0,4,1 0 -1 0 -1

8、 0 1 0,1,0 0 -3 -1 -1 -1 1 1,1,0,0,-3,-1,-1,-1,0,0,因为辅助问题的最优值W*=10，则原问题无可行解。,线性规划的二阶段法 例2-1,例2 用二阶段法解 线性规划,解:,引进人工变量y20，建立第一阶段的辅助问题为,线性规划的二阶段法举例（例2-2）,辅助问题的标准形式为,则第一阶段的初始单纯形表 为T（B1）,例2-3,T(B1),x2,x1,w,1,0 1 1/4 -2/3 -1/3,2,1 0 1/2 0 2/3,0,0,0,0,0,T(B2),-1,例2-4,得w*=0，且基变量中不含有人工变量，则划去T(B2)中y2所在列,把检验数行

9、用原问题的目标函数的系数替代再把基变量的检验数化为0,即得第二阶段的初始单纯形表.,T(B2),c,-4,-3,0,0,-z,11,0 0 11/4 -2,例2-5,则原问题的一个初始单纯形表如下,x2,x1,1,2,0 1 1/4 -2/3,1 0 1/2 0,-z,0 0 11/4 -2,x2,x3,-z,11,0,-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 用二阶段法解下 列线性规划,解: 该问题的标准形式为：,线性规划的二阶段法举例（例3-2）,辅助问题的标准形式为,则第一

10、阶段的单纯形初表为T（B1）,引进人工变量y1,y2,y3，建立第一阶段的辅助问题为：,例3-3,T(B1),y1,y2,w,3/2,0 1 1/2 1/2 1 0 1/2,3/2,0 1 1/2 1/2 0 1 -1/2,3,0,2,1,1,0,T(B2),0,x1,1/2,1 0 -1/2 1/2 0 0 1/2,-1,例3-4,T(B2),x2,y2,w,3/2,0 1 1/2 1/2 1 0 1/2,0,0 0 0 0 -1 1 -1,0,0,0,0,0,0,T(B3),0,x1,1/2,1 0 -1/2 1/2 0 0 1/2,-2,例3-5,x2,y2,w,3/2,0 1 1/2

11、1/2 1 0 1/2,0,0 0 0 0 -1 1 -1,0,0,0,0,0,0,T(B3),0,x1,1/2,1 0 -1/2 1/2 0 0 1/2,-2,c,2,1,0,0,得w*=0，T(B3)中基变量中含有人工变量y2,且y2所在行的对应的X系数全为0 ,则划去T(B3)中y2所在行，此时，基变量中不再含有人工变量，则划去T(B3)中人工变量所在列,把检验数行用原问题的标准形式的目标函数的系数替代再把基变量的检验数化为0,即得第二阶段的初始单纯形表.,XB,b,x1 x2 x3 x4 y1 y2 y3,例3-6,T(B3),T(B4),z,0,0,-5/2,1/2,-3/2,x3 x1,3 2,0 2 1 1 1 1 0 1,z,-4,0 -1 0 -2,原最优解X* =(2,0,3,0)T,最优值为 z*=-4,Yes,Yes,NO,NO,Yes,NO,二阶段法