利用动态规划解决生产计划安排问题摘要动态规划是解决多阶段决策过程最优化的一种方法。

这种方法是基于将困难的多阶段决策问题变换成一系列互相联系比较容易的单阶段问题的考虑，同时由于各段决策间有机的联系着，本段决策的执行将影响到下一段的决策，所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。

动态规划是现代企业管理中的一项重要决策方法，可用于解决最优路径问题、资源分配问题、成产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。

由于它有独特的解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。

动态规划模型的分类：1.离散确定型；2.离散随机型；3.连续确定型；4.连续随机型。

其中离散确定型是最基本的，本次分析是用离散确定型的动态规划模型来进行最优决策的。

近几十年来，动态规划在理论、方法和应用等方面取得了突出的进展，并在工程技术、经济、工业生产与管理、军事工程等领域得到广泛的应用。

利用动态规划对生产计划安排进行决策，可以将长久的生产问题一步步具体化，分步化，使计划更清晰，便于管理层进行决策。

关键词：动态规划生产计划决策一．动态规划法的基本概念与方法使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，此时要用到以下概念：（1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移 （6）指标函数 1.阶段用动态规划求解多阶段决策系统问题时，要根据具体情况，将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，描述阶段的变量称为阶段变量，常用字母k 表示。

上例分六个阶段，是一个六阶段的决策过程。

例中由系统的最后阶段向初始阶段求最优解的过程称为动态规划的逆推解法。

2.状态状态表示系统在某一阶段开始时所处的自然状况或客观条件。

上例中第一阶段有一个状态，即{}A 0。

第二阶段有两个状态，即{}A B 11,, ，等。

过程的状态可用状态变量来描述，某个阶段所有可能状态的全体可用状态集合来描述，如{}s A 10=，{}s A B 211=,，{}s A B C D 32222=,,,, 。

3.决策某一阶段的状态确定以后，从该状态演变到下一阶段某一状态所作的选择称为决策。

第n 阶段的决策与第n 个阶段的状态有关，通常用)(n n x u 表示第n 阶段处于n x 状态时的决策变量，而这个决策又决定了第1+n 阶段的状态。

如上例中在第k 阶段用u x k k ()表示处于状态x k 时的决策变量。

决策变量限制的范围称为允许决策集合。

用D x k k ()表示第k 阶段从x k 出发的决策集合。

4. 策略由每阶段的决策u x i n i i ()(,,,)=12 组成的决策函数序列称为全过程策略或简称策略，用p 表示。

即{}p x u x u x u x n n ()(),(),,()11122=由系统的第k 阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略。

用p x k k ()表示k 子过程策略。

即 {}p x u x u x u x k k k k k k n n ()(),(),,()=++11对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。

允许策略集合中达到最优效果的策略称为最优策略。

5. 状态转移某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定。

设第k 个阶段的状态变量为x k ，决策变量为u x k k ()，则第k +1阶段的状态x k +1，用x k +1=T x u k k k (,)表示从k 阶段到k +1阶段的状态转移规律，称它为状态转移方程。

6. 阶段效益系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是阶段状态x k 和阶段决策u k 的函数，记为y x u k k k (,)。

7. 指标函数指标函数是衡量全过程策略或子过程策略优的数量指标，指标函数的最优值称之为最优指标函数。

系统用某一策略而产生的效益用数量表示, 根据不同的实际，效益可以是利润、距离、产量或资源的耗量等。

指标函数可以定义在全过程上也可以定义在后部子过程上。

二．动态规划的逆序解法及matlab 实现{}⎩⎨⎧-===∈+=+++++1,,1,),,(,0)()(|)())(,(min )(11111 n n k u x T x x f x D u x f x u x v x f k k k k n n k k k k k k k k k k k称此为动态规划逆序求解的基本方程。

可以把建立动态规划模型归纳成以下几个步骤 （1）将问题恰当地划分为若干个阶段；（2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性； （3）规定决策变量，确定每个阶段允许决策集合； （4）写出状态转移方程；（5）确定个阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。

三．动态规划模型的建立基本方程：对于n 阶段的动态规划问题，在求子过程上的最优指标函数时，k 子过程与1+k 子过程有如下递推关系：{}⎩⎨⎧=-=+=++++0)(1,2,,1,,)(),(min )(1111n n k k k k k k k x f n n k x f x s r s f 其中第一式子里的求最小值是指在k s 的状态下，在所有作出的各种决策k x 中，取一个第k 阶段的指标值),(k k k x s r 与以k x 为第1+k 状态的1+k 子过程的最优指标函数值之和中的最小值。

对于求指标函数最大的动态规划问题的基本方程则把min 改为max 就行了。

下面用一个例子来说明如何用动态规划解决生产计划问题某工厂有1000台机器，可以在高低两种负荷下进行生产。

家属在高负荷下生产时，产品的年产量g 和投入的机器数量u 1的关系为g =8u 1,机器的完好率为0.7，在低负荷下生产时，产品的年产量h 和投入的机器数量y 的关系为h=5y ，机器完好率为0.9.现在要求制定一个5年内生产计划，问应如何安排在5年内的产品总产量最高。

解：设阶段数k 表示年度。

状态变量s k 为第k 年度初拥有的完好机器台数；决策变量u k 为第k 年度中分配高负荷下生产的机 器台数。

低负荷下生产的机器台数是s k -u k 。

状态转移方程允许决策集合 0≤u k ≤s k 第k 年度产量为(,)85()k k k k k k v s u u s u =+-指标函数为51,51(,)k k k k V v s u ==∑递推方程为6610()0u1()max {85()(0.70.9())}5,,2,1k kk k k k k k k k k u s f s f s u s u f u s u k +≤≤⎧=⎪⎪=+-++-⎨⎪=⎪⎩当k=5时 , 5555565660()max {85()()}u s f s u s u f s ≤≤=+-+55560max{35}u s u s ≤≤=+u 5*= s 5 , f 5(s 5)=8 s 5当k=4时 ,1)(0.70.9()k k k k k k k s au b s u u s u +=+-=+-444444454440()max {85()(0.70.9())}u s f s u s u f u s u ≤≤=+-++-= 444440max {13.6u +12.2( s - u )}u s ≤≤=44440max {1.4u +12.2 s }u s ≤≤u 4*= s 4 , f 4(s 4)=13.6s 4 u 5*= s 5 , f 5(s 5)=8 s 5 u 4*= s 4 , f 4(s 4)=13.6s 4依次类推可得， u 3*=s 3 f 3(s 3)=17.5 s 3u 2*=0 f 2(s 2)=20.8 s 2u 1*=0 f 1(s 1)=23.7 s 1 因此最优策略为:u 1*=0, u 1*=0, u 3*=s 3, u 4*= s 4 u 5*= s 5, 最高产量为23700。

四．结论我们从以上例子可以看到，用动态规划解决一个看似难以下手的问题其实是比较容易的，在计算方面，由于计算机程序的可实现性，运算量也很小，实际运用与操作都是具有相当的现实性与简易性的。

附录动态规划逆序算法的matlab 实现%M函数dynprog.mfunction[p_opt,fval]=dynprog(x,DecisFun,ObjFun,TransFun)% [p_opt,fval] =dynprog(x,DecisFun,ObjFun,TransFun)% 自由始端和终端的动态规划，求指标函数最小值的逆序算法递归计算程序。

x是状态变量，一列代表一个阶段状态；% M函数DecisFun（k,x）由阶段k的状态变量x求出相应的允许决策变量；% M函数ObjFun(k,x,u)是阶段指标函数，M函数TransFun(k,x,u)是状态转移函数，其中x 是阶段k的某状态变量，u是相应的决策变量；% 输出p_opt由4列构成，p_opt=[序号组；最优轨线组；最优策略组；% 指标函数组];fval是一个列向量，各元素分别表示p_opt各最优策略组对应始端状态x的最优函数组；k=length(x(1,:)); f_opt=nan*ones(size(x)); d_opt=f_opt;t_vubm=inf*ones(size(x)); x_isnan=~isnan(x); t_vub=inf;% 计算终端相关值tmpl=find(x_isnan(:,k));tmp2=length(tmpl);for I=1:tmp2u=feval(DecisFun,k,x(i,k)); tmp3=length(u);for j=1:tmp3tmp=feval(ObjFun,k,x(tmpl(i),k), u(j));if tmp<=t_vub,f_opt(i,k)=tmp; d_opt(i,k)=u(j); t_vub=tmp;end;end;end%逆推计算各阶段的递归调用程序for ii=k-1:-1:1tmp10=find(x_isnan(:,ii));tmp20=length(tmp10); for i=1:tmp20u=feval(DecisFun,ii,x(i,ii));tmp30=length(u); for j=1:tmp30tmp00=feval(ObjFun,ii,x(tmp10(i),ii),u(j));tmp40=feval(TransFun,ii,x(tmp10(i),ii),u(j));tmp50=x(:,ii+1)-tmp40;tmp60=find(tmp50= =0);if~isempty(tmp60),tmp00=tmp00+f_opt(tmp60(1),ii+1);if tmp00<=t_vubm(i,ii)f_opt(i,ii)=tmp00; d_opt(i,ii)=u(j);t_vubm(i,ii)=tmp00;end;end;end;end;end;fval=f_opt(tmp1,1);% 记录最优决策、最优轨线和相应指标函数值p_opt=[];tmpx=[];tmpd=[];tmpf=[];tmp0=find(x_isnan(;,1));tmp01=length(tmp0);for i=1:tmp01,tmpd(i)=d_opt(tmp0(i),1);tmpx(i)=x(tmp0(i),1);tmpf(i)=feval(ObjFun,1,tmpx(i),tmpd(i));p_opt(k*(I-1)+1,[1,2,3,4])=[1,tmpx(i),…,tmpd(i),tmpf(i)]; for ii=2:ktmpx(i)=feval(TransFun,ii-1,tmpx(i),tmpd(i);tmp1=x(:,ii)-tmpx(i); tmp2=find(tmp1= =0);if~isempty(tmp2)tmpd(i)=d_opt(tmp2(1),ii);end;tmpf(i)=feval(ObjFun,ii,tmpx(i),tmpd(i));p_opt(k*(i-1)+ii,[1,2,3,4])=[ii,tmpx(i),…,tmpd(i),tmpf(i)]; end;end;。