1、动态规划的基本要素

动态规划一般要包合以下要素：阶段的划分、状态的选取、阶段決策、 状态转移方程、指标函数和最优值函数的构造以及动态规划的基木方程。

2、动态规划的基本思想

动态规划的基本思想可归纳如下：

 
(1)动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件,也就是要正确地写出基本方程。要做到这一点，必先将问题的过程分成几个相互联系的阶段，怡当地选取状态变量和决策变量及定义级优值的数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界件开始，逐段递推寻优，在每一个子问题的求解中，均利用下它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，即使整个问题的最优解。

（2）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。

（3）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态变量的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。
 

1、最短路问题的解法

问题的提法：寻求网络中两点间的最短路就是寻求连接这两个点的边的总权数为最小的通路。（注意：在有向图中，通路—开的初等链中所有的弧应是首尾相连的。）

从Vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从Vs到该点的最短路的权(称为P标号），或者是从Vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号,并且把某一个具有T标号的点改变为具有P标号的点，从而使D中具有P标号的顶点数多一个,这样，至多经过P-1步,就可以求出从Vs到各点的最短路。 

(2)Dikstra 算法的具体步骤：给定非负赋权有向图D=(V,A)
 

2、最大流问题

最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流f*，使其流量v(f)达到最大， 这种流f称为最大流，这个问题称为(网络)最大流问题。最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。

最大流问题可以建立如下形式的线性规划数学模型：

并且要学会确定最小截集最大流，这是常考的类型，不在此赘述。

1、绘制网络计划图的基本原则

（1）节点编号必须按箭尾编号小于箭头编号来标记； 

（2）网络计划图只能有一个起始节点，表示工程项目的开始，一个终点节点，表示工程项目的结束,当工程开始时或完成时有几个平行工作时，可以用虚工作将它们分别与起始节点与终点节点连接起来； 

（3）相邻两节点之间只能有一条箭线连接，否则会造成逻辑上的混乱

（4）网络计划图不能有缺口和回路

（5）绘制网络计划图时，应尽可能将关键路线布置在网络计划图的中心位置，按工作先后顺序将联系紧密的工作布置在邻近的位置。为了便于在网络计划图上标注时间等信息，箭线最好是水平线或具有一段水平线的折线。 

（6）全图要尽量避免重叠，要具有封闭性，连通性，有向性，不可逆性。
 

2、网络计划的优化

（1）工期优化：若网络计划图的计算工期大于上级要求的工期时，必须根据要求计划的进度,缩短工程项目的完工工期。主要采取的措施是增加对关键工作的投人，以便缩短关键工作的持线时间，实现工期缩短。 

（2)资源优化：在编制初始网络计划图后，需要进一步考虑尽量利用现有资源的问题。即在项目的工期不变的条件下，均衡地利用资源。具体操作如下：①优先安排关键工作所需要的资源；②利用非关键工作的总时差，错开各工作的开始时间，进开在同一时区内集中使用同一资源，以免出现高峰 ③在确实受到资源制约时，或在考虑经济效益的前提下，在许可时，也可以适当推迟工程的工期，实现错开高峰的目的。

 
(3)时间一费用优化：编制网络计划时，要研究如何使完成项目的工期尽可能缩短，费用尽可能少;或在保证既定项目完成时间条件下，所需要的费用最少;或在费用限制的条件下,项目完工的时间最短。这就是时间一费用优化要解决的问题。