线性规划及其扩展-课件

第一章第一章 线性规划及其扩展线性规划及其扩展第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论 线性规划的人工变量法线性规划的人工变量法目前有两种方法：目前有两种方法：大大M M法法和和二阶段法二阶段法。人人工工变变量量法法在在讨讨论论单单纯纯形形法法时时，我我们们总总是是假假定定AXAXb b的的系系数数矩矩阵阵A A的的秩秩r(A)=mn,r(A)=mn,或或者者已已有有一一个个可可行行基基。但但是是，在在许许多多问问题题中中，初初始始可可行行基基是是不不容容易易找找到到的的，或或者者A A不不满满秩秩。这样单纯形法就很难进行。这样单纯形法就很难进行。所以，我们要探讨如何寻找第一个可行基？所以，我们要探讨如何寻找第一个可行基？大大M M法（法（1 1）把原问题化为下列形式：其中把原问题化为下列形式：其中M M是任意大的正数是任意大的正数大大M M法（法（2 2）关于大关于大M M法的几点注释：法的几点注释：(1)在引入人工变量之前，约束条件已是等式，为了这些等式得到满足，因此在最优解中人工变量取值必须为零；为此在目标函数中人工变量的取值为充分小的负数，用“-M”代表；(2)若在单纯形表中有j0，且存在非零人工变量，则原问题无可行解；若基变量中不再含有非零的人工变量，这表示原问题有解；(3)引入的人工变量个数越少越好，只要出现单位矩阵作为基阵即可。大大M M法举例（法举例（1 1）例例解：将原问题化为标准形为：大大M M法举例（法举例（2 2）引入的人工变量个数越少越好引入人工变量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 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 -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）原线性规划问题的最优解为因为在单纯形表T(B4)中，非基变量检验数均小于等于零，且人工变量均为非基变量，取值为零，故原线性规划问题达到最优。线性规划的二阶段法线性规划的二阶段法(1)原线性规划问题为原线性规划问题为第一阶段第一阶段:y y1 1，y y2 2，y ym m称为人工变量称为人工变量构造原构造原(LP)的辅助问题的辅助问题线性规划的二阶段法线性规划的二阶段法(2)原原(LP)的辅助问题的标准形式为：的辅助问题的标准形式为：辅助问题必有最优解辅助问题必有最优解线性规划的二阶段法线性规划的二阶段法(初始单纯形表初始单纯形表1)辅助问题的标准形式的辅助问题的标准形式的系数矩阵为：系数矩阵为：线性规划的二阶段法线性规划的二阶段法(初始单纯形表初始单纯形表2)用单纯形法求解用单纯形法求解,最终得到辅助问题的最优单纯形表最终得到辅助问题的最优单纯形表T(B*)二阶段法的计算步骤二阶段法的计算步骤:第二步第二步 若若 w*0,则原线性规划无可行解则原线性规划无可行解,停止求解停止求解,否则转第三步否则转第三步.第一步第一步 用单纯形法求辅助问题的最优单纯形表用单纯形法求辅助问题的最优单纯形表T(B*)和和最优值最优值w*.第三步第三步 T(B*)中基变量中不含人工变量中基变量中不含人工变量y,则把则把T(B*)中人中人工变量所在列划去工变量所在列划去,把检验数行用原规划的目标函把检验数行用原规划的目标函数的系数替代再把基变量的检验数化为数的系数替代再把基变量的检验数化为0,即得原即得原规划的一个可行基的单纯形表规划的一个可行基的单纯形表.再用单纯形法迭再用单纯形法迭代代,直到终止直到终止.否则转第四步否则转第四步.第四步第四步 w*=0,T(B*)中基变量中含有人工变量中基变量中含有人工变量yr,若若yr所在所在行的对应的行的对应的X系数全为系数全为0,则划去则划去T(B*)中中yr所在行所在行和所在的列和所在的列,转第三步转第三步。否则以某变量。否则以某变量xS的系数的系数brs 0为轴心项进行换基迭代为轴心项进行换基迭代后转第三步后转第三步。线性规划的二阶段法举例（线性规划的二阶段法举例（1）例例1.用二阶段法求解下列用二阶段法求解下列(LP)问题问题 解解:化原问题为标准形式化原问题为标准形式 则第一阶段的辅助问题为则第一阶段的辅助问题为 线性规划的二阶段法举例（线性规划的二阶段法举例（1-2）辅助问题的标准形式为辅助问题的标准形式为 线性规划的二阶段法举例（例线性规划的二阶段法举例（例1-3）则辅助问题的单纯表则辅助问题的单纯表 T(B1)XB b x1 x2 x3 x4 x5 x6 y2 y3x4 y2 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 00-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 用二阶段法解用二阶段法解线性规划线性规划 解解:引进人工变量引进人工变量y20，建立第一阶段的辅助问题为建立第一阶段的辅助问题为 线性规划的二阶段法举例（例线性规划的二阶段法举例（例2-2）辅助问题的标准形式为辅助问题的标准形式为 则第一阶段的初始则第一阶段的初始单纯形表单纯形表 为为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/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则原问题的一个初始单纯形表如下则原问题的一个初始单纯形表如下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 用二阶段法解下用二阶段法解下列线性规划列线性规划 解解:该问题的标准形式为：该问题的标准形式为：线性规划的二阶段法举例（例线性规划的二阶段法举例（例3-2）辅助问题的标准形式为辅助问题的标准形式为 则第一阶段的则第一阶段的单纯形初表为单纯形初表为T（B1）引进引进人工变量人工变量y1,y2,y3，建立第一阶段的辅助问题为：建立第一阶段的辅助问题为：例例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 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)中人工变量所在列中人工变量所在列,把检验数行用原问题的标准形式的目标函数的系数替代再把检验数行用原问题的标准形式的目标函数的系数替代再把基变量的检验数化为把基变量的检验数化为0,即得第二阶段的初始单纯形表即得第二阶段的初始单纯形表.XBb x1 x2 x3 x4 y1 y2 y3例例3-6 XB bx1 x2 x3 x4 x2 x1 3/2 1/20 1 1/2 1/2 1 0 -1/2 1/2 c 0 2 1 0 0 T(B3)T(B4)z00-5/21/2-3/2x3x1320 2 1 11 1 0 1 z-40 -1 0 -2原最优解原最优解X*=(2,0,3,0)T最优值为最优值为z*=-4Yes Yes NO NO Yes NO 二阶段法的框图表示为如下二阶段法的框图表示为如下:开始开始w*=0是否成立？是否成立？构造辅助问题的构造辅助问题的 初始单纯形表初始单纯形表无可行解无可行解 单纯形法单纯形法换基迭代换基迭代得到辅助问题的得到辅助问题的最优单纯形表最优单纯形表 构造辅助问题构造辅助问题L输入标准形式输入标准形式结束结束基变量中含有基变量中含有y？划去基变量所划去基变量所在列可得在列可得 原原问题的单纯形问题的单纯形表表换基迭代换基迭代划去该划去该Y所在的所在的行和所在的列行和所在的列强迫强迫X入基入基基变量基变量Y所在行所在行X 的系数是否全为零的系数是否全为零堂练题堂练题用二阶段法解下列线性规划问题用二阶段法解下列线性规划问题：