第10章最优化问题程序设计方法.ppt

第十章 最优化问题程序设计方法;§10.1 最优化问题建模一般步骤; 二、选择合适的优化方法 各种优化方法都有各自的特点和一定的适用场合．根据具体的最优化问题，适当地选择优化方法才会有较好的效果． 选择优化方法时，主要考虑的因素是：目标函数的维数与连续性；它的一阶、二阶偏导数是否存在，是否易于求得；约束条件是等式约束，还是不等式约束或两者兼有等不同情况． 一般地，对于维数较低的问题应选用结构简单、易于编程的方法．对于维数较高的问题，效率就显得十分重要，应选择收敛速度较快的方法，对于求导困难或导数不存在的优化问题应选用直接法． ; 三、制订流程图和编写源程序 为了使所编写源程序有个正确的思路，必须先根据具体最优化问题制定一个较详细的流程图．该图应反应优化计算的步骤及各种运算之间的逻辑关系．流程图既便于程序的编制，又便于使用者对程序的阅读． 编写源程序是一种技巧较高而且很细致的工作．即使是一个较为简单的最优化问题，也需要考虑许多方面的因素．若某些优化方法已有比较成熟的源程序，应尽量优先采用，以期缩短编程时间和提高计算的可靠性与有效性．; 一个新编制的程序，即使在编写过程中已经作过周密的考虑，也很难在计算机上一次通过，总会发生这样或那样的障碍，可能是语法规则方面的错误，也可能是运行错误等等．因此，新编程序必须经过调试和试算后才能确认它的正确性． 试算是必要一环，所谓试算，是用一个比较简单的、已经作好标准答案的题目用编好的源程序运算，观察结果是否正确，以期检查程序的正确性，试算通过后再作正式计算，其结果就比较可信了． ; 分析优化结果的目的在于考证优化结果的正确性与实用性．尽管最优化方法本身是一种科学方法，是可以信赖的．但由于实际工程问题的复杂性和某些算法在研究上的不完善性，或由于设计者在建模中失误与疏忽，都会导致计算结果与实际情况不相符，甚至有时是荒谬的．所以对优化结果要进行分析．如果经分析，发现计算结果存在问题，则需寻查原因，进行调整，修改，直至获得完全符合实际情况为止． 最后还需指出，一般情况下通过优化计算所得的最优解只能保证是一个局部最优解．只有凸规划问题的局部最优解才是全局最优解．为了得到全局最优解，只要多选几个分布在不同位置的初始点进行优化计算．若所得各解都归于同一解上去，可认为所得解为全局最优解，否则应从这些解中择其目标函数最小者做为全局最优解． ;§10.2常用最优化方法的特点及选用标准; （二）有效性 这是指算法的解题效率而言的．有效性常用两种衡量标准．其一是用同一题目，在相同的精度要求和初始条件下，比较占用机时数多少．其二是在相同精度要求下，计算同一题目获得最优解时所需要的计算目标函数值次数及导数值次数． （三）简便性 简便性包括两个方面的含意．一方面是指实现这种算法人们所需要的准备工作量的大小．例如，编制程序的复杂程度，程序调试出错率的高低，算法中所用调整参数的多少等等．另一方面是指算法所占用存贮单元的数量，如果某些算法占用单元数很大，就会对机型提出特殊要求，显然这对使用者是不方便的． ; 由上面的三个评价准则可以看出，要断然地肯定某算法最好或最坏是不可能的．因为各种算法就上面三个准则作评价时一般是各有长短，而且由于目标函数的多样性，各种算法对不同目标函数所体现出来的准则衡量结果也有差异．因此算法的评价实际上是一个比较复杂的问题． 下面分别就常用无约束方法和常用约束方法作一概略评论，以供参考．;一、常用无约束最优化方法评价准则 表10.1是几种常用无约束方法的比较．;二、常用约束最优化方法评价标准 表10.2列出了几种常用约束方法的比较 ;§10.3 最优化问题编程的一般过程; 二、编制程序 (1) 先画出代表整个计算流程的总框图．如有必要再画出有关局部过程的详细框图．对较大的最优化问题，它给出了整个构思及各分支的相互联系，是必不可少的一步，但有些人忽视这点．当然框图也不宜过于详细，否则，反而主次不分，起不到应有作用． (2) 根据框图，按算法语言规定逐条编写设计程序．特别要强调的是对一个程序必须多次反复核对，每一个符号都要认真对待．程序结构有两种：整体式或积木式，一般简单的程序采用只有一个主程序的整体式结构比较简便明了．对于大型复杂的最优化问题编程一般采用模块式（积木式）程序设计方法．这样主控程序就可以较短，基本体现出总框图的思路，主控程序中需要用到有关的子程序时，只要调用它就行了．模块式程序设