『无忧PPT』PPT免费下载,PPT素材,PPT背景PPT图片PPT模板PPT制作免费下载的门户网站Rss 2.0无忧PPT-PPT门户网站

PPT模板下载排行榜(New) 无忧PPT原创PPT模板 无忧PPT官方微博 精品PPT模板

运筹学-北京邮电大学-5PPT资源下载

::推荐PPT模板::
  • ::运筹学-北京邮电大学-5下载地址::
  • 下载地址1  
  • 上传作者:chinappt
  • 来源:运筹学-北京邮电大学|PowerPoint资源|免费下载|PPT模板|PPT资源|商务|PowerPoint工具|business|PPTresources
  • 运筹学-北京邮电大学-5简介
  • 运筹学-北京邮电大学-5

    第五章 动态规划
    不要过河拆桥
    动态规划  Dynamic programming
    五十年代贝尔曼(B. E. Bellman)为代表的研究成果
    属于现代控制理论的一部分
    以长远利益为目标的一系列决策
    最优化原理,可归结为一个递推公式
         决策树法
        例5.1.1 最短路问题
    表现为明显的阶段性
    一条从A 到B 的最短路径中的任何一段都是最短的
        5.1.2 动态规划的基本概念及递推公式
    状态
    最短路问题中,各个节点就是状态
    生产库存问题中,库存量是状态
    物资分配问题中,剩余的物资量是状态
    控制变量(决策变量)
    最短路问题中,走哪条路
    生产库存问题中,各阶段的产品生产量
    物资分配问题中,分配给每个地区的物资量
    阶段的编号与递推的方向
    一般采用反向递推,所以阶段的编号也是逆向的
    当然也可以正向递推
        动态规划的步骤
    1、确定问题的阶段和编号
    2、确定状态变量
    用 Sk 表示第 k 阶段的状态变量及其值
    3、确定决策变量
    用 xk 表示第 k 阶段的决策变量,并以 xk*表示该阶段的最优决策
    4、状态转移方程
       sk-1= g(sk, xk) 反向编号     sk+1= g(sk, xk) 正向编号      
    5、直接效果
    直接一步转移的效果 dk(sk, xk)
    6、总效果函数
    指某阶段某状态下到终端状态的总效果,它是一个递推公式
        动态规划的步骤
    hk 是一般表达形式,求当前阶段当前状态下的阶段最优总效果
    (1) 如最短路问题,是累加形式,此时有
    5.2 动态规划模型举例
        5.2.1 产品生产计划安排问题
         例1  某工厂生产某种产品的月生产能力为10件,已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时,可以存储起来备以后各月销售,一件产品的月存储费为2元,试安排月生产计划并做到:
          1、保证满足每月的销售量,并规定计划期初和期末库存为零;
          2、在生产能力允许范围内,安排每月生产量计划使产品总成本(即生产费用加存储费)最低。
        例1 产品生产计划安排
    设xk为第k阶段生产量,则有直接成本
                       dk(sk, xk)= ck xk+2sk
    状态转移公式为
                      sk-1= sk+ xk- yk
    总成本递推公式
    第一阶段最优决策表
    第二阶段:最大可能库存量 7 件
    由状态转移方程: s1=s2+x2-120 及 x210,可知 s2[2,7],min x2=5
    由阶段效果递推公式有:f2(2,10)=d2(2,10)+f1*(0,6)     =22+8010+456=1260
    得第二阶段最优决策表,如下
    第二阶段最优决策表
    第三阶段:最大可能库存量 4 件
    由状态转移方程: s2=s3+x3-72 及 x310,可知 s3[0,4],min x3=5
    由阶段效果递推公式有:f3(1,10)=d3(1,10)+f2*(4,8)           =21+7210+1104=1826
    得第三阶段最优决策表,如下
    第三阶段最优决策表
    第四阶段:初始库存量 s4=0
    由状态转移方程: s3=s4+x4-60
    可知 x46,由阶段效果递推公式有:f4(0,6)=d4(0,6)+f3*(0,10)           =706+1902=2322
    得第四阶段最优决策表,如下
        例2 生产–库存管理问题(连续变量)
        设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤,700公斤,500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比,系数为0.005。厂内有仓库可存放产品,存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。
    解:四个季度为四个阶段,采用阶段编号与季度顺序一致。
            设 sk 为第k季初的库存量,则边界条件为 s1=s5=0
            设 xk 为第k季的生产量,设 yk 为第k季的订货量;
             sk ,xk ,yk 都取实数,状态转移方程为 sk+1=sk+xk - yk
             仍采用反向递推,但注意阶段编号是正向的
             目标函数为
    例2 生产–库存管理问题(连续变量)
    第一步:(第四季度) 总效果  f4(s4,x4)=0.005 x42+s4
         由边界条件有: s5= s4 + x4 – y4=0,解得:x4*=1200 – s4
         将x4*代入 f4(s4,x4)得:
            f4*(s4)=0.005(1200 – s4)2+s4=7200 –11 s4+0.005 s42
    第二步:(第三、四季度) 总效果  f3(s3,x3)=0.005 x32+s3+ f4*(s4)
        将 s4= s3 + x3 – 500 代入  f3(s3,x3) 得:
         例2 生产–库存管理问题(连续变量)
    第三步:(第二、三、四季度) 总效果
                 f2(s2,x2)=0.005 x22+s2+ f3*(s3)
        将 s3= s2 + x2 - 700 代入  f2(s2,x2) 得:
         例2 生产–库存管理问题(连续变量)
    第四步:(第一、二、三、四季度) 总效果
                 f1(s1,x1)=0.005 x12+s1+ f2*(s2)
        将 s2= s1 + x1 – 600= x1 – 600  代入  f1(s1,x1) 得:
        5.2.2 资源分配问题
    例3    某公司有9个推销员在全国三个不同市场推销货物,这三个市场里推销人员数与收益的关系如下表,试作出使总收益最大的分配方案。
        例3  第一阶段:给第三市场分配
        s1 有0~9种可能,第一阶段最优决策表如下:
        例3  第二阶段:给第二市场分配
        s2 有0~9种可能,第二阶段最优决策表如下:
        例3  第三阶段:给第一市场分配
        由边界条件 s3=9,第三阶段最优决策表如下:
        5.2.2 资源分配问题
    例4  项目选择问题
          某工厂预计明年有A,B,C,D四个新建项目,每个项目的投资额 wk及其投资后的收益 vk如下表所示。投资总额为30万元,问如何选择项目才能使总收益最大。
    上述问题的静态规划模型如下:
        例4 项目选择问题
    解:设项目选择的顺序为A, B, C, D;
    1、阶段 k=1, 2, 3, 4 分别对应 D, C, B, A项目的选择过程
    2、第 k 阶段的状态 sk,代表第 k 阶段初尚未分配的投资额
    3、第 k 阶段的决策变量 xk,,代表第 k 阶段分配的投资额
    4、状态转移方程为 sk–1= sk– wk xk
    5、直接效益 dk(sk ,xk)= vk 或 0
    6、总效益递推公式

        例4 第一阶段(项目D)的选择过程
    s1<8 时,x1只能取0;w1=8, v1=5
    例4 第二阶段(项目C)的选择过程
        例4 第三阶段(项目B)的选择过程
        5.2.3 串联系统可靠性问题
    例5  有 A, B, C 三部机器串联生产某种产品,由于工艺技术问题,产品常出现次品。统计结果表明,机器 A, B, C 产生次品的概率分别为 pA=30%, PB=40%, PC=20%, 而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率,决定拨款 5 万元进行技术改造,以便最大限度地提高产品的成品率指标。现提出如下四种改进方案:
    方案1: 不拨款,机器保持原状;
    方案2: 加装监视设备,每部机器需款 1 万元;
    方案3: 加装设备,每部机器需款 2 万元;
    方案4: 同时加装监视及控制设备,每部机器需款 3 万元;
    采用各方案后,各部机器的次品率如下表。
        例5 串联机器可靠性问题
    解:为三台机器分配改造拨款,设拨款顺序为A, B, C,阶段序号反向编号为 k,即第一阶段计算给机器 C 拨款的效果。
            设 sk 为第 k 阶段剩余款,则边界条件为 s3=5;
            设 xk 为第 k 阶段的拨款额;
            状态转移方程为 sk-1=sk-xk;
            目标函数为  max R=(1-PA)(1-PB)(1-PC)
             仍采用反向递推
    第一阶段 :对机器 C 拨款的效果
             R1(s1,x1)=d1(s1,x1) R0(s0,x0)= d1(s1,x1)
    第二阶段最优决策表
    第二阶段 :对机器 B, C 拨款的效果
       由于机器 A 最多只需 3 万元,故 s2  2
       递推公式:
          R2(s2,x2)=d2(s2,x2) R1(s1,x1*)
         例:R2(3,2)=d2(3,2) R1(1,1)=(1-0.2) 0.9=0.72
         得第二阶段最优决策表
    第二阶段最优决策表
    第三阶段 :对机器 A, B, C 拨款的效果
          边界条件:s3 = 5
       递推公式:
          R3(s3,x3)=d3(s3,x3) R2(s2,x2*)
         例:R3(5,3)=d3(5,3) R2(2,2)=(1-0.05) 0.64=0.608
         得第三阶段最优决策表
        例6 用动态规划解非线性规划
    动态规划总结
    二大类:生产-库存问题;资源分配问题

  • 最热经济下载

    没有任何图片PPT下载资源
     
    网友评论:(只显示最新10条。评论内容只代表网友观点,与本站立场无关!) 【发表评论
    PPT搜索