文档详情

运筹学 动态规划2.ppt

发布:2017-06-19约5.68千字共38页下载文档
文本预览下载声明
解:终端条件:f4(s4)=0 k=3时,递推方程为 s3 D3(s3) s4 60x3+f4(s4) f3(s3) X*3 解:终端条件:f4(s4)=0 k=3时,递推方程为 s3 D3(s3) s4 60x3+f4(s4) f3(s3) X*3 0 0 0 0+0=0 0 0 1 0 1 0+0=0 0 0 … … … … … … 5 0 1 5 0 0+0=0 60+0=60 60 1 … … … … … … 10 0 1 2 10 5 0 0+0=0 60+0=60 120+0=120 120 2 k=2时,递推方程为 s2 D2(s2) s3 40x2+f3(s3) f2(s2) X*2 k=2时 s2 D2(s2) s3 40x2+f3(s3) f2(s2) X*2 0 1 0 1 0+0=0 0 0 … … … … … … 4 0 1 2 4 2 0 0+0=0 40+0=40 80+0=80 80 2 … … … … … … 7 0 1 2 3 7 5 3 1 0+60=60 40+60=100 80+0=80 120+0=120 120 3 … … … … … … 10 0 1 2 3 4 5 10 8 6 4 2 0 0+120=120 40+60=100 80+60=140 120+0=120 160+0=160 200+0=200 200 5 k=1时,递推方程为 s1 D1(s1) s2 60x1+f2(s2) f1(s1) X*1 X1=(0,5,0), X1=(2,2,0),最优值为 Z = 200 s1 D1(s1) s2 60x1+f2(s2) f1(s1) X*1 10 0 1 2 3 10 7 4 1 0+200=200 60+120=180 120+80=200 180+0=180 200 0,2 练习:某厂生产三种产品,各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售,运输能力总重量不超过 6 吨,问如何安排运输,使总利润最大? 种类 1 2 3 重量(吨/公斤) 2 3 4 单件利润(元) 80 130 180 最优方案:X1 =(0.2.0)X2 =(1.0.1)Z=260 P286 10.4 P288 10.14 * * 根据情况决定是否要求学员在课堂上做该题。 * 该公式使用局限性太大,(g-h)/g(b-a)1怎么办?无法使用 * 在生产与经营管理中经常遇到的问题。大批量生产,降低生产成本,但提高库存成本;少量生产,降低库存成本,但增加生产成本,如何找到平衡点,是摆在管理者面前的一个问题。 分为:离散变量和连续变量 管理者往往将其分成若干段:关心的每个阶段产量、生产能力、单位库存价格、库存能力、单位时间需求量等 * 第十章 动态规划应用举例 运筹学 第九章 动态规划应用举例 生产与存储问题 本章内容 资源分配问题 背包问题 复合系统工作可靠性问题 排序问题 设备更新问题 货郎担问题 第一节 资源分配问题 设总投资额为a万元,拟投资于n个项目上,已知对第i个项目投资xi万元,收益函数为gi(xi),问应如何分配资金才可以使总收益最大?这是一个与时间无明显关系的静态最优化问题,可先列出其静态模型为: 据此,有下式: (一)投资分配问题 例1 某公司有资金10万元,若投资于项目(i=1,2,3)的投资额为xi时,其收益分别为g1(x1)=4x1, g2(x2)=9x2, g3(x3)=2x3,问应如何分配投资额才能使总收益最大? 建立模型: 例2 有资金4万元,投资A、B、C三个项目,每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益(万吨)和投入资金(万元)关系见下表: 求对三个项目的最优投资分配,使总投资效益最大。 1、阶段k:每投资一个项目作为一个阶段; 2、状态变量xk:投资第k个项目前的资金数; 3、决策变量dk:第k个项目的投资; 4、决策允许集合:0≤dk≤xk 5、状态转移方程:xk+1=xk-dk 6、阶段指标:vk(xk ,dk)见表中所示; 7、递推方程:fk(xk)=max{vk(xk ,dk)+fk+1(xk+1)} 8、终端条件:f4(x4)=0 分析: k=4,f4(x4)=0 k=3,0≤d3≤x3,x4=x3-d3 k=2,0≤d2≤x2,x3=x2-d2 k=1,0≤d1≤x1,x2=x1-d1 最优解为 x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0, 即项目A投资1万元,项目B投资0万元,
显示全部
相似文档