4.3动态规划建模与求解.ppt

最优化原理： 一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略 2、动态规划模型的几个要素： 3、建立动态规划模型的基本要求： 3)具有明确的指标函数，且阶段指标值可以计算 例 （资源分配问题） 4.4.2 动态规划模型的求解 例（季节工问题）某工厂的生产任务随季节波动，为降低成本宜用季节临时工，但熟练的生产工人临时难以聘到，培训新手费用又高，各季节工人需用量如下表所示，每季节超过需用量聘用，每人浪费2000元，聘用或解聘费为200元乘上两个季节聘用人数之差的平方，问厂长一年中应如何聘用工人可使总花费最小？（假定工资按实际工作时间计算，则聘用人数可为分数） * 4.3.1 建摸 1、理论依据 -----最优化原理 1)阶段数k 2)状态变量sk 3)决策变量uk （ sk ） 4)指标函数Vk,n 状态转移方程 5)最优值函数fk(sk) 1）所研究的问题必须能够分成几个相互联系的阶段，而且在每一个阶段都具有需要进行决策的问题。 2）在每一阶段都必须有若干个与该阶段相关的状态 一般情况下，状态是所研究系统在该阶段可能处 于的情况或条件 建模时总是从与决策有关的条件中，或是从问题的约束条件中去选择状态变量。 4)能正确列出最优值函数的递推公式和边界条件 （b）能通过现阶段的决策，使当前状态转移 成下一阶段的状态 即 能够给出状态转移方程 （c）状态的无后效性 状态的选取必须注意以下几个要点： （a）在所研究问题的各阶段，都能直接或间 接确定状态变量的取值 某公司有资金a万元，拟投资于n个项目，已知对第i个项目投资xi万元，收益为 g i (xi)，问应如何分配资金可使总收益最大？ 解：阶段k=1,2, …,n 状态变量sk 决策变量uk ：第k个项目的投资额 ：在第k阶段时可以用于投资 第k到第n个项目的资金数 状态转移方程： 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个备用元件时，正常工作的概率为pi （ xi ）。设装一个i部件的设备元件费用为ci ，重量wi为，要求整个系统所装备用元件的总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？ 例 复合系统工作可靠性问题 解：设A---整个系统正常工作，Ai—部件i正常工作 满足： 非线性规划问题 系统由n个部件串联组成，每一个部件上装有备用件，部件i(i=1,2, …,n)上装有xi个备用元件时，正常工作的概率为pi （ xi ）。设装一个i部件的设备元件费用为ci ，重量wi为，要求总费用不超过C，总重量不超过W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？ 例 复合系统工作可靠性问题 解： n个部件=n个阶段 决策变量uk = 部件k上所装的备用元件数xk 状态变量： sk =第k个到第n个部件可使用的总费用 yk =第k个到第n个部件容许的总重量 状态转移方程： 指标函数Vk,n 最优指标函数fk(sk， yk ）= 在部件k，可使用 的总费用为sk，总重量为yk 时，从部件k 到部件n的系统工作可靠性的最大值 复合系统工作可靠性的动态规划基本方程为： 与问题无关 动态规划基本方程： 解法 离散型 连续型 ：分段穷举法 ：利用解析方法或线性规划方法 没有固定的方法 具体模型具体分析 要求：经验 、技巧、灵活 难！ 投资额 收益 工厂 13 15 12 5 10 11 10.5 4 8 7.5 9 3 7 4.5 7 2 5 2 4.5 1 3 2 1 一、离散变量的分段穷举法 例（资源分配问题）某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表： 问