运筹学 第01章 线性 规划问题.ppt

文档介绍：运筹学
第一章线性规划问题
本章重点
线性规划建模
线性规划的图解法
线性规划的标准形式
单纯形法
两阶段法
大M法
线性规划的概念
对于求取变量xj(j=1,2,…,n),使之既满足线性约束条件,又使线性的目标函数取得极值的一类最优化问题称为线性规划问题
xj(j=1,2,…,n)表示解决问题的方案,称为决策变量
约束条件表示要解决的问题的限制条件,用一组决策变量的线性等式或线性不等式来表示
目标函数表示要解决的问题要求达到的目标,用决策变量的线性函数表示
线性规划建模步骤
设定决策变量
明确约束条件并用决策变量的线性等式或不等式表示
用变量的线性函数表示要达到的目标,并确定是求极小还是求极大
根据变量的物理性质确定变量是否具有非负性
注:其中最关键是设定决策变量这一步
生产计划问题(1)
某工厂用三种原料生产三种产品,已知的条件如下表所示,试制订总利润最大的日生产计划
产品所需原料数量
(公斤/ 件)
产品Q1
(件)
产品Q2
(件)
产品Q3
(件)
原料可用量
(公斤/日)
原料P1
2
3
0
1500
原料P2
0
2
4
800
原料P3
3
2
5
2000
产品的利润
(千元/ 件)
3
5
4
生产计划问题(2)
设每天生产三种产品的件数分别为x1、x2、x3
其中,max是maximize的缩写,含义为“最大化”;
to的缩写,其含义是“受限制于……”
配料问题(1)
养海狸鼠,饲料营养要求:VA每天至少700克,VB每天至少30克,VC每天刚好200克。现有五种饲料,搭配使用,饲料成分如下表。问如何购买饲料,使得花费最少?
饲料
Va(g)
Vb(g)
Vc(g)
价格(元/kg)
I(kg)
II(kg)
III(kg)
IV(kg)
V(kg)
3
2
1
6
18
1


2


1

2

2
7
4
9
5
营养要求(g)
700
30
200
配料问题(2)
设购买饲料分别为x1、x2、x3 、x4、x5 kg
目标函数为:花费最少,则有
其中,min是minimize的缩写,含义为“最小化”;
合理下料问题(1)
、、, ?
总共有以下8种切割方案,设xj分别代表采用切割方案j使用的原料数量
合理下料问题(2)
目标函数为:使裁剪后零料最少,则有