下载文档原格式
动态规划方法求解线性规划问题动态规划是一种常用的优化方法，可以用来求解线性规划问题。
线性规划是一种数学建模方法，用于在给定的一组约束条件下，寻找使目标函数最大（或最小）的变量值。
本文将介绍动态规划方法在解决线性规划问题中的应用。
一、线性规划问题的定义和形式线性规划问题可以用下列形式来描述：目标函数：max/min Z = c₁x₁ + c₂x₂ + ... + cₙxₙ约束条件：a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙ其中，c₁、c₂、...、cₙ为目标函数的系数，x₁、x₂、...、xₙ为变量，a₁₁、a₁₂、...、aₙₙ为约束条件的系数，b₁、b₂、...、bₙ为约束条件的常数。
目标是找到使目标函数最大（或最小）的变量值。
二、动态规划方法求解线性规划问题的基本思想动态规划方法可以将线性规划问题转化为一个多阶段决策问题，并通过递推的方式求解最优解。
具体步骤如下：1. 将线性规划问题转化为标准形式：将不等式约束转化为等式约束，并引入松弛变量。
2. 构建动态规划模型：定义状态和状态转移方程。
3. 初始化：确定初始状态和初始条件。
4. 递推求解：根据状态转移方程，逐步计算得到最优解。
5. 回溯得到最优解：根据递推过程中记录的状态，回溯得到最优解。
三、动态规划方法求解线性规划问题的具体步骤1. 将线性规划问题转化为标准形式：将不等式约束转化为等式约束，并引入松弛变量。
例如，将约束条件 a₁₁x₁ + a₁₂x₂ ≤ b₁转化为 a₁₁x₁ + a₁₂x₂ + x₃ = b₁，其中 x₃为松弛变量。
2. 构建动态规划模型：定义状态和状态转移方程。
定义状态：设 f(i,j) 表示前 i 个约束条件中，使得目标函数最大（或最小）的变量值。
状态转移方程：f(i,j) = max/min { f(i-1,j), f(i-1,j-aᵢ₋₁₁x₁ - aᵢ₋₁₂x₂) +cᵢ₋₁x₁ + cᵢ₋₁x₂ }其中，f(i-1,j) 表示不使用第 i 个约束条件时的最优解，f(i-1,j-aᵢ₋₁₁x₁ -aᵢ₋₁₂x₂) + cᵢ₋₁x₁ + cᵢ₋₁x₂表示使用第 i 个约束条件时的最优解。
动态规划算法详解及经典例题⼀、基本概念（1）⼀种使⽤多阶段决策过程最优的通⽤⽅法。
（2）动态规划过程是：每次决策依赖于当前状态，⼜随即引起状态的转移。
⼀个决策序列就是在变化的状态中产⽣出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
假设问题是由交叠的⼦问题所构成，我们就能够⽤动态规划技术来解决它。
⼀般来说，这种⼦问题出⾃对给定问题求解的递推关系中，这个递推关系包括了同样问题的更⼩⼦问题的解。
动态规划法建议，与其对交叠⼦问题⼀次重新的求解，不如把每⼀个较⼩⼦问题仅仅求解⼀次并把结果记录在表中（动态规划也是空间换时间的）。
这样就能够从表中得到原始问题的解。
（3）动态规划经常常使⽤于解决最优化问题，这些问题多表现为多阶段决策。
关于多阶段决策：在实际中，⼈们经常遇到这样⼀类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若⼲个联系的阶段。
⽽在各阶段中。
⼈们都须要作出⽅案的选择。
我们称之为决策。
⽽且当⼀个阶段的决策之后，经常影响到下⼀个阶段的决策，从⽽影响整个过程的活动。
这样，各个阶段所确定的决策就构成⼀个决策序列，常称之为策略。
因为各个阶段可供选择的决策往往不⽌⼀个。
因⽽就可能有很多决策以供选择，这些可供选择的策略构成⼀个集合，我们称之为同意策略集合（简称策略集合）。
每⼀个策略都对应地确定⼀种活动的效果。
我们假定这个效果能够⽤数量来衡量。
因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择⼀个策略，使其在预定的标准下达到最好的效果。
经常是⼈们所关⼼的问题。
我们称这种策略为最优策略，这类问题就称为多阶段决策问题。
（4）多阶段决策问题举例：机器负荷分配问题某种机器能够在⾼低两种不同的负荷下进⾏⽣产。
在⾼负荷下⽣产时。
产品的年产量g和投⼊⽣产的机器数量x的关系为g=g(x)，这时的年完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0<a<1)；在低负荷下⽣产时，产品的年产量h和投⼊⽣产的机器数量y 的关系为h=h(y)。
动态规划方法求解线性规划问题动态规划是一种常用的优化方法，可以用来求解线性规划问题。
线性规划是数学规划的一种重要方法，它通过线性约束条件和线性目标函数来求解最优解。
在实际应用中，线性规划时常遇到大规模问题，传统的求解方法效率较低。
而动态规划方法可以通过将大问题分解为小问题，并利用子问题的最优解来求解整个问题的最优解，从而提高求解效率。
动态规划方法求解线性规划问题的步骤如下：1. 确定问题的状态：将线性规划问题转化为动态规划问题时，需要确定问题的状态。
对于线性规划问题，状态可以是决策变量的取值范围或者问题的某种特征。
2. 定义状态转移方程：根据问题的状态，定义状态转移方程。
状态转移方程描述了问题从一个状态转移到另一个状态时的转移规则。
3. 确定边界条件：确定问题的边界条件，即问题的初始状态和结束状态。
4. 构建动态规划表：根据状态转移方程和边界条件，构建动态规划表。
动态规划表是一个二维表格，用于存储问题的中间结果。
5. 填充动态规划表：根据状态转移方程和边界条件，填充动态规划表。
填充的过程是从表格的左上角开始，逐行逐列地计算表格中的每一个单元格的值，直到填充到右下角。
6. 根据动态规划表求解最优解：根据填充好的动态规划表，可以得到问题的最优解。
最优解可以通过回溯法得到，即从右下角开始，根据动态规划表的值和状态转移方程，逆向推导出问题的最优解。
动态规划方法求解线性规划问题的优点在于可以将大问题分解为小问题进行求解，并且可以利用子问题的最优解来求解整个问题的最优解。
这样可以大大提高求解效率，特殊是对于大规模问题来说。
此外，动态规划方法还具有较好的可扩展性和灵便性，可以根据问题的特点进行相应的调整和优化。
举例来说，假设有一个线性规划问题，要求在满足一定约束条件的情况下，最大化目标函数的值。
可以将该问题转化为动态规划问题，并按照上述步骤进行求解。
首先确定问题的状态，可以将决策变量的取值范围作为状态。
然后定义状态转移方程，根据问题的约束条件和目标函数，确定状态之间的转移规则。
动态规划算法求最优解问题何思瑶;沈樾;辛琰钰【摘要】在实际生活中,寻找最优解的问题时常出现,它帮助我们寻找解决问题的最佳方案.然而,它在为我们提供便利的同时也给我们带来了极大的考验.本文采用动态规划算法将待求解问题划分成若干个子问题分别求解,最终得到原问题的最优答案,以寻找问题的最优方案.【期刊名称】《电声技术》【年(卷),期】2019(043)003【总页数】3页(P42-44)【关键词】算法;最优解;子问题;动态规划【作者】何思瑶;沈樾;辛琰钰【作者单位】河北农业大学,河北保定071000;河北农业大学,河北保定071000;河北农业大学,河北保定071000【正文语种】中文【中图分类】TP301.61 算法简介动态规划算法的基本思想是将待求解问题划分成若干个相互关联的子问题，通过对子问题的求解以自底向上的方式计算出最优值。
动态规划算法通过提高程序的空间复杂度来达到降低时间复杂度的目的。
由此可见，使用动态规划算法进行求解的问题需要具备两个性质，即最优子结构性质[1]和重叠子问题性质[1]。
最优子结构性质：即待求解问题的最优解包含了其子问题的最优解[2]，因此，通过求解子问题的最优解可逐步构成原问题的最优解。
重叠子问题性质：即求解由原问题分解出的子问题后，其结果可用于求解其他的子问题，做到对每一个子问题只求解一次，避免产生不必要的重复计算，以获得更高的解题效率。
对于动态规划算法的具体实现，可分为以下步骤。
(1)分析问题，找出问题的最优解性质及其结构特征；(2)以自底向上的方式计算出最优值并对过程中产生的结果进行存储；(3)根据计算过程中存储的信息构造并输出最优解。
2 算法的具体实现2.1 问题分析本文分析并求解最长公共子序列问题[1]，以此展示动态规划算法求最优解问题的具体实现。
在最长公共子序列问题的求解过程中，可将原字符串分解为长度不相同的多个子字符串，由子字符串的最长公共子序列加上不属于子字符串的原字符串中共有元素构成原问题的最长公共子序列，降低了程序的时间复杂度[3]。
动态规划方法求解线性规划问题动态规划是一种常用的优化方法，可以用于求解线性规划问题。
线性规划是一种数学建模方法，用于在给定的约束条件下最大化或最小化线性目标函数。
在实际问题中，线性规划经常出现，例如资源分配、生产计划、运输问题等。
动态规划方法是一种将问题分解为子问题并逐步求解的方法。
它的基本思想是通过对问题的分析，将大问题分解为小问题，并将小问题的解组合起来得到整个问题的最优解。
动态规划方法适用于具有最优子结构和重叠子问题性质的问题。
下面以一个具体的线性规划问题为例，介绍动态规划方法的求解步骤：假设有一个生产厂家需要生产两种产品A和B，每种产品的生产需要消耗不同的资源，并且有一定的利润。
资源的供应是有限的，且每种产品的生产数量也是有限的。
现在需要确定生产哪些产品以及生产的数量，使得总利润最大化。
首先，将问题转化为数学模型。
假设产品A的单位利润为5，产品B的单位利润为8，产品A的生产需要消耗1个资源，产品B的生产需要消耗2个资源。
假设资源的供应量为10，且产品A和产品B的生产数量都不能超过5。
定义状态变量和决策变量。
假设状态变量为i，表示第i个资源的剩余量，决策变量为x，表示生产产品A的数量。
建立状态转移方程。
根据题目要求，可以得到状态转移方程为：f(i) = max(f(i-1), f(i-1) + 5 * x)其中，f(i)表示剩余资源为i时的最大利润。
确定边界条件。
当剩余资源为0时，最大利润为0，即f(0) = 0。
通过递推求解。
根据状态转移方程和边界条件，可以递推求解出剩余资源为10时的最大利润。
最后，根据求解出的最大利润，可以确定生产产品A和产品B的数量，以及最终的利润。
以上是动态规划方法求解线性规划问题的基本步骤。
在实际应用中，可能会涉及更多的约束条件和决策变量，需要根据具体情况进行建模和求解。
需要注意的是，动态规划方法虽然可以有效地求解线性规划问题，但对于复杂的问题，可能需要较大的计算量和时间复杂度。
动态规划方法求解线性规划问题动态规划是一种常用的优化算法，可以用于求解线性规划问题。
在线性规划中，我们需要找到一组变量的取值，使得目标函数达到最大或最小值，同时满足一系列线性约束条件。
动态规划方法可以帮助我们高效地解决这类问题。
首先，我们需要明确线性规划问题的数学模型。
假设我们有n个变量x1, x2, ..., xn，目标函数为f(x1, x2, ..., xn)，约束条件为g1(x1, x2, ..., xn) ≤ b1, g2(x1, x2, ..., xn) ≤ b2, ..., gm(x1, x2, ..., xn) ≤ bm。
其中，f(x1, x2, ..., xn)是一个关于变量x1, x2, ..., xn的线性函数，g1(x1, x2, ..., xn), g2(x1, x2, ..., xn), ..., gm(x1, x2, ..., xn)是关于变量x1, x2, ..., xn的线性不等式，b1, b2, ..., bm是常数。
接下来，我们可以使用动态规划方法求解线性规划问题的最优解。
具体步骤如下：1. 定义状态：我们需要定义子问题的状态。
在这里，我们可以将线性规划问题的状态定义为子问题的目标函数值。
2. 确定状态转移方程：我们需要确定子问题之间的转移关系。
在这里，我们可以使用递推的方式来定义子问题之间的关系。
假设dp[i]表示目标函数值为i时的最优解，那么我们可以得到状态转移方程为：dp[i] = max(dp[i - c1] + v1, dp[i - c2] +v2, ..., dp[i - cn] + vn)，其中ci表示第i个约束条件的系数，vi表示第i个约束条件的常数。
3. 初始化边界条件：我们需要初始化子问题的边界条件。
在这里，我们可以将dp[0]初始化为0，表示目标函数值为0时的最优解。
4. 递推求解：我们可以使用动态规划的递推方式来求解子问题的最优解。
从dp[1]开始，依次计算dp[2], dp[3], ..., dp[k]，直到dp[m]，其中m为目标函数的最大值或最小值。
运筹学习题库一、线性规划1．某工厂生产甲、乙、丙三种产品，单位产品所需工时分别为2、3、1个工时；单位产品所需原材料分别为3、1、5公斤；单位产品利润分别为2元、3元、5元。
工厂每天可利用的工时为12个，可供应的原材料为15公斤。
1）试确定使总利润为最大的日生产计划和最大利润。
2）若由于原材料涨价，使得产品丙的单位利润比原来减少了2元，问原来的最优生产计划变否？若不变，说明为什么；若变，请求出新的最优生产计划和最优利润。
3）在保持现行最优基不变的情况下，若要增加一种资源量，应首先考虑增加哪种资源？为什么？单位资源增量所支付的费用是多少才合算？为什么？2．给出一线性规划问题如下：max z = 3x1 + x2x1 + x2≤4－x1 + x2≤26x1 + 2x2≤18x１，x2≥0试用对偶理论判断该问题是否存在以x１、x2和x3为基变量的最优解？3．用单纯形法求解某个目标函数为max，约束为≤形式，x4、x5为松弛变量的线性规划问题的最终表如下：试用改进单纯形法原理求该问题的数学模型。
4．给出一个线性规划问题如下：max z = x1 +2 x2 +3 x3x1 + 2x2 + 3x3≤84x1+ 5x3≤12x1，x2 ，x3 ≥0已知其对偶问题的最优解为Y* = (1，0 )，试用对偶理论求上述问题的最优解和最优值。
5．试用大M法求下述线性规划问题的最优解和最优值（不能用图解法）：max z = 3x 1 – 3 x 2x1 + x2 ≥1 2x 1 + 3x 2 ≤6x 1，x 2 ≥06．已知一线性规划问题如下：max z = 5x 1 + 2 x 2 + 4 x 3 3 x 1 + x 2 + 2 x 3 ≤ 46 x 1 + 3 x 2 + 5 x 3 ≤ 10 x 1，x 2，x 3 ≥ 0试用松紧定理判断X = ( 0，0，2 )T 是否是该问题的最优解，若不是，说明为什么；若是， 请求出相应的目标函数值。
例1 求解下列整数规划的最优解：()123123max 45634510..01,2,3,j j Z x x x x x x s t x j x =++++⎧⎪⎨=⎪⎩≤≥为整数.解 （1）建立动态规划模型：阶段变量：将给每一个变量j x 赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3. 设状态变量k s 表示从第k 阶段到第3阶段约束右端最大值，则10.j s = 设决策变量k x 表示第k 阶段赋给变量k x 的值(1,2,3)k =. 状态转移方程：2113223,4.s s x s s x =-=-阶段指标：111122223333(,)4,(,)5,(,)6.u s x x u s x x u s x x === 基本方程；()(){}()3113,2,1044()max ,()0.s k k k k k k k k k k x a f s u s x f s f s ++⎡⎤=⎢⎥⎢⎥⎣⎦⎧=+⎪⎨⎪=⎩≤≤ 其中1233,4, 5.a a a === （1） 用逆序法求解： 当3k =时，()(){}{}33333443330055max 6max 6,ssx x f s x f s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=≤≤≤而{}[]30,1,2,3,4,5,6,7,8,9,10.s x ∈表示不超过x 的最大整数。
因此，当30,1,2,3,4s =时，30x =；当35,6,7,8,9s =时，3x 可取0或1；当310s =时，3x 可取0，1，2，由此确定()33.f s 现将有关数据列入表4.1中当时，有()(){}(){}22222332322220044max 5max 54,ssx x f s xf s xf s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=+-≤≤≤≤而{}20,1,2,3,4,5,6,7,8,9,10s ∈。
所以当20,1,2,3s =时，20x =；当24,5,6,7s =时，201x =或；当28,9,10s =时20,1,2x =。
由此确定()22f s 。
现将有关数据列入表4.2中.当时,有()(){}(){}11111221211110033max 4max 43,ssx x f s x f s x f s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=+-≤≤≤≤而110,s =故1x 只能取0,1,2,3,由此确定()11f s 。
现将有关数据列入表4.3中。
11222()13.4 4.21,x s s x *==*=1时,f 取得最大值又由查表得及33330, 4.10.2,1,0,max 13.s x x x Z ***======3再由表查得因此,最优解为 x 最优解例5 用动态规划方法解下列非线性规划问题⎩⎨⎧=≥≤++⋅⋅=3,2,1 0 max 3213221i x c x x x x x x z i 解： 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。
按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k =1，2，3 设状态变量为s 1，s 2，s 3，s 4并记s 1≤c 取问题中的变量x 1，x 2，x 3为决策变量 状态转移方程为： s 3=x 3 s 3+x 2=s 2 s 2+x 1=s 1≤c 允许决策集合为： x 3=s 30≤x 2≤s 20≤x 1≤s 1各阶段指标函数为：v 1（x 1）=x 1 v 2（x 2）=x 22 v 3（x 3）=x 3，各指标函数以乘积方式结合，最优指标函数f k （s k ）表示从第k 阶段初始状态s k 出发到第3阶段所得到的最大值，则动态规划基本方程为：⎪⎩⎪⎨⎧==⋅=++∈1)(1,,2,3 )]()([max )(4411)(s f k s f x v s f k k k k s D x k k k k k 用逆序解法由后向前依次求解：k =3时，334433)(33)(max )]()([max )(33333s x s f x v s f s x s D x ==⋅==∈x 3*=s 3k =2时，)]([max )(max )]()([max )(2222032203322)(222222222x s x s x s f x v s f s x s x s D x -⋅=⋅=⋅=≤≤≤≤∈令h 2（s 2，x 2）=x 22（s 2－x 2） 用经典解析法求极值点：032222222=-=x s x dx dh 解得：2232s x =x 2=0（舍）22222262x s dx h d -=02322222222<-==s s x dx h d所以2232s x =是极大值点。
32222222274)32()32()(s s s s s f =-=2*232s x =k =1时，])(274[max )274(max )]()([max )(3111032102211)(111111111x s x s x s f x v s f s x s x s D x -⋅=⋅=⋅=≤≤≤≤∈令3111111)(274),(x s x x s h -⋅= 0)1()(2712)(274211131111=--+-=x s x x s dx dh 解得：1141s x =x 1=s 1（舍）)2)((2724)(2724)(2712)1()(271211111112112112112s x x s x s x x s x s dx h d --=-+----=02794121112112<-==s s x dx h d 所以1141s x =是极大值点。
41311111641)41(27441)(s s s s s f =-⋅=1*141s x =由于s 1未知，所以对s 1再求极值，)641(max )(max 41011011s s f cs cs ≤≤≤≤= 显然s 1=c 时，f 1（s 1）取得最大值411641)(c s f =反向追踪得各阶段最优决策及最优值：s 1=cc s x 41411*1==411641)(c s f = c x s s 43*112=-= c s x 21322*2==33222161274)(c s s f ==c x s s 41*223=-=c s x 413*3==c s s f 41)(333== 所以最优解为：4**3*2*1641,41,21,41c z c x c x c x ==== 例6 用动态规划方法解下列非线性规划问题⎩⎨⎧=≥≤++⋅⋅=3,2,1 06 max 32133221j x x x x x x x z j解： 按变量个数将原问题分为三个阶段，阶段变量k =1，2，3； 选择x k 为决策变量；状态变量s k 表示第k 阶段至第3阶段决策变量之和；取小区间长度Δ=1，小区间数目m =6/1=6，状态变量s k 的取值点为：⎩⎨⎧=≥=626,5,4,3,2,1,01s k s k 状态转移方程：s k +1=s k －x k ；允许决策集合：D k （s k ）=｛x k |0≤x k ≤s k ｝ k =1，2，3 x k ，s k 均在分割点上取值；阶段指标函数分别为：g 1（x 1）=x 12g 2（x 2）=x 2 g 3（x 3）=x 33，最优指标函数f k （s k ）表示从第k 阶段状态s k 出发到第3阶段所得到的最大值，动态规划的基本方程为：⎪⎩⎪⎨⎧==⋅=++≤≤1)(1,2,3 )]()([max )(44110s f k s f x g s f k k k k s x k k kk k =3时，333333)(max )(33s x s f s x === s 3及x 3取值点较多，计算结果以表格形式给出，见表6.1-6.3所示。
表6.1 计算结果表6.2 计算结果表6.3计算结果112112s3=s2－x2*=4－1=3，查表6.1得：x3*=3，所以最优解为：x1*=2，x2*=1，x3*=3，f1(s1)=108。
上面讨论的问题仅有一个约束条件。
对具有多个约束条件的问题，同样可以用动态规划方法求解，但这时是一个多维动态规划问题，解法上比较繁琐一些。
例7 某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表6.4所示。
试问在各地区如何设置销售点可使每月总利润最大。
表6.4利润值将问题分为3个阶段，k=1，2，3；决策变量x k表示分配给第k个地区的销售点数；状态变量为s k表示分配给第k个至第3个地区的销售点总数；状态转移方程：s k+1=s k－x k，其中s1=4；允许决策集合：D k（s k）=｛x k|0≤x k≤s k｝阶段指标函数：g k（x k）表示x k个销售点分配给第k个地区所获得的利润；最优指标函数f k（s k）表示将数量为s k的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：⎪⎩⎪⎨⎧==-+=+≤≤0)(1,2,3 )]()([max )(4410s f k x s f x g s f k k k k k s x k k kk 数值计算如表所示。
表6.5 k =3时计算结果表6.6 k =2时计算结果表6.7 k =1时计算结果1231售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。
例9 （生产—库存问题）某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。
解: 以每个时期作为一个阶段，该问题分为4个阶段，k =1，2，3，4； 决策变量x k 表示第k 阶段生产的产品数； 状态变量s k 表示第k 阶段初的库存量；以d k 表示第k 阶段的需求，则状态转移方程：s k +1=s k +x k －d k ；k =4，3，2，1 由于期初及期末库存为0，所以s 1=0，s 5=0；允许决策集合D k （s k ）的确定：当s k ≥d k 时，x k 可以为0，当s k <d k 时，至少应生产d k －s k ，故x k 的下限为max （0，d k －s k ）每期最大生产能力为6，x k 最大不超过6，由于期末库存为0，x k 还应小于本期至4期需求之和减去本期的库存量，k kj j s d -∑=4，所以x k 的上限为min （k kj j s d -∑=4，6），故有：D k （s k ）=｛x k | max （0，d k －s k ）≤x k ≤min （k kj j s d -∑=4，6）｝阶段指标函数r k （s k ，x k ）表示第k 期的生产费用与存贮费用之和：⎩⎨⎧=++==6,5,4,3,2,15.0305.0),(k k k k k k k k x s x x s x s r 最优指标函数f k （s k ）表示第k 期库存为s k 到第4期末的生产与存贮最低费用，动态规划基本方程为：⎪⎩⎪⎨⎧==+=++∈0)(1,2,3,4 )](),([min )(5511)(s f k s f x s r s f k k k k k s D x k k k k k 先求出各状态允许状态集合及允许决策集合，如表6.8所示。
