数学建模算法动态规划.doc

《数学建模算法动态规划.doc》由会员分享，可在线阅读，更多相关《数学建模算法动态规划.doc（17页珍藏版）》请在三一办公上搜索。

1、第四章 动态规划1 引言1.1 动态规划的发展及研究内容动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。动态规划问世以来

2、，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基

3、本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由到距离最短（或费用最省）的路线。例2 生产计划问题工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种

4、产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。2 基本概念、基本方程和计算方法2.1

5、动态规划的基本概念和基本方程一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。2.1.1 阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用表示。在例1中由出发为，由出发为，依此下去从出发为，共个阶段。在例2中按照第一、二、三、四季度分为，共四个阶段。2.1.2 状态状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（state

6、 variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用表示第阶段的状态变量，它可以是一个数或一个向量。用表示第阶段的允许状态集合。在例1中可取，或将定义为，则或，而。个阶段的决策过程有个状态变量，表示演变的结果。在例1中取，或定义为，即。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。2.1.3 决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制

7、（control）。描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用表示第阶段处于状态时的决策变量，它是的函数，用表示的允许决策集合。在例1中可取或，可记作，而。决策变量简称决策。2.1.4 策略决策组成的序列称为策略（policy）。由初始状态开始的全过程的策略记作，即.由第阶段的状态开始到终止状态的后部子过程的策略记作，即，.类似地，由第到第阶段的子过程的策略记作.可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用表示。2.1.

8、5. 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作 （1）在例1中状态转移方程为。2.1.6. 指标函数和最优值函数指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用表示，。指标函数应具有可分离性，即可表为的函数，记为并且函数对于变量是严格单调的。过程在第阶段的阶段指标取决于状态和决策，用表示。指标函数由组成，常见的形式有：阶段指标之和，即，阶段指标之积，即，阶段指标之极大（或极小），即.这

9、些形式下第到第阶段子过程的指标函数为。根据状态转移方程指标函数还可以表示为状态和策略的函数，即。在给定时指标函数对的最优值称为最优值函数（optimal value function），记为，即，其中可根据具体情况取或。2.1.7 最优策略和最优轨线使指标函数达到最优值的策略是从开始的后部子过程的最优策略，记作。是全过程的最优策略，简称最优策略（optimal policy）。从初始状态出发，过程按照和状态转移方程演变所经历的状态序列称最优轨线（optimal trajectory）。2.1.8 递归方程如下方程称为递归方程 （2）在上述方程中，当为加法时取；当为乘法时，取。动态规划递归方程是

10、动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由逆推至，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解法。这时，状态转移方程和递归方程分别为：， 纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首先建立起动态规划的数学模型：（i）将过程划分成恰当的阶段。（ii）正确选择状态变量，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合。 （iii）选择决策变量，确定允许决策集合。（iv）写出状态转移方程。（v）确定阶段指标及指标函数的形式（阶段指标之和，阶段指标之积，阶段指

11、标之极大或极小等）。（vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。3 逆序解法的计算框图以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它情况容易在这个基础上修改得到。一般化的自由终端条件为 (3)其中为已知。固定始端条件可表示为。如果状态和决策是连续变量，用数值方法求解时需按照精度要求进行离散化。设状态的允许集合为.决策的允许集合为.状态转移方程和阶段指标应对的每个取值和的每个取值计算，即，。最优值函数应对的每个取值计算。基本方程可以表为 （4）按照（3），（4）逆向计算出，为全过程的最优值。记状态的最优决策为，由和按照状态转移方程计算出最优状态，记作。

12、并得到相应的最优决策，记作。于是最优策略为。算法程序的框图如下。图的左边部分是函数序列的递推计算，可输出全过程最优值，如果需要还可以输出后部子过程最优值函数序列和最优决策序列。计算过程中存是备计算之用，在算完后可用将替换掉；存是备右边部分读之用。图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略和最优轨线。4 动态规划与静态规划的关系动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。动态规划可以看作求决策使指标函数达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约

13、束条件，原则上可以用非线性规划方法求解。一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明。例3 用动态规划解下列非线性规划 ； s.t. .其中为任意的已知函数。解 按变量的序号划分阶段，看作段决策过程。设状态为，取问题中的变量为决策。状态转移方程为取为阶段指标，最优值函数的基本方程为（注意到）；.按照逆序解法求出对应于每个取值的最优决策，计算至后即可利用状态转移方程得到最优状态序列和最优决策序列。与静态规划相比，动态规划的优越性在于：（i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。

14、而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。 （ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可

15、以用来寻找次优策略。（iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。动态规划的主要缺点是： （i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。 （ii）用数值方法求解时存在维数灾（curse of d

16、imensionality）。若一维状态变量有个取值，那么对于维问题，状态就有个值，对于每个状态值都要计算、存储函数，对于稍大（即使）的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。5 若干典型问题的动态规划模型5.1 最短路线问题 对于例1一类最短路线问题（shortest Path Problem），阶段按过程的演变划分，状态由各段的初始位置确定，决策为从各个状态出发的走向，即有，阶段指标为相邻两段状态间的距离，指标函数为阶段指标之和，最优值函数是由出发到终点的最短距离（或最小费用），基本方程为利用这个模型可以算出例l的最短路线为， 相应的最短距离为18。5.2 生产

17、计划问题对于例 2一类生产计划问题（Production planning problem），阶段按计划时间自然划分，状态定义为每阶段开始时的储存量，决策为每个阶段的产量，记每个阶段的需求量（已知量）为，则状态转移方程为 (5)设每阶段开工的固定成本费为，生产单位数量产品的成本费为，每阶段单位数量产品的储存费为，阶段指标为阶段的生产成本和储存费之和，即 (6)指标函数为之和。最优值函数为从第段的状态出发到过程终结的最小费用，满足其中允许决策集合由每阶段的最大生产能力决定。若设过程终结时允许存储量为，则终端条件是 （7）（5）（7）构成该问题的动态规划模型。5.3 资源分配问题一种或几种资源（包

18、括资金）分配给若干用户，或投资于几家企业，以获得最大的效益。资源分配问题（resource allocating Problem）可以是多阶段决策过程，也可以是静态规划问题，都能构造动态规划模型求解。下面举例说明。例4 机器可以在高、低两种负荷下生产。台机器在高负荷下的年产量是，在低负荷下的年产量是，高、低负荷下机器的年损耗率分别是和（）。现有台机器，要安排一个年的负荷分配计划，即 每年初决定多少台机器投入高、低负荷运行，使年的总产量最大。如果进一步假设，（），即高、低负荷下每台机器的年产量分别为和，结果将有什么特点。解 年度为阶段变量。状态为第年初完好的机器数，决策为第年投入高负荷运行的台数

19、。当或不是整数时，将小数部分理解为一年中正常工作时间或投入高负荷运行时间的比例。机器在高、低负荷下的年完好率分别记为和，则，有。因为第年投入低负荷运行的机器台数为，所以状态转移方程是 （8）阶段指标是第年的产量，有 （9）指标函数是阶段指标之和，最优值函数满足 (10)及自由终端条件 （11） 当中的用较简单的函数表达式给出时，对于每个可以用解析方法求解极值问题。特别，若，（10）中的 将是的线性函数，最大值点必在区间的左端点或右端点取得，即每年初将完好的机器全部投入低负荷或高负荷运行。6 具体的应用实例例5 设某工厂有1000台机器，生产两种产品，若投入台机器生产产品，则纯收入为，若投入台机

20、器生产种产品，则纯收入为，又知：生产种产品机器的年折损率为20%，生产产品机器的年折损率为10%，问在5年内如何安排各年度的生产计划，才能使总收入最高？解 年度为阶段变量。令表示第年初完好机器数，表示第年安排生产种产品的机器数，则为第年安排生产种产品的机器数，且。则第年初完好的机器数 （12）令表示第年的纯收入，表示第年初往后各年的最大利润之和。显然 （13）则 （14）（1）时，由（13）、（14）式得 关于求导，知其导数大于零，所以在等于处取得最大值，即时，。（2）时，由（12）、（14）式得 当时，（3）时， 当时，（4）时，当时，。（5）时，当时，。因为 （台）所以由（12）式，进行回

21、代得 （台） （台） （台） （台）注：台中的0.4台应理解为有一台机器只能使用0.4年将报废。例6 求解下面问题 解： 按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为，并记；取问题中的变量为决策变量；各阶段指标函数按乘积方式结合。令最优值函数表示第阶段的初始状态为，从阶段到3阶段所得到的最大值。设， ， 则有 ， ， 用逆推解法，从后向前依次有 及最优解 由，得和（舍去）又，而，故为极大值点。所以 及最优解 。同样利用微分法易知 ，最优解。由于已知，因而按计算的顺序反推算，可得各阶段的最优决策和最优值。即，由所以，由所以，因此得到最优解为：，； 最大值为：。习 题 四1

22、. 用Matlab编程求例5的解。2. 有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表： 工作工人甲乙丙丁15192619182317212122162324181917 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？试对此问题用动态规划方法求解。3. 为保证某一设备的正常运转，需备有三种不同的零件。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为8000元。已知备用零件数与它的可靠性和费用的关系如下表所示。备件数增加的可靠性设备的费用（千元）0.30.40.50.20.50.90.10.20.7123356234现要求在既不超出投资

23、额的限制，又能尽量提高设备运转的可靠性的条件下，问各种零件的备件数量应是多少为好？4. 某工厂购进100台机器，准备生产I、II两种产品，若生产产品I，每台机器每年可收入45万元，损坏率为65；若生产产品II，每台机器每年收入为35万元，损坏率为35，估计三年后将有新型机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？这两个过程的步骤分述如下。（A）标号过程：（i）给发点标号为。（ii）若顶点已经标号，则对的所有未标号的邻接顶点按以下规则标号： 若，且时，令，则给顶点标号为，若，则不给顶点标号。 ，且，令，则给标号为，若，则不给标号。（iii）不断地重复步骤（ii）直到

24、收点被标号，或不再有顶点可以标号为止。当被标号时，表明存在一条从到的可增广轨，则转向增流过程（B）。如若点不能被标号，且不存在其它可以标号的顶点时，表明不存在从到的可增广轨，算法结束，此时所获得的流就是最大流。（B）增流过程（i）令。（ii）若的标号为），则；若的标号为，则。（iii）若，把全部标号去掉，并回到标号过程（A）。否则，令，并回到增流过程（ii）。求网络中的最大流的算法的程序设计具体步骤如下：对每个节点，其标号包括两部分信息 该节点在可能的增广路中的前一个节点，以及沿该可能的增广路到该节点为止可以增广的最大流量。STEP0 置初始可行流（如零流）；对节点标号，即令=任意正值（如1）

25、。STEP1 若，继续下一步；否则停止，已经得到最大流，结束。STEP2 取消所有节点的标号，即令，；令LIST=，对节点标号，即令充分大的正值。STEP3 如果LIST且，继续下一步；否则：（3a）如果已经有标号（即），则找到了一条增广路，沿该增广路对流进行增广（增广的流量为，增广路可以根据pred回溯方便地得到），转STEP1。（3b）如果没有标号（即LIST=且），转STEP1。STEP4 从LIST中移走一个节点；寻找从节点出发的所有可能的增广弧：（4a）对非饱和前向弧，若节点没有标号（即），对进行标号，即令，并将加入LIST中。（4b）对非空后向弧，若节点没有标号（即），对进行标号，

26、即令，并将加入LIST中。例14 用Ford-Fulkerson算法计算如下网络中的最大流，每条弧上的两个数字分别表示容量和当前流量。解 编写程序如下：clc,clear,M=1000;u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;u(3,5)=1;u(4,3)=3;u(4,5)=3;f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;f(3,5)=1;f(4,3)=1;f(4,5)=0;n=length(u);list=;maxf(n)=1;while maxf(n)0 maxf=zeros(1,n);pred

27、=zeros(1,n); list=1;record=list;maxf(1)=M; while (isempty(list)&(maxf(n)=0) flag=list(1);list(1)=; index1=(find(u(flag,:)=0); label1=index1(find(u(flag,index1). -f(flag,index1)=0); label1=setdiff(label1,record); list=union(list,label1); pred(label1)=flag; maxf(label1)=min(maxf(flag),u(flag,label1).

28、-f(flag,label1); record=union(record,label1); label2=find(f(:,flag)=0); label2=label2; label2=setdiff(label2,record); list=union(list,label2); pred(label2)=-flag; maxf(label2)=min(maxf(flag),f(label2,flag); record=union(record,label2); end if maxf(n)0 v2=n; v1=pred(v2); while v2=1 if v10 f(v1,v2)=f(

29、v1,v2)+maxf(n); else v1=abs(v1); f(v2,v1)=f(v2,v1)-maxf(n); end v2=v1; v1=pred(v2); end end endf8 最小费用流及其求法8.1 最小费用流上面我们介绍了一个网络上最短路以及最大流的算法，但是还没有考虑到网络上流的费用问题，在许多实际问题中，费用的因素很重要。例如，在运输问题中，人们总是希望在完成运输任务的同时，寻求一个使总的运输费用最小的运输方案。这就是下面要介绍的最小费用流问题。在运输网络中，设是定义在上的非负函数，它表示通过弧单位流的费用。所谓最小费用流问题就是从发点到收点怎样以最小费用输送一已知

30、量为的总流量。最小费用流问题可以用如下的线性规划问题描述：s.t. ， .显然，如果最大流，则本问题就是最小费用最大流问题。如果，则本问题无解。8.2 求最小费用流的一种方法迭代法这里所介绍的求最小费用流的方法叫做迭代法。这个方法是由Busacker和Gowan在1961年提出的。其主要步骤如下：(i)求出从发点到收点的最小费用通路。(ii)对该通路分配最大可能的流量： 并让通路上的所有边的容量相应减少。这时，对于通路上的饱和边，其单位流费用相应改为。(iii)作该通路上所有边的反向边。令，(iv)在这样构成的新网络中，重复上述步骤(i)，(ii)，(iii)，直到从发点到收点的全部流量等于为

31、止（或者再也找不到从到的最小费用道路）。下面我们编写了用Floyd算法求最短路的函数floydpath和最小费用最大流函数mincostmaxflow。最短路函数如下：function path=floydpath(w);num=length(w);M=sum(sum(w).*num;w=w+(w=0)-eye(num).*M;p=zeros(num);for k=1:num for i=1:num for j=1:num if w(i,j)w(i,k)+w(k,j) w(i,j)=w(i,k)+w(k,j); p(i,j)=k; end end endendif w(1,num)=M pat

32、h=;else path=zeros(num); s=1;t=num;m=p(s,t); while isempty(m) if m(1) s=s,m(1);t=t,t(1);t(1)=m(1); m(1)=;m=p(s(1),t(1),m,p(s(end),t(end); else path(s(1),t(1)=1;s(1)=;m(1)=;t(1)=; end endend最小费用最大流函数如下：function flow=mincostmaxflow(rongliang,cost,flowvalue);%第一个参数：容量矩阵；第二个参数：费用矩阵；%第三个参数：指定容量值（可以不写，表示求

33、最小费用最大流）%前两个参数必须在不通路处置零，且为同维矩阵%返回值为可行流矩阵%必须有函数文件floydpath.mM=sum(sum(rongliang);flow=zeros(size(rongliang);allflow=sum(flow(1,:);if nargin3 flowvalue=M;endwhile allflowflowvalue w=(flow0).*cost); path=floydpath(w);%调用floyd if isempty(path) return; end theta=min(min(path.*(rongliang-flow)+(path.*(ron

34、gliang-flow)=0).*M); theta=min(min(path.*flow+(path.*flow=0).*M),theta); if allflow+thetaflowvalue theta=flowvalue-allflow; end flow=flow+(rongliang0).*(path-path).*theta; allflow=sum(flow(1,:);end对于习题五中的第7题，我们的调用函数如下：clear;clc;cost= 0 4 1 0 0; 0 0 0 6 1; 0 2 0 3 0; 0 0 0 0 2; 0 0 0 0 0;rongliang= 0

35、 10 8 0 0; 0 0 0 2 7 ; 0 5 0 10 0; 0 0 0 0 4; 0 0 0 0 0;y=mincostmaxflow(rongliang,cost)习 题 五1. 一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去，但由于船小，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去？2. 北京（Pe）、东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)各城市之间的航线距离如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa

36、2157365161Pe5178685113T6070686113由上述交通网络的数据确定最小生成树。3. 某台机器可连续工作4年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的的处理价如下表所示。又新机器第一年运行及维修费为0.3万元，使用1-3年后机器每年的运行及维修费用分别为0.8，1.5，2.0万元。试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。第一年第二年第三年第四年年初购置价使用了年的机器处理价2.52.02.61.62.81.33.11.14. 某产品从仓库运往市场销售。已知各仓库的可供量、各市场需求量及从仓库至市

37、场的路径的运输能力如下表所示（表中数字0代表无路可通），试求从仓库可运往市场的最大流量，各市场需求能否满足？仓库 市场1234可供量300201001001040405052020100需求量20206020 5. 某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？6. 下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题，画出网络图并求数值解。产量 销地123产量2030242252087销量4567. 求下图所示网络的最小费用最大流，弧旁数字为。5.