当前位置:文档之家› 4第四章线性规划的标准型及单纯形法

4第四章线性规划的标准型及单纯形法


30
单纯形法的计算步骤
• 1、找到初始可行基,建立单纯形表 • 2、计算检验数,若σj ≤0 则得最优解。否则转下步 • 3、若某σK ≥ 0而P’K ≤0 ,则最优解无界,否则转 下步 • 4、根据max {σj } = σK 原则确定XK 进基变量;根 据θ规则 θ = min {b’i / a’ik a’ik >0} = b’l/ a’lk 确定XL出 基变量 • 5、以a’lk 为枢轴元素进行迭代 • 6、重复第二步到第五步
31
单纯形法的进一步探讨
• 极小化问题直接求解:检验数的判别由σj ≤0
• • • • 变为σj ≥ 0 人工变量法之一:大M法 人工变量价值系数M例 人工变量法之二:构造目标函数,分阶段求解例 无穷多最优解情形:非基变量检验数 σj= 0 退化解的情形:有两个以上 θ值相等
32
单纯形法的计算机求解
• 程序说明 • 应用举例 例题1 例题2
33
34
Obj :
n
MaxZ c j x j
j 1
n
S .T .
a
j 1
ij
x j bi
i 1,2, , m
xj 0
j 1,2, , n
7
线性规划的标准型
• 向量式:
Obj :
n
MaxZ CX
S .T .
p
j 1
j
x j bi
i 1,2, , m
xj 0 C ( c1 ,c 2 , , c n )
a
n j
n
, ij
xj
代入
j m 1 ,
c
xj
c i bi c i
, i 1 m i 1
m
m
j m 1
aij x j
m i 1
n
j m 1 ,
c
n
j
xj
c i bi
, i 1
j m 1

j
n
(c j c i a ij )x j 判别标准: j 0, 达 到 最 大 值
5
线性规划的标准型
• 代数式 Maxz=c1x1+c2x2+…+cnxn
s.t. a11x1+a12x2+…a1nxn=b1 a21x1+a22x2+…a2nxn=b2
……
am1x1+am2x2+…amnxn=bm
x1,x2,…,xn≥0
(xj ≥0
j=1,2,…,n)
6
线性规划的标准型
• 和式:
10
非标准型转化举例之一
maxZ=70X1+120X2 9X1+4X2 ≤360 4X1+5X2 ≤200 3X1+10X2≤300 X1≥0 X2≥0 maxZ=70X1+120X2 9X1+4X2+X3=360 4X1+5X2 3X1+10X2 +x4=200
+ 5
x
=300
X1≥0 X2≥0 X3 ≥0 ≥0
24
Z0
j m 1

n
xj
单纯形法
• 基变换 若σj ≥ 0,则取 max{σj } = σK ,相应之非基变量XK 若非零,将使Z增加,故令XK 进基。令XK≠0 其余 非基变量保持为零, XK 原是非基变量,取零值, XK ≠0 将迫使某个原基变量为零,当XK取值超过 任意b’i / a’ik 时,将破坏非负性条件, 于是令θ = min {b’i / a’ik ,a’ik >0 } = b’L/ a’Lk 。 这时原基变量XL=0,由基变量变成非基变量 a’Lk处在变量转换的交叉点上,称之为枢轴元素
3600
84 20 24 4280
30.76 20 100
σj
0 70 120 X3 X1 X2 σj
34
0 1 0 0
0
0 0 1 0 1 0 0 0
0
0
-12
-3.12 1.16 0.4 -0.2 -0.12 0.16 -13.6 -5.2
29
Cj
CB
3 -3 -1
3 -3 0
b
12 1 27 6
26
某厂生产两种产品,需要三种资源,已知各 产品的利润、各资源的限量和各产品的资源 消耗系数如下表:
劳动力 设备 原材料 单位产品利 润(元)
产品A 9 4 3 70
产品B 4 5 10 120
资源限制 360工时 200台时 300公斤
27
• 问题:如何安排生产计划,使得获利最多? • 步骤:
21
• (SLP)的基可行解对应于其可行域的顶 点(极点) • 若(SLP)有最优解,则必有最优基可行 解
• 可行基解——迭代——更优的可行基解— —最优基解(单纯形法的原理)
22
单纯形法
• 最优性检验:LP经过若干步迭代,成为如下形 式:
X1+
+a’1m+1xm+1+…+a’1nxn=b’1 +a’2m+1xm+1+…+a’2nxn=b’2 …………………………….. xm+a’mm+1xm+1+…+a’mnxn=b’m

a mn a1n a12
9
非标准型转化为标准型
• 目标函数极小化转为极大化: minZ=-max(-Z) ,一个数的极小化等价于其相反数的极 大化。 • 不等式约束的转化: ∑aijxj≤bi 加入松弛变量 ∑aijxj≥bi 减去剩余变量 • 非正变量:即xk ≤0 则令x’k =- xk 自由变量:即xk无约束,令xk= x’k- x”k
m
19
例题6 基可行解说明
maxZ=70X1+120X2 9X1+4X2+X3=360
4X1+5X2 +x4=200
P1 P2 P3 P4 P5
9 A= 4
4 5
1 0
0 1
0 0
3X1+10X2+x5 =300 Xj≥0 j=1,2,…,5 m 这里m=3,n=5。 C n=10
3
10
0
0
1
20
例题6 基可行解说明
• 基(P3,P4,P5),令非基变量x1,x2=0, 则基变量x3=360, x4=200, x5=300,可行解
• 基(p2,p4,p5),令非基变量x1=0,x3=0基变量 x2=90,x4=-250,x5=-600.非可行解 • 基( p2,p3,p4 ),令非基变量x1,x5=0,则 基变量x2=30, x3=240, x4=50,可行解(P21图)
• 设m×n矩阵A中有一个r阶子式D不等于零, 而所有r+1阶子式(如果存在的话)全等于 零,则称D为矩阵A的最高阶非零子式,称 数r为矩阵A的秩,记作R(A)=r。 • 零矩阵的秩为零。 • m×n矩阵A的秩R(A)≤min{ m,n}
• 假设:约束方程组的系数矩阵A的秩为m (R(A)=m),m<n
25
单纯形法解题举例
单纯形表的格式:
Cj
CB
C1 C2 … CM
XB b
X1 b 1 X2 B2 … … XM bm σj
C1 C2 … CN X1 x2 …. Xn a11 a21 … am1 σ1 a12 … a22 … … am2… σ2 … a1n a2n … amn σn
θi
θ1 θ2 … θm
16

•基的概念:如前所述LP标准型
和式:maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n 矩阵式:maxZ=CX AX=b X ≥0 约束方程的系数矩阵A的秩为m,且m<n。设 A=B+N ,B是A中mxm阶非奇异子矩阵,则称B是 LP的一个基,即:B是A中m个线性无关向量组。
1、确定决策变量:设生产A产品x1kg,B产品x2kg
2、确定目标函数:maxZ=70X1+120X2 3、确定约束条件: 人力约束 9X1+4X2≤360 设备约束 4X1+5X2 ≤200 原材料约束3X1+10X2 ≤300 非负性约束X1≥0 X2≥0
28
Cj
CB
0 0 0
70 120 0 0 0
17
基解
不失一般性,设B是A的前m列,即 B=(p1,p2,…,pm),其相对应的变量 XB=(x1,x2,…,xm)T,称为基变量;其余变量 XN=(Xm+1,…,Xn)T称为非基变量。 令所有非基变量等于零, 则X=(x1,x2,…xm,0,…,0)T称为基解 。
18
基可行解
• 基可行解:基解可正可负,负则不可行, 故称满足非负性条件的基解为基可行解。 • 相应的基为可行基。 • 退化的基可行解:若某个基变量取值为零, 则称之为退化的基可行解。 • 基解的数目:最多C n=n!/m!(n-m)!
x’1 ≥ 0 x2 ≥0 x’3 ≥0 x”3 ≥0 x4≥0 x5≥0
12
非标准型转化举例之三
minZ=-3x1-x2+4x3
-x1+2x2+x3 =5 x1-x2+x3 ≥-6 x1 ≤0 x2 ≥0 x3无约束
13
非标准型转化举例之三
minZ=-3x1-x2+4x3 maxZ’=-3x’1+x2-4(x’3-
x4
x5 ≥0
11
非标准型转化举例之二
相关主题