试求出最优策略的一般关系式。
显然，这时状态转移方程为
k段的指标函数为
令表示由状态出发，从第k年至第n年末时所生产的产品的总产量最大值。
可写出逆推关系式为：
我们知道，在低负荷下生产的时间愈长，机器完好率愈高，但生产产量少。
而在高负荷下生产产量会增加，但机器损坏大。
这样，即使每台产量高，总起来看产量也不高。
从前面的数字计算可以看出，前几年一般是全部用于低负荷生产，后几年则全部用于高负荷生产，这样才产量最高。
如果总共为n年，从低负荷转为高负荷生产的是第t年，1≤t≤n。
即是说，从1至t−1年在低负荷下生产，t至n年在高负荷下生产。
现在要分析t与系数a、b、c、d是什么关系。
从回收率看，（b−a）值愈大，表示在高负荷下生产时，机车损坏情况比在低负荷时严重得多，因此t值应选大些。
从产量看，（c−d）值愈大，表示在高负荷下生产较有利，故t应选小些。
下面我们从（9-2）式这一基本方程出发来求出t与（b−a）、（c−d）的关系。
令。
则在低负荷生产时有，高负荷生产时有。
对第n段，有
由于c＞d，所以应选1才能使最大。
也就是说，最后一年应全部投入高负荷生产。
故
对n-1段，根据（9-2）式有
因此，欲要满足上式极值关系的条件是当
时，应取，即n−1年仍应全部在高负荷下生产。
否则，当（9-4）式不满足时，应取，即n−1年应全部投入低负荷生产。
由前面知道，只要在第k年投入低负荷生产，那么递推计算结果必然是从第1年到第k年均为低负荷生产，即有。
可见，算出后，前几年就没有必要再计算了。
故只需研究哪一年由低负荷转入高负荷生产，即从那一年开始变为1就行。
根据这点，现只分析满足（9-4）式的情况。
由于，故（9-3）式变为
又由于，将它代入上式得
对n-2段，由（9-2）式有
由此可知，只要满足极值条件式
就应选，否则为0，即应继续在高负荷下生产。
依次类推，如果转入高负荷下生产的是第t年，则由
可以推出，应满足极值关系的条件必然是：
相应的有最优策略
它就是例2在始端固定终端自由情况下最优策略的一般结果。
从这个例子看到，应用动态规划，可以在不求出数值解的情况下，确定最优策略的结构。
可见，只要知道了a，b，c，d四个值，就总可找到一个t值，满足（9-5）式，且
例如题中给定的，代入（9-5）式，应有
可见，所以t=3，即从第三年开始将全部机器投入高负荷生产，五年内总产量最高。
上面的讨论表明：
当x在［0，］上离散地变化时，利用递推关系式逐步计算或表格法而求出数值解。
当x在［0，］上连续地变化时，若和是线性函数或凸函数时，根据递推关系式运用解析法不难求出和最优解；若和不是线性函数或凸函数时，一般来说，解析法不能奏效，那只好利用递推关系式（9-1）求其数值解。
首先要把问题离散化，即把区间［0，］进行分割，令x=0，Δ，2Δ，…，mΔ=。
其Δ的大小，应根据计算精度和计算机容量等来确定。
然后规定所有的和决策变量只在这些分割点上取值。
这样，递推关系式（9-1）便可写为
对依次计算，可逐步求出及相应的最优决策，最后求得就是所求的最大总收入。
这种离散化算法可以编成程序在计算机中计算。
1。
2二维资源分配问题
设有两种原料，数量各为a和b单位，需要分配用于生产n种产品。
如果第一种原料以数量为单位，第二种原料以数量为单位，用于生产第i种产品，其收入为。
问应如何分配这两种原料于n种产品的生产使总收入最大?
此问题可写成静态规划问题：
用动态规划方法来解，状态变量和决策变量要取二维的。
设状态变量（x，y）:
x——分配用于生产第k种产品至第n种产品的第一种原料的单位数量。
y——分配用于生产第k种产品至第n种产品的第二种原料的单位数量。
决策变量：
——分配给第k种产品用的第一种原料的单位数量。
——分配给第k种产品用的第二种原料的单位数量。
状态转换关系：
，式中和分别表示用来生产第k+1种产品至第n种产品的第一种和第二种原料的单位数量。
允许决策集合：
表示以第一种原料数量为x单位，第二种原料数量为y单位，分配用于生产第k种产品至第n种产品时所得到的最大收入。
故可写出逆推关系为
最后求得即为所求问题的最大收入。
1。
拉格朗日乘数法
引入拉格朗日乘数λ，将二维分配问题化为
满足条件；，其中λ作为一个固定的参数。
令
于是问题变为，满足且为整数
这是一个一维分配问题，可用对一维的方法去求解。
这里，由于λ是参数，因此，最优解是参数λ的函数，相应的也是λ的函数。
即，为其解。
如果，则可证明为原问题的最优解。
如果，将调整λ的值（利用插值法逐渐确定λ），直到满足为止。
这样的降维方法在理论上有保证，在计算上是可行的，故对高维问题，可用上述拉格朗日乘数法的思想来降低维数。
2。
逐次逼近法
这是另一种降维方法，先保持一个变量不变，对另一个变量实现最优化。
然后交替地固定，以迭代的形式反复进行，直到获得某种要求为止。
先设为满足的一个可行解，固定x在，先对y求解，则二维分配问题变为一维问题：
可用对一维的方法来求解。
设这解为，然后再固定y为，对x求解，即
设其解为，再固定x为，对y求解，这样依次轮换下去得到一系列的解。
因为
，
故函数值序列是单调上升的，但不一定收敛到绝对的最优解，一般只收敛到某一局部最优解。
因此，在实际计算时，可选择几个初始点进行计算，然后从所得到的几个局部最优解中选出一个最好的。
3．粗格子点法（疏密法）
在采用离散化的方法计算时，先将矩形定义域：
0≤x≤a，0≤y≤b分成网格，然后在这些格子点上进行计算。
如将a、b各分为和等份，则总共有（+1）·（+1）个格点，故对每个k值需要计算的共有（+1）·（+1）个。
因此，这里的计算量是相当大的。
随着分点加多，格子点数也增多，那时的计算量将大得惊人。
为了使计算可行，往往根据问题要求的精确度，采用粗格子点法逐步缩小区域来减少计算量。
粗格子点法是先用少数的格子点进行粗糙的计算，在求出相应的最优解后，再在最优解附近的小范围内进一步细分，并求在细分格子点上的最优解，如此继续细分下去直到满足要求为止。
这种方法可能会出现最优解“漏网”的情况，因此，应用此法时要结合对指标函数的特性进行分析。
1。
3固定资金分配问题
设有n个生产行业，都需要某两种资源。
对于第k个生产行业，如果用第1种资源和第2种资源进行生产，可获得利润为。
若第1种资源的单位价格为a，第2种资源的单位价格为b，现有资金Z。
问应购买第1种资源多少单位（设为X），第2种资源多少单位（设为Y），分配到n个生产行业，使总利润最大?
此问题的数学模型可写为
（1）把资源分配利润表换算成资金分配利润表，即将换算成。
但必须注意，分配的资金应先使较贵的资源单位最大。
设有资金分配到第k个生产行业，则由知，在给定z的情况下，若购买第2种资源单位，则留下的资金只能购买第1种资源单位，。
于是得到资金利润函数为
式中（z/b）指以资金z购买第2种资源的最大单位数，指以资金z购买了第2种资源单位以后能购买第1种资源的最大单位数。
（2）计算最优资金分配所获得最大利润。
规定最优值函数表示以总的资金z分配到k至n个生产行业可能获得的最大利润。
则有逆推关系式：
（3）求出，即为问题的解。
这样，就把一个原含有两个状态变量的问题转化为只含有一个状态变量的问题。
二、生产与存储问题
在生产和经营管理中，经常遇到要合理地安排生产（或购买）与库存的问题，达到既要满足社会的需要，又要尽量降低成本费用。
因此，正确制定生产（或采购）策略，确定不同时期的生产量（或采购量）和库存量，以使总的生产成本费用和库存费用之和最小，这就是生产与存储问题的最优化目标。
2。
1生产计划问题
设某公司对某种产品要制定一项n个阶段的生产（或购买）计划。
已知它的初始库存量为零，每阶段生产（或购买）该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。
问该公司如何制定每个阶段的生产（或采购）计划，从而使总成本最小。
设为第k阶段对产品的需求量，为第k阶段该产品的生产量（或采购量），为第k阶段结束时的产品库存量。
则有
表示第k阶段生产产品时的成本费用，它包括生产准备成本K和产品成本a（其中a是单位产品成本）两项费用。
即
表示在第k阶段结束时有库存量所需的存储费用。
故k阶段的成本费用为
m表示每阶段最多能生产该产品的上限数。
上述问题的数学模型为
用动态规划方法来求解，可看作一个n阶段决策问题。
令为状态变量，它表示第k阶段开始时的库存量。
为决策变量，它表示第k阶段的生产量。
状态转移方程为
最优值函数表示从第1阶段初始库存量为0到第k阶段末库存量为时的最小总费用。
顺序递推关系式为：
其中。
这是因为一方面每阶段生产的上限为m；另一方面由于保证供应，故第k-1阶段末的库存量必须非负，即，所以。
边界条件为或从边界条件出发，利用上面的递推关系式，对每个k，计算出中的在0至之间的值，最后求得的即为所求的最小总费用。
例3某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如表9-5所示。
表9-5
时期（k）
1
2
3
4
需求量（）
2
3
2
4
假定该厂生产每批产品的固定成本为3千元，若不生产就为0；每单位产品成本为1千元；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期末未售出的产品，每单位需付存储费0。
5千元。
还假定在第一个时期的初始库存量为0，第四个时期之末的库存量也为0。
试问该厂应如何安排各个时期的生产与库存，才能在满足市场需要的条件下，使总成本最小。
解用动态规划方法来求解，其符号含义与上面相同。
按四个时期将问题分为四个阶段。
由题意知，在第k时期内的生产成本为
第k时期末库存量为时的存储费用为
故第k时期内的总成本为
而动态规划的顺序递推关系式为
其中和边界条件
当k=1时，由
对在0至之间的值分别进行计算。
同理得
当k=2时，由
其中。
对在0至之间的值分别进行计算。
从而有
当k=3时，由
其中。
对在0至之间的值分别进行计算，从而有
当k=4时，因要求第4时期之末的库存量为0，即=0，故有
再按计算的顺序反推算，可找出每个时期的最优生产决策为：
其相应的最小总成本为20。
5千元。
把上面例题中的有关数据列成表9-6，可找出一些规律性的东西。
表9-6
阶段i
0
1
2
3
4
需求量
—
2
3
2
4
生产量
—
5
0
6
0
库存量
0
3
0
4
0
由表中的数字可以看到，这类库存问题有如下特征：
（1）对每个i，有，（i＝1，2，3，4）其中=0。
（2）对于最优生产决策来说，可分解为两个子问题，一个是从第1阶段到第2阶段；另一个是从第3阶段到第4阶段。
每个子问题的最优生产决策特别简单，它们的最小总成本之和就等于原问题的最小总成本。
如果对每个i，都有，则称该点的生产决策（或称一个策略）具有再生产点性质（又称重生性质）。
如果=0，则称阶段i为再生产点（又称重生点）。
由假设=0和=0，故阶段0和n是再生产点。
可以证明：
若库存问题的目标函数g（x）在凸集合S上是凹函数（或凸函数），则g（x）在S的顶点上具有再生产点性质的最优策略。
下面运用再生产点性质来求库存问题为凹函数的解。
设（j≤i）为阶段j到阶段i的总成本，给定j−1和i是再生产点，并且阶段j到阶段i期间的产品全部由阶段j供给。
则
根据两个再生点之间的最优策略，可以得到一个更有效的动态规划递推关系式。
设最优值函数表示在阶段i末库存量=0时，从阶段1到阶段i的最小成本。
则对应的递推关系式为，边界条件为
为了确定最优生产决策，逐个计算。
则（0）为n个阶段的最小总成本。
设为计算时，使（9-7）式右边最小的j值，即
则从阶段到阶段n的最优生产决策为：
故阶段为再生产点。
为了进一步确定阶段−1到阶段1的最优生产决策，记m=−1，而是在计算时，使（9-7）式右边最小的j值，则从阶段到阶段的最优生产决策为：
故阶段为再生产点，其余依此类推。
例4利用再生产点性质解例3。
解因都是凹函数，故可利用再生产点性质来计算。
（1）按（9-6）式计算
（2）按（9-7）式和（9-8）式计算
（3）找出最优生产决策
由，故。
因所以
故，所以最优生产决策为：
，相应的最小总成本为20。
5千元。
例5某车间需要按月在月底供应一定数量的某种部件给总装车间，由于生产条件的变化，该车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。
已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时数如表9-7所示。
表9-7
月份k
0
1
2
3
4
5
6
需求量
0
8
5
3
2
7
4
单位工时
11
18
13
17
20
10
设仓库容量限制为H=9，开始库存量为2，期终库存量为0，需要制定一个半年的逐月生产计划，既使得满足需要和库容量的限制，又使得生产这种部件的总耗费工时数为最少。
解按月份划分阶段，用k表示月份序号。
设状态变量为第k段开始时（本段需求量送出之前，上段产品送入之后）部件库存量。
决策变量为第k段内的部件生产量。
状态转移方程：
且，故允许决策集合为
最优值函数表示在第k段开始的库存量为时，从第k段至第6段所生产部件的最小累计工时数。
因而可写出逆推关系式为
当k=6时，因要求期终库存量为0，即=0。
因每月的生产是供应下月的需要，故第6个月不用生产，即=0。
因此=0，而由（9-9）式有
当k=5时，由（9-9）式有，故
及最优解
当k=4时，有
其中的允许决策集合由（9-11）式确定。
由，故有。
又，因而。
而由（9-10）式知：
，所以为，故得及最优解
当k=3时，
由（9-11）式得为，故得及最优解。
当k=2时，
其中为，故得及最优解。
当k=1时，
其中为，故得及最优解
当k=0时，
其中为，故得及最优解，因=2，所以=357和=7
再按计算顺序反推，即得各阶段最优决策为：
所以，0至5月最优生产计划为：
7，4，9，3，0，4，最小总工时为357。
2。
2不确定性的采购问题
在实际问题中，还会遇到某些多阶段决策过程，其状态转移不是完全确定的，出现了随机性因素，状态转移是按照某种已知概率分布取值的。
具有这种性质的多阶段决策过程称为随机性决策过程。
用动态规划方法也可处理这类随机性问题，又称为随机性动态规划。
升级会员 