单纯形法(4)

第四章 人工变量及其处理方法

在用单纯形表解决线性规划问题时，为了使初始可行基成为一个单位矩阵，在有约束条件中需要加入人工变量，但加入人工变量后的数学模型与原模型一般不等价。因此我们需要引入新的方法解决这一问题。 考虑线性规划：

maxZ??cjxj

j?1nn???xjpj?b s.t? （4-1） j?1??xj?0,j?1,2,...,n式中b?0，pj?(a1j,a2j,...,amj)T.则在每一个约束方程左边加上一个人工变量

xn?i(i?1,2,...,m)，可得到：

?a11x1?a12x2???a1nxn?xn?1?b1?ax?ax???ax?x2112222nnn?2?b2? ? （4-2） ????????????????ax?ax???ax?xm22mnnn?m?bm?m11?x1,x2,...,xn,xn?1,...,xn?m?0?(4-2)式含有一个m阶单位矩阵，以xn?1,...,xn?m为基变量，得到一个初始基本可行解：x(0)?(0,...,0,b1,...,bm)T可以从x(0)出发进行迭代。

但是以（4-2）式为约束方程的线性规划模型与原规划问题一般不是等价的 。

只有当最优解中，人工变量都取零值时，才可以认为两个问题的最优解是相当的。 关于这一点有以下结论：

（1） 以（4-2）式为约束方程组的线性规划问题的最优解中人工变量都处在非基

变量位置（即取零值），原问题（4-1）式有最优解，且将前者最优解中去掉人工变量部分即为后者最优解。 （2） 若问题（4-2）式的最优解中包含非零的人工变量，则原问题（4-1）无可行

解。 （3） 若问题（4-2）式的最优解的基变量中包含人工变量，但该人工变量取值为

零，这时刻将某个非基变量引入基变量中来替换该人工变量，从而得到原问题的最优解 对于以上结论这里不作更多的理论上的证明。如何将基变量中的人工变量赶出去，下面我们主要介绍两种方法：大M法和两阶段法。

16

4.1大Ｍ法

将当以（4-2）式作为约束方程组时，若将目标函数修改为

maxZ??cjxj?Mxn?1?Mxn?2?Mxn?m （4-3）

j?1n其中M是个很大的正数，因为是对目标规划实现最大化。因此人工变量必须从基变量中迅速出去，否则目标函数不可能实现最大化。 例 考虑线性规划问题：

maxZ?3x1?x2?x3；

?x1?2x2?x3?11??4x?x?2x?3?123 s.t? (4-4)

??2x1?x3?1??x1,x2,x3?0.用大M法求解步骤如下：

解：添加人工变量将上述问题转化为：

maxZ?3x1?x2?x3?0?x4?0?x5?Mx6?Mx7；

x1?2x2?x3?x?11???4x?x?2x?x?x?3?12356 s.t??2x1?x3?x7?1??xj?0,j?1,2,...,7.?式中M是一个很大的正数,令B(0)?(p4,p6,p7)作初试可行基，作单纯形表如下 cj 3 -1 -1 0 0 -M -M cB 0 -M -M xB x4 x6 x7 b 11 3 1 4M x1 1 -4 -2 x2 -2 1 0 x3 1 2 [1] x4 1 0 0 0 x5 0 -1 0 -M x6 0 1 0 0 x7 0 0 1 0 ? 11 3/2 1 ?z 3-6M M-1 3M-1 17

0 -M -1 0 -1 -1 3 -1 -1 x4 x6 x3 10 1 1 1+M 12 1 1 2 4 1 1 -2 3 0 -2 1 [3] 0 -2 1 1 0 0 0 -2 [1] 0 M-1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 -1 0 -M -2 -1 0 -1 0 1 0 0 2 1 0 1-M 2/3 1 4/3 -1 -2 1 1-3M -5 -2 1 -M-1 -5/3 -2 -7/3 \\ 1 \\ 4 \\ \\ ?z x4 x2 x3 ?z x1 x2 x3 1/3 -2/3 0 -1 2/3 -4/3 ?z -1/3 -1/3 1/3-M -2/3-M 从上表中可以看出人工变量全部出基，且检验数全部小于0，故

x*?(4,1,9,0,0,0,0)T是原问题的最优解，最优值为z*?2

显然，若对于最小化问题，若用大M法，则对最小化目标函数中应加上惩罚项，才能在最小化过程中迫使人工变量xa从基变量中换Mxa（xa为一个人工变量）出去，则有如下一般形式：

maxZ??cjxj?Mxn?1?Mxn?2?Mxn?m

j?1n式中xn?i(i

?1,2,...,m)均为人工变量。

下面我们来介绍处理人工变量的另一种方法：两阶段法

18

4.2两阶段法

当线性规划问题（4-1）式添加人工变量后，得到以（4-2)式为约束方程的线性规划，然后将问题拆成两个线性规划。第一阶段求解第一个线性规划：

minw??xn?i；

i?1m?a11x1?a12x2???a1nxn?xn?1?b1?ax?ax???ax?x2112222nnn?2?b2? s.t??????????????? (4-5)

??ax?ax???ax?xm11m22mnnn?m?bm??x1,x2,...,xn,xn?1,...,xn?m?0?第一个线性规划的目标函数是对所有人工变量之和求最小值。

（1） 若求得的最优解中，所有人工变量都处在费基变量的位置，即

xn?i?0(i?1,2,...m,)及w*?0，则从第一阶段的最优解中去掉人工

变量之后，即为原问题的一个基本可行解。作为原问题的一个初始基本可

行解，再求解原问题，从而进入第二阶段。

（2） 假若求得第一阶段的最优解中，至少有一个人工变量不为零值，则说明添

加人工变量之前的原问题无可行解，不再需要进入第二阶段计算。 因此两阶段法的第一阶段求解，有两个目的：一，判断原问题有无可行解；二，若有可行解，泽尔可求得原问题的一个初始基本可行解，再对原问题进行第二阶段的计算。

下面用两阶段法求解(4-4).建立第一阶段的线性规划问题：

minw?x6?x7；

?x1?2x2?x3?x4?11??4x?x?2x?x?x?3?12356 s.t??2x1?x3?x7?1??xj?0,j?1,2,...,7?式中有B

19

(0)?(p4,p6,p7)?I3，可作为初始基本可行解。建立初始单纯

形表如下所示，并由此开始进行出基入基运算：

0 0 0 0 0 1 1 cj xB x4 x6 x7 cB 0 1 1 0 1 0 0 1 0 b 11 3 1 -4 10 1 1 -1 12 1 1 0 x1 1 -4 -2 6 3 0 -2 0 3 0 -2 0 x2 -2 1 0 -1 -2 [1] 0 -1 0 1 0 0 x3 1 2 [1] -3 0 0 1 0 0 0 1 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 x5 0 -1 0 1 0 -1 0 1 -2 -1 0 0 x6 0 1 0 0 0 1 0 0 2 1 0 1 x7 0 0 1 0 -1 -2 1 3 -5 -2 1 1 ? 11 3/2 1 \\ 1 \\ ?z x4 x6 x3 ?z x4 x2 x3 ?z 通过二次基迭代之后，?j此第一阶段的最优解已得到：x?0，且人工变量x6,x7已从基变量中换出。因

(0)?(0,1,1,12,0,0,0)T为最优解。将最优表中

(0)关于人工变量列划去，即可作为第二阶段的单纯形表。x第二阶段的初始基本可行解。

建立第二阶段的数学模型：

maxz?(0,1,1,12,0)T为

?3x1?x2?x3?0?x4?0?x5；

20

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库单纯形法(4)在线全文阅读。