第四章动态规划
§1 引言
1.1 动态规划的发展及研究内容
动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪50 年代初R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。
例1 最短路线问题
图1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G距离最短（或费用最省）的路线。
图1 最短路线问题
例2 生产计划问题
工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3 （千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。
1.2 决策过程的分类根据过程的时间变量是离散的还是连续的，分为离散时间
决策过程（discrete-time
-56-
decision process ）和连续时间决策过程（continuous-time decision process ）；根据过程的 演变是确定的还是随机的，分为确定性决策过程（deterministic decision process ）和随 机性决策过程（stochastic decision process ），其中应用最广的是确定性多阶段决策过程。 §2 基本概念、基本方程和计算方法
2.1 动态规划的基本概念和基本方程 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。
2.1.1 阶段 阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶
段，以便按阶段的次序解优化问题。阶段变量一般用 k = 1,2,L , n 表示。在例 1 中由 A 出发为 k = 1 ，由 B i (i = 1,2) 出发为 k = 2 ，依此下去从 F i (i = 1,2) 出发为 k = 6 ，共
n = 6 个阶段。在例 2 中按照第一、二、三、四季度分为 k = 1,2,3,4 ，共四个阶段。
2.1.2 状态 状态（state ）表示每个阶段开始时过程所处的自然状况。它应能描述
过程的特征并 且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各 阶段的状态无关。通常还要求状态是直接或间接可以观测的。
描述状态的变量称状态变量（state variable ）。变量允许取值的范围称允许状态集合 (set of admissible states)。用 x k 表示第 k 阶段的状态变量，它可以是一个数或一个向量。 用 X k 表示第 k 阶段的允许状态集合。在例 1 中 x 2 可取 B 1 , B 2 ，或将 B i 定义为
i (i = 1,2) ，则 x 2 = 1 或 2 ，而 X 2 = {1,2} 。
n 个阶段的决策过程有 n + 1 个状态变量，x n +1 表示 x n 演变的结果。在例 1 中 x 7 取 G ，或定义为1 ，即 x 7 = 1 。 根据过程演变的具体情况，状态变量可以是离散的或连
续的。为了计算的方便有时
将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。
状态变量简称为状态。
2.1.3 决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这
种选择手段称为决策（decision ），在最优控制问题中也称为控制（control ）。 描述决
策的变量称决策变量（decision variable ），变量允许取值的范围称允许决策 集合（set of admissible decisions ）。用 u k ( x k ) 表示第 k 阶段处于状态 x k 时的决策变量， 它是 x k 的函数，用U k ( x k ) 表示 x k 的允许决策集合。在例 1 中 u 2 (B 1 ) 可取 C 1 ,C 2 或
C 3 ， 可记作 u 2 (1) = 1,2,3 ，而U 2 (1) = {1,2,3} 。
决策变量简称决策。
2.1.4 策略
决策组成的序列称为策略（policy ）。由初始状态 x 1 开始的全过程的策略记作 p 1n ( x 1 ) ，即
p 1n ( x 1 ) = {u 1 ( x 1 ),u 2 ( x 2 ),L ,u n ( x n )}.
由第 k 阶段的状态 x k 开始到终止状态的后部子过程的策略记作 p kn ( x k ) ，即
p kn ( x k ) = {u k ( x k ),L , u n ( x n )}， k = 1,2,L , n - 1. 类似地，由第 k 到第 j 阶段的子过程的策略记作
-57-
p kj ( x k ) = {u k ( x k ),L ,u j ( x j )}.
可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用 P 1n ( x 1 ), P kn ( x k ), P kj ( x k ) 表示。
2.1.5. 状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用
状态转移方程（equation of state transition ）表示这种演变规律，写作
x k +1 = T k ( x k , u k ), k = 1,2,L , n .
在例 1 中状态转移方程为 x k +1 = u k ( x k ) 。
2.1.6. 指标函数和最优值函数
指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有 后部子过程上的数量函数，用V k ,n (x k , u k , x k +1 ,L , x n +1 ) 表示， k = 1,2,L , n 。指标函 数应具有可分离性，即V k ,n 可表为 x k , u k ,V k +1, n 的函数，记为
V k ,n (x k , u k , x k +1 ,L , x n +1 ) = ?k (x k , u k ,V k +1,n (x k +1 , u k +1 ,L , x n +1 ))
并且函数?k 对于变量V k +1, n 是严格单调的。
过程在第 j 阶段的阶段指标取决于状态 x j 和决策 u j ，用 v j ( x j , u j ) 表示。指标函 数由 v j ( j = 1,2,L , n ) 组成，常见的形式有：
阶段指标之和，即
n
V k ,n (x k , u k , x k +1 ,L , x n +1 ) = ∑v j (x j , u j ) ，
j =k 阶段指标之积，即
n
V k ,n (x k , u k , x k +1 ,L , x n +1 ) = ∏v j (x j , u j ) ，
j =k
阶段指标之极大（或极小），即
（1）
V k ,n (x k , u k , x k ,L , x 1 ) = max(min)v j (x j , u j ) . + n + 1 k ≤ j ≤n
这些形式下第 k 到第 j 阶段子过程的指标函数为V k , j (x k , u k ,L , x j +1 ) 。
根据状态转移方程指标函数 V k ,n 还可以表示为状态 x k 和策略 p kn 的函数，即
V k ,n (x k , p kn ) 。在 x k 给定时指标函数V k ,n 对 p kn 的最优值称为最优值函数（optimal value function ），记为 f k ( x k ) ，即
f k (x k ) = opt V k ,n (x k , p kn ) ，
p kn ∈P kn ( x k )
其中 opt 可根据具体情况取 max 或 min 。
2.1.7 最优策略和最优轨线 使指标函数 V k ,n 达到最优值的策略是从 k 开始的后部子过程的最优策略，记作
p * * * * = {u ,L , u }。 p 是全过程的最优策略，简称最优策略（optimal policy ）
。从初始 kn k n 1n 状态 x (= x * ) 出发，过程按照 p *
和状态转移方程演变所经历的状态
序 列 1 1 1n * * * {x , x ,L , x }称最优轨线（optimal trajectory ）
。 1 2 -58-
n +1
2.1.8 递归方程
如下方程称为递归方程
?? f n +1 ( x n +1 ) = 0或（2） ? f ( x ) = ( x , u ) ? f
( x )}, k = n ,L ,1 opt {v k +1 k +1 ??
k k k k k u ∈U ( x ) k k k 在上述方程中，当 ? 为加法时取 f n +1 (x n +1 ) = 0 ；当 ? 为乘法时，取 f n +1 (x n +1 ) = 1。动
态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子 策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由 k = n + 1 逆 推至 k = 1，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解 法。这时，状态转移方程和递归方程分别为：
r
x k = T (x k +1 ,
u k ), k = 1,L , n ，
k ?? f 0 (x 1）= 0或? f (x ) = opt {v (x , u ) ? f (x )}, k = 1,L , n k k +1 k k +1 k k -1 k ??
u ∈U r
+ ( x k + ) k k 1 1 例 3 用 lingo 求解例 1 最短路线问题。
model:
Title Dynamic Programming; sets:
vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L; road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4, C1 D1 E1 D1,C1 E1,D1 F1,E1 D2,C2 E2,D2 F2,E2 D1,C2 E2,D2 F1,E2 D2,C3 E3,D3 F2,E3 D2,C3 E2,D3 F1,E3 D3,C4 D2,C4 D3, E3,
F2,F1 G,F2 G/:D; endsets data:
D=5 3 3 1 5 1 5 2 2 3 3 3 6 6 3 3
6 8 8
7 6 4 6 2 3
8 2 5 4 3; L=0,,,,,,,,,,,,,,,; enddata
@for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i))); end
纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首 先建立起动态规划的数学模型：
（i ）将过程划分成恰当的阶段。 （ii ）正确选择状态变量 x k ，使它既能描述过程的状态，又满足无后效性，同时确 定允许状态集合 X k 。
（iii ）选择决策变量 u k ，确定允许决策集合U k ( x k ) 。 （iv ）写出状态转移方程。 （v ）确定阶段指标 v k ( x k ,u k ) 及指标函数V kn 的形式（阶段指标之和，阶段指标之 积，阶段指标之极大或极小等）。
（vi ）写出基本方程即最优值函数满足的递归方程，以及端点条件。 §3 逆序解法的计算框图
-59-
以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它 情况容易在这个基础上修改得到。
一般化的自由终端条件为
f n +1 (x n +1, i ) = ?(x n +1, i ), i = 1,2,L , n n +1 (3) 其中? 为已知。固定始端条件可表示为 X = {x } = {x *
}。
1 1 1 如果状态 x k 和决策 u k 是连续变量，用数值方法求解时需按照精度要求进行离散
化。设状态 x k 的允许集合为
X k = {x ki | i = 1,2,L , n k }, i = 1,2,L , n k , k = 1,2,L , n . 决策 u ki ( x ki ) 的允许集合为
= {u | j = 1,2,L , n ki }, i = 1,2,L , n k , k = 1,2,L , n . ( j )
( j ) U ki ki
状态转移方程和阶段指标应对 x 的每个取值 x 和 u 的每个取值
u 计算，即 k ki ki ki ( j ) ) ( j ) T k = T k ( , ，v k = v ( x ,
u ) 。最优值函数应对 x k 的每个取值 x ki 计算。基本方 x ki u ki 程可以表为
ki ki f ( j ) ( x ) = v ( x , u ( j ) ) + f (T ( x , u ( j )
)), k ki k ki ki k +1 k ki ki f ( x ) = opt f ( j ) ( x ),
（4）
k ki k ki j
j = 1,2,L , n ki , i = 1,2,L , n k , k = n ,L ,2,1.
图 2 解法框图
-60-
按照（3），（4）逆向计算出f ( x* ) ，为全过程的最优值。记状态x 的最优决策为
1 1 ki
u* ( x) ，由x* 和u* ( x) 按照状态转移方程计算出最优状态，记作x* 。并得到相应的ki ki 1 ki ki k
* * * * * * * *
最优决策，记作u ( x ) 。于是最优策略为{u ( x), u ( x),L, u( x)} 。
k k 1 1 2 2 n n
算法程序的框图如图2 所示。
图的左边部分是函数序列的递推计算，可输出全过程最优值f ( x* ) ，如果需要还
1 1
*
可以输出后部子过程最优值函数序列f ( x) 和最优决策序列u ( x ) 。计算过程中存
k ki
f k ( x
ki
) 是备计算f
k -1
之用，在f k -1 算完后可用
k ki
*
f
k -1
将
k
f 替换掉；存u ( x) 是备右边
k ki
部分读u* ( x* ) 之用。
k k
图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略* * * * * * * * *
{u ( x), u ( x),L, u( x)} 和最优轨线{x , x ,L, x }。
1 1
2 2 n n 1 2 n
§4 动态规划与静态规划的关系
动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。
动态规划可以看作求决策u1 , u2 ,L, u n 使指标函数V1n ( x1 ,u1，u2 ,L,u n ) 达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。
一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明。
例4 用动态规划解下列非线性规划
n
max ∑g k (u k ) ；
k =1
n
∑u k=a, u k ≥ 0 .
s.t.
k =1
其中g k (u k ) 为任意的已知函数。
解按变量u k 的序号划分阶段，看作n段决策过程。设状态为x1 , x2 ,L, x n+1 ，取问题中的变量u1 , u2 ,L, u n 为决策。状态转移方程为
x 1 =a, x
k +1
=x
k
-u
k
, k = 1,2,L, n.
取g k (u k ) 为阶段指标，最优值函数的基本方程为（注意到x n +1 = 0 ）
f k (x
k
)=max[g
k
(x
k
)+f
k +1
(x
k +1
)]；
0≤u k ≤x k
0 ≤x
k
≤a, k =n, n -1,L,2,1；
f
n +1
(0) = 0 .
*
按照逆序解法求出对应于x 每个取值的最优决策u ( x) ，计算至f1 (a)后即可利
k k k
用状态转移方程得到最优状态序列{x*} 和最优决策序列{u* ( x* )}。
k
与静态规划相比，动态规划的优越性在于：
k k
（i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为
-61-
一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。
（ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。
（iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。
动态规划的主要缺点是：
（i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。
（ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m 个取值，那么对于n维问题，状态x k 就有m 个值，对于每个状态值都要计算、存储函数f k ( x k ) ，对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。
n
§5 若干典型问题的动态规划模型
5.1 最短路线问题
对于例1 一类最短路线问题（shortest Path Problem），阶段按过程的演变划分，状态由各段的初始位置确定，决策为从各个状态出发的走向，即有x k +1 =u k ( x k ) ，阶段指标为相邻两段状态间的距离d k ( x k , u k ( x k )) ，指标函数为阶段指标之和，最优值函数
f k ( x
k
) 是由x
k
出发到终点的最短距离（或最小费用），基本方程为
f
k
(x
k
)=min[d
k
(x
k
,u
k
(x
k
))+f
k +1
(x
k +1
)],k=n,L,1;
u k ( x k )
f
n +1
( x
n +1
) = 0.
利用这个模型可以算出例l 的最短路线为AB1C2 D1 E2 F2G，相应的最短距离为18。
5.2 生产计划问题
对于例2 一类生产计划问题（Production planning problem），阶段按计划时间自然
划分，状态定义为每阶段开始时的储存量x k ，决策为每个阶段的产量u k ，记每个阶段的需求量（已知量）为d k ，则状态转移方程为
x
k +1 =x
k+u k -d k , x k ≥ 0, k= 1,2,L, n. (5)
设每阶段开工的固定成本费为a，生产单位数量产品的成本费为b，每阶段单位数量产品的储存费为c，阶段指标为阶段的生产成本和储存费之和，即
?a +bu, u > 0
k k
v ( x, u) =cx +? (6)
k k k k
?0
-62-
指标函数V kn 为 v k 之和。最优值函数 f k ( x k ) 为从第 k 段的状态 x k 出发到过程终结的最
f k ( x k ) = min[v k ( x k , u k ) + f k +1 ( x k +1 )], k = n ,L ,1.
u k ∈U k
其中允许决策集合U k 由每阶段的最大生产能力决定。若设过程终结时允许存储量为 x ，则终端条件是
n +1 f ( x 0
) = 0.
（7）
n +1 n +1 （5）~（7）构成该问题的动态规划模型。
5.3 资源分配问题
一种或几种资源（包括资金）分配给若干用户，或投资于几家企业，以获得最大的 效益。资源分配问题（resource allocating Problem ）可以是多阶段决策过程，也可以是 静态规划问题，都能构造动态规划模型求解。下面举例说明。
例 5 机器可以在高、低两种负荷下生产。u 台机器在高负荷下的年产量是 g (u ) ， 在低负荷下 的年产量是 h (u ) ，高、低负 荷下机器的 年损耗率分 别是 a 1 和 b 1 （ 0 < b 1 < a 1 < 1 ）。现有 m 台机器，要安排一个 n 年的负荷分配计划，即每年初决定 多少台机器投入高、低负荷运行，使 n 年的总产量最大。如果进一步假设 g (u ) = αu ， h (u ) = βu （α > β > 0 ），即高、低负荷下每台机器的年产量分别为α 和 β ，结果将 有什么特点。
解 年度为阶段变量 k = 1,2,L , n 。状态 x k 为第 k 年初完好的机器数，决策 u k 为 第 k 年投入高负荷运行的台数。当 x k 或 u k 不是整数时，将小数部分理解为一年中正常 工作时间或投入高负荷运行时间的比例。
机器在高、低负荷下的年完好率分别记为 a 和 b ，则 a = 1 - a 1 ， b = 1 - b 1 ，有
a <
b 。因为第 k 年投入低负荷运行的机器台数为 x k - u k ，所以状态转移方程是 x k +1 = au k + b ( x k - u k ) （8） 阶段指标 v k 是第 k 年的产量，有
v k ( x k , u k ) = g (u k ) + h ( x k - u k )
指标函数是阶段指标之和，最优值函数 f k ( x k ) 满足
（9）
f k ( x k ) = max [v k ( x k , u k ) + f k +1 ( x k +1 )],
0≤u k ≤ x k
0 ≤ x k ≤ m , k = n ,L ,2,1.
(10)
及自由终端条件
f n +1 ( x n +1 ) = 0, 0 ≤ x n +1 ≤ m .
（11）
当 v k 中的 g , h 用较简单的函数表达式给出时，对于每个 k 可以用解析方法求解极 值问题。特别，若 g (u ) = αu ，h (u ) = βu ，（10）中的 [v k ( x k , u k ) + f k +1 ( x k )] 将是 u k 的线性函数，最大值点必在区间 0 ≤ u k ≤ x k 的左端点 u k = 0 或右端点 u k = x k 取得， 即每年初将完好的机器全部投入低负荷或高负荷运行。
§6 具体的应用实例
例 6 设某工厂有 1000 台机器，生产两种产品 A 、B ，若投入 x 台机器生产 A 产
-63-
品，则纯收入为 5x ，若投入 y 台机器生产 B 种产品，则纯收入为 4 y ，又知：生产 A 种 产品机器的年折损率为 20%，生产 B 产品机器的年折损率为 10%，问在 5 年内如何安 排各年度的生产计划，才能使总收入最高？
解 年度为阶段变量 k = 1,2,3,4,5 。 令 x k 表示第 k 年初完好机器数， u k 表示第 k 年安排生产 A 种产品的机器数，则
x k - u k 为第 k 年安排生产 B 种产品的机器数，且 0 ≤ u k ≤ x k 。 则第 k + 1年初完好的机器数
x k +1 = (1 - 0.2)u k + (1 - 0.1)(x k - u k ) = 0.9x k - 0.1u k
（12）
令 v k (x k , u k ) 表示第 k 年的纯收入， f k (x k ) 表示第 k 年初往后各年的最大利润之 和。
显然
f 6 (x 6 ) = 0
则
（13） f k (x k ) = max {v k (x k , u k ) + f k +1 (x k +1 )}
0≤u k ≤ x k
= max {5u k + 4(x k - u k ) + f k +1 (x k +1 )} = max {u k + 4x k + f k +1 (x k +1 )} （14）
0≤u k ≤ x k
（1） k = 5 时，由（13）、（14）式得
0≤u k ≤ x k
f 5 (x 5 ) = max {u 5 + 4x 5 }
0≤u 5 ≤ x 5
u 5 + 4x 5 关于 u 5 求导，知其导数大于零，所以 u 5 + 4x 5 在 u 5 等于 x 5 处取得最大值， 即 u 5 = x 5 时， f 5 (x 5 ) = 5x 5 。
（2） k = 4 时，由（12）、（14）式得
f 4 (x 4 ) = max {u 4 + 4x 4 + 5x 5 }
0≤u 4 ≤ x 4
= max {u 4 + 4x 4 + 5(0.9x 4 - 0.1u 4 )} = max {0.5u 4 + 8.5x 4 }
0≤u 4 ≤ x 4
当 u 4 = x 4 时， f 4 (x 4 ) = 9x 4 （3） k = 3 时，
0≤u 4 ≤ x 4
f 3 (x 3 ) = max {u 3 + 4x 3 + 9x 4 }
0≤u 3 ≤ x 3
= max {u 3 + 4x 3 + 9(0.9x 3 - 0.1u 3 )} = max {0.1u 3 + 12.1x 3 }
0≤u 3 ≤ x 3
当 u 3 = x 3 时， f 3 (x 3 ) = 12.2x 3 （4） k = 2 时，
0≤u 3 ≤ x 3
f 2 (x 2 ) = max {u 2 + 4x 2 + 12.2x 3 } = max {-0.22u 2 + 14.98x 2 }
0≤u 2 ≤ x 2
当 u 2 = 0 时， f 2 (x 2 ) = 14.98x 2 。 （5） k = 1 时，
0≤u 2 ≤ x 2
f 1 (x 1 ) = max{u 1 + 4x 1 + 14.98x 2 } = max{-0.498u 1 + 17.482x 1}
0≤u 1 ≤ x 1
0≤u 1 ≤ x 1
当 u 1 = 0 时， f 1 (x 1 ) = 17.482x 1 。因为
x 1 = 1000 （台）
-64-
所以由（12）式，进行回代得
x 2 = 0.9x 1 - 0.1u 1 = 900 （台） x 3 = 0.9x 2 - 0.1u 2 = 810 （台） x 4 = 0.9x 3 - 0.1u 3 = 648 （台） x 5 = 0.9x 4 - 0.1u 4 = 518.4 （台）
注： x 5 = 518.4 台中的 0.4 台应理解为有一台机器只能使用 0.4 年将报废。 例 7 求解下面问题
2
max z = u u u 1 2 3
?u 1 + u 2 + u 3 = c (c > 0)
?
?u i ≥ 0 i = 1,2,3
解： 按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量 为 x 1 , x 2 , x 3 , x 4 ，并记 x 1 = c ；取问题中的变量 u 1 , u 2 , u 3 为决策变量；各阶段指标函数 按乘积方式结合。令最优值函数 f k (x k ) 表示第 k 阶段的初始状态为 x k ，从 k 阶段到 3 阶段所得到的最大值。
设 x 3 = u 3 ， x 3 + u 2 = x 2 ， x 2 + u 1 = x 1 = c 则有
u 3 = x 3 ， 0 ≤ u 2 ≤ x 2 ， 0 ≤ u 1 ≤ x 1
用逆推解法，从后向前依次有
*
f 3 (x 3 ) = max{u 3 } = x 3 及最优解 u = x 3
3 u 3 = x 3 2
2
f 2 (x 2 ) = max {u f (x )} = max {u (x - u 2 )} = max
h 2 (u 2 , x 2 ) 2 3 3 2 2 0≤u 2 ≤ x 2 0≤u 2 ≤ x 2 0≤u 2 ≤ x 2
dh 由 2
du 2
2 x
3 = 2u x - 3u 2 = 0 ，得 u = 和 u
= 0 （舍去） 2 2 2 2 2 2 d 2
h
2 2
= 2x 2 - 6u 2 = -2x 2 < 0 ，故 u 2 = x 2 为极大值点。 3
又 du 2
= 2 x 2 2
2
3
) = 4 x 3 2 x
u *
所以 f (x 及最优解 = 。 2 2
2 2 2 27
3
4 (x - u )3
} f (x ) = max{u f (x )} = max{u 1 1 1 2 2 1 27 1 1 0≤u ≤ x 0≤u ≤ x 1 1 1 1
同样利用微分法易知 f (x ) = 1 x 4 ，最优解 u * = 1 x 。 1 1 1 1 1 64 4
由于 x 1 已知，因而按计算的顺序反推算，可得各阶段的最优决策和最优值。即
= 1 c ， f (x ) = 1 c 4 64
u * 1 1 1 4 由
x = x - u *
= c - 1 c = 3 c
2 1 1
4 4 -65-
所以
2 x
3 = 1 c ， f (x ) = 1 c 3 16
u *
= 2 2 2
2 2 由
x = x - u * = 3 c - 1 c = 1 c 3 2 2
4 2 4
所以
= 1 c ， f (x ) = 1 c u *
3 3 3
4 4
因此得到最优解为： u * = 1 c ， u * = 1 c ， u * = 1 c ；
1 2 3 4 2 4
最大值为： max z = f (c ) = 1 c 4
。 1
64
习 题 四
1. 用 Matlab 编程求例 6 的解。
2. 有四个工人，要指派他们分别完成 4 项工作，每人做各项工作所消耗的时间如 表 1 所示。
表 1
问指派哪个人去完成哪项工作，可使总的消耗时间为最小？试对此问题用动态规划 方法求解。
3. 为保证某一设备的正常运转，需备有三种不同的零件 E 1 , E 2 , E 3 。若增加备用零 件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为 8000 元。已 知备用零件数与它的可靠性和费用的关系如表 2 所示。
表 2
现要求在既不超出投资额的限制，又能尽量提高设备运转的可靠性的条件下，问 各种零件的备件数量应是多少为好？
4. 某工厂购进 100 台机器，准备生产 I 、II 两种产品，若生产产品 I ，每台机器每 年可收入 45 万元，损坏率为 65％；若生产产品 II ，每台机器每年收入为 35 万元，损 坏率为 35％，估计三年后将有新型机器出现，旧的机器将全部淘汰。试问每年应如何
-66-
备件数
增加的可靠性 设备的费用（千元）
E 1
E 2
E 3
E 1
E 2
E 3
1 2 3
0.3
0.4 0.5
0.2 0.5 0.9
0.1 0.2 0.7
1 2 3
3 5 6
2 3 4
工作 工人
A
B
C
D
甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁
19
21
23
17
安排生产，使在三年内收入最多？
5．3 名商人各带 1 名随从乘船渡河，一只小船只能容纳 2 人，由他们自己划行。 随从们密约，在河的任一岸，一旦随从人数比商人多，就杀商人。此密约被商人知道， 如何乘船渡河的大权掌握在商人们手中，商人们怎样安排每次乘船方案，才能安全渡河 呢？
6．某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间（单位：天）如 表 3 所示，试求最优的加工顺序和总加工天数。
表 3
-67-
任务 车间
1
2
3
4
5
6 印刷车间 装订车间
3 8
10 12
5 9
2 6
9 5
11 2
第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G距离最短（或费用最省）的路线。 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随
第四章 数学规划模型 【教学目的】：深刻理解线性规划，非线性规划，动态规划方法建模的基本特点，并能熟练建立一些实际问题的数学规划模型；熟练掌握用数学软件（Matlab ，Lindo ，Lingo 等）求解优化问题的方法。 【教学重点难点】： 教学重点：线性规划和非线性规划的基本概念和算法，解决数学规划问题的一般思路和 方法，线性规划模型、整数规划模型、非线性规划模型的构建及其Matlab 与Lingo 实现。 教学难点：区分线性规划模型和非线性模型适用的实际问题，以及何时采用线性模型， 何时采用非线性模型，线性模型与非线性模型的转化。 【课时安排】：10学时 【教学方法】：采用多媒体教学手段，配合实例教学法，通过对典型例题的讲解启发学生思维，并给与学生适当的课后思考讨论的时间，加深知识掌握的程度。安排一定课时的上机操作。 【教学内容】： 在众多实际问题中，常常要求决策（确定）一些可控制量的值，使得相关的量（目标）达到最佳（最大或最小）。这些问题就叫优化问题，通常需要建立规划模型进行求解。称这些可控制量为决策变量，相关的目标量为目标函数；一般情况下，决策变量x 的取值是受限制的，不妨记为x ∈Ω，Ω称为可行域，优化问题的数学模型可表示为 Max(或Min)f(x), x ∈Ω 一般情况下，x 是一个多元变量，f(x)为多元函数，可行域比较复杂，一般可用一组不等式组来表示，这样规划问题的一般形式为 () x Min f x . ()0,1,2,,i st g x i m ≤= 虽然，该问题属于多元函数极值问题，但变量个数和约束条件比较多，一般不能用微分法进行解决，而通过规划方法来求解；这里讨论的不是规划问题的具体算法，主要是讨论如何将一个实际问题建立优化模型，并利用优化软件包进行求解。 根据目标函数和约束函数是否为线性，将规划模型分为线性规划和非线性规划。 4.1线性规划 线性规划(LP)研究的实际问题多种多样的，它在工农业生产、经济管理、优化设计与控
-56- 第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪50 年代初R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是 一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 图1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G 距离最短（或费用最省）的路线。 图1 最短路线问题 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3 （千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time -57- decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随 机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。§2 基本概念、基本方程和计算方法 2.1 动态规划的基本概念和基本方程 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 2.1.1 阶段
动态规划的原理及应用 动态规划是运筹学的一个分支，是求解多阶段决策过程的最优化数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类问题的新方法——动态规划。 动态规划主要用于以时间划分阶段的动态过程优化问题，但一些与时间无关的静态规划如线性规划或非线性规划，人为引进时间因素后，把它们看成多阶段过程，也可用动态规划求解。 1．动态规划的基本理论 一．动态规划的术语 在研究现实的系统时，我们必须将系统具体的术语抽象为数学统一的术语。在此先简要介绍动态规划中的常用术语。 级：我们把系统顺序地向前发展划分为若干个阶段，称这些阶段为“级”。在离散动态规划中，“级”顺序的用自然整数编号，即1，2，…，n. 状态（λ）：用来描述、刻画级的特征。状态可以是单变量，也可以时向量。在此，我们假设研究的状态具有“无记忆性”，即当前与未来的收益仅决定于当前的状态，并不依赖于过去的状态和决策的历史。 状态空间（Λ）：由全部系统可能存在的状态变量所组成。
决策：在每一级，当状态给定后，往往可以做出不同的决定，从而确定下一级的状态，这种决定称为决策。描述决策的变量称为决策变量。对每个状态λ∈Λ，有一非空集X(λ)称为λ的决策集。决策变量x(λ)∈X（λ）。 变换：若过程在状态λ，选择决策x(λ)，可确定一个状态集T（λ，x(λ)）,过程将从λ移动到其中某个状态.T(λ,x(λ))称为变换函数，它确定过程从一个状态到另一个状态的演变。T（λ,x(λ)）可分为两种类型，即确定型和不确定型。确定型的T（λ,x(λ)）只含有一个元。不确定型指我们不能确切知道决策的结果，但作为某已知概率分布支配的变换结果，在每级状态和决策是确定的。这时，集函数T（λ,x(λ)）将包含多个元素。当T（λ,x(λ)）=0 时，过程终止。 策略：顺序排列的决策集，记为v。所有可能的策略集构成策略空间Γ。 收益：评价给定策略的目标函数r(λ，v)，它依赖于状态和策略。总收益是集收益s(λ,v)的某个组合（通常为集收益之和）。若T（λ,x(λ)）=0，则r(λ1，v1)= s(λ1,v1)；若T（λ,x(λ)）= λ2，则r(λ1，v)= s(λ1,v1)+ r(λ1，v2)。 二．序贯决策过程 动态规划的寻优过程可以有正序、逆序两种方式。当初始状态给定时，用逆序方式比较好，当终止状态给定时，用正序方式较好。 采用分级的序贯决策方法，把一个含有n个变量的问题转化为求解n个单变量问题。为了应用最优化原理，必须满足分级条件，即目标函数可分性和状态可分性。 目标函数可分性：
线性规划 1.简介： 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源. 线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.规划问题。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。 (x)都是线性函数，则该模型称为在优化模型中，如果目标函数f(x)和约束条件中的g i 线性规划。 2.线性规划的3个基本要素 （1）决策变量 （2）目标函数f(x) (x)≤0称为约束条件） （3）约束条件（g i 3.建立线性规划的模型 （1）找出待定的未知变量（决策变量），并用袋鼠符号表示他们。 （2）找出问题中所有的限制或者约束，写出未知变量的线性方程或线性不等式。
（3）找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值。以下题为例，来了解一下如何将线性规划用与实际的解题与生活中。 生产计划问题 某工厂生产甲乙两种产品，每单位产品消耗和获得的利润如表 试拟订生产计划，使该厂获得利润最大 解答：根据解题的三个基本步骤 （1）找出未知变量，用符号表示： 设甲乙两种产品的生产量分别为x 1与x 2 吨，利润为z万元。 （2）确定约束条件： 在这道题目当中约束条件都分别为：钢材，电力，工作日以及生产量不能为负的限制 钢材：9x 1+5 x 2 ≤360， 电力：4x 1+5 x 2 ≤200， 工作日：3x 1+10 x 2 ≤300， x 1≥0 ，x 2 ≥0， （3）确定目标函数： Z=7x 1+12 x 2
-1- 第一章线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947 年G. B. Dantzig 提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性 规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000 元与3000 元。 生产甲机床需用A、B机器加工，加工时间分别为每台2 小时和1 小时；生产乙机床 需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时 数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1 x 台甲机床和2 x 乙机床时总利润最大，则1 2 x , x 应满足 （目标函数）1 2 max z = 4x + 3x (1) s.t.（约束条件） ?? ? ?? ? ? ≥ ≤ + ≤ + ≤ , 0 7 8 2 10 1 2 2 1 2 1 2 x x x x x x x （2） 这里变量1 2 x , x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性
数学建模8-动态规划和目标规划 一、动态规划 1.动态规划是求解决策过程最优化的数学方法，主要用于求解以时间划分阶段的动态过程的 优化问题。但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2.基本概念、基本方程： （1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移方程： （6）指标函数和最优值函数： （7）最优策略和最优轨线 （8）递归方程： 3．计算方法和逆序解法（此处较为抽象，理解较为困难，建议结合例子去看）
4．动态规划与静态规划的关系：一些静态规划只需要引入阶段变量、状态、决策等就可以用动态规划方法求解（详见书中例4） 5．若干典型问题的动态规划模型： （1）最短路线问题： （2）生产计划问题:状态定义为每阶段开始时的储存量x k，决策为每个阶段的产量，记每个阶段的需求量（已知量）为d k，则状态转移方程为 （3）资源分配问题：详见例5
状态转移方程： 最优值函数： 自有终端条件： （4）具体应用实例：详见例6、例7。 二、目标规划 1．实际问题中，衡量方案优劣要考虑多个目标，有主要的，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，这时可用目标规划解决。其求解思路有加权系数法、优先等级法、有效解法等。 2．基本概念： （1）正负偏差变量： （2）绝对（刚性）约束和目标约束 ，次位赋（3）优先因子（优先等级）与权系数：凡要求第一位达到的目标赋予优先因子P 1……以此类推。 予P 2 （4）目标规划的目标函数： （5）一般数学模型：
工厂资源规划问题 冉光明 29 信息与计算科学 指导老师：赵姣珍
目录 摘要 (1) 关键词 (1) 问题的提出 (2) 问题重述与分析 (3) 符号说明 (4) 模型假设 (4) 模型建立与求解 (5) 模型检验 (9) 模型推广 (10) 参考文献 (11) 附录 (12)
摘要：本问题是个优化问题。问题首先选择合适的决策变量即各种产品数，然后通过决策变量来表达约束条件和目标函数，再利用或编写程序，求得最优产品品种计划；最后通过优化模型对问题作以解释，得出当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时，得到的是最优品种规划。 问题一回答：当技术服务消耗33小时、劳动力消耗67小时、不消耗行政管理时， 产品不值得生产。用运算分析，当产品的利润增加至25 3 时，若使产品品种计划最优， 此时需要消耗技术服务29h，劳动力消耗46h，行政管理消耗25h。 问题二回答：利用得到当技术服务增加1h时，利润增加2.5元;劳动力增加1h，利润增加1元；行政管理的增减不会影响利润。 问题三回答：增加的决策变量，调整目标函数。当技术服务消耗33h，劳动力消耗17h，不消耗行政管理，新增量50h时，管理部门采取这样的决策得到最优的产品品种规划。 问题四回答：增加新的约束条件，此时当技术服务消耗32h，劳动力消耗58h，行政管理消耗10h时，得到最优产品品种规划。 本文对模型的求解给出在线性约束条件下的获利最多的产品品种规划。 关键词：线性规划；优化模型；最优品种规划
问题的提出 某工厂制造三种产品，生产这三种产品需要三种资源：技术服务、劳动力和行政管理。下表列出了三种单位产品对每种资源的需要量： 现有100h的技术服务、600h劳动力和300h的行政管理时间可使用，求最优产品品种规划。且回答下列问题： ⑴若产品值得生产的话，它的利润是多少？假使将产品的利润增加至25/3元，求获利最多的产品品种规划。 ⑵确定全部资源的影子价格。 ⑶制造部门提出建议，要生产一种新产品，该种产品需要技术服务1h、劳动力4h 和行政管理4h。销售部门预测这种产品售出时有8元的单位利润。管理部门应有怎样的决策？ ⑷假定该工厂至少生产10件产品，试确定最优产品品种规划。
数学建模常用的十种解题方法 摘要 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言，把它表述为数学式子，也就是数学模型，然后用通过计算得到的模型结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。数学建模的十种常用方法有蒙特卡罗算法；数据拟合、参数估计、插值等数据处理算法；解决线性规划、整数规划、多元规划、二次规划等规划类问题的数学规划算法；图论算法；动态规划、回溯搜索、分治算法、分支定界等计算机算法；最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法；网格算法和穷举法；一些连续离散化方法；数值分析算法；图象处理算法。 关键词：数学建模；蒙特卡罗算法；数据处理算法；数学规划算法；图论算法 一、蒙特卡罗算法 蒙特卡罗算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。在工程、通讯、金融等技术问题中, 实验数据很难获取, 或实验数据的获取需耗费很多的人力、物力, 对此, 用计算机随机模拟就是最简单、经济、实用的方法; 此外, 对一些复杂的计算问题, 如非线性议程组求解、最优化、积分微分方程及一些偏微分方程的解⑿, 蒙特卡罗方法也是非常有效的。 一般情况下, 蒙特卜罗算法在二重积分中用均匀随机数计算积分比较简单, 但精度不太理想。通过方差分析, 论证了利用有利随机数, 可以使积分计算的精度达到最优。本文给出算例, 并用MA TA LA B 实现。 1蒙特卡罗计算重积分的最简算法-------均匀随机数法 二重积分的蒙特卡罗方法(均匀随机数) 实际计算中常常要遇到如()dxdy y x f D ??,的二重积分, 也常常发现许多时候被积函数的原函数很难求出, 或者原函数根本就不是初等函数, 对于这样的重积分, 可以设计一种蒙特卡罗的方法计算。 定理 1 )1( 设式()y x f ,区域 D 上的有界函数, 用均匀随机数计算()??D dxdy y x f ,的方法: (l) 取一个包含D 的矩形区域Ω,a ≦x ≦b, c ≦y ≦d , 其面积A =(b 一a) (d 一c) ; ()j i y x ,,i=1,…,n 在Ω上的均匀分布随机数列,不妨设()j i y x ,, j=1，…k 为落在D 中的k 个随机数, 则n 充分大时, 有
应用一图论算法 图论在计算机处理问题中占有重要地位，现实中的很多问题最终都可以转化成图论问题，或者要借助图结构来存储和处理。但是怎么把一图存入计算机就要涉及到数学建模的知识。 比如下面一图： 如果要求出从节点v1到节点v5的所有路径，就可以借助计算机来很轻松的解决。但前提条件是，必须要把图以一种计算机可以理解的形式存进去，即要把它抽象为数学问题。 在此，我们需要定义一些关于图的概念，以便更好的描述问题。 边与顶点的关系有如下几种典型情况： 简单图：无自回环，无重边的图。
无向图：边没有指向， 1212 e. i i i i i ψ（）={v,v}=v v此时称边e i与顶点12 i i v,v关联，称 顶点 1 i v与顶点 2 i v邻接。 有向图:边有指向， 1212 e. i i i i i ψ u u u u u r （）=（v,v）=v v 下面是具体涉及到图如何存储的问题： 1.图G(V,E)的关联矩阵x R=(r) ij n m ，若G(V,E)为无向图， 1 2 i j ij i j j i j j v e r v e e v e e ? ? =? ? ? 与不关联 与关联,为非自回环 与关联,为自回环 若G(V,E)为有向图， 1 2 i j ij i j i j v e r v e v e ? ? =? ? ? 与不关联 是的起点 是的终点 因此该图可以用关联矩阵表示出来，如下所示 1100000 1010100 0101001 0011010 0000111 R ?? ? ? ? = ? ? ? ?? 这样，我们就可以以矩阵的形式将图存入计算机
1．某公司打算向它的三个营业区增设6个销售店，每个营业区至少增设1个。各营业区每年增加的利润与增设的销售店个数有关，具体关系如表1所示。试规划各营业区应增设销售店的个数，以使公司总利润增加额最大。 ： 个销售店，C 区增设1个销售店.最大利润为490万元。 贝尔曼（Bellman ）最优化原理：在最优策略的任意一阶段上，无论过去的状态和决策如何，对过去决策所形成的当前状态而言，余下的诸决策必须构成最优子策略。 2.某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表所示。试确定500万元资 解：将问题按工厂分为三个阶段3,2,1=k ，设状态变量k （3,2,1=k ）代表从第k 个工厂到第3个工厂的投资额，决策变量k x 代表第k 个工厂的投资额。于是有状态转移率k k k x S S -=+1、允许决策集合}0|{)(k k k k k S x x S D ≤≤=和递推关系式： )}()({max )(10k k k k k S x k k x S f x g S f k k -+=+≤≤ )1,2,3(=k
0)(44=S f 当3=k 时： )}({max }0)({max )(330330333333x g x g S f S x S x ≤≤≤≤=+= 于是有表2-1，表中*3x 表示第三个阶段的最优决策。 当2=k 时： )}()({max )(2232202222x S f x g S f S x -+=≤≤ 于是有表7-3。 当1=k 时： )}()({max )(1121101111x S f x g S f S x -+=≤≤ 于是有表2-3。 然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）甲工厂投资200万元，乙工厂投资200万元，丙工厂投资100万元；（2）甲工厂没有投资，乙工厂投资200万元，丙工厂投资300万元。按最优分配方案分配投资（资源），年利润将增长210万元。
精心整理 第四章决策 一、单项选择题 1、有一种说法认为"管理就是决策"，这实际上意味着：（C ） A.对于管理者来说只要善于决策就一定能够获得成功 B.管理的复杂性和挑战性都是由于决策的复杂性而导致的 C.决策能力对于管理的成功具有特别重要的作用 D.管理首先需要的就是面对复杂的环境作出决策 2 A.3、根据"A.B.C.D.4(1)5 A.B.C.D.620A.B.C.D.这不是真正意义上的授权而只是一种工作落实 7、某企业原先重大战略决策的基本过程是由各部门(如财务部、销售部、生产部、人事部等)独立把各自部门的情况写成报告送给总经理，再由总经理综合完成有关的战略方案。后来，对此过程作了些调整，这就是：总经理收到各部门呈上的报告后，有选择地找些管理人员来磋商，最后由自己形成决策。再后来，总经理在收到报告后，就把这些报告交给一个有各部门人员共同参与组成的委员会，通过委员会全体成员的面对面讨论，最终形成有关决策。对此你的看法是：（Ｃ） A.这种处理方式的改变对企业战略决策以及其它方面的工作没什么影响 B.这种处理方式的改变可以大大提高企业决策的效率 C.这种处理方式的改变增加了信息沟通的范围，可带来更多的成员满意感 D.这种处理方式的改变提高了企业上下信息沟通的效率 8、现在社会上销售彩票的很多。一家三口在抽奖时，常常喜欢让孩子来抽，请问这是遵循了什么决策原则?（A ）
A.乐观原则 B.悲观原则 C.折衷原则 D.最小最大后悔值原则 9、某企业集团拟投资开发新产品，现有两个方案，假定其开发费用相同。开发甲产品，估计投产后，市场竞争不激烈时每年可获利150万元，市场竞争激烈时每年亏损50万元。开发乙产品，估计投产后无论市场竞争激烈与否，每年均可获利70万元。根据预测，这两种拟开发的产品投产后，出现市场竞争不激烈情况的概率为0.6，出现市场竞争激烈情况的概率为0.4。如果只能在这两个方案中选一个，你的评价是什么?（B） A.开发甲产品比开发乙产品好。 B.开发乙产品比开发甲产品好。 C.开发甲产品与开发乙产品没什么差别。 D.根据以上资料尚无法下结论。 10、在以下X、Y和Z三种方案中，哪一个方案最好？（B） A.X 11 A. B. C. D. 12 A. 13、 A. 13 A. C. 14 A.关于公司各部门办公电脑的分配方案 D.对一位客户投诉的例行处理 C.对一家主要竞争对手突然大幅削价作出反应 D.对一位公司内部违纪职工按规章进行处理 15、在制定计划时，为了有效地确定前提条件，应当：（A） A.找出并着重研究那些关键性的、战略性的的提条件， B.要准备不止一套的备选前提条件，以供出现偶发事件时应急使用。 C.所选择的各前提条件相互间必须协调一致。 D.对以上3条作综合考虑。 16、有一个大家熟悉的商务趣闻：甲乙两家鞋业公司的经理各派了一位市场调查员去某岛调查，发现岛上的居民从来不穿鞋。结果甲公司的调查员向公司报告称自己发现厂一个新市场，进而开拓了市场；而乙公司的调查员则
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的
1 预测模块：灰色预测、时间序列预测、神经网络预测、曲线拟合（线性回归）； 2 归类判别：欧氏距离判别、fisher判别等； 3 图论：最短路径求法； 4 最优化：列方程组用lindo 或lingo软件解； 5 其他方法：层次分析法马尔可夫链主成分析法等； 6 用到软件：matlab lindo （lingo）excel ； 7 比赛前写几篇数模论文。 这是每年参赛的赛提以及获奖作品的解法，你自己估量着吧…… 赛题解法 93A非线性交调的频率设计拟合、规划 93B足球队排名图论、层次分析、整数规划 94A逢山开路图论、插值、动态规划 94B锁具装箱问题图论、组合数学 95A飞行管理问题非线性规划、线性规划 95B天车与冶炼炉的作业调度动态规划、排队论、图论 96A最优捕鱼策略微分方程、优化 96B节水洗衣机非线性规划 97A零件的参数设计非线性规划 97B截断切割的最优排列随机模拟、图论 98A一类投资组合问题多目标优化、非线性规划 98B灾情巡视的最佳路线图论、组合优化 99A自动化车床管理随机优化、计算机模拟 99B钻井布局0-1规划、图论 00A DNA序列分类模式识别、Fisher判别、人工神经网络 00B钢管订购和运输组合优化、运输问题 01A血管三维重建曲线拟合、曲面重建 01B 工交车调度问题多目标规划 02A车灯线光源的优化非线性规划 02B彩票问题单目标决策 03A SARS的传播微分方程、差分方程 03B 露天矿生产的车辆安排整数规划、运输问题 04A奥运会临时超市网点设计统计分析、数据处理、优化 04B电力市场的输电阻塞管理数据拟合、优化 05A长江水质的评价和预测预测评价、数据处理 05B DVD在线租赁随机规划、整数规划
随机库存的分配 摘要 卖方管理库存（VMI，Vendor-Managed Inventory）是现代物流中一个比较新的管理思想，它是指货物的提供者根据所有客户的当前库存量决定在一定时间内对他们的货物分配量。基于VMI思想，设计出当供货方的供应能力有限、客户需求随机情况下的分配方案，能够应用到实际的物流管理信息系统中，具有实际意义。 针对此问题，在客户需求量服从同一指数分布的前提条件下，首先通过MATLAB软件编写程序，得到50个客户的随机需求量和初始库存量，然后从车辆配载能力出发，以客户的库存费用最小为目标函数，以供货总量和每辆车的承载能力为约束条件，建立非线性随机规划模型，通过lingo软件求解模型，得到所有客户库存费用最小时的分配方案，同时得到最小库存费用为699.5543。 关键词：随即需求库存分配随机规划
一、问题重述 考虑由一个供货方和n个客户组成的配送网络，配送活动的组织基于VMI 思想。假设供货方的供应能力有限(意味着某些客户可能得不到供应)，可供应的货物总量为A；拥有车辆数为K，车辆k的载重量为b k(k∈K)。每个客户的需求量是随机的，但需求的分布函数F i已知(假设F i是严格增函数，并假设不同客户的需求是相互独立的，且服从相同分布)，周期初的初始库存为βi，h+i为单位货物的保管费，h-i为单位货物的缺货损失费。令q i(w i)表示客户i在得到配送量w 时的库存费用函数。令y ik表示车辆k是否服务客户i，是取1，否取0。 i 当y ik(i=1，…，n；k=0，…，K)的取值确定后，也就意味着确定了对所有客户的一个划分，如令Y k表示车辆k服务的客户集合，其应满足Y k={i∶y ik=1}。 请写出库存分配问题的模型，并带入适当规模的数据进行计算，分析其计算结果，得出结论。 二、问题分析 本问题讨论的是当供货方的供应能力不足、客户需求随机情况下的库存分配问题。客户的需求量是随机的，但需求的分布函数F i已知(假设F i是严格增函数，并假设不同客户的需求是相互独立的，且服从相同分布)，在处理问题时，可以将需求量当作服从相同参数的同一指数分布，通过MATLAB软件来产生指数分布的随机数作为客户需求量，要使得所有客户的库存费用最小，需要构造与配送量、库存费、保管费等有关的目标函数，将有限的车辆数和每辆车的承载能力以及供货方的总供应量作为约束条件，建立模型，通过lingo软件求解得到具体的配送方案。 三、模型假设 1.假设客户的随即需求量服从参数为0.5的指数分布； 2.假设每个客户的初始库存量在0.1~1.5吨之间随即取值； 3.假设所有客户的库存保管费和缺货损失费相同； 4.假设供货方的总供应量为所有客户随即需求量之和的0.8倍； 5.假设不考虑运货车辆的运费。 四、符号说明
§6 动态规划模型举例 以上讨论的优化问题属于静态的，即不必考虑时间的变化，建立的模型——线性规划、非线性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以时间或空间为标志）根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。例如： （1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出为后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。 （2）发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标运动的情况，不断地决定导弹飞行的方向和速度，使之最快地命中目标。 （3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外，每次更新都要付出更新费用。因此，应当如何决定它每年的使用时间，使总的效益最佳。 动态规划模型是解决这类问题的有力工具，下面介绍相关的基本概念及其数学描述。 （1）阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为阶段变量，记为k 。 （2）状态 状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究过程的状况。各阶段的状态通常用状态变量描述。常用k x 表示第k 阶段的状态变量。n 个阶段的决策过程有1+n 个状态。用动态规划方法解决多阶段决策问题时，要求整个过程具有无后效性。即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。 （3）决策 某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。用)(k k x u 表示第k 阶段处于状态k x 时的决策变量，它是k x 的函数，用)(k k x D 表示k x 的允许决策集合。 （4）策略 一个由每个阶段的决策按顺序排列组成的集合称为策略。由第k 阶段的状态k x 开始到终止状态的后部子过程的策略记为)}(,),(),({)(11n n k k k k k k x u x u x u x p Λ++=。在实际问题中，可供选择的策略有一定范围，称为允许策略集合。其中达到最优效果的策略称为最优策略。 （5）状态转移方程 如果第k 个阶段状态变量为k x ，作出的决策为k u ，那么第1+k 阶段的状态变量1+k x 也被完全确定。用状态转移方程表示这种演变规律，写作(1k k T x =+k x ，)k u （6）最优值函数 指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数。 下面的方程在动态规划逆序求解中起着本质的作用。
一、单项选择题 2．被称为决策“硬技术”的决策方法是指（ A ） A．计量决策法 B．主观决策法 C．边际分析法 D．德尔菲法 3．个人管理与集体管理相比，据美国管理协会的调查结果显示，在制定决策方面（ C ） A．前者更有效 B．后者更有效C．两者同样有效D．两者都无效 4．管理的核心是（ A ） A．决策 B．领导 C．激励 D．处理好人际关系48．该项决策具有极大偶然性和随机性，又无先例可循且有大量不确定因素，其方法和步骤也难以程序化和标准化，这项决策就是（ D ）。 A．风险型决策 B．不确定型决策 C．程序化决策 D．非程序化决策 11．决策程序的首要环节是（ C ）。 A．确定决策原则 B．确定决策方法 C．确定决策目标 D．拟定可行方案 13．某企业在下年度有甲、乙、丙三种产品方案可供选择，每种方案都面临畅销、较好、一般和滞销四种状态，每种状态的概率和损益值如下表所示：
那么，用决策树法选出的最优方案是方案。（ A ） A．甲 B．乙 C．丙 D．甲和乙 14．一般情况下，根据决策的特征，决策选择的目标是一种目标。（ C ） A．限定 B．最佳 C．满意 D．最低15．在于充分利用组织已经形成的组织活动能力，其结果主要影响组织活动的效率，并由此决定了组织的生存能力。（ C ）A．战略计划 B．长期计划 C．短期计划D．战略决策 18．面对未能可能呈现的多种状态，决策者虽无法事先确定究竟呈现何种状态，但可判断各种状态出现的概率。（ B ） A．确定型决策法B．风险型决策法C．非确定型决策法D．追踪决策法 20．环境研究对组织决策有着非常重要的影响，具体表现在可以提高组织决策的（B ） A．有效性、及时性、稳定性 B．前瞻性、有效性、稳定性
第十三章线性规划与数学建模简介 【授课对象】理工类专业学生 【授课时数】6学时 【授课方法】课堂讲授与提问相结合 【基本要求】1、了解数学模型的基本概念、方法、步骤； 2、了解线性规划问题及其数学模型； 3、了解线性规划问题解的性质及图解法. 【本章重点】线性规划问题. 【本章难点】线性规划问题、线性规划问题解的性质、图解法. 【授课内容】 本章简要介绍数学建模的基本概念、方法、步骤，并以几个典型线性规划问题为例，介绍构建数学模型的方法及其解的性质。 §1 数学建模概述 一、数学建模 数学建模是构造刻划客观事物原型的数学模型并用以分析、研究和解决实际问题的一种科学方法。运用这种科学方法，必须从实际问题出发，遵循从实践到认识再实践的认识规律，围绕建模的目的，运用观察力、想象力的抽象概括能力，对实际问题进行抽象、简化，反复探索，逐步完善，直到构造出一个能够用于分析、研究和解决实际问题的数学模型。因此，数学建模是一种定量解决实际问题的创新过程。 二、数学模型的概念
模型是人们对所研究的客观事物有关属性的模拟。例如在力学中描述力、 量和加速度之间关系的牛顿第二定律F＝ma就是一个典型的（数学）模型。一般地，可以给数学模型下这样的定义：数学模型是磁于以部分现实世界为一定目的而做的抽象、简化的数学结构。 通俗而言，数学模型是为了一定目的对原型所作的一种抽象模拟，它用数学式子，数学符号以及程序、图表等描述客观事物的本质特征与内在联系。 三建立数学模型的方法和步骤 建立数学模型没有固定模式。下面介绍一下建立模型的大体过程： 1.建模准备 建模准备是确立建模课题的过程。这类课题是人们在生产和科研中为了使 认识和实践过一步发展必须解决的问题。因此，我们首先要发现这类需要解决的实际问题。其次要弄清所解决问题的目的要求并着手收集数据。进行建模筹划，组织必要的人力、物力等，确立建模课题。 2．模型假设 作为建模课题的实际问题都是错综复杂的、具体的。如果不对这些实际问题进行抽象简化，人们就无法准确把握它的本质属性，而模型假设就是根据建模的目的对原型进行抽象、简化，抓住反映问题本质属性的主要因素，简化掉那些非本质的次要因素。有了这些假设，就可以在相对简单的条件下，弄清各因素之间的关系，建立相应的模型。 合理的假设是建立理想模型的必要条件和基本保证。如果假设是合理的，则模型切合实际，能解决实际问题；如果假设不合理中或过于简化，则模型与实际情况不符或部分相符，就解决不了问题，就要修改假设，修改模型。 3．构造模型
四类基本模型 1 优化模型 1.1 数学规划模型 线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2 微分方程组模型 阻滞增长模型、SARS 传播模型。 1.3 图论与网络优化问题 最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。 1.4 概率模型 决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。 1.5 组合优化经典问题 ● 多维背包问题(MKP) 背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。如何将尽可能多的物品装入背包。 多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。如何选取物品装入背包，是背包中物品的总价值最大。 多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。该问题属于NP 难问题。 ● 二维指派问题(QAP) 工作指派问题：n 个工作可以由n 个工人分别完成。工人i 完成工作j 的时间为ij d 。如何安排使总工作时间最小。 二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。 二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。 ● 旅行商问题(TSP) 旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。 ● 车辆路径问题(VRP) 车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在