第%卷第,期信息工程大学学报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>3G3?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的强大功能，对动态规划模型的求解方法做［&］［!］这类问题全局最优解的一种有效方法，特别是对于了尝试，并结合“最佳组队问题”和最短路问题实际中的某些非线性规划问题可能是最优解的唯进行了应用检验，实际证明结果是令人满意的。一方法。然而，动态规划仅仅是解决多阶段决策问题的一种方法，或者说是考查问题的一种途径，而&动态规划的基本模型不是一种具体的算法。就目前而言，动态规划没有统一的标准模型，其解法也没有标准算法，在实际实际中，要构造一个标准的动态规划模型，通应用中，需要具体问题具体分析。动态规划模型的常需要采用以下几个步骤：求解问题是影响动态规划理论和方法应用的关键!划分阶段按照问题的时间或空间特征，把所在，而子问题的求解和大量结果的存储、调用更问题分为若干个阶段。这些阶段必须是有序的或是一个难点所在。然而，随着计算机技术的快速发者是可排序的（即无后向性），否则，应用无效。展，特别是内存容量和计算速度的增加，使求解较"选择状态将问题发展到各个阶段时所处收稿日期：!""#$"%$&%修回日期：!""’$"’$"(作者简介：于斌（&)(!$），男，江苏姜堰人，信息工程大学硕士研究生，主要研究方向为通信工程。>=信息工程大学学报()).年"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""的各种客观情况用不同的状态表示，即称为状态。状态的选择要满足无后效性和可知性，即状态不仅依赖于状态的转移规律，还依赖于允许决策集合和指标函数结构。!确定决策变量与状态转移方程当过程处于某一阶段的某个状态时，可以做出不同的决策，描述决策的变量称为决策变量。在决策过程中，由一个状态到另一个状态的演变过程称为状态转移。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。"写出动态规划的基本方程动态规划的基本方程一般根据实际问题可分为两种形式，逆序形式和顺序形式。动态规划基本方程的逆序形式为!"）!$"!%"（#"）｛&"$"（#"%&｝"!’，.，&（#""#$（#"，）%!"%&），’’&，(，{边界条件：!’%&（#’%&）!)或!（’#’）!&（’#’，$’）（&）其中第"阶段的状态为#"，其决策变量$"表示状态处于#"%&的决策，（#"，状态转移方程为#"%&!("$"）"阶段的允许决策集合记为%"）&"$"，（#"，（#"，）为指标函数。当求解时，由边...