第二章 线性规划与单纯形法.ppt

第二章线性规划与单纯形法
LP(linear programming)的基本概念
LP是在有限资源的条件下,合理分配和利用资源,以期取得最佳的经济效益的优化方法。
LP有一组有待决策的变量,
一个线性的目标函数,
一组线性的约束条件。
OR1
1
LP的数学模型 例题1—生产计划问题
某厂生产两种产品,需要三种资源,已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表:
产品A
产品B
资源限量
劳动力
设备
原材料
9
4
3
4
5
10
360
200
300
利润元/kg
70
120
OR1
2
例题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
3
例题2——配方问题
养海狸鼠饲料中营养要求:VA每天至少700克,VB每天至少30克,VC每天刚好200克。现有五种饲料,搭配使用,饲料成分如下表:
饲料
Va
Vb
Vc
价格元/KG
I
II
III
IV
V
3
2
1
6
18
1


2


1

2

2
7
4
9
5
营养要求
700
30
200
OR1
4
例题2建模
设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg……
目标函数:最省钱 minZ=2x1+7x2+4x3+9x4+5x5
约束条件:3x2+2x2+x3+6x4+18x5 ≥700
营养要求: x1+++2x4+ ≥30
+x2++2x4+ =200
用量要求: x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40
非负性要求:x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
OR1
5
例题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
6
例题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
7
归纳:线性规划的一般模式
目标函数:max(min)Z=c1x1+c2x2+c3x3+…+cnxn
约束条件:a11x1+a12x2+a13x3+…+a1nxn ≤(= ≥)b1
a21x1+a22x2+a23x3+…+a2nxn ≤(= ≥)b2
…………
am1x1+am2x2+am3x3+…+amnxn ≤(= ≥)bn
非负性约束:x1 ≥0,x2 ≥0,…,xn ≥0
OR1
8

由中学知识可知:y=ax+b是一条直线,同理:Z=70x1+120x2→x2=70/120x1-Z/120也是一条直线,以Z为参数的一族等值线。
9x1+4x2 ≤360 → x1 ≤360/9-4/9x2
是直线 x1=360/9-4/9x2 下方的半平面。所有半平面的交集称之为可行域,可行域内的任意一点,就是满足所有约束条件的解,称之为可行解。
OR1
9
例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
10