动态规划投资问题范例

动态规划投资问题范文1

关键词： 高维 优化方法 渠道工程

1　大中型渠道工程优化设计的高维动态规划模型及求解方法

1.1　大中型渠道工程优化设计的高维动态规划模型 文献［13］提出了大中型渠道工程系统的定性定量混合系统动态规划模型，模型的决策变量为各渠段纵坡(Ii)和各渠段的定性方案(Si)，目标函数为工程计算分析期内的总支出费用，并考虑首末水位、不冲不淤、渠道最小水位衔接和工程总约束.

(1) 填挖土方量约束. 若获得满足约束条件，且使文献［13］目标函数最小的解，而渠道工程的填方量大于挖方量，附近又没有土方资源，此时文献［13］中模型获得的解就不一定为最优解，因此，还应加上填挖方量约束方程

(1)

式中Vis(Ii，Si)和Vis(Ii，Si)为i渠段的填方和挖方量.

(2)流量损失约束.不同的衬砌方式、不同的渠道过水断面影响渠段的流量损失和投资，而输配水渠道的设计主要在于保证下游获得在一定水位时的流量，因此，在可能的情况下还应进一步考虑流量损失约束：

(2)

式中h4i(Ii，Si)为i渠段的流量输水损失，取决于i渠道的定性方案Si(沿渠衬砌方式等)、土壤性质、流量和过水断面；Q0，QN 分别为渠道工程的渠首设计引水量和渠末应获得的设计流量

1.2 求解方法 考虑全部约束条件，则模型为四维，该模型的求解工作量、难度比文献［13］的二维问题大大增加了，为此本文在模型的求解方面进行了一定的探讨，提出了高维动态规划的试验选优方法.

1.2.1 基本原理 本文对高维动态规划的降维传统技术之一——拉格朗日乘子法［1］进行了修正，提出了广义拉氏方法，使加入到目标函数中去的约束检验在计算迭代过程中进行，而不是传统的计算迭代结束后检验，因而不管拉格朗日乘子取值多少，采用广义拉氏方法的解均为满足约束条件的可行解.此时的问题就转化为寻找最优拉氏乘子的问题，根据数学模型和拉氏乘子的物理意义，容易知道拉氏乘子的取值范围，在此基础上则可采用部分试验选优方法［8—12］(如正交试验法)确定最优的乘子值.

1.2.2 拉氏乘子已知时的优化技术 对于一般的高维问题(下面方程式依次为(3)(4))

Wj(λ1，X1)=bj-hj1(X1)，(8)

Wi(λ1)=Wi(λ1，X*1)，j=1，2，…，m-1，(9)

式中ζ1为hm1(ζ1)=λ1 的解，0≤X1≤ζ1，同时迭代过程中X1应满足加入至目标函数中去的m-1个约束，Wj(λ1，X1)≥0，j=1，2，…，m-1.

i 阶段：

(10)

Wj(λi，Xi)=Wj(λi-1)-hji(Xi)，(11)

λi-1=λi-hmi(λi)，(i=2，3，…，N)(12)式中ζ为hmi(ζi)=λi 的解，0≤Xi≤ζi，同时迭代过程中Xi应满足 Wj(λi，Xi)≥0(j=1，2，…，m-1)，最后i=N时式(9)中的松驰变量Wj=Wj(λ*N).

由上递推关系可获得uj(j=1，2，…，m-1)已知情况下的最优决策X*i(i=1，2，…，N).

1.2.3 拉氏乘子的优化技术 由式(5)目标函数可知(F)/(bj)=uj，uj 的物理意义为某种资源(bj)的影子价格，uj 的数值大小取决于该资源的利用情况.在求解实际问题时，使式(3)、(4)最优的u*j 获得是困难的，但确定uj的数值范围是容易的.

例如已知uj(j=1，2，…，m-1)的数值范围来确定其对应的最优值 u*j，最直接的方法是把uj在其数值范围内离散，然后将所有组合代入模型(5)、(6)，以获得最优解，若m较大时，这样工作量太大，显然是不太实际的，但可以采用部分试验选优方法如正交试验法［14～17］，在全部可能组合中选取少量组合， 采用模型(5)、(6)以获得优化解，然后通过正交分析来获得所有可能组合中的最优解及依次的次优解.

1.2.4 正交试验和正交表 采用正交试验在uj(j=1，2，…，m-1)的取值范围内确定u*j，其最优性、精度和计算工作量的关键在于正交表的构造选择.正交试验的最优性在文献［15—17］中已被广泛讨论和确认，精度和uj在其对应取值范围内的离散步长有关，并直接影响计算优化的工作量.若构造一般型正交表Lp(tq)，t为uj 在其可行域内离散的个数，其为素数或素数幂；q为该正交表最多可以按排uj的个数，即q≥m-1;P为对应一维动态规划模型计算个数；

P=

(13)

q=(-1)/(t-1)

(14)

式中v为任意正整数，则可以获得计算工作量(P)和m，t之间的关系

P≥(m-1)(t-1)+1

(15)

选择构造正交表时完全可以使式(15)取等号，则若m=1001，取t=11或101，那么一个1001维动态规划问题的优化工作量相当于104+1或105+1个对应一维动态规划问题的计算工作量，目前一般计算机均可接受，而对于现行动态规划的所有降维、简化方法是无法想象的.

1.3 渠道工程优化设计模型的求解 模型(1)—(6)转化为一维问题：

Wj(λ1，X1)=bj-hj1(X1)，(21)

Wj(λ1)=Wj(λ1，X*1)，(22)

X1∈(I1，S1)，式中ζ1∈［v1，u1］，设渠段1定性方案依

次代入下式：

(23)

得对应的，t=1，2，…，T1｝;t1为对应定性方案u时的纵坡I1可行取值范围，结合式(17)、(18)有：（下面的情况分别为：渠段末有流量变化，无交叉节制提水建筑；除上情况）

(24)

i 阶段：

(25)

Wj(λi，Xi)=Wj(λi-1)-hji(Xi)，

(26)

λi-1=λi-h1i(Xi)，

i=2，3，…，N.

(27)

Xi∈(Ii，Si).式中ζi∈(vi，ui)，渠段i的定性方案S依次代入下式：

以此递推得uj已知情况下式(16)—(19)的解.

关于uj(j=2，3，4)的取值范围确定.本课题根据Ii和Si的可行范围、沿渠地形的变化情况、各渠段的流量，以及模型(16)中目标函数的物理意义，可以知道：

的数值范围(Ai，Bi)即：

若设u2=u3=u4=ui，则可得：

采用最不利的(Ii，Si)代入即可获得uj的取值范围.

1.4 实例分析 采用文献［13］算例，有关主要参数和可能的定性方案见表1.通过计算分析u2，u3，u4的取值范围均取为［0，2.4］，选用L9(34)型正交表对所选的9个uj组合进行了对应的一维动态规划问题求解，其最优解和采用DDDP法求解结果目标值相差5.6%，对uj进一步离散选用L25(56)型正交表选择对应25个uj组合进行对应的一维动态规划问题求解分析，其最优解和采用DDDP法求解结果基本相同，此时占用计算机的运算时间不到DDDP法的1/6，有关计算主要成果摘要见表2和表3.

2　结 论

(1)寻求高维动态规划的求解方法是近40年国内外众多学者久攻不下的系统科学重大研究的课题.目前经典方法一般仅能求解3—5维问题，其它近似方法也只能求解数拾维问题.本文提出的试验选优方法可以使较高维数的高维动态规划问题求解成为可能.本文的试验方法主要针对正交试验法而言的，对于采用其它部分试验选优方法进行优化分析，还有待于进一步探讨.

(2)本文提出的大型渠道工程优化设计的高维动态规划模型对大型调水工程优化设计具有较为重要的参考价值.

表1 定性方案和基本数据

渠 段 OA AB BC CD 渠长/km 15 11 32 21 设计流量/m/s 100 100 50 50 加大流量/m/s 120 120 60 60 最小流量/m/s 40 40 20 20 沿渠土壤性质 砂土 砂土 砂壤 砂壤 断面形状和衬砌方案 a.梯形断面；扩宽系数 K=2.5，2.2，2.0，1.8；换土压实.b.梯形断面；扩宽系数 K=2.2，2.0，1.8，1.6；无衬砌. 可行提水泵站方案的提水扬程/m 0

2

3 0

2

3 2

3

4 0

2

3 沿渠地面高程/m 36.3 37.7 38.1 39.2 39.9 其它主要资料 a.总投资小于1亿元；b.渠道首末水头分别为35.5m和37.5m.

c.要求挖方和填方之差小于10%.

表2 计算成果对照表

渠 段 DDDP 法 试验方法uj离散5点 试验方法uj

离散3点 备注 运算时间 15小时40分 2小时32分 1小时08分 　 目标值：计算分析期内

总支出费用现值/亿元 2.802 2.802 2.96 　 投资现值/亿元 0.934 0.934 0.967 　 总土方量/104m 1109 1109 1185 　 总挖方/104m 602 602 687 　 总填方/104m 507 507 498

动态规划投资问题范文2

【关键词】经济管理；物流；运筹学

运筹学具有良好的科学性，它的应用也是非常的广泛。而在各个领域中，运筹学对问题的解决方法也是多种多样。在系统的分析和问题的求解方面，不同领域中的运筹学的特点是相同的，但也存在着一些内在的特点。本文主要从经济管理和物流入手，对运筹学的应用进行了简单的分析。

一、经济管理中的运筹学

（一）动态规划

在运筹学中，动态规划属于其中的一个分支，它作为一种数学的最优化方法，能够对多阶段决策进行一个有效的解决和处理。在具体的操作中，多阶段决策问题的处理非常的困难，而动态规划能将其划分为单个阶段的决策问题，这样一来，在解决决策问题的处理过程中，也就容易得到决策问题的解决和实现。之后的过程中，当一个个简单的决策问题得到处理后，再通过整体的规划，复杂的多阶段决策问题的解决也就能够得以实现。在解决问题的整个过程中，寻求最优决策即是动态规划的重要内容。它能够优化多阶段决策的处理过程，也就是以系统总体为基点，使各阶段决策处理中的目标函数值的实现得到最优化。作为动态规划，它在经济管理中能够对生产的最优控制、设备的更新、资源的分配、路径的最优化、库存、排序、生产的调度等问题进行有效的解决和处理。也正因为如此，运筹学中的动态规划已成为现代经济管理中的一个重要方法。

（二）线性规划

运筹学中的线性规划的应用非常的广泛，随着经济管理的发展，它的理论也逐步的得到了成熟，其对资源的优化配置、物资的调用、生产的计划等问题能够进行有效的处理。对于线性规划而言，在经济管理的活动中，它主要对两个问题有所研究：一是依据仅有的资金和设备等资源，对生产计划的安排进行合理的研究，以此获得经济效益的最大化；二是对工艺流程的安排、产品成份的调整和生产的组织进行合理的研究，最少的进行资金和设备等资源的使用，取得资料消耗的最优化，进而实现经济管理中的生产指标。通常来讲，线性规划是依据数学模型来进行问题的处理的，即先对管理的目标进行决策变量的选取，在通过函数的形式，进行决策变量的表达，这种表达可以称其为目标函数。而通过有关变量的等式对问题的条件进行表达，可称其为约束条件。在数学形式中，如果约束条件和目标函数成为线性时，数学模型也就会在线性规划中得到良好的构建。

二、物流中的运筹学

在现有的物流管理中，如空运、铁路、公路、水运等各种高效的运输工具都得到了广泛的应用，其不同运输方式之间的优化组合和合理配置也得到了有效的实现。而作为物流领域中的运筹学而言，它的应用也是相当的广泛，实际问题的解决效果也是非常的显著。

（一）物资存储

存储论在运筹学中又称库存论，它的研究方向主要是物资库存的策略，也就是高效率的进行补货频率和物资库存量的确定。在物流领域中，能够实现库存的合理，是生产顺利进行的一个重要体现，能够使得费用的支出和资金的占用得到有效的减少，并尽可能的缩短货物流通的周期，进而促使生产活动的加速和完善。作为物流的节点，如配送中心、工厂、仓库、物流中心等都存在着一些库存现象，而为了优化物流活动的利益和成本，可对存储理论进行合理的应用，来辅助决策问题的处理。此外，在进行决策问题的处理中，还可以应用相应的模型进行高效的求解活动，如随机型和确定型的存储模型。作为其中的确定型存储模型，其在实现的过程中也存在中许多不同的情况，如不能有缺货，并进行连续的补货；可以有缺货，并一次性完成补货等。而随机型存储模型也有非常多的实现状况，如一次性订货的离散型和连续型的随机存储模型。此外，通常所运用的库存补货策略也具有不同的实现状况：连续的进行检查，固定订货点和订货量的策略；固定最大库存和订货点的策略；周期性检查和综合库存的策略。在具体的实践中，往往会依据物资库存的特点，对补货策略和库存控制模型进行选用和结合，实现存储系统的一个合理构建，且具备合理的存储网络、合理的存储结构、合理的存储量。

（二）决策论

在人类的活动中，决策的存在是非常的普遍的，而物流中的决策，也是一项相对不易活动过程。它借助充分的资料，依据物流系统的实验、经验、数学分析、客观环境，在合理的决策方案中，进行决策方案的合理选择。例如租赁车辆、自建仓库、物资调运计划、生产计划以及投资计划等。对于物流中的决策问题而言，有的决策可以非常的简单，但有的决策就相对比较的复杂。而依据标准的不同，决策的类型也会存有很多的不同形式。具体来说，如果依照决策目标的多少，其可被划分为多目标决策和单目标决策。多目标决策就比较的复杂，如果要进行物流中心的建设，既要对设施的先进性进行合理的考虑，也要对投资的大小进行合理的考虑。对多目标决策来说，这些目标会有一定的冲突，而在进行决策冲突的过程中，就要综合全面的进行问题的考虑和处理。但对于单目标决策而言，它的执行就比较的简单，解决的方法也有很多种，例如动态规划、线性规划等。相对于两者而言，对多目标决策的解决则是决策论中的重点内容，进行这类问题时，可用的、行之有效的方法也是非常的众多，其中最主要的还是层次分析法，即结合定量和定性的一种方法。

三、结束语

对于运筹学来讲，它的科学性很高，其应用数量的方法，对有限的资源进行合理的研究和运用，以此实现决策和管理的综合性和最优化。我国国民经济的发展非常的迅速，运筹学的完善和应用也是非常的显著，并成为应用数学的重要分支。在具体的实施中，运筹学主要对生产和管理中的普遍问题进行提炼，并借助数学方法，实现问题的处理和解决。

参考文献：

动态规划投资问题范文3

关键词 背包问题;NP完全;动态规划

中图分类号 TP301 文献标识码 A

A Dynamic Programming Method for

Classified 0-1 Knapsack Problem

JIANG Ya-jun1, YI Xue-jun2

(1.Department of Computer and Communication Engineering, Hunan University of Science and Engineering, Yongzhou，

Hunan 425100 China; 2.College of Mathematics and Econometrics, Hunan University, Changsha,Hunan 410082 China)

Abstract This paper studied the classified 0-1 knapsack problem, and proposed a dynamic programming method. The complexity of the recursive process is O(nW), and the complexity of the traceback process is O(n), where n is the total number of goods and W is the bearing weight of the knapsack. The example shows that it is easy to find the optimal solution by the method.

Key words Knapsack Problem; NP-complete; Dynamic Programming

1 引 言

0-1背包问题属于NP完全问题，可以表述为：已知n个物品和一个承重量为W的背包，每个物品i的重量为wi，价值为vi（i=1,2,…,n），现要从这n个物品中选出若干件放入背包，使得装入背包物品的总重量不超过W，且总价值达到最大.0-1背包问题在信息安全、工程决策等领域中有着极为重要的应用［1-5］,对0-1背包问题扩展研究，如0-1二次背包问题［6］、多目标0-1背包问题［7］、0-1背包问题［8］等，有着十分重要的应用价值和学术意义.

本文将传统的0-1背包问题扩展为分组0-1背包问题，阐述了分组0-1背包问题的动态规划解决方案，为背包问题的应用拓展了新的思路.

2 分组0-1背包问题的数学模型

在分组0-1背包问题中，所有物品被分成若干组，在装入固定承重量的背包时，要求每组物品不能全部取完并且总价值最大.在选择装入背包的物品时，对每个物品只有两种选择，即装入背包或不装入背包.不能将物品装入背包多次，也不能只装入部分的物品.在这里假设所有物品的重量和背包的承重量都是正整数.分组0-1背包问题的数学模型描述为：

给定n个物品，分成r组，设为

{G11,…,G1s1,…,Gj1,…,Gjsj,…,Gr1,…,Grsr},

其中∑rj=1sj=n，r＞1，sj＞1（j=1,2,…,r）.各物品的重量和价值分别为：

{w11,…,w1s1,…,wj1,…,wjsj,…,wr1,…,wrsr},

{v11,…,v1s1,…,vj1,…,vjsj,…,vr1,…,vrsr},

其中wji＞0，vji＞0，i=1,…,sj，j=1,…,r.给定W＞0，求解n元0-1向量=(x11,…,x1s1,…,xj1,…,xjsj,…,xr1,…,xrsr)，使得当∑rj=1∑sji=1xjiwji≤W，∑sji=1xji＜sj时，∑rj=1∑sji=1xjivji达到最大.

3 动态规划法

为了用动态规划法求解分组0-1背包问题，可以用一个动态规划表M跟踪递推，行对应于每一个物品，列对应于背包的承重量， M(j)［i,k］代表第∑j－1l=1sl+i行第k列单元格的值，它表示当背包承重量为k时，从物品G11,…,G1s1,…,Gj1,…,Gji中选取但各组不全部取完装入到背包中的最大价值.表格的填充从上到下，从左到右.

定理1 当0≤k≤W, 0≤i≤sj，1≤j≤r时，设M(1)［0,k］=0，M(j)［i,0］=0；当2≤j≤r时，设M(j)［0,k］=M(j－1)［sj－1,k］，则分组0-1背包问题中最优子集的最大价值递推公式为：

1）若1≤i＜sj，则

经 济 数 学第 29卷第1期蒋亚军等：一种求解分组0-1背包问题的动态规划法

M(j)［i,k］=M(j)［i－1,k］,k＜wji,max {M(j)［i－1,k］,M(j)［i－1,k－wji］+vji}，k≥wji.(1）

2）若i=sj，则

M(j)［sj,k］=

M(j)［sj－1,k］,k＜wjsj,max {M(j)［l－1,k－∑sjτ=l+1wjτ］+∑sjτ=l+1vjτ,l=1,2,…,sj},k≥∑sji=1wji,max {M(j)［sj－1,k］,M(j)［sj－1,k－wjsj］+vjsj},wjsj≤k＜∑sji=1wji.（2）

证明 对于有序物品组{G11,…,G1s1,…,Gj1,…,Gjsj,…,Gr1,…,Grsr}中第l个物品，存在唯一(i,j)，使得l=s1+…+sj－1+i,这里1≤i≤sj，1≤j≤r.显然当1≤l≤s1时，即j=1时，直接令l=i.这里特别说明，当某组只有一个物品时，显然该组可以不作考虑，故这里假设sj＞1，j=1,2,…,r.

下面用归纳法来证明由递推公式给出的M(j)［i,k］满足相应的最大价值：

1）当l=1时(对应(i,j)=(1,1))，易知对于任意k，由公式（1）给出的M(1)［1,k］满足最大价值.

当l=2时(对应(i,j)=(2,1))，易知对于任意k，由公式（1）或公式(2) 给出的M(1)［2,k］满足最大价值.

2）假设1≤l≤m时（对应唯一(i,j)），对于任意k，由公式（1）或公式(2) 给出的M(j)［i,k］满足最大价值.

3）下面证明对于l=m+1时（对应唯一i′,j′），对于任意k，由公式（1）或公式（2）给出的M(j′)［i′,k］也满足最大价值.

分三种情形进行讨论：

（）m=s1+…+sj′－1+i′－1（这里1≤i′＜sj′）,

（）m=s1+…+sj′－2+sj′－1,

（）m=s1+…+sj′－1+sj′－1.

1）对于情形（）， 当l=m+1时（对应唯一i′,j′=i+1,j），因为i′＜sj′，第m+1个物品不是所在组最后一个，则该物品被取与否，该组都不会出现选满的情形.

当k＜wj′i′时，则第m+1个物品不能被取，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］满足最大价值，因而M(j′)［i′,k］=M(j′)［i′－1,k］.

当k≥wj′i′时，则第m+1个物品有可能被取或不取两种情形：当第m+1个物品不取时，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］满足最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k］；而当第m+1个物品被取时，由归纳假设M(j′)［i′－1,k－wj′i′］=M(j)［i,k－wj′i′］满足最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k－wj′i′］+vj′i′.综合前述两种情形有：M(j′)［i′,k］=max {M(j′)［i′－1,k］,M(j)［i′－1,k－wj′i′］+vj′i′}.

由上可知，当l=m+1（对应唯一i′,j′），且m=s1+…+sj′－1+i′－1时（这里1≤i′＜sj′）, 有

M(j′)［i′,k］=

M(j′)［i′－1,k］,k＜wj′i′max {M(j′)［i′－1,k］,k≥wj′i′M(j)［i′－1,k－wj′i′］+vj′i′}

2）对于情形（），当l=m+1（对应唯一(i′,j′)=(1,j+1)），因为sj′＞1，第m+1个物品是所在组第1个，则该物品被取与否，该组都不会被全部选满.

当k＜wj′1时，则第j′类中第1个物品不能被选择，由归纳假设M(j′)［1,k］=M(j′－1)［sj′－1,k］=M(j′)［0,k］.

当k≥w(j′)1时，则第j′类中第1个物品有可能被取或不取两种情形：当第1个物品不取时，由题设及归纳假设M(j′)［0,k］=M(j′－1)［sj′－1,k］满足最大价值，所以M(j′)［1,k］=M(j′－1)［sj′－1,k］；而当第1个物品被取时， 由题设及归纳假设M(j′)［0,k－wj′1］=M(j′－1)［sj′－1,k－wj′1］满足最大价值，所以M(j′)［1,k］=M(j′)［0,k－wj′1］+vj′1.综合前述两种情形有：M(j′)［1,k］=max {M(j′)［0,k］,M(j′)［0,k－w(j′)1］+v(j′)1}.

由上可知，当l=m+1（对应唯一(i′,j′)，且m=s1+…+sj′－2+sj′－1时，有

M(j′)［1,k］=M(j′)［0,k］,k＜wj′1;max {M(j′)［0,k］,

M(j′)［0,k－wj′1］+vj′1},k≥wj′1.

3）对于情形（），当l=m+1时（对应(i′,j′)=(sj′,j′)=(i+1,j)），这里i=sj－1，第m+1个物品是所在组最后1个.

当k＜wj′sj′时，则第m+1个物品不能被选择，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］满足最大价值，所以M(j′)［i′,k］=M(j′)［i′－1,k］.

当k≥∑sj′i=1wj′i时, 有sj′种情形：即当l=1,2,…,sj′时，第j′组中第l个物品不取,而之后的物品都取.由归纳假设M(j′)［l－1,k－∑sj′l=l+1wj′l］满足最大价值，所以

M(j′)［sj′,k］=max {M(j′)［l－1,k－∑sj′τ=l+1wj′τ］

+∑sj′τ=l+1vj′τ,l=1,2,…,sj′}.

当wj′sj′≤k＜∑sj′i=1wj′i时, 此时第m+1个物品有可能被取或不取两种情形:当第m+1个物品不取时，由归纳假设M(j′)［i′－1,k］=M(j)［i,k］满足最大价值，所以M(j′)［i′,k］=M(j′)［sj′,k］=M(j′)［i′－1,k］=M(j′)［sj′－1,k］；而当第m+1个物品被取时，由归纳假设M(j′)［sj′-1,k-wj′sj′］满足最大价值，所以M(j′)［sj′,k］=M(j′)［sj′-1,k-wj′sj′］+v(j′)sj′.综合前述两种情形有

M(j′)［sj,k］=max{M(j′)［sj′-1,k］,

M(j′)［sj,j′-1,k-wj′sj′］+vj′sj′}.

由式（1）、式（2）和式（3）可知，当l=m+1（对应唯一i′,j′），且m=s1+…+sj′－1+sj′－1 时，有

M(j′)［sj′,k］=

M(j′)［sj′－1,k］,k＜wjsj′,max {M(j′)［l－1,k－∑sj′τ=l+1wj′τ］+∑sj′τ=l+1vj′τ,l=1,2,…,sj},k≥∑sj′i=1wj′i,max {M(j′)［sj′－1,k］,M(j′)［s(j′)－1,k－wj′sj′］+vj′sj′},wj′sj′≤k＜∑sji=1wj′i.

由1）、2）和3）可知，对于（）、（）和（）三种情形证明了对于l=m+1（对应唯一(i′,j′)），由递推公式（1）或（2）给出的M(j′)［i′,k］满足最大价值要求.

因而对于任意1≤l≤n（对应的(i,)）和任意k，由递推公式（1）或（2）给出的M(j)［i,k］为对应的最大价值.证毕.

为了通过动态规划表M求取最优子集，定义一个回溯表F来跟踪上述递推过程，行对应于每一个物品，列对应于背包的承重量.令

F(j)［i,k］=

0,M(j)［i,k］=M(j)［i－1,k－wji］+vji;sj－t,M(j)［sj,k］=M(j)［t,k－∑sjτ=t+2wjτ)］+∑sjτ=t+2vjτ, t=0,1,…,sj－2;1M(j)［i,k］=M(j)［i－1,k］.（3）

回溯过程从动态规划表M的最后一项M(r)［sr,T′］直到M(1)［0,0］，回溯方法描述为：

1）若F(j)［i,k］=0，则回溯至M(j)［i－1,k－wji］，此时令xji=1；

2）若F(j)［i,k］=1，则回溯至M(j)［i－1,k］，此时令xji=0；

3）若F(j)［i,k］=sj－t＞1，则回溯至M(j)［i－(sj－t),k－∑sjτ=t+2wjτ)］，此时令xjt+2=xjt+3=…=xjsj=1，xjt+1=0.

4 计算实例

给定三组物品{G11,G12,G13,G21,G22,G23,G31,G32}，它们的重量和价值如表1所述，设背包的承重量W=6.则根据公式（1）和（2）可计算出动态规划表M，如表2如述.根据公式（3）可计算出回溯表F，如表3如述.由表2和表3，回溯可以得到=(x11,x12,x13,x21,x22,x23,x31,x32)=(1,0,1,0,1,1,0,1).故最优子集为{G11,G13,G22,G23,G32}，最大价值为33元.

5 结 论

本文研究了分组0-1背包问题，并提出了解决分组0-1背包问题的动态规划解决方法，在物品总数为n个和背包承重量为W时，生成动态规划表M的复杂度为O(nW)，生成回溯表F的复杂度为O(n).该方法思路简单，容易理解，计算实例验证了利用该方法易于找到最优解.

参考文献

［1］ B Chor, R Rivest. A knapsack-type public key cryptosystem based on arithmetic in finite fields［J］.IEEE Transactions on Information Theory,1988,34(5):901-909.

［2］ C Laih, J Lee, L Harn, et al. Linearly shift knapsack public-key cryptosystem［J］.IEEE Journal of Selected Areas Communication,19,7(4):534-539.

［3］ D Yao, K Frikken, M Atallah, et al. Private information:to reveal or not to reveal［J］. ACM Transactions on Information and Systems Security, 2008, 12(1):1-27.

［4］ 张生, 魏忠华, 何尚录等. 0-1背包问题在限额投资决策中的应用及其扰动分析［J］.内蒙古师范大学学报:自然科学汉文版,2007,36(5):595-598.

［5］ 张琳, 胡正华, 黄河. 基于背包问题的散货航次方案优选方法研究［J］.价值工程,2011,20(5):221-222.

［6］ 谢涛, 陈火旺, 康立山. 二次背包问题的一种快速解法［J］. 计算机学报,2004,27(9):1162-1169.

动态规划投资问题范文4

【关键词】动态成本控制；技改项目；成本差异分析；财务评价

一、技改项目与新建项目的区别

PMI将项目定义为：为了提供某种特定的产业与服务而进行的临时性的努力与试验。其中“临时性”是指每个项目是有其阶段性的，它们都具有固定的开始以及结束的时间。而“特定的产业与服务”是指其并且区别于其他一般的项目。因此，企业的技改工程项目是企业为了提高其产能，减低能耗，通过可行性分析以及自身的定位，为获得特定的产业与服务而展开的临时性的尝试。

企业的技改项目除了具有与一般的新建项目所具有的共性之外，具有不同于一般新建项目的独特性，例如费用上的节约，建设期的缩短，手续上的减少，在一定时期内能够尽快达到效益以及投资目标。

二、将动态成本控制方法与技改项目的独特性相结合

基于1955年由经济学家筱原三代平提出的“动态比较成本说”中可以得到动态成本区别于历史成本，严格上来说，动态成本应该定义为一种即刻可以进行重置的成本，也就是随着市场环境的变化而动态变化的，按当前市场的材料实际价格与当前的工费成本核定的非静态不变的成本。而技改项目作为一种需要通过投资而得到收益的临时性活动，需要企业采用更为科学的评价评估方法进行全方位决策，特别是贯通于技术改造项目的全寿命周期中的连贯性控制，而对于成本进行动态控制是全寿命周期项目管理需要应用的重要方式，也是全寿命周期项目进行整体优化的核心内容。动态成本控制流程能够大致地反映各个项目的动态成本控制的情况，其包括：

1.目的。指导技改项目工程开发成本控制，明确技改醒目成本控制目标，建立成本控制预警机制，降低成本经营风险。

2.术语与定义。动态成本：指项目在实施过程中体现的预期成本的结果。

3.职责。明确成本管理总部、技术管理总部、招标采购总部、各总监的成本控制职责。

4.工作流程。首先进行技改项目工程目标成本的制定，然后再对全寿命周期的技改项目工程成本进行动态成本控制，最后再进行项目工程目标成本调整。

三、成本差异模型的基本思想

成本差异是在实际成本与标准成本进行对比的过程中产生的，而成本差异分析是将实际成本与预先确定的标准成本进行比较，接着对于两者是否存在差异进行分析，机动地通过成本差异分析寻找出实际成本与标准成本产生差异的直接原因并及时进行改正，对于成本的差异进行分析，能够为成本改善和控制指明方向，有效地降低企业生产运行成本，提高企业在本行业内的核心竞争力。

1.制定标准成本。标准成本是根据企业的标准耗费和标准价格制定的。

2.及时收集施工企业的实际成本信息，例如月季度成本报表、周成本报表等。分析比较标准成本与实际成本产生差异的具体数额，得出直接成本差异值。

3.由此基础而对导致差异的成本因素进行差异分析调

查，找出产生差异的根本原因。

4.明确差异产生的责任，采取行之有效的措施，对成本差异进行改正。下图所示为成本差异分析的具体过程：

四、基于贝叶斯网络和动态规划在成本差异模型中的运用

针对技改工程项目成本差异分析，由于其目前的分析方法简单，需要考虑的因素较少，一般设定在技改项目全寿命周期中很多影响因素是固定数值，其是稳定不变的；并将其当作一个静态的过程，其变量因素之间是、互相没有影响的，没有涉及其中的互相影响及反馈作用。

通过分析以后沿用系统动力学方法，可以对技改项目全寿命周期的安全、环保许可，土地规划，设计审核，工程配套，设备采购，合同谈判，施工管理，开车等一系列，以全局的系统视野对技改项目进行研究调查和分析比较，基于贝叶斯网络和动态规划以建立技改项目处理项目成本差异模型。

贝叶斯网络：贝叶斯网络是基于后验概率贝叶斯定理而形成的，其以数理统计的方式处理已知数据为基础的方法。贝叶斯网络将不确定的事件连接起来，用以预估与其他影响关联的事件，其在这样的过程中，充分发挥了贝叶斯网络的分类、聚类、预测和因果关联关系分析的功能，为决策者带来指导意见，并且通俗易懂，在预测功能中得到广泛运用，但是贝叶斯网络也具有其一定的弱点例如在预测频率很低的概率事件中所起的作用不够理想。

贝叶斯预测运行如图所示：

动态规划：一般情况下将动态规划的基本原理归于一个常态的递推的关系表达式，将其用于描述多个阶段的决策过程的状态转移。经常使用的方法为逆序法或者顺序求法来解决这类问题，也就是以最终状态为出发点，由后向前逐步推导到初始的状态，由此而得到一个最优的决策序列。

动态规划与其他的优化技术相比较可以发现其能够得到一个整体的多阶段的最优解。由于时间参数在决策过程中呈现为可连续或者离散特征，所以决策过程可据此分为可连续决策过程以及离散性决策过程。从另个方向来考虑，根据决策的演变过程是确定性的或者是随机性的可以具体划分为确定性决策过程和随机性决策过程。综合以上分析，决策过程模型分为离散确定性、离散随机性、连续确定性、连续随机性共四种不同的决策过程模型。

将成本差异控制方法运用于技术改造项目的动态成本控制的过程之中，其数据采集过程较其他方法来说更为繁琐，当n∞时决策人员进行成本控制时会发现由于数据处理却缺乏相应的计算机计算程序的模块，而使得这种决策的过程更为困难。但此种方法有其可取的地方，比如可以在特定的时间点为成本管理以及项目决策人员提供良好的宜于进行解决成本差异调查决策的量化模型和固定思维。

通过将成本差异动态控制模型与成本自身的特点以及项目管理人员的经验做法相结合，决策人可以高效地将该决策做到合理的范围。

参 考 文 献

[1]许珂.基于贝叶斯和动态规划的成本差异控制模型及应用研究

[D].天津：天津大学.2011

动态规划投资问题范文5

[关键词]投资组合模型均值—方差随机规划

一、引言

由于投资收益和风险的不确定性，个体投资者和金融机构面临的核心问题就是如何在不确定的环境下对资产进行有效的配置，实现资产回报的最大化与所承担风险最小化的均衡，即如何进行投资组合的选择。美国经济学家HarryM.Markowitz于1952年发表题为《资产组合》的文章与1959年出版同名专著，详细阐述了“资产组合”的基本假设、理论基础与一般原则，标志着数量化方法进入了投资研究领域。经过50多年的发展，投资组合理论的研究取得了很大的进展。

二、投资组合选择相关概念

1.投资组合

对投资组合概念的理解可以从物质和行为两个层次进行，首先，从物质层面上看，投资组合一般指投资者有意识的将资金分散投放于多种投资项目而形成的投资项目或资产的群组；其次从行为层面上看，投资组合是指配置各种资产以符合投资者对风险和收益等需求的过程。

；二是在风险给定的条件下，使得期望收益率最大化。有效投资组合可以构成资产的有效边界，或者称为有效前沿。

2.投资组合选择

投资组合选择的概念与投资组合和有效投资组合的概念密切相关，是指研究如何把财富分配到不同的资产中，以达到在给定风险水平下最大化收益，或者在收益一定的情况下最小化风险的过程。这种投资风险与收益的权衡贯穿于投资活动的始终，是投资决策与管理的基本问题之一。

三、投资组合选择模型

1.均值—方差模型

20世纪50年代，Markowitz从投资者如何通过多样化投资来降低风险这一角度出发，提出了“均值—方差”模型，创立了投资组合理论。均值—方差模型依赖的假设条件主要有:(1)证券市场是完全有效的;(2)证券投资者都是理性的;(3)证券的收益率性质由均值和方差来描述;(4)证券的收益率服从正态分布;(5)各种证券的收益率的相关性可用收益率的协方差表示;(6)每种资产都是无限可分的;(7)税收及交易成本等忽略不计。在此前提下，投资者从众多资产组合均值—方差集中寻求帕累托最优解。但均值—方差模型与效用理论只有当投资者的效用函数是二次的或者收益满足正态分布的条件时，才能完全符合，而这样的条件在实际中常常难以满足，因此均值—方差模型在实际应用中受到了较多的。

2.单指数模型

1963年Sharpe提出了单指数模型，用对角线模式来简化方差—协方差矩阵中的非对角元素，假设各个证券是的且其收益率仅与市场因素有关，如证券市场指数、国民生产总值、物价指数等，即证券收益率可由单一的外在指数决定，从而大大地简化了模型的分析与计算工作量，解决了均值—方差模型在实际应用过程中的计算困难。

3.MM理论

Modigliani和Miller在研究企业资本结构和企业价值之间的关系时，提出了无套利均衡思想，即所谓的MM理论。无套利分析方法是当今金融工程面向产品设计、开发和实施的基本分析方法，并成为现代金融学研究的基本方法.

4.均值—绝对偏差模型

Konno和Yamazaki运用绝对偏差风险函数代替了Markowitz模型中的方差作为风险度量的函数，建立了均值—绝对偏差投资组合选择模型，通过求解一个线性规划问题来达到均值—方差模型的目标，从而既能保持均值—方差模型中好的性质，又避免了求解过程中的计算困难。

四、动态投资组合选择模型

从上述投资组合选择模型的发展中，可以看出理论界对于投资组合中收益与风险的认识与度量不断加深。但这些模型对于投资组合选择问题的考量都是基于静态或单阶段的，然而在实践中，投资行为却往往是动态的和长期的。。

随机规划是在不确定条件下解决决策问题的有力分析方法，针对随机规划中对随机变量的不同处理方案，随机规划可以分为三类：第一种也是最常见的一种方法，取随机变量所对应函数的数学期望，从而把随机规划转化为一个确定的数学规划，这种在期望值约束下，使目标函数的期望达到最优的模型通常称为期望值模型；第二种由Charnes和Cooper提出，主要针对约束条件中含有随机变量，且必须在观测到随机变量的实现之前作出决策的问题，其解决办法是允许所作决策在一定程度上不满足约束条件，但该决策应使约束条件成立的概率不小于某一置信水平；第三种由Liu提出，其主要思想是使事件实现的概率在不确定环境下达到最大化的优化问题。

Mossin于1968年首先提出多阶段投资组合问题，用动态规划的方法将单阶段模型推广到多阶段的情况，但由于不能直接用动态规划方法求解，始终未能得到象单阶段一样形式的解析解，直到Li等在2000年用嵌入的思想方法得到了多阶段均值—方差投资组合选择问题的解析最优有效策略和有效前沿的解析表达式。

近年来，随着计算技术和信息技术的发展，随机规划的方法在动态投资组合选择的研究和实践中取得了很多成果。如：Kallberg、White和Ziemba提出了投资组合选择随机规划模型的一般理念；Kusy和Ziemba将随机规划模型应用于银行的资产负债管理；Kouwenberg介绍了用于资产负债管理的随机规划的一般模型及相应的情景生成方法；FrankRussell公司和Yasuda保险公司开发的多阶段随机规划模型，以多重周期的方式确定最优化投资策略，并将其运用于财产与意外保险领域；TowersPerrin公司开发了CAP:Link系统以帮助其客户了解涉及资本市场投资的风险与机会等。

随机规划模型通过构造代表不确定性因素未来变动情况的情景树，作为状态输入，将决策者对不确定性的预期加入到模型中，可以将诸多市场与环境因素加入多阶段投资组合选择模型中，具有很大的灵活性和很强的应用性。但随机规划模型由于其求解的难度会随模型考虑的范围和考虑的阶段数的增加而急剧增加，因此对算法的依赖程度较大。

随机规划投资组合选择模型是建立在对利率、通货膨胀率、投资收益率等随机变量的参数化基础上，建立模型，找出最佳的投资组合，其步骤为:(1)生成未来经济元素，包括利率、股市、债券等证券市场收益率、通货膨胀率等;(2)根据研究对象的特征，研究其现金流量;(3)选择目标函数和约束条件，建立随机规划模型；(4)将步骤(1)、(2)中产生的随机参数值载入模型求解，解释其涵义并加以改进;(5)对投资组合进行决策。

参考文献：

[1]H.Markowitz,Portfolioselection.journalofFinance,1952.7:p.77～91

[2]H.Markowitz,PortfolioSelection:EfficientDiversificationofInvestment.JohnWiley&Sons,NewYork,1959

动态规划投资问题范文6

关键词：期权理论；电力投资 ；应用

在电力企业逐渐发展的过程中，电力投资也愈发的重要，但是由于电力投资的基本密集行和分散性，电力市场发展的不稳定性，都给电力投资带来了极大的风险。因此，必须全面的对电力的市场环境进行分析，能依据实际情况建立投资项目的实物期权模型，最大程度的计算出投资的最大价值，能有效的规划时间，规避投资上的风险，确保能做出最科学最合理的电力投资。本文就是要就电力市场环境下的金融期权理论在电力投资中的缺陷及作用进行分析，病对多元化的期权理论在电力投资中的应用进行探讨。

一、 电力投资中的期权理论的概况

1.金融期权

期权作为金融行业发展所衍生的一种选择的权利，是赋予相应的所有者可以在规定的时间内，以约定好的价格买入或卖出一定基础资产的权利，而在期权合约中出售或购买资产的价格为期权的执行价格，而期权的规定时间为期权合约的期限。期权的购买者付给了出售者一定的资金将期权买定后，就有买入或卖出基本资产的权利，购买者根据自身的实际情况考虑是否行使期权的义务。期权又分为买入时的看涨期和卖出期的看跌期，在看涨期，持有者享有购买某资产的权利，而看跌期也相对的享有出售的权利，在我们现今的交易中大多是在期权合约到期的任何时间都能行使其权利。

而期权基本包括股票、债券等几项，在股票方面，投资者认为哪支股票呈现看涨状态，就会以一定的价格购买，而在期权的合约到期的时间，如果该股票涨了，就可以执行期权，就可以以更高的价格出售从而获得利润，而在期权的期限内，股票跌了，就能不执行期权，这样在期权期间，股票的上涨能最大程度的增加利润，而在下跌时又能使得损失固定在一定的区域内，这样通过期权，在不同的电力市场环境下，能切实的扩大投资利润，又能有效的规避风险。

2.实物期权

所谓的实物期权就是实物项目期权与金融期权的结合，且与金融期权的概念是一致的，在电力投资的过程中，投资者可以根据电力市场的实际情况灵活的做出选择。在市场预期比较好的时候扩大投资，相反就相应的减少投资。实物期权能保证投资者在进行电力投资的过程中利用期权有效的利用，最大程度的保证其收益，又能规避风险，将损失锁定在相应的范围内，真正的在投资中实现期权灵活性的价值。

二、 期权理论在电力投资中的应用

1.实物期权方法应用

期权理论在电力投资中的应用，首先是实物期权方法。NPV法存在很多不足，例如管理的灵活性较差，并且具有很多不确定因素，这样在电力投资中存在很大的风险，因此在具体项目投资决策中，形成了实物期权方法。这种方法的主要内容是当投资者拥有了通过实物进行投资的机会，但是投资的强制性差，投资是一种权利，非义务，因为投资直接关系到投资者的期权，决策结果也是关系到执行是否具有效力。

2.实物期权的投资的具体程序

首先，要构建实物期权的具体应用程序框架，并且重点分析影响投资决策的不同要素，根据风险等级来区分投资要素中所包含的其他的实物期权，重点分析其差异性与不确定性，最大程度保证投资的安全，通过数学统计进行指标分析与数据描述，构建数学模型，针对电力投资决策体系来进行相关性探究。

其次，要选择合适的实物期权定价模型，通过数据的采集与整理分析，确定期权的定价模式，将数据带入到模型中来分析投资的相关因素。

再次，利用通过实物期权方法统计得出的定价结果来进行风险评测，在具体的策略设计、投资规划上充分考虑，从多个视角进行分析，整个应用过程中一旦出现误差，及时进行纠正，保证实物期权法结果的科学性与准确性。

最后，检查上一步的过程，并且考察是否需要扩大投资选项的组合、是否需要重新构造投资策略等。

3.动态规划方法应用

期权理论在电力投资的应用中，动态规划也是实践中比较常见的一种方法，其重点在于解决当下收益问题，结合发展情况进行决策，选择最优方案。动态规划法要求要统计出在固定期限内，资产取得效益可能性，并且选择最优决策，通过综合性分析，统计出结果价值。 动态规划法是解决期权定价问题中非常高效的方法之一，它能够处理复杂的决策结构、期权价值同标的资产价值之间的复杂关系，针对含有复杂的价值漏损也能够进行分析统计。在所有利用动态规划方法计算期权价值的方法中，最常用的方法为二叉树期权定价模型法，它假定在每个小的时间步长，标的资产价格面临上涨或下跌两种可能，从而标的资产价格运动的可能路径形成一个二叉树图。

展望未来电力市场的发展前景，可以加个金融输电权交易引入到市场建设中，激励电网扩展，将输电网扩展工作相对应的资金融授予新输电网络投资人员，将此作为补偿，为输电网络发展开拓视野。前些年的输电网投资工作都是通过收取电费的方式来回收，输电的基本定价取决于输电网的投资成本以及。但是因为存在垄断的情况，所以电力系统发展协调性比较差，如果单纯依靠电网公司进行计划，很难保证市场运行效率。将输电价格作为电网投资的激励方式是不能有效控制输电成本的。因为输电网络的扩张会增加金融输电权，但是市场运行机构也可以将新输电权分配到输电网投资者手中，通过金融输电权来补偿电网建设成本，控制投资的风险性。在新的工作模式下，投资人员必须根据电权信号来完善投资决策，对电网进行优化与补充。通过吸引新的电网投资者，用户不再完全被动的承担原有电网公司强制的输电费用，提高输电环节的竞争程度和运行效率。

结束语

作为一种规避阻塞风险的金融工具，金融输电权赋予其持有者获得指定电能注入节点和流出节点之间节点电价价差所对应收益（或支出）的权利。随着我国电力行业的不断发展，为了适应市场经济的，国家逐步放开一些经济性，允许金融类工具应用其中，期权理论在电力投资上的应用便是比较典型的一种形式。本文详细分析了电力市场环境下发输电投资的现状，并概况介绍了期权理论在输电以及发电投资中的一些应用。笔者通过实物期权方法应用于发电投资决策，获取最佳投资时间，提高了电力投资的灵活性，充分体现了电力投资中面对不确定因素的能动性。最大程度避免传统的发电投资存在的弊端，进而做出更合理的电力投资决策。

参考文献：

[1] 蒋贤锋.跳跃扩散过程下的实物期权及在电力投资中的应用[D].东北财经大学，2013，06.

[2] 包伟.期权理论在电力投资中的应用研究[D].湖南大学，2012，03.

[3] 吴先.华实物期权理论在风险投资决策中的应用研究[D].武汉理工大学，2013，12.