西电工程优化课件第3章

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

1、第三章线性规划概述线性规划是最简单、理论最为成熟、应用最为广泛的一种数学规划方法。线性规划问题的提出：最早是1939年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。1947年，美国学者丹西格（G.B.Dantzig）提出了线性规划问题的单纯形方法，使线性规划的算法趋于成熟。3.1线性规划模型一.问题的提出例1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示，问：工厂应如何安排生产可获得最

2、大的总利润？产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500决策变量：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。约束条件：根据题意，两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是可以得到不等式：3x1+2x2≤65；对设备B，两种产品生产所占用的机时数不能超过40，于是可以得到不等式：2x1+x2≤40；对设备C，两种产品生产所占用的机时数不能超过75，于是可以得到不等式：3x2≤75；产品数不可能为负，即

3、x1,x2≥0。目标函数：即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2。综上所述，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：目标函数Maxz=1500x1+2500x2约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示

4、“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。二.一般形式目标函数：Max(Min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2...am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥0三.线性规划模型的标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x

5、2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0线性规划的标准形式的特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1.极小化目标函数的问题设目标函数为Minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn注：尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf＝

6、-Maxz2.约束条件为“≤”时∑aijxj≤bi→∑aijxj+xn+i=bixn+i——松弛变量(slackvariable)；3.约束条件为“≥”时∑aijxj≥bi→∑aijxj－xn+i=bixn+i——过剩变量(surplusvariable)；显然，xn+i具有非负约束，即xn+i≥0这样处理所得最优解不变；maxz=x1+10x2x1+2x2≤100x1、x2≥0maxz=x1+10x2x1+2x2+x3=100x1、x2、≥04.若xk为无符号限制则令xk=xk1－xk2，其中xk1、xk2≥05.若bi

7、<0，则－bi>0举例:化下列线性规划为标准形maxz=2x1+2x2－4x3s.t.x1+3x2－3x3≥30x1+2x2－4x3≤80x1、x2≥0，x3无限制maxz=2x1+2x2－4x3’+4x3”s.t.x1+3x2－3x3’+3x3”–x4=30x1+2x2－4x3+4x3”+x5=80x1、x2、x3’、x3”、x4、x5≥0四.矩阵形式线性规划的一般形式：MaxcTx(LP)s.t.Ax≤bx≥0其中：c,xRnbRmA:mn矩阵线性规划的标准形式：MaxcTx(LP)s.t.Ax=bx≥0其中：c

8、,xRnbRmA：mn矩阵3.2线性规划的图解法一、基本概念可行解(FeasibleSolution)——任一满足约束条件的一组决策变量的数值；可行域(FeasibleRegion)——所有可行解组成的集合，也称为可行解集；目标函数等值线(Objectivefunctionline)——为于同一直