第1讲 最优化技术基础-1

1、第第1 1讲讲 最优化技术基础最优化技术基础1 水工程最优化问题概述水工程最优化问题概述 最优化问题的研究始于二次世界大战之前，最优化问题的研究始于二次世界大战之前，当时用于解决最优化问题的数学方法主要是古典当时用于解决最优化问题的数学方法主要是古典的微分法和变分法。二次世界大战中，由于出现的微分法和变分法。二次世界大战中，由于出现了大量不能用古典方法解决的最优化问题，因而了大量不能用古典方法解决的最优化问题，因而产生了数学规划方法。此后，最优化理论和方法产生了数学规划方法。此后，最优化理论和方法逐渐得到丰富和发展。特别是逐渐得到丰富和发展。特别是6060年代以来，随着年代以来，随着电子计算机

2、技术的飞速发展，最优化技术借助计电子计算机技术的飞速发展，最优化技术借助计算机这一有效的计算工具，使许多最优化方法得算机这一有效的计算工具，使许多最优化方法得以实现目前，这项技术已形成为一门新兴的学以实现目前，这项技术已形成为一门新兴的学科，最优化理论的应用已遍及各个领域。科，最优化理论的应用已遍及各个领域。 在水工程领域存在着大量的最优化问题在水工程领域存在着大量的最优化问题如水处理设备的设计、制造、安装及运行如水处理设备的设计、制造、安装及运行方式的选取，水处理工艺系统的选择和确方式的选取，水处理工艺系统的选择和确定，都涉及许多最优化问题定，都涉及许多最优化问题 在水工程领域中，最优化理论

3、和方法最在水工程领域中，最优化理论和方法最先应用于废水处理方面，在给水处理方面先应用于废水处理方面，在给水处理方面的应用是在上世纪的应用是在上世纪7070年代末期，在给排水年代末期，在给排水管网设计方面也有最优化应用的一些成果。管网设计方面也有最优化应用的一些成果。 2 水工程的寻优问题水工程的寻优问题 例例1 1 设计一个中间有隔板的长方形沉淀设计一个中间有隔板的长方形沉淀水箱，要求各个面壁加底板的总面积不得超过水箱，要求各个面壁加底板的总面积不得超过288m2，应如何确定尺寸，使沉淀水箱的容积，应如何确定尺寸，使沉淀水箱的容积最大？最大？ 设沉淀箱的长、宽、高分别为设沉淀箱的长、宽、高分别

4、为x、y、z，要求，要求确定确定x、y、z，而使沉淀箱容积，而使沉淀箱容积Vxyz最大。最大。x、y、z的取值，显然必须满足：的取值，显然必须满足： x、y、z0 3yz+xy+2xz288我们可以把这个问题写成这种形式我们可以把这个问题写成这种形式 : Vmax=xyz (11）x、y、z要满足如下条件要满足如下条件: : x、y、z03yz+xy+2xz288 （12） 例例2 2 靠近某河流有两个化工厂靠近某河流有两个化工厂(下图下图)。流经。流经第一个化工厂的河水流量是第一个化工厂的河水流量是500104 m3/d；在两；在两个化工厂之间有一条流量为个化工厂之间有一条流量为200104

5、 m3/d的支流。的支流。第一个化工厂每天排放工业污水第一个化工厂每天排放工业污水2104 m3；第二；第二个化工厂每天排放工业污水个化工厂每天排放工业污水1.4104 m3。从第一。从第一个化工厂排出的污水流到第二个化工厂之前，有个化工厂排出的污水流到第二个化工厂之前，有20可自然净化。根据环保要求，河流中工业污可自然净化。根据环保要求，河流中工业污水的含量应不大于水的含量应不大于0.2。若这两个化工厂都各自。若这两个化工厂都各自处理一部分污水，第一个化工厂处理污水的成本处理一部分污水，第一个化工厂处理污水的成本是是0.1元元/m3，第二个化工厂污水处理的成本是，第二个化工厂污水处理的成本是

6、0.08元元/m3。现在问，在满足环保要求的条件下，两个。现在问，在满足环保要求的条件下，两个化工厂各处理多少污水才能使两厂总的处理污水化工厂各处理多少污水才能使两厂总的处理污水费用最小？费用最小？ 设第一个化工厂每天处理污水量为设第一个化工厂每天处理污水量为x1104 m3，第二个，第二个化工厂每天处理污水量为化工厂每天处理污水量为x2104m3，两个化工厂总的处，两个化工厂总的处理污水费每天为理污水费每天为: 0.1x11040.08x2 104 1000 x1800 x2 （元）（元）500104 m3/d200104 m3/d问题是要求这个总处理污水费用最小，即要选问题是要求这个总处理

7、污水费用最小，即要选择择x1和和x2，使，使 1000 x1800 x2min或者或者, ,等价地使等价地使 5x14 x2min x1和和x2并不能任意选择，它们受到许多条件的限并不能任意选择，它们受到许多条件的限制。制。每个化工厂每天处理的污水量不能为负值每个化工厂每天处理的污水量不能为负值, 但但也不会大于每天的排放置，即也不会大于每天的排放置，即 x1、x2 0 x1 2， x2 1.4 从第一个化工厂到第二个化工厂，河流中污从第一个化工厂到第二个化工厂，河流中污水含量不应大于水含量不应大于0.2，所以，所以即 x1 1 流经第二个化工厂后，河流中的污水量仍应流经第二个化工厂后，河流中

8、的污水量仍应不大于不大于0.2，这时有，这时有 即即 0.8x1 +x2 1.6或或 4x1 +5x2 8 问题的数学表达式可写成如下的形式问题的数学表达式可写成如下的形式: x1、x2要满足如下条件：要满足如下条件： minZ=min( 5x14 x2)x1 1 x1 2 x2 1.44x1 +5x2 8x1、x2 03 最优化问题的理论表述最优化问题的理论表述(1)系统系统“最优化最优化” 是是“系统的最优化系统的最优化”系统是指许多单元按某种目的而构成的整体，即系统是指许多单元按某种目的而构成的整体，即一组相互联系、相互依赖、相互制约、相互作用的一组相互联系、相互依赖、相互制约、相互作用

9、的事物或过程组成的具有特定功能和行为的整体。确事物或过程组成的具有特定功能和行为的整体。确定系统，就是确定研究的范围。定系统，就是确定研究的范围。通常一个系统是由比它更小的系统所组成的。而通常一个系统是由比它更小的系统所组成的。而一个系统又往往是另一个更大系统的组成部分。我一个系统又往往是另一个更大系统的组成部分。我们把组成系统的次一级较小的系统称为原系统的子们把组成系统的次一级较小的系统称为原系统的子系统。最基本的子系统是单元设备或单元过程。系统。最基本的子系统是单元设备或单元过程。(2) 决策变量和状态变量决策变量和状态变量 每一个系统都可以用一组基本参数来表示每一个系统都可以用一组基本参

10、数来表示, , 有结构有结构参数参数(设备几何尺寸、台数等设备几何尺寸、台数等)，操作参数，操作参数(运行控制的运行控制的参数参数)或其它物理量。这些参数中可独立变化的参数，或其它物理量。这些参数中可独立变化的参数，称为称为决策变量或设计变量决策变量或设计变量。另一些参数是由。另一些参数是由决策决策变量变量所决定的，称为所决定的，称为状态变量状态变量。 任何系统总有由它本身过程特性所决定的内部联系，任何系统总有由它本身过程特性所决定的内部联系，这种内部联系就是确定基本参数之间相互关系的数学这种内部联系就是确定基本参数之间相互关系的数学方程式，又称为状态方程。所以一旦决定了决策变量方程式，又称为

11、状态方程。所以一旦决定了决策变量, , 状态变量也就随之决定了。从这个意义上说，只要决状态变量也就随之决定了。从这个意义上说，只要决定了决策变量，系统的状态也就被单一地确定了。定了决策变量，系统的状态也就被单一地确定了。 显然显然, , 系统的基本参数数目总是大于描述它内部系统的基本参数数目总是大于描述它内部联系的数学方程式的数目的，所以这些方程组就有无联系的数学方程式的数目的，所以这些方程组就有无穷多个解。正因为如此，研究系统的最优化就十分必穷多个解。正因为如此，研究系统的最优化就十分必要和有意义。要和有意义。 (3) 目标函数、约束条件、可行点和可行域目标函数、约束条件、可行点和可行域1)

12、 1)目标函数目标函数 上述例子都是用一个数学式子来评价生产过程上述例子都是用一个数学式子来评价生产过程或设计方案的优劣程度，这种数学式子就称为最优或设计方案的优劣程度，这种数学式子就称为最优化问题的化问题的目标函数目标函数(也称性能指标或最优化准数也称性能指标或最优化准数)。即事先对系统规定最优化准则，或者列出系统最优即事先对系统规定最优化准则，或者列出系统最优设计或最优控制所要达到目标的数学表达式设计或最优控制所要达到目标的数学表达式, 它是它是状态变量、决策变量的某种形式的函数，但最终它状态变量、决策变量的某种形式的函数，但最终它是决策变量的函数。是决策变量的函数。设目标函数为 式中 x

13、i 决策变量，il，2，n; yj 状态变量，j1，2，r 因为状态变量是决策变量的函数:因此因此使用更简捷的记法使用更简捷的记法: S = S(x , y) (18)因为因为 y=y(x)所以所以 S = S(x, y(x)=S(x) (19) 例例1的目标函数是的目标函数是: man xyz 或或 min(-xyz)例例2的目标函数是的目标函数是: min 1000 x1 + 800 x2 有时目标函数难以用一个数学式表达出来，或者即使能表达出来，表达式也非常复杂。但是，只要给出一种规则，依据这种规则，可以由决策变量、状态变量计算出目标函数的值，那么也同样可以认为目标函数已经给定了。 很显

14、然，目标函数的形式要视对系统的最优化具体要求而定，其函数结构和形式没有统一的标准。建立的目标函数是否合适, 对最优化问题是很重要的。 需要指出，例3, 例4是取经济指标为目标函数。与经济因素有关的一类目标函数，通常都比较复杂，而由于经济问题中包含过程的随机性和不确定因素，问题将会更加复杂一些。 2) 2) 约束条件约束条件 有些最优化问题对决策变量的取值没有什么限制，这种问题称为无约束问题。但在大多数最优化问题中，决策变量和状态变量是不可能任意取值的。由于技术条件、环境要求等，对它们的变化范围总要加以限制，或者规定它们之间的相互关系。这些称为问题的约束条件。通常约束条件有两种形式， (1) 等

15、式约束 (2) 不等式约束 这两种不等式可以用一个来代替在(113)式两边乘( 1)就转化为(112)式的形式 此外，利用一个正的辅助变量xn+1(称为松弛变量松弛变量) ) ，可以把不等式约束变为等式约束, 如(112)式可以写成(1) 等式约束 (2) 不等式约束 3) 3) 可行点及可行域可行点及可行域 满足所有约束条件的一个方案, 即决策变量的一组取值，称为一个可行点可行点。所有可行点的集合称为可行域可行域. 所谓寻优，就是在可行域上寻找最优的可行点。 (4) 最优化问题的一般表达式通常用下面的形式表达最优化问题 s. t. 是subject to的缩写，即 “受约束于”。min指求目

16、标函数值最小有时用op S 代替min S (op是optimization的缩写),用更简捷的记法: 这里x=(x1，x2, ，xn); V是指满足所有约束条件的x的集合，即可行域。 4 最优化问题的类型最优化问题的类型 一个最优化问题，至少有两个要素，第一个是可能的方案，第二个是追求的目标，而后者是前者的函数。如果第一个要素与时间无关，则称该问题为静态最优化问题，否则称为动态最优化问题(主要用于自动调节和自动控制系统)。 如果目标函数是决策变量的线性函数, 而且约束条件也是决策变量的线性等式或不等式，则称该问题为线性规划问题(如例2) 如果目标函数和约束条件中，有一个或几个是决策变量的非线

17、性函数，称非线性规划问题(例1)。 决策变量中全是整数或离散值时，称为整数规划。如果决策变量中有一部分是离散值，其余的是连续变量，则称为混合规划。 没有约束条件的规划问题，称为无约束问题，否则称为有约束的规划问题。我们所遇到的问题大部分是有约束的规划问题5 水工程的数学模型水工程的数学模型 建立水工程系统的数学模型，是求解优化问建立水工程系统的数学模型，是求解优化问题的重要一步。题的重要一步。 对物理化学过程和系统作出的数学描述，称对物理化学过程和系统作出的数学描述，称为数学模型。为数学模型。 为了能对现象，过程和系统作数学描述，往为了能对现象，过程和系统作数学描述，往往需要对过程和系统进行必

18、要的简化，简化的基往需要对过程和系统进行必要的简化，简化的基础是实际过程和系统之间的等效性。也就是说，础是实际过程和系统之间的等效性。也就是说，数学模型是用数学手段将现象和系统的特征或者数学模型是用数学手段将现象和系统的特征或者本质描述出来的数学表达式完整的数学模型应本质描述出来的数学表达式完整的数学模型应该包括过程和系统的主要参数以及主要参数间的该包括过程和系统的主要参数以及主要参数间的关系。关系。(1) 数模分类数模分类 (2) 建模方法建模方法1) 理论模型理论模型 理论模型是指主要依据基本的物理化学定律而推导理论模型是指主要依据基本的物理化学定律而推导出来的模型。出来的模型。2) 相似

19、理论和因次分析方法相似理论和因次分析方法 对有些现象即使列出了微分方程，由于十分复杂对有些现象即使列出了微分方程，由于十分复杂也无法求解；有的连微分方程也难以建立起来。这就也无法求解；有的连微分方程也难以建立起来。这就不得不直接依靠试验的方法探求这些现象的规律性。不得不直接依靠试验的方法探求这些现象的规律性。这就是模型化方法，即用方程分析或因次分析的方法这就是模型化方法，即用方程分析或因次分析的方法导出相似准数，并根据相似原理建立模型台，在模型导出相似准数，并根据相似原理建立模型台，在模型台上通过试验方法求出相似准数之间的函数关系，再台上通过试验方法求出相似准数之间的函数关系，再将此函数关系推

20、广到设备实物，从而得到实物的工作将此函数关系推广到设备实物，从而得到实物的工作规律。规律。3) 经验公式经验公式 如果过程的状态特征值如果过程的状态特征值y和过程参数和过程参数x之间的之间的关系难以直接用公式表示，该现象的理论根据不关系难以直接用公式表示，该现象的理论根据不清楚，或者十分复杂，但可以认为其实侧值与某清楚，或者十分复杂，但可以认为其实侧值与某个关系式比较吻合，那么，为了从数量上估计这个关系式比较吻合，那么，为了从数量上估计这种关系，可以利用经验公式来构造模型种关系，可以利用经验公式来构造模型 如果一个表达式的一部分是理论模型，另一如果一个表达式的一部分是理论模型，另一部分则是根据

21、实测数据构造出来的，则称为半经部分则是根据实测数据构造出来的，则称为半经验公式验公式 我们简单地介绍一下这种构造经验公式的方法 设在过程参数 X(x1, X2,xn.)的不同值下，得到过程状态特征y的一系列测量值：首先讨论y与x是线性关系的方程:01 122.mmybb xb xb x我们用下面的原则来决定b i(i0，1，2,n)如此选择bi，使的值最小。这一方法称为最小二乘法。bi 的值可由解下面的(m+1)元线性联立方程组而得到即如果用矩阵形式表达，则更简捷：式中称为构造矩阵构造矩阵yXXbXTT这时有 由试验数据选配经验公式形式，应尽量根据专业示例或经验确定。 如果没有示例参考，就把试

22、验点描在坐标纸上，根据数据点的分布情况来确定经验公式的形式。 对于选配多变量的经验公式，先考虑一个主要变量, 而把其它变量固定，研究过程特征值与这个主要变量间的关系，配出合适的公式，再进一步考虑其它变量的影响。yXXXbTT1)(构造经验公式的例: 例例1 试构造密度为2.7 gcm3，的滑石粉悬浊液沉降过程的数学模型。测得时刻以前变成沉淀的悬浮物百分数Q，数据如下： 首先，把试验值画在坐标纸上(下图)，研究应配何种曲线推想以下的双曲线比较合适111,00mmmQQQQQ或%例例1配曲线的回归系数计算程序配曲线的回归系数计算程序1%选用的公式形式：选用的公式形式：Q=Qm*t/(t+to)%x

23、=1/t; y=1/Q; y=b1+b2*xt1=5 10 15 20 30 50 70 100 120;Q1=23 40 56 60 75 82 84 91 93; %原始数据对原始数据对x=1./t1y=1./Q1X=ones(9,1) x %形成形成“构造矩阵构造矩阵”b=inv(X*X)*X*y %其中其中inv(X*X)=(X*X)-1Qm=1/b(1)to=Qm*b(2)X = 1.0000 0.2000 1.0000 0.1000 1.0000 0.0667 1.0000 0.0500 1.0000 0.0333 1.0000 0.0200 1.0000 0.0143 1.000

24、0 0.0100 1.0000 0.0083b = 0.0085 0.1697Qm = 117.0729to =19.8690令则有012111,mmyxbbQQQ12ybb x这样，本例中的沉降曲线经验公式沉降曲线经验公式为120210.0085,0.1697,1117.0729,19.8690mmbbQQbb%例例1 绘图程序绘图程序t=0:120;Q=Qm*t./(t+to);plot( t1,Q1,o,t,Q,-)grid on0204060801001200204060801001201119.8691 117.0729,117.0729117.072919.869QQ或%例例1配曲

25、线的回归系数计算程序配曲线的回归系数计算程序2%使用使用regress函数计算多元线性回归方程的系数函数计算多元线性回归方程的系数t1=5 10 15 20 30 50 70 100 120;Q1=23 40 56 60 75 82 84 91 93; %原始数据对原始数据对x=1./t1;y=1./Q1;X=ones(9,1) x; %形成构造矩阵形成构造矩阵b,bint,r,rint,stats=regress(y,X); %regress函数的调用格式函数的调用格式b,bint,stats %显示参数显示参数Qm=1/b(1)to=Qm*b(2) b = %系数向量系数向量 0.0085

26、 0.1697bint = %系数向量系数向量 的的95置信区间置信区间 0.0074 0.0097 0.1551 0.1844stats = %分别为分别为R2、F、p 0.9908 749.8300 0.0000 当当p，则否定假设H0；否则，假设H0是相容的。 F分布的临界值有表可查。) 1/(/mnQmUF仍用前例1经验公式，检验所得公式是否可用。假设y1/Q 遵从正态分布规律F分布的密度函数分布的密度函数22211(0.0435+0.0250+.+0.0108 )0.01809()( 12* )8.8597e-004( 12* )8.2709e-006/1 749.8300/(1)/

27、(9 1 1)iiiyynUyybbxyQybbxU mUFQnmQ %例例1配曲线的检验配曲线的检验t1=5 10 15 20 30 50 70 100 120;Q1=23 40 56 60 75 82 84 91 93; x=1./t1;y=1./Q1;X=ones(9,1) x; b=regress(y,X); % F值计算值计算yp=mean(y)d1=(b(1) + b(2) *x-yp).2;d2=(y-(b(1) + b(2) *x).2;U=sum(d1),Q=sum(d2)F=(U/1)/(Q/(9-1-1)yp = 0.0180U = 8.8597e-004Q = 8.27

28、09e-006F = 749.8300 在在0.05下，查自由度为下，查自由度为I、7的的F分布表分布表得临界值得临界值 5.59 现在现在F749.835.59 ，所以否定假设，所以否定假设H0，即认为，即认为y与与x间存在线性相关关系。所以公间存在线性相关关系。所以公式真实地描述了沉降过程，可以在本例的沉淀式真实地描述了沉降过程，可以在本例的沉淀过程的分析中加以使用。过程的分析中加以使用。 需要注意的是需要注意的是, 上述检验数学模型是否符合实际的上述检验数学模型是否符合实际的F分布检验方法，分布检验方法，有如下假定有如下假定: 过程状态特征是遵从正态分布的独立随机量。这种方法过程状态特征

29、是遵从正态分布的独立随机量。这种方法对线性方程是正确的，对多项式模型和有线性系数的其它模型也是正对线性方程是正确的，对多项式模型和有线性系数的其它模型也是正确的如果模型是非线性的，这时确的如果模型是非线性的，这时Q/(n-m-1)并不是并不是2的无偏估计的无偏估计, 故故上面适于线性模型的利用上面适于线性模型的利用F分布检验回归模型的方法不再适用分布检验回归模型的方法不再适用5) 经济数据的数学处理经济数据的数学处理 对经济数据进行数学处理不属于水工程的数学模型的研究范围，但它在讨论水工程最优化问题中十分重要, 所采用的方法和前述的经验公式基本相同。管道造价公式管道造价公式(费用函数费用函数)

30、形式应具有下列特点形式应具有下列特点:(1)能较好的描述实际情况,与实际资料的拟合差最小;(2)费用函数的各参数都能通过一定的数学方法求得;(3)形式简单,便于应用.随着优化技术的应用,发表的费用函数形式较多,例如: C=a+bD C=KDH C=K1 +K2D+K3H+K4HD使用时应注意:(1)公式精度; (2)地区性; (3)时间性.给水管道造价公式1. 给水管道造价计算模式在进行给水管道技术经济分析时，需要知道管材的造价计算公式。 可将上表数据（D，C）点绘在坐标图上。一般有如图1的形状。这种曲线一般可用以下数学公式来表达： CaDz （1）式中a、z为常数，与各地的具体条件（管材价格

31、、地质条件、施工条件）有关,见下图。 影响造价的因素管道种类管道材料施工地点土壤含水状态运输条件铸铁管预应力砼管塑料管 公路 铁路 水路在城区内在城区外 干土 湿土输水管配水管网从式（1）可见，a是D0时的C值，再由图1，曲线反向延长交C轴于a点，故a可在（0，C1）区间内取值。为进一步求和z的值，须将曲线式（1）变为直线形式：C-aDz该式两边取对数：lg(C-a)= lgzlgD (2)设Ylg(C-a), blg, XlgD, 则YbzX (3)因此可用直线拟合的方法求得上述式（1）中的各个常数。 2. 2. 关于关于a a取值的精确化取值的精确化 在上述拟合过程中，a的取值是由图1所示

32、的散点图曲线经反向延长交C轴所得坐标值，故不太精确。为了使a取值的精确化，应使得所取a值得到的回归方程的相关指数R（拟合优度检验准则之一）最大。 求a的一个简单方法是枚举法，即a依次取(0,C1)区间内的整数值，分别求得相应的z、b和R值，然后取R值最大时所对应的a、z、b作为管道造价公式（1）的最后结果，用于工程技术经济分析中。 4. 程序及其应用 matlab程序及上机运行所得结果如下：%GZ_1: c=a+beta*Dzn=9; D=.1,.15,.2,.3,.4,.5,.6,.9,1c=20.3,29.1,36,56.7,83.6,103.7,144.3,351,417.3;cp=me

33、an(c);G=c(1); x=log(D); X=ones(9,1),x; disp(*优化计算过程优化计算过程*)disp( a b z R);for a=1:G y=log(c-a); beta,betaint,r,rint,stats=regress(y,X); b(a)=exp(beta(1);z(a)=beta(2);R(a)=stats(1); w=a,b(a),z(a),R(a);w endRmax=max(R);for a=1:G if R(a)=Rmax s=a; endenddisp(*优化计算结果优化计算结果*)disp( a b z R);SOLUTION=s,b(s

34、),z(s),R(s)* 优化计算过程 * a b z R 1.0000 324.9123 1.3293 0.9675 2.0000 325.7654 1.3503 0.9697 3.0000 326.7718 1.3724 0.9719 4.0000 327.9520 1.3957 0.9741 5.0000 329.3306 1.4204 0.9763 6.0000 330.9375 1.4466 0.9786 7.0000 332.8095 1.4744 0.9808 8.0000 334.9923 1.5042 0.9830 9.0000 337.5439 1.5361 0.9852

35、10.0000 340.5391 1.5707 0.9873 11.0000 344.0768 1.6082 0.9893 12.0000 348.2914 1.6494 0.9911 13.0000 353.3713 1.6951 0.9926 14.0000 359.5931 1.7465 0.9937 15.0000 367.3842 1.8053 0.9941 16.0000 377.4572 1.8744 0.9932 17.0000 391.1305 1.9589 0.9903 18.0000 411.2760 2.0692 0.9831 19.0000 446.3049 2.23

36、42 0.9656 20.0000 553.4406 2.6277 0.9004* 优化计算结果 * a b z RSOLUTION = 15.0000 367.3842 1.8053 0.9941 C= 15 + 367.4 *D 1.81 c1=s+b(s)*D.z(s);plot(D,c,r*,D,c1,b-)grid onxlabel(D,m)ylabel(c,yuan/m)0.10.20.30.40.50.60.70.80.91050100150200250300350400450D,mc,yuan/m%埋深埋深h=2m, 造价造价c1(元元/m);d1=0.2,0.25,0.3,0

37、.35,0.4,0.45,0.5,0.6,0.7,0.8,0.9,1;h1=2,2,2,2,2,2,2,2,2,2,2,2;c1=54.6,65.1,75.8,85.6,92.7,102.3,111.6,136.3,168.3,213.1,261.7,341.7; %埋深埋深h=3m ,造价造价c2(元元/m);d2=0.2,0.25,0.3,0.35,0.4,0.45,0.5,0.6,0.7,0.8,0.9,1,1.1,1.2,1.35,1.5,1.65,1.8,2;h2=3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3;c2=79.6,88.2,99.2,109.

38、0,116.5,130.5,139.9,165.3,196.3,240.8,293.3,372.0,446.9,516.0,613.2,751.6,876.6,948.5,1274.5;%埋深埋深h=5m, 造价造价c3(元元/m);d3=0.2,0.25,0.3,0.35,0.4,0.45,0.5,0.6,0.7,0.8,0.9,1,1.1,1.2,1.35,1.5,1.65,1.8,2;h3=5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5;c3=137.8,149.0,157.0,169.1,177.5,189.8,202.5,229.3,263.5,309.0

39、,363.3,441.0,526.1,592.5,691.0,832.4,959.2,1078.2,1367.5;%回归计算d=d1,d2,d3;h=h1,h2,h3;c=c1,c2,c3;x1=log(d);x2=log(h);y=log(c);X=ones(50,1),x1,x2; %形成回归矩阵Xb,bint,r,rint,stats=regress(y,X)k=exp(b(1) %求原造价公式的系数0.6330 1.1360 32HD187.1901bbHkDcb = 5.2321 1.1360 0.6330k = 187.19016求解最优化问题的数学方法求解最优化问题的数学方法 和

40、和MATLAB优化工具箱优化工具箱 二战以来，古典微分法和变分法是求解最优二战以来，古典微分法和变分法是求解最优化问题的唯一方法。但当独立变量数目很多，目化问题的唯一方法。但当独立变量数目很多，目标函数和约束条件很复杂时，使用古典方法已很标函数和约束条件很复杂时，使用古典方法已很难奏效，促使人们研究更有力助手段来处理最优难奏效，促使人们研究更有力助手段来处理最优化问题。这些方法统称为化问题。这些方法统称为“数学规划法数学规划法” 介绍求解水工程最优化问题时常用到的一些介绍求解水工程最优化问题时常用到的一些方法主要有：线性规划法、非线性规划法和动态方法主要有：线性规划法、非线性规划法和动态规划法

41、。规划法。 MATLABMATLAB的优化工具箱能够解决各种各的优化工具箱能够解决各种各样的优化问题。样的优化问题。 第一节 古典解析方法 对于简单的函数，利用微分法可以求出其各个局部最优值(极值)，然后加以比较，从而得出全局最优值。 对于单变量函数 f(x)，如果其一阶导数存在，则欲使x*为极值点的必要条件是 f (x)0通常称使f (x)0的点为驻点 极值点必为驻点，但驻点并不一定全是极值点, 驻点是否为极值点，可以通过该点处的二阶导数来判断 若在驻点附近， 该点为极大值点 若在驻点附近， 该点为极小值点0)(xf0)(xf f(x) 在点x*处的n个一阶偏导，构成一个n维向量称为 f(x

42、)在x*处的梯度：对于n元函数 f(x) = f(x1， x2 ， xn)如果 f(x) 具有连续的一阶偏导，则x*(x1*， x2* ， xn*)为 f(x) 的一个极值点的必要条件是),.,2 , 1(, 0)(nixxfi*21)(,)(,)(*)(xxTnxxfxxfxxfxf 因此，如果 f (x)有连续的一阶偏导，则x*为 f (x)的一个驻点的必要条件是0*)(xf极值的充分条件极值的充分条件 f (x)有连续的二阶偏导，x*为 f (x)的一个驻点， 则x*为极小点的充分条件是f (x)的海赛矩阵在该点为正定的； x*为极大点的充分条件是f (x)的海赛矩阵在该点为负定的。 f

43、 (x)在x*处的海赛矩阵为其中 读del，或 nabla，汉密登符号，即微分算子zkyjxi对有等式约束条件的可微函数其极值可用拉格朗日乘子法求解。 *22221222222122122122122,*)(xxnnnnnxfxxfxxfxxfxfxxfxxfxxfxfxf本问题最优化的数学形式是288230,. .maxxzxyyzzyxtsxyz例1 设计一个中间有隔板的长方形污水沉淀箱，设计一个中间有隔板的长方形污水沉淀箱，要求各个面壁加底板的总面积不得超过要求各个面壁加底板的总面积不得超过288m2，应如何确定尺寸使沉淀箱的容积最大应如何确定尺寸使沉淀箱的容积最大容易看出，当 3yz

44、十 xy 十 2xz288时，可以设法增加 3yz 十 xy 十2xz 的值而使 xyz 值增加。所以(12)式中的第二个式子可用等式代替即问题成为用拉格朗日乘子法构造新的函数)28823(xzxyyzxyzL288230,. .maxxzxyyzzyxtsxyz求L关于x、y、z的偏导，并令其为0，得到解得 x1.5y，y=2z，x3z，即 x：y：z=3：2：1,所以 从而求出最优解x12m，y8m，z4m。如采用MATLAB求解，此题为非线性约束规划问题。非线性约束规划问题。0)23(0)3(0)2(xyxyzLxzxzyLzyyzxL28832323323xxxxxx 第二节 线性规划

45、法 线性规划法是数学规划中提出较早、在理论和算法上也较为成熟的一个分支。实践中有许多线性规划问题，而一些非线性规划问题往往可以近似地作为线性规划问题来处理，所以研究线性规划问题的解法是很有意义的。 一、图解法 我们在前面已提出了一个线性规划问题，该例用数学形式表达出来是 这是一个二维问题，可以在平面直角坐标系中以x1、x2为坐标轴，把问题的约束条件直观地表示出来。 下图中的阴影部分表示问题的可行域。minZ= 5x14 x2s.t.： 4x1 +5x2 8 x1 1 x1 2 x2 1.4 x1,x2 0s.t.：4x1 +5x2 8 (1) x1 1 (2) x1 2 (3) x2 1.4

46、(4) x1,x2 0 (5) 目标函数在坐标平面上可表示为以z为参数的一族平行线 位于直线上的点，其目标函数的值是相同的。当z值由大变小，直线沿其法线方向向左下方移动。当移动到Q点时，z值最小。这就得到了最优解x11，x2=0.8，相应的目标函数最优值z8.2。实际上，总的处理污水最小费用为每天1640元。 从上面的例子可以看出，可行域是一个凸集，而且最优解恰巧在可行域的一个顶点上，这并不是偶然的 44512zxx 在图解中我们所看到的现象，并不是个别的现象，而是由线性规划的性质所决定的. 数学上已经证明线性规划问题的下述基本定理: 1)线性规划问题的所有可行解组成的集合，即可行域，是一个凸

47、集 2)线性规划问题的基本可行解对应于可行域的顶点 3)若可行域有界，则线性规划问题的目标函数一定可在其可行域的某个顶点处达到最优值。 4)对于具有n个变量, m个等式约束的线性规划问题(nm)，其可行域的每一个顶点是m个边界的交点。每条边界是按某一变量为零“画”出来的因此在顶点处，在n个变量中，肯定有m个变量为零。 5)某线性规划问题如有最优解，则必定是在某个顶点处二、单纯形法（Simplex Method） 虽然可行域顶点的数目是有限的(它不超过 个)，但当n、m的数目相当大时，穷举法是行不通的。单纯形法是解线性规划问题的最基本的方法。 该法的基本思想:先任取一个基本可行解(即可行域的一个

48、顶点)，从这个解开始，转换到另一个基本可行解(可行域的另一个顶点)，而使目标函数的值改善, 再从这个解出发，重复刚才的步骤; 这样，用迭代法一次次迭代, 直到目标函数不再改善为止。 单纯形法只考察全部基本可行解中的一部分，因此效率较高。mnC在Matlab中, 用LINPROG函数求解如下形式的线性规划问题: min f X s. t. AX B （线性不等式约束） AeqX=Beq （线性等式约束） LB X UB （LB为下界约束向量, UB为上界约束向量）(1)目标函数若为 max f X, 则转化为 min f X;(2)若 AX B, 则转化为 AX B.具体求解时具体求解时,首先给

49、首先给f,A,b赋值赋值, 然后按以下格式调用函数然后按以下格式调用函数LINPROG: :X=LINPROG(f,A,B) %返回解向量返回解向量XX, fmin=LINPROG(f,A,B) %返回返回X 和目标函数的最小值和目标函数的最小值fminX=LINPROG(f,A,B, LB,UB) X=LINPROG(f,A,B,LB,UB,X0) %X0为设置的为设置的X初值初值X, fmin,KEY,C=LINPROG(f,A,B,Aeq,Beq, LB,UB, X0) %返回KEY1，说明求解成功。C为迭代计算次数。% 例1 min z=-3*x1-5*x2-4*x3% s.t. 2*

50、x1+3*x28% 2*x2+5*x310% 3*x1+2*x2+4*x316% x1,x2,x30f=-3 -5 -4;A=2 3 0;0 2 5;3 2 4;-1 0 0;0 -1 0;0 0 -1;b=8 10 16 0 0 0;x, minz =linprog(f,A,b)运行结果显示:x = 2.5366 0.9756 1.6098minz = -18.9268%例2: min z=10 x+15y% s.t. -x -0.375% -3.116x-6.977y -6.34% -1.372x-1.688y -0.91% x 0.8, y 0.8, x, y 0f=10 15;A=-1

51、 0;-3.116 -6.977;-1.372 -1.688;1 0;0 1;-1 0;0 -1;b=-0.375 -6.34 -0.91 0.8 0.8 0 0;x, minz =linprog(f,A,b)运行结果显示:x = 0.3750 0.7412minz = 14.8683%例3: min 5x1+4x2+2x3% Sub.to: 6x1-x2+x38 % x1+2x2+4x3 10% -1 x1 3% 0 x2 2 % x30 f=-5 4 2; A=6 -1 1;1 2 4; b=8,10; lb=-1,0,0; ub=3,2,inf; x,lam= lp(f,A,b,lb,u

52、b) minz=f*x运行结果显示:X = 1.3333 0 0Lam = 0.8333 0 0 3.1667 2.8333 0 0minz = -6.6667Lam表明: 6x1-x2+x38, x20,x30发挥了作用.f=-2 1 4 3 1; A=0 2 1 4 2; 3 4 5 -1 -1;B=54; 62; Aeq=; Beq=; LB=0,0,3.32,0.678,2.57;x,f_opt,key,c=linprog(f,A,B,Aeq,Beq,LB,)例4 min 2x1-x2-4x3-3x4-x5s.t. 2x2+x3+4x4+2x554 3x1+4x2+5x3x4x562

53、x3 3.32， x4 0.678， x5 2.57， x1，x20.【解】A=,B=, Aeq=,Beq=, 下界LB 0,0,3.32,0.678,2.57;上界无限制，写成.Optimization terminated successfully.x = 19.7850 0.0000 3.3200 11.3850 2.5700f_opt = -89.5750key = 1 key值为值为1，说明求解成功，说明求解成功c = iterations: 6 % 6步得解，可见程序功能很强步得解，可见程序功能很强 cgiterations: 0 algorithm: lipsol三三. . 应用

54、示例应用示例例例1: 图示为某水库自流引水至水厂供水，可利用水头为图示为某水库自流引水至水厂供水，可利用水头为12.5m，输水量为，输水量为Q=116l/s，输水管总长为，输水管总长为4780m。若可供铺设的输水管有下表中的四种管径，。若可供铺设的输水管有下表中的四种管径，并已知它们的单价和并已知它们的单价和1000m水头损失。如何选择这水头损失。如何选择这4种不同的口径输水管的长种不同的口径输水管的长度搭配，既保证供水又使总造价最少？度搭配，既保证供水又使总造价最少？ 解：设分别取用管径为600，500，400，300mm的管道长度为m时，管道的总造价Y最低。则目标方程： 万元约束条件： M

55、atlab编程如下：Y=220 140 108 72;Aeq=1 1 1 1;Beq=4780;A=0.42 1.03 3.12 13.8;b=12500;lb=0 0 0 0;ub=4780 4780 4780 4780; x=linprog(Y,A,b,Aeq,Beq,lb,ub)minz=Y*x即分别取用管径为600，500，400，300mm的管道长度为0，1154.8，3625.2，0m时，管道的总造价Y最低为55.319万元。 运行结果：运行结果：Optimization terminated.x = 1.0e+003 * 0.0000 1.1548 3.6252 0.0000mi

56、nz = 5.5319e+0051234min220140Yxxxx+108 +72123412341234123447800.421250004780 xxxxxxxxxxxxxxxx+1. 03 +3. 12 +13. 8、 、 、 、 、例例2 一城镇需要从郊区一个湖泊取水，有一条河流进出。城市一城镇需要从郊区一个湖泊取水，有一条河流进出。城市是通过上水系统取水并通过下水系统向湖泊排放污水。现在需决是通过上水系统取水并通过下水系统向湖泊排放污水。现在需决定上水系统净水厂和下水系统污水处理厂的最优处理能力。最好定上水系统净水厂和下水系统污水处理厂的最优处理能力。最好的系统设计方案应使水质满

57、足标准，且处理的总费用为最小。各的系统设计方案应使水质满足标准，且处理的总费用为最小。各单元关系如图单元关系如图: 设设 w w1 1从城市排放到污水处理厂的污染物量，从城市排放到污水处理厂的污染物量，(t/d);(t/d); w w2 2从污水处理厂排入湖泊的污染物量，从污水处理厂排入湖泊的污染物量，(t/d)(t/d)； w w3 3 取水量中的污染物量，取水量中的污染物量，(t/d);(t/d); w w4 4净水厂送至城市的流量中的污染物量，净水厂送至城市的流量中的污染物量，(t/d)(t/d)。流经湖泊的水量流经湖泊的水量9.8549.85410103 3 m m3 3 /d,/d,

58、湖泊水容积为湖泊水容积为98.5498.5410103 3 m m3 3 。城市每天产生污染物量城市每天产生污染物量1.359 t, w1.359 t, w4 4+1.359+1.359w w1 1；通过稀释和自；通过稀释和自然净化的作用，然净化的作用，w w3 30.25w0.25w2 2；根据饮用水标准和城市供水量计算，；根据饮用水标准和城市供水量计算，折合成折合成w w4 4, , 有有w w4 40.453 t/d0.453 t/d，根据游泳娱乐的水质要求，换算后，根据游泳娱乐的水质要求，换算后得得w w2 21.7t/d ; 1.7t/d ; 处理后污染物应不大于处理前污染物，处理后

59、污染物应不大于处理前污染物，w w2 2 w w1 1，w w4 4 w w3 3；显然，；显然，w w1 1,w,w2 2,w,w3 3,w,w 4 400。 净水厂的处理费用为净水厂的处理费用为 C C1 19 910104 4 + 6.02 + 6.021010-3-3(w(w3 3 w w4 4) () (美元美元a)a) 污水处理厂的处理费用：污水处理厂的处理费用： C C2 26 610104 4 + 1.21 + 1.211010-2-2(w(w1 1 w w2 2) () (美元美元a)a)根据上面的假设条件，经过整理得到线性规划问题: minC minCC C1 1 + C

60、C2 2 151510104 4+1.21+1.211010-2-2w1-1.21w1-1.21* *1010-2-2w2w2 +6.02 +6.021010-3-3w3-6.02w3-6.021010-3-3w4w4 s st t w1-w1-w4 41.359;1.359; 0.25w2-w3 0.25w2-w30;0; w1- w1-w20;20; w3-w40; w3-w40; w40.453; w40.453; w21.7 w21.7 w1,w2,w3,w40 w1,w2,w3,w40 用用MatlabMatlab编程求解编程求解: :目标函数中的常数项在求解过程中可目标函数中的常数