最优化理论与方法-电子科技大学

第三章最优化理论与方法最优化计算方法主要是研究在一定限制条件下，选取某种方案以达到最优化目标的一门学科。达到最优目标的方案，称为最优方案，搜索最优方案的方法，称为最优化方法。这种方法的数学理论，称为最优化理论。实际上最优化方法已广泛应用于空间技术、军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、经济管理等等领域。最优化方法包括的内容很广泛，如线性规划、非线性规划、整数规划、动态规划、多目标规划、组合优化等等。最优化理论与方法3.1线性规划问题的数学模型3.2二维线性规划的图解法3.3二维线性规划的基本概念及解的性质3.4单纯形法3.7一维搜索法3.8无约束最优化方法§3.1线性规划问题的数学模型一.最优化问题举例例1（运输问题）设有位于不同城市的m个电视机厂A1，A2，…，Am，其产量分别为a1，a2，…，am（台），其产品供应n个城市B1，B2，…，Bn。每个城市的需要量分别为b1，b2，…，bn（台）。假定产需平衡，即=miia1=niib1=已知从Ai到Bj的运费单价为cij（元/台）（i=1,2,…,m；j=1,2,…,n）。问由每个厂到每个城市的运输量各为多少时，既能保证需要量，又能使总运费最少？解设由Ai到Bj的运输量为xij（台）（i=1,2,…,m；j=1,2,…,n），则要求总运费达到最小，其中要满足的约束条件为：==minjijijxc11综上，可把所得到的线性规划问题记为:==========,,,2,1;,,2,1,0,,,2,1,,,2,1,..,min1,111mjnixnjbxmiaxtsxcijmijijnjiijminjijij…………=njijx1=miijx1=ai，i=1,2,…,m；=bj，j=1,2,…,n例2(系统可靠性问题)在设计某些大型的系统工程时,常常要考虑它们的可靠性。设一个系统是由n个部件串联而成。为提高系统的可靠性，每个部件都装有备用件，一旦原部件出现故障，备用件就自动进入系统。显然,备用件越多系统可靠性越大，但费用也越高，重量也越大，这在实际上是不行的。假定当部件k配置uk个备用件时，这个部件正常工作的概率为pk(uk)，而每个备用件k的费用为ck,重量为ak。试在总费用不超过C，总重量不超过A的条件下决定各部件的备用件的数量，使得系统正常工作的概率最大。解因为系统正常工作的概率是各部件正常工作的概率的乘积，所以问题归纳为uk是正整数。=nkkkup1)(max=nkkkCucts1.=nkkkAua1例3（非线性方程组的求解）解非线性方程组是相当困难的一类问题，由于最优化方法的发展，对解非线性方程组提供了一种有力的手段。解非线性方程组===0),,,(0),,,(0),,,(21212211nnnnxxxfxxxfxxxf…………………在方程组有解的情况下等价于下列函数的最小值点：),,,(),,,(min211221nniinxxxfxxxF==……例4合理下料问题某车间有长度为180cm的钢管(数量充分多),今要将其截为三种不同长度,长度为70cm的管料100根,而52cm、35cm的管料分别不得少于150根和120根,问应采取怎样的截法,才能完成任务,同时使剩下的余料最少？解所有可能的截法共有8种,如下表所示：截法一二三四五六七八需要量长度702111000010052021032101503510130235120余料56235246235选其中一种余料最少的截法,但不能完成任务.所以我们必须同时采取若干种截法,配合起来,在完成任务的条件下,使总的余料最少.设采用第i种截法的钢管数目为xi(i=1,…,8),那么截出70cm的管料数目应为(2x1+x2+x3+x4)根,其总数应为100,即2x1+x2+x3+x4=100同理可得2x2+x3+x4+3x5+2x6+x7≥150x1+x3+3x4+2x6+3x7+5x8≥120由题意可知xi≥0(i=1,…,8)余料的总长度为于是上述下料问题的数学模型为1234567856235246235.fxxxxxxxx=12345678123423567134678min56235246235;..2100,232150,3235120,0,(1,2,,8).ifxxxxxxxxstxxxxxxxxxxxxxxxxj===≥≥≥i说明：由于求变量x1，x2，…，xn使某函数f(x1，x2，…，xn)（也记为f(x))达到极大，等价于使-f(x)达到极小。所以上述例子均可归结为函数的带约束或不带约束的极小化问题，简称最优化问题，其中称f(x)为目标函数。二．最优化问题的数学模型与分类1.根据问题不同特点分类(1)无约束极小化问题求x=(x1，x2，…，xn)T使函数f(x)达到最小,记为)(minxfnRx或min)(xf（2）约束极小化问题记为=migtsfi,,2,1,0)(..)(minxx…hj(x)=0,j=1,2,…,n说明：若某些问题的约束条件出现h(x)≤0，则可令g(x)=-h(x)而将此约束转化为g(x)≥0,所以模型中的不等号均假定为≥.注:∵h(x)=0h(x)≥0-h(x)≥0其中S={x|gi(x)≥0,i=1,…,m}称为可行集或可行域，S中的点称为可行点。所以上述(2)约束极小化问题也可表为：或)(minxfSx=migtsfi,…,2,1,0)(..)(minxx2.根据函数类型分类根据目标函数和约束函数是否是线性函数可分为三类，具体见下表。类目标函数约束函数线性规划线性线性二次规划二次函数线性非线性规划除上(1)极大值问题极小化对maxf(x),只要令g(x)=-f(x),则极大值问题就转化为求g(x)的极小值问题.4.将一般的线性规划问题转化成标准形式的方法3.线性规划问题数学模型的标准形式11min();..(1,2,,),0(1,2,,).njjjnijjijjfxcxstaxbimxjn======≥称变量xn+p为松驰变量.(3)转变“≥”约束为等式约束(2)转变“≤”约束为等式约束引入xn+p≥0,使npjjpjaxb=1≤n+p1npjjpjaxxb==1nqjjqjaxb=≥1nqjjnqqjaxxb==引入xn+q≥0,使称变量xn+q为剩余变量.标准形式要求xi≥0,模型中如果出现xi可任取值,则称xi为自由变量,此时可作如下处理:(4)消除自由变量例5将下面线性规划化为标准形.引入新变量,令即可.0,0jixx+≥≥iiixxx=1231312123123max(23);..270,325,xxxstxxxxxxxxxx=≤≥0,≥0,任意.1231312123123max(23);..270,325,xxxstxxxxxxxxxx=≤≥0,≥0,任意.解极大问题极小化:123123max(23)min(23).xxxxxx=引入松驰变量x4≥0,使.134270xxx=引入剩余变量x5≥0,使125320.xxx=消除自由变量x3,令36767,0,0,xxxxx=≥≥1231312123123max(23);..270,325,xxxstxxxxxxxxxx=≤≥0,≥0,任意.则原规划的标准形式为注:标准形中还可要求bi≥0(i=1,…,m),若某个bi≤0,则可在所在等式两端同乘以(1)即可.5.线性规划的标准形还可以写成矩阵形式126714671251267min(233)..277032050,1,2,,7ixxxxstxxxxxxxxxxxxi====令则线性规划的标准形式又可写成矩阵形式:12(,,)Tncccc=12(,,)Tmbbbb=12(,,)Tnxxxx=111212122212nnmmmnaaaaaaAaaa=min;..,0.TcxstAxbx=≥min;..,0.TcxstAxbx=≥的矩阵形式为:如例5，即规化:126714671251267min(233)..277032050,1,2,,7ixxxxstxxxxxxxxxxxxi====1234567(0,0,5),(,,,,,,)TTbxxxxxxxx==其中)3,3,0,0,0,2,1(=Tc200107732001001100011A=§3.2二维线性规划的图解法当x=(x1,x2)(即二维线性规划)时,可行集R可用图形表示出来,因而可用图解法来求该线性规划的解.对线性规划min();..,0.TfxcxstAxbx==≥设其可行集为R.例1用图解法求解12121212min()2;..24,3212,0,0.fxxxstxxxxxx=≤≤≥≥解先绘出可行集,由x1≥0,x2≥0,可知可行集在第一象限内;因–x1+2x2≤4,可知可行集在以直线–x1+2x2=4为分界线,且含原点的半平面内;而3x1+2x2≤12是包含坐标原点的、以直线3x1+2x2=12为分界线的半平面.这两个半平面在第一象限的交集就是可行集,如下图所示的阴影部分.再绘出目标函数的等值线.当目标函数值为z0时,其等值线为–x1-2x2=z0这是一条直线,当z0取不同值时,可得到其他等值线.因具有相同的斜率,所以等值线是彼此平行的直线.例如,当z0=0时,得一通过坐标原点的等值线–x1-2x2=0然后确定目标函数的负梯度方向(这是函数值下降最快的方向):()(1,2),Tfx=如上图中箭头所指的方向.最后沿(1,2)T方向,作目标函数值的一系列等值线(一族平行线).由图可知,沿目标函数值下降方向的等值线在点x*=(2,3)与可行集R唯一相交;若目标函数值继续下降,相应的等值线与可行集将不再相交.故点x*=(2,3)为此线性规划的唯一最小值点,相应的最小值为8.例中最优解是R的一个“顶点”.一般地,可证:(1)若可行集R=,则线性规划无最优解;例2解线性规划12121212min(22)...1,20,0,0.xxxtxxxxxx≥≤≥≥(2)若线性规划的最优解存在,则必可在R的某个“顶点”处取得.(3)若R的某两个顶点是最优解,则这两个顶点所连接的线段上任一点都是最优解.解可行集如下图所示的阴影部分.绘出过原点的等值线;求出目标函数的负梯度方向:()(2,2)Tfx=沿(-2,-2)T的方向作目标函数的等值线,也即2x1+2x2=0的平行线,易见x*=(1,0)是此规划的唯一最小值点,且最小值为2.说明:将例2的min改为max,即min(-2x1-2x2).此目标函数的下降方向与例2的相反,由图可知此线性规划没有最优解.例3将例1的目标函数改为f(x)=-3x1-2x2,而约束条件不变,即求解可行集如图:12121212min()2;..24,3212,0,0.fxxxstxxxxxx=≤≤≥≥f(x)=-3x1-2x2可行集的4个顶点为:(0,2),(0,0),(4,0),(2,3)相应的函数值依次为:-4,0,-12,-12所以,目标函数的最小值为-12,且点(2,3)与(4,0)之间的所有点都是该规划的最优解,该规划有无穷多个解.§3.3线性规划的基本概念及解的性质其中A为mn矩阵,设秩R(A)=m,则m≤n,用Pj表示A的第j列,则Ax=b可记为1njjjxPb==基:若可逆,则称B为该线性规划的基.称为基向量.称xji为基变量.其余变量称为非基变量.12(,,,)jjjmBPPP=(