运筹学课件第3章

《运筹学课件第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章线性规划3.1线性规划模型例1某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数、每件产品可以获得的利润以及三种设备可利用的时数如下表所示。产品甲产品乙设备能力/h设备A3265设备B2140设备C0375利润/（元/件）15002500问题：工厂应如何安排生产可获得最大的总利润？解设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1

2、+2x2≤65。对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x2≤40。3.1线性规划模型3.1线性规划模型对于设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2≤75；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2。综合上述讨论，在加工时间以及利润与产品产量呈线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下线性规划模型：3.1线

3、性规划模型目标函数Maxz=1500x1+2500x2约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥03.1线性规划模型这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于…”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。一般形式目标函数：Max(Min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤(

4、=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2...am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥03.1线性规划模型标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥03.1线性规划模型可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式

5、的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。3.1线性规划模型1.极小化目标函数的问题设目标函数为Minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即Minf＝-Maxz3.1线性规划模型2.约束条件不是等式的问题设约束条件为ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量s，使它等于约束右边与左边之差，即s=bi

6、–(ai1x1+ai2x2+…+ainxn)显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+s=bi3.1线性规划模型当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地令s=(ai1x1+ai2x2+…+ainxn)-bi显然，s也具有非负约束，即s≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-s=bi3.1线性规划模型为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束

7、引进不同的松弛变量。3.1线性规划模型例2将以下线性规划问题转化为标准形式Minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x3≤15.74.1x1+3.3x3≥8.9x1+x2+x3=38x1,x2,x3≥03.1线性规划模型解首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x3其次考虑约束，有2个不等式约束，引进松弛变量x4，x5≥0。于是，我们可以得到以下标准形式的线性规划问题：Maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x

8、3+x4=15.74.1x1+3.3x3-x5=8.9x1+x2+x3=38x1,x2,x3,x4,x5≥03.1线性规划模型3.变量无符号限制的问题在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj′-xj″其中xj′≥0，xj″≥0