线性规划模型目标函数.ppt

线性规划
线性规划内容
一、线性规划模型
二、线性规划模型的标准形式
三、用matlab解线性规划
线性规划所解决的问题具有以下共同的特征:
2. 存在一定的限制条件(即约束条件),这些限
制条件是关于未知数的一组线性等式或线性不等
式来表示。
1. 每一个问题都用一组未知数(x1 ,x2 ,…,xn )表示某一方案;这些未知数的一组定值就代表一个具体方案。由于实际问题的要求,通常这些未知数取值是非负的。
3. 有一个目标要求,称为目标函数。目标函数可
表示为一组未知数的线性函数。根据问题的需要,
需求目标函数实现最大化或最小化。
一、线性规划模型
一般的线性规划问题的数学模型:
目标函数( 线性函数):
Min(max)z = c1x1 + c2x2 + …+ cnxn
约束条件(.):
a11x1+a12x2+…+a1nxn(≥)b1
a21x1+a22x2+…+a2nxn (≥) b2
.
.
.
am1x1+am2x2 +…+amnxn (≥) bm

x1 ,x2 ,…,xn ≥0

式中( )可以是关系符号:> ,<, =, ≥,≤中的任意一个(线性等式或线性不等式)。
一、线性规划模型
线性规划模型的求解:
图解法
单纯形法
matlab软件求解。
以下介绍几种常见的线性规划问题。
问题一:任务分配问题:某车间有甲、乙两台车床,,三种工件的数量分别为400、600和500,,才能既满足加工工件的要求,又使加工费用最低?
引例1
解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3,在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,
可建立以下线性规划模型:
目标函数:
约束条件:
问题二:,:速度25件/小时,正确率98%,计时工资4元/小时;二级检验员的标准为:速度15件/小时,正确率95%,计时工资3元/,,该工厂应聘一级、二级检验员各几名?
解设需要一级和二级检验员的人数分别为x1、x2人,
则应付检验员的工资为:
因检验员错检而造成的损失为:
引例2
故目标函数为:
约束条件为:
线性规划模型
目标函数:

约束条件:
注:本问题应还有一个约束条件:x1、,求得其最优解刚好是整数:x1=9,x2=0,,将其取整后不一定是相应整数规划的最优解,这样的整数规划应用专门的方法求解.