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

线性规划的标准型和基本概念
口线性规划问题及其数学模型
口线性规划的图解法
口线性规划的标准形式
口标准型线性规划的解的概念
口线性规划的基本理论
口线性规划问题及其数学模型
■问题的提出:
在生产管理的经营活动中,通常需要对“有限的资源”寻求
最佳”的利用或分配方式
有限资源:劳动力、原材料、设备或资金等
·最佳:有一个标准或目标,使利润达到最大或成本达到最
有限资源的合理配置有两类问题
如何合理的使用有限的资源,使生产经营的效益达到最大
在生产或经营的任务确定的条件下,合理的组织生产,安排经
营活动,使所消耗的资源数最少
例1,某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生■
素。生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每
周可提供的资源总量如下表所示
每吨产品的消耗
每周资源总量
维生素(公斤)
160
设备(台班)
已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据
市场需求调查的结果,甲药品每周的产量不应超过4吨。问该厂应如何
安排两种药品的产量才能使每周获得的利润最大
每吨产品的消耗
每周资源总量
维生素(公斤)
设备(台班)
单位利润(万元)
2
定义x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数
数学模型为
maxZ=5X,+2x2
t
30x,+20X,≤160
subject to)
5X,+X<15
(such that)
X1≤4
X,≥0,X、≥0
例2靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天
500万m3,在两个工厂之间有一条流量为200万m3的支流。两化工厂每
。从第一化工
厂排出的工业污水流到第二化工厂以前,有20%可以自然净化。环保
%。两化工厂处理工业污水的
成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的
条件下,每厂各应处理多少工业污水,使这两个工厂处理工业污水
的费用最小
工厂1
工厂2
500万m3
200万m3
决策变量:x1、x2分别代表工厂1和工厂2处理
污水的数量(万m)
则目标函数:minz=10001+800x2
约束条件:
第一段河流(工厂1—工厂2之间)
(2-x1)
第二段河流:[(2-x)+(-x2)%
此外有:
x12;x2≤
化简有
minz=1000x1+800x2
+
称之为上述问题的数学模型。
例3,某铁器加工厂要制作100套钢架,,
。,问应如何下料,可使
材料最省
分析:在长度确定的原料上截取三种不同规格的圆钢,可以归纳
出8种不同的下料方案:
圆钢(米)IⅡⅢⅣvⅥⅦⅦ
111
004
料头(米)

问题归纳为如何混合使用这8种不同的下料方案,来制造100
套钢架,且要使剩余的料头总长为最短
圆钢(米)
ⅡmⅳvⅥⅦⅦ

022
2
030
料头(米)

设x表示用第j种下料方案下料的原料根数,j=1,2…8,
min/=x,+x,+x3+X4+X+x6+x,+X
数学模型
X,+2X,+
≥100
2x3+2x4+X5+x6+3x,≥100
3x,+X,+2x,+
3x。+X。+4
100
x;≥0,j=1,2…8且为整数
这是一个下料问题,是在生产任务确定的条件下,合理的组织生产
使所消耗的资源数最少的数学规划问题。
满足一组约束条件的同时,寻求变量x1至x2的值,使目标函数取得最
小值
■线性规划的一般数学模型
线性规划模型的特征:
(1)用一组决策变量x1,x2,…x表示某一方案,且在一般情况下,
变量的取值是非负的。
(2)有一个目标函数,这个目标函数可表示为这组变量的线性函数
(3)存在若干个约束条件,约束条件用决策变量的线性等式或线
性不等式来表达。
(4)要求目标函数实现极大化(max)或极小化(min)
满足上述4个特征的规划问题称为线性规划问题
线性规划的模型的一般形式
目标函数
max(min)=,X,+C,x2+,.+c,X
a1Xx1+a1X2+……+a1Xn≤(=,≥)b1
满足约束条件a21x1+a2X2+……+a2xn≤(=,≥