【大学竞赛】数学建模辅导 优化(p88)

1、整理课件 动态规划方法简介动态规划方法简介 整理课件整理课件整理课件12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策图示图示 整理课件 动态规划是用来解决多阶段决策过程最优动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一化的一种数量方法。其特点在于，它可以把一个个n 维决策问题变换为几个一维最优化问题，从维决策问题变换为几个一维最优化问题，从而一个一个地去解决。而一个一个地去解决。 需指出：动态规划是求解某类问题的一种需指出：动态规划是求解某类问题的一种方法，方法，是考察问题的一种途径是考察问题的一种途径，而不是一种算，而不是一种算法。必须对具体问题进

2、行具体分析，运用动态法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。用动态规划方法去求解。整理课件二、多阶段决策问题举例二、多阶段决策问题举例1)工厂生产过程工厂生产过程：由于市场需求是一随着时间而：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。据库存和需求情况决定生产计划安排。整理课件 2)2)设备更新问题设备更新问

3、题：一般企业用于生产一般企业用于生产活动的设备，刚买来时故障少，经济效益活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用费因此就需要综合权衡决定设备的使用

4、年限，使总的经济效益最好。年限，使总的经济效益最好。整理课件3) 3)连续生产过程的控制问题连续生产过程的控制问题：一般化工一般化工生产过程中，常包含一系列完成生产生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使产过程中各设备的输入和输出，以使总产量最大。总产量最大。整理课件整理课件4)4)运输网络问题（最短路问题）运输网络问题（最短路问题）：如图如图1所示的运输网络，点间连线上的数字表所

5、示的运输网络，点间连线上的数字表示两地距离示两地距离(也可是运费、时间等也可是运费、时间等)，要，要求从求从v1至至v10的最短路线。的最短路线。 这种运输网络问题也是静态决策问题。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它但是，按照网络中点的分布，可以把它分为分为4个阶段，而作为多阶段决策问题个阶段，而作为多阶段决策问题来研究。来研究。整理课件 以上所举问题的发展过程都与时间因以上所举问题的发展过程都与时间因素有关，阶段的划分常取时间区段来表示，素有关，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素并且各个阶段上的决策往往也与时间因素有关，这就使

6、它具有了有关，这就使它具有了“动态动态”的含义，的含义，所以把处理这类动态问题的方法称为动态所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含规划方法。不过，实际中尚有许多不包含时间因素的一类时间因素的一类“静态静态”决策问题，就其决策问题，就其本质而言是一次决策问题，是非动态决策本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法当作多阶段决策问题，应用动态规划方法加以解决。加以解决。整理课件 三、动态规划方法导引三、动态规划方法导引 例例1 1：为了说明动态规划的基本思想方法和

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

8、共有3 32 22 21 11212条条可能的路线，分别算出各条路线的距离，最后可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是进行比较，可知最优路线是v v1 1 v v3 3 v v7 7 v v9 9 v v10 10 , ,最短距离是最短距离是1818整理课件 显然，当组成交通网络的节点很多显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重将会十分庞大，而且其中包含着许多重复计算复计算 第二种方法即所谓第二种方法即所谓“局部最优路径局部最优路径”法，是说某人从法，是说某人从k k出发，他并

9、不顾及全线出发，他并不顾及全线是否最短，只是选择当前最短途径，是否最短，只是选择当前最短途径，“逢近便走逢近便走”，错误地以为局部最优会，错误地以为局部最优会致整体最优，在这种想法指导下，所取致整体最优，在这种想法指导下，所取决策必是决策必是v1 v3 v5 v8 v10 v1 v3 v5 v8 v10 ，全程长度是全程长度是2020；显然，这种方法的结果；显然，这种方法的结果常是错误的常是错误的整理课件 第三种方法是第三种方法是动态规划方法动态规划方法。动态规。动态规划方法寻求该最短路问题的基本思想是，划方法寻求该最短路问题的基本思想是，首先将问题划分为首先将问题划分为4 4个阶段，个阶段，

10、每次的选择总每次的选择总是综合后继过程的一并最优进行考虑是综合后继过程的一并最优进行考虑，在，在各段所有可能状态的最优后继过程都已求各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得得的情况下，全程的最优路线便也随之得到。到。 为了找出所有可能状态的最优后继过为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。逐段向前递推计算直至始点。整理课件 具体说，此问题先从具体说，此问题先从v v1010开始，因为开始，因为v v

11、1010是终是终点。再无后继过程，故可以接着考虑第点。再无后继过程，故可以接着考虑第4 4阶段上阶段上所有可能状态所有可能状态v v8 8 , ,v v9 9的最优后续过程因为从的最优后续过程因为从v v8 8 , ,v v9 9 到到v v1010的路线是唯一的，所以的路线是唯一的，所以v v8 8 , ,v v9 9 的最的最优决策和最优后继过程就是到优决策和最优后继过程就是到v v1010 ，它们的最短，它们的最短距离分别是距离分别是5 5和和3 3。 接着考虑阶段接着考虑阶段3 3上可能的状态上可能的状态v v5 5 , ,v v6 6 , , v v7 7 , , 到到v v1010

12、的最优决策和最优后继过程在状态的最优决策和最优后继过程在状态V V5 5上，上，虽然到虽然到v v8 8是是8 8，到，到v v9 9是是9 9，但是综合考虑后继过程，但是综合考虑后继过程整体最优，取最优决策是到整体最优，取最优决策是到v v9 9, ,最优后继过程是最优后继过程是v v5 5v v9 9 v v10 10 ，最短距离是，最短距离是1212同理，状态同理，状态v v6 6的的最优决策是至最优决策是至v v8 8 ；v v7 7的最优决策是到的最优决策是到v v9 9 。整理课件 同样，当阶段同样，当阶段3 3上所有可能状态的最上所有可能状态的最优后继过程都已求得后，便可以开始考

13、虑优后继过程都已求得后，便可以开始考虑阶段阶段2 2上所有可能状态的最优决策和最优上所有可能状态的最优决策和最优后继过程，如后继过程，如v v2 2的最优决策是到的最优决策是到v v5 5, ,最优路最优路线是线是v v2 2v v5 5v v9 9v v10 10 ，最短距离是，最短距离是1515依依此类推，最后可以得到从初始状态此类推，最后可以得到从初始状态v v1 1的最的最优 决 策 是 到优 决 策 是 到v v3 3最 优 路 线 是最 优 路 线 是v v1 1v v3 3v v7 7v v9 9v v10 10 ，全程的最短距离是，全程的最短距离是1818。图。图5151中粗实

14、线表示各点到中粗实线表示各点到v v1010的最优的最优路线，每点上方括号内的数字表示该点到路线，每点上方括号内的数字表示该点到终点的最短路距离。终点的最短路距离。整理课件 综上所述可见，全枚举法虽可找出最优方案，综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方但不是个好算法，局部最优法则完全是个错误方法，只有法，只有动态规划方法属较科学有效的算法动态规划方法属较科学有效的算法。它。它的基本思想是，的基本思想是，把一个比较复杂的问题分解为一把一个比较复杂的问题分解为一系列同类型的更易求解的子问题系列同类型的更易求解的子问题，便于应用计算，便于应用计算机。整个求

15、解过程分为两个阶段，机。整个求解过程分为两个阶段，先按整体最优先按整体最优的思想逆序地求出各个子问题中所有可能状态的的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。问题的最优策略和最优路线。计算过程中，系统计算过程中，系统地删去了所有中间非最优的方案组合，从而使计地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。算工作量比穷举法大为减少。整理课件四、动态规划的基本概念与基本方程四、动态规划的基本概念与基本方程 使用动态规划方法解决多阶段决策使用动态规划方法解决多阶段决策问题

16、，首先要将实际问题写成动态规划问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术这里需要对动态规划的下述一些基本术语进一步加以说明和定义语进一步加以说明和定义： 整理课件 (一) 阶段 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目，图1

17、所示的最短路问题就是一个四阶段决策过程， 。1,2,3,4k 整理课件 （二）状态二）状态 1.状态与状态变量。用以描述事物用以描述事物( (或或系统系统) )在某特定的时间与空间域中所处位置在某特定的时间与空间域中所处位置及运动特征的量，称为状态及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段阶段k k的初始状态记作的初始状态记作s sk k，终止状，终止状态记为态记为s sk+1k+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。

18、状态应描述过程特征状态应描述过程特征; ;能直接或间接观测能直接或间接观测; ;具有无后效性具有无后效性. . 某阶段的状态给定后，则过程未来发展不受该阶段以前各阶段状态的影响某阶段的状态给定后，则过程未来发展不受该阶段以前各阶段状态的影响整理课件 2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间在图1所示的最短路问题中，第一阶段状态为v1，状态变量s1的状态集合S1=v1；第二阶段则有三个状态：v2 , v3 , v4 , 状 态 变

19、量s2的 状 态 集 合S2=v2 ,v3 ,v4 ；第三阶段也有三个状态:v5 ,v6 ,v7 ，状态变量s3的状态集合S3=v5 ,v6 ,v7 ；第四阶段则有二个状态： v8 ,v9 , 状态变量s4的状态集合S4=v8 ,v9 ；整理课件 （三）决策三）决策 所谓决策，就是确定系统过程发展的方案。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，也可以是状态变量的函数，记以u uk k= = u uk k( (s sk k) )，表示于阶段k状态sk时的决策变量

20、。 决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用U Uk k( (s sk k) )表示, u uk k( (s sk k) U) Uk k( (s sk k) )允许决策集合实际是决策的约束条件。整理课件 （四）状态转移方程（四）状态转移方程 系统在阶段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)无关。系

21、统状态的这种转移，用数学公式描述即有：)(,(1kkkkksusTs(1)整理课件 （五）、策略（五）、策略 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成 的 决 策 序 列 ， 简 称 策 略 ， 表 示 为p1,nu1,u2,un。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,nuk,uk+1,un ，显然当k=1时的k部子策略就是全过程策略。 在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集

22、合，称之允许策略集合，记作P1,n ，从允许策略集中，找出具有最优效果的策略称为最优策略。整理课件 (六) 指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。例如：图1的指标就是运费。整理课件 (1)(1)阶段指标函数（也称阶段效应）。阶段指标函数（也称阶段效应）。用用v vk k( (s sk k,u,uk k) )表示第表示第k k段处于段处于s sk k状态且所作决策为状态且所作决策为u uk k( (s sk k) )时的

23、指标，则它就是第时的指标，则它就是第k k段指标函数段指标函数。 (2)(2)过程指标函数（也称目标函数）。过程指标函数（也称目标函数）。 不仅跟当前状态不仅跟当前状态s sk k有关，还跟该子过程策略有关，还跟该子过程策略p pk,nk,n( (s sk k) )有关，表示为有关，表示为: :,()k nk nkVps整理课件 适于用动态规划求解的问题的过程指标函数适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分（即目标函数），必须具有关于阶段指标的可分离形式对于部子过程的指标函数可以表示为：离形式对于部子过程的指标函数可以表示为： ,1,1,1()(,()k

24、 nk nkkkkknknkVpss u Vps (2),11 ,1 ,1()(,)(,)(,)(,)()nknknkiiiiknkkkiiiikkkkknknkVpsvsuvsuvsuvsuVps 整理课件 ( (七七) ) 最优解最优解 用用f fk k( (s sk k) )表示第表示第k k子过程指标函数在状态子过程指标函数在状态s sk k下的最下的最优值优值, ,即即 相应的子策略称为相应的子策略称为s sk k状态下的最优子策略，记状态下的最优子策略，记为为p pk,nk,n* *( (s sk k) ) ；而构成该子策赂的各段决策称为该；而构成该子策赂的各段决策称为该过程上的最

25、优决策，记为过程上的最优决策，记为 ；有有 ,()()()(*(),1,2,k nk nkkkk nk nkk nk nkpPsfsoptVpsVpskn )(,),(),(11nnkkkksususu ,1,1,2,k nkknpuuukn 整理课件 最优化原理最优化原理 （贝尔曼最优化原理）（贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质：作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优的状态和决策如何，余下的诸决策必构成一个最优子策略。子策略。该原理的具

26、体解释是，若某一全过程最优该原理的具体解释是，若某一全过程最优策略为策略为：1,11122( )( ),(),(),()nkknnpsu su su su s 则对上述策略中所隐含的任一状态而言，则对上述策略中所隐含的任一状态而言， 第第k k子过程上对应于该状态的最优策略必然子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略包含在上述全过程最优策略p p1 1* *中，即为中，即为,11()(),(),()k nkkkkknnpsususus ( (八八) ) 动态规划的最优性原理动态规划的最优性原理整理课件1111()()0() ( ,)(),1,2,1kkknnkkkkkkku

27、Dsfsf soptv s ufskn n 整理课件（三）、建立动态规划模型的步骤（三）、建立动态规划模型的步骤 1 1、划分阶段、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。 2 2、正确选择状态变量、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，选择变量既要能确切描

28、述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。变量的选择是从过程演变的特点中寻找。 3 3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。整理课件 4 4、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变阶段状态变量，状态转移方

29、程应当具有递推关系。量，状态转移方程应当具有递推关系。 5 5、确定阶段指标函数和最优指标函数，建立动态规、确定阶段指标函数和最优指标函数，建立动态规划基本方程划基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数阶段的收益，最优指标函数是指从第是指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最阶段末所获得收益的最优值，最后写出动态规划基本方程。优值，最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统动态规划模型与线性规划模型不同，动态

30、规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。不断实践总结，才能较好掌握建模方法与技巧。 整理课件例一、从例一、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过其中需经过两级中间站，两点之间的连线上的数字表示距离，如两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？图所示。问应该选择什么路线，使总距离最短？ AB1B2C1C2C3D24333321114五、建模举例：最短路径问题五、建模举例：最短路径问题整理课件 解：整个计算

31、过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。 第一阶段（第一阶段（C D）：）： C 有三条路线到终点有三条路线到终点D 。 AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 整理课件 d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5第二阶段（第二阶段（B C）：）：

32、B 到到C 有六条路线。有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)整理课件 d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)整理课件第三阶段（第三阶段（ A B ）：）： A 到到B 有二条路线。有二条路线。 f3(A)1 = d(A, B

33、1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f3 (A) = min = min6,7=6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路线为最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A整理课件AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为 6整理课件SETS:CITIES/1.7/:F;ROADS(CITIES,CITIES)/1, 2 1, 32, 4 2, 5 2, 6

34、3, 4 3, 5 3, 6 4, 7 5, 7 6, 7/:D;ENDSETS DATA:D=2 4 3 3 1 2 3 1 1 3 4;ENDDATAF(SIZE(CITIES)=0;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS(i,j):D(i,j)+F(j);ENDlINGO程序整理课件 Feasible solution found. Total solver iterations: 0 Variable Value Row Slack or Surplus运行结果运行结果整理课件练习练习1：AB1B2C1C2C3C4D1D2D3E1E

35、2E3F1F2G53136876368533842221333525664最优路线为：最优路线为：A B1 C2 D1 E2 F2 G 路长路长18求从求从A到到G的最短路径的最短路径3整理课件 有资金有资金4 4万元，投资万元，投资A A、B B、C C三个项目，每个项目的投资效三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目益与投入该项目的资金有关。三个项目A A、B B、C C的投资效益的投资效益（万吨）和投入资金（万元）关系见下表（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。求对三个项目的最优投资分配，使总投资效益最大。练习练习2 2整

36、理课件w阶段k：每投资一个项目作为一个阶段；w状态变量xk：投资第k个项目前的资金数；w决策变量dk：第k个项目的投资；w决策允许集合：0dkxkw状态转移方程：xk+1=xk-dkw阶段指标：vk(xk ,dk)见表中所示；w递推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)w终端条件：f4(x4)=0整理课件k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3整理课件k=2，0d2x2，x3=x2-d2整理课件k=1，0d1x1，x2=x1-d1整理课件无约束最优化问题无约束最优化问题标准形式：标准形式：RmaxnXfXRmin nXfX例：选址问题 某市燃气

37、公司计划要建一个煤气供应站，该站要向城市中某市燃气公司计划要建一个煤气供应站，该站要向城市中有固定位置的有固定位置的m m 个用户供货个用户供货. .对于选定的坐标系而言，已知对于选定的坐标系而言，已知第第i i 个用户的位置为个用户的位置为如果只考虑直线距离，如何确定这个煤气站的位置，才能如果只考虑直线距离，如何确定这个煤气站的位置，才能使总的运输距离最短使总的运输距离最短？整理课件解：设煤气站的位置为解：设煤气站的位置为则第则第i 个用户到个用户到该站的直线距离为该站的直线距离为故故 m 个用户到该站的总距离为个用户到该站的总距离为故选址问题可以归结为求变量故选址问题可以归结为求变量使得使

38、得整理课件无约束优化问题的解法无约束优化问题的解法可微，则利用可微，则利用 求其驻点，然后利用充分条件判别这些驻点是否求其驻点，然后利用充分条件判别这些驻点是否是极值点。是极值点。.2. 搜索算法（迭代算法）搜索算法（迭代算法）基本思想基本思想：首先给定目标函数首先给定目标函数 的极小点的一个初始的极小点的一个初始估计点估计点 然后按照一定的规则产生一个点列然后按照一定的规则产生一个点列 ，希望，希望这种点列的极限是的一个极小点这种点列的极限是的一个极小点 .需要给定初始点需要给定初始点整理课件常见的算法常见的算法： 梯度法（最速下降法）梯度法（最速下降法）用用MATLABMATLAB优化工具

39、箱求解无约束最优化优化工具箱求解无约束最优化计算机实现计算机实现 前面我们介绍了前面我们介绍了Matlab 工具箱中函数用工具箱中函数用linprog解线性规划的解线性规划的方法，方法，Matlab优化工具箱还提供了一般无约束优化与约束优化优化工具箱还提供了一般无约束优化与约束优化的求解问题，下面介绍的求解问题，下面介绍Matlab优化工具箱的主要函数。优化工具箱的主要函数。整理课件MATLAB优化工具箱简介优化工具箱简介1.1.MATLAB求解优化问题的主要函数求解优化问题的主要函数整理课件 使用优化函数或优化工具箱中其他优化函数时使用优化函数或优化工具箱中其他优化函数时, , 输入变量见下

40、表输入变量见下表:整理课件3.3.优化函数的输出变量见下表优化函数的输出变量见下表: :整理课件3.3.优化函数的输出变量见下表优化函数的输出变量见下表: :整理课件4 4控制参数选项的设置控制参数选项的设置 (3) MaxIterMaxIter: 允许进行迭代的最大次数,取值为正整数.选项中常用的几个参数的名称、含义、取值如下选项中常用的几个参数的名称、含义、取值如下: :off时,不显示输出; 取值为iter时,显示每次迭代的信息;取值为finalfinal.(2)MaxFunEvals: 允许进行函数评价的最大次数,取值为正整数.整理课件例：opts=optimset(Display,

41、iter, TolFun,1e-8) 该语句创建一个称为选择的优化选项结构,其中显示参数设为iter, TolFun参数设为1e-8. 控制参数选项可以通过函数控制参数选项可以通过函数optimsetoptimset创建或修改创建或修改. .命令的命令的格式如下：格式如下：(1) options=optimset(optimfun) 创建一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构.（2）options=optimset(param1,value1,param2,value2,.) 创建一个名称为选项的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.

42、(3) options=optimset(oldops, param1,value1,param2,value2,.) 创建名称为oldops的参数的拷贝,用指定的参数值修改oldops中相应的参数.返回整理课件用用MATLAB解无约束优化问题解无约束优化问题 其中等式（其中等式（3 3）、（）、（4 4）、（）、（5 5）的右边可选用（）的右边可选用（1 1）或（）或（2 2）的等式右边的等式右边. . 函数函数fminbndfminbnd的算法基于黄金分割法和二次插值法，它要求的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解目标函数必须是连续函数，并可

43、能只给出局部最优解. . 常用格式如下：常用格式如下：（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（）整理课件MATLAB(wliti1) 主程序为主程序为wliti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作图语句作图语句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin (

44、x); xmax,ymax=fminbnd (f1, 0,8)整理课件例例2 2 有边长为有边长为3 3m的正方形铁板，在四个角剪去相等的正方形以的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？制成方形无盖水槽，问如何剪法使水槽的容积最大？解解先编写先编写M文件如下文件如下: : function f=fun0(x) f=-(3-2*x).2*x;主程序为主程序为wliti2.m: x,fval=fminbnd(fun0,0,1.5); xmax=x fmax=-fval运算结果为运算结果为: xmax = 0.5000, = 0.5000,fmaxm时水

45、槽的容积最大时水槽的容积最大, ,最大最大容积为容积为2 2m3. .MATLAB(wliti2)整理课件 命令格式为命令格式为: :（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，ou

46、tput= fminunc（.）； 或x，fval，exitflag，output= fminsearch（.） 2.多元函数无约束优化问题多元函数无约束优化问题标准型为：标准型为：min()F X整理课件3 fminunc为中型优化算法的步长一维搜索提供了两种算法，由选项中参数LineSearchType控制： LineSearchType=quadcubic (缺省值)，混合的二次和三次多项式插值； LineSearchType=cubicpoly，三次多项式插使用使用fminunc和和 fminsearch可能会得到局部最优解可能会得到局部最优解. .说明说明: :fminsearch是

47、用单纯形法寻优是用单纯形法寻优.fminunc算法见以下几点说明：算法见以下几点说明：1 fminunc为无约束优化提供了大型优化和中型优化算法.由选项中的参数LargeScale控制：LargeScale=on (默认值默认值),使用大型算法使用大型算法LargeScale=off (默认值默认值),使用中型算法使用中型算法2 fminunc为中型优化算法的搜索方向提供了4种算法，由 选项中的参数选项中的参数HessUpdate控制：控制： HessUpdate=bfgs（默认值），拟牛顿法的（默认值），拟牛顿法的BFGS公式；公式；HessUpdate=dfp，拟牛顿法的，拟牛顿法的DFP

48、公式；公式；HessUpdate=steepdesc，最速下降法，最速下降法整理课件例例3 3 minMATLAB(wliti3)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); M文件如下文件如下: : x0 = -1, 1; x=fminunc(fun1,x0); y=fun1(x) 3. 3.运行结果运行结果: : 12212122( )(42421) exf xxxx xx整理课件非线性规划非线性规划 返回返回整理课件 定义定义 如果目标函数或约束条件中至少有一个是非线性函

49、数,则最优化问题就叫做非线性规划问题非线性规划问题非现性规划的基本概念非现性规划的基本概念 一般形式一般形式: （1） 其中 ， 是定义在 R Rn 上的实值函数，简记: Xfmin jihgf, 其它情况其它情况: 求目标函数的最大值，或约束条件小于等于零两种情况，都可通过取其相反数化为上述一般形式1nj1ni1nR :h ,R :g ,R :RRRfnTnRxxxX,21 .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsji整理课件 定义定义1 1 把满足问题（1）中条件的解 称为可行解可行解（或可行（或可行点点），），所有可行点的集合称为可行集可行集（或（或可行域可

50、行域）记为D即 问题(1)可简记为 XfDXmin定义定义2 2 对于问题(1),设 ,若存在 ,使得对一切 ,且 ,都有 ,则称X*是f(X)在D上的局部极小值点局部极小值点（局部最优解局部最优解）特别地,当 时，若 ,则称X*是f(X)在D上的严格局部极小值点严格局部极小值点（严格局部最严格局部最优解优解）DX *0DX *XX*XX XfXf* XfXf*定义定义3 3 对于问题(1),设 ,若对任意的 ,都有则称X*是f(X)在D上的全局极小值点全局极小值点（全局最优解全局最优解）特别地,当 时，若 ,则称X*是f(X)在D上的严格全局极小值严格全局极小值点点（严格全局最优解严格全局最

51、优解）DX *DX *XX XfXf* 返回返回)(nRX njiRXXhXg XD , 0, 0| ,Xf Xf *整理课件非线性规划的基本解法非线性规划的基本解法 返回返回整理课件MATLAB 优化工具箱解非线性规划优化工具箱解非线性规划整理课件 用MATLAB软件求解,其输入格式输入格式如下: 1x=quadprog(H,C,A,b); 2x=quadprog(H,C,A,b,Aeq,beq); 3x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5x=quadprog(H,C,

52、A,b,Aeq,beq,VLB,VUB,X0,options); 6x,fval=quaprog(); 7x,fval,exitflag=quaprog(); 8x,fval,exitflag,output=quaprog();1二次规划二次规划整理课件例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 MATLAB（youh1）1写成标准形式写成标准形式： 2输入命令输入命令： H=1 -1; -1 2; c=-2 ;-6;A=2 -2; -2 4;b=2;2; Aeq=;beq=; VLB=0;0

53、;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3运算结果运算结果为： T111222 2 -221min( , )2 462xxzx xxx 1212 1 121 2200 xxxxs.t.整理课件 1 首先建立M文件fun.m,用来定义目标函数F（X）:function f=fun(X);f=F(X);2一般非线性规划一般非线性规划 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其他变量的含义与线性规划、二次规划中相同用MATLAB求解上述问题，基本步骤分三步：整理课件3 建立主程序.求解非线性规划的函数是fmincon,命令

54、的基本格式如下： (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= fm

55、incon()输出极值点M文件迭代的初值参数说明变量上下限整理课件注意：注意：1 fmincon函数提供了大型优化算法和中型优化算法默认时: 若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法当既有等式约束又有梯度约束时，使用中型算法2 fmincon函数的中型算法使用的是序列二次规划法在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hesse矩阵3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关整理课件1写成标准形式写成标准形式： s.t. 00546322121xxxx2

56、100 xx22212121212minxxxxf22212121212minxxxxf 2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0例例2整理课件2先建立先建立M-文件文件 fun3m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2MATLAB(youh2)3再建立主程序youh2m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4运算结果为：运算结果为：

57、x = 07647 10588 fval = -20294整理课件1 1先建立先建立M文件文件fun4m定义目标函数定义目标函数: function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);12212122( )e (42421)xf xxxx xx x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例3 2再建立再建立M文件文件myconm定义非线性约束：定义非线性约束： function g,ceq=mycon(x) g=x(1)+x(2);15+x(1)*x(2)-

58、x(1)-x(2); -x(1)*x(2)-10;整理课件3主程序主程序youh3m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb, vub,mycon)MATLAB(youh3)4 运算结果为运算结果为： x = -12250 12250 fval = 18951整理课件 例4 12221122221212 min2s.t. 250 70 05, 010fXxxgXxxgXxxxx 1先建立先建立M文件文件funm定义目标函数定义目标函数: function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;整理课件3 主程序主程序fxxm为为: x0=3;25; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0, VLB,VUB,mycon2)MATLAB(fxx(fun)整理课件4 运算结果为运算结果为: x = 40000 30000fval =-110000exitfla