文档介绍：第三章
线性规划
线性规划模型
例:某工厂拥有A、B、C 三种类型的设备,生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:
产品甲
产品乙
设备能力(h)
设备A
3
2
65
设备B
2
1
40
设备C
0
3
75
利润(元/件)
1500
2500
问题:工厂应如何安排生产可获得最大的总利润?
解:设变量xi为第i种(甲、乙)产品的生产件数(i=1,2)。根据题意,我们知道两种产品的生产受到设备能力(机时数)的限制。对设备A,两种产品生产所占用的机时数不能超过65,于是我们可以得到不等式:3 x1 + 2 x2 ≤ 65;
对设备B,两种产品生产所占用的机时数不能超过40,于是我们可以得到不等式:2 x1 + x2 ≤ 40;
线性规划模型
对设备C,两种产品生产所占用的机时数不能超过75,于是我们可以得到不等式:3x2 ≤75 ;另外,产品数不可能为负,即 x1 ,x2 ≥0。同时,我们有一个追求目标,即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润:z=1500x1+2500x2 。综合上述讨论,在加工时间以及利润与产品产量成线性关系的假设下,把目标函数和约束条件放在一起,可以建立如下的线性规划模型:
线性规划模型
目标函数 Max z =1500x1+2500x2 
约束条件 . 3x1+2x2≤ 65
2x1+x2≤ 40
3x2≤ 75
x1 ,x2 ≥0
线性规划模型
这是一个典型的利润最大化的生产计划问题。其中,“Max”是英文单词“Maximize”的缩写,含义为“最大化”;“.”是“subject to”的缩写,表示“满足于……”。因此,上述模型的含义是:在给定条件限制下,求使目标函数z达到最大的x1 ,x2 的取值。
线性规划模型
一般形式
目标函数:
Max(Min)z = c1x1 + c2x2 + …+ cnxn
约束条件:
a11x1+a12x2+…+a1nxn≤( =, ≥)b1
a21x1+a22x2+…+a2nxn≤( =, ≥)b2
.
.
.
am1x1+am2x2 +…+amnxn≤( =, ≥)bm
x1 ,x2 ,…,xn ≥ 0
线性规划模型
标准形式
目标函数:
Max z = c1x1 + c2x2 + …+ cnxn
约束条件:
a11x1 + a12x2 + …+ a1nxn = b1
a21x1 + a22x2 + …+ a2nxn = b2
.
.
.
am1x1 + am2x2 + …+ amnxn = bm
x1 ,x2 ,…,xn ≥ 0
线性规划模型
可以看出,线性规划的标准形式有如下四个特点:目标最大化、约束为等式、决策变量均非负、右端项非负。
对于各种非标准形式的线性规划问题,我们总可以通过以下变换,将其转化为标准形式:
线性规划模型
:
设目标函数为
Min f = c1x1 + c2x2 + …+ cnxn
则可以令z = -f ,该极小化问题与下面的极大化问题有相同的最优解,即
Max z = -c1x1 - c2x2 - …- cnxn
但必须注意,尽管以上两个问题的最优解相同,但他们最优解的目标函数值却相差一个符号,即
Min f = - Max z
线性规划模型