当前位置:文档之家› 线性规划的标准型和基本概念

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


1
201
0
1
0
0
2.1
0
022
1
1
3
0
1.5
3
120
3
1
0
4
料头(米) 0 0.1 0.2 0.3 0.8 0.9 1.1
1.4
设xj表示用第j种下料方案下料的原料根数,j=1,2…8, minZ=x1 +x2 +x3 +x4 +x5 +x6 +x7 +x8
数学模型 s.t.
x1 2x2
x4
x6
• 例2 靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天 500万m3,在两个工厂之间有一条流量为200万m3的支流。两化工厂每 天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工 厂排出的工业污水流到第二化工厂以前,有20%可以自然净化。环保 要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的 成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的 条件下,每厂各应处理多少工业污水,使这两个工厂处理工业污水 的费用最小
工厂1
工厂2
500万m3
200万m3
5
决污策水变的量数:量x1(、万xm2—3)。—分别代表工厂1和工厂2处理
则目标函数:min z=1000x1+800x2 约束条件:
第一段河流(工厂1——工厂2之间):
(2-x1)/500 ≤0.2%
第二段河流:[ 0.8(2-x1) +(1.4-x2)]/700≤0.2%
例4,利用例1说明图解法的主要步骤,
例1的数学模型为
maxZ 5x1 2x2
30x1 2 0x2 160
s.t.
5x1 x1
x2 15 4
x1 0, x2 0
x2 5x1+x2=15
10 C
x1=4
5 5x1+2x2=5
B( 2, 5)
maxZ 5x1 2x2
30x1 2 0x2 160
线性规划的标准型和基本概念
线性规划问题及其数学模型 线性规划的图解法 线性规划的标准形式 标准型线性规划的解的概念 线性规划的基本理论
1
线性规划问题及其数学模型
问题的提出:
在生产管理的经营活动中,通常需要对“有限的资源”寻求 “最佳”的利用或分配方式。 有限资源:劳动力、原材料、设备或资金等 最佳:有一个标准或目标,使利润达到最大或成本达到最小。
圆钢(米) Ⅰ
ⅡⅢⅣ Ⅴ Ⅵ


2.9
1
201
0
1
0
0
2.1
0
022
1
1
3
0
1.5
3
120
3
1
0
4
料头(米) 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4
问题归纳为如何混合使用这8种不同的下料方案,来制造100套 钢架,且要使剩余的料头总长为最短。
圆钢(米) Ⅰ
ⅡⅢⅣ Ⅴ Ⅵ


2.9
5x1 x2 15
x1
4
x1 0, x2 0
Z=
Z x1
,Z x 2
=(5,2)
▽Z
30x1+20x2=160
O1 A5
10
15
x1
线性规划图解法的基本步骤:
(1)建立以x1,x2为坐标轴的直角坐标系,画出线性规划 问题的可行域,
(2)求目标函数 Z=C1x1+C2x2 的梯度▽Z =(c1,c2), (3)任取等值线 C1x1+C2x2=Z0, 沿梯度▽Z正方向平移,
100
2x3 2x4 x5 x6 3x7 100
3x1 x2 2x3
3x5 x6 4x8 100
x j 0,j 1,28 且, 为整数
➢ 这是一个下料问题,是在生产任务确定的条件下,合理的组织生产, 使所消耗的资源数最少的数学规划问题。 ➢ 满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最 小值。
线性规划的一般数学模型
线性规划模型的特征: (1)用一组决策变量x1,x2,…xn表示某一方案,且在一般情况下,
变量的取值是非负的。 (2)有一个目标函数,这个目标函数可表示为这组变量的线性函数。 (3)存在若干个约束条件,约束条件用决策变量的线性等式或线
性不等式来表达。 (4)要求目标函数实现极大化(max)或极小化(min)。维生素(公斤) 设来自(台班)每吨产品的消耗


30
20
5
1
每周资源总量
160 15
已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据 市场需求调查的结果,甲药品每周的产量不应超过4吨。问该厂应如何安 排两种药品的产量才能使每周获得的利润最大?
维生素(公斤) 设备(台班) 单位利润(万元)
有限资源的合理配置有两类问题 如何合理的使用有限的资源,使生产经营的效益达到最大; 在生产或经营的任务确定的条件下,合理的组织生产,安排经 营活动,使所消耗的资源数最少。
例1,某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生 素。生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每 周可提供的资源总量如下表所示:
每吨产品的消耗


30
20
5
1
5

每周资源总量
160 15
定义x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数。
数学模型为
maxZ=5x1 +2x 2
s.t. (subject to) (such that)
30x1 20x2 160
5x1 x2 15
x1
4
x1 0, x2 0
a m2x2
amn xn
(
,
)b m
x1,x2 ,xn 0
通常称 x1,x2 ,为L决, x策n变量, a11,a12 ,L , a m为n 消耗系数,
c为1,c价2 ,值L系, c数n , b1,b2 ,L ,为b资m 源限制系数。
线性规划的图解法
适用于求解两个变量的线性规划问题
图解法的基本步骤
➢ 满足上述4个特征的规划问题称为线性规划问题
线性规划的模型的一般形式:
目标函数
max(min)Z=c1x1+c2x2 +L L +cn xn
a11x1 a12x2 a1n xn ( , )b1
满足约束条件
a21x1 a22x2 a2n xn ( , )b2
a m1x1
此外有:
x1≤2; x2≤1.4
化简有:
min z=1000x1+800x2
x1
≥1
0.8x1 + x2 ≥1.6
x1 ≤2
x2≤1.4
x1、x2≥0 称之为上述问题的数学模型。
6
例3,某铁器加工厂要制作100套钢架,每套要用长为2.9米,2.1米 和1.5米的圆钢各一根。已知原料长为7.4米,问应如何下料,可使材 料最省? ➢ 分析:在长度确定的原料上截取三种不同规格的圆钢,可以归纳 出8种不同的下料方案:
相关主题