文档介绍：第一章线性规划 (Linear Programming, LP)
概述
线性规划问题的提出最早是1939年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。
1947年,美国学者丹西格()提出了线性规划问题的单纯形方法。
线性规划理论最为成熟、应用最为广泛
第一节线性规划问题及其数学模型
一、问题提出
例1(生产计划问题)某企业利用A、B、C三种资源,在计划期内生产甲、乙两种产品,已知生产单位产品资源的消耗、单位产品利润等数据如下表,问如何安排生产计划使企业利润最大?
产品
资源
甲
乙
资源限制
A
B
C
1
2
0
1
1
1
300kg
400kg
250kg
单位产品利润(元/件)
50
100
决策变量:x1、x2——分别代表甲、乙两种产品的生产数量。
目标函数:max z=50x1+100x2
约束条件: x1 + x2≤300
2x1 + x2≤400
x2≤250
即有:
max z=50x1+100x2
x1 + x2≤300
2x1 + x2≤400
x2≤250
x1、x2≥0
称之为上述问题的数学模型。
例2 靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天500万m3,在两个工厂之间有一条流量为200万m3的支流。。从第一化工厂排出的工业污水流到第二化工厂以前,有20%可以自然净化。%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下,每厂各应处理多少工业污水,使这两个工厂处理工业污水的费用最小.
工厂1
工厂2
200万m3
500万m3
决策变量:x1、x2——分别代表工厂1和工厂2处理污水的数量(万m3)。
则目标函数:min z=1000x1+800x2
约束条件:
第一段河流(工厂1——工厂2之间):
(2-x1)/500 ≤%
第二段河流:[ (2-x1) +(-x2)]/700≤%
此外有: x1≤2; x2≤
化简有:
min z=1000x1+800x2
x1 ≥1
+ x2 ≥
x1 ≤2
x2≤
x1、x2≥0
称之为上述问题的数学模型。
三、图解法举例
例1 max Z=50x1+100x2
x1 + x2≤300
2x1 + x2≤400
x2≤250
x1、x2≥0
x2
x1
z* =27500
z1=50x1+100x2=0
B
O
A
C
D
z2=14000
该问题有唯一最优解
x1=50;x2=250
x1 + x2≤300
2x1 + x2≤400
x2≤250
例2 max Z=50x1+50x2
x1 + x2≤300
2x1 + x2≤400
x2≤250
x1、x2≥0
x2
x1
z1=50x1+50x2=0
B点和C点所代表的坐标同时为最优解,即该问题有无穷多最优解
B
O
A
C
D
x1 + x2≤300
2x1 + x2≤400
x2≤250
max Z=50x1+100x2
z* =27500
z2=15000