第1章 线性规划与单纯形法-第5节-2007-8

优化类课程课件

第5节 单纯形法的进一步讨论 节 5.1 人工变量法 5.2 退化 5.3 检验数的几种表示形式

优化类课程课件

5.1 人工变量法 设线性规划问题的约束条件为

∑P xj j =1

n

j

=b

其中没有可作为初始基的单位矩阵，则分别给每一个 其中没有可作为初始基的单位矩阵， 约束方程加入人工变量x 约束方程加入人工变量xn+1,…,xn+m,得到

=b a11 x1 + a12 x2 + L + a1n xn + xn +1 a x + a x +L+ a x + xn + 2 =b 22 2 2n n 21 1 L a x + a x + L + a x + xn + m = b m1 1 m2 2 mn n x1 , L , xn ≥ 0; xm +1 , L , xn + m ≥ 0

优化类课程课件

1)以 为基变量，并可得到一个m 1)以xn+1,…,xn+m为基变量，并可得到一个 ×m 为零， 单位矩阵。令非基变量x 单位矩阵。令非基变量 1,…,xn为零，便可得到一 个初始基可行解X 个初始基可行解 (0)=(0,0,…,0,b1,b2,…,bm)T 2) 把人工变量经基变换从基变量中逐个替换出来， 把人工变量经基变换从基变量中逐个替换出来， 直到基变量中不含有非零人工变量， 直到基变量中不含有非零人工变量，则原问题有解 3) 若在最终表中当所有 cj-zj≤0 , 而在其中还有某 若在最终表中当所有c 个非零人工变量，这表示原问题无可行解。 个非零人工变量，这表示原问题无可行解。 原问题无可行解 如何解含有人工变量的线性规划问题? 如何解含有人工变量的线性规划问题?

优化类课程课件

1大M法 假定人工变量在目标函 数中的系数为(-M)(M为任 数中的系数为 为任 意大的正数), 意大的正数 ， 因此，要实现最大化时， 因此，要实现最大化时， 必须把人工变量从基变量 换出。 换出。否则目标函数不可 能实现最大化。 能实现最大化。

优化类课程课件

例8 现有线性规划问题，试用 大M法求解。

min z = 3 x1 + x2 + x3 x1 2 x2 + x3 ≤ 11 4x + x + 2x ≥ 3 1 2 3 2 x1 + x3 = 1 x1 , x2 , x3 ≥ 0

优化类课程课件

解 在上述问题的约束条件中加入松弛变 量x4,剩余变量x5,人工变量x6,x7,得到min z = 3x1 + x2 + x3 + 0 x4 + 0 x5 + Mx6 + Mx7 = 11 x1 2 x2 + x3 + x4 4x + x + 2x x5 + x 6 = 3 1 2 3 + x3 + x7 = 1 2 x1 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0 这里M是一个任意大的正数 这里 是一个任意大的正数。

优化类课程课件

因本例的目标函数是要求 min,所以用所有 j-zj≥0来判 ，所以用所有c 来判 别目标函数是否实现了最小化. 别目标函数是否实现了最小化. 用单纯形法进行计算时， 用单纯形法进行计算时，见表 1-6。 。cj→ CB 0 M M cj-zj XB x4 x6 x7 b 11 3 1 -3 x1 1 -4 -2 -3+6M 1 x2 -2 1 0 1-M 1 x3 1 2 [1] 1-3M 0 x4 1 0 0 0

基变量

0 x5 0 -1 0 M

M x6 0 1 0 0

M x7 0 0 1 0

θi 11 3/2 1

表1-6

优化类课程课件

在表1-6的最终计算结果表中，表明已得到最优解是： 最终计算结果表中，表明已

得到最优解是： =9, =0;目标函数z= z=x1=4,x2=1,x3=9,x4=x5=x6=x7=0;目标函数z=-2cj→ CB 0 M 1 cj-zj 0 1 1 cj-zj -3 1 1 cj-zj x1 x2 x3 4 1 9 2 x4 x2 x3 12 1 1 XB x4 x6 x3 b 10 1 1 -3 x1 3 0 -2 -1 [3] 0 -2 -1 1 0 0 0 1 x2 -2 [1] 0 1-M 0 1 0 0 0 1 0 0 1 x3 0 0 1 0 0 0 1 0 0 0 1 0 0 x4 1 0 0 0 1 0 0 0 1/3 0 2/3 1/3 0 x5 0 -1 0 M -2 -1 0 1 -2/3 -1 -4/3 1/3 M x6 0 1 0 0 2 1 0 M-1 2/3 1 4/3 M-1/3 M x7 -1 -2 1 3M-1 -5 -2 1 M+1 -5/3 -2 -7/3 M-2/3 θi

1

4

优化类课程课件

2. 2.两阶段法第一阶段： 第一阶段： 不考虑原问题是否存在基可行解； 不考虑原问题是否存在基可行解；给原线性规划 问题加入人工变量 人工变量， 构造仅含人工变量的目标函数 仅含人工变量 问题加入人工变量，并构造仅含人工变量的目标函数 和要求实现最小化 最小化。 和要求实现最小化。如目标函数 min ω = xn +1 + L + xn + m + 0 x1 + 0 x2 + L + 0 xn = b1 a11 x1 + a12 x2 + LL + a1n xn + xn +1 + xn + 2 = b2 a21 x1 + a22 x2 + LL + a2 n xn 约束条件 L L L L L L L + xn + m = bm am1 x1 + am 2 x2 + LL + am xn x1 , x2 , LL , xn , xn +1 , L , xn + m ≥ 0

优化类课程课件

第一阶段求解用单纯形法求解上 述模型 ， 若得到 ω=0 , 这说明原问题存在基 可行解 ， 可以进行第 二段计算。 二段计算。 否则原问题无可行 应停止计算。 解，应停止计算。

优化类课程课件

第二阶段： 将第一阶段计算得 到的最终表， 到的最终表，除去 人工变量。 人工变量。将目标 函数行的系数， 函数行的系数，换 原问题的目标函数 系数，作为第二阶 系数， 段计算的初始表。 段计算的初始表。 各阶段的计算方法 及步骤与第3节单纯 及步骤与第 节单纯 形法相同。 形法相同。

例9 试用两阶段法 求解线性规划问题

目标函数 min z = 3x1 + x2 + x3 x1 + 2x2 + x3 ≤ 11 4x1 + x2 + 2x3 ≥ 3 约束条件 + x3 = 1 2x1 x1, x2 , x3 ≥ 0

优化类课程课件

解 先在上述线性规划 问题的约束方程中加 入人工变量， 入人工变量，给出第 一阶段的数学模型为： 一阶段的数学模型为：目标函数 min ω = x6 + x7 = 11 x1 + 2 x2 + x3 + x4 x5 + x6 = 3 4 x1 + x2 + 2 x3 约束条件 + x3 + x7 = 1 2 x1 x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0

优化类课程课件

第一阶段用单纯形法求解，见表1-7。 第一阶段用单纯形法求解，见表1 求得的结果是ω=0 ω=0, 求得的结果是ω=0,得到最优解是 x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0 因人工变量x 因人工变量 6=x7=0,所以 ， (0,1,1,12,0)T是这线 ， , , , 性规划问题的基可行解。 性规划问题的基可行解。 于是可以进行第二阶段 运算。 运算。将第一阶段的最终 表中的人工变量取消填入 原问题的目标函数的系数。 原问题的目标函数的系数。 进行第二阶段计算， 进行第二阶段计

算，见表 1-8。 。

优化类课程课件

表 1-17c j→ CB 0 1 1 c j -zj 0 M 1 c j -zj 0 1 1 c j -zj x4 x2 x3 12 1 1 x4 x6 x3 10 1 1 XB x4 x6 x7 b 11 3 1 0 x1 1 -4 -2 0 3 0 -2 0 3 0 -2 0 0 x2 -2 1 0 -1 -2 [1] 0 -1 0 1 0 0 0 x3 1 2 [1] -1 0 0 1 0 0 0 1 0 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 0 x5 0 -1 0 1 0 -1 0 1 -2 -1 0 0 1 x6 0 1 0 0 0 1 0 0 2 1 0 1 1 x7 0 0 1 0 -1 -2 1 3 -5 -2 1 1 1 θi 11 3/2 1

优化类课程课件

第二阶段计算，见表1-8c j→ CB 0 1 1 cj-zj -3 1 1 cj-zj x1 x2 x3 4 1 9 2 XB x4 x2 x3 b 12 1 1 -3 x1 [3] 0 -2 -1 1 0 0 0 1 x2 0 1 0 0 0 1 0 0 1 x3 0 0 1 0 0 0 1 0 0 x4 1 0 0 0 1/3 0 2/3 1/3 0 x5 -2 -1 0 1 -2/3 -1 -4/3 1/3 4 θi

从表 中得到最优解为 1=4,x2=1,x3=9, 从表1-8中得到最优解为 中得到最优解为x 目标函数值 z=-2.

优化类课程课件

5.2 退化 单纯形法计算中用θ规则确定换出变量时，有 单纯形法计算中用θ规则确定换出变量时， 时存在两个以上相同的最小比值， 时存在两个以上相同的最小比值，这样在下一 次迭代中就有一个或几个基变量等于零， 次迭代中就有一个或几个基变量等于零，这就 出现退化解。 出现退化解。 这时换出变量 l=0,迭代后目标函数值不变。 这时换出变量x ,迭代后目标函数值不变。 这时不同基表示为同一顶点。 这时不同基表示为同一顶点。有人构造了一个 特例，当出现退化时，进行多次迭代， 特例，当出现退化时，进行多次迭代，而基从 B1,B2,…又返回到 1,即出现计算过程的循环， 又返回到B 即出现计算过程的循环， 又返回到 便永远达不到最优解。 便永远达不到最优解。

优化类课程课件

尽管计算过程的循环现象极少出现， 尽管计算过程的循环现象极少出现，但还是有可 能的。如何解决这问题? 先后有人提出了“摄动 能的。如何解决这问题? 先后有人提出了“ 字典序法” 1974年由勃兰特 年由勃兰特(Bland) 法 ” , “ 字典序法 ” 。 1974 年由勃兰特 (Bland) 提出一种简便的规则， 提出一种简便的规则，简称勃兰特规则： (1) 选取 j-zj>0 中下标最小的非基变量 k为换 选取c 中下标最小的非基变量x 入变量， 入变量，即 k=min(j|cj-zj>0) (2) 当按θ规则计算存在两个和两个以上最小 比值时，选取下标最小的基变量为换出变量。 比值时，选取下标最小的基变量为换出变量。 按勃兰特规则计算时，一定能避免出现循环。 按勃兰特规则计算时，一定能避免出现循环。 证明可参考文献[ 证明可参考文献[4]

优化类课程课件

5.3 检验数的几种表示形式 目标函数: max z=CX;AX=b,X≥0 目标函数: cj-zj≤0,(j=1,2,…,n)作为最优解的 ≤0,(j=1,2, ,n ,(j=1,2, ,n) 判别准则。 判别准则。 还有其他的几种情况归纳如下: 还有其他的几种情况归纳如下: 设x1,x2,…,xm为约束方程的基变量，可得 设 为约束方程的基变

量，xi = bi

j = m +1

∑a

n

ij x j ,

i = 1,2, L, m

优化类课程课件

将它们代入目标函数后，可有两种表达形式(1) z=

∑ c b + ∑ (c ∑ c ai i n j i =1 j = m +1 i =1 j =m +1

m

n

m

i ij ) x j

= z0 +m

∑ (ci i

j

z j )x jn m

(1 37)

(2)

z=

∑ c b ∑ (∑ c ai =1 j = m +1 i =1 j = m +1

i ij

c j )x j (1 38)

= z0

∑ (z

n

j

c j )x j

优化类课程课件

判别准则的选择 要求目标函数实现最大化时，若用(1-37) 要求目标函数实现最大化时 若用 最大化 式来分析，就得到c 式来分析，就得到 j-zj≤0,(j=1,2,…,n) ( , ) 的判别准则。若用(1-38)式来分析，就得 式来分析， 的判别准则。若用 式来分析 到zj-cj≥0,(j=1,2,…,n)的判别准则。 ( )的判别准则。 在要求目标函数实现最小化时，可用(1在要求目标函数实现最小化 最小化时 可用(1 (137)式或(1-38)式来分析 式或(1 式来分析， 37)式或(1-38)式来分析，这时分别用 cj-zj≥0或zj-cj≤0,( =1,2, ,n)来 ≥0或 ≤0,( =1,2,…,n ,(j=1,2, ,n) 判别目标函数已达到最小。 判别目标函数已达到最小。 可按自己的习惯选用。 可按自己的习惯选用。

优化类课程课件

几种判别准则的汇总，表1-9。标准型 检验数 cj-zj zj-cj max z=CX AX=b,X≥0 ≤0 ≥0 min z=CX AX=b,X≥0 ≥0 ≤0

本文来源：https://www.bwwdw.com/article/m8ae.html