两阶段法的优缺点
发布网友
发布时间：2023-02-06 13:28
共1个回答
热心网友
时间：2024-12-05 02:39
寻找线性规划问题初始基可行解的方法
两阶段法(two-phase method)是寻找线性规划问题初始基可行解的一种方法，把增加人工变量的线性规划问题分为两个阶段去求解。
第一阶段主要是为了得到原问题的一个基本可行解，第二阶段是在第一阶段得到的基本可行解的基础上求解原线性规划问题。[1]
中文名
两阶段法
外文名
two-stagemethod
适用领域
有人工变量的线性规划
应用学科
运筹学
发展简史定律定义方法应用应用领域TA说参考资料
发展简史
大M法与两阶段法都是在原问题缺少初始可行基的情况下利用引人人工变量构造人工基，以达到运用单纯形法求解原问题的目的。用大M法处理人工变量，手工计算求解时不会碰到麻烦。但用电子计算机求解时，对M就只能在计算机内输出一个机器最大字长的数字。如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数比较接近，或远远小于这个数字，由计算机计算时有可能使计算结果发生错误，从而使求解的最终结果与原问题真正的最优解不一致。为了克服这个困难，可以对添加人工变量后的线性规划问题分为两个阶段来计算，而避免M的使用，这个方法称为两阶段法。
定律定义
两阶段法的方法步骤具体阐述如下，线性规划LP问题的标准化后的矩阵形式为：
在约束条件中加入人工变量y=(y1,y2,···,ym)T变为
，人工变量设为xs也可。
第一阶段
第一阶段的就是求解这个目标函数是只包含人工变量的辅助问题。首先构造一个辅助的人工目标函数：令目标函数中其他变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束不变的条件下求这个目标函数极小化的解：
也即
因为人工变量是虚拟的，在最优时它不应该有取值。如果原问题有可行解，那么人工变量必定取零yi=0(i=1, 2, ···,m)，那么辅助问题的最优值一定为z=0。设最优解目标函数值为z，第一阶段求解的结果有三种可能的情况：
(1)如果第一阶段求解结果为z≠0，说明最优解的基变量中含有非零的人工变量，从而表明原问题无可行解，不必进行第二阶段，计算终止。
(2)如果第一阶段求解结果z=0，如果辅助问题的最优基变量中没有人工变量，进入第二阶段。
(3)如果第一阶段求解结果z=0，如果辅助问题的最优基变量中仍有为0的人工变量，这表明原问题有退化的情况，在辅助问题的最优的单纯形表中有：
其中
为非基变量下标集，这时又分两种情况：
(i)若arj全为0，则人工变量所在行中有原变量（现在是非基变量）下的元素都是0，这表明原问题的约束方程中有多余的，将其去掉，转入第二阶段。
(ii)若arj不全为0，则以ars为主元，进行换基迭代，最后转入转入第二阶段。
第二阶段
当第一阶段求解结果表明问题有可行解时，第二阶段是在原问题中去除人工变量，并由第一阶段得到的最优解出发，继续寻找原问题的最优解。[2]即在第一阶段的最优单纯形表中去掉人工变量所在的行列，将价值系数改换成原问题的价值系数，进一步迭代，求解原问题的最优解或者无穷多最优解。
方法应用
鉴于两阶段法求解相对抽象复杂，这里我们用一个实例演示其求解过程。为了方便读者进行两阶段法和大M法对比，这里我们采用和大M法相同的算例进行演示。
先将其转化为标准形式，即
这里我们加入了两个松弛变量
和
,但是此时仍然没有一个m*m的线性无关矩阵作为初始基底（此时m=3），于是我们看到
代表的列可以作为基底
，于是我们再加入两个变量
和
，从而能够构成一个基阵。这两个变量
和
即为人工变量。
变换后的形式如下：
接下来我们要进行第一阶段。
第一阶段
构造辅助函数
列表求解
Cj
0
0
0
0
0
1
1
CB
xB
b
P1
P2
P3
P4
P5
P6
P7
0
x4
4
1
1
1
1
0
0
0
4
1
x6
1
-2
[1]
-1
0
-1
1
0
1
2入基，6出基。
Cj
0
0
0
0
0
1
1
CB
xB
b
P1
P2
P3
P4
P5
P6
P7
0
x4
3
3
0
2
1
1
-1
0
1
0
x2
1
-2
1
-1
0
-1
1
0
-
1入基，7出基 (此时其实4出基也可以，但是我们为了尽快把人工变量出基，这里选择7出基)
Cj
0
0
0
0
0
1
1
CB
xB
b
P1
P2
P3
P4
P5
P6
P7
0
x4
0
0
0
0
1
-1/2
-1/2
-1/2
0
x2
3
0
1
1/3
0
0
0
1/3
-
人工变量全被出基，Z=0，表示优化问题有解，进入第二阶段。
第二阶段
在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算初始表，用单纯形法继续计算。
Cj
-3
0
1
0
0
CB
xB
b
P1
P2
P3
P4
P5
0
x4
0
0
0
0
1
-1/2
-
0
x2
3
0
1
1/3
0
0
-
3入基，1出基
Cj
-3
0
1
0
0
CB
xB
b
P1
P2
P3
P4
P5
0
x4
0
0
0
0
1
-1/2
0
x2
5/2
-1/2
1
0
0
1/4
此时检验数已经没有正数，此时
,
,
,
,
,
z=3/2。得解。
读者可以对上述的单纯形表和大M法对比，可以发现，大部分的取值是相同的。
应用领域
在大规模线性规划问题的求解中，通常采用两阶段法运算。[3]
