动态规划求解方法的Matlab实现及应用[1].txt我自横刀向天笑，笑完我就去睡觉。
你的手机比话费还便宜。
路漫漫其修远兮，不如我们打的吧。
第%卷第,期信息工程大学学报S>:+%<>+,!""’年>月T>8D3F:>C53C>DEFB2>3G3?23@@D23?032H@DA2BI6@N+!""’!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!动态规划求解方法的!"#$"%实现及应用于斌，刘姝丽，韩中庚<信息工程大学信息工程学院，河南郑州#’"""!）摘要：文章对动态规划问题的求解方法进行了分析研究，根据问题的特点、难点和关键点做了针对性的处理，然后用!"#$"%做了实现尝试，从而实现了“最佳组队”和“最短路线”等问题的求解。
实践证明所采用方法和程序都是有效的。
关键词：动态规划；基本方程；!"#$"%实现；最佳组队中图分类号：*!!&+,文献标识码：-文章编号：&%.&$"%.,<!""’）",$"">’$"#!"#$"%&’"$(>"#(*+*,#-’./+"0(123*43"00(+45663*"1-"+78#9566$(1"#(*+/0123，4506789:2，。
-<=7>3?9?@3?<53AB2B8B@>C53C>DEFB2>3G3?23@@D23?，53C>DEFB2>3 G3?23@@D23?032H@DA2BI，=7@3?J7>8 #’"""!，K723F）5%9#3"1#：1IF3F:IJ23?F3L23H@AB2?FB23?B7@LI3FE2MND>?DFEE23?FNND>FM7，F3@CC@MB2H@L2AN>AF:7FAO@@3L>3@FMM>DL23?B>B7@ND>O:@E+P7@3F3FBB@ENB>3B7@ND>O:@EA>C“1@ABB@FE9C>DE23?”F3L“67>DB@ABNFB7”7FAO@@3A8MM@AAC8::IEFL@OIQFB:FO+5B2AND>H@LB7FBB7@E@B7>LF3LND>?DFEE@FD@@CC@MB2H@+:’/。
*379：LI3FE2MND>?DFEE23?；OFA2M@R8FB2>3；QFB:FO；O@ABB@FE9C>DE23?ND>O:@E小规模的动态规划问题成为可能，从而使得动态规"引言划的理论和方法在实际中的应用范围迅速增加。
目前，在计算机上实现动态规划的一般求解方动态规划是一类解决多阶段决策问题的数学法并不多见，尤其是用来解决较复杂的具体问题的方法，在工程技术、科学管理、工农业生产及军事等成果甚少。
本文从实际出发，利用数学工具软件领域都有广泛的应用。
在理论上，动态规划是求解QFB:FO的强大功能，对动态规划模型的求解方法做［&］［!］这类问题全局最优解的一种有效方法，特别是对于了尝试，并结合“最佳组队问题”和最短路问题实际中的某些非线性规划问题可能是最优解的唯进行了应用检验，实际证明结果是令人满意的。
一方法。
然而，动态规划仅仅是解决多阶段决策问题的一种方法，或者说是考查问题的一种途径，而&动态规划的基本模型不是一种具体的算法。
就目前而言，动态规划没有统一的标准模型，其解法也没有标准算法，在实际实际中，要构造一个标准的动态规划模型，通应用中，需要具体问题具体分析。
动态规划模型的常需要采用以下几个步骤：求解问题是影响动态规划理论和方法应用的关键!划分阶段按照问题的时间或空间特征，把所在，而子问题的求解和大量结果的存储、调用更问题分为若干个阶段。
这些阶段必须是有序的或是一个难点所在。
然而，随着计算机技术的快速发者是可排序的<即无后向性），否则，应用无效。
展，特别是内存容量和计算速度的增加，使求解较"选择状态将问题发展到各个阶段时所处收稿日期：!""#$"%$&%修回日期：!""’$"’$"(作者简介：于斌<&>(!$），男，江苏姜堰人，信息工程大学硕士研究生，主要研究方向为通信工程。
>=信息工程大学学报年""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" ""的各种客观情况用不同的状态表示，即称为状态。
状态的选择要满足无后效性和可知性，即状态不仅依赖于状态的转移规律，还依赖于允许决策集合和指标函数结构。
!确定决策变量与状态转移方程当过程处于某一阶段的某个状态时，可以做出不同的决策，描述决策的变量称为决策变量。
在决策过程中，由一个状态到另一个状态的演变过程称为状态转移。
状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
"写出动态规划的基本方程动态规划的基本方程一般根据实际问题可分为两种形式，逆序形式和顺序形式。
动态规划基本方程的逆序形式为!"）!$"!%"<#"）｛&"$"<%&｝"!’，.，&<#""#$<#"，）% !"%&），’’&，(，{边界条件：!’%&<#’%&）!>或!<’#’）!&<’#’，$’）<&）其中第"阶段的状态为#"，其决策变量$"表示状态处于#"%&的决策，<#"，状态转移方程为#"%&!("$"）"阶段的允许决策集合记为%"）&"$"，<#"，<#"，）为指标函数。
当求解时，由边界条件从"!’开始，由后向前逆推，逐阶段求出最优决策和过程的最优值，直到最后求出!<&#&）即得到问题的最优解。
类似的，动态规划基本方程的顺序形式为{ !"<#"%&）!"#$$"!%>#"%&）｛&"<#"%&，$"）%!"’&<#"）｝，"!&，(，.，’’&，’）<#&边界条件：!>!><(）其中状态转移方程为#"!(>"$"）"阶段的<#"%&，，允许决策集合为%<>#"%&）指标函数为&"，<#"%&，$"）。
当求解时，由边界条件从"!&开始，由前向后顺推，逐阶段求出最优决策和过程的最优值，直到最后求出!<’#’）即得到问题的最优解。
"(基本方程求解的*+$,+-实现动态规划没有统一的标准模型，对于基本方程<&）和<(）的求解也没有统一的标准算法。
但是，我们分析用动态规划解决问题的思想方法，会发现一个共同的明显特征，这就是将所研究的问题分为关联着的多个阶段后，每个阶段都有若干个对应的子问题，求解问题的关键就是按阶段次序求解大量子问题的最优解。
而且对于每一个子问题的求解结果都必须完整贮存下来，上一阶段子问题的结果将对下一阶段产生一定的影响，即对全局最优决策也产生影响。
如何处理好所有各阶段的大量子问题的求解及结果的贮存和调用等，这是编程求解动态规划问题的难点所在，也是必须要解决的问题。
(*&*+$,+-实现方法综述在这里仅就动态规划基本方程的逆序形式进行讨论，顺序形式也类似。
对于各个阶段的子问题的求解方法基本都是相同的，在当前阶段的所有子问题求得最优决策以后，通过状态转移方程可以确定出下一阶段的状态和允许状态集合，从而可以在决策集合上来寻求这个新阶段的最优决策。
从第’个阶段出发，直到第一个阶段为止，即可得到全过程的最优决策。
因此，在具体实现的过程中，针对每一个状态编写一个相对通用的函数，然后在主程序中循环调用该函数，以实现任意状态下的最优决策。
问题的主体程序框图如图&所示。
图&主程序框图(*(具体程序实现按照如上的程序框图，编写相关程序，主要由.个子程序构成：#主函数/012$3"1［#+3，453］!+,-’<6，7）输入状态向量6和相关指标矩阵7，返回最优策略和相应指标值；用全局变量8，88，888，分别记录指标值、状态地址和相应决策。
$状态计算子函数!.’/0-1’//<1，66，9+,）计算相应状态下的最优决策，并存储；1为目前阶段数，66为前一阶段某个状态的最优决策，9+,为相应指标值。
!辅助计算子函数!.’/0-1’［6:。
，<］!2>32<6，$"$，1，6:。
）确定变量88；在某个阶段，对该阶段所第+期于斌等：动态规划求解方法的9/#:/。