运筹学 动态规划-作业及答案

第八章 动态规划一、用逆序法求解下列问题1、P237, 8.1 有600万元资金用于三个工厂的更新改造，投资数以百万元为单位取整数，已知工厂II 的投资不超过300万元，工厂I 和III 的投资均不少于100万元，又不超过400万元，已知各工厂投资更新改造后，每年可增加的效益如下表，试用动态规划方法确定投资分配方案，使预期效益为最大。

(单位：万元)解：该问题可分为3个阶段，分别为分配资金给Ⅰ、Ⅱ、Ⅲ三个厂。

设k 为阶段变量，第k 个阶段给第k 个厂分配设备；k S 是第k 个阶段的状态变量，表示可分配给第k 个厂到第3个厂的设备数；k x 是第k 个阶段的决策变量，表示分配给第k 个厂的设备数；状态转移方程：k k k x S S -=+1，并且41=S 。

指标函数：)](),([max )(11+++=k k k k k x k k S f x s r S f k0)(44=S f下面按照逆序解法求解。

第三阶段：500400,300,200,1003，=S 万，33x S =, 第二阶段：500,400,300,2002=S 万。

223x S S -=第1阶段：6001=S 万。

112x S S -=按照与计算相反的顺序可推知有一个最优解：3001=*X ，2002=*X ，1003=*X ，最大利润为25万。

2、P237, 8.2 如图，要铺设一条从A 到E 的输油管线，箭线旁数字为各点间相应距离（km ）一个运筹学小组正研究讨论线路选择，使得总距离为最短。

甲提出用求最短距离的Dijkstra 算法求解；乙认为这个问题也可用动态规划方法求解，但丙丁认为从A 到E 经B1、D1的线路，与经B2、C1、D2的线路阶段数不等，故动态规划行不通；丙提出建立整数规划模型求解，甲乙对此持怀疑的态度；丁设想用破圈法或避圈法找出图中最小部分树，树图中A-E 的唯一链即为A 至E 铺设管道的最佳选择，对此甲和乙不同意。

《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（）BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是（）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。

CA.降低的B.不增不减的C.增加的D.难以估计的6.最小枝权树算法是从已接接点出发，把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中，( )的说法是错误的。

DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。

CA.1200B.1400C.1300D.17009.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（）。

DA.最短路线—定通过A点B.最短路线一定通过B点C.最短路线一定通过C点D.不能判断最短路线通过哪一点10.在一棵树中，如果在某两点间加上条边，则图一定( )AA.存在一个圈B.存在两个圈C.存在三个圈D.不含圈11.网络图关键线路的长度( )工程完工期。

CA.大于B.小于C.等于D.不一定等于12.在计算最大流量时，我们选中的每一条路线( )。

CA.一定是一条最短的路线B.一定不是一条最短的路线C.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线13.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法14.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用( )。

《运筹学》第五章习题及答案《运筹学》第五章习题1．思考题（1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。

（2）动态规划的阶段如何划分？（3）试述用动态规划求解最短路问题的方法和步骤。

（4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。

（5）试述建立动态规划模型的基本方法。

（6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。

2．判断下列说法是否正确（1）动态规划分为线性动态规划和非线性动态规划。

（2）动态规划只是用来解决和时间有关的问题。

（3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。

（4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。

（5）在动态规划模型中，问题的阶段等于问题的子问题的数目。

（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加而引起的。

3．计算下图所示的从A到E的最短路问题4．计算下图所示的从A到E的最短路问题5．计算从A到B、C、D的最短路线。

已知各线段的长度如下图所示。

6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？7．用动态规划求解下列各题（1）．222211295m a x x x x x z-+-=；???≥≤+0,52121x x x x；（2）．33221m a x x x x z=???≥≤++0,,6321321x x x x x x；8．某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过10千克。

物品重量及其价值等数据见下表。

试问每种物品装多少件，使整个背包的价值最大？913千克。

物品重量及其价值的关系如表所示。

试问如何装这些物品，使整个背包价值最大？10量和相应单位价值如下表所示，应如何装载可使总价值最大？303011底交货量，该厂的生产能力为每月600件，该厂仓库的存货能力为300件，又每生产100件产品的费用为1000元。

《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（）BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是（）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。

CA.降低的B.不增不减的C.增加的D.难以估计的6.最小枝权树算法是从已接接点出发，把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中，( )的说法是错误的。

DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。

CA.1200B.1400C.1300D.17009.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（）。

DA.最短路线—定通过A点B.最短路线一定通过B点C.最短路线一定通过C点D.不能判断最短路线通过哪一点10.在一棵树中，如果在某两点间加上条边，则图一定( )AA.存在一个圈B.存在两个圈C.存在三个圈D.不含圈11.网络图关键线路的长度( )工程完工期。

CA.大于B.小于C.等于D.不一定等于12.在计算最大流量时，我们选中的每一条路线( )。

CA.一定是一条最短的路线B.一定不是一条最短的路线C.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线13.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法14.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用( )。

动态规划练习题USACO 2.2 Subset Sums题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。

举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：and {1,2}这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:{1,6,7} and {2,3,4,5} {注1+6+7=2+3+4+5}{2,5,7} and {1,3,4,6}{3,4,7} and {1,2,5,6}{1,2,4,7} and {3,5,6}给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。

程序不能预存结果直接输出。

PROGRAM NAME: subsetINPUT FORMAT输入文件只有一行，且只有一个整数NSAMPLE INPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数，如果不存在则输出0。

SAMPLE OUTPUT (file subset.out)4参考程序如下：#include <fstream>using namespace std;const unsigned int MAX_SUM = 1024;int n;unsigned long long int dyn[MAX_SUM];ifstream fin ("subset.in");ofstream fout ("subset.out");int main() {fin >> n;fin.close();int s = n*(n+1);if (s % 4) {fout << 0 << endl;fout.close ();return ;}s /= 4;int i, j;dyn [0] = 1;for (i = 1; i <= n; i++)for (j = s; j >= i; j--)dyn[j] += dyn[j-i];fout << (dyn[s]/2) << endl;fout.close();return 0;}USACO 2.3 Longest Prefix题目如下：在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。

动态规划运筹学例题动态规划是运筹学中常用的一种优化技术，它利用规划、三角函数和其他数学技术来解决日常生活中的各种问题，比如最优路线问题、最优资源分配问题、最优出行路线问题等。

本文将通过一个例题，来介绍动态规划的基本思想，以及如何利用动态规划来解决问题。

例题一：已知一条路线，由A点到B点，有N个途经的节点，每个节点之间的距离已知。

求从A到B的最短路线。

按照动态规划的思想，首先将该问题分解为若干个子问题，并根据子问题的解来解决原问题，这种分解和解决问题的方式称为动态规划。

对于上面的问题，可以将其分解为N个子问题，分别是从A到第1个节点、从第1个节点到第2个节点、从第2个节点到第3个节点，以此类推，最后一个子问题是从第N-1个节点到B点的最短路程。

将上面的N个子问题中，从第i个节点到B点的最短路程记为d[i]，由于从第i个节点到B点可能经过i+1、i+2、……、N-1节点，因此要找到d[i]，只需要找到经过i+1、i+2、……、N-1节点的最短路程即可，即求d[i]=Min{d[i+1]+length[i][i+1],d[i+2]+length[i][i+2],…,d[N-1]+length[i][N-1]}，其中length[i][j]是第i个节点到第j个节点的距离。

以上就是动态规划的解题步骤，它能将原问题分解成若干个子问题，并找到最优解。

对于本例来说，通过上述步骤，就可以得到从A 到B的最短路程。

这种分解和求解问题的方法是动态规划，可以用来解决许多类似的问题，如：1）最优路线问题；2）旅行推销员问题；3）硬币找零问题。

动态规划的一大特点是，他能很好地将问题分解为多个子问题，并能从子问题的解中求解出最优解。

总之，动态规划是一种很有用的优化技术，它可以有效解决各种运筹学问题。

它不仅可以帮助我们解决许多具体问题，而且还能使我们更好地理解问题及其解法。

动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。

该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。

他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。

他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。

动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。

动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。

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

第一节动态规划的基本方法多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。

例1：最短路线问题某工厂需要把一批货物从城市A运到城市E，中间可经过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？下面引进几个动态规划的基本概念和相关符号。

(1)阶段(Stage)把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。

如例l中 (最短路线问题)可看作是n=4阶段的动态规划问题，k=2表示处于第二阶段。

(2)状态(State)状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。

描述各阶段状态的变量称为状态变量，常用字母sk表示第k阶段的状态变量，状态变量的取值范围称为状态集，用Sk表示。

如例l中，第一阶段的状态为A（即出发位置）。

第二阶段有三个状态：B1 、B2、B3，状态变量s2=B2表示第2阶段系统所处的位置是B2。

《运筹学》课堂作业及答案第⼀部分绪论第⼆部分线性规划与单纯形法1 判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同，但从⼏何上理解，两者是⼀致的；(b)线性规划模型中增加⼀个约束条件，可⾏域的范围⼀般将缩⼩，减少⼀个约束条件，可⾏域的范围⼀般将扩⼤；(c)线性规划问题的每⼀个基解对应可⾏域的⼀个顶点；(d)如线性规划问题存在可⾏域，则可⾏域⼀定包含坐标的原点；(e)对取值⽆约束的变量x i，通常令其中，在⽤单纯形法求得的最优解中有可能同时出现(f)⽤单纯形法求解标准型的线性规划问题时，与对应的变量都可以被选作换⼊变量；(g)单纯形法计算中，如不按最⼩⽐值原则选取换出变量，则在下⼀个解中⾄少有⼀个基变量的值为负；(h)单纯形法计算中，选取最⼤正检验数δk对应的变量x k作为换⼊变量，将使⽬标函数值得到最快的增长；(i)⼀旦⼀个⼈⼯变量在迭代中变为⾮基变量后，则该变量及相应列的数字可以从单纯形表中删除，⽽不影响计算结果；(j)线性规划问题的任⼀可⾏解都可以⽤全部基可⾏解的线性组合表⽰；(k)若x1，x2分别是某⼀线性规划问题的最优解，则也是该线性规划问题的最优解，其中λ1，λ2可以为任意正的实数；(1)线性规划⽤两阶段法求解时，第⼀阶段的⽬标函数通常写为X ai为⼈⼯变量)，但也可写为，只要所有k i均为⼤于零的常数；(m)对⼀个有n个变量、m个约束的标准型的线性规划问题，其可⾏域的顶点恰好为个；(n)单纯形法的迭代计算过程是从⼀个可⾏解转转换到⽬标函数值更⼤的另⼀个可⾏解；(o)线性规划问题的可⾏解如为最优解，则该可⾏解⼀定是基可⾏解；(p)若线性规划问题具有可⾏解，且其可⾏域有界，则该线性规划问题最多具有有限个数的最优解；(q)线性规划可⾏域的某⼀顶点若其⽬标函数值优于相邻的所有顶点的⽬标函数值，则该顶点处的⽬标函数值达到最优；(r)将线性规划约束条件的“≤”号及“≥”号变换成“＝”号，将使问题的最优⽬标函数值得到改善；(s)线性规划⽬标函数中系数最⼤的变量在最优解中总是取正的值；(t)⼀个企业利⽤3种资源⽣产4种产品，建⽴线性规划模型求解得到的最优解中，最多只含有3种产品的组合；(u)若线性规划问题的可⾏域可以伸展到⽆限，则该问题⼀定具有⽆界解；(v)⼀个线性规划问题求解时的迭代⼯作量主要取决于变量数的多少，与约束条件的数量关系相对较⼩。