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

第三讲_线性规划的二阶段法第一章 线性规划及其扩展
第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)
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 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 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)的辅助问题
整理课件