线性规划的标准型和基本概念.ppt

线性规划的标准型和基本概念
线性规划问题及其数学模型
线性规划的图解法
线性规划的标准形式
标准型线性规划的解的概念
线性规划的基本理论
1
问题的提出:
在生产管理的经营活动中,通常需要对“有限的资源”寻求“最佳”的利用或分配方式。
有限资源:劳动力、原材料、设备或资金等
最佳:有一个标准或目标,使利润达到最大或成本达到最小。
有限资源的合理配置有两类问题
如何合理的使用有限的资源,使生产经营的效益达到最大;
在生产或经营的任务确定的条件下,合理的组织生产,安排经营活动,使所消耗的资源数最少。
线性规划问题及其数学模型
2
例1,某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每周可提供的资源总量如下表所示:
每吨产品的消耗
每周资源总量
甲
乙
维生素(公斤)
30
20
160
设备(台班)
5
1
15
已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果,甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大?
3
定义x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数。
数学模型为

.
(subject to)
(such that)
每吨产品的消耗
每周资源总量
甲
乙
维生素(公斤)
30
20
160
设备(台班)
5
1
15
单位利润(万元)
5
2
4
例2 靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天500万m3,在两个工厂之间有一条流量为200万m3的支流。。从第一化工厂排出的工业污水流到第二化工厂以前,有20%可以自然净化。%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下,每厂各应处理多少工业污水,使这两个工厂处理工业污水的费用最小
工厂1
工厂2
200万m3
500万m3
5
决策变量: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
称之为上述问题的数学模型。
6
例3,某铁器加工厂要制作100套钢架,,。,问应如何下料,可使材料最省?
分析:在长度确定的原料上截取三种不同规格的圆钢,可以归纳出8种不同的下料方案:
圆钢(米)
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
Ⅵ
Ⅶ
Ⅶ

1
2
0
1
0
1
0
0

0
0
2
2
1
1
3
0

3
1
2
0
3
1
0
4
料头(米)
0







问题归纳为如何混合使用这8种不同的下料方案,来制造100套钢架,且要使剩余的料头总长为最短。
7
设xj表示用第j种下料方案下料的原料根数,j=1,2…8,

数学模型

.
这是一个下料问题,是在生产任务确定的条件下,合理的组织生产,
使所消耗的资源数最少的数学规划问题。
满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最
小值。
圆钢(米)
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
Ⅵ
Ⅶ
Ⅶ

1
2
0
1
0
1
0
0

0
0
2
2
1
1
3
0

3
1
2
0
3
1
0
4
料头(米)
0







且为整数
8
线性规划的一般数学模型
线性规划模型的特征:
(1)用一组决策变量x1,x2,…xn表示某一方案,且在一般情况下,
变量的取值是非负的。
(2)有一个目标函数,这个目标函数可表示为这组变量的线性函数。
(3)存在若干个约束条件,约束条件用决策变量的线性等式或线
性不等式来表达。
(4)要求目标函数实现极大化(max)或极小化(min)。