机械优化设计课件prt4.ppt

第五章 线性规划 约束函数和目标函数都为线性函数的优化问题称作线性规划问题； 它的解法在理论上和方法上都很成熟，实际应用也很广泛； 对非线性问题，有可能采用线性逼近方法求解； 线性规划方法还常被用作解决非线性问题的子问题的工具； 第一节 线性规划的标准形式与基本性质 一，线性规划实例 某车间生产甲，乙两种产品。甲产品每件需要 9kg材料、3个工时、4kW电、可获利60元。乙产品每件需要 4kg材料、10个工时、5kW电、可获利120元。每天能供应 360kg材料、300个工时、200kW电、问每天生产甲，乙两种产品个多少件，才能够获得最大的利润。 解：设每天生产甲、乙产品分别为x1,x2件，则有 f(x1,x2)=60x1+120x2-max 9x1+4x2≤360 （材料约束） 3x1+10x2≤300（工时约束） 4x1+5x2≤200 （电力约束） x1≥0, x2≥0 将其化成标准形式为： 求 x= (x1,x2)T min f(x1,x2)=-60x1-120x2 9x1+4x2+ x3 =360 3x1+10x2 + x4 =300 4x1+5x2 + x5=200 xi≥0, (i=1,2,3,4,5) 二、线性规划的标准形式为 求 x=[x1,x2,…,xn]T 使 f(x)=c1x1+c2x2+…+cnxn-min 且满足 a11x1+a12x2+…+a1nxn=b1 a21x1+a22x2+…+a2nxn=b2 : : : : : : : : am1x1+am2x2+…+amnxn=bm bj≥0 (j=1,2,…,m) xi≥0 (i=1,2,…,n) 求 使目标函数 要求满足 约束条件包括两部分：一是等式约束条件，二是变量的非负要求，它是标准形式中出现的唯一不等式形式。 如果有其它不等式约束条件，可以通过引入松弛变量将其化成等式约束形式。 例如：约束条件为 2x1+x22 x1=0,x2=0 引入松弛变量x3=0将 上述条件化成等式形式 2x1+x2+x3=0 x1,x2,x3=0 这样，可行域就由二维空间ABC转成三维空间A’B’C’,如上图。 如果在原来的问题中有一些变量并不要求是非负的，那么可以把它们两个非负变量的差。例如 Xk=Xk’-Xk’’ Xk’=0, Xk’’=0 当把松弛变量以及非负变量引入后，再将所有的变量重新编序，原来的线性规划问题就变成了标准形式。 松弛变量在目标函数中并不出现，而新的非负变量一般将出现在目标函数中。 在所有具有实际意义的线性规划中，总是mn.因为如果m=n,从方程组中唯一决定x,即方程组只有唯一解，没有可供选择的x,这样就不存在所谓优化问题。如果mn,是矛盾方程组，不存在严格满足方程组的解。所以只有mn,方程的解才是不定的，一般将有无穷多个解，我们就可以从中找出使目标函数取最小值的解。 三、线性规划的基本性质 x2 80 9x1+4x2=360 60 40 4x1+5x2=200 D 20 C 3x1+10x2=120 B f(x*)=-4080 0 20 40 A 60 80 100 x1 　　　　 f(x)=0 用代数解法求解约束方程，由于变量数n=5,方程数m=3,mn固有无穷多组解。 若在5个变量中p=n-m=2个变量取零值，当方程组有解时，其解是唯一的，这样的解称为基本解，其个数为 满足非负要求的基本解称作基本可行