张灿最优化理论

1、大作业封面模板理学院最优化理论课程设计学 号：xxxxx专 业：应用数学学生姓名：xxxx任课教师：xxxx教授 2015年10月摘 要针对本学期对于最优化理论的学习，我们学到了很多东西，本文主要对于动态规划这一思想的核心内容和其基本特点，探讨了动态规划思想的适用范围，通过数学建模的思维，构建Matlab程序语言，解决实际问题。本文总结指出，动态规划这一思想，关键还在于对不同的问题建立有效的数学模型，在把握本质的基础上灵活运用。本文对Matlab软件作了简要的介绍, 并使用其优化工具函数mixfy编写程序, 计算最优决策序列和总利润的最大值,实现资源的优化配置, 具有良好的通用性、有效性和简便

2、性, 并能够简便快速分析与计算出资源优化配置的结果, 为作出正确的决策提供了切实有效的方法。最优化理论的灵活运用，解决多阶段决策过程最优化问题，将复杂问题全局化，简洁的把结果呈现出来，方便及快捷。关键字 最优化理论 动态规划 数学建模 Matlab软件 一 课题背景及研究意义1 最优化理论综述最优化理论是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优，以及怎样找到最优方案。概括的说，凡是追求最优目标的数学问题都属于最优化问题，作为最优化问题，一般都有三个要素：第一是目标；第二是反感；第三是限制条件，而且目标应是方案的“函数”。如果方案与时间无关，则该问题属于静态最优化问

3、题，否则称为动态最优化问题1。关于最优化的问题在生活中普遍存在，例如，工程设计中怎样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，

4、有利于战争的全局，在人类活动的各个领域中，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。通过本学期对于最优化理论的学习，我们学到了很多东西，主要针对以下的五个方面：（1） 基本的线性规划问题，它是最优化问题的一种特殊情形，实质是从多个变量中选取一组适当的变量作为解，使这组变量满足一组确定的线性式，而且使一个线性目标函数达到最优（最大或最小），熟练的将原问题化为标准形式，或引入人工变量进行转化，利用单纯形法使可行域中的某个基可行解转换为另一个基可行解，直到目标函数达到最优，基可行解即为最优解；或研究对偶问题的实际经济意义，

5、例如资源分配下的工厂利益最大的问题的讨论，将原线性规划问题转换为对偶问题，从一个角度分析使问题更易求解。（2） 一维搜索法：通过构造一个搜索方向和确定一个步长，使下一个迭代点所处的目标函数值下降的方法，分别采用了对分法，Newton切线法，黄金分割法，抛物线插值法等进行求最优解。（3） 常用无约束最优化方法：可直接用来求解无约束优化问题，也可将很多约束优化问题转化为无约束优化问题，用无约束的方法进行求解，采用多种方法：最速下降法，以一个给定的初始点出发，通过迭代公式，按照特定的算法产生一串点列，则收敛的点列为其最优解；Newton法，为了寻求迭代速度快，用一个二元函数来近似该点处的目标函数，其

6、极小点的方向构造搜索方向；修正Newton法，克服Newton法的缺点，保留Newton方向作为搜索方向，摒弃步长恒取1，用一维搜索确定最优步长；共轭方向法，它是一种对初始点要求较为严格的收敛速度不宜过快的新算法，相比下最速下降法收敛速度降低，Newton法收敛速度快，但计算量大；共轭梯度法：通过由共轭方向的迭代点的负梯度与共轭向量的线性组合确定，构成一种具体的共轭方向法等等的一系列方法。（4） 动态规划：同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一

7、种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。（5） 通过学习最优化理论的课程，在最优序列的应用实例中，我熟练的运用各种方法求最优解，建立符合问题的数学模型，学会使用Matlab软件及其优化工具函数mixfy编写程序解决实际问题，计算最优决策序列和总利润的最大值的方法和技巧，对运用计算机软件完成课程的波形绘制，微分方程的求解及数据处理，学习动态规划的基本方法，实现资源的优化配置，其具有良好的通用性，有效性和简便性，并能够简便快速分析与计算出资源优化配置的结果，为实际解决提供切实有效的方法。关于最优化理论的经典算法和分类

8、情况众多，本文主要研究动态规划问题的解决方法,主要对于动态规划这一思想的核心内容和其基本特点，探讨了动态规划思想的适用范围，通过数学建模的思维，构建Matlab程序语言，解决实际问题。本文总结指出，动态规划这一思想，关键还在于对不同的问题建立有效的数学模型，在把握本质的基础上灵活运用。2 动态规划理论综述2.1 课题背景动态规划是一种重要的程序设计思想，具有广泛的应用价值。使用动态规划思想来设计算法，对于不少问题往往具有高时效，因而，对于能够使用动态规划思想来解决的问题，使用动态规划是比较明智的选择，它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线

9、性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作动态规划。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作

10、。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献2。动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配

11、问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。我们知道，能够用动态规划解决的问题，往往是最优化问题，且问题的最优解(或特定解)的局部往往是局部问题在相应条件下的最优解，而且问题的最优解与其子问题的最优解要有一定的关联，要能建立递推关系。如果这种关系难以建立，即问题的特定解不仅依赖于子问题的特定解，而且与子问题的一般解相关，那么，一方面难以记录下那么多的“一般解”，另一方面，递

12、推的效率也将是很低的；此外，为了体现动态规划的高时效，子问题应当是互相重叠的，即很多不同的问题共享相同的子问题3。2.2 研究意义动态规划为我们解决与重叠子问题相关的最优化问题提供了一个思考方向，通过迭代的方法考虑子问题，将问题规模减小而最终解决问题。通过学习动态规划的基本方法，对多阶段决策过程进行数学描述，建立相应的数学模型，利用Matlab软件及其优化工具函数mixfy编程计算最优决策序列和总利润的最大值,学会求解各种优化问题和使用优化工具箱，以数学模型解决最短路线，资源分配等实际问题。故本文主要采用动态规划的方法进行探究实际问题。3 Matlab软件 MATLAB 是目前在国际上被广泛接

13、受和使用的科学与工程计算软件，是美国MathWorks公司开发的计算机软件,一种在工程计算领域广为流行的程序包。虽 然 Cleve Moler 教授开发它的初衷是为了更简单、更快捷地解决矩阵运算，但 MATLAB 现 在的发展已经使其成为一种集数值运算、符号运算、数据可视化、图形界面设计、程序设 计、仿真等多种功能于一体的集成软件。Matlab的典型应用：（1）Matlab软件操作实验，主要介绍Matlab的基本语法和用法，以及它在线性代数，解析几何，微积分，数理统计中的应用和图形处理功能；（2）数理实验，主要引导学生去探究一些基本的数学概念和数值计算方法，并对一些常见物理过程进行计算，模拟；

14、（3）数学建模实验，应用于实际，解决现实的问题。二 动态规划基本理论知识1. 多阶段决策过程的数学描述有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图2-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。Sn+1SndnStage ngn = r(Sn,dn)（b）输 出输 入决 策阶 段状态转移（a） 图2

15、-1 输出状态与输入状态由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用表示。显然是状态变量和决策变量的函数，即，如图2-1所示，显然，输出是输入和决策的函数，即： （2-1） 式（1-1）即为状态转移律。在由N个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。2. 动态规划的基本概念动态规划的数学描述离不开它的一些基本概念与符号，因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。（1）阶段（stage）阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一

16、般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。对于具有N个阶段的决策过程，其阶段变量k1，2，N。（2）状态（state）状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态既反映前面各阶段系列决策的结局，又是本阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。各阶段的状态通常用状态变量来加以描述。作为状态应具有这样的性质：如果某阶段状态给定后，则该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是以往历史的一个总结。这个性质称为无后效性或健忘性。（3）决策（d

17、ecision）决策是指决策者在所面临的若干个方案中做出的选择。决策变量dk表示第k阶段的决策。决策变量的取值会受到状态的某种限制，用表示第k阶段状态为时决策变量允许的取值范围，称为允许决策集合，因而有。（4）状态转移律（transformation function）状态转移律是确定由一个状态到另一状态演变过程的方程，这种演变的对应关系记为。（5）策略（policy）与子策略（sub-policy）由所有阶段决策所组成的一个决策序列称为一个策略，具有N个阶段的动态规划问题的策略可表示为：从某一阶段开始到过程终点为止的一个决策子序列，称为过程子策略或子策略。从第k个阶段起的一个子策略可表示为：

18、（6）指标函数指标函数有阶段指标函数和过程指标函数之分。阶段指标函数是对应某一阶段决策的效率度量，用来表示；过程指标函数是用来衡量所实现过程优劣的数量指标，是定义在全过程（策略）或后续子过程（子策略）上的一个数量函数，从第k个阶段起的一个子策略所对应的过程指标函数常用来表示，即： 构成动态规划的过程指标函数，应具有可分性并满足递推关系；即： 这里的表示某种运算，最常见的运算关系有如下两种：a. 过程指标函数是其所包含的各阶段指标函数的“和”，即： 于是 b. 过程指标函数是其所包含的各阶段指标函数的“积”，即： 于是 (7)最优指标函数从第个阶段起的最优子策略所对应的过程指标函数称为最优指标函

19、数，可以用式（1-2）加以表示： (2-2)其中“opt”是最优化“optimization”的缩写，可根据题意取最大“max”或最小“min”。在不同的问题中，指标函数的含义可能是不同的，它可能是距离、利润、成本、产量或资源量等。3. 动态规划的数学模型动态规划的数学模型除包括式（2-2）外，还包括阶段的划分、各阶段的状态变量和决策变量的选取、允许决策集合和状态转移律的确定等。如何获得最优指标函数呢？一个N阶段的决策过程，具有如下一些特性：（1）刚好有N个决策点；（2）对阶段k而言，除了其所处的状态和所选择的决策外，再没有任何其它因素影响决策的最优性了；(3)阶段k仅影响阶段的决策，这一影响

20、是通过来实现的；(4)贝尔曼（Bellman）最优化原理：在最优策略的任意一阶段上，无论过去的状态和决策如何，对过去决策所形成的当前状态而言，余下的诸决策必须构成最优子策略4。根据贝尔曼（Bellman）最优化原理，可以将式（2-2）表示为递推最优指标函数关系式（2-3）或式（2-4）： （2-3） （2-4）利用式（2-3）和式（2-4）可表示出最后一个阶段（第N个阶段，即k=N）的最优指标函数： （2-5） （2-6）其中称为边界条件。一般情况下，第阶段的输出状态已经不再影响本过程的策略，即式（2-5）中的边界条件，式（2-6）中的边界条件；但当问题第阶段的输出状态对本过程的策略产生某种影

21、响时，边界条件就要根据问题的具体情况取适当的值，这一情况将在后续例题中加以反映。已知边界条件，利用式（2-3）或式（2-4）即可求得最后一个阶段的最优指标函数；有了，继续利用式（2-3）或式（2-4）即可求得最后两个阶段的最优指标函数；有了，进一步又可以求得最后三个阶段的最优指标函数；反复递推下去，最终即可求得全过程个阶段的最优指标函数，从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。通过上述分析可以看出，任何一个多阶段决策过程的最优化问题，都可以用非线性规划（特殊的可以用线性规划）模型来描述；因此，从原则上讲，一般也可以用非线性规划（

22、或线性规划）的方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什么局限性呢？4. 动态规划的优缺点动态规划的优点：第一，求解更容易、效率更高。动态规划方法是一种逐步改善法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故较易于确定最优解。第二，解的信息更丰富。非线性规划（或线性规划）的方法是对问题的整体进行一次性求解的，因此只能得到全过程的解；而动态规划方法是将过程分解成多个阶段进行求解的，因此不仅可以得到全过程的解，同时还可以得到所有子过程的解。动态规划的缺点：第一，没有一个统一的标准模型。由于实际问题不同，其动态规划模

23、型也就各有差异，模型构建存在一定困难。第二，应用条件苛刻。由于构造动态规划模型状态变量必须满足“无后效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集合和指标函数的结构，不少实际问题在取其自然特征作为状态变量时并不满足这一条件，这就降低了动态规划的通用性。第三，状态变量存在“维数障碍”。最优指标函数是状态变量的函数，当状态变量的维数增加时，最优指标函数的计算量将成指数倍增长；因此，无论是手工计算还是电算“维数障碍”都是无法完全克服的。三 动态规划理论在实际问题中的应用通过学习动态规划的基本方法，对多阶段决策过程进行数学描述，建立相应的数学模型，利用Matlab软件及其优化工具函数mi

24、xfy编程计算最优决策序列和总利润的最大值,学会求解各种优化问题和使用优化工具箱，以数学模型解决最短路线，资源分配等实际问题。1. 最短路线问题 用自编函数mixfy求解图3-1所示网络中从出发点到收点的最短路（图中各弧边为各段距离）。 图3-1 路线的网络图 解：图3-1有5个结点，12个流段。设分段流量为，并标在图3-1上，下面利用自编函数mixfy求图3-1中，从出发点到收点的最短路。先求出结点流段出入矩阵q。i=1,2,2,2,3,4,4,4,5,5;j=1,2,4,5,3,6,7,10,8,9;i1=1,1,2,2,3,3,4,5,5;j1=4,6,7,8,5,9,11,10,12;

25、使用自编函数stp:q=stg(i,j,i1,j1,5,12)求出结点流段出入矩阵q。从图3-1发点处可知流量函数为：f=1,1,1,zeros(1,9);因规定分段容量为单位容量，故ub=ones(12,);分段距离作为费用，故费用函数为：f1=2,5,4,2,1,7,5,3,4,1,5,7;至此，取v=1,用编函数mixfy:ex,z,fp=mixfy(1,f,f1,q,ub);求得，ex=1,fp=13,以及 z=1.0,0.0,0.0,1.0,0.0,0.0,0.0,1.0,0.0,1.0,1.0,0.0取 p=round(z) 得p=1,0,0,1,0,0,0,1,0,1,1,0使用

26、自编函数check2:qp,pf,pf1,rb,p=check2(f,f1,q,ub,p)求得： qp=0,0,0,0,pf=1,pf1=13,rb0由此可知，p是流值为1的最小费用整流，其费用值为13。取 zr=find(p)得 zr=1,4,8,10,11zr是0-1流p的流值为1的流段标号。参照图3-1.沿着zr所指流段，得到一条从发点至收点的最短路： 其路长为13，这就是从发点至收点的最短路。2. 资源分配问题所谓资源分配问题，就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。审计人员任务分配。某会计公司有3名审计

27、员：一名是已在公司服务4 年以上的高级审计员，两名是在公司工作不到2年的初级审计员。公司要用这3名审计员从事3项即将签订的合同任务：两名审计和一项专业发展计划。计划员的任务是以最佳方式把审计人员分配到3项不同的合同任务中。该公司不仅要求最大利润，而且要尽可能的为公众服务，目标函数还必须反应各项工作因每个审计员的承担而体现出来的无形的货币价值。在本例中，只需考虑以下两种无形价值：用于此项工作的过去经验的价值和由新经验所获得的知识。故目标函数中各变量的系数等于账面价值，过去经验价值和知识价值之和，均列于表3-1中。关于表3-1的几点说明： （1）专业发展规划未列出账面价值，但对各审计员却可以产生很

28、大的知识价值。 （2）高级审计员经验价值通常高于初级审计员的经验价值。 （3）如果一个高级审计员年年都从事一项审计工作，则他就会迟钝化，对公司的价值将会变小。这样，高级审计员的知识价值以负值来表现。表3-1 审计员承担的各个无形价值审计员任务账面价值既往经验价值学识价值总价值初级审计第一项审计119828第二项审计1186251号发展规划002525初级审计第一项审计1271029第二项审计12711302号发展规划002727高级审计第一项审计1820-434第二项审计1725-537发展规划003030下面给出约束条件：（1） 每个审计员分配3项合同的总工时数不超过100小时。（2） 每项

29、合同完成工时的上、下极限： 25第一项审计完成工时50 第二项审计完成工时=130 70发展规划完成工时90问应如何分配审计员，使会计公司获利最大？解：这是一个审计人员任务分配问题。设为初级审计员1号从事第一项审计工作的工时数，为初级审计员1号从事第二项审计工作的工时数，为初级审计员1号从事发展规划工作的工时数，为初级审计员2号从事第一项审计工作的工时数，为初级审计员2号从事第二项审计工作的工时数，为初级审计员2号从事发展规划工作的工时数，为高级审计员从事第一项审计工作的工时数，为高级审计员从事第二项审计工作的工时数，为高级审计员从事发展规划工作的工时数。从表3-1可知会计公司的利润函数为：

30、下面来看约束条件。最多工时不超过100工时： 1号审计员 2号审计员 高级审计员每项合同完成时数约束： 第一项审计 第一项审计 第二项审计 发展规划 发展规划这样，所述问题的数学模型为： 下面给出上述问题的计算程序：f=28,25,25,29,30,27,34,37,30;0=ones(1,3);z2=zeros(1,2);Z3=zeros(1,3);z6=zeros(1,6);a=0,z6;z3,0,z3;z6,0;a1=1,z,2,1,z2,1,z2;a2=z2,1,z2,1,z2,1;a=a;a1;-a1;a2;-a2;b=100,100,100,50,-25,90,-70;q=0,0.

31、95,z2,0.9,z2,1.2,0;bq=135;1b=zeros(9,1);x,fv,ex=linprog(f,a,b,q,bq,ib,);上述程序执行后，求得：ex=1,fv=-8400,及x=0,0,77.5,100,0,50,37.5,12.5。这样，使会计公司获得最大的分配方案为：初级审计员1号用77.5工时作专业发展规划，初级审计员2号用100工时作第二项审计，高级审计员用50工时作第一项审计，用37.5工时作第二项审计，用12，5工时作发展规划。其最大利润为8400元。如用xx=reshape(x,3,3);xx=xx;则得 这就是最优解审计人员的分配方案表示排列。又用 得 y表示初级审计员1号，初级审计员2号，高级审计员所用总工时。又用 得 z表示初级审计员1号，初级审计员2号，高级审计员分别给公司贡献得收入为1937.5元、3000元、3