下载文档原格式
运筹学动态规划第7章动态规划动态规划是Bellman 在1957年提出的解多阶决策问题的方法，在那个时期，线性规划很流行，它是研究静态问题的，而Bellman 提出的解多阶决策问题的方法适用于动态问题，相对于线性规划研究静态问题，取名动态规划。
动态规划方法应用范围非常广泛，方法也比较简单。
动态规划是将一个多阶决策问题分解为一系列的互相嵌套的一步决策问题，序贯求解使问题得到简化。
动态规划问题按照问题的性质可以分为确定性的和随机性的，按决策变量的和状态变量的取值可以分为离散型的和连续型的。
此外还有依据时间变量连续取值还是离散取值又分为连续时间动态规划问题和离散时间动态规划问题。
本章重点讨论离散时间确定性动态规划问题，包括状态变量和决策变量连续取值和离散取值两种情况。
7.1解多阶决策问题的动态规划法1.多阶决策问题的例(1)最优路径问题—多阶决策问题的例为了直观，先从最优路径问题谈起，它可以看作一个多阶决策过程。
通过最优路径问题的解可以看到用动态规划法解多阶决策问题的基本思想。
考虑图7-1所示的最优路径问题。
一汽车由S 点出发到终点F ，P 和Q 是一些可以通过的点。
图中两点间标出的数字是汽车走这一段路所需的时间(单位为小时)。
最优路径问题是确定一个路径，使汽车沿这条路径由S 点出发达到F 点所用时间最短。
最优路径问题可以看作一个多阶决策问题，由S 到城市甲是第1个阶段，第1个结点P 1或第2个结点Q 1做为第1阶段可以通过的两个站点，由城市甲到城市乙是第2阶段，这个阶段是从P 1或Q 1到P 2或Q 2，由城市乙到城市丙是第3阶段，这个阶段是从P 2或Q 2到P 3或Q 3，由城市丙的P 3或Q 3到F 做为第四阶段。
（2）最优路径问题的解对最优路径问题，存在一个非常明显的原理，即最优路径的一部分还是最优路径。
换句话说，如果SQ P Q F 123是所求的最优路径，那么，汽车从这一路径上的任何一点，例如P 2，出发到F 的最优路径必为P Q F 23。
管理运筹学判断题背诵讲义第一章 线性规划与单纯形表a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的； b) 线性规划模型中增加一个约束条件,可行域的范围般将缩小,减少一个约束条件,可行域的范围一般将扩大；c) 线性规划问题的每一个基解对应可行域的一个顶点； d)如线性规划问题存在可行域，则可行域定包含坐标的原点；e)对取值无约束的变量j x ，通常令'''j j j x x x =-其中'j x ≥0,''j x ≥0,在用单纯形法求得的最优解中有可能同时出现'j x >0，''j x >0；f)用单纯形法求解标准型的线性规划问题时，与j σ>0对应的变量都可以被选作换人变量；g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；h) 单纯形法计算中,选取最大正检验数k σ对应的变量k x 作为换入变量，将使目标函数值得到最快的增长；i)一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从 单纯形表中删除,而不影响计算结果；j)线性规划问题的任-可行解都可以用全部基可行解的线性组合表示；k)若X 1,X 2分别是某一线性规划问题的最优解则X=1λX 1 +2λX 2也是该线性规划问题的最优解，其中1λ，2λ可以为任意正的实数；1)线性规划用两阶段法求解时，第一阶段的目标函数通常写为 minz=ai ix ∑(ai x 为人工变量)，但也可写为minz=i ai ik x ,只要所有k i ,均为大于零的常数； m)对一个有n 个变量、m 个约束的标准型的线性规划问题,其可行域的顶点恰好为m n c 个；n) 单纯形法的迭代计算过 程是从一个可行解转换到目标函数值更大的另一个可行解；o)线性规划问题的可行解如为最优解，则该可行解定是基可行解；p)若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解；q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；r) 将线性规划约束条件的“≤”号及“≥”号变换成“一”号,将使问题的最优目标函数值得到改善；s)线性规划目标函数中系数最大的变量在最优解中总是取正的值:t)一个企业利用3种资源生产4种产品建立线性规划模型求解得到的最优解中最多只含有3种产品的组合；u)若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解； v)一个线性规划问题求解时的选代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。
