2021年2021年度例1某工厂和用户订合同在四个月内出售定量的某产品产量.讲义.ppt

例1 某工厂与用户订合同,在四个月内出售一定量的某产品，产量限制为10的倍数,工厂每月最多生产100件,产品可以存储,存储费用为每台200元,每个月的需求量及每件产品的生产成本如下表
在1月初没有存货情况下确定每月的生产量，要求既能满足每月的合同需求量，又使生产成本和存储费用达到最小。
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
1
我们可把此问题的解决动态地视为各月(称阶段)先后作出决策(指生产量)的过程——多阶段的决策过程,每个月作决策时,不能仅考虑本月的费用(称阶段指标),因为本月的决策会对以后各月的决策产生影响,因此应考虑从本月直到第四月末的总费用(总指标)
月份
每件生产成本（百元）
需要量（件）
1
70
60
2
72
70
3
80
120
4
76
60
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
2
每月的决策依赖于各月初仓库中的存货量(称为始端)而和以前各月如何造成这存货量的情况无关(称为无后效性)
1月
2月
3月
4月
月初存储量
0
40
70
0
产量（件）
100
100
50
60
当1月初无存货时的最优决策为：
则第四月的决策为月初仓储为0时的最优决策，第三、四月的决策即为第三月初仓储数为70时的最优决策，以及第二、三、四月的决策即为第二月初仓储数为40时的最优决策。
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
3
1、动态规划的基本概念1)阶段:整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，记k为阶段变量2)状态:每个阶段开始所处的自然状况,它描述了研究问题过程的状况。xk 表示第k阶段的状态变量。
无后效性:如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
4
3)决策:某一阶段的状态确定后,可作出各种选择演变到下一阶段某一状态,这种选择手段称为决策。uk(xk):第k阶段处于状态xk时决策变量,决策变量限制的取值范围为允许决策集合。Dk(xk): xk的允许决策集合。
4)策略:由每个阶段的决策按顺序排列组成的集合。p(x1) ={u1(x1),u2(x2),...un(xn)}
由第k阶段的状态xk开始到终止状态的后部子过程的策略:
pk(xk)= {uk(xk),uk+1(xk+1),…, un(xn)}。
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
5
5)状态转移方程:
xk+1=Tk(xk,uk)
即:第k个阶段状态为xk,作出决策uk,那么第k+1阶段的状态变量 xk+1也被完全确定。
6)指标函数和最优值函数:指标函数是系统执行某一策略所产生结果的数量表示,它定义在全过程和所有后部子过程上,即:
V(u1,u2,...,un,x1,x2,...xn+1) Vk(uk,...,un,xk,...xn+1) 指标函数的最优值称为最优函数。
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
6
7)最优策略:使指标函数Vk达到最优的策略是从阶段k开始的后部子过程的最优策略, pk*={uk*,... un*}
最优策略：即全过程的最优策略记为p*
最优性原理:最优决策的任何截断仍是最优的,这是动态规划的基本原理。
动态规划方法:符合最优性原理,无后效性的多阶段决策过程并进行求解的方法。 动态规划的逆序求解方法:从终点逐段向始点方向寻找最优的一种方法。
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
7
例2 ,第1阶段是1月份,…,第4阶段是4月份
xk——第k阶段开始的产品存储数(状态变量)
uk——第k阶段的产量（决策变量）；
ck——第k阶段每件产品的生产成本；
qk——第k阶段的需求量；
阶段指标函数为: vk(xk, uk) = ckuk + 2xk；
状态转移方程为: xk+1 = xk + uk - qk；
逆序法基本方程为：
fk(xk,uk)=min{vk(xk,uk)+fk+1(xk+1)|uk∈Dk(xk)}
k = 3, 2, 1。
例1某工厂和用户订合同在四个月内出售定量的某产品产量.
2021/1/25
8
例2:求从始点v1到终点v10的最短路径(两顶点连线上的数