大学本科 运筹学 教程第二章线性规 划(2).ppt

文档介绍：0
x1
(1)
(2)
x2
Z=
Z=6
2
3
2
1
=MinZ
∴ x﹡= ( , )T,
z﹡=
(1)
A
0
x1
(1)
x2
1
(2)
8
Z=-3
Z=-8
(6,3)
∴无最优解
(4)
LP问题的单纯形法
Simplex method
单纯形法基本思想
线性规划的基可行解,对应于其可行域的各个顶点;
一个线性规划问题若存在最优解,则最优解必在可行域的顶点处,即最优解必是基可行解中的一个(或一些)。
单纯形法基本思想
将模型的一般形式变成标准形式,再根据标准型模型,从可行域中找一个基本可行解,并判断是否是最优。如果是,获得最优解;如果不是,转换到另一个基本可行解,当目标函数达到最大时,得到最优解。
线性规划模型的标准形式
表格形式:
设变量
j
i
Max(min)Z = c1x1 + …+ cnxn
. a11x1 + …+ a1nxn ≤( =, ≥) b1
a21x1 + …+ a2nxn ≤( =, ≥) b2
︰
︰
am1x1 + …+ amnxn ≤( =, ≥) bm
x1 , … xn ≥ 0
例:
maxZ = 3x1-3x2+5x4-x5
. x1 -2x3 +2x4 =12
x2 -2x3 =1
-4x3 +3x4 +x5 =27
x1, x2 , x3 , x4 , x5 ≥ 0
1 0 -2 2 0
0 1 -2 0 0
0 0 -4 3 1
x1
x2
x5
maxZ =∑cx
. ∑ax =b
x ≥0
b ≥0
关于基
1 0 0
0 1 0
0 0 1
x1
x2
x5
的典式
maxZ = 3x1-3x2+5x4-x5
. x1 -2x3 +2x4 =12
x2 -2x3 =1
-4x3 +3x4 +x5 =27
x1, x2 , x3 , x4 , x5 ≥ 0
对基
1 0 0
0 1 0
0 0 1
x1
x2
x5
x1 =12 x2 =1
有基可行解
x3 =0 x4 =0
x5 = 27
初始单纯形表
C j
-1
5
0
-3
3
比值
基xB
解b′
-3
3
X1
12
-
27
2
-4
0
0
6
-1
0
X2
X5
1
X1
X2
X3
X4
X5
1
-2
2
0
0
0
-4
3
1
0
0
-2
1
0
0
检验行σj
σj =cj-cB aj
σ4>0
min
目标函数值
θi
CB