第一章线性规划.ppt

第一章线性规划
第一节线性规划问题及其数学模型
例1 某厂生产甲、乙、丙三种产品,主要消耗A、B、C三种原料,。
产
品
单
位
消
耗
原
料
甲
乙
丙
原料总量(kg)
A
B
C
1
5
0
4
2
2
2
3
5
4500
6300
3800
产品单价(百元)
2
4
5
要求确定甲、乙、丙的产量,使总产值最大。
解:将一个实际问题转化为线性规划模型有以下几个步骤:
:
x1=生产产品甲的数量,
x2=生产产品乙的数量,
x3=生产产品丙的数量。
:工厂的目标是使总产值最大,更具体一点,是使三种产品单价与产量的乘积的总和最大,因此目标函数可写为:
如果工厂可以随意选择生产产品甲、乙、丙的数量,他们的总产值可以随意大。而这实际上是不可能的,因为任何生产都会受到种种客观条件的限制。一个正确的模型应通过约束方程来反映这些客观条件。本例中的限制条件是对原料A、B、C的使用数量不能超过其拥有量。这三个条件可由以下方程表示:
:
:
一般情况,决策变量只取正值(非负值)
x1  0, x2  0 , x3  0
线性规划模型的三要素
:为实现优化目标需受到的限制,用
决策变量的等式或不等式表示;
:需决策的量,即待求的未知数;
:需优化的量,即欲达的目标,用决
策变量的表达式表示;
例2 某工厂熔炼一种新型不锈钢,需要用四种合金A、B、C、D为原料,经测这四种原料关于元素铬(Cr),锰(Mn)和镍(Ni)的含量(%)、单价,以及这种不锈钢所需铬(Cr),锰(Mn)和镍(Ni)的最低含量(%):
假设熔炼时重量没有损耗。
问题:要熔炼成100吨这样的不锈钢,应选用原料A、B、C、D各多少吨,能够使成本最小?
原
料
含
量
成
分
A
B
C
D
不锈钢所需各元
素的最低含量
铬(Cr)





锰(Mn)





镍(Ni)





单价(万元/吨)




解设选用原料A、B、C、D分别为x1,x2,x3,x4吨。根据题目,目标函数为:
约束条件为:
(熔炼成100吨不锈钢)
(铬的含量)
(锰的含量)
(镍的含量)
另外,各种合金原料的选用不能为负值。
问题归结为下列模型: