第五章动态规划(Dynamic rogramming)
研究多阶段决策问题
1951年提出动态规划。
1957年出版Dynamic Programming
应用:最优调度、资源分配
最优路径、最优控制
设备更新、库存问题
§
例.
某产品从A城运至F城,其间要经过若干
个城镇和若干条道路,路线结构如图所示,
图中给出了每段道路的运费(元),试选
择一条合理的运输路线,使总运费最小?
1
2
3
4
分析:方案①:A→B1→C1→E1→F 运费:26元
方案②: A→B3→C3→E3→F 运费:22元
方案③: A→B2→C1→E2→F 运费:18元
最优方案:方案③
§
阶段:过程的划分,包括时间、空间的划分,
阶段数:n
阶段变量:描述阶段的变量用k 表示,k=1,2,…..,n
状态:描述过程的必要信息。最短路问题中,各个节点就是状态
状态应具有无后效性: 若给定了某阶段状态,则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.
状态变量:描述状态的变量,用s表示。
决策:决定(选择),从一个阶段的状态到
下一个阶段状态的选择。
决策变量:描述决策的变量,用u表示.
策略:决策按顺序构成的序列,用p表示。
动态规划83542 来自淘豆网m.daumloan.com转载请标明出处.
