动态规划的建模与求解

《动态规划的建模与求解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.3动态规划的建模与求解4.3.1建摸1、理论依据-----最优化原理最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略2、动态规划模型的几个要素：1)阶段数k2)状态变量sk3)决策变量uk（sk）4)指标函数Vk,n状态转移方程5)最优值函数fk(sk)3、建立动态规划模型的基本要求：1）所研究的问题必须能够分成几个相互联系的阶段，而且在每一个阶段都具有需要进行决策的问题。2）在每一阶段都必须有若干个与该阶段相关的状态一般情况下，状态是所研究系统在该阶段可能处于的情况或条件建模时总是从

2、与决策有关的条件中，或是从问题的约束条件中去选择状态变量。3)具有明确的指标函数，且阶段指标值可以计算4)能正确列出最优值函数的递推公式和边界条件（b）能通过现阶段的决策，使当前状态转移成下一阶段的状态即能够给出状态转移方程（c）状态的无后效性状态的选取必须注意以下几个要点：（a）在所研究问题的各阶段，都能直接或间接确定状态变量的取值例（资源分配问题）某公司有资金a万元，拟投资于n个项目，已知对第i个项目投资xi万元，收益为gi(xi)，问应如何分配资金可使总收益最大？解：阶段k=1,2,…,n状态变量sk决策变量uk：第k个项目的投资额：在第k阶段时可以用于投资第k到第n个

3、项目的资金数状态转移方程：sk+1=sk-uk指标函数Vk,n：第k阶段可分配的资金数为sk时，第k至第n个项目的最大总收益边界条件：k=n,n-1,…,2,1资源分配问题的动态规划基本方程：建立递推公式：：在第k阶段分配的资金数为sk时，第k至第n个项目的最大总收益某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并设计了备用元件自动投入装置。显然，备用元件越多，整个系统的可靠性越大，但备用元件增多也会导致系统的成本、重量相应增大。设部件i(i=1,2,…,n)上装有xi个备用元件

4、时，正常工作的概率为pi（xi）。设装一个i部件的设备元件费用为ci，重量wi为，要求整个系统所装备用元件的总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？例复合系统工作可靠性问题解：设A---整个系统正常工作，Ai—部件i正常工作满足：非线性规划问题系统由n个部件串联组成，每一个部件上装有备用件，部件i(i=1,2,…,n)上装有xi个备用元件时，正常工作的概率为pi（xi）。设装一个i部件的设备元件费用为ci，重量wi为，要求总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？例复合系统工作可

5、靠性问题解：n个部件=n个阶段决策变量uk=部件k上所装的备用元件数xk状态变量：sk=第k个到第n个部件可使用的总费用yk=第k个到第n个部件容许的总重量状态转移方程：指标函数Vk,n最优指标函数fk(sk，yk）=在部件k，可使用的总费用为sk，总重量为yk时，从部件k到部件n的系统工作可靠性的最大值复合系统工作可靠性的动态规划基本方程为：与问题无关动态规划基本方程：4.4.2动态规划模型的求解解法离散型连续型：分段穷举法：利用解析方法或线性规划方法没有固定的方法具体模型具体分析要求：经验、技巧、灵活难！投资额收益工厂12314.525274.57397.58410.51

6、1105121513一、离散变量的分段穷举法例（资源分配问题）某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表：问：对三个工厂如何分配，才能使总收益达到最大？状态变量sk：阶段k=1，2，3决策变量uk：给工厂k的投资额在第k阶段时可供工厂k到工厂3分配的资金数状态转移方程：sk+1=sk-ukgk(uk)=给工厂k投资uk（十万元）的收益指标函数Vk,nfk（sk）投资工厂k至工厂3所得的最大总收益求f1（5）=在工厂k，可供分配的资金数为sk时，基本方程：k=300112233057845451013投资额收益

7、工厂12314.525274.57397.58410.511105121513012345k=20000102015205012774.50或1730123899.57.529.54501234101011.512.511312.5012345131212.514.51615416投资额收益工厂12314.525274.57397.58410.511105121513sk+1=sk-uk00112233057845451013012345k=1sk+1=sk-uk投资额收益工厂12314.525274.