管理运筹学07动态规划资料课件.ppt

《管理运筹学07动态规划资料课件.ppt》由会员分享，可在线阅读，更多相关《管理运筹学07动态规划资料课件.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.多阶段决策过程2.Bellman最优性原理3.动态规划的数学描述4.例6.15.确定性动态规划问题6.随机性动态规划问题蓬鉴哺缩猩坛抱钓奏年禾泰毋志锹革金偏檄反蔬捂船右劳炳洒恭吹仿荒妓管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划多阶段决策过程多阶段决策过程多阶段决策问题多阶段决策问题是指这样一类问题，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，从而使整个过程达到最佳的活动效果。任何一个阶段(Stage，决策点)都是由输入(Input)、决策(De

2、cision)、转移律(Transformation)和输出(output)构成的，如图6-1(a)所示。由于每一阶段都对应一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用gn表示。显然gn是状态变量sn和决策变量dn的函数，即gn=rn(sn,dn)，如图6-1(b)所示。狂古骆精肯檄亡甥叼记户习沸骑触胯魂赠傈讼肥曼俐虹雄冶刮揽钵跟兑桌管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划多阶段决策过程多阶段决策过程 决策 输入 阶

3、段 输出 转移律 图6-1(a)dn sn(in)n sn(out)gn=rn(sn,dn)图6-1(b)弥啃致镑馋老珐齐舆卞褒而争迎湍金慧蔗烦胡办蛔赤颓秒铆愤垦浪脾卖丰管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划多阶段决策过程多阶段决策过程 d1 d2 dNs1 s2 s3 sN sN+1 1 2 N g1 g2 gN 图 6-2 N 阶段决策系统示意图侵氛厄肉咖痰俗压肝束映受骨烘筛矛荣紫帽冠缝同职酗染悬构衅哉肩锐箔管理运筹学07动态规划管理运筹学07动态规划1/10

4、/2023Bellman最优性原理最优性原理 作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优子策略。简而言之，一个最优策略的任一子策略都是最优子策略。峪砌阀配汗玻五砾都俐思桥琵洱阉竟孽妇努颖朵洗鸯博诸擦钾守奖看哉异管理运筹学07动态规划管理运筹学07动态规划1/10/2023动态规划的数学描述动态规划的数学描述1.阶段2.状态3.决策 4.状态转移律5.策略与子策略6.阶段指标函数7.过程指标函数8.最优指标函数储漾纵瓢殿癸阮尾诡蔽反捻举永捂睫联移毒维测比鹤潭激塘醚饿茫桥系壳管理运筹学07动态规划管理运筹学07动态规划1

5、/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划阶段阶段在多阶段决策过程中，决策点将整个过程划分为若干部分，其中的每一部分即为一个阶段。描述阶段的变量称为阶段变量，常用 k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，一个N 个阶段的多阶段决策问题其阶段变量 k=1，2，N。秦醛强悉攻艇劣帅巧稻裂勇腺洒蚁袄唾怕奇夯砰筒逆漳痈侗顽甩谈积恬风管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划

6、状态状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态反映前面各阶段决策的结局，又是本阶段决策的出发点和依据。状态是各阶段信息的传递点和结合点，各阶段的状态通常用状态变量Sk来描述。作为状态应具有这样的性质：在某阶段的状态给定后，该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是过程以往历史的一个总结。这个性质称为无后效性无后效性或健忘性健忘性。鼻金捉酿娥相镶薛煞壁斤三晕删潞漆屈但廓恐途绑住孩蓝轿兄链辛招食况管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛

7、曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划决策决策决策是指决策者在若干可行方案中所作出的选择。决策变量dk(Sk)表示第k 阶段、状态为Sk时的决策。决策变量的取值会受到一定的限制，用Dk(Sk)表示第k 阶段、状态为Sk 时决策变量允许的取值范围，称为允许决策集合，因而有dk(Sk)Dk(Sk)。哗稠佩试姨印彦蚌杠远诈遥迄鸡厄佑摘若账锣齐嚷巳卡剑护话妆功黑临君管理运筹学07动态规划管理运筹学07动态规划1/10/2023状态转移律状态转移律 状态转移律是确定由一个状态到另一个状态演变过程的关系式，这种演变的对应关系记为Sk+1=Tk(Sk,dk)。评冲船族

8、斗虱卵江贫坍球硅辞黍否果儡狭睫值币姚娘蹄汰渤佣棱晨茹芦墙管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划策略与子策略策略与子策略各阶段决策所组成的决策序列称为一个策略，具有N个阶段的动态规划问题的策略可表示为d1(S1),d2(S2),dN(SN)。从某一阶段开始到过程终点为止的决策序列，称为子过程策略或子策略。从第k个阶段起的子策略可表示为dk(Sk),dk+1(Sk+1),dN(SN)。走田妄霄合处妆夯塌郸肖膊辅孩备硒照察呆租疆掌绰条部靶忠铭纫容完遥管理运筹学07动态规

9、划管理运筹学07动态规划1/10/2023阶段指标函数阶段指标函数 阶段指标函数是对应某一阶段决策的效率度量，用gk=rk(Sk,dk)来加以表示。桶瓷邓鹅秩踢脆豺柯珍父智搏坟焕霸祸竖购馅兜旁酗漾骆耗询型枫劲蛔能管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划过程指标函数过程指标函数过程指标函数是用来衡量所实现过程优劣的数量指标，它是定义在全过程（策略）或后续子过程（子策略）上的数量函数。过程指标函数常用Rk,N 来表示，构成动态规划的过程指标函数应具有可分性并满足递推关系

10、，即Rk,N 可表示为rk 和Rk+1,N二者的函数。最常见的过程指标函数与阶段指标函数的关系有如下两种：1.过程指标函数是阶段指标函数的和，此时Rk,N=rk+Rk+1,N 2.过程指标函数是阶段指标函数的积，此时Rk,N=rk Rk+1,N腊看矮瑟抢啤倘嵌憾从曹态创斡予阶迢递淋章窗舷褥伍串庭曼脐梁畴惊疙管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划最优指标函数最优指标函数包混畸陷婚瘤讯慕笼犁奔村韭繁暖注贮密柠茂惊吾呸斩碗灸仕箱阎柳钨喘管理运筹学07动态规划管理运筹学0

11、7动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划 A B C D B1 12 9 C1 15 6 A 4 B2 20 D 8 16 10 C2 16 B3 9例例1锨镇汪形煤盔派封利羚羡叫烽嚣脑胯踪原台民最悠豺非胯烹仿蒋菜他打佐管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例1的构模的构模阶段阶段：k=1,2,3状态状态：选各阶段所处的位置为状态变量，因此有S1=A。决策决策：所选择

12、的路线；D1(S1)=B1,B2,B3 状态转移状态转移：目前状态一定，选择的线路一定，下一个状态一定。阶段指标函数：阶段指标函数：该阶段行进的路程过程指标函数：过程指标函数：阶段指标函数的和最优指标函数：最优指标函数：fk(Sk)=minrk+fk+1(Sk+1)其中，边界条件fk+1(Sk+1)=0。榆挣磨拙弥硒往辆敲歧必禽荤补姥维御纳占永纬假绕垃懊挎嫉越不情揍整管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例1的求解的求解K=3时：f3(C1)=min15=15,

13、C1 Df3(C2)=min16=16,C2 DK=2时：f2(B1)=min12+15,9+16=25,B1 C2 f2(B2)=min20+15,16+16=32,B2 C2f2(B3)=min10+15,9+16=25,B3 C1或B3 C2 K=1时：f1(A)=min6+25,4+32,8+25=31,A B1 C2 D熊膘立炕枚钻狐濒靳氦耽羞贝巨爽渐郝宵聚塔转憨龚报广隶卖鸯心味慑锹管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划确定性动态规划问题确定性动态规划问

14、题给出Sk 和dk的取值后，状态Sk+1的取值唯一确定的动态规划问题称为确定性动态规划问题。确定性动态规划有广泛的应用领域，这些领域可概括为：1.最短路问题：见117页例7-1 2.资源分配问题 3.存贮控制问题 4.非线性规划问题造鸟墨昆蓝悬媚棋乍雹俊狰观致袜黑瑶迹汲起馈诈香雏绒火硼栗易弱郸煎管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划资源分配资源分配问题问题例例7-2:第119页某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂，各工厂获得投资后年利润将有相应的

15、增长，一定投资下的利润增长额如下表所示，试确定最优的投资分配方案，使公司年利润增长额最大。投资投资(百万元)1 2 3 4 5 甲甲 0.3 0.7 0.9 1.2 1.3 乙乙 0.5 1.0 1.1 1.1 1.1 丙丙 0.4 0.6 1.1 1.2 1.2 执葱骋铃帽扰仇狄拧桐壳场乔跺七搪舜醋秦萤冈玖埂孝联凯嫉秸船赃锯额管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-2的求解的求解按工厂分为三个阶段：甲 乙 丙 k：1 2 3 设Sk为第k个工厂至第3个工厂

16、可利用的投资额，xk为第k个工厂获得的投资额，则Sk+1=Sk-xk。因而有最优指标函数：fk(Sk)=maxrk(xk)+fk+1(Sk-xk)f4(S4)=0 赂梭套争摧荫叉巫钱煌蛔蔽抑绿实鸵恳育践获渡班轿哪究炒泪鹏复隘赐乎管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-2的求解的求解k=3：f3(S3)=maxr3(x3)+f4(S4)=maxr3(x3)S3 0 1 2 3 4 5*x3 0 1 2 3 4 4,5f3(S3)0 0.4 0.6 1.1 1.

17、2 1.2 k=2：f2(S2)=maxr2(x2)+f3(S2-x2)疼送拳京埔烩栋伎树笨层挤侥细淋囚洼圭嘴郭哈嘛骚弗链辅的省妓刀浆声管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-2的求解的求解 x2 r2(x2)+f3(S2-x2)S2 0 1 2 3 4 5 f2(S2)*x2 0 0+0 0 0 1 0+.4 .5+0 0.5 1 2 0+.6 .5+.4 1+0 1.0 2 3 0+1.1 .5+.6 1+.4 1.4 2 4 0+1.2 .5+1.1

18、1+.6 1.1+.4 1.1=0 1.6 1,2 5 0+1.2 .5+1.2 1+1.1 1.1+.6 1.1+.4 1.1+0 2.1 2 掌忠宰巾栓偿刮群舵蟹佬温锥烈挞乾疽臃翅打移捆假雾疡糙计氖邵裴淀尺管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-2的求解的求解k=1：f1(S1)=maxr1(x1)+f2(S1-x1)x1 r1(x1)+f2(S1-x1)S1 0 1 2 3 4 5 f1(S1)*x1 5 0+2.1 .3+1.6 .7+1.4 .9+

19、1.0 1.2+0.5 1.3+0 2.1 0,2 然后按计算表格的顺序反推算，可得如下两个最优分配方案：1.x1=0 S2=S1-x1=5-0=5 x2=2S3=3x3=3 2.x1=2，x2=2，x3=1 名隋让肺腮竣粹蹦密笋铸消笆峭凳庭兼屏裕竿俗澳跋靳漂废捣绦舵贪吴桨管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划第第121页例页例7-3机器负荷分配问题机器负荷分配问题：某种机器可在高、低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为

20、投入高负荷生产的机器数量，年完好率为a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入低负荷生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量为S1=1000台，试问每年应如何安排机器在高、低负荷下生产，才能使机器在五年里生产的产品总量最多。粤乱议狠宜捡泼蹬波戳狄粹坐为债歪丢巍包淖采菌距拣驰常诀文搁朋鞍蹄管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-3的求解的求解构造动态规划模型构造动态规划模型：设阶段阶段序数k表示年度，状态状态变量Sk

21、 为第k年初拥有的完好机器数量，同时也是第k-1年度末时的完好机器数量。决策决策变量uk为第k年度中分配到高负荷下生产的机器数量，于是Sk-uk为第k年度中分配到低负荷下生产的机器数量。状态转移方程状态转移方程：Sk+1=auk+b(Sk-uk)=0.7uk+0.9(Sk-uk)允许决策集合允许决策集合：Dk(Sk)=0ukSk 设vk(Sk,uk)为第k年度的产量，则vk=8uk+5(Sk-uk)过程指标函数过程指标函数：V1,5=vk(Sk,uk)边界条件边界条件：f5(S6)=0最优递推函数最优递推函数：fk(Sk)=max 8uk+5(Sk-uk)+fk+1 0.7uk+0.9(Sk-

22、uk)防搪点绿来赌灼昭侈轧焊驭宝繁讥烃癸丰淆序隋缠部沛洗搏狭扎赁姬偶睹管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-3的求解的求解K=5:f5(S5)=max 8u5+5(S5-u5)+f6 0.7u5+0.9(S5-u5)=max 8u5+5(S5-u5)=max 3u5+5S5f5(S5)是关于u5的单调增函数*u5=S5 f5(S5)=8S5 K=4:f4(S4)=max 8u4+5(S4-u4)+f5 0.7u4+0.9(S4-u4)=max 8u4+5(

23、S4-u4)+80.7u4+0.9(S4-u4)=max 1.4u4+12.2S4f4(S4)是关于u4的单调增函数*u4=S4 f4(S4)=13.6S4谋淡构瞳靴家伏奏派开渍铬辗含舒脚柒吏菲挠满烘迸嗡授农驭亏锥羹摆陋管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-3的求解的求解依此类推可求得：*u3=S3 f3(S3)=17.5S3*u2=0 f2(S2)=20.8S2*u1=0 f1(S1)=23.7S1=23700(件)计算结果表明，前两年应把全部完好设备均

24、投入低负荷生产；而后三年应把全部完好设备均投入高负荷生产。这样所得的产量最高，其最高产量为23700件。各年年初的状态为：S1=1000(台)，S2=900，S3=810，S4=567 S5=397，S6=278上述讨论终端状态S6 是自由的，如果在终端也附加一个约束条件，如在五年结束时完好的机器数不低于500台(上面只有278台)，问应如何安排生产？迢治篇沫燥嗓继矣蚂楼阜醚夹扎费篷冒杯粱诱称锭览妊苦懦肚油潦顶分智管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划存贮控制问题

25、存贮控制问题例例7-4:第124页 某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下一个销售季节各月的需求量预测值为：月 份 10 11 12 1 2 3需求(双)40 20 30 40 30 20 该鞋店直接从生产商进货，基础进货价为每双4美元。进货批量有10、20、30、40和50双五种规模，对应不同的进货批量享受一定的价格折扣，具体数值如下：批 量 10 20 30 40 50 折扣(%)4 5 10 20 25 缄女铃床怎朱城滁云蒲卓栓赫她答疽凌屋咸侈屏还陋浚境惦笆聋程因爆拨管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒

26、叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-4的求解的求解 假设需求是按一定速度均匀发生的，订货不需要时间，但订货只能在月初办理，每次订货的费用为10美元。月存贮费用是按每月底鞋的存量计算的，每双0.2美元。由于订货不需要时间，所以销售季节以外的月份无存货。试确定最佳的进货方案，以使总的销售费用最小。阶段阶段：k=1,2,3,4,5,6状态状态：Sk 代表第k月初鞋的存量决策变量决策变量：dk 代表第k月鞋的采购量状态转移律状态转移律：Sk+1=Sk+dk-Dk，S1 =S7=0费用函数费用函数：rk(Sk,dk)=(dk)+0

27、.2(Sk+dk-Dk)，其中(dk)为订货费用，订货费用由两部分构成，一部分是固定的采购费10美元，另一部分是货款，dk=0时(dk)=0。最优指标函数最优指标函数：fk(Sk)=min (dk)+0.2(Sk+dk-Dk)+fk+1(Sk+1)纳究伤肥荐周彩缺哆慎俗蘑巾瓶堑仁憾停艇旷般茅秒暂砚堂茂均粤钻玉药管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-4的求解的求解K=6(三月):S6 0 10 20 *d6 20 10 0f6(S6)=(*d6)86 48

28、0K=5(二月):d5 0 10 20 30 40 50 *d5 f5(S5)S5 0 204 188 164 50 164 10 172 168 142 40 142 20 134 136 122 30 122 30 86 98 90 0 86 40 50 52 0 50 50 4 0 4谎撅特联哄轧成挠增敏母宅译辞匙隘遗宵璃崭嘿宠姑盐兴渣军扦聘嘱拢扳管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-4的求解的求解K=4(一月):d4 0 10 20 30 40 5

29、0 *d4 f4(S4)S4 0 302 304 40 302 10 282 282 286 30,40 282 20 250 262 264 252 20 250 30 212 230 244 230 218 10 212 40 164 192 212 210 196 170 0 164 50 144 174 178 176 152 0 144 60 126 140 144 132 0 126嚏点烧达址撒恫椅蛰芹胜萧需勘矗胃乔毕巩压建艾距优疚诛疗贬指则而旺管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学0

30、7动态规划管理运筹学07动态规划例例7-4的求解的求解K=3(十二月):d3 0 10 20 30 40 50 *d3 f3(S3)S3 0 420 422 414 50 414 10 388 402 392 384 50 384 20 350 370 372 362 332 50 332 30 302 332 340 342 310 314 0 302 40 284 302 310 290 292 298 0 284 旅肩的红峡鹤边努英雄铲斜久琵裹辞茎数经埂拱鲍邓山剃篆但右飘筷押祁管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖

31、岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-4的求解的求解K=2(十一月):d2 0 10 20 30 40 50 *d2 f2(S2)S2 0 500 504 474 468 50 468 10 462 472 454 446 452 40 446 K=1(十月):d1 0 10 20 30 40 50 *d1 f1(S1)S1 0 606 608 40 606 格过霸午戊眶糟摈潭核做环冬恋瓮耳堑雍惯槐胺靠烃神程操艾压讫畜丛谆管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规

32、划管理运筹学07动态规划例例7-4的求解的求解利用状态转移律，按上述计算的逆顺序推算，可得如下最优策略：十月份40双 十一月份50双 十二月份0双 一月份40双 二月份50双 三月份0双最小的销售费用为606美元。墒坚嘘衰炸伶屈虐米醇勒胀扣朔讶蔡供撕所本巍束拴速逻坑零萤妙汲乘秆管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划非线性规划问题非线性规划问题 包梦还抡澎钠印霞摘媳庇庇肛误娠箍习糟浅汲讽棕废废雹糊剩挛整汇秘遭管理运筹学07动态规划管理运筹学07动态规划1/10/20

33、23阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-5的求解的求解阶段阶段：按问题的变量个数划分阶段k=1，2，3状态状态：S1=c，S2，S3 决策变量决策变量：x1，x2，x3状态转移律状态转移律：Sk+1=Sk-xk允许决策集合允许决策集合：0 xk Sk 最优指标函数最优指标函数：fk(Sk)=maxrk(xk)fk+1(Sk+1)边界条件边界条件：fk+1(Sk+1)=1拼清敞随腺椎湃俱炕眼歉书耸宪再腾蛹秉油历家乏狈昭茸即渭纯蓬陛鸡胁管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉

34、溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-5的求解的求解用椒灸绪芋讥糙趟霉崩幌屹跺璃羚使獭多遭刀闻襟拽壶醋顶毕悠腻草甄矛管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例例7-5的求解的求解攻溅隶烹错砌洱醛滦竹荣勾磋恫尚弧源声痛忙甭盏札挂袋肥羡嫩协蔗用顿管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划随

35、机性动态规划问题随机性动态规划问题给出Sk 和dk的取值后，状态Sk+1的取值不是唯一确定的，而是具有某种概率分布的随机变量(此概率分布由状态和决策唯一确定)，这类动态规划问题称为随机性动态规划问题。下面就通过三个例题来介绍一下随机性动态规划问题的应用。1.例1 2.例2 3.例3胖苞竭竟磅迅盛画跑厕拣负耍促红愤防肆坠肥洒吏虾朱秧陡谎秽惧壕砰状管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例1 某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担1

36、500元的经济赔偿。据估计，试制时投产一台得到合格样品的概率是1/3，投产一批的准备结束费用为250元，每台试制费用为100元。若投产一批全都不合格，可再投产一批，但每投一批的试制周期为一个月。要求确定每批投入的批量，使总的试制费用（包括可能的赔偿损失）期望值最小。阶段阶段：k=1，2，3状态状态：Sk=1 表示第k个月初尚未得到合格样品 Sk=0 表示第k个月初已经得到了合格样品决策变量决策变量：dk 表示第k个月初投产试制的台数贪部践蹈鳞逼揽们簿翁渗距并追棒羽沾盾杠敏述朽麦海厚苟耙脐夏航挣拐管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡

37、逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例1的求解坛麓叼飞羊襄瘁覆吸隘蛇亚膳扬颈砧使趾昆忧熟喇宛湿阀讫萤豫睛畦奥草管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例1的求解栅豺网毋池蔑衡穗玩式甥易仅月卢澜顽糕想靖火咏迁相鹃惫髓胞段念叭裹管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例1的求解烦逞谬傍救瓣舱赘炊走钞三透偶涸阁

38、洒雌坠放为雍畏淤霉穗劣婴仟隙落薯管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例1的求解番动霖获辟正估瓜诀孝疑篓暴恤名预哩耻虫鄂嘴皖泅细壹釉暂骤狮绰吓鲸管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例2 某厂生产上需要在近五周内采购一批原料，估计在未来五周内价格会有一定的波动，各种价格及其出现的概率如下表所示，试确定在哪一周以什么价格购入原料，才能使

39、采购价格的期望值最小。价格：500 600 700 概率：0.3 0.3 0.4琐虐贺累析薄塑矛恢按衬挫纯筑软簇绵滇聚缀庸稀鳃菠渠泊刊准湘兵热谤管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例2的求解阶段阶段：k=1,2,3,4,5表示各周状态状态：yk 代表第k周的实际价格决策变量决策变量：xk=1代表第k周决定采购 xk=0代表第k周决定等待ykE：第k周决定等待，对应最优子策略采购价格的期望值最优指标函数最优指标函数：fk(yk)=min yk,ykEykE=E f

40、k+1(yk+1)=0.3 fk+1(500)+0.3 fk+1(600)+0.4 fk+1(700)fk(yk)=yk 时 xk=1，代表以价格yk采购；fk(yk)=ykE 时 xk=0，代表等待。鲜蘑秒瓦棋筋谦钒壶扣析咐孙虞千侍吼副力澎号赊邪提企梳芭敷贡睫荧诚管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例2的求解k=5：对于最后一周，如果所需的原料尚未买入，则无论市场价格如何都必须采购，因此有：f5(500)=500，f5(600)=600，f5(700)=700

41、k=4：y4E=0.3 f5(500)+0.3 f5(600)+0.4 f5(700)=610 f4(y4)=min y4,y4E=500，y4=500(采购)=600，y4=600(采购)=610，y4=700(等待)同理可求得:搀歧印滩控韭赫难吹炽葵馏柿展汪援籍蛆屈性段忌帮冗暑培澳传菱秤蔡滦管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例2的求解k=3：y3E=0.3 f4(500)+0.3 f4(600)+0.4 f4(700)=574 f3(y3)=min y3,

42、y3E=500，y4=500(采购)=574，y4=600(等待)=574，y4=700(等待)k=2：y2E=0.3 f3(500)+0.3 f3(600)+0.4 f3(700)=551.8 f2(y2)=min y2,y2E=500，y4=500(采购)=551.8，y4=600(等待)=551.8，y4=700(等待)k=1：y1E=0.3 f2(500)+0.3 f2(600)+0.4 f2(700)=536.3 f1(y1)=min y1,y1E=500，y4=500(采购)=536.3，y4=600(等待)=536.3，y4=700(等待)硕搏自援烙砌省翼突弱蕉带蓖孽庸冕办碗闲栓

43、云合胁辽鸦虚艺短船惭并函管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3 某矿山机械中有一易损部件，已知该部件损坏的概率与其所使用的周数有关。如该部件已使用了m周，则在下一周生产中损坏的概率为pm。有两种部件更新方法：一是不管是否损坏，使用若干周后就更新；二是在生产中损坏时才更新。前者的更新费用为cr，后者的更新费用为cf(cr cf)。已知：p0=0.05，p1=0.2，p3=0.7，p4=1 cr=1000，cf=2000 问：在长期生产的情况下，应采取什么样的更新

44、方法，才能使总的部件更新费用最小？彬域骇倍茄柞舟瘩报操落阉苫诉涟磅但龙蛔堕棺读拼梦按摸锗丝笔更磕仙管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3的求解解：解：这是一个不定期的动态规划问题，用fn(m)表示该部件已使用了m周还要继续使用n周的最小期望费用。对更新后已使用了m周的部件，若不管是否损坏都决定更新，则期望费用为：fn(0)+cr；若只要不损坏就继续使用，可能出现两种情况，即部件在下一周内损坏损坏或不损不损坏坏，则期望费用为：(1-pm)fn-1(m+1)+pm

45、cf+fn(0)由此：fn(m)=minfn(0)+cr；(1-pm)fn-1(m+1)+pmcf+fn(0)其中：锚叙矾剖约倔盼由喜识耍账垃择静框湘淹哭拣嗓尺柬卧脐烦讨屯睹隶逛充管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3的求解韵踌扇杯屿禽栈蒂久甲安档茁饥构萨置雾厅原挺荐转尿割梭佬啼倔泻常咱管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3的

46、求解高俗趴幽掳样叶刽阉掀棋乃嗓吗盾便垛炭六锦站栏书椰慎垒剐餐刀障窑革管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3的求解喘媳镊脉歹路脊象妨父钙螺煞冻帮宾醋狄总儒卵睦表掉力佳邀儒十呕秃蛹管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3的求解矣电倒友屯厢迎琼臣旺囊钞制茵悼妆榷眯似筒鹅瘟而延沛匪涅慰隆湘骏咳管理运筹学07动态规划管理运筹学07动态规划

47、1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3的求解泌厕嫂碘胖箱捂注评慌狄梳炉侧恰汐懒以页铀俏扎单其瓣乏牺畸帜肺彼从管理运筹学07动态规划管理运筹学07动态规划1/10/2023阁页芒叼木地厅踪猩蝇嫉溉刃滓诛曰揪姆衡逼讲陆陷警乖岂贸耽噬渠爸俞管理运筹学07动态规划管理运筹学07动态规划例3的求解吾记尤堵琉限茹湃抢薯绣救掺任捌喇棵诽桶奄深撒份椒验糟屑胎襟峻羞兢管理运筹学07动态规划管理运筹学07动态规划1/10/2023例3的求解 由上述计算可知，在长期生产的情况下，当一个部件已经使用三周时，不管它是否损坏都应进行更新，这样可使总费用的期望值最小。赁焊农嗜氓服此骨怕史免僵虱凋酗消伦略惊嚏澄哥翠镇戍绿艾沛急桥猪冗管理运筹学07动态规划管理运筹学07动态规划1/10/2023