线性规划的二阶段法

关于线性规划的二阶段法

线性规划的人工变量法目前有两种方法：大M法和二阶段法。人工变量法在讨论单纯形法时，我们总是假定AX＝b的系数矩阵A的秩r(A)=m<n,或者已有一个可行基。但是，在许多问题中，初始可行基是不容易找到的，或者A不满秩。这样单纯形法就很难进行。所以，我们要探讨如何寻找第一个可行基？第2页,共32页，2024年2月25日，星期天大M法（1）把原问题化为下列形式：其中M是任意大的正数第3页,共32页，2024年2月25日，星期天大M法（2）关于大M法的几点注释：(1)在引入人工变量之前，约束条件已是等式，为了这些等式得到满足，因此在最优解中人工变量取值必须为零；为此在目标函数中人工变量的取值为充分小的负数，用“-M”代表；(2)若在单纯形表中有λj≤0，且存在非零人工变量，则原问题无可行解；若基变量中不再含有非零的人工变量，这表示原问题有解；(3)引入的人工变量个数越少越好，只要出现单位矩阵作为基阵即可。第4页,共32页，2024年2月25日，星期天大M法举例（1）例解：将原问题化为标准形为：第5页,共32页，2024年2月25日，星期天大M法举例（2）引入的人工变量个数越少越好引入人工变量y2,y3≥0,由大M法得辅助问题为：其中大M为任意大的正数得上述辅助问题的单纯形初表为：第6页,共32页，2024年2月25日，星期天大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人工变量优先出基第7页,共32页，2024年2月25日，星期天大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第8页,共32页，2024年2月25日，星期天大M法举例（5）原线性规划问题的最优解为因为在单纯形表T(B4)中，非基变量检验数均小于等于零，且人工变量均为非基变量，取值为零，故原线性规划问题达到最优。第9页,共32页，2024年2月25日，星期天线性规划的二阶段法(1)原线性规划问题为第一阶段:y1，y2，…，ym称为人工变量构造原(LP)的辅助问题第10页,共32页，2024年2月25日，星期天线性规划的二阶段法(2)原(LP)的辅助问题的标准形式为：辅助问题必有最优解第11页,共32页，2024年2月25日，星期天线性规划的二阶段法(初始单纯形表1)辅助问题的标准形式的系数矩阵为：第12页,共32页，2024年2月25日，星期天线性规划的二阶段法(初始单纯形表2)用单纯形法求解,最终得到辅助问题的最优单纯形表T(B*)第13页,共32页，2024年2月25日，星期天二阶段法的计算步骤:第二步若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为轴心项进行换基迭代后转第三步。

第14页,共32页，2024年2月25日，星期天线性规划的二阶段法举例（1）例1.用二阶段法求解下列(LP)问题

解:化原问题为标准形式则第一阶段的辅助问题为第15页,共32页，2024年2月25日，星期天线性规划的二阶段法举例（1-2）

辅助问题的标准形式为第16页,共32页，2024年2月25日，星期天线性规划的二阶段法举例（例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第17页,共32页，2024年2月25日，星期天二阶段法举例（例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，则原问题无可行解。第18页,共32页，2024年2月25日，星期天线性规划的二阶段法例2-1例2用二阶段法解线性规划

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

第19页,共32页，2024年2月25日，星期天线性规划的二阶段法举例（例2-2）

辅助问题的标准形式为

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

为T（B1）第20页,共32页，2024年2月25日，星期天

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第21页,共32页，2024年2月25日，星期天例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第22页,共32页，2024年2月25日，星期天例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第23页,共32页，2024年2月25日，星期天例3-1例3用二阶段法解下列线性规划

解:该问题的标准形式为：第24页,共32页，2024年2月25日，星期天线性规划的二阶段法举例（例3-2）

辅助问题的标准形式为则第一阶段的单纯形初表为T（B1）引进人工变量y1,y2,y3，建立第一阶段的辅助问题为：第25页,共32页，2024年2月25日，星期天例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第26页,共32页，2024年2月25日，星期天例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第27页,共32页，2024年2月25日，星期天例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)中人工变量所在列,把检验数行用原问题的标准形式的目标函数的系数替代再把基变量的检验数化为0,即得第二阶段的初始单纯形表.XBbx1x2x3x4y