第三讲线性规划的人工变量法(Max型)

第一章线性规划及其扩展第5节单纯形法的进一步讨论

线性规划的人工变量法目前有两种方法：大M法和两阶段法。人工变量法在讨论单纯形法时，我们总是假定AX＝b的系数矩阵A的秩r(A)=m<n,或者已有一个可行基。但是，在许多问题中，初始可行基是不容易找到的，或者A不满秩。这样单纯形法就很难进行。所以，我们要探讨如何寻找第一个可行基？大M法（1）把原问题化为下列形式：其中M是任意大的正数大M法（2）关于大M法的几点注释：(1)在引入人工变量之前，约束条件已是等式，为了这些等式得到满足，因此在最优解中人工变量取值必须为零；为此在目标函数中人工变量的取值为充分小的负数，用“-M”代表；(2)若在单纯形表中有λj≤0，且存在非零人工变量，则原问题无可行解；若基变量中不再含有非零的人工变量，这表示原问题有解；(3)引入的人工变量个数越少越好，只要出现单位矩阵作为基阵即可。大M法举例（1）例解：将原问题化为标准形为：大M法举例（2）引入的人工变量个数越少越好引入人工变量y2,y3≥0,由大M法得辅助问题为：其中M为任意大的正数得上述辅助问题的单纯形初表为：大M法举例（3）

T(B1)XBb

x1x2x3x4x5y2y3x4y2y3419-z’10M1111000-21-10-1100310001-2M-34M10-M00

T(B2)x4

x2

y3

-z’330211-101-21-10-110660403-31

6M6M-304M+1

03M-4M0人工变量优先出基大M法举例（4）

T(B3)XBb

x1x2x3x4x5y2y3x4x2x1031-z’30001-1/21/2-1/2011/30001/3102/301/2-1/21/600303/2-M-3/2-M+1/2

T(B4)x4

x2

x3

-z’00001-1/21/2-1/25/2-1/2100-1/41/41/43/23/20103/4-3/41/4

-3/2-9/200

0-3/4-M+3/4-M-1/4大M法举例（5）原线性规划问题的最优解为因为在单纯形表T(B4)中，非基变量检验数均小于等于零，且人工变量均为非基变量，取值为零，故原线性规划问题达到最优。线性规划的两阶段法(1)原线性规划问题为第一阶段:y1，y2，…，ym称为人工变量构造原(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的系数brs0为轴心项进行换基迭代后转第三步。

线性规划的两阶段法举例（1）例1.用两阶段法求解下列(LP)问题

解:化原问题为标准形式则第一阶段的辅助问题为线性规划的两阶段法举例（1-2）

辅助问题的标准形式为则第一阶段的初始单纯形表

为T（B1）线性规划的两阶段法举例（例1-3）

T(B1)XBb

x1x2x3x4x5x6y2y3x4y2y3643w71111000010-10-101001-100-10111-20-1-100

T(B2)x4

x1

y3

w2012110-10410-10-1010301-100-101301-100-1-10两阶段法举例（例1-4）

T(B2)x4

XBb

x1x2x3x4x5x6y2y3x1

y3

w2012110-10410-10-1010301-100-101301-100-1-10x2

T(B3)x1y3w2012110-10410-10-1010100-3-1-1-111

100-3-1-1-100

因为辅助问题的最优值w*=1＞0，则原问题无可行解。线性规划的两阶段法例2-1例2用两阶段法解线性规划

解:引进人工变量y2≥0，建立第一阶段的辅助问题为

线性规划的两阶段法举例（例2-2）

辅助问题的标准形式为

则第一阶段的初始单纯形表

为T（B1）

XB

b

x1x2x3x4y2

x2y2

231/211/2-2/303/203/401

w

33/203/400例2-3

T(B1)x2x1w1011/4-2/3-1/32101/202/300000

T(B2)-1例2-4得w*=0，且基变量中不含有人工变量，则划去T(B2)中y2所在列,把检验数行用原问题的目标函数的系数替代再把基变量的检验数化为0,即得第二阶段的初始单纯形表.

T(B2)c-4-300

XB

b

x1x2x3x4y2

x2x1

12011/4-2/3-1/3101/202/3

w

00

000-1-z110011/4-2例2-5则原问题的一个初始单纯形表如下x2

x1

12011/4-2/3101/20-z0011/4-2XBbx1x2x3x4

x2

x3

-z110-1/210-2/3420100-11/200-2原问题最优解X*=(0,0,4,0)T原问题最优值为z*=0例3-1例3用两阶段法解下列线性规划

解:该问题的标准形式为：线性规划的两阶段法举例（例3-2）

辅助问题的标准形式为则第一阶段的单纯形初表为T（B1）引进人工变量y1,y2,y3，建立第一阶段的辅助问题为：例3-3

XB

bx1x2x3x4y1y2y3

y1y2y3

121-1110100110101020-11001

w

4

2

202000

T(B1)y1y2w3/2011/21/2101/23/2011/21/201-1/2302110

T(B2)0x11/210-1/21/2001/2-1例3-4

XB

bx1x2x3x4y1y2y3

y1y2x1

3/23/21/2011/21/2101/2011/21/201-1/210-1/21/2001/2

w

3

021100-1

T(B2)x2y2w3/2011/21/2101/200000-11-1000000

T(B3)0x11/210-1/21/2001/2-2例3-5x2y2w3/2011/21/2101/200000-11-1000000

T(B3)0x11/210-1/21/2001/2-2c2100得w*=0，T(B3)中基变量中含有人工变量y2,且y2所在行的对应的X系数全为0,则划去T(B3)中y2所在行，此时，基变量中不再含有人工变量，则划去T(B3)中人工变量所在列,把检验数行用原问题的标准形式的目标函数的系数替代再把