版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
管理运筹学课件第一章—管理运筹学线性规划
管理运筹学
OperationalResearch
天津大学管理学院
郭均鹏
管理运筹学
教师简介：
郭均鹏：博士，副教授，
硕士生导师。
主要研究领域：运筹决策技术；
信息管理与8＞企业信息3〉化；
绩效考核与薪酬体系设计
联系方式：天津大学管理学院，300072
guojp@tju.edu
管理运筹学
授课内容：
线性规划
图论与网络分析
网络计划
风险型决策
排队论
博弈论
课程教材：
吴育华，杜纲.《管理科学基础》，天津大学出版社。
管理运筹学
绪论
产生于二战时期，运筹学(OperationalResearch)直译为“运作研究”。
60年代，在工业、农业、社会等各领域得到广泛应用
在我国，50年代中期由钱学森等引入
运用数学方法，为决策者进行最优决策提供科学依据的一门应用科学。
一、运筹学的产生与发展
二、学科性质
管理运筹学
三、运筹学的分支
线性规划
非线性规划
图论与网络分析
存储论
决策论
排队论
对策论(博弈论)
管理运筹学
四、管理运筹学的工作程序
明确问题
问题分类
建立数学模型
求解数学模型
结果分析
实施
注意计算机软件的应用一一
Lindo、WinQSB等
管理运筹学
第一章线性规划
(LinearProgramming,简称LP)
§1线性规划的模型与图解法
一、LP问题及其数学模型
例1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单
耗数据如表，试拟定使总收入最大的生产计划。
12
7
单价
300
10
3
油
200
5
4
电
360
4
9
煤
资源限制
乙
甲
产品
资源
管理运筹学
12
7
单价
300
10
3
油
200
5
4
电
360
4
9
煤
资源限制
乙
甲
产品
资源
线性规划模型三要素：
（1）决策变量
设甲产品生产xl,乙产品生产x2
(2)目标函数
MaxZ=7xl+12x2
(3)约束条件
9xl+4x2W360
4x1+5x2<200
3xl+10x2<300
xl,x220
s.t.
返回
SubjectTo,意为“使其满足”
管理运筹学
Max(Min)Z=clxl+c2x2+…+cnxn
allxl+al2x2+…+alnxnW(=,2)bl
amixl+am2x2+…+amnxnW=,2)bm
xl,x2,,,,,xn20
LP模型的一般形式
矩阵表示
MaxZ=CX
AXWb
X20
s.t.
其中：
X=(xl,x2,…，xn)T为决策变量C=(cl,c2,…，cn)称为价格
系数
A=(aij)mXn称为技术系数
b=(bl,b2,…，bm)T称为资源系数
管理运筹学
课堂练习
某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四
种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试
决定总花费最小的购买方案。(列出模型)
7
8
5
10
每头日需
200
0.2
0.4
0.3
0.1
N
300
0
0.3
0.2
0.5
M
价格
D
C
B
A
养分
饲料
管理运筹学
课堂练习
某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四
种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试
决定总花费最小的购买方案。（列出模型）
7
8
5
10
每头日需
200
0.2
0.4
0.3
0.1
N
300
0
0.3
0.2
0.5
M
价格
D
C
B
A
养分
饲料
答案：设购买M饲料xl,N饲料x2
0.5xl+0.1x2210
0.2x1+0.3x225
0.3x1+0.4x2Q8
0.2x227
xl,x220
s.t.
MinZ=300xl+200x2
管理运筹学
二、线性规划的图解法
1.步骤
（1）作约束的图形一一可行域
可行解的集合
①先作非负约束
②再作资源约束
9x1+4x2=360
4x1+5x2=200
3x1+10x2=300
公共部分，即为可行域
例：煤电油例
MaxZ=7xl+12x2
9xl+4x2W360
4x1+5x2<200
3xl+10x2<300
xl,x220
s.t.
xl
x2
40
20
60
80
100
20
40
60
80
100
0
管理运筹学
（2）作目标函数的等值线
①给z不同的值，作相应直线，判断出z增大时，直线的移动方向
②将直线向增大方向移动，直至可行域边界，交点X*即为最优解。
7x1+12x2=84
7x1+12x2=168
如：令7xl+12x2=84
7xl+12x2=168
9x1+4x2=360
4x1+5x2=200
3x1+10x2=300
20
60
80
100
20
40
60
80
100
0
X*=(20,24),
Z*=428
管理运筹学
最优解：xl=0,x21
最优目标值z=3
课堂练习
图解法求解线性规划
0
1
2
3
4
1
2
3
4
x
1
X
2
0
-1
-2
(1)
(2)
(3)
管理运筹学
2.LP解的几种情况
（1）唯一解
（2）多重最优解
（3）无可行解
注：出现（3）、（4）情况时，建模有问题
（4）无有限最优解
管理运筹学
图解法的结论：
线性规划的可行域是凸集
线性规划的最优解若存在，必在可行域的在极点获得
若在两个极点同时获得，则有无穷多最优解
凸集
不是凸集
极点
管理运筹学
三、线性规划应用举例与软件求解
例1（下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5
m的圆钢各一根。已知原料每根长7.4m,问：应如何下料，可使所用原料最省？
管理运筹学
例1（下料问题）某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5
口的圆钢各一根。已知原料每根长7.4m,问：应如何下料，可使所用原料最省？
余料
1.5
2.1
2.9
方案
7.4m
2.9m
2.Im
1.5m
2
0
1
0.1
I
1
2
0
0.3
II
1
1
1
0.9
III
1
0
3
0
IV
0
3
0
1.1
V
0
2
2
0.2
VI
0
1
3
0.8
vn
0
0
4
1.4
vm
管理运筹学
50
io
30
2x1+x2+x3+x4=100
2x2+x3+3x5+2x6+x7=100
xl+x3+3x4+2x6+3x7+4x8=100
xl,x2,x3,x4,x5,x6,x7,x820
设xl,x2,x3,x4,x5,x6,x7,x8分别为上述8种方案下料的原材料根数，
建立如下的LP模型：
最优解为：xl=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0
minZ=xl+x2+x3+x4+x5+x6+x7+x8
s.t.
余料
1.5
2.1
2.9
方案
2
0
1
0.1
I
1
2
0
0.3
II
1
1
1
0.9
III
1
0
3
0
IV
0
3
0
1.1
V
0
2
2
0.2
VI
0
1
3
0.8
vn
0
0
4
1.4
VDI
管理运筹学
一、线性规划的标准型
MaxZ=clxl+c2x2+,,,+cnxn
allxl+al2x2+…+alnxn=bl
amixl+am2x2++amnxn=bm
xl,x2,,xn20
s.t.
1、标准形式
MaxZ=CX
AX=b
X20
s.t.
注：标准型中要求bi20
§2单纯形法
矩阵表示
管理运筹学
2、非标准型
标准型
(1)MinZ=CX
MaxZ'=-CX
(2)约束条件
例如：9xl+4x2W360
9xl+4x2+x3=360
松弛变量
“W”型约束，加松弛变量；
“2”型约束，减松弛变量；
(3)自由变量xj
进行变量替换：xj=xj'-xj'',其中xj'、
xj''20
管理运筹学
二、LP解的基本概念
考虑标准型：
MaxZ=CX
AX=b
X20
s.t.
(1)
(2)
1.可行解
满足(1)、(2)的解
2.基本解
设r(A)=m,
则BX=b有唯一解，
称
为基本解，简称基解。
且不妨设
非奇异，
O
设为
结论：基本解的个数W
管理运筹学
3.基可行解
若基解X20,则称为基可行解。
可行解
基解
基可行解
结论：LP的基可行解对应于可行域的顶点。
基：A中m阶可逆子阵，记为B。
基向量：B中的列。
基变量：和基向量相对应的决策变量。
其余部分称为非基子阵，记为N。
管理运筹学
例、研究约束集合
基本解的个数W
令x2=x3=0,得基本解
Xl=(l/2,0,0)T,
对应于A点；
1/2
1
1/3
A
B
C
x2
x3
xl
令xl=x3=0,得基本解
X2=(0,1,0)T,
对应于B点；
令xl=x2=0,得基本解
X3=(0,0,1/3)T,
对应于C点；
管理运筹学
基可行解
例、研究约束集合
基本解的个数W
令xl=0,得基本解
Xl=(0,3,2,-1)T,
对应于A点；
令x2=0,得基本解
X2=(3,0,1,-8)T,
对应于B点；
令x3=0,得基本解
X3=(2,1,0,5)T,
对应于F点；
画出可行域
1
2
3
4
1
2
3
4
A
B
C
D
E
F
0
xl
x2
标准化
令x4=0,得基本解
X4=(l/3,8/3,5/3,0)T,
对应于D点；
管理运筹学
三、单纯形法的基本方法
基本方法：
确定初始基可行解
检验是否最优？
转到另一更好的
基可行解
停
Y
N
方法前提：模型化为标准型
管理运筹学
1.初始可行基B0的确定
若A中含有I：BO=I
若A中不含I：人工变量法
管理运筹学
2.最优性检验
矩阵分块
把目标函数用非基变量表示：
检验数向量，记为。。当。W0时，当前解为最优解。
方法：
(1)计算每个xj的检验数
(2)若所有。jWO,则当前解为最优；
否则，至少有ok>O,转3。
管理运筹学
3.换基迭代(基变换)
(1)进基：取
对应的Pk进基。
(2)出基：取
对应的P1进基。
得新基，转2。
管理运筹学
。的计算：
0
0
x5
x4
x3
x2
xl
B-lb
CB
XB
四、单纯形法的实现一一单纯形表
例：煤电油例
MaxZ=7xl+12x2
9xl+4x2W360
4x1+5x2W200
3xl+10x2W300
xl,x220
s.t.
MaxZ=7xl+12x2
9xl+4x2+x3=360
4x1+5x2+x4=200
3xl+10x2+x5=300
xl，…，x5N0
s.t.
化为标准型
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表：
7
管理运筹学
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
四、单纯形法的实现一一单纯形表
例：煤电油例
MaxZ=7xl+12x2
9xl+4x2^360
4x1+5x24200
3xl+10x2W300
xl,x220
s.t.
MaxZ=7xl+12x2
9xl+4x2+x3=360
4x1+5x2+x4=200
3xl+10x2+x5=300
xl，…，x520
s.t.
化为标准型
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表：
7
90
9的计算：
40
30
管理运筹学
o
9
x5
x4
x3
x2
xl
B-lb
CB
XB
四、单纯形法的实现一一单纯形表
例：煤电油例
MaxZ=7xl+12x2
9xl+4x2W360
4x1+5x2W200
3xl+10x2<300
xl,x220
s.t.
MaxZ=7xl+12x2
9xl+4x2+x3=360
4x1+5x2+x4=200
3xl+10x2+x5=300
xl,x5N0
s.t.
化为标准型
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[]
枢纽元素
管理运筹学
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表：
7
90
40
30
[]
x3
x4
x2
0
0
12
30
0.3
1
0
0
0.1
o
以10为主元进行初等行变换
50
2.5
0
0
1
-0.5
240
7.8
0
1
0
-0.4
3.4
0
0
0
—1.2
即：
管理运筹学
O
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[]
x3
x4
x2
0
0
12
30
0.3
1
0
0
0.1
以10为主元进行初等行变换
50
2.5
0
0
1
-0.5
240
7.8
0
1
0
-0.4
3.4
0
0
0
-1.2
即：
30.8
20
100
管理运筹学
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[]
x3
x4
x2
0
0
12
30
0.3
1
0
0
0.1
o
以10为主元进行初等行变换
50
2.5
0
0
1
-0.5
240
7.8
0
1
0
-0.4
3.4
0
0
0
-1.2
30.8
20
100
[]
管理运筹学
x3
xl
x2
0
7
12
24
0
1
0
-0.12
0.16
o
20
1
0
0
0.4
-0.2
84
0
0
1
-3.12
1.16
0
0
0
-1.36
-0.52
o
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[]
x3
x4
x2
0
0
12
30
0.3
1
0
0
0.1
50
2.5
0
0
1
-0.5
240
7.8
0
1
0
-0.4
3.4
0
0
0
-1.2
30.8
20
100
[]
以为主元进行初等行变换
2.5
管理运筹学
x3
xl
x2
0
7
12
24
0
1
0
-0.12
0.16
o
20
1
0
0
0.4
-0.2
84
0
0
1
-3.12
1.16
0
0
0
-1.36
-0.52
o
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[]
x3
x4
x2
0
0
12
30
0.3
1
0
0
0.1
50
2.5
0
0
1
-0.5
240
7.8
0
1
0
-0.4
3.4
0
0
0
-1.2
30.8
20
100
[]
，X*=(20,24,84,0,0)T
Z*=428
管理运筹学
例：
用单纯形法求解
MinS=-xl+2x2
xl-x2>-2
xl+2x2W6
xl,x220
s.t.
化为标准型
MaxS?=xl-2x2
-xl+x2+x3=2
xl+2x2+x4=6
xl,…，x420
s.t.
-2
1
o
6
1
0
2
[1]
6
0
x4
不考虑
0
1
1
-1
2
0
x3
0
x4
x3
x2
xl
B-lb
CB
XB
-1
0
-4
0
o
1
0
2
1
6
1
xl
1
1
3
0
8
0
x3
，X*=(6,0,8,0)T
Z*=-6
管理运筹学
x3
xl
x2
0
7
12
24
0
1
0
-0.12
0.16
o
20
1
0
0
0.4
-0.2
84
0
0
1
-3.12
1.16
0
0
0
-1.36
-0.52
o
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
x3
x4
x2
0
0
12
30
0.3
1
0
0
0.1
50
2.5
0
0
1
-0.5
240
7.8
0
1
0
-0.4
3.4
0
0
0
-1.2
30.8
20
100
注：单纯形表中的信息
⑴每一列的含义：
B-l(bA)=(B-lb,B-lPl,B-lPn)
⑵每个表中的B和B-l的查找：
B从初表中找；
B-l从当前表中找，对应于初表中的I的位置。
以第2个表为例：
管理运筹学
⑶终表分析——最优基B*和(B*)-l的查找
x3
xl
x2
0
7
12
24
0
1
0
-0.12
0.16
o
20
1
0
0
0.4
-0.2
84
0
0
1
-3.12
1.16
0
0
0
-1.36
-0.52
o
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
x3
x4
x2
0
0
12
30
0.3
1
0
0
0.1
50
2.5
0
0
1
-0.5
240
7.8
0
1
0
-0.4
3.4
0
0
0
-1.2
30.8
20
100
注：单纯形表中的信息
管理运筹学
1＞五、人工变量法（大M法）
1问题：
例：用单纯形法求解
MaxZ=5xl+3x2+2x3+4x4
5x1+x2+x3+8x4=10
2x1+4x2+3x3+2x4=10
xl,x2,x3,x420
s.t.
MaxZ=CX
AX=b
X20
s.t.
设问题：
，A中不含I
（I）
管理运筹学
增加人工变量X人=（xn+1,....,xn+m）T,
X人在目标函数中的系数为-M（M为充分大正数）。
于是原问题化为：
2方法：
单纯形法求解（H）,若
最优基变量中不含X人，则所得解的前n个分量即为X*
否则，（I）无解。
3结论：
MaxZ=CX-MX人
AX+IX人力
X,X人20
s.t.
（ID
管理运筹学
例：用单纯形法求解
MaxZ=5xl+3x2+2x3+4x4
5x1+x2+x3+8x4=10
2x1+4x2+3x3+2x4=10
xl,x2,x3,x420
s.t.
解：增加人工变量x5、x6,则模型化为:
MaxZ=5x1+3x2+2x3+4x4-Mx5-Mx6
5x1+x2+x3+8x4+x5=10
2xl+4x2+3x3+2x4+x6=10
xl,…，x620
s.t.
管理运筹学
MaxZ=5xl+3x2+2x3+4x4-Mx5-Mx6
5x1+x2+x3+8x4+x5=10
2xl+4x2+3x3+2x4+x6=10
xl,,,,,x620
s.t.
0
1
x5
o
1
2
3
4
2
0
8
1
1
5
0
x6
x4
x3
x2
xl
B-lb
CB
XB
x5
x6
-M
-M
10
10
5+7M
3+5M
2+4M
4+10M
0
0
5/4
5
管理运筹学
0
1
x5
o
1
2
3
4
2
0
[8]
1
1
5
0
x6
x4
x3
x2
xl
B-lb
CB
XB
x5
x6
-M
-M
10
10
5+7M
3+5M
2+4M
4+10M
0
0
5/4
5
o
x4
x6
4
-M
5/4
5/8
1/8
1/8
1
0
15/2
3/4
15/4
11/4
0
1
5/2+3/4M
0
0
5/2+15/4M
3/2+11/4M
10
2
管理运筹学
0
1
x5
o
1
2
3
4
2
0
⑻
1
1
5
0
x6
x4
x3
x2
xl
B-lb
CB
XB
x5
x6
-M
-M
10
10
5+7M
3+5M
2+4M
4+10M
0
0
5/4
5
o
x4
x6
4
-M
5/4
5/8
1/8
1/8
1
0
15/2
3/4
[15/4]
11/4
0
1
5/2+3/4M
0
0
5/2+15/4M
3/2+11/4M
10
2
o
x4
x2
4
3
1
3/5
0
1/30
1
2
1/5
1
11/15
0
2
0
0
-1/3
5/3
10
管理运筹学
0
1
x5
o
1
2
3
4
2
0
[8]
I
1
5
0
x6
x4
x3
x2
xl
B-lb
CB
XB
x5
x6
-M
-M
10
10
5+7M
3+5M
2+4M
4+10M
0
0
5/4
5
x4
x6
4
-M
5/4
5/8
1/8
1/8
1
0
15/2
3/4
[15/4]
11/4
0
1
5/2+3/4M
0
0
5/2+15/4M
3/2+11/4M
10
2
o
x4
x2
4
3
1
[3/5]
0
1/30
1
2
1/5
1
11/15
0
2
0
0
-1/3
5/3
10
o
xl
x2
5
3
5/3
1
0
1/18
5/3
5/3
0
1
13/18
-1/3
0
-10/3
0
-4/9
，X*=(5/3,5/3,0,0)T,Z*=40/3
管理运筹学
六、单纯形法总结
1、Min型单纯形表与Max型的区别仅在于:
令ok=min{ojW0}的xk进基，当。20时最优。
2、解的几种情况及其在单纯形表上的体现(讨论Max型)
唯一
最优解
◎j<0,
非基。<0
多重
最优解
ojW0
有非基。k=0
无界解
有ok>0
但BTPkW0
无可行解
用大M法求解，最优基中含有X人
退化解
最优解中某基变量为0
管理运筹学
§3线性规划的对偶问题
(DualProgramming,简称DP)
一、对偶问题的提出和模型
1、问题的提出
煤电油例
今有另厂要购买三种资源，在原厂可接受的条件下，单价多少可是另厂付
费最低？
MaxZ=7xl+12x2
9xl+4x2W360
4x1+5x2W200
3xl+10x2W300
xl,x220
s.t.
设煤电油价格分别为yl,y2,y3
MinW=360yl+200y2+300y3
s.t.
9yl+4y2+3y327
4yl+5y2+10y3212
yl,y2,y320
DUAL
管理运筹学
2、模型
MaxZ=CX
AXWb
X20
s.t.
原问题(P):
对偶问题(D)：
MinW=bTY
ATY2CT
Y20
s.t.
特点：
(1)P为max型，D为min型
(2)P的变量个数=D的约束个数
(3)P的约束个数=D的变量个数
MaxZ=7xl+12x2
9xl+4x2W360
4x1+5x2W200
3xl+10x2<300
xl,x220
s.t.
MinW=360yl+200y2+300y3
s.t.
9yl+4y2+3y327
4yl+5y2+10y3>12
yl,y2,y320
管理运筹学
1、对称性
(P)与(D)互为对偶
二、对偶性质与定理
2、弱对偶性
设X、Y分别为(P)、(D)的任一可行解，则
管理运筹学
3、解的最优性
设分别为（P）与（D）的可行解，且
则
4、无界性
若（P）为无界解,则（D）无可行解
若（D）为无界解,则（P）无可行解
管理运筹学
5、对偶定理
若（P）有最优解,则（D）也有最优解,且二者最优值相等.
管理运筹学
小结:
（1）对偶最优解Y*=CBB-1,其中B为原问题的最优基;
（2）如何从（P）的终表中确定Y*?
Y*即为（P）终表的XS的检验数的负值；
若无XS,则用Y*=CB*（B*）T计算。
-CBB-l
C-CBB-1A
B-l
B-1A
CBB-lb
0
XS
C
X
6、检验数
管理运筹学
x3
xl
x2
0
7
12
24
0
1
0
-0.12
0.16
o
20
1
0
0
0.4
_0.2
84
0
0
1
-3.12
1.16
0
0
0
-1.36
-0.52
o
0
x5
x4
x3
x2
xl
B-lb
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
例:煤电油的单纯形表:
7
90
40
30
（初表）
（终表）
由终表:Y*=（0,1.36,0.52）T
管理运筹学
三、对偶问题最优解的经济解释一一影子价格
设DP其最优值为Z*(注：与LP最优值同)，则根据
Z*=bTy*=blyl*+b2y2*+????+bmym*
??Z/??bi=yi*
简单推导：
Y*=(yl*,y2*,...,ym*)为DP的最优解，则yi*表示LP某资
源bi变化1个单位对目标产生的影响，称yi*为bi的影子价格。
例、煤电油例的对偶问题的最优解为Y*=(01.360.52),
则煤电油三种资源的影子价格分别为0、1.36,0.52
管理运筹学
影子价格在管理决策中的作用：
(1)影子价格W市场价格
若
影子价格＞市场价格，则应
影子价格〈市场价格，则应
买进该资源
卖出该资源
(2)影子价格反映了资源的稀缺性，
影子价格越高，则越稀缺
例如：煤的影子价格为0,则表明有剩余
管理运筹学
§4灵敏度分析
任务：当LP的系数A、b、c变化时，是否影响最优解或最优基？
或：若不影响最优解或最优基，A、b、c的变化范围？
对解的影响
可行性:B-lb^0
最优性：
管理运筹学
一、b变
(只影响解的可行性)
问题：br在何范围变化时，不影响最优基？
设第r种资源br-br+A(b-*
)
方法：
(保证可行性)
即
,解出△即可
例：煤电油例，讨论b2的变化
解得-50WAW27或150Wb2W227
管理运筹学
二、C变
（只影响解的最优性）
问题：cj在何范围变化时，不影响最优基（解）？
设第j种资源cjfcj+4（cf
）
方法：
（讨论检验数）
（1）cj为非基价格系数
，解出
管理运筹学
（2）cj为基价格系数
此时需考虑所有非基变量的检验数：
解出
例：煤电油例，为使最优解不变，求cl的变化范围。
解：考虑所有非基检验数
同理，
令
基变量的检验数仍全为0,故无需考虑。
管理运筹学
三、A变
（1）增加新变量xn+1
8
10
单价
4
8
油
3
6
电
12
3
煤
T
丙
例如，煤电油例又增加产品丙或丁，相关数据如右表。
问题：增加后是否影响最优基（解），从而判断是否有利？（使目标改善）
方法：是否有利取决于是否进基。
故只需计算
,则有利
,则不利
例：
丙不应投产。
同理可得
丁应投产。
管理运筹学
（2）某列Pj-Pj?（只考虑非基向量情形）
问题：改变后是否影响最优基（解）、有利？
方法：
只需计算
，则有利
,则不利
管理运筹学
§5整数规划
IntegerProgramming（简称IP）
一、整数规划的一般模型
LP:maxz=CX
AX=b
X'O
IP:maxz=CX
AX=b
X20
X为整数
管理运筹学
整数规划的解法：分枝定界法或割平面法
基本思想是把一个整数规划问题化为一系列的线性规划问题来求解
整数规划的分类：
纯整数规划：所有变量都限制为整数
混合整数规划：仅部分变量限制为整数
0-1整数规划：变量的取值仅限于0或1
管理运筹学
［例］人力资源分配的问题
某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下:
设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该
公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务
人员？
30
2：00——6：00
6
20
22：00——2：00
5
50
18：00——22：00
4
60
14：00------18：00
3
70
10：00——14：00
2
60
6：00——10：00
1
所需人数
时间
班次
管理运筹学
解：设xi表示第i班次时开始上班的司机和乘务人员数,于是LP模型为:
xl+x6N60
xl+x2270
x2+x3260
x3+x4250
x4+x5220
x5+x6230
xl,x2,x3,x4,x5,x620且为整数
minz=xl+x2+x3+x4+x5+x6
最优解：X*=(60,10,50,0,30,0),Z*=150
管理运筹学
二、0-1整数规划
投资场所的选址问题
指派问题
背包问题
消防队问题
管理运筹学
1.投资场所的选址问题
某城市拟在东、西、南三区设立商业网点，备选位置有ArA7共7个,
如果选Ai,估计投资为bi元，利润为ci元，要求总投资不超过B元，规定
东区：AkA2、A3中至多选2个
西区：A4、A5中至少选一个
南区：A6、A7中至少选一个
问如何设点使总利润最大？
1,Ai被选中
0,Ai没被选中
解:令
xi=
maxz=
xi=0或1,i=l,…,7
EbixiWB
i=l
7
xl+x2+x3W2
x4+x521
x6+x721
s.t.
管理运筹学
课堂练习1:
某钻井队要从srsio共10个井位中确定五个钻井探油，如果选Si,
估计钻探费用为Ci元，并且井位选择上要满足下列条件：
(1)或选择S1和S7,或选择S8;
(2)选择了S3或S4就不能选择S5,反过来也一样；
(3)在S5,S6,S7,S8中最多只能选两个。
问如何选择井位使总费用最小？
管理运筹学
课堂练习1：某钻井队要从SrSlO共10个井位中确定五个钻井探油，
如果选Si,估计钻探费用为ci元，并且井位选择上要满足下列条件：
(1)或选择S1和S7,或选择S8
(2)选择了S3或S4就不能选择S5,反过来也一样
(3)在S5,S6,S7,S8中最多只能选两个
问如何选择井位使总费用最小？
1,Si被选中
0,Si没被选中
解：令
xi=
minz=
s.t.
或1,i=l,•••,10
管理运筹学
某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上
场参赛，要求：
(1)中锋只有1人上场
(2)后卫至少有一人上场
（3）只有2号上场，6号才上场
要求平均身高最高，应如何选拔队员？
课堂练习2:
管理运筹学
1,队员i被选中
0,队员i没被选中
解:令
xi=
maxz=
或1,i=l,…，8
s.t.
某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上
场参赛，要求：
（1）中锋只有1人上场
（2）后卫至少有一人上场
（3）只有2号上场，6号才上场
要求平均身高最高，应如何选拔队员？
管理运筹学
2.指派问题
例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记
作任务E、J、G、R,现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同
语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时
间最少？
问题描述：n项任务可由n个人完成，由于专长不同，各人完成各任务的时
间也不同，求最优安排。
要求：每人只能完成一项任务，每项任务只能由一人完成。
管理运筹学
xll+X12+xl3+xl4=1（甲只能干一项工作）
x21+x22+x23+x24=1（乙只能干一项工作）
x31+x32+x33+x34=1（丙只能干一项工作）
x41+x42+x43+x44=1（丁只能干一项工作）
xl1+x21+x31+x41=1（E任务只能一人干）
xl2+x22+x32+x42=1（J任务只能一人干）
xl3+x23+x33+x43=1（G任务只能一人干）
xl4+x24+x34+x44=1（R任务只能一人干）
xij=0或1,i,j=1,2,3,4
minz=2xl1+15x12+13x13+4x14+10x21+4x22+14x23+15x24
+9x31+14x32+16x33+13x34+7x41+8x42+11x43+9x44
1,指派第i人去完成第j项任务
0,不指派第i人去完成第j项任务
解:令
xij=
管理运筹学
课堂练习：P57例2.23
例：甲、乙、丙、丁是四名游泳运动员，他们各种姿势的100m游泳成绩如
表。为组成一个4X100m混合泳接力队，怎样选派运动员，方使接力队的游泳成
绩最好？
57.0
60.8
69.4
74.0
T
59.1
77.8
84.3
67.6
丙
52.8
57.0
66.2
65.8
乙
58.4
66.6
86.8
75.5
甲
自由泳
蝶泳
蛙泳
仰泳
运动员
管理运筹学
3.背包问题
问题描述
已知：一个背包最大容量为b公斤；有m件物品供选择，每件物品重ai公
斤,价值为ci(i=l,•••,m)o
问题：携带哪些物品可使总价值最大？
一般模型
s.t.
1,物品i被选中
0,物品i没被选中
xi=
管理运筹学
例：一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能带
115kg的物品，现有5件物品，分别重54、35、57、46、19kg,其价值依次为7、
5、9、6、3o问携带哪些物品可使总价值最大？
解：
模型为：
s.t.
管理运筹学
4.消防队问题
某城市的消防总部将全市划分为11个防火区，设有4个消防救火
站。下图①〜④表示消防站，「11表示防火区域，图中连线表示各地区由哪个消
防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如
果可以，应关闭哪个消防站？
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
管理运筹学
1,保留第i个消防队
0,撤消第i个消防队
解:令
x
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《丰碑》教案-2026-2027学年湘美版（新教材）小学美术五年级上册
- 3.2《团团圆圆过中秋 秋天里还有什么节日》教案设计 2026秋新道德与法治二年级上册
- 2025-2026年天津市人教版小学英语三年级上册第10单元测试卷
- 2026年天津市人教版初中语文上册第3单元阅读理解专项训练习题
- 2025-2026年湘教版九年级化学下册第9章化学实验测试卷
- 变压器安装检查记录
- 2023年7月国家开放大学中文专科《中国古代文化常识》期末纸质考试真题试题及答案
- 摩根大通-超盈国际控股(2111.HK)：销售额势头仍然稳健汇率因素制约了近期利润增长维持“增持”评级-20260909
- 2027届湖北省汉川二中物理高二第一学期期末复习检测试题含解析
- 2027届安徽省阜阳市高一物理第一学期期中复习检测模拟试题含解析
- TCAICI39-2022《通信光缆附挂供电杆路技术规范》
- 肿瘤学概论试题
- 2025年云上贵州大数据（集团）有限公司招聘笔试参考题库含答案解析
- 电路中电位的概念及计算(电工基础课件)
- 医院长期照护管理制度
- 《Python语言》电子教学课件
- 《翰墨之情》课件 2024-2025学年苏少版初中美术七年级上册
- DZ∕T 0399-2022 矿山资源储量管理规范（正式版）
- 劳动创造美好生活-新时代劳动教育教程（中职劳动教育）全套教学课件
- 明挖法施工教学课件
- 幼儿园中班下学期语言绘本-沙滩上
评论
0/150
提交评论