下载文档原格式
动态规划方法求解线性规划问题1. 线性规划问题简介线性规划是一种常见的数学优化方法，用于求解线性约束条件下的最优解。
它的目标是在给定的约束条件下，找到使目标函数取得最大（或者最小）值的变量取值。
2. 动态规划方法概述动态规划是一种通过将问题分解为子问题并逐步解决的方法。
它适合于具有重叠子问题和最优子结构性质的问题。
对于线性规划问题，动态规划方法可以通过将问题分解为多个子问题，并利用子问题的最优解来求解整体问题的最优解。
3. 动态规划方法求解线性规划问题的步骤步骤1: 定义状态首先，我们需要定义状态变量。
对于线性规划问题，状态变量可以是目标函数的值，或者是满足约束条件的变量取值。
步骤2: 定义状态转移方程接下来，我们需要定义状态之间的转移关系。
对于线性规划问题，状态转移方程可以表示为：dp[i] = max(dp[i-1] + a[i], a[i])其中，dp[i]表示第i个状态的最优值，a[i]表示第i个状态的值。
步骤3: 初始化状态在动态规划方法中，我们需要初始化第一个状态的值。
对于线性规划问题，我们可以将第一个状态的值设置为目标函数的初始值。
步骤4: 递推求解最优解接下来，我们可以使用状态转移方程递推求解最优解。
通过计算每一个状态的最优值，我们可以得到整体问题的最优解。
步骤5: 回溯求解最优解最后，我们可以通过回溯的方式求解最优解的具体取值。
通过追踪每一个状态的转移路径，我们可以找到使目标函数取得最大（或者最小）值的变量取值。
4. 动态规划方法求解线性规划问题的实例为了更好地理解动态规划方法求解线性规划问题的过程，我们来看一个具体的实例。
假设有一个线性规划问题，目标是最大化目标函数：maximize 3x + 4y约束条件为：2x + y <= 10x + 3y <= 15x, y >= 0我们可以按照以下步骤使用动态规划方法求解该线性规划问题：步骤1: 定义状态我们定义状态变量为目标函数的值，即dp[i]表示目标函数的值为i时的最优解。
动态规划方法求解线性规划问题动态规划是一种常用的优化方法，可以用来求解线性规划问题。
线性规划是一种数学建模方法，用于在给定的一组约束条件下，寻找使目标函数最大（或最小）的变量值。
本文将介绍动态规划方法在解决线性规划问题中的应用。
一、线性规划问题的定义和形式线性规划问题可以用下列形式来描述：目标函数：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 个约束条件时的最优解。
动态规划方法求解线性规划问题动态规划方法是一种常用的优化算法，可以用于求解线性规划问题。
线性规划是一种数学优化问题，其目标是在一组线性约束条件下，最大化或最小化一个线性目标函数。
动态规划方法通过将问题划分为一系列子问题，并利用子问题的最优解来求解整个问题的最优解。
首先，我们需要定义线性规划问题的数学模型。
假设我们有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)是一个线性函数，g1(x1, x2, ..., xn), g2(x1, x2, ..., xn), ..., gm(x1, x2, ..., xn)是一组线性函数，b1, b2, ..., bm是一组常数。
接下来，我们可以使用动态规划方法来求解线性规划问题。
动态规划方法的核心思想是将原问题划分为一系列子问题，并利用子问题的最优解来求解整个问题的最优解。
我们可以使用一个二维数组dp[i][j]来表示子问题的最优解，其中i表示决策变量的个数，j表示目标函数的取值。
具体的求解过程如下：1. 初始化dp数组。
将dp数组的所有元素初始化为无穷大（对于最小化问题）或负无穷大（对于最大化问题），并将dp[0][0]初始化为0。
2. 逐步求解子问题。
从dp[1][1]开始，依次计算dp[i][j]的值。
对于每个dp[i][j]，我们需要考虑两种情况：选择第i个决策变量和不选择第i个决策变量。
如果选择第i个决策变量，则dp[i][j]的值等于dp[i-1][j-c[i]] + f[i]，其中c[i]表示第i个决策变量的系数，f[i]表示第i个决策变量的目标函数系数。
如果不选择第i个决策变量，则dp[i][j]的值等于dp[i-1][j]。
动态规划算法详解及经典例题⼀、基本概念（1）⼀种使⽤多阶段决策过程最优的通⽤⽅法。
（2）动态规划过程是：每次决策依赖于当前状态，⼜随即引起状态的转移。
⼀个决策序列就是在变化的状态中产⽣出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
假设问题是由交叠的⼦问题所构成，我们就能够⽤动态规划技术来解决它。
⼀般来说，这种⼦问题出⾃对给定问题求解的递推关系中，这个递推关系包括了同样问题的更⼩⼦问题的解。
动态规划法建议，与其对交叠⼦问题⼀次重新的求解，不如把每⼀个较⼩⼦问题仅仅求解⼀次并把结果记录在表中（动态规划也是空间换时间的）。
这样就能够从表中得到原始问题的解。
（3）动态规划经常常使⽤于解决最优化问题，这些问题多表现为多阶段决策。
关于多阶段决策：在实际中，⼈们经常遇到这样⼀类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若⼲个联系的阶段。
⽽在各阶段中。
⼈们都须要作出⽅案的选择。
我们称之为决策。
⽽且当⼀个阶段的决策之后，经常影响到下⼀个阶段的决策，从⽽影响整个过程的活动。
这样，各个阶段所确定的决策就构成⼀个决策序列，常称之为策略。
因为各个阶段可供选择的决策往往不⽌⼀个。
因⽽就可能有很多决策以供选择，这些可供选择的策略构成⼀个集合，我们称之为同意策略集合（简称策略集合）。
每⼀个策略都对应地确定⼀种活动的效果。
我们假定这个效果能够⽤数量来衡量。
因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择⼀个策略，使其在预定的标准下达到最好的效果。
经常是⼈们所关⼼的问题。
我们称这种策略为最优策略，这类问题就称为多阶段决策问题。
（4）多阶段决策问题举例：机器负荷分配问题某种机器能够在⾼低两种不同的负荷下进⾏⽣产。
在⾼负荷下⽣产时。
产品的年产量g和投⼊⽣产的机器数量x的关系为g=g(x)，这时的年完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0<a<1)；在低负荷下⽣产时，产品的年产量h和投⼊⽣产的机器数量y 的关系为h=h(y)。
动态规划算法求最优解问题何思瑶;沈樾;辛琰钰【摘要】在实际生活中,寻找最优解的问题时常出现,它帮助我们寻找解决问题的最佳方案.然而,它在为我们提供便利的同时也给我们带来了极大的考验.本文采用动态规划算法将待求解问题划分成若干个子问题分别求解,最终得到原问题的最优答案,以寻找问题的最优方案.【期刊名称】《电声技术》【年(卷),期】2019(043)003【总页数】3页(P42-44)【关键词】算法;最优解;子问题;动态规划【作者】何思瑶;沈樾;辛琰钰【作者单位】河北农业大学,河北保定071000;河北农业大学,河北保定071000;河北农业大学,河北保定071000【正文语种】中文【中图分类】TP301.61 算法简介动态规划算法的基本思想是将待求解问题划分成若干个相互关联的子问题，通过对子问题的求解以自底向上的方式计算出最优值。
动态规划算法通过提高程序的空间复杂度来达到降低时间复杂度的目的。
由此可见，使用动态规划算法进行求解的问题需要具备两个性质，即最优子结构性质[1]和重叠子问题性质[1]。
最优子结构性质：即待求解问题的最优解包含了其子问题的最优解[2]，因此，通过求解子问题的最优解可逐步构成原问题的最优解。
重叠子问题性质：即求解由原问题分解出的子问题后，其结果可用于求解其他的子问题，做到对每一个子问题只求解一次，避免产生不必要的重复计算，以获得更高的解题效率。
对于动态规划算法的具体实现，可分为以下步骤。
(1)分析问题，找出问题的最优解性质及其结构特征；(2)以自底向上的方式计算出最优值并对过程中产生的结果进行存储；(3)根据计算过程中存储的信息构造并输出最优解。
2 算法的具体实现2.1 问题分析本文分析并求解最长公共子序列问题[1]，以此展示动态规划算法求最优解问题的具体实现。
在最长公共子序列问题的求解过程中，可将原字符串分解为长度不相同的多个子字符串，由子字符串的最长公共子序列加上不属于子字符串的原字符串中共有元素构成原问题的最长公共子序列，降低了程序的时间复杂度[3]。
动态规划方法求解线性规划问题动态规划是一种常用的优化算法，可以用于求解线性规划问题。
在线性规划中，我们需要找到一组变量的取值，使得目标函数达到最大或最小值，同时满足一系列线性约束条件。
动态规划方法可以帮助我们高效地解决这类问题。
首先，我们需要明确线性规划问题的数学模型。
假设我们有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 求解下列整数规划的最优解：()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中表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 =。
动态规划算法详解及经典例题动态规划什么是动态规划？动态规划的⼤致思路是把⼀个复杂的问题转化成⼀个分阶段逐步递推的过程，从简单的初始状态⼀步⼀步递推，最终得到复杂问题的最优解。
基本思想与策略编辑:由于动态规划解决的问题多数有重叠⼦问题这个特点，为减少重复计算，对每⼀个⼦问题只解⼀次，将其不同阶段的不同状态保存在⼀个⼆维数组中。
1. 拆分问题：根据问题的可能性把问题划分成通过递推或者递归⼀步⼀步实现。
关键就是这个步骤,动态规划有⼀类问题就是从后往前推到,有时候我们很容易知道 : 如果只有⼀种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前⼀步推导,得到前⼀步的最佳选择 2. 定义问题状态和状态之间的关系：⽤⼀种量化的形式表现出来,类似于⾼中学的推导公式,因为这种式⼦很容易⽤程序写出来,也可以说对程序⽐较亲和(也就是最后所说的状态转移⽅程式) 3. 动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若⼲个⼦问题（阶段），按顺序求解⼦阶段，前⼀⼦问题的解，为后⼀⼦问题的求解提供了有⽤的信息。
在求解任⼀⼦问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。
依次解决各⼦问题，最后⼀个⼦问题就是初始问题的解。
我的理解是：⽐如我们找到最优解,我们应该讲最优解保存下来,为了往前推导时能够使⽤前⼀步的最优解,在这个过程中难免有⼀些相⽐于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每⼀次都把最优解保存了下来,⼤⼤降低了时间复杂度。
动态规划解决问题的过程分为两步：1.寻找状态转移⽅程式2.利⽤状态转移⽅程式⾃底向上求解问题动态规划原理使⽤条件：可分为多个相关⼦问题，⼦问题的解被重复使⽤使⽤条件：可分为多个相关⼦问题，⼦问题的解被重复使⽤Optimal substructure（优化⼦结构）：⼀个问题的优化解包含了⼦问题的优化解缩⼩⼦问题集合，只需那些优化问题中包含的⼦问题，降低实现复杂性我们可以⾃下⽽上的Subteties（重叠⼦问题）：在问题的求解过程中，很多⼦问题的解将被多次使⽤。
例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,67,89s =时，3x 可取0或1；当310s =时，3x 可取0，1，2，由此确定()33.f s 现将有关数据列入表4.1中表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中。
表 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 1v 2（x 2）=x 22v 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 2g 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 计算结果1121123= s 2－x 2*=4－1=3，查表6.1得：x 3*=3，所以最优解为：x 1*=2，x 2*=1，x 3*=3，f 1(s 1)=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 ，其中s 1=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时计算结果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,1 5.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所示。
