假定该厂生产每批产品的固定成本为3千克，，若不生产就为0；每单位产品成本为1千元；每个时期生产能力所允许的最大生产量不超过6各单位；每个时期末未能售出的产品，每单位需付存储费0.5千元。

[0, min(∑d m dj, ? k)] ,其中v1 = 0,v5 = 0 。

j k=

为求出该问题的最优值，利用上面的计算程序 dynprog.m。根据上面所述的阶段指标函数、状态转移函数和递推关系式，编写出下面3个M_函数，以备主程序调用。

还假定在第一个时期的初始库存量为0，第四个是期末

的库存量也为0。试问该厂应如何安排各个时期的生产与库存，才能在满足市场需要的条件下，使总成本最小。解：用动态规划方法求解，

按四个时期将该问题分为四个阶段；记Vk为状态变量，它表示第k阶段开始时的库存

量；

记Xk为决策变量，它表示第k阶段的生产量； 可得状态转移方程：Vk+1

=Vk

+Xk

-dk

,k=1,2,3,4 由

题意知，在第k时期内的生产成本为:

?0...................当 xk =0 ? c xk

k( ) =

?3+1*xk.......当 x??k

=1,2,...6?

??∞..................当 x?k >6 ?

在第 k时期末库存量为vk+1 时的存储费

为:h vk k( ) = 0.5*(v x dk + ?k k) 故第k时期

内的总成本为: c x h vk k( ) + k k

( ) 则阶

段指标函数为:

V v c x h vk k() = k k(

) + k k( )

最优值函数

f V

k k

( ) 表示从第k阶段初始库存量为

V

k时到第四阶段末库存量为

0时的最小总费用。则有递

推关系式:

??f vk k() = max(0,dk vk xkmin? )≤ ≤6(V vk k(

) +f

vk+1( k+1)) ?

??f v5 ( 5 ) = 0, x d v4 = ?44

其中

x

≥ max(0,d v?

k k k),这是因为一方面每阶段生

产的下限为0；另一方面由于要保证供应，故第k阶段末的库存量vk+1 必须非负，即v x dk + ?k

k

≥

0 ，所以 x d vk ≥ ?k

k。vk的取值范围为

6

% DecisFun.m function

u=DecisFun(k,x) d=[2 3 2 4];m=6; if k==4 u=d(k)-x; else u=max(0,d(k)-x):m; End

% SubObjFun.m

function f=SubObjFun(k,x,u) d=[2 3 2 4]; if u==0 f=0.5*(x+u-d(k)); else if u>6

f=10^6;

else f=3+u+0.5*(x+u-d(k)); end

End % TransFun.m function s=TransFun(k,x,u) d=[2 3 2 4]; s=x+u-d(k);

在matlab命令空间输入：

x1=0:4;s=nan*ones(5,1);s(1)=0; x=[s x1' x1' x1'];

[p_opt,fval]=dynprog(x,'DecisFun','SubObjF un','TransFun') 运行结果如下：

p_opt =1.0000 0 5.0000 9.5000 2.0000 3.0000 0 0 3.0000 0 6.0000 11.0000

4.0000 4.0000

0 0 fval = 20.5000

从上面的结果可知，每个时期的最优决策为： X1=5,x2=0,x3=6,x4=0。

其相应的最小总成本为20.5千元。

从上面的结果中还可以看出，各个时期初的库存量分别为：V1=0,v2=2,v3=0,v4=4

这里的结果与文[1]的结果完全符合，这说明该程序是可行的。

3.2 二维背包问题

有一个人带一个背包上山，其可携带物品重量的限

度为10公斤，背包体积限制为22立方米。假设有3种物品可供他选择装入背包。已知第i种物品每件重量为w(i)公斤，体积为v(i)立方米，携带该物品xi件产生的效益值为c(i)*xi。问此人该如何选择携带物品，才

能使产生的效益值最大。其中 w=[3 4 5];v=[8 6 4];c=[4 5 6]; 解：用动态规划方法求解，按物品的种类数将该问题分为3各个阶段；

si表示用于装入第i种物品到第3种物品的总重

量；

ti表示用于装入第i种物品到第3种物品的总体

积； ui表示装入第i种物品的件数；可得状态转移方程：

sk+1 = ?s ck u tk( )* k k, +1 = ?t ck uk

( )* k

允许决策集合为：

s tk , k

)}

Ds u( k k,) = {uk | 0 ≤ ≤ukmin(

w vk k

最优值函数 f s tk k k( ,

) 表示当总重量不超过

st

k公斤，总体积不超过

k立方米背包装入第

t种物品到

第3种物品产生的最大效益值。

可得基本方程：

??f s tk k k( ,) =u D s tk∈maxk k k( ,

)( ( )*ck u f s tk+ k+1( k+1, k+1)), ?

??f v t4 ( 4 , 4 ) = 0 k= 3,2,1

下面同样用计算程序dynprog1.m求解：在使用此程序先要建立下面3个M_函数：

% DecisFun1.m function

[u1,u2]=DecisFun1(k,x1,x2) w=[3 4 5];v=[8 6 4];

u1=0:1:min(x1/w(k),x2/v(k));u2=1; % 因为这里只有一个决策变量，故令u2恒为1，这样是程序的需要，

% 也可减少计算量，此时u2就没有任何意义，只是一个虚拟的量

% SubObjFun1.m function

f=SubObjFun1(k,x1,x2,u1,u2) c=[4 5 6];

f=-c(k)*u1; % 求最大值转化为求最小值 % TransFun1.m function

s=TransFun1(k,x1,x2,u1,u2) w=[3 4 5];v=[8 6 4];

s(1)=x1-u1*w(k);s(2)=x2-u1*v(k);

在matlab命令空间输入：

7a1=0:10;b1=0:22;s1=nan*ones(11,1);s1(1)=10; s2=nan*ones(23,1);s2(1)=22;

x1=[s1 a1' a1'];x2=[s2 b1' b1'];

[p_opt,fval]=dynprog1(x1,x2,'DecisFun1','S ubObjFun1','TransFun1') 运行结果如下： p_opt =

1 10 22 2 1 -8 2 4 6 1 1 -5 3 0 0 0

1

0 fval

= -13

从 上面 的结 果可 知： 最优 装入 方案 为： u1=2,u2=1,u3=0;也即各种物品分别装入2件，1件，0件，此时产生的最大效益值为13。

此程序得出的结果与事实相符合，说明此程序是可行的。

4 程序使用的几点说明

程序dynprog.m只能使用于具体问题中只有一个状态变量的情形，程序dynprog1.m适用于状态变量为二维的情形。这两个程序都要求各阶段状态变量的取值是离散的。

要使用好这两个程序，关键要做到以下三点： 一、 要掌握动态规划的基本原理与基本概念，能对具体问题写出基本方程的逆序形式，要认真读懂这两个程序，理解程序中每个变量所代表的含义，只有理解了程序，才能更好地使用程序，才能对运行出的结果进行分析；

二、 对具体问题要作具体的分析，要用动态规划的方法求解问题，要能够写出状态转移方程、基本方程以及允许决策集合，并要根据这些方程在matlabruan软件中建立四个M_函数，以备主程序调用；

三、 每个阶段的状态变量的取值一定要合理地离散化。

5 结束语

本文中运用matlab语言实现了动态规划（包括状态变量二维情形）的逆序算法，两个实例的应用检验了该程序的有效性，同时也表明了该算法程序对众多类典型的动态规划应用问题尤其是确定离散型的应用问题的通用性。本文拓展了文[2]中有关动态规划逆序算法的 matlab程序实现，由原来的一维情形扩展到二维情形，这是一个进步。当问题的阶段数和各阶段的状态数较小时，这两个程序能够运行出结果，但当问题的阶段数较和各阶段的状态数较大时，这两个程序运行时就要花费较长的时间，有时甚至是运行不出结果来，因为花费的时间太长。

参考文献：

[1]《运筹学》教材编写组，运筹学[M] 北京:清华大学出版社，2005.6

[2] 胡良剑 丁晓东 孙晓君，数学实验-使用MATLAB[M] 上海:上海科技出版社，2001

[3] 张志涌，精通MATLAB6.5[M] 北京:北京航空航天大学出版社，2003

[4] 刘保柱 苏彦华 张宏林， MATLAB7.0从入门到精通

（修订版） 北京：人民邮电出版社，2010

8