最优化计算方法

最优化计算方法传算法和人工神经网络等,每章都配备了一定数量的练习题,并提供了较为详尽和具体的参考文献、本教材是作者在多年讲授工学硕士生“最优化计算”和工学博士生“智能计算方法”的基础上集体讨论编写而成的.第一篇由潘少华博士执笔,第二篇和第三篇第十三章由蒋金山博士执笔,第三篇笫十章第十一章和第十二章由何春雄博士执笔.由于编者知识和能力所限,谬误与不足之处有待在教学实践中加以更正和补充,也恳请读者不吝赐教编者2007年8月于华南理工大学数学科学院目录第一篇线性规划第1章线性规划的数学模型和基本对偶关系……性质……………………………13.2对偶性定理……………1.1线性规划问题及其数学模型13.3对偶单纯形法………………531.1.1问题的提出……………………13.3.1对偶单纯形法的基本1.1.2线性规划问题的数学模型…3思路……………531.2线性规划问题的图解法…3.3.2对偶单纯形法的计算1.2.l图解法的步骤步骤……531.2.2线性规划问題求解的几种3.3.3初始对偶基本可行解的可能结果……………求法…1.3线性规划的基木性质8习题1.3.1线性规划的基本概念……8第4章灵敏度分析和参数线性1.3.2凸集与凸集的顶点………10规划……………611.3.3线性规划的基本定理…114.1灵敏度分析………习题…………………………134.1.1参数c的灵敏度分析…6l第2章单纯形法……54.1.2参数b的灵敏度分析…632.1单纯形法的原理152.1.1确定初始基本可行解154.1.3约束条件的系数列向量A的灵敏度分析2.1.2最优性检验和解的判别……164.1.4增加一个新变量xn+1的2.1.3从一个基本可行解转换分析65到相邻且改善了的基本4.1.5增加一个新约束条件的可行解……19分析………672.2单纯形法的计算步骤……204.2参数线性规划…692.3人工变量的处理方法…25习题…732.3.1大M法………26第5章线性规划应用实例762.3.2两阶段法…………………285.1套裁下料问题……7624单纯形法的有限终止性305.2配料问题…772.5改进单纯形法……………335.3生产工艺优化问题…792.5.单纯形法的矩阵描述…335.4多周期动态生产计划问题……802.5.2改进单纯形法……355.5有配套约束的资源优化问题习题…405.6投资问趣…………………82第3章线性规划的对偶理论白晶。血击血虚b由435.6.1投资项目组合选择…3.1线性规划的对偶问题●●●●。4●着D435.6.2连续投资问题3.1.1对偶问题的提出……435.7运输问题及其扩展…3.1.2原问题与对偶问题之间的5.7.1产销平衡的运输问题85最优化计算方法5.7.2产销不平衡的运输问题……86题885.7.3有转运的运输问题…87第二篇非线性规划第6章非线性规划基本概念与基本7.3抛物线逼近法………………114原理………………………917.3.1经过三点(x1,∫(x1))、6.1非线性规划的数学模型和基本(x2,f(x2))和(x3,∫(x3))概念……售●D鲁●香91作抛物线φ(x)1146.1.1非线性规划问题举例………917.3.2用抛物线p(x)的极小点作6.1.2非线性规划问题的一般为f(x)的近似极小点…114数学模型……………927.3.3迭代1156.1.3基本概念…9374外推内插法6.2凸函数和凸规划………………967.4.1基本原理与步骤…1156.2.1凸函数定义与性质………9674.2计算举例1166.2.2凸函数的判别…………99习题1176.2.3凸规划…101第8章无约束问题最优化方法1186.3无约束问题的极值条件1018.1变量轮换法……1186.3.1用海赛矩阵判断驻点的8.1.1基本原理…………118性质……1028.1.2算法步驟…·自非咖非命41186.3.2极值点的必要条件和8.1.3计算举例………19充分条件10282模式搜索方法……1206.4下降迭代算法………………1048.2.上探测移动…………………1216.4.1下降迭代算法的概念…1048.2.2模式移动……216.4.2下降方向与可行下降8.2.3算法的基本思想………121方向1058.24算法终止准则…………1216.4.3下降迭代算法的一般8.2.5算法步骤122步骤……………10582.6计算举例…12264.4算法终止条件1068.3可变单纯形法………………124习题…………………10783.1基本原理和步驟………124第7章一雏搜索………………10883.2计算举例自。··曲司·看●D垂1257.1黄金分割法…1088.4最速下降法看音b鲁1267.1.1单谷函数及其性质……10884.1基本原理与步骤…1277.1.2黄金分割法基本原理8.4.2计算举例…………127与步骤8.4.3最速下降法性能分析…12872牛顿法.44‘·:÷·4·4··1128.5牛顿法……………………1297.2.1牛顿法的基本原理……1128.5.1牛顿法基本原理…1297.2.2牛顿法的算术步骤11385.2阻尼牛顿法及其计算7.2.3计算举例………………113步骤………131目录8.5.3计算举例………1319.2.1线性近似规划的构成…1508.6共轭梯度法……………1329.2.2近似规划法的算法8.6.1基本概念和基本原理……132步骤……………………………1518.6.2正定二次函数的共轭梯9.23计算举例………151度法··1349.3可行方向法…中·q鲁曹·自“·自身.·1538.6.3正定二次函数共軛梯度9.3.1基本原理与算法步骤154法的计算步驟…1369.3.2计算举例1558.6.4计算举例1369.4罚函数法1578.6.5用于一般函数的共轭梯9.4.1外点法…………………………157度法…鲁中中·鲁1389.4.2内点法1618.7拟牛顿法…………………1389.4.3混合法1638.7.1拟牛顿条件1399.5乘子法……………………1658.7.2DF法1399.5.1只有等式约柬的问题…1658.7.3DFP变尺度法的计算9.5.2只有不等式约束的步骤……140问题……………………167874计算举例…14I9.5.3同时含有等式约束与不等习题………。曲·曲●。啬自。D。D。142式约束的问题……170第9章约束问题最优化方法…14496二次规划……………………1709.1约束优化问题的最优性条件…1449.6.1二次规划的基本概念与9.1.1基本概念………………144基本性质……………………1709.1.2Kuhn- Tucker条件(一阶9.6.2等式约束二次规划问题…172必要条件)…………1469.6.3有效集法……………………1769.1.3关于凸规划的全局最优解9.6.4对偶问题…………………180定理……………………14996.5二次规划的应用—支持9.1.4二阶充分条件………………149向量机简介1809.2近似规划法……150习题…183第三篇现代最优化算法第10章最优化问题概论18610.4启发式算法…4●··曲申自te非鲁自·曲鲁19510.1最优化问题…18610.4.1启发式算法的概念………19510.1.1函数优化问题………18610.4.2启发式算法的分类……19710.1.2组合优化问题·自售看。D…18710.4.3启发式算法的性能10.2计算复杂性与NP完全分析…………198问题……18810.5小结与注记9910.2.1计算复杂性的概念……188习题……………………20010.2.2 NP, NP-C fu NP-hard第11章模拟退火算法……………201概念…19111.物理退火过程与SA算法10.3邻域概念…195的马氏链描述……………201最优化计算方法11.1.1物理退火过程与 Metropolis性分析看。阜鲁鲁·鲁·即···导D··鲁248准则●看看看鲁鲁個即即看曹日身即··0112.5遗传算法的技实现………·2511.1.2物理退火过程的统计力学12.5.1编码方業的确定…………251模型……………………20212.5.2遗传算法的性能评估……2521.1.3SA算法的基本步骤……20312.5.3初始参数的选取和停止11.1.4SA算法的马尔科夫原则…253( Markov)链描述……20512.5.4控制参数的选取和进化112马尔科夫链简介…………206技术…………………25411.3时齐算法的收敛性…看自·D■备21012.6遗传算法的改进与注记………258114非时齐SA算法的习题………………………259收敛性简介p争·鲁中P自鲁■…215第13章人工神经网络…26011.5SA算法实现的技术问题21713.1概述……26011.5.1初温的选择…21713.2人工神经网络的基本概念…26111.5.2时齐SA算法的退温过程13.2.1基本人工神经网络控制方法……………219模型……………26111.5.3时齐SA算法各温度下的13.2.2人工神经网络的学迭代长度规则…………221习算法…26111.54SA算法的停止准则…22213.2.3人工神经元及感知11.5.5组合优化问题解的形式和器模型………………262邻域结构设计。。··垂…22213.3前馈神经网络及其主要11.6改进SA算法及注记……223算法…………………………266习题22413.3.1多层前馈网络…267第12章遗传算法……22513.3.2反向传播算法(BP12.1遗传算法的基本概念与计算算法)……………267流程··申最p·鲁4◆22513.4自组织映射神经网络……●鲁一26912.1.1遗传算法的基本概念……2253.4.1竞争学习…………26912.1.2遗传算法的计算流程……22713.4.2自组织特征映射……27012.2遗传算法的数学模型…228135反馈型神经网络…271l12.2.1生物进化概念的数学13.5.1离散 Hopfield网络…272描述……22813.5.2连续 Hopfield网络鲁鲁p看鲁T22.2遗传机制的数学描述……23013.6人工神经网络应用案例……27812.3遗传算法的模式理论…23813.6.1自组织网络用于模式12.3.1模式与遗传算子……238识别……………………27912.3.2模式定理…242136.2 Hopfield人工神经网络12.4遗传算法的收敛性分析……246在TSP中的应用27912.4.1矩阵序列的收敛性与习题………282马氏链·▲D■自d鲁啁·鲁·●……246参考文献…●D●●●鲁283124.2标准遗传算法的收敛第一篇线性规划第1章线性规划的数学模型和基本性质线性规划是理论和求解方法都比较成熟,且具有广泛应用的一个运筹学分支.本章介绍它的数学模型并讨论其基本性质1.1线性规划闷題及其教学棋型1.1.1问题的提出在生产管理和经营活动中,经常会遇到这样两类问题:一类是如何合理地使用有限的劳动力、设备资金等资源以获得最大的利润;另一类是为了达到一定的目标,应如何组织生产,或合理安排生产工艺流程,或调整产品的成分…以使消耗的资源(人力、设备台时、资金、原材料等)为最少例1-1某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素生产每吨药品所需要的维生素量所占用的设备时间,以及所获得的利润见表1-1.已知该厂每周所能得到的维生素量为160kg,每周设备最多能开15个台班,而且根据市场需求,甲种产品每周产量不应超过4L.试问该厂应如何安排两种产品的每周产量以使获取的利润最大?毫1-1甲乙每天可用能力维生素/kg20160设备/台班利润/万元解设该厂每局安排生产甲、乙两种药品的产量分别为x1(t)和x2(t),则每周所能获得的利润总额为z=5x1+2x2(万元)但生产量的大小要受到维生素量设备的台班和市场最大需求量的限制,即x1和x2要满足下述一组不等式条件30x1+20x2≤1605x1+x2≤152第一篇线性规划另外,x1和x2显然只能取非负值,故有≥0于是,问题可以写成下列数学形式max z = 5xt +2x?s.t.30x1+20x,≤1605x1+x2≤15≤4x1≥0其中,maxz=5x1+2x2表示要求函数z=5x1+2x2达到最大,s.t.为英文“ subject to”(受约東于)的缩写.因此,要求在上面所列出的全部条件下,求x1和x2的一组值,使函数z=5x1+2x2达到最大例1-2某公司经销种产品,现要将三个生产点A1(=1,2,3)生产的产品分别运往四个销售点B(=1,2,3,4)已知三个生产点的每日产量各销售点的每日销量,以及每吨产品从各生产点到销售点的运价见表1-2试问该公司应姐何调运产品,可在满足各销售点需要量的前提下,使总运费最少?表1-2运价(元/)销售点B生产点ABB.B3B生产量(t)A4310A94108需求量(t)35解设从生产点A到销售点B的调运数量为x(t),则总运费为z=4x1+1lx12+3x13+10x14+x1+92+2x23+8x24+7x3+4x2+10x3+5xy我们的目标是在一定条件下使函数z达到最小值由于从各生产点运出的数量不能超过它的产量,故应有12x1a≤5x21+x22+x2+x24≤7x32+x33同时,还应保证各销售点所需产品都得到满足,因此有ut t 221 t x3+x2+x2x13+x23+x3=58此外,调运量x;(i=1,2,3;j=1,2,3,4)都应取非负值:第1章线性规划的数学模型和基本性质≥0(i=1,2,3;j=1,2,3,4)于是,问题可写成下列数学形式:minz=4xnt+11x12+3x13+10x14+x21+9x2x23+824+7x31+4x+10x33+5x4s.t.x1+x12+x13+x14≤5+x2+x3+x4≤7+x33+x3+x4≤8(1-2)11x12+x22+xg2=4x13+x23+x3=5x1A+4十x三14(i=1,2,3;j=1,2,3,4)注意到,此问题中三个生产点的生产总量恰好等于四个销售点的需求总量,因此,要保证各个销售点的需求量都得到满足,三个生产点的生产量应全部运走.故,式(1-2)中的三个不等式也可以改写成等式在上述两个例题中,都首先要确定一组具有明确含义的变量,称之为决簟变量.问题的目标是选取这些决策变量的值使得一个函数取得最大值或最小值,此函数称之为目标函数我们又利用决策变量把问题的条件表示成等式或不等式,并称这些等式和不等式为约束条件.如果目标函数是决策变量的线性函数,而且约束条件也都是关于决策变量的线性等式或线性不等式,则相应的数学问题就称为一个线性规划问题.显然,上述两个例子都是线性规划问题1.1.2线性规划问题的数学模型从实际问题得到的线性规划模型是多种多样的,为了方便讨论,规定下列形式的线性规划为标准型:minz=∑cs1.∑anx=b(讠=1,2,…,m)(1-3)≥0(j=1,2,…,n)其中b2≥0(i=1,2,…,m).也就是说,以后谈及的标准型线性规划都是指对目标函数一律求最小值;决策变量一律要求为非负变量;约束条件除非负约束条件外一律为等式约束;的束条件的右端项一律非负定义如下矩阵和向量lAAAA