OR1 1
第二章 线性规划与单纯形法
2.1 LP(linear programming)的基本概念
LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。
LP有一组有待决策的变量，
一个线性的目标函数，
一组线性的约束条件 。
OR1 2
2.1.1 LP的数学模型例题 1— 生产计划问题
某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：
产品 A 产品 B 资源限量劳动力设 备原材料
9
4
3
4
5
10
360
200
300
利润 元 /kg 70 120
OR1 3
例题 1建模
问题：如何安排生产计划，使得获利最多？
步骤：
1、确定决策变量：设生产 A产品 x1kg,B产品 x2kg
2、确定目标函数,maxZ=70X1+120X2
3、确定约束条件：人力约束 9X1+4X2≤360
设备约束 4X1+5X2 ≤200
原材料约束 3X1+10X2 ≤300
非负性约束 X1≥0 X2≥0
OR1 4
例题 2—— 配方问题
养海狸鼠 饲料中营养要求,VA每天至少 700克,VB每天至少 30克,VC每天刚好 200克。现有五种饲料，搭配使用，饲料成分如下表：
饲料 Va Vb Vc 价格元 /KG
I
II
III
IV
V
3
2
1
6
18
1
0.5
0.2
2
0.5
0.5
1
0.2
2
0.8
2
7
4
9
5
营养要求 700 30 200
OR1 5
例题 2建模
设抓取饲料 I x1kg;饲料 II x2kg;饲料 III x3kg……
目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5
约束条件,3x2+2x2+x3+6x4+18x5 ≥700
营养要求,x1+0.5x2+0.2x3+2x4+0.5x5 ≥30
0.5x1+x2+0.2x3+2x4+0.8x5 =200
用量要求,x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40
非负性要求,x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
OR1 6
例题 3：人员安排问题
医院护士 24小时值班，每次值班 8小时。
不同时段需要的护士人数不等。据统计：
序号 时段 最少人数 安排人数
1 06— 10 60 X1
2 10— 14 70 X2
3 14— 18 60 X3
4 18— 22 50 X4
5 22— 02 20 X5
6 02— 06 30 x6
OR1 7
例题 3建模
目标函数,min Z=x1+x2+x3+x4+x5+x6
约束条件,x1+x2 ≥70
x2+x3 ≥60
x3+x4 ≥ 50
x4+x5 ≥20
x5+x6 ≥30
非负性约束,xj ≥0,j=1,2,…6
OR1 8
归纳：线性规划的一般模式
目标函数,max(min)Z=c1x1+c2x2+c3x3+…+c nxn
约束条件,a11x1+a12x2+a13x3+…+a 1nxn ≤(= ≥)b1
a21x1+a22x2+a23x3+…+a 2nxn ≤(= ≥)b2
… … … …
am1x1+am2x2+am3x3+…+a mnxn ≤(= ≥)bn
非负性约束,x1 ≥0,x2 ≥0,…,x n ≥0
OR1 9
2.1.2线性规划图解法
由中学知识可知,y=ax+b是一条直线，同理,Z=70x1+120x2→x 2=70/120x1-Z/120也是一条直线，以 Z为参数的一族等值线。
9x1+4x2 ≤360 → x 1 ≤360/9-4/9x2
是直线 x1=360/9-4/9x2 下方的半平面。
所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。
OR1 10
例 1图示
.
90
80
60
40
20
0 20 40 60 80 100
x1
x2
9x1+4x2≤ 360
4x1+5x2≤200
3x1+10x2≤300
A
B
C
D E F
G
H I
Z=70x1+120x2
OR1 11
概念
概念：
1、可行解：满足所有约束条件的解。
2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。
3、基解：约束条件的交点称为基解（直观）
4、基可行解：基解当中的可行解。
5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形
OR1 12
结论
可行域是个凸集
可行域有有限个顶点
最优值在可行域的顶点上达到
无穷多解的情形
无界解情形
无解情形
OR1 13
2.1.3线性规划的标准型
代数式 maxZ=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn=b1
a21x1+a22x2+…+a 2nxn=b2
… … …
am1x1+am2x2+…+a mnxn=bm
xj≥0 j=1,2,…,n
OR1 14
线性规划的标准型
和式,maxZ=∑cjxj
∑aijxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
j=1
n
n
j=1
OR1 15
线性规划的标准型
向量式,maxZ=CX
∑pjxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
C=(c1,c2,c3,…,c n)
X=(X1,X2,X3,…,X n) T
n
j=1
OR1 16
线性规划的标准型
矩阵式,maxZ=CX AX=b X ≥0
其中,b=(b1,b2,…,b m)T
a11 a12 …,a1n
A= a21 a22 … a2n
… … …
am1 am2 … amn
OR1 17
标准型的特征
目标函数极大化
约束条件为等式
决策变量非负
OR1 18
非标准型转化为标准型
目标函数极小化转为极大化：
minZ=－ max(－ Z),一个数的极小化等价于其相反数的极大化。
不等式约束的转化,∑aijxj≤bi 加入松弛变量
∑aijxj≥bi 减去剩余变量
非正变量：即 xk ≤0 则令 x’k =－ xk
自由变量：即 xk无约束，令 xk= x’k－ x”k
OR1 19
非标准型转化举例 之一
maxZ=70X1+120X2 maxZ=70X1+120X2
9X1+4X2≤360 9X1+4X2+X3=360
4X1+5X2 ≤200 4X1+5X2 +x4=200
3X1+10X2 ≤300 3X1+10X2+x5 =300
X1≥0 X2≥0 Xj≥0 j=1,2,…,5
OR1 20
非标准型转化举例 之二
minZ=x1+2x2-3x3 maxZ’=x’1－ 2x2+3(x’3－ x”3)
x1+x2+x3 ≤9 － x’1+x2+x’3－ x”3 + x4=9
-x1-2x2+x3 ≥2 x’1－ 2x2+x’3 － x”3 - x5= 2
3x1+x2-3x3=5 － 3x’1+x2－ 3(x’3 － x”3 )=5
x1 ≤0 x2 ≥0 x3无约束 x’1 ≥ 0 x2 ≥0 x’3 ≥0
x”3 ≥0 x4≥0 x5≥0
OR1 21
2.1.4基可行解
基的概念,如前所述 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中 m?m阶非奇异子矩阵，则称
B是 LP的一个 基,即,B是 A中 m个线性无关向量组。
n
j=1
n
j=1
OR1 22
基解的概念不失一般性,设 B是 A的前 m列,即
B=(p1,p2,…,p m）,其相对应的变量
XB=(x1,x2,…,x m)T,称为基变量；其余变量
XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则 X=（ x1,x2,… xm,0,…,0)T
称为基解 。
OR1 23
基可行解的概念
基可行解,基解可正可负，负则不可行
（违背非负性约束条件），称满足所有约束条件的基解为 基可行解。
退化的基可行解,若某个基变量取值为零，
则称之为退化的基可行解。
基解的数目：最多 Cmn=n!/m!(n-m)!
OR1 24
例题 6 基可行解说明
maxZ=70X1+120X2 P1 P2 P3 P4 P5
9X1+4X2+X3=360 9 4 1 0 0
4X1+5X2 +x4=200 A= 4 5 0 1 0
3X1+10X2+x5 =300 3 10 0 0 1
Xj≥0 j=1,2,…,5
这里 m=3,n=5。 Cmn=10
OR1 25
例题 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图）
OR1 26
2.2单纯形法
2.2.1初始基可行解的确定从系数矩阵中找到一个可行基 B，不妨设 B由 A
的前 m列组成，即 B=(P1,P2,……Pm) 。进行等价变换－－约束方程两端分别左乘 B－ 1 得
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2
…………………………….,
xm+a’mm+1xm+1+…+ a’mnxn=b’m
令非基变量为 0，得基可行解
X(0)=(b1’,b2’,……b m,0,……0 ） T z0=∑cibi’
OR1 27
2.2单纯形法
2.2.2最优性检验,LP经过若干步迭代，成为如下形式：
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1- ∑a’1jxj
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2- ∑a’2jxj
…………………………….,……………..
xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m- ∑a’mjxj
OR1 28
单纯形法一般性表示,xi=b’i- ∑a’ijxj i=1,2,…m 将 xi代入目标函数得,Z= ∑ cjxj
= ∑ cixi+ ∑ cjxj
= ∑ci（ b’i- ∑a’ijxj ） + ∑ cjxj
= ∑cibi’+∑(cj- ∑ cia’ij)xj
令,σj= cj- ∑ cia’ij z0=∑cibi’ 则 Z=z0+ ∑ σj xj
σj判别准则,σj ≤0时,达到最优解
OR1 29
单纯形法
2.2.2基变换若存在 σ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处在变量转换的交叉点上，称之为枢轴元素
σj ≥ 0
OR1 30
单纯形法解题举例单纯形表的格式：
Cj C1 C2 … C n
θiCB XB b x1 x2 …,xn
C1
C2
…
Cm
x1
x2
…
xm
b 1
b2
…
bm
a11 a12 … a 1n
a21 a22 … a 2n
… … …
am1 am2… a mn
θ1
θ2
…
θm
σj σ1 σ2 … σ n
OR1 31
Cj C1 C2 … C n
CB XB b X1 X2 X3 X4 X5 θj
0
0
0
X3
X4
X5
360
200
300
9 4 1 0 0
4 5 0 1 0
3 10 0 0 1
90
40
30
σj 0 70 120 0 0 0
0
0
120
X3
X4
X2
240
50
30
7.8 0 1 0 -0.4
2.5 0 0 1 -0.5
0.3 1 0 0 0.1
30.76
20
100
σj 3600 34 0 0 0 -12
70
120
0
X3
X1
X2
84
20
24
0 0 1 -3.12 1.16
1 0 0 0.4 -0.2
0 1 0 -0.12 0.16
σj 4280 0 0 0 -13.6 -5.2
OR1 32
2.2.3单纯形法的计算步骤
找到初始可行基，建立单纯形表
计算检验数，若所有 σj ≤0则得最优解，结束。否则转下步
若某 σK ≥ 0而 P’K ≤0,则最优解无界，结束。否则转下步
根据 max {σj } =σK 原则确定 XK 进基变量；根据 θ
规则,θ = min {b’i / a’ik a’ik >0} = b’L/ a’Lk 确定 XL为出基变量
以 a’Lk 为枢轴元素进行迭代，回到第二步
OR1 33
2.3单纯形法的进一步探讨
2.3.1极小化问题直接求解：检验数的判别由所有 σj ≤0即为最优，变为所有 σj≥ 0则为最优。
人工变量法之一：大 M法 人工变量价值系数 M
例
人工变量法之二：构造目标函数，分阶段求解例
2.3.2无穷多最优解情形：非基变量检验数 σj= 0
2.3.3退化解的情形：有两个以上 θ值相等
OR1 34
2.3.4单纯形法的计算机求解
程序说明
应用举例例题 1
例题 2
OR1 35
2.5LP应用举例之一
例 13合理下料问题料长 7.4米，截成 2.9,2.1,1.5米各 200根。
如何截取余料最少？关键：设变量。
方案料型
1 2 3 4 5 6 7 8
2.9米
2.1米
1.5米
1 2 0 1 0 1 0 0
0 0 2 2 1 1 3 0
3 1 2 0 3 1 0 4
合计残料
7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0
0 0.1 0.2 0.3 0.8 0.9 1.1 1.4
OR1 36
应用举例之二
例 14混合配方问题
A,B,C,D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。
已知产品价格和原料价格，求利润最大的配方。关键：设变量。
OR1 37
应用举例之三
例 15.滚动投资问题兹有 100万元闲钱，投资方向有四：
第四年第一年 第二年 第三年
A项目 110%
B项目 135%
C项目 125%
D项目 104%
第五年各年投资什么项目，使第五年末资本总额为最大？
OR1 38
应用举例之四
例 16动态生产计划问题工厂做 n个月的生产计划，第 j月需求量 dj、
正常生产能力 aj、加班生产能力 bj、正常生产成本 cj、加班生产成本 ej、库存能力为 I、库存费用
hj，设期初、期末库存为零。求费用最小的生产计划。
设第月正常生产 xj件，加班生产件 yj，存储 zj
件。则：
本期生产 +上期库存 -本期库存 =本期需求
第二章 线性规划与单纯形法
2.1 LP(linear programming)的基本概念
LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。
LP有一组有待决策的变量，
一个线性的目标函数，
一组线性的约束条件 。
OR1 2
2.1.1 LP的数学模型例题 1— 生产计划问题
某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：
产品 A 产品 B 资源限量劳动力设 备原材料
9
4
3
4
5
10
360
200
300
利润 元 /kg 70 120
OR1 3
例题 1建模
问题：如何安排生产计划，使得获利最多？
步骤：
1、确定决策变量：设生产 A产品 x1kg,B产品 x2kg
2、确定目标函数,maxZ=70X1+120X2
3、确定约束条件：人力约束 9X1+4X2≤360
设备约束 4X1+5X2 ≤200
原材料约束 3X1+10X2 ≤300
非负性约束 X1≥0 X2≥0
OR1 4
例题 2—— 配方问题
养海狸鼠 饲料中营养要求,VA每天至少 700克,VB每天至少 30克,VC每天刚好 200克。现有五种饲料，搭配使用，饲料成分如下表：
饲料 Va Vb Vc 价格元 /KG
I
II
III
IV
V
3
2
1
6
18
1
0.5
0.2
2
0.5
0.5
1
0.2
2
0.8
2
7
4
9
5
营养要求 700 30 200
OR1 5
例题 2建模
设抓取饲料 I x1kg;饲料 II x2kg;饲料 III x3kg……
目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5
约束条件,3x2+2x2+x3+6x4+18x5 ≥700
营养要求,x1+0.5x2+0.2x3+2x4+0.5x5 ≥30
0.5x1+x2+0.2x3+2x4+0.8x5 =200
用量要求,x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40
非负性要求,x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
OR1 6
例题 3：人员安排问题
医院护士 24小时值班，每次值班 8小时。
不同时段需要的护士人数不等。据统计：
序号 时段 最少人数 安排人数
1 06— 10 60 X1
2 10— 14 70 X2
3 14— 18 60 X3
4 18— 22 50 X4
5 22— 02 20 X5
6 02— 06 30 x6
OR1 7
例题 3建模
目标函数,min Z=x1+x2+x3+x4+x5+x6
约束条件,x1+x2 ≥70
x2+x3 ≥60
x3+x4 ≥ 50
x4+x5 ≥20
x5+x6 ≥30
非负性约束,xj ≥0,j=1,2,…6
OR1 8
归纳：线性规划的一般模式
目标函数,max(min)Z=c1x1+c2x2+c3x3+…+c nxn
约束条件,a11x1+a12x2+a13x3+…+a 1nxn ≤(= ≥)b1
a21x1+a22x2+a23x3+…+a 2nxn ≤(= ≥)b2
… … … …
am1x1+am2x2+am3x3+…+a mnxn ≤(= ≥)bn
非负性约束,x1 ≥0,x2 ≥0,…,x n ≥0
OR1 9
2.1.2线性规划图解法
由中学知识可知,y=ax+b是一条直线，同理,Z=70x1+120x2→x 2=70/120x1-Z/120也是一条直线，以 Z为参数的一族等值线。
9x1+4x2 ≤360 → x 1 ≤360/9-4/9x2
是直线 x1=360/9-4/9x2 下方的半平面。
所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。
OR1 10
例 1图示
.
90
80
60
40
20
0 20 40 60 80 100
x1
x2
9x1+4x2≤ 360
4x1+5x2≤200
3x1+10x2≤300
A
B
C
D E F
G
H I
Z=70x1+120x2
OR1 11
概念
概念：
1、可行解：满足所有约束条件的解。
2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。
3、基解：约束条件的交点称为基解（直观）
4、基可行解：基解当中的可行解。
5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形
OR1 12
结论
可行域是个凸集
可行域有有限个顶点
最优值在可行域的顶点上达到
无穷多解的情形
无界解情形
无解情形
OR1 13
2.1.3线性规划的标准型
代数式 maxZ=c1x1+c2x2+…+c nxn
a11x1+a12x2+…+a 1nxn=b1
a21x1+a22x2+…+a 2nxn=b2
… … …
am1x1+am2x2+…+a mnxn=bm
xj≥0 j=1,2,…,n
OR1 14
线性规划的标准型
和式,maxZ=∑cjxj
∑aijxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
j=1
n
n
j=1
OR1 15
线性规划的标准型
向量式,maxZ=CX
∑pjxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
C=(c1,c2,c3,…,c n)
X=(X1,X2,X3,…,X n) T
n
j=1
OR1 16
线性规划的标准型
矩阵式,maxZ=CX AX=b X ≥0
其中,b=(b1,b2,…,b m)T
a11 a12 …,a1n
A= a21 a22 … a2n
… … …
am1 am2 … amn
OR1 17
标准型的特征
目标函数极大化
约束条件为等式
决策变量非负
OR1 18
非标准型转化为标准型
目标函数极小化转为极大化：
minZ=－ max(－ Z),一个数的极小化等价于其相反数的极大化。
不等式约束的转化,∑aijxj≤bi 加入松弛变量
∑aijxj≥bi 减去剩余变量
非正变量：即 xk ≤0 则令 x’k =－ xk
自由变量：即 xk无约束，令 xk= x’k－ x”k
OR1 19
非标准型转化举例 之一
maxZ=70X1+120X2 maxZ=70X1+120X2
9X1+4X2≤360 9X1+4X2+X3=360
4X1+5X2 ≤200 4X1+5X2 +x4=200
3X1+10X2 ≤300 3X1+10X2+x5 =300
X1≥0 X2≥0 Xj≥0 j=1,2,…,5
OR1 20
非标准型转化举例 之二
minZ=x1+2x2-3x3 maxZ’=x’1－ 2x2+3(x’3－ x”3)
x1+x2+x3 ≤9 － x’1+x2+x’3－ x”3 + x4=9
-x1-2x2+x3 ≥2 x’1－ 2x2+x’3 － x”3 - x5= 2
3x1+x2-3x3=5 － 3x’1+x2－ 3(x’3 － x”3 )=5
x1 ≤0 x2 ≥0 x3无约束 x’1 ≥ 0 x2 ≥0 x’3 ≥0
x”3 ≥0 x4≥0 x5≥0
OR1 21
2.1.4基可行解
基的概念,如前所述 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中 m?m阶非奇异子矩阵，则称
B是 LP的一个 基,即,B是 A中 m个线性无关向量组。
n
j=1
n
j=1
OR1 22
基解的概念不失一般性,设 B是 A的前 m列,即
B=(p1,p2,…,p m）,其相对应的变量
XB=(x1,x2,…,x m)T,称为基变量；其余变量
XN=(Xm+1,…,Xn)T称为非基变量。令所有非基变量等于零,则 X=（ x1,x2,… xm,0,…,0)T
称为基解 。
OR1 23
基可行解的概念
基可行解,基解可正可负，负则不可行
（违背非负性约束条件），称满足所有约束条件的基解为 基可行解。
退化的基可行解,若某个基变量取值为零，
则称之为退化的基可行解。
基解的数目：最多 Cmn=n!/m!(n-m)!
OR1 24
例题 6 基可行解说明
maxZ=70X1+120X2 P1 P2 P3 P4 P5
9X1+4X2+X3=360 9 4 1 0 0
4X1+5X2 +x4=200 A= 4 5 0 1 0
3X1+10X2+x5 =300 3 10 0 0 1
Xj≥0 j=1,2,…,5
这里 m=3,n=5。 Cmn=10
OR1 25
例题 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图）
OR1 26
2.2单纯形法
2.2.1初始基可行解的确定从系数矩阵中找到一个可行基 B，不妨设 B由 A
的前 m列组成，即 B=(P1,P2,……Pm) 。进行等价变换－－约束方程两端分别左乘 B－ 1 得
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2
…………………………….,
xm+a’mm+1xm+1+…+ a’mnxn=b’m
令非基变量为 0，得基可行解
X(0)=(b1’,b2’,……b m,0,……0 ） T z0=∑cibi’
OR1 27
2.2单纯形法
2.2.2最优性检验,LP经过若干步迭代，成为如下形式：
X1+ +a’1m+1xm+1+…+ a’1nxn=b’1 x1=b’1- ∑a’1jxj
x2+ +a’2m+1xm+1+…+ a’2nxn=b’2 x2=b’2- ∑a’2jxj
…………………………….,……………..
xm+a’mm+1xm+1+…+ a’mnxn=b’m xm=b’m- ∑a’mjxj
OR1 28
单纯形法一般性表示,xi=b’i- ∑a’ijxj i=1,2,…m 将 xi代入目标函数得,Z= ∑ cjxj
= ∑ cixi+ ∑ cjxj
= ∑ci（ b’i- ∑a’ijxj ） + ∑ cjxj
= ∑cibi’+∑(cj- ∑ cia’ij)xj
令,σj= cj- ∑ cia’ij z0=∑cibi’ 则 Z=z0+ ∑ σj xj
σj判别准则,σj ≤0时,达到最优解
OR1 29
单纯形法
2.2.2基变换若存在 σ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处在变量转换的交叉点上，称之为枢轴元素
σj ≥ 0
OR1 30
单纯形法解题举例单纯形表的格式：
Cj C1 C2 … C n
θiCB XB b x1 x2 …,xn
C1
C2
…
Cm
x1
x2
…
xm
b 1
b2
…
bm
a11 a12 … a 1n
a21 a22 … a 2n
… … …
am1 am2… a mn
θ1
θ2
…
θm
σj σ1 σ2 … σ n
OR1 31
Cj C1 C2 … C n
CB XB b X1 X2 X3 X4 X5 θj
0
0
0
X3
X4
X5
360
200
300
9 4 1 0 0
4 5 0 1 0
3 10 0 0 1
90
40
30
σj 0 70 120 0 0 0
0
0
120
X3
X4
X2
240
50
30
7.8 0 1 0 -0.4
2.5 0 0 1 -0.5
0.3 1 0 0 0.1
30.76
20
100
σj 3600 34 0 0 0 -12
70
120
0
X3
X1
X2
84
20
24
0 0 1 -3.12 1.16
1 0 0 0.4 -0.2
0 1 0 -0.12 0.16
σj 4280 0 0 0 -13.6 -5.2
OR1 32
2.2.3单纯形法的计算步骤
找到初始可行基，建立单纯形表
计算检验数，若所有 σj ≤0则得最优解，结束。否则转下步
若某 σK ≥ 0而 P’K ≤0,则最优解无界，结束。否则转下步
根据 max {σj } =σK 原则确定 XK 进基变量；根据 θ
规则,θ = min {b’i / a’ik a’ik >0} = b’L/ a’Lk 确定 XL为出基变量
以 a’Lk 为枢轴元素进行迭代，回到第二步
OR1 33
2.3单纯形法的进一步探讨
2.3.1极小化问题直接求解：检验数的判别由所有 σj ≤0即为最优，变为所有 σj≥ 0则为最优。
人工变量法之一：大 M法 人工变量价值系数 M
例
人工变量法之二：构造目标函数，分阶段求解例
2.3.2无穷多最优解情形：非基变量检验数 σj= 0
2.3.3退化解的情形：有两个以上 θ值相等
OR1 34
2.3.4单纯形法的计算机求解
程序说明
应用举例例题 1
例题 2
OR1 35
2.5LP应用举例之一
例 13合理下料问题料长 7.4米，截成 2.9,2.1,1.5米各 200根。
如何截取余料最少？关键：设变量。
方案料型
1 2 3 4 5 6 7 8
2.9米
2.1米
1.5米
1 2 0 1 0 1 0 0
0 0 2 2 1 1 3 0
3 1 2 0 3 1 0 4
合计残料
7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0
0 0.1 0.2 0.3 0.8 0.9 1.1 1.4
OR1 36
应用举例之二
例 14混合配方问题
A,B,C,D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。
已知产品价格和原料价格，求利润最大的配方。关键：设变量。
OR1 37
应用举例之三
例 15.滚动投资问题兹有 100万元闲钱，投资方向有四：
第四年第一年 第二年 第三年
A项目 110%
B项目 135%
C项目 125%
D项目 104%
第五年各年投资什么项目，使第五年末资本总额为最大？
OR1 38
应用举例之四
例 16动态生产计划问题工厂做 n个月的生产计划，第 j月需求量 dj、
正常生产能力 aj、加班生产能力 bj、正常生产成本 cj、加班生产成本 ej、库存能力为 I、库存费用
hj，设期初、期末库存为零。求费用最小的生产计划。
设第月正常生产 xj件，加班生产件 yj，存储 zj
件。则：
本期生产 +上期库存 -本期库存 =本期需求
