最新-【大学课件】动态规划方法简介P88-

动态规划方法简介

动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（Ballman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题。docin/sundae_meng动态规划方法简介动态规划是解决多阶段决策过程1

动态规划是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。docin/sundae_meng动态规划是现代企业管理中的一种重要决策方法，2

一.多阶段决策过程最优化

多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。动态规划的基本原理docin/sundae_meng动态规划的基本原理docin/sundae_meng312n状态决策状态决策状态状态决策图示

多阶段决策问题，不论其本身是否与时间有关，由于分为阶段依次解决，这便具有明显的时序性，而在各阶段中所采取的决策是随阶段而变动的，不同阶段采取不同决策，这便是动态的含义.阶段往往可以用时段来表示，但动态规划在一定条件下也可以解决一些与时间无关的静态最优化问题，只要人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。docin/sundae_meng12n状态决策状态决策状态状态决策图示多阶段决4

动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而一个一个地去解决。需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。docin/sundae_meng动态规划是用来解决多阶段决策过程最优化的一种5二、多阶段决策问题举例1)工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。docin/sundae_meng二、多阶段决策问题举例1)工厂生产过程：由于市场需求是一随着6

2)设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。docin/sundae_meng2)设备更新问题：一般企业用于生产活动的设备，刚73)连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。docin/sundae_meng3)连续生产过程的控制问题：一般化工生产过程中，常包含一系列8docin/sundae_mengdocin/sundae_meng94)运输网络问题（最短路问题）：如图1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从v1至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。docin/sundae_meng4)运输网络问题（最短路问题）：如图1所示的运输网络，点间连10

以上所举问题的发展过程都与时间因素有关，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。docin/sundae_meng以上所举问题的发展过程都与时间因素有关，阶段的划11

三、动态规划方法导引

例1：为了说明动态规划的基本思想方法和特点，下面以图1所示为例讨论的求最短路问题的方法。第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有3×2×2×1＝12条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1→v3→

v7→

v9→v10,最短距离是18．docin/sundae_meng三、动态规划方法导引docin/sundae_meng12

显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1→v3→v5→v8→v10，全程长度是20；显然，这种方法的结果常是错误的．docin/sundae_meng显然，当组成交通网络的节点很多时，用穷举法求最优13

第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。docin/sundae_meng第三种方法是动态规划方法。动态规划方法寻求该最短14

具体说，此问题先从v10开始，因为v10是终点。再无后继过程，故可以接着考虑第4阶段上所有可能状态v8,v9的最优后续过程．因为从v8,v9

到v10的路线是唯一的，所以v8,v9

的最优决策和最优后继过程就是到v10

，它们的最短距离分别是5和3。接着考虑阶段3上可能的状态v5,v6,v7,到v10的最优决策和最优后继过程．在状态V5上，虽然到v8是8，到v9是9，但是综合考虑后继过程整体最优，取最优决策是到v9,最优后继过程是v5→v9→v10，最短距离是12．同理，状态v6的最优决策是至v8

；v7的最优决策是到v9

。docin/sundae_meng具体说，此问题先从v10开始，因为v10是终点。15

同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程，如v2的最优决策是到v5,最优路线是v2→v5→v9→v10，最短距离是15…依此类推，最后可以得到从初始状态v1的最优决策是到v3最优路线是v1→v3→v7→v9→v10，全程的最短距离是18。图5—1中粗实线表示各点到v10的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。docin/sundae_mengdocin/sundae_meng16

综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。docin/sundae_mengdocin/sundae_meng17四、动态规划的基本概念与基本方程

使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义：docin/sundae_meng四、动态规划的基本概念与基本方程

使用动态规划方18

(一)阶段为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量．阶段数等于多段决策过程从开始到结束所需作出决策的数目，图1所示的最短路问题就是一个四阶段决策过程，

。docin/sundae_meng(一)阶段docin/sundae_meng19

（二）状态

1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。状态应描述过程特征;能直接或间接观测;具有无后效性.某阶段的状态给定后，则过程未来发展不受该阶段以前各阶段状态的影响docin/sundae_meng（二）状态状态应描述过程特征;能直接或间接观测;具有20

2．可能状态集一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。通常可能状态集用相应阶段状态sk的大写字母Sk表示，sk∈Sk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间．在图1所示的最短路问题中，第一阶段状态为v1，状态变量s1的状态集合S1={v1}；第二阶段则有三个状态：v2,v3,v4

,状态变量s2的状态集合S2={v2,v3,v4}

；第三阶段也有三个状态:v5,v6,v7

，状态变量s3的状态集合S3={v5,v6,v7}

；第四阶段则有二个状态：v8,v9,状态变量s4的状态集合S4={v8,v9}

；docin/sundae_meng2．可能状态集docin/sundae_meng21

（三）决策所谓决策，就是确定系统过程发展的方案。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，也可以是状态变量的函数，记以uk=uk(sk)，表示于阶段k状态sk时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示,uk(sk)∈Uk(sk)允许决策集合实际是决策的约束条件。docin/sundae_meng（三）决策docin/sundae_meng22

（四）状态转移方程

系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1，系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2,…,sk-1及其决策u1(s1),u2(s2)…uk-1(sk-1)无关。系统状态的这种转移，用数学公式描述即有：(1)docin/sundae_meng（四）状态转移方程(1)docin/sundae_23

（五）、策略

策略(Policy)也叫决策序列．策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,n{u1,u2,…,un}。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,n{uk,uk+1,…,un}，显然当k=1时的k部子策略就是全过程策略。在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n

，从允许策略集中，找出具有最优效果的策略称为最优策略。docin/sundae_meng（五）、策略docin/sundae_meng24

(六)指标函数用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。例如：图1的指标就是运费。docin/sundae_mengdocin/sundae_meng25

(1)阶段指标函数（也称阶段效应）。用vk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数。

(2)过程指标函数（也称目标函数）。

不仅跟当前状态sk有关，还跟该子过程策略pk,n(sk)有关，表示为:docin/sundae_meng(1)阶段指标函数（也称阶段效应）。用vk(sk,26

适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式．对于部子过程的指标函数可以表示为：

(2)多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:docin/sundae_meng适于用动态规划求解的问题的过程指标函数（即目标函27

(七)最优解

用fk(sk)表示第k子过程指标函数在状态sk下的最优值,即

相应的子策略称为sk状态下的最优子策略，记为pk,n*(sk)；而构成该子策赂的各段决策称为该过程上的最优决策，记为；有

docin/sundae_meng(七)最优解docin/sundae_meng28

最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：

则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为(八)动态规划的最优性原理

docin/sundae_meng最优化原理（贝尔曼最优化原理）则对上述策略中所29(九)动态规划的基本方程

基于上述原理，提出了一种逆序递推法；该法的关键在于给出一种递推关系。一般把这种递推关系称为动态规划的函数基本方程。

当过程指标函数为下列“和”的形式时，相应的函数基本方程为docin/sundae_meng(九)动态规划的基本方程基于上述原理，提出了一种逆序30（三）、建立动态规划模型的步骤

1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。

2、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。

3、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。docin/sundae_meng（三）、建立动态规划模型的步骤docin/sundae_m314、确定状态转移方程根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。

5、确定阶段指标函数和最优指标函数，建立动态规划基本方程阶段指标函数是指第k

阶段的收益，最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。

以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。docin/sundae_meng4、确定状态转移方程以上五步是建立动态规划数学模型32例一、从A

地到D

地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114五、建模举例：最短路径问题docin/sundae_meng例一、从A地到D地要铺设一条煤气管道,其中需经过两级中间33

解：整个计算过程分三个阶段，从最后一个阶段开始。

第一阶段（C→D）：C

有三条路线到终点D

。

AB1B2C1C2C3D24333321114DC1C2C3显然有f1(C1)

=1；

f1(C2)

=3；

f1(C3)

=4

docin/sundae_meng解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶34

d(B1,C1)+f1(C1)

3+1f2(B1)=mind(B1,C2

)+f1(C2)

=min3+3

d(B1,C3)+f1(C3)1+44=min6=45第二阶段（B→C）：B到C

有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B1→C1→D)docin/sundae_meng第二阶段（B→C）：B到C有六条路线。A35

d(B2,C1)+f1(C1)

2+1f2(B2)=mind(B2,C2

)+f1(C2)

=min3+3

d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B2→C1→D)docin/sundae_mengAB1B2C1C2C3D24333321114D36第三阶段（

A→B

）：A到B有二条路线。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路线为A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2Adocin/sundae_meng第三阶段（A→B）：A到B有二条路线。37AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为A→B1→C1→D

路长为6docin/sundae_mengAB1B2C1C2C3D24333321114DC1C2C338SETS:CITIES/1..7/:F;ROADS(CITIES,CITIES)/1,21,32,42,52,63,43,53,64,75,76,7/:D;ENDSETSDATA:D=24331231134;ENDDATAF(SIZE(CITIES))=0;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS(i,j):D(i,j)+F(j)));ENDlINGO程序docin/sundae_mengSETS:lINGO程序docin/sundae_meng39

Feasiblesolutionfound.Totalsolveriterations:0VariableValueF(1)6.000000F(2)4.000000F(3)3.000000F(4)1.000000F(5)3.000000F(6)4.000000F(7)0.000000D(1,2)2.000000D(1,3)4.000000D(2,4)3.000000D(2,5)3.000000D(2,6)1.000000D(3,4)2.000000D(3,5)3.000000D(3,6)1.000000D(4,7)1.000000D(5,7)3.000000D(6,7)4.000000RowSlackorSurplus10.00000020.00000030.00000040.00000050.00000060.00000070.000000运行结果docin/sundae_mengFeasiblesolutionfound.运行结果d40练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：A→B1→C2→D1→E2→F2→G

路长＝18求从A到G的最短路径3docin/sundae_meng练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F41

有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。

练习2docin/sundae_meng

有资金4万元，投资A、B、C三个项目，每个项目42阶段k：每投资一个项目作为一个阶段；状态变量xk：投资第k个项目前的资金数；决策变量dk：第k个项目的投资；决策允许集合：0≤dk≤xk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)见表中所示；递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}终端条件：f4(x4)=0docin/sundae_meng阶段k：每投资一个项目作为一个阶段；docin/sundae43k=4，f4(x4)=0

k=3，0≤d3≤x3，x4=x3-d3

docin/sundae_mengk=4，f4(x4)=0

k=3，0≤d3≤x3，x4=x344k=2，0≤d2≤x2，x3=x2-d2docin/sundae_mengk=2，0≤d2≤x2，x3=x2-d2docin/sund45k=1，0≤d1≤x1，x2=x1-d1docin/sundae_mengk=1，0≤d1≤x1，x2=x1-d1docin/sund46无约束最优化问题标准形式：例：选址问题

某市燃气公司计划要建一个煤气供应站，该站要向城市中有固定位置的m

个用户供货.对于选定的坐标系而言，已知第i个用户的位置为如果只考虑直线距离，如何确定这个煤气站的位置，才能使总的运输距离最短？docin/sundae_meng无约束最优化问题标准形式：例：选址问题某市燃气公司计划要47解：设煤气站的位置为则第i个用户到该站的直线距离为故

m

个用户到该站的总距离为故选址问题可以归结为求变量使得docin/sundae_meng解：设煤气站的位置为则第i个用户到该站的直线距离为故m48无约束优化问题的解法1.如果可微，则利用

求其驻点，然后利用充分条件判别这些驻点是否是极值点。.2.搜索算法（迭代算法）基本思想：首先给定目标函数的极小点的一个初始估计点然后按照一定的规则产生一个点列，希望这种点列的极限是的一个极小点.需要给定初始点docin/sundae_meng无约束优化问题的解法1.如果可微，则利用求其驻点，然后利用49常见的算法：１．梯度法（最速下降法）2.牛顿法3.共轭梯度法用MATLAB优化工具箱求解无约束最优化计算机实现

前面我们介绍了Matlab工具箱中函数用linprog解线性规划的方法，Matlab优化工具箱还提供了一般无约束优化与约束优化的求解问题，下面介绍Matlab优化工具箱的主要函数。docin/sundae_meng常见的算法：１．梯度法（最速下降法）用MATLAB优化工具50MATLAB优化工具箱简介1.MATLAB求解优化问题的主要函数docin/sundae_mengMATLAB优化工具箱简介1.MATLAB求解优化问题的主要512.优化函数的输入变量

使用优化函数或优化工具箱中其他优化函数时,输入变量见下表:docin/sundae_meng2.优化函数的输入变量使用优化函数或优化工具箱中其他优化523.优化函数的输出变量见下表:docin/sundae_meng3.优化函数的输出变量见下表:docin/sundae_me533.优化函数的输出变量见下表:docin/sundae_meng3.优化函数的输出变量见下表:docin/sundae_me544．控制参数选项的设置(3)MaxIter:允许进行迭代的最大次数,取值为正整数.选项中常用的几个参数的名称、含义、取值如下:(1) 陈列:显示水平.取值为'off'时,不显示输出;取值为'iter'时,显示每次迭代的信息;取值为'final'时,显示最终结果.默认值为'final'.(2) MaxFunEvals:允许进行函数评价的最大次数,取值为正整数.docin/sundae_meng4．控制参数选项的设置选项中常用的几个参数的名称、含义、取值55例：opts=optimset('Display','iter','TolFun',1e-8)

该语句创建一个称为选择的优化选项结构,其中显示参数设为'iter',TolFun参数设为1e-8.

控制参数选项可以通过函数optimset创建或修改.命令的格式如下：(1)options=optimset('optimfun')

创建一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构.（2）options=optimset('param1',value1,'param2',value2,...)

创建一个名称为选项的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.(3)options=optimset(oldops,'param1',value1,'param2',value2,...)

创建名称为oldops的参数的拷贝,用指定的参数值修改oldops中相应的参数.返回docin/sundae_meng例：opts=optimset('Display','it56用MATLAB解无约束优化问题

其中等式（3）、（4）、（5）的右边可选用（1）或（2）的等式右边.

函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解.

常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）[x，fval]=fminbnd（…）（4）[x，fval，exitflag]=fminbnd（…）（5）[x，fval，exitflag，output]=fminbnd（…）docin/sundae_meng用MATLAB解无约束优化问题其中等式（3）、（457MATLAB(wliti1)

主程序为wliti1.m:

f='2*exp(-x).*sin(x)';fplot(f,[0,8]);%作图语句

[xmin,ymin]=fminbnd(f,0,8)f1='-2*exp(-x).*sin

(x)';[xmax,ymax]=fminbnd(f1,0,8)docin/sundae_mengMATLAB(wliti1)主程序为wliti1.58例2有边长为3m的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解先编写M文件fun0.m如下:

function

f=fun0(x)f=-(3-2*x).^2*x;主程序为wliti2.m:

[x,fval]=fminbnd('fun0',0,1.5);xmax=xfmax=-fval运算结果为:xmax=0.5000,fmax=2.0000.即剪掉的正方形的边长为0.5m时水槽的容积最大,最大容积为2m3.MATLAB(wliti2)docin/sundae_meng例2有边长为3m的正方形铁板，在四个角剪去相等的正方形以59

命令格式为:（1）x=fminunc（fun,X0）；或x=fminsearch（fun,X0）（2）x=fminunc（fun,X0，options）；或x=fminsearch（fun,X0，options）（3）[x，fval]=fminunc（...）；或[x，fval]=fminsearch（...）（4）[x，fval，exitflag]=fminunc（...）；或[x，fval，exitflag]=fminsearch（5）[x，fval，exitflag，output]=fminunc（...）；或[x，fval，exitflag，output]=fminsearch（...）2.多元函数无约束优化问题标准型为：mindocin/sundae_meng命令格式为:2.多元函数无约束优化问题标准型60[3]fminunc为中型优化算法的步长一维搜索提供了两种算法，由选项中参数LineSearchType控制：

LineSearchType=‘quadcubic’(缺省值)，混合的二次和三次多项式插值；

LineSearchType='cubicpoly'，三次多项式插使用fminunc和fminsearch可能会得到局部最优解.说明:fminsearch是用单纯形法寻优.fminunc算法见以下几点说明：[1]fminunc为无约束优化提供了大型优化和中型优化算法.由选项中的参数LargeScale控制：LargeScale=‘on'(默认值),使用大型算法LargeScale=‘off'(默认值),使用中型算法[2]fminunc为中型优化算法的搜索方向提供了4种算法，由

选项中的参数HessUpdate控制：

HessUpdate='bfgs'（默认值），拟牛顿法的BFGS公式；HessUpdate='dfp'，拟牛顿法的DFP公式；HessUpdate='steepdesc'，最速下降法docin/sundae_meng[3]fminunc为中型优化算法的步长一维搜索提供了两种61例3minMATLAB(wliti3)1.编写M文件

fun1.m:function

f=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2.输入M文件wliti3.m如下:

x0=[-1,1];x=fminunc('fun1',x0);y=fun1(x)

3.运行结果:

x=0.5000-1.0000y=1.3029e-10docin/sundae_meng例3minMATLAB(wliti3)1.编写M文件f62*非线性规划的基本解法非线性规划的基本概念非线性规划

返回docin/sundae_meng*非线性规划的基本解法非线性规划的基本概念非线性规划返回d63

定义

如果目标函数或约束条件中至少有一个是非线性函数,则最优化问题就叫做非线性规划问题．非现性规划的基本概念

一般形式:

（1）其中，是定义在Rn上的实值函数，简记:

其它情况:

求目标函数的最大值，或约束条件小于等于零两种情况，都可通过取其相反数化为上述一般形式．1nj1ni1nR

:h

,R

:g

,R

:RRRf®®®()nTnRxxxXÎ=,,,21L()()ïîïíì===³.,...,2,1

0

m;1,2,...,

0..

ljXhiXgtsjidocin/sundae_meng定义如果目标函数或约束条件中至少有一64

定义1

把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．定义2

对于问题(1),设,若存在,使得对一切

,且,都有,则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地,当时，若

,则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．定义3对于问题(1),设,若对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地,当时，若,则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．

返回)(nRXÎ()(){}njiRXXhXgXDÎ

=

³=,0,0|()(),XfXf£*docin/sundae_meng定义2对于问题(1),设65非线性规划的基本解法SUTM外点法SUTM内点法（障碍罚函数法）1．罚函数法2．近似规划法

返回docin/sundae_meng非线性规划的基本解法SUTM外点法SUTM内点法（障碍罚函数66MATLAB优化工具箱解非线性规划docin/sundae_mengMATLAB优化工具箱解非线性规划docin/sundae67

用MATLAB软件求解,其输入格式如下:

1．x=quadprog(H,C,A,b);2．x=quadprog(H,C,A,b,Aeq,beq);3．x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4．x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5．x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6．[x,fval]=quaprog(…);7．[x,fval,exitflag]=quaprog(…);8．[x,fval,exitflag,output]=quaprog(…);1．二次规划docin/sundae_meng用MATLAB软件求解,其输入格式如下:1．二次68例1

min

f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.

x1+x2≤2-x1+2x2≤2

x1≥0,x2≥0MATLAB（youh1）1．写成标准形式：2．输入命令：

H=[1-1;-12];c=[-2;-6];A=[2-2;-24];b=[2;2];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3．运算结果为：

x=32z=-15.5s.t.docin/sundae_meng例1minf(x1,x2)=-2x1-6x2+x169

1．首先建立M文件fun.m,用来定义目标函数F（X）:functionf=fun(X);f=F(X);2．一般非线性规划

其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其他变量的含义与线性规划、二次规划中相同．用MATLAB求解上述问题，基本步骤分三步：docin/sundae_meng1．首先建立M文件fun.m,用来定义目标函数F（X）:703．建立主程序.求解非线性规划的函数是fmincon,命令的基本格式如下：

(1)x=fmincon(‘fun’,X0,A,b)

(2)x=fmincon(‘fun’,X0,A,b,Aeq,beq)

(3)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB)

(4)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)(5)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)

(6)[x,fval]=fmincon(…)

(7)[x,fval,exitflag]=fmincon(…)(8)[x,fval,exitflag,output]=fmincon(…)输出极值点M文件迭代的初值参数说明变量上下限docin/sundae_meng3．建立主程序.求解非线性规划的函数是fmincon,命令71注意：[1]fmincon函数提供了大型优化算法和中型优化算法．默认时:若在fun函数中提供了梯度（options参数的GradObj设置为’on’），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法．当既有等式约束又有梯度约束时，使用中型算法．[2]fmincon函数的中型算法使用的是序列二次规划法．在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hesse矩阵．[3]fmincon函数可能会给出局部最优解，这与初值X0的选取有关．docin/sundae_meng注意：docin/sundae_meng721．写成标准形式：

s.t.

2x1+3x26

s.t.

x1+4x25

x1,x20例2docin/sundae_meng1．写成标准形式：2x1+3x2732．先建立M-文件fun3．m:

functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2MATLAB(youh2)3．再建立主程序youh2．m：

x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)4．运算结果为：

x=0．76471．0588fval=-2．0294docin/sundae_meng2．先建立M-文件fun3．m:MATLAB(youh2)741．先建立M文件fun4．m定义目标函数:

functionf=fun4(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

x1+x2=0s.t.1.5+x1x2-x1-x20

-x1x2–10

0例32．再建立M文件mycon．m定义非线性约束：

function[g,ceq]=mycon(x)g=[x(1)+x(2);1．5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];docin/sundae_meng1．先建立M文件fun4．m定义目标函数:753．主程序youh3．m为:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')MATLAB(youh3)4．运算结果为：

x=-1．22501．2250fval=1．8951docin/sundae_meng3．主程序youh3．m为:MATLAB(youh3)4．76

例4

1．先建立M文件fun．m定义目标函数:functionf=fun(x);f=-2*x(1)-x(2);2．再建立M文件mycon2．m定义非线性约束：function[g,ceq]=mycon2(x)g=[x(1)^2+x(2)^2-25;x(1)^2-x(2)^2-7];

docin/sundae_meng例41．先建立M文件f773．主程序fxx．m为:

x0=[3;2．5];VLB=[00];VUB=[510];[x,fval,exitflag,output]=fmincon('fun',x0,[],[],[],[],VLB,VUB,'mycon2')MATLAB(fxx(fun))docin/sundae_meng3．主程序fxx．m为:MATLAB(fxx(fun))d784．运算结果为:

x=4．00003．0000fval=-11．0000exitflag=1output=iterations:4funcCount:17stepsize:1algorithm:[1x44char]firstorderopt:[]cgiterations:[]

返回docin/sundae_meng4．运算结果为:返回docin/sundae_meng79应用实例：供应与选址

某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出．目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t．假设从料场到工地之间均有直线道路相连．（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小．（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？docin/sundae_meng应用实例：供应与选址某公司有6个建筑工地要开80（一）建立模型

记工地的位置为(ai，bi)，水泥日用量为di，i=1,…,6;料场位置为(xj，yj)，日储量为ej，j=1,2；料场j向工地i的运送量为Xij．当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj．docin/sundae_meng（一）建立模型记工地的位置为(ai，bi)，水泥日用量81（二）使用临时料场的情形

使用两个临时料场A(5,1)，B(2,7)．求从料场j向工地i的运送量Xij

.

在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题．线性规划模型为：设X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

编写程序gying1．mMATLAB（gying1）docin/sundae_meng（二）使用临时料场的情形使用两个临时料场A(5,82计算结果为：x=[3．00005．00000．00007．00000．00001．00000．00000．00004．00000．00006．000010．0000]’fval=136．2275docin/sundae_meng计算结果为：x=[3．00005．00000．083（三）改建两个新料场的情形

改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小．这是非线性规划问题．非线性规划模型为：docin/sundae_meng（三）改建两个新料场的情形改建两个新料场，要同时确定料84设X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,,X61=X6

X12=X7,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12

x1=X13,y1=X14,x2=X15,y2=X16

（1）先编写M文件liaoch．m定义目标函数．MATLAB（liaoch）(2)取初值为线性规划的计算结果及临时料场的坐标:

x0=[35070100406105127]';编写主程序gying2．m．MATLAB（gying2）docin/sundae_meng设X11=X1,X21=X2,X31=X3,85(3)计算结果为：x=[3．00005．00000．07077．000000．9293003．929306．000010．07076．38754．39435．75117．1867]’fval=105．4626exitflag=1docin/sundae_meng(3)计算结果为：x=[3．00005．000086(4)若修改主程序gying2．m,取初值为上面的计算结果:x0=[3．00005．00000．07077．000000．9293003．929306．000010．07076．38754．39435．75117．1867]’则得结果为:x=[3．00005．00000．30947．00000．01080．6798003．690605．989210．32025．53694．91945．82917．2852]’fval=103．4760exitflag=1总的吨千米数比上面结果略优．(5)若再取刚得出的结果为初值,却计算不出最优解．MATLAB（gying2）MATLAB（gying2）docin/sundae_meng(4)若修改主程序gying2．m,取初值为上面的计算87(6)若取初值为:x0=[35471000005115．63484．86877．24797．7499]',

则计算结果为:x=[3．00005．00004．00007．00001．0000000005．000011．00005．69594．92857．25007．7500]’fval=89．8835exitflag=1总的吨千米数89．8835比上面结果更好．通过此例可看出fmincon函数在选取初值上的重要性．MATLAB（gying2）

返回docin/sundae_meng(6)若取初值为:通过此例可看出fmincon函数在选取88

动态规划方法简介

动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（Ballman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题。docin/sundae_meng动态规划方法简