下载文档原格式
《最优化理论》课程教学大纲一、课程基本信息
二、课程目标及对毕业要求指标点的支撑
三、教学内容及进度安排
四、课程考核
五、教材及参考资料
教材：《最优化理论与算法（第2版）》,陈宝林著，清华大学出版社，2005年，ISBN：97873021137680
参考书：
1、《最优化方法》，孙文瑜、徐成贤、朱德通主编，高等教育出版社，2004年第一版,ISBN：9787040143751o
2、《最优化理论与方法》，袁亚湘，孙文瑜著，科技出版社，2010年（第二版），ISBN：9787030054135o
3、《最优化计算方法》，黄正海，苗新河著，科技出版社，2015年（第二版），ISBN：9787030433053o
六、教学条件
本课程属于基础理论与应用型课程，对实验条件要求不是很高。
学校实验大楼拥有的计算机软硬件资源，高性能计算机，投影仪等设备，基本能够完成所需的理论计算任务、数值模拟试验以及程序测试等。
需要使用多媒体教室授课，授课电脑安装了WindoWS7、
OffiCe2010、1ingo11Python>Mat1ab2015>Mathematica11>MathTyPe6.9以上版本的正版软件。
附录：各类考核评分标准表。
高效求解三维装箱问题的剩余空间最优化算法一、本文概述随着物流、制造业和计算机科学的快速发展，三维装箱问题（Three-Dimensional Bin Packing Problem, 3D-BPP）已成为一个备受关注的研究热点。
该问题涉及如何在有限的三维空间内，以最优的方式放置形状和大小各异的物体，以最大化空间利用率并减少浪费。
在实际应用中，如货物装载、仓库管理、集装箱运输等领域，高效求解三维装箱问题具有重大的经济价值和社会意义。
本文旨在研究三维装箱问题的剩余空间最优化算法，通过对现有算法的分析与改进，提出一种高效且实用的解决方案。
我们将对三维装箱问题进行详细定义和分类，阐述其在实际应用中的重要性和挑战性。
然后，我们将综述目前国内外在该领域的研究现状和进展，分析现有算法的优势和不足。
在此基础上，我们将提出一种基于启发式搜索和优化策略的剩余空间最优化算法，并通过实验验证其有效性和性能。
本文的主要贡献包括：1）对三维装箱问题进行系统性的分析和总结；2）提出一种新型的剩余空间最优化算法，以提高空间利用率和求解效率；3）通过实验验证所提算法的性能，并与其他先进算法进行比较和分析。
本文的研究成果将为三维装箱问题的求解提供新的思路和方法，有助于推动相关领域的理论研究和实际应用。
本文所提算法在实际应用中具有较高的推广价值，有望为物流、制造业等领域带来显著的经济效益和社会效益。
二、相关文献综述装箱问题，特别是三维装箱问题（3D Bin Packing Problem,3D-BPP），一直是计算机科学和运筹学领域研究的热点和难点。
随着物流、制造业等行业的快速发展，对装箱算法的效率和性能要求日益提高。
剩余空间最优化作为装箱问题中的一个重要目标，对于提高空间利用率、降低成本和减少浪费具有重要意义。
近年来，众多学者对三维装箱问题的剩余空间最优化算法进行了深入研究。
传统的启发式算法，如最先适应算法（First Fit）、最佳适应算法（Best Fit）和最差适应算法（Worst Fit）等，虽然简单直观，但在处理大规模或复杂装箱问题时往往效果不佳。
1.城市环境综合整治定量考核制度是考核市政府。
2.宏观环境管理：从综合决策入手，解决发展战略问题，实施主体是国家和地方政府。
3. 微观环境管理：从执法监督入手，解决具体的污染防治和生态破坏问题，实施主体是环保部门。
4. 环境管理基本任务：转变人类社会的一系列基本观念和调整人类社会行为5 人类行为：政府行为、企业行为、个人行为6.系统优化分析通常是通过最优化数学模型实现的。
最优化的方法目前最常用的最优化方法有线性规划、动态规划与网络分析等。
7. “减量化、再使用、再循环”为经济活动的准则(称为3R 原则)P192 (考点) 8.组成9.通过隶属度大小来评价环境质量的方法(含糊数学法)10.城市垃圾产生量预测：常采用排放系数预测法、回归分析法、灰色预测法11.水环境规划是协调(人类社会经济发展与水资源保护)之间关系的重要途径和手段。
12.在环境管理手段中，行政手段具有(强制性、权威性、规范性)13.均匀处理最优规划：均匀处理最优规划，以全区域的污水处理费用最低为目标，寻求污水处理厂的位置与规模的最佳组合。
14.水环境容量的大小与(水体特征、污染物特性、水质目标、排污方式)有关15. A 值法属于地区系数法16.环境管理的三大主要方法：17 同时选择近10 年最枯季平均流量或者近10 年最枯季平均库容作为参考设计水文条件。
是指以人为中心的所有周围事物的总称。
大气污染问题；水环境污染问题；垃圾处理问题；土地荒漠化和沙灾问题；持久性有机污染问题；三峡库区的环境问题对环境系统的发展变化趋势进行研究而对人类自身活动和环境所做的时间和空间的合理安排是对伤害环境质量的人类活动施加影响，协调发展与环境的关系，达到既发展经济满足人类基本需要，又不超出环境允许极限的一切措施的总称。
经济制约型：满足经济发展的需要，环境保护只服从于经济发展的要求；协调型：既考虑经济对环境的影响，也考虑环境对经济发展的制约关系；环境制约型:经济发展要服从环境质量的要求按环境要素分:大气、水、固体废弃物、噪声污染控制规划;按行政区域和管理层次:国家、区域和部门环境规划按性质上划分:生态规划、污染综合防治规划、自然保护规划、科学技术与产业发展规划环境管理的范围来划分：流域环境管理、区域环境管理、行业环境管理、部门环境管理环境管理的性质分：资源环境管理、质量环境管理 (以环境质量评价和环境监测为内容的环境管理)、技术环境管理按环保部门的工作领域来分：环境规划管理、建设项目环境管理、环境监督管理可持续发展的原则、全过程控制原则、环境经济的双赢原则、公众参预原则可持续发展的原则：可持续性原则；公平性原则；共同性原则；.需求性原则10 在处理利益冲突的双方关系时，使双方都得利，而不是牺牲一方利益而保证另一方获利。
最优化方法结课作业年级数学121班学号201200144209 姓名李强1、几种方法比较无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。
这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。
（直接法：又称数值方法，它只需计算目标函数驻点的函数数值，而不是求其倒数，如坐标轮换法，单纯型法等。
间接法：又称解析法，是应用数学极值理论的解析方法。
首先计算出目标函数的一阶或一阶、二阶导数，然后根据梯度及海赛矩阵提供的信息，构造何种算法，从而间接地求出目标函数的最优解，如牛顿法、最速下降法共轭梯度法及变尺度法。
）在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。
根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。
一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。
一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。
由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。
在多变量函数的最优化中,迭代格式Xk+1=Xk+akdk其关键就是构造搜索方向dk和步长因子ak设Φ(a)=f(xk+adk)这样从凡出发,沿搜索方向dk,确定步长因子ak,使Φ(a)<Φ(0)的问题就是关于步长因子a 的一维搜索问题。
其主要结构可作如下概括:首先确定包含问题最优解的搜索区间，然后采用某种分割技术或插值方法缩小这个区间，进行搜索求解。
一维搜索通常分为精确的和不精确的两类。
如果求得ak使目标函数沿方向dk达到极小,即使得f (xk+akdk)=min f (xk+ adk) ( a>0)则称这样的一维搜索为最优一维搜索,或精确一维搜索,ak叫最优步长因子;如果选取ak使目标函数f得到可接受的下降量,即使得下降量f (xk)一f (xk+akdk)>0是用户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维搜索。
由于在实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到这一点,因为精确的一维搜索需要付出较高的代价,而对加速收敛作用不大,因此花费计算量较少的不精确一维搜索方法受到了广泛的重视和欢迎。
精确一维搜索,作为一种理想的状态,虽然在实际计算中被采用的概率较之不精确一维搜索要小,但有关精确一维搜索技术的研究历史悠久成果相当丰富,方法众多,其理论体系也相对比较完备,对其进行进一步的研究仍有着重要的理论意义和现实意义。
通常我们根据算法中有无使用导数的情况,将精确一维搜索算法分为两大类:一类是不用函数导数的方法,这其中就包括二分法(又称作对分法或中点法)、0.618法(黄金分割脚、Fibonacci法(分数法)、割线法、成功一失败法等;另一类是使用函数导数的方法,包括经典的Newton法、抛物线法以及各种插值类方法等。
（1）在不用导数的方法中,二分法、0.618法(黄金分割法)以及Fibonacci法均是分割方法,其基本思想就是通过取试探点和进行函数值比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近函数的极小值,从而各点均可看作极小点的近似。
分割类方法仅需计算函数值,因此使用的范围较广,尤其适用于非光滑及导数表达式复杂或写不出等情形。
二分法是一种最简单的分割方法,每次迭代都将搜索区间缩短一半,故二分法的收敛速度是线性的,收敛比为0.5,收敛速度较慢。
其优势就是每一步迭代的计算量都相对较小,程序简单,而且总能收敛到一个局部极小点。
黄金分割法是一种针对目标函数是单峰函数亦即目标函数为凸的情形的分割类方法,因其不要求函数可微,且每次迭代只需计算一个函数值,程序简单容易实现而被广泛采用。
由于黄金分割法是以等比例τ=0.618分割缩小区间的,因此它是一种近似最优方法。
针对在实际中遇到的目标函数往往不是单峰函数的情况,HPonfiger(1976)提出了.0618法的改进形式,即在缩小区间时,不只是比较两个内点处的函数值,而是对两内点及其两端点处的函数值进行综合比较,以避免搜索得到的函数值反而比初始区间端点处的函数值大的情况。
经过这样的修改,算法比.0618法要更加可靠。
Fibonacci法是另一种与.0618法相类似的分割类方法,两者的主要区别在于Fibonacci法搜索区间的缩短比率不是采用黄金分割数τ,而是采用Fibonacci数列。
在使用Fibonacci法时,通常是由用户给定最终区间长度的上限,从而确定探索点的个数,逐步进行搜索。
通过对Fibonacci数列进行分析表明,在迭代次数n趋于无穷的情形。
Fibonacci法与.0618法的区间缩短率相同,因而Fibonacci法的收敛速度也是线性的,收敛比也是黄金分割数τ。
可以证明,Fibonacci法是分割方法求解一维极小化问题的最优策略,而0.618法只是近似最优的,但因0.618法不必预先知道探索点的个数,程序实现更加容易,因而应用也更加广泛。
抛物线法也可称作三点二次插值法,其基本思想与下面要叙述的牛顿法相同,也是用二次函数近似目标函数,并以其极小点去近似目标函数的极小点,不同之处是牛顿法是利用目标函数fx()在x0处的二阶Tyalor展式来逼近f(x),而抛物线法则是利用目标函数fx()在三个点x0,xl,xZ处的函数值构造一个二次函数作为其近似。
一般地,抛物线法并不能保证算法一定收敛,在迭代过程中有可能会出现相邻迭代点xk，xk+1充分接近且xk+1并非函数近似极小点的退化情况。
但在己知迭代点列收敛到目标函数极小点的情况,可以证明:在一定的条件下,抛物线法是超线性收敛的,收敛的阶约为1.3。
割线法与分割法类似,也是通过取试探点和进行函数值比较,使包含所求点的搜索区间缩小,但试探点的取法与分割法不同,它是选取连接两个端点的线段与横轴的交点作为试探点。
割线法不能保证每次都使搜索区间缩小一定的比例,因而不具有全局线性收敛性,但是它却利用了函数的一些性质。
在函数接近线性时,它是非常快的。
如果函数本身是线性函数时,它可以一步找到解。
(ii)一般地,使用导数的方法通常包括牛顿法、插值法等,其中插值法又有一点二次插值法(牛顿法)、二点二次插值法)、三点二次插值法以及三次插值法、有理插植法等常用方法。
求一维无约束极小化问题的牛顿法是从计算方法中方程求根的牛顿法演化而来的,其基本思想是用目标函数f (x)在己知点x0处的二阶Tylor展式g (x)来近似代替目标函数,用g (x)的极小点作为f (x)的近似极小点,迭代公式是牛顿法的优点是收敛速度快,具有局部二阶收敛速度;缺点是要在每个迭代点处计算函数的二阶导数值,增加了每次迭代的工作量,而且它要求迭代初始点要选的好,也就是说初始点不能离极小值太远,在极小点未知的情况下,做到这一点是很困难的,这就限制了算法的应用范围,导致算法不实用。
事实上,牛顿法也是插值类方法的一种。
插值法是一类重要的一维搜索方法,其基本思想是在搜索区间内不断用低次(通常不超过三次)多项式来逼近目标函数,并用插值多项式的极小点去近似目标函数的极小点。
实践表明,在目标函数具有较好的解析性质时,插值方法比直接方法(如.0618或Fibonacci法)效果更好。
所谓不精确一维搜索方法是指应用各种可接受的步长选择律的线性搜索方法。
常用的不精确一维搜索算法包括利用简单准则的后退方法、经典的Armijo-Goldstein方法、Wolfe-Powell 方法和强Wolfe-Powell方法、以及其后发展起来的利用Curry-Altman步长律、改进的Curry-Altman步长律、Danilin-Pshenichuyi步长律、De Leone-Grippo步长律、Backtracking步长律等的各种方法坐标轮换法：可靠性较高，算法效率太低，操作方便，一般只用于低维问题，n<10 鲍威尔法：可靠性高，算法效率较高，操作较复杂，一般适用于n<10~20的问题梯度法：可靠性较高，算法效率低，操作方便用于低维、低精度的问题。
牛顿法：可靠性低，算法效率高，操作不方便，很少用。
变尺度法：可靠性高(BFGS比DFP更高)，算法效率高,使用较复杂,适用于高维问题2、牛顿法如前面所提到的，最速下降法在最初几步迭代中函数值下降很快外，总的说来下降的并不快，且愈接近极值点下降的愈慢。
因此，应寻找使目标函数下降更快的方法。
牛顿法就是一种收敛很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极小值点来近似原目标函数的极小值点并逐渐逼近改点。
一维目标函数()f x 在()k x 点逼近用的二次曲线（即泰勒二次多项式）为()()()()()()21()()()()()()2k k k k k k x f x f x x x f x x x ϕ'''=+-+- 此二次函数的极小点可由()()0k xϕ'=求得。
对于n 维问题，n 为目标函数()f X 在()k X点逼近用的二次曲线为：()()()()()2()()1()()().[][].().[]2k k k k k T k k X f x f X X X X X f X X X ϕ⎡⎤=+∇-+-∇-⎣⎦令式中的Hessian 2()()()()k k f XH X ∇=，则上式可改写为：()()()()()()()1()()().[][].().[]2()k k k k k T k k X f x f X X X X X H X X X f X ϕ⎡⎤=+∇-+--⎣⎦≈当()0X ϕ∇=时可求得二次曲线()X ϕ的极值点，且当且仅当改点处的Hessian 矩阵为正定时有极小值点。
由上式得：()()()()()()[]k k k X f X H X X X ϕ∇=∇+-令()0X ϕ∇=，则()()()()()[]0k k k f X H X X X ∇+-=若()()k H X为可逆矩阵，将上式等号两边左乘1()()k H X -⎡⎤⎣⎦，则得1()()()()()[]0k k k n H X f X I X X -⎡⎤∇+-=⎣⎦整理后得1()()()()()k k k X XH X f X -⎡⎤=-∇⎣⎦当目标函数()f X 是二次函数时，牛顿法变得极为简单、有效，这时()()k H X 是一个常数矩阵，式()()()()()()()1()()().[][].().[]2()k k k k k T k k X f x f X X X X X H X X X f X ϕ⎡⎤=+∇-+--⎣⎦≈变成精确表达式，而利用式1()()()()()k k k X X H X f X -⎡⎤=-∇⎣⎦作一次迭代计算所得的X 就是最优点*X 。
