第七章 动态规划3

《第七章 动态规划3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹帷幄之中决胜千里之外第七章动态规划运筹学教学要求：了解动态规划的基本思想掌握一维离散动态规划的建模和求解方法应用会运用动态规划方法解决一些基本应用问题。第一节　动态规划原理和模型在生产和经营活动中，经常遇到这样的问题，它们包含若干个相互联系的阶段，而且，在每一阶段都要做出决策，一个阶段的决策除影响该阶段本身的效果之外，还影响到下一阶段的起始状态，从而影响到整个过程的效果最优因此不但要考虑这一阶段，还要把它看成是整个过程决策链中的一个链环，这种过程称为多阶段决策过程，如企业在生产过程中，由于需求是随时间变化的

2、，因此为了获得全年的最佳效益，就要逐月或逐季度地根据库存和需求决定生产计划。动态规则是将一个较复杂的多阶段决策问题分解为若干相互关联的较容易求解的子(单）决策问题。而每一个子决策问题都有多种选择当一个子决策问题确定以后，将影响另一个子决策问题从而影响到整个问题的决策第一节　动态规划原理和模型例1、最小费用问题：某运输公司拟将一批货物从A地运往E地，其间的交通系统网络如下图所示。图上节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。AB1B2B3C1C2C3D1D2E第2阶段

3、第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段4311344461697812553第一节　动态规划原理和模型一、动态规则的实例例2、机器负荷分配问题：年初完好机器数为u台，其中有u1台用于高负荷生产，产品的年产量为s1=g(u1)，年终完好机器数为au1(a称完好率,0

4、案中找到最优方案一般先保守生产后风险生产可使产量最大第一节　动态规划原理和模型例某运输公司有500辆运输卡车，在超负荷运输(即每天满载行驶500km以上)情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3，在低负荷运输(即每天行驶300KM以下)情况下，年利润为16万元/辆、年损坏率为0.1，现在要求制订一个5年运输计划，问每年年初应如何分配完好车辆在两种不同负荷下运输的卡车数量，使在5年内总利润最大？U低高低低低低高高高高年初第二年第三年第四年第五年第一节　动态规划原理和模型例3、排序问题：有5个零件需要在A

5、、B两台机床上加工，每个零件都必须经过先A后B的加工顺序，加工时间如下表，问应如何安排加工顺序，使总的加工时间最少？零件号机床A机床B136292347453574第一节　动态规划原理和模型以上问题的一个共同特点是问题的过程可以分解成相互联系的若干阶段，在每个阶段均需要作出决策，各个阶段的决策取决于目前的状态，它又将影响到以后的发展，当各个阶段的决策确定之后，就构成一个决策序列，我们的目的就是要在决策系列中，寻找最优的决策序列二、动态规则的分类离散确定性离散随机性连续确定性连续随机性第一节　动态规划原理和模型三、动态

6、规则的基本概念1、阶段将所给问题，按时间或空间特性分解成若干互相联系的部分，用字母K表示阶段变量第一节　动态规划原理和模型AB1B2B3C1C2C3D1D2E4311344461697812553U低高低低低低高高高高年初第二年第三年第四年第五年4个阶段多种选择5个阶段2种选择2、状态状态就是每个阶段的起始位置，它既是该阶段某支路的起点，又是前一阶段某支路的终点,通常一个阶段包含若干个状态，第K阶段的状态就是该阶段所有始点集合状态变量：描述各阶段状态的变量，用sk表示状态集合：状态变量sk的取值集合AB1B2B3C1

7、C2C3D1D2E4311344461697812553S1={A},S2={B1,B2,B3}S3={C1,C2,C3}S4={D1,D2}第一节　动态规划原理和模型3、决策从一个阶段给定状态出发，到下阶段某一状态的选择决策变量：描述决策的变量，常用uk(xk)表示第k阶段状态xk的决策变量第一节　动态规划原理和模型AB1B2B3C1C2C3D1D2E4311344461697812553若第2阶段从状态B1出发到第3阶段时选定的状态为C1,则有u2(B1)=C1允许的决策集合：第K阶段某给定状态xk的决策变量uk

8、(xk)的允许取值范围常用Dk(xk)表示AB1B2B3C1C2C3D1D2E4311344461697812553D2(B1)={C1,C3}D2(B2)={C1,C2,C3}第一节　动态规划原理和模型4、策略由第一阶段开始到最后阶段终点的全过程的每一阶段的决策ui(xj)(i,j=1,2,3,..)组成的决策序列，记为P1,n(X)={u1