精品
运筹学LPILP
运筹学模型（2）
【七桥问题】 在哥雷斯堡（Konigsberg）有一条名叫普雷尔（Pregel）的河流从城市中 间流过，普雷尔河的中央有一大一小两座岛屿，河岸和两座岛由七座桥相互连 接，如图 3-53 所示:
A
B
C
D
图 3-53 于是在居民们每天散步的时候就产生了一项有趣的消遣活动：从 A 岸、B 岛、C 岛、D 岸这四个地方任选一处出发，走过所有七座桥，最后回到出发的地方， 而且要求每座桥只能经过一次，不得重复。
x3+3x4 +x6+3x7+x8>=100
Xj>=0且为整数 j=1,2,3,……8
运筹学模型（4）
【排班问题】
某工厂的中心调度室，每昼夜 24 小时都要有人员值班，已知每 个时间段（每 4 小时为一个时间段）所需要的值班人员如表 1.6。又 知每一调度人员在任 1 时段开始上班后，要连续工作 8 小时（包括 轮流吃饭时间）才能满足调度值班工作需要。为使参加值班的总人 数最少，试列出数学模型
x1 x1
x2 1 2x2
0
x1,2 0
图解法（5）——无可行解
min s 2 x 1 2 x 2
s
.t
.
x
1
x1
x2 x2
1 2
x1,2 0
图解法（6）—— 结论
线性规划问题的解有四种情况 1．有唯一最优解 2．有无穷多最优解 3．有可行解，但无最优解（解无界） 4．无可行解
运筹学模型（3）
【合理下料问题】 某工地要求做 100 套钢筋，每套为 3 根，它们的长度分别为
2.9 米，2.1 米和 1.5 米；原材料长为 7.4 米，为应当怎样截割钢 筋，才能使所需的原材料根数为最少？
提示1：如果只需要截2.9米的100根，如何下料？ 提示2：如果需要截2.9米和2.1米的各100根，又如何下料？
可行解 ——不可行解 可行解集（可行区域） 最优解 最优目标函数值 基本可行解 基本最优解
图解法（3）——无穷多最优解
max s x1 2 x2
x1 4
s.t.
x2 3 x1 2x2 8
x j 0( j 1.2)
图解法（4）——解无界
max s 2 x 1 2 x 2
s .t .
3
50
4
30
25
如何调运，才能使总成本最省？
第一章 线性规划
图解法 单纯型法 两阶段法 对偶规划 对偶单纯型法 灵敏度分析 目标规划
图解法（1）——唯一最优解
max s 2 x1 5 x2
x1 4
s.t.
x2 3 x1 2 x2 8
x j 0( j 1.2)
图解法（2）——基本概念
J段
时间段
需人数
1
2-----6
2
2
6-----10
5
3
10-----14
10
4
14------18
12
5
18-------22
6
6
22-------2
7
Xj-----j时段初形成得人数 j=1,2,3,4,5,6 Minf=x1+x2+x3+x4+x5+x6 X1+x6>=2 X1+x2>=5 X2+x3>=10 X3+x4>=12 X4+x5>=6 X5+x6>=7
例 1.5 将 下 列 线 性 规 划 问 题 化 为 标 准 形
m in f 2 x1 x2
3 x1 2 x2 6
s.t.
x1 7 x2 4 x1 x2 2
x j 0，j 1，2
单纯型法（一）
某工厂计划在一个生产周期内生产甲、乙两种产品， 这两种产品分别需要经过A、B两道工序加工。已知每件 产品在每道工序上加工所需的机时及生产每件产品可以获 得的利润如下表，如何安排生产，才能使总利润最大？
（ 2） 标 准 形 的 矩 阵 表 示
m ax f = c Tx
A x= b
s .t.
x
0
其中
A
（
a
）
ij m
n
c c 1 , c 2 , . . . , b b 1 , b 2 , . . . ,
x x 1 , x 2 , . . . ,
T
cn
b n T T
xn
线性规划问题的标准形式（二）
单纯型法
标准化 单纯型法
线性规划问题的标准形式(一)
1．目标函数求最大 2．约束条件取等号 3．变量为非负
(1) 标 准 形 的 代 数 表 示
m ax
n
f c j x j x j bi
j1
(i 1, 2, ..., m )
xj 0
( j 1, 2, ..., n )
甲 乙 可用机时
工序A 2
4
80
工序B 3
2
60
单位利润 60 50
单纯型法（二）
m ax f = 60x1+ 50x 2
2x1+ 4x2 80
s .t .
3
x
1
+
2
x
2
60
x
1
0, x2
0
x2
（0，20）C
B（10，15）
（0，0）O
x1
A （20，0）
单纯型法（三）
x2
（0，20）C
B（10，15）
max f = 60x1+50x2
（0，0）O
2
x
1
+
4
x
2
x3
80
s.t. 3x1+ 2x 2
x4 60
x
1
0,
j
1，2，3，4
A （20，0）
单纯型法（四）
max f = 60x1+50x2
2
x
1
+
4
x
2
x3
80
s.t. 3x1+ 2x 2
x4 60
x
1
0,
j
1，2，3，4
有八种方法截取
2.9m 2.1m 1.5m
1 2 34 56 7 8 2 1 11 00 0 0 0 2 10 32 1 0 0 0 13 01 3 4 x1 x2 x3 x4 x5 x6 x7 x8
Mf=x1+x2+x3+x4+x5+x6+x7+x8
2x1+x2+x3+x4>=100
2x2+3x3 +3x5+2x6+x7>=100
运筹学模型（5）
【运输问题】
现有两个仓库（发点）运送库存原棉来满足三个纺织厂（收点）的需要。三个 纺织厂所需数量和两个仓库现有库存量，以及每吨原棉从各个仓库运送到各个纺 织厂所需的运费见表 1.3
表 1.3 运输费
仓库 1# 仓库 2# 需求量（吨）
工厂 1*
2 2 40
工厂 2*
1 2 15
工厂 3* 库存量（吨）
max f 120010x2 20x4
s.t.
x1
8 3
x2
2 3
x2
x3
2 3
x4
1 3
x4
40 20
xj 0, j 1,2,3,4
maxf 150015x1 25x4