13
武汉理工大学
能源与动力工程学院
数学模型
目标函数：min(或max)z=c1x1+c2x2+…..+cnxn 约束条件： a11x1+a12x2+…+a1nxn≤(=, ≥)b1 a21x1+a22x2+…+a2nxn≤(=, ≥)b2 ………………………………… am1x1+am2x2+…+amnxn≤(=, ≥)bm
21
x1 x2 x3 1 14 7 x1 x2 x4 1 7 12 x1 x2 x5 8 x1 , x2 .....x5 0
武汉理工大学
能源与动力工程学院
线性规划数学模型的一般形式：
满足 minf(x)=c1x1+c2x2+……+cnxn
a11x1+a12x2+…+a1nxn =b1 a21x1+a22x2+…+a2nxn=b2 ………………………………… am1x1+am2x2+…+amnxn=bm xj≥0 j=1,2,…,n m,n正整数。m为独立的约束方程个数，n为变量个数 n＞m bi≥0 (i=1,2,…,m)
11
武汉理工大学
能源与动力工程学院
该配料问题的最优化数学模型为: 目标函数: 飞机汽油１的总产量越多越好 maxz= x1+x2+x3+x4 约束函数(限制条件): X5+x6+x7+x8≥250000 X1+x5≤380000 X2+x6≤265200 2.85x1-1.42x2+4.27x3-18.49x4≥0 2.85x5-1.42x6+4.27x7-18.49x8≥0 16.5x1+2.0x2-4.0x3+17.0x4≥0 7.5x5-7.0x6-13.0x7+8.0x8≥0 xj≥0 j=1,2,…,8
x1+x2=10
武汉理工大学
能源与动力工程学院
求x＝（x1
§1.3线性规划问题的标准型 x2 )T
使f(x)=-5x1-10x2
并满足：
min 设计变量： x1 ， x2
松弛变量： x3 ， x4 ， x5 松弛变量:把不等式约束变成等式约束 所增加的变量称为松弛变量。 剩余变量:若不等式约束为“≥”形式, 则在改写等式约束时,所增加变量前面 的符号应为负,这时所增加的变量称为 剩余变量。 自由变量:若约束条件中有某个变量无 ' ' ' ' 非负限制,令 xk xk xk' 其中xk , xk' 0
2x1+3x2100
4x1+2x2 120 x1、x20 求出x1、x2的值
（原材料限制）
（工时限制） （变量非限制）
要求：总产值最大，maxf(x1、x2)= 6x1+4x2 maxf(x1、x2)
3
两个变量的线性规划
武汉理工大学
能源与动力工程学院
例2 分配任务的最优化问题
现有四种不同规格的产品要分配在四台不同性能的机床上 同时加工，由于产品的规格不同和机床的性能各异，因此每 一件产品在不同机床上加工的工时定额是不同的，其工时定 额如表，问应如何分配加工任务，使总的加工时间最少？
X2+x6≤265200 (标准汽油2号的库存量限制)
X3+x7≤408100 (标准汽油3号的库存量限制) X4+x8≤130000 (标准汽油4号的库存量限制) xj≥0 j=1,2,…,8
8
(非负限制)
武汉理工大学
能源与动力工程学院
2、蒸汽压和辛烷值的限制条件 分压定律：设有一混合气体，由n种气体组成。令混合气体的压力 为p，所站总容积为v；各组分的压力分别为p1,p2….pn,各组分所 n 占容积分别为V1，V2，…..Vn,则“ pV piVi ”， 利用分压定律建立蒸汽压力的限制条件： 根据表1-2，飞机汽油1的蒸汽压力应为：
Ｂ：常数项列阵
Ｘ≥０：表示向量Ｘ中的每一个分量都大于零
23
武汉理工大学
能源与动力工程学院
§1.4线性规划问题的解 1.可行解：满足非负约束条件的约束方程的任何一个解 都是可行解。在可行区中的任何一个解都是可行解。
i 1
7.11102 x1 11.38102 x2 5.69102 x3 28.45102 x4 x1 x2 x3 x4
根据表1-3，蒸汽压力不大于9.96*10-2
7.11x1 11.38x2 5.69x3 28.45x4 9.96 x1 x2 x3 x4
工时 机床 产品
1 7 20 21 48
2 50 13 16 27
4
3 16 40 25 43
4 1 35 42 16
1 2 3 4
武汉理工大学
能源与动力工程学院
解:今要求四种产品同时在四台不同的机床上进行加工，因此 每种产品只能而且必须分配在一台机床上，同时每台机床只 能而且必须加工一种产品，所以这个问题属于任务分配问题 (表示产品j不分配在机床i上加工） 设 xij= 0 1 (表示产品j分配在机床i上加工） 则限制条件为 4 xij 1, i 1,2,3,4 (第i台机床只加工一种产品)
x1, x2…xn的全部或部分非负
14
武汉理工大学
能源与动力工程学院
§1.2线性规划的图解法
一、引例 例：若有某水泥制品厂生产Ａ、Ｂ两种混合料。按照工厂的生 产能力，每小时可生产Ａ料14t或Ｂ料7t。从运输距离来讲， 每小时能运Ａ料7t或Ｂ料12t。按工厂的运输能力，不论何种 混合料，每小时只能运出物料8t。已知生产Ａ料所创造的经济 价值为5元／t，Ｂ料为10元／t。试问该厂每小时能创造的最 大经济价值为多少？这时每小时生产的Ａ、Ｂ料各为多少？ 解：设x1、x2分别为每小时生产的A、B料数量， 故设计变量为X=(x1、x2)T 目标函数：f(x)= 5x1+10x2 约束条件： ??
x2 60
约束条件:
2x1+x2≤60
30
2x1+x2=60
3x1+5x2=150
3x1+5x2≤150
x1,x2≥0
18
0
30
50
x1
武汉理工大学
能源与动力工程学院
解的几种特殊情况 2.可行集无界 x
2
目标函数: maxz=f(x1,x2)=2x1-x2
1
x1-3x2= -3
约束条件:
x1+x2≥1
X3+x7≤408100
X4+x8≤130000
12
武汉理工大学
能源与动力工程学院
小
结
1)每一问题都用一组未知数(x1,x2,…,x3)表示某一方案,这组 未知数的一组定值就代表一个具体方案。一些实际问题还要求 这些未知数的全部或部分取值是非负的。
2）这些未知数需满足一定的限制条件，这些限制条件都可以 用一组线性等式或不等式来表示。 3）都有一个目标要求，并且这个目标可表示为这组未知数的 线性函数（目标函数）。 按研究的问题不同，要求目标函数实现最大或最小 线性规划问题
0 1
Z=2x1-x2
x1
x1-3x2≤-3
x1,x2≥0
19
x1+x2=1
武汉理工大学
能源与动力工程学院
解的几种特殊情况 3.可行集为空集 目标函数: maxz=f(x1,x2)=x1+3x2
x2 30
约束条件:
x1+x2≤10
2x1+x2=30
2x1+x2≥30
x1,x2≥0
20
10
0 10 15 x1
9
武汉理工大学
能源与动力工程学院
整理后得： 2.85x1-1.42x2+4.27x3-18.49x4≥0 (1号飞机汽油蒸汽压指标限制) 要求飞机汽油2的蒸汽压力与飞机汽油1的相同，则： 2.85x5-1.42x6+4.27x7-18.49x8≥0 (2号飞机汽油蒸汽压指标限制)
10
武汉理工大学
能源与动力工程学院
关于辛烷值的考虑也可采用类似分压定律
对于1号飞机汽油,有
107.5 x1 93.0 x2 87.0 x3 108.0 x4 91.0 x1 x2 x3 x4
整理后得:
16.5x1+2.0x2-4.0x3+17.0x4≥0 (1号飞机汽油辛烷值指标限制) 对于2号飞机汽油,有 7.5x5-7.0x6-13.0x7+8.0x8≥0 (2号飞机汽油辛烷值指标限制)
15
武汉理工大学
能源与动力工程学院
解：设x1、x2分别为每小时生产的A、B料数量 故设计变量为X=(x1、x2)T 目标函数：f(x)= 5x1+10x2
约束条件：
x1 x2 1 14 7 x1 x2 1 7 12 x1 x2 8 x1 , x2 0
16
武汉理工大学 x2
能源与动力工程学院
图解法（生产规划问题的几何描述）
x1 x2 1 7 12
１２
１０
８
f(x)等值线
D
E
６
f(x)=70
４
G
可行区
２
C
x1 x2 1 14 7
A
0 ２ ４ ６
x1 x2 8
B
８
17
１０
１２
x1 １４
武汉理工大学
能源与动力工程学院
解的几种特殊情况 1.无穷多个最优解 目标函数: maxz=f(x1,x2)=6x1+10x2