当前位置：文档之家 › 运筹学——单纯形矩阵描述与改进单纯形法

运筹学——单纯形矩阵描述与改进单纯形法

  • 格式：pptx
  • 大小：569.76 KB
  • 文档页数：58

下载文档原格式

  / 58

合集下载

运筹学 对偶理论和灵敏度分析

运筹学 对偶理论和灵敏度分析
对偶理论和灵敏度分析
1.单纯形的矩阵描述
用矩阵语言描述单纯形法的关键是写出两个基本的 表达式,设线性规划的标准型为 maxz=CX AX=b X≥0
C=(CB,CN)，X=(XB,XN)’，A=(B,N)
由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得 到用非基变量表示基变量的表达式:
-2 -3 -1 -1 1/3 x3 -1/3 0 x1 4/3 1 x5 1/3 0 0
' ' - a 1k / alk ' ' - a 2k / alk ... ' 1 / alk ... ' ' - a mk / alk
3对偶理论
某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最 后都需在C车间装配，相关数据如表所示： 问如何安排甲、乙两产品的产量，使利润为最大。 工时单耗 生产能力 产品 甲 乙 车间 A 1 0 8 B 0 2 12 C 3 4 36 单位产品获利 3 5 • maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 S.t. 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0
(4)影子价格在资源采购决策中的应用。
当资源的市场价格低于影子价格，企业买进该资源，扩 大生产，当资源的市场价格高于影子价格，企业应设法转让 该资源。
(5)利用影子价格分析工艺改变后对资源节约的收益。 例如设工厂现有钢材100吨，其影子价格为3/4，采用新 工艺后，钢材可以节约2%，则由此带来的经济收益为：
(3)影子价格在新产品开发决策中的应用。 产品 资源 A B 影子价格(万元)
钢材 煤 机时
单位利润(万元)

运筹学及其应用3.4 改进单纯形法

运筹学及其应用3.4 改进单纯形法

σENXXB
+
N
B−1 NX N − z = −C
= B−1b B B−1b
4
σENXXB
+
N
B−1b B B−1b
即 (CN − CB B−1N )X N − z = −CB B−1b
令 XN = 0
得 X B = B−1b,
z = CB B−1b,
σ N
= CN
− CB B−1N
基本可行解
X
=
B
−1b

0
目标函数
z = CBB−1b
注! 使σ N ≥ 0的B为最优基,
若能找到最优 B,则最优解直接由上式求 出.
5
v 在单纯形法的矩阵形式中我们可以发现，单纯形表中的其它 数字可利用B −1和原始系数进行运算直接得到：
σ j = c j − z j = c j − C B B −1 Pj
b' = B −1b
P
' j
=
B −1Pj
z = CB B−1b
v 这就是改进单纯形法的出发点。
v
令向量Y表示C
B
B
−1
，即
Y
= CBB−1 称其为单纯形乘子。
6
A = (B, N ), C = (CB ,C N ), X = ( X B , X N ),
min z = CB X B + C N X N BX B + NX N = b X B ≥ 0, X N ≥ 0
3
BX B + NX N = b CBXB + CN XN − z = 0 B−1BX B + B−1 NX N = B−1b 得X B = − B−1 NX N + B−1b 代入CB X B + CN X N − z = 0 (CN − CB B−1N )X N − z = −CB B−1b

运筹学单纯形法

运筹学单纯形法

单纯形表
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
Cj CB XB b 0 0 Z X3 3 X4 1 0 1 2 0 0
标准化
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
X1 X2 X3 X4 1 0 1 1 1 2 1 0 0 0 1 0
Z=x1+2x2 x1+x2+ x3 =3 x2 +x4=1 单纯形表
Cj
1
2
0
0
单纯形法原理 单纯形表 CB XB b
z=x1+2x2 x3 =3-x1-x2 x4=1 -x2
x2进基，x4离基
X1 X2 X3 X4

3/1 11
0
1 0
1 1
1 1
2 2 0 1 0 2 0 1 0 0 1 0 -1 0
max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40
x1=0
(x1,x2,x3,x4)= (0,1,2,0), z=2 C (x1,x2,x3,x4)= (2,1,0,0), z=4,最优解
B
x4=0 x3=0
(x1,x2,x3,x4)= (0,0,3,1), z=0
1 0
0 0
0 1
0
CB XB b 0 2 Z Cj CB XB b 1 2 Z X1 2 X2 1 4 X3 2 X2 1 2 1 1 0 0
X1 X2 X3 X4 1 0 1 1 0 0 0 -1 1 -1

运筹学5-单纯形法

运筹学5-单纯形法

保持可行性 保持可行性 保持可行性
保持可行性
X1
X2
X3
...
Xk
保持单调增 保持单调增 保持单调增
Z1
Z2
Z3
...
保持单调增
Zk
当Zk 中非基变量的系数的系数全为负值时，这时的基 本可行解Xk 即是线性规划问题的最优解，迭代结束。
(2) 线性规划的典则形式
标准型
Max Z CX AX b
s.t X 0
j 1
j 1
j 1
j 1
与X 0 相比，X 1 的非零分量减少1个，若对应的k-1个 列向量线性无关，则即为基可行解；否则继续上述步
骤，直至剩下的非零变量对应的列向量线性无关。
几点结论
❖ 若线性规划问题有可行解,则可行域是一个凸多边形或 凸多面体(凸集),且仅有有限个顶点(极点);
❖ 线性规划问题的每一个基可行解都对应于可行域上的 一个顶点(极点);
10
令 x1 0 x2 0
则 x3 15
X 0 0 15 24T
x4 24
为基本可行解，B34为可行基
B
0
X 24
3
108
A
0
X 34
0
15 24
0
0
X 23
12
45 0
1 基本解为边界约束方程的交点； 2 基对应于可行解可行域极点； 3 相邻基本解的脚标有一个相同。
1 0
1 0
B23 1 0 B24 1 1 B34 0 1
C42
2!
4! 4
2
!
43 21 21 21
6
由于所有|B|≠ 0， 所以有6个基阵和 6个基本解。

运筹学单纯形法

运筹学单纯形法
总结：①在迭代过程中要保持常数列向量非负，这能确保基 可行解旳非负性。最小比值能做到这一点。 ②主元素不能为0。因为行旳初等变换不能把0变成1。 ③主元素不能为负数。因为用行旳初等变换把负数变成1会 把常数列中相应旳常数变成负数。
16
三、其他解旳情况 1、无穷多种解 例2 解LP问题：
min Z x1 2 x2 x3 0 x4 0 x5
xx51
1 2c 5 3c
其中c是满足非负性旳任意常数。
21
再由
x1,
x5
旳非负性，知：
x1 x2
1 2c c
0 0
x5 5 3c 0
解出 0 c 5 3
最优解为：
(2c 1, c,0,0,5 3c)T （其中0 c 5 ）
3
最优值为：max S 1.
22
2、无最优解旳两种情况：
相应地，将 X 0代入目的函数得 Z ( X 0 ) 0
从数学角度看，若让非基变量 x1, x2 取值从零增长，
6
min Z 2x1 x2 0x3 0x4 0x5
相应旳目旳函数值Z也将随之降低。所以有可能找到一种 新旳基本可行解，使其目旳函数值有所改善。即进行基变
换，换一种与它相邻旳基。再注意到 x1 前旳系数－2比 x2
x3
6 x1 x1
2x2 x2
x4 x5
xi 0
i 1,,5
15 24 5
目前可行基{ x3, x4 , x5 }所相应旳基本可行解
X 0 (0,0,15,24,5)T
(相应可行域旳 o(0,0) )
显然不是最优。 因为从经济意义上讲， x1 0, x2 0
意味着该厂不安排生产，所以没有利润。
2

运筹学第2章 单纯形法

运筹学第2章 单纯形法

所有检验数 j 0 ，则这个基本可行解是最优解。
n
z z0 j x j
j m 1
m
j ciaij c j =CTBa j c j
i 1
m
m
z0 c j x j = cibi =CBT b
j 1
i 1
✓对于求目标函数最小值的情况，只需 σj≤0
0
XB
b
x1
-1 x5 0
0
0 x4 3
1
-3 0
0
00
x2
x3
x4
0
-2 0
2
-2 1
0 10
-1 bi/aik
x5
1
0
0
29 2020/3/4
2、无界解
在求目标函数最大值的问题中，所谓无界解是指在约束条件 下目标函数值可以取任意的大。
•存在着一个小于零的检验数，并且该列的系数向量的每个元素 都小于或等于零，则此线性规划问题是无界的，一般地说此类
2x1 x2 x3 x5 2
s.t. x1 2x2
x4
3

x1,
x2 , x3, x4 , x5 0
✓添加人工变量x5来人为的创造一个单位矩阵作为基 ✓M叫做罚因子，任意大的数。 ✓人工变量只能取零值。必须把x5从基变量中换出去，否 则无解。
cj
3
2
00
CB XB
2020/3/4
14
(2)出基变量和主元的确定——最小比值规则
min

bi aik
aik

0


bl alk
确定出基变量的方法：把已确定的入基变量在各约束方程中的正的系数

运筹学---单纯形法

运筹学---单纯形法单纯形法是一种解线性规划问题的有效算法。

在这个问题中，我们寻找一组决策变量，以便最大化或最小化一个线性目标函数，同时满足一系列线性限制条件。

单纯形法通过暴力搜索可行解并逐步优化目标函数来求解该问题。

单纯形法的主要思想是从一个初始可行解开始，并通过迭代来逐步移动到更优的解。

在每一步迭代中，算法将当前解移动到一个相邻的顶点，直到找到一个优于当前解的顶点。

具体操作包括选择一个非基变量，并将其作为入基变量，同时选择一个基变量并将其作为出基变量。

新的基变量将替换原来的非基变量，并且目标函数的值将被更新。

关键是如何选择入基变量和出基变量。

为此，单纯形法使用一个称为单纯形表的矩阵来跟踪线性规划问题的状态。

单纯形表包含目标函数系数，限制条件系数，决策变量的当前值以及对角线上的单位矩阵。

通过适当地操作这个表，可以确定要移动到哪个相邻顶点，并相应地更新解和目标函数的值。

一般来说，单纯形法需要在指数时间内解决线性规划问题，因为需要遍历所有可能的可行解。

但是，在实际应用中，单纯形法往往比其他算法更快和更有效。

此外，在使用单纯形法时，需要注意陷入无限循环或者找不到一个可行解的可能性。

单纯形法的主要优点是：它是一种简单而直观的求解线性规划问题的方法；它易于实现，并且在许多情况下可以很快地求解问题。

它还可以用于解决大规模问题，包括具有成千上万个变量和限制条件的问题。

在实际应用中，单纯形法经常与其他算法结合使用，例如内点法或分支定界法。

这些方法可以提供更好的性能和结果。

但是，在许多情况下，单纯形法仍然是解决线性规划问题的首选算法。

在总体上，单纯形法是一种强大而灵活的工具，可以帮助研究人员和决策者在面对复杂的决策问题时做出明智的选择，并实现最大的效益。

运筹学02-单纯形法


反之，若经过迭代，不能把人工变量都变
为非基变量，则表明原LP问题无可行解。
19
第2章
单纯形法
2.3 人工变量法
2.3.1 大M法
在原问题的目标函数中添上全部人工变量，并令其系数 都为-M，
而M是一个充分大的正数。即
max z = c1x1 + c2x2 + c3x3 + … + cnxn – M( xn+1 + xn+2 +…+ xn+m )
思路：由一个基本可行解转化为另一个基本可行解。 等价改写为 目标方程 max z max z = 3x1+5x2 z -3x1 -5x2 = 0 z -3x1 -5x2 x1 +x3 x1 +x3 = 8 2x2 +x4 2x2 +x4 = 12 s.t. s.t. 3x1+4x2 +x5 3x1 + 4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 x1 ， x2 ，x3，x4，x5 ≥ 0
以主列中正值元素为分母，同行右端常数为分子，求比值；
6
第2章
单纯形法
2.1 单纯形法的基本思想
(Ⅰ)
用换基运算 将X0 转化为 另一个基本 可行解 X1。
z- 3x1 -5x2 = 0 0 换基运算—— x1 +x3 = 8 ① 方程组的初等变换 目的是把主列变为 22x2 +x4 = 12 ② 单位向量：主元变 3x1 + 4x2 +x5 = 36 ③ 为1，其余变为0。 X0 = ( 0, 0, 8, 12, 36 )T z0 = 0
⑴ 当前基：m阶排列阵

3.1单纯形法的矩阵描述

故所有检验数可表示 C C B B1 A与 C B B1
§3.1 单纯形法的矩阵描述
• (2)单纯形表与矩阵表示的关系
Page 8
由（ 3 - 5)、（ 3 - 6)式知 X B +B 1 NX N B 1b - z (C N C B B N ) X N -C B B b
Page 5
由(3 - 3)式知 BX B b NX N X B B 1b B 1 NX N 上式代入 (3 - 2)式得 z C B (B 1b B 1 NX N ) C N X N =C B B 1 b ( C N C B B 1 N ) X N (3 6 ) (3 5)
因为，不满足最优性条件，所以不是最优解
小结
学习要点：
Page 14
1. 掌握矩阵的运算； 2.理解基矩阵的作用； 3.了解矩阵运算与单纯表的关系。
The end,thank yoቤተ መጻሕፍቲ ባይዱ!
运筹学
( Operations Research )
Chapter3 对偶理论和灵敏度分析
本章主要内容：
§3.1 单纯形法的矩阵描述 §3.2 单纯形法的矩阵计算
§3.3 对偶问题的提出
§3.4 线性规划的对偶理论
§3.5 影子价格
§3.6 对偶单纯形法
§3.7 灵敏度分析
( Duality Theory )
量是基变量， 从而确定基矩 阵； b.求基矩阵的 逆矩阵； c.求检验数。
N 1 3
1 / 2 0 2 1 1 4 1 3 0 4 0 1 1 1 2 0
1 3 0 4 2 2 3 1 2
2 由最终表反推出初始表 例2：设用单纯形法求解某个线性规划问题的最终表如下（目标max， 约束 Page 12 为≤形式，x3,x4,x5为松弛变量），试写出原始线性规划模型。

3.1单纯形法的矩阵描述

0 0 σj7 x115 x2来自0 x30 x4
0 x5 0 0 1
二、单纯形法矩阵描述 Page 9 bi 6 θi 6/1 8/2 3/1 0 3 3/1 2/1 — 45 的应用
1 检查计算是否正确
x3
x4 x5
1
1 0 7
1
2 1 15
1
0 0 0
0
1 0 0
8 3
0
-1 -2 1 -15 1 -2 1
2 由最终表反推出初始表 例2：设用单纯形法求解某个线性规划问题的最终表如下（目标max， 约束 Page 11 为≤形式，x3,x4,x5为松弛变量），试写出原始线性规划模型。
x3 x1 x2 σj 解：
0
0
1 0 0 0
1
-1 1 0 -7
1 -2 1 -1
1 2 3
松弛变量的价值系数为0 x1、x2的价值系数设为c1、c2
1 0 0
0 1 0
1 1 1 1 1 1 1 1 B ( B ) 0 1 2 0 1 2 p3 0 0 1 0 0 1
p1
p2
0 − c1 = −7
c1 = 7
0 +2c1−c2 = −1
故：
c2 = 15
目标函数值：
常数项：
1 1 1 6 1 1 X B B b 0 1 2 8 2 0 0 1 3 3
z C B B 1b 1 0 7 15 2 59 3
运筹学
( Operations Research )
( Duality Theory )
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

( B 1b)i (B1Pj )i
(B1Pj )i
0
( B 1b)l (B1Pj )l
换入变量的系数向量
10
小结
1）掌握矩阵的运算； 2）理解基矩阵的作用； 3）了解矩阵运算与单纯表的关系。
11
求解线性规划问题的关键是计算B-1 ，以下介绍一 种比较简便的计算B-1的方法。
设mn系数矩阵为A，求其逆矩阵时，可先从第1列开始。
a11
A
a21
a12
a22
a1m a2m
am1
am2
amm
12
以a11为主元素, 进行变换
a11
主元素
P1
a21
1/ a11
1
a21 /
a11
(1)
am1
am1
/
a11
13
然后构造含有（1）列，而其他列都是单位列的矩阵
1/ a11 0 0
E1
a21 /
BXB b NX N ; X B B1b B1NX N ; 目标函数：
z CB B1b (CN CB B1N ) X N
(2 1) (2 2) (3 2)
4
令非基变量=0，由上式得到：
基可行解
X
(1)
B 1b 0
;
目标函数的值 z CBB1b
5
（1）非基变量的系数表示为： (CN CB B1N ) 对应已用的检验数符号 c j z j ( j 1,2,, n) 所有检验数可表示为： C - CBB1(B | N )
6
（2）单纯形表与矩阵表示的关系
X B B1NX N B1b; 目标函数：
- z (CN CB B1N ) X N -CB B1b
0 I
B 1 N
1 0 CN CB B1N
z
X X
B N
B1b CB B1b
(2 7)
7
单纯形表中的数据
基变量
非基变量
系数矩阵 检验数
XB B1B I
（4）基变换计算 将新的基 P3,P4 ,P2 单位矩阵。计算：
2
1/ 2
1 1/ 2
P2 0
1
0
；构造 E1
1
0
4
主元素
1 / 4
1 / 4
1 1/ 21
1 1/ 2
B11
E1B01
1
0 1 1
0
1/ 4
1
1/ 4
22
（5）计算非基变量的系数矩阵
)
E2
E1
A
0 0
1 0
a( 2 ) 23
a( 2 ) m3
a2(
2) m
a( 2 )
mm
17
重复以上的步骤，直到获得
1
Em
E2
E1
A
1
I
1
可见En…E2E1=A-1。用这方法可以求得单纯形法的基矩阵B的 逆矩阵B-1
18
第2节 改进单纯形法
以例1为例进行计算。
max z 2x1 3x2 0x3 0x4 0x5
X
X X
B N
相应地可将目标函数系数C分为两部分：CB和CN，分别 对应于基变量XB和非基变量XN，并且记作
C=（CB, CN）
3
线性规划问题可表示为：
目标函数 max z CB X B CN X N 约束条件 BX B NX N b 非负条件 XB, X N 0
将（2-2）式移项及整理后得到：
0
XN B 1 N CN CB B1N
等式右边
RHS B 1b CB B1b
8
单纯形表中的数据
基变量
非基变量 松弛变量 等式右边
XB 系数矩阵 B1B I
检验数
0
XN
Xs RHS
B1N
B1
B1b
CN CBB1N CBB1 CBB1b
9
（3）θ规则表示为：
RHS值
表示选用>0的分量
min
/
a(1 22
)
P( 1 ) 2
2
1
/
a(1 22
)
(2)
a(1) m2
/
a(1 22
)
16
然后构造含有（2）列，而其他列都是单位列的矩阵
可得到
1
a( 1 ) 12
/
a(1) 22
0
E2
0
0
1
/
a(1 22
)
a( 1 ) m2
/
a(1) 22
0 1
1
0
a( 2 ) 13
a( 2 1m
x1 2x2 x3
8
4 x1
x4 16
4 x2
x5 12
19
第2节 改进单纯形法
第1步：确定初始基，初始基变量;确定换入、换出变量 （1）确定初始基和初始基变量：
1
B0 P3 ,
P4 ,
P5
1
x3
; X B0 x4
1
x5
（2）计算非基变量的检验数，确定换入变量。 N0 CN0 CB0 B01N0 ( 注意：N0 P1 ,P2 )
价值系数 C CB1 ,CN1 ( 0,0,3),( 2,0 )
24
第2节 改进单纯形法
第2步：计算非基变量的检验数，确定换入变量
N1 CN1 CB1 B11N1 ( 注意：N1 P1 ,P5 )
a11
1
am1 / a11
1
14
可得到
a21
a11
a21 a11
a22
a12
a21 a11
1
1
a(1) 12
a(1) 1m
E1P1
0 0
;
E1
A
0 0
a(1) 22
a(1) m2
a(1) 2m
a(1)
mm
15
而后以第2列的
a(1) 22
为主元素，进行变换
a(1) 12
第1节 单纯形法的矩阵描述
设线性规划问题可以用如下矩阵形式表示： 目标函数 max z=CX 约束条件 AX≤b 非负条件 X≥0
1
将该线性规划问题的约束条件加入松弛变量后，得到标 准型：
max z=CX+0Xs AX+IXs=b
X，X s≥0
其中I 是m×m单位矩阵。
2
若以Xs为基变量，并标记成XB，可将系数矩阵（A，I） 分为（B，N）两块。B是基变量的系数矩阵，N是非基 变量的系数矩阵。并同时将决策变量也分为两部分：
2,
3
(
0,0,0
)
1 0
0 1
01 2 04 0
0 0 1 0 4
2, 3 对应 x1,x2
换入变量
20
第2节 改进单纯形法
(3) 确定换出变量
表示选择>0的元素
min
B01b B01P2
i i
B01P2 0
min
8 2
,16 0
ቤተ መጻሕፍቲ ባይዱ
,12 4
3
对应x 5
21
第2节 改进单纯形法
1
1 1 / 21
N1 4
B11N1
1
0 4
1
1 / 4 1
1 1 / 2 4 0
1 / 4
（6）计算RHS
1 1 / 2 8 2
B11b
1
0 16 16
1/ 4
12
3
23
第2节 改进单纯形法
第1步计算结束后的结果
基 B1 P3 ,P4 ,P2 ; 基变量 X B1 x3 ,x4 ,x2 T ; 非基变量 X N1 x1,x5 T ;