线性规划的二阶段法.ppt

感谢大家观看第32页,共32页，星期六，2024年，5月************************************************************关于线性规划的二阶段法线性规划的人工变量法目前有两种方法：大M法和二阶段法。人工变量法在讨论单纯形法时，我们总是假定AX＝b的系数矩阵A的秩r(A)=mn,或者已有一个可行基。但是，在许多问题中，初始可行基是不容易找到的，或者A不满秩。这样单纯形法就很难进行。所以，我们要探讨如何寻找第一个可行基？第2页,共32页，星期六，2024年，5月大M法（1）把原问题化为下列形式：其中M是任意大的正数第3页,共32页，星期六，2024年，5月大M法（2）关于大M法的几点注释：(1)在引入人工变量之前，约束条件已是等式，为了这些等式得到满足，因此在最优解中人工变量取值必须为零；为此在目标函数中人工变量的取值为充分小的负数，用“-M”代表；(2)若在单纯形表中有λj≤0，且存在非零人工变量，则原问题无可行解；若基变量中不再含有非零的人工变量，这表示原问题有解；(3)引入的人工变量个数越少越好，只要出现单位矩阵作为基阵即可。第4页,共32页，星期六，2024年，5月大M法举例（1）例解：将原问题化为标准形为：第5页,共32页，星期六，2024年，5月大M法举例（2）引入的人工变量个数越少越好引入人工变量y2,y3≥0,由大M法得辅助问题为：其中大M为任意大的正数得上述辅助问题的单纯形初表为：第6页,共32页，星期六，2024年，5月大M法举例（3）T(B1)XBbx1x2x3x4x5y2y3x4y2y3419-z’10M1111000-21-10-1100310001-2M-34M10-M00T(B2)x4x2y3-z’330211-101-21-10-110660403-316M6M-304M+103M-4M0人工变量优先出基第7页,共32页，星期六，2024年，5月大M法举例（4）T(B3)XBbx1x2x3x4x5y2y3x4x2x1031-z’30001-1/21/2-1/2011/30001/3102/301/2-1/21/600303/2-M-3/2-M+1/2T(B4)x4x2x3-z’00001-1/21/2-1/25/2-1/2100-1/41/41/43/23/20103/4-3/41/4-3/2-9/2000-3/4-M+3/4-M-1/4第8页,共32页，星期六，2024年，5月大M法举例（5）原线性规划问题的最优解为因为在单纯形表T(B4)中，非基