时间：2023-02-21 17:08:15
开篇：写作不仅是一种记录，更是一种创造，它让我们能够捕捉那些稍纵即逝的灵感，将它们永久地定格在纸上。下面是小编精心整理的12篇动态规划，希望这些内容能成为您创作过程中的良师益友，陪伴您不断探索和进步。
关键词：动态规划；编程；技巧
中图分类号：J954 文献标识码：A 文章编号：1007-9599 （2012） 16-0000-02
首先，第一类动态规划的题目。这类问题往往直接采用递推的方式从前往后一步步记录下每一步的结果，最后得出问题的解就可以了。我们来看一个例子：
“数字三角形问题”。问题的大意是：给定一个由n行数字组成的数字三角形，如下面所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
5（行数）
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
这道题很明显要用动态规划算法求解。假设我们要求第i行的最大值，怎么求呢？可能有的人会找每一行最大的数，但这样是行不通的，因为我们要找到一条路径，也就是上一行与下一行选的数必须不能隔数字。那怎么办呢？我们如果要找第i行的最大值，可以从第i-1行来找。对于第i行的每一个数字，通过选第i-1行中符合题目要求的数字，求出到该数的路径的最大值。我们最后求出的第n行的最大值中求出最大的即可。
附上代码（c语言）：
#include
int main（）
{
int n，i，j，max；
int num[120][120]；
int sum[120][120]；
scanf（"%d"，&n）；
for（i=1；i
{
for（j=1；j
{
scanf（"%d"，&num[i][j]）；
}
}
sum[1][1]=num[1][1]；
for（i=2；i
{
for（j=1；j
{
if（j==1）
{
sum[i][j]=sum[i-1][j]+num[i][j]；
}
else if（j==i）
{
sum[i][j]=sum[i-1][j-1]+num[i][j]；
}
else
{
if（sum[i-1][j-1]>sum[i-1][j]）
{
sum[i][j]=sum[i-1][j-1]+num[i][j]；
}
else
{
sum[i][j]=sum[i-1][j]+num[i][j]；
}
}
}
}
max=0；
for（i=1；i
{
if（sum[n][i]>max）
{
max=sum[n][i]；
}
}
printf（"%d＼n"，max）；
return 0；
}
其次，第二类动态规划算法。这类动态规划算法往往不像第一种那么直接往后递推就可以了。这类问题往往要借助于前面求解过的子问题，而且不一定是刚刚求解过的子问题。其实这类问题有点分治法的意思，但是可以记录下已经求解过的子问题的结果，不必再在后面的问题中求解一遍。我们来看一个典型的例子——“0-1背包问题”：
题目大意是，有一个背包容量为v，还有若干个宝物，第i个宝物的价值为v[i]，容量为w[i]。试设计一个算法，在背包容量范围内，把总价值最大的宝物总和加入到背包内。数据输入实例：
4（宝物个数） 6（背包容量）
1 4 （第一个宝物的容量和价值，下同）
2 6
3 12
2 7
这个问题怎么分析呢？我们假设已经装到第i个宝物了，容量为m时最大价值为f[m]。那么这时最大的价值为多少呢？如果第i个宝物装到了背包中，那么这时价值为f[m—w[i]]+v[i]，如果不装呢，价值仍为f[m]。取其中最大值。这里求数组f的各个元素时，我们可能需要前面求过的子问题。
附上代码（c语言）：
#include
int main（）
{
int dp[13000]，n，m；
int w[3500]，d[3500]，i，j；
scanf（"%d%d"，&n，&m）；
for（i=1；i
{
scanf（"%d%d"，&w[i]，&d[i]）；
}
memset（dp，0，sizeof（dp））；
for（i=1；i
{
for（j=m；j>=w[i]；j--）
{
if（dp[j]
{
dp[j]=dp[j-w[i]]+d[i]；
}
}
}
printf（"%d＼n"，dp[m]）；
return 0；
}
最后，我们来看第3类动态规划问题。这类动态规划牵涉到了数据结构的内容，对我们这部分的学习以及抽象出算法模型的能力有比较大的要求。我们必须先对这部分的数据结构有自己的理解和体会，然后才能用算法的知识求解这类问题。我们来看一个问题：
“加分2叉树”。 设一个n个节点的二叉树tree的中序遍历为（l，2，3，…，n），其中数字1，2，3，…，n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1，2，3，…，n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历
【输入格式】
多组测试数组，对于每组：
第1行：一个整数n（n
第2行：n个用空格隔开的整数，为每个节点的分数（分数
【输出格式】
第1行：一个整数，为最高加分（结果不会超过4，000，000，000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。
【输入样例】
5
5 7 1 2 10
【输出样例】
145
3 1 2 4 5
这个问题就用到了2叉树的知识。我们首先得对树有一定的了解，必须了解树的各种遍历方式，先序遍历，中序遍历，后序遍历。
先序遍历，也叫先根遍历，遍历的顺序是，根，左子树，右子树
中序遍历，也叫中根遍历，遍历的顺序是，左子树，根，右子树
后序遍历，也叫后跟遍历，遍历的顺序是，左子树，右子树，根
然后我们来分析这道题。
设节点d为最优的根节点，那么可以把这棵树分成[1，d-1]和[d+1，n]，这颗树的加分为子树[1，d-1]的加分与子树[d+1，n]加分的乘积与d的加分的和，而[1，d-1]和[d+1，n]的加分也可也一定是最优加分，所以这个题具有最优子结构，那么可以用动态规划。
设f[k，j]为子树k到j的最高加分，求f[k，j]的最优值，就要求f[1，d-1]和f[d+1，n]的最优加分，那么枚举根节点p，则有
f[k，j]的最优值=f[k，p-1]*f[p+1，j]+v[p]（k
规划方程为f[k，j]=max{f[k，p-1]*f[p+1，j]+v[p]}（k
[关键词] 个体投资 理财 动态规划
一、序言
随着经济体制特别是投资体制的深化，我国的投资主体结构发生了重大变化，其主要表现之一就是个人投资的崛起。随着个人收入的不断增长以及社会各种不确定因素的不断增多，如何合理的处理和运用钱财，让自己的投资发挥最大的效用，获得最大收益，成为摆在我们面前的现实问题。本文中，根据股票、基金、储蓄三种理财方式的收益和风险的关系，对收入的可支配部分进行投资理财优化。
二、模型假设
1.投资市场在一定程度上是有效的，即投资者对投资的预期收益和风险可以进行估量。
2.投资者的目的是实现风险与收益的最佳组合。
3.在风险投资决策中，不同的项目可以用预期的获利g和需要承担的风险q来表示，
则投资者可以对这些不同的项目赋以一个相应的效用值Z，这就构成效用函数。
4.假设这n个投资项目用表示。
三、模型建立
假定个人总投资额为a万元，拟投资于n个项目上，已知对第i个项目投资万元，收益函数为,风险系数为。问应如何分配资金才可以使总效益最大而风险较小？
按问题的变量个数划分阶段，k=1,2,3,4,5.设状态变量为并记，取问题中的变量,为决策变量。状态转移方程为。
其动态规划基本方程为
四、实例分析
根据2006年开放式基金年度收益调查表，储蓄投资收益公式以及两只股票的理论收益表作出表：
表 五个项目的预期收益 单位:万元
则投资收益为:
根据以上数据，假设个人可支配资金为6万元，现投资理财方式有储蓄E,购买股票B,C,开放式基金A,D,分别用表示，对于理财来说最终目的是收入增加而风险较小。试找出一种最佳投资方案。
1.用连续型动态规划求解
把表中的数据通过matlab软件将以上数据拟合，得到投资资金与投资收益的关系：
对于基金A、股票B、股票C、基金D来说，、
、
、
状态转移方程为
允许决策集合为
各阶段指标函数为
其动态规划基本方程为
状态转移方程为
用逆序算法求解得：
所以最优解为:
2.用离散型动态规划求解
设限定在6万元的有限集合里，将它离散成有限个点，单位是万元。
设状态变量为并记，取问题中的变量为决策变量。
状态转移方程为
其动态规划基本方程为：
求得结果为：如果向这五种项目投资6万元，则应向基金A投资2万元，不向股票B与储蓄E投资，向股票C投资2万元，向基金D投资2万元，这样才能以相对较小的风险获得较大的收益9.7136万元。
参考文献:
[1]沈继江主编:数学建模[M].哈尔滨:哈尔滨工程大学出版社,2000,3:136～140
[2]杨大谐:谈个人证券投资[J].哈尔滨金融高等专科学校,1997年第2期:25～28
[3]李聪:基于概率模型的证券投资决策支持[J].文章编号:1000-5188（2003）01～0077～0006
[4]方运生:多目标规划最优投资组合方法[J].文章编号:1008～7710（2003）03～0004～03
煤矿企业的生产工程性极强，生产过程总所遇到的问题众多，所以导致采矿过程中的许多问题只能凭借实践的经验来进行组织和安排。随着煤矿企业开采深度的不断增加，矿井的地质以及企业的生产条件也逐渐复杂，对于采矿的难度以及生产成本也不断增大，因此导致煤矿开采生产过程中遇到众多的现实问题，如煤炭市场逆转，价格下降、需求下滑、库从增加，以及许多如交通受阻的外在因素的影响，这对煤炭企业影响很大，经常使得煤矿企业的经营雪上加霜。近年来，随着运筹学在企业生产管理中的应用日益发展，动态规划在煤矿开采方面的应用，提高了煤矿开采的安全性、高效性，给煤矿开采技术的发展带来崭新的局面。
一、采矿企业问题的提出
假设某采矿企业调查研究了解市场情况，估计在今后四个时期市场对动力煤的需求量，如表所示：
假定煤矿企业在所有时期，开采每批动力煤的固定成本费为3千元人民币，若不开采，则费用为0，每单位生产成本费为1千元人民币，同时在每个阶段时期企业的开采能力为最大开采批量不超过6个单位。又设每个阶段的每个单位动力煤的库存费用500元人民币，同时规定在第一期期初及第四期期末均没有库存煤。在以上的条件下采矿企业需要合理的安排企业的开采量和库存量，从而使企业所花费的成本最低。
二、动态规划法的发展及其研究内容
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。
三、模型的建立
第一，建立模型Ⅰ。在采矿企业提出生产与存贮问题时，忽略生产准备费用，首先考虑到生产、需求与库存之间存在着的平衡关系，这是一个一般的线性规划问题，可假设生产量为 1x， 2x，
关键词:生态节能;生态住宅投资;动态规划模型;评价指标
中图分类号:TU982文献标识码:A
文章编号:1009-2374(2010)21-0111-02
随着我国社会、经济的发展,人们对居住环境及住宅建筑的规划设计提出了各种新的要求,已从过去仅作栖息之所演变为生活、休息、交往、娱乐、学习、工作等多功能的场所和建筑,于是大量节能建筑及绿色建筑成为最新技术的载体,且当与我国当今的节约型社会发展政策相符,并根据当代的使用需求对建筑设计进行生态节能优化投资。因此就需要在前期投资做好最优规划,以达到最大的收益。本文针对现状建立了动态规划模型,可求得符合要求最切合实际的住宅投资收益。
1生态节能住宅设计的提出
1.1城市建设现状
一幢幢高楼拔地而起,一座座大桥横跨两江。然而,随着城市化建设的提速,一些功利性的开发正肆意破坏着与城市相濡以沫的自然地貌,那些毫无建筑特色的水泥森林更让我们这座城市开始变得面目全非。为了最大限度的避免在城市建设中给后人留下遗憾,充分展现各个城市独有的自然风貌,让人、城市和自然和谐发展,和谐相处,针对各个城市的现有资源优势,从人文关怀、乡土历史和自然生态的保护利用、休闲娱乐、节约资源等多个方面提出了合理、详细的集交通功能与休闲和生态保护相协调的绿色节能建筑投资规划方案。
在我国有限的资源条件下解决建筑开发与社会、生态环境之间的最优适应和协调发展问题,在错综复杂的多元化可变因素条件下,找到满意的设计方案。根据现代设计法的理论与工程实践经验,建立科学的、全面的动态规划是最关键的环节,它贯穿于系统分析、设计的全过程中,最终选出最优投资方案。
1.2影响住宅投资的主要因素
1998年住房制度改革使人们的住房消费观念发生了根本改变,从而带动房地产业及整个经济发展。随着经济发展和人们生活水平的提高,我国住房正在从生存型向舒适型转变。人们从当初只是购买住房,逐步发展到间接地购买周围的环境,包括绿色、蓝天、空气、阳光等自然环境及基础设施、购物、交通、文化、教育、物业管理等社会和人文环境。而收入差距的拉大又形成了具有不同消费能力的阶层分化,我国住房消费市场细分化趋势更加明显。工薪阶层较注重住房建筑质量、户型、地段、交通、物业管理等;事业成功人士及高收入阶层开始追逐环境质量、居住、生活品位及个性化等。因此,住宅市场细分为住宅建设结构调整和消费增加提供了空间。
城市规划调整,城市规模扩大,城市交通等市政基础设施建设加快直接促进住宅建设快速发展。在这一点上,北京最具有代表性。交通状况一直是影响房地产开发的一个很重要的因素。而且,政府扶持为住宅投资和市场发展提供了政策保障。
住宅投资主要取决于市场综合评价运行指标,其次也受人口数量和年龄结构、经济运行状况、投资环境、金融条件等因素的影响。总之,随着我国经济稳定快速增长,人民生活水平的提高,住宅投资需求旺,增长空间大。
1.3生态节能建筑优化设计的综合评价指标
人们的社会属性,决定了住宅及其环境不仅具有庇护功能,还必须为生活关系中充满条件与行为世界提出价值意义和秩序要求,应是一个物质生活和精神生活的综合体。所以,创造符合人们要求的优质建筑产品,需要科学的,全面的综合评价指标体系作为前提和依据。我们利用AHP表达住宅建筑优化设计方案综合评价指标体系,如下图所示:
然而住宅投资价值来源于建筑的品质,有投资价值的物业一定要具备适宜性。即要适于人们居住和使用,契合人的动作和行为。这就要求,首先,物业的功能空间布置的顺序要合乎人的行为习惯;其次,功能空间和用具的尺度要符合人体活动舒适性的要求;第三,要有良好的通风采光,以维护人与自然的交流通道,才有益于保持使用者的良好的生存状态;第四,要尽可能大限度地引入人文的或自然的景观,以满足人的安全感、超脱感、优越感等心理要求;第五,要尽可能地拓展空间的可达性,即对外交通、交流的网络的通畅。对于现代的物业要求有较高的智能化水平。
室内空间的功能设计的好坏之所以重要,是因为室内空间的功能配置、布局、尺度直接影响使用人的活动效率、居住的舒适程度和生活质量。人们固然可以通过长时间的被动训练,而习惯和接受室内空间的不当设置、布局和尺度;但是不适当的设计所造成的空间浪费、利用率不高或活动的低效率以及动作的重复,是不会随着时间的延长而淡化的。由于设计不合理所造成的损失会在无形中减少投资者的投资回报。另外,随着人们现代生产、生活节奏加快,工作时间常常处于紧张的状态。因此,未来的人们将更需要用生活享乐和亲情生活来补偿和平衡心身。所以在未来的居住空间中,人们将更加注意身体的保养、注重高品位的娱乐及家庭亲情的培养。
依据综合评价指标,建立明确的投资目标,以达到优化资金、收益最大的目的。
2建立投资优化模型
所谓“资源分配问题”,就是把一定数量的若干资源合理地分配给若干个使用者,使指标函数达到最优。设某个地产投资的总量为a,拟用于n项经营活动,若给第j项活动分配xj个单位,其收益为gj(xj),找到最优的分配方式,使得这n项经营活动总的收益值最大,则有:
利用此问题的特性,把它看做一个多阶段决策问题,建立如下的动态规划模型:
以阶段变量k表示资金分配给第k项经营活动的过程;
以状态变量xk表示在开始给第k项经营活动分配资金时尚剩余的资金数量;
以决策变量uk表示分配给第k项经营活动的资金数量,则允许决策集合为Uk(xk)={uk|0≤uk≤xk},状态转移方程为xk+1=xk-uk;
以Vk(xk,uk)表示从现在有xk个单位资金分配给第k项经营活动uk个单位资金后的预计收益。
以fk(xk)表示从现在有xk个单位资金分配给第k项经营活动后,所得的最大收益,则函数基本方程为:
3模型应用
某建筑住宅小区总投资四千元,计划分配给经济效益(Ⅰ)、社会效益(Ⅱ)和环境效益(Ⅲ)三大效益,经调查,得到下表:
(千万)
效益 0 1 2 3 4
(Ⅰ) 0 4 6 7 9
(Ⅱ) 0 2 5 7 10
(Ⅲ) 0 5 7 8 11
通过此表及以上模型,可通过动态规划模型求出资金的最有分配策略及其最大收益值。
函数的基本方程为:
计算如下:
k=3时
u3
x3 V3(x3,u3)+0 f3(x3) u3*
0 1 2 3 4
0 0 0 0
1 0 5 5 1
2 0 5 7 7 2
3 0 5 7 8 8 3
4 0 5 7 8 11 11 4
k=2时,x3=x2- u2
u2
x2 V2(x2,u2)+f3(x3) f2(x2) u2*
0 1 2 3 4
0 0+0=0 0 0
1 0+5=5 2+0=2 5 1
2 0+7=7 2+5=7 5+0=5 7 0,1
3 0+8=8 2+7=9 5+5=10 7+0=7 10 2
4 0+11=11 2+9=11 5+7=12 7+5=12 10+0=10 12 2,3
k=1时,x2=x1-u1=4- u1
u1
x1 V1(x1,u21)+f2(x2) f1(x1) u1*
0 1 2 3 4
4 0+12=12 4+10=14 6+7=13 7+5=12 9+0=9 14 1
按k=1,2,3的顺序查表,方法如下:
得到最优分配方案为:分别给(Ⅰ)、(Ⅱ)、(Ⅲ)分配1、0、3(由于不可能在社会效益方面不投资,所以此解舍去)或者1、1、2。因此,最优解为经济效益1千万,社会效益1千万,环境效益2千万,最大收益为14千万。模型计算结果显示,环境效益在投资决策中占有很重要的地位,通过在投资项目实施后,也充分展示了动态规划模型从某种意义上在投资决策中的使用价值。
4结语
生态节能文化表现为谋求人与自然平等相待、和谐共处、共存共荣的新的生存方式,自然回归、向历史回归的各类手法,使身居闹市的居民,有一个调节身心、与自然融合、自由、清新和欢愉的空间。本文中建立的模型比较简单,在许多方面还不是很成熟,但利用本模型可以确定住宅投资决策的优化,能够利用计算结果,结合工程的实际情况,对住宅的投资做出最满意的决策,因而本模型具有一定的实际应用价值。如何在以后发展中更好的解决建设与生态节能问题,还需要一代代建设者的不断探讨,不断努力。
参考文献
[1] 戚昌滋.设计学[M].建筑工业出版社,2003.
[2] 刘启波,王玲,田静峰.住宅建筑优化设计方案综合评价指标体系的研究[J].基建优化,1998,(4).
[3] 王玉玲,朱江雁.浅谈住宅节能设计[J].新疆化工,2006,(1).
[4] 唐焕文,秦学志.实用最优化方法[M].大连理工大学出版社,2004.
[5] 张进嘉,陈大昆.住宅的优化设计[J].住宅科技,2001,(2).
[6] 朱通德.最优化模型与试验[M].同济大学出版社,2003.
[7] 刘琳.什么因素影响住宅投资[J].中国投资,2008,(5).
【关键词】财务指标 动态规划 投资组合
一、引言
我国资本市场虽然发展迅速,但其仍处于新兴的初始阶段,随着市场规模的扩大,市场运作的风险也在逐步加大。[1]而资本市场的风险与上市公司的质量与信用密切相关。随着我国股票市场的发展,选择上市公司进行股票投资,应更加理性,更加注重所选择上市公司的经营状况和可能存在的投资风险。
截止到2010年6月，我国上海证券交易所共有852家上市公司发行A股，54家发行B股。深圳证券交易所共有781家上市公司发行A股，59家发行B股。共计1746家（同时发行A股和B股的按2家计算）。如何在众多的上市公司中进行选择成了投资者面临的难题。然而，财务指标可以很好的帮助投资者了解企业的财务状况和未来发展前景，为正确选择股票进行投资奠定了基础。股票选择出来以后，如何在这些股票之间对资金进行合理分配，才能使投资组合获得最大收益？本文将应用动态规划(dynamic programming)方法解决该问题。
二、财务指标
（一）财务指标介绍
上市公司的财务指标有每股指标，盈利能力指标，成长能力指标，营运能力指标，偿债及资本结构指标，现金流量指标，其他指标。
下面主要介绍盈利能力指标，营运能力指标和成长能力指标。
盈利能力指标：盈利能力是指企业在一定时期内赚取利润的能力。[2]该指标是企业财务结构和经营经销的综合表现。盈利能力指标包括总资产利润率，主营业务成本率，资产报酬率等。
营运能力指标：企业生产经营资金周转的速度越快，表明企业资金利用的效率越高，企业管理人员的经营能力越强。营运能力指标包括流动资产周转指标、固定资产周转指标和总资产周转指标。[3]
成长能力指标：该指标体现了企业的经济实力和发展潜力，是企业的经营及管理状况的有效表现。其包括主营业务收入增长率，净利润增长率，净资产增长率，总资产增长率。
（二）财务指标的应用
上市公司由于其公开披露的财务信息很多，想较准确地把握企业的财务现状和未来，没有其他任何工具比财务指标更重要。然而，上市公司反映的财务指标有60多个，要是逐个都参考的话，不仅工作量较大，要求的专业素质也较高。[4]而成长能力指标中的净资产增长率是指企业本期净资产总额与上期净资产总额的比率，即(期末净资产一期初净资产)/期初净资产，反映了企业资本规模的扩张速度，是衡量企业规模变动和成长状况的重要指标。[5]若净资产收益率较高则代表了该上市公司有较强的生命力，如果在较高净资产收益率的情况下，有保持较高的净资产增长率，则表示企业未来发展更加强劲。所以，本文将主要考虑上市公司的净资产增长率在2007年至2010年的表现作为挑选股票的主要依据。且不同的行业可以有效的降低非系统分析，故经过比较选择分别挑选出来自不同行业的四只股票：船舶制造业的中国船舶（股票代码：600150），酿酒行业的贵州茅台（股票代码：600519），其他行业的东方园林（股票代码：002310），环保行业的桑德环境（股票代码：000826）.这四只股票在2007年至2010年的净资产增长率均超过17%，为行业领先。
三、动态规划
（一）动态规划简介
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。1951年美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，即把多阶段过程转化为一系列单阶段问题，逐个求解，从而创立了解决这类过程优化问题的新方法――动态规划。[6]
动态规划的好处在于，它把多变量的、复杂的决策问题进行分阶段决策，变成了求解多个单变量的决策问题。[7]首先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解，即从边界条件开始，逐阶段递推求优；在每一个子问题求解过程中均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得到的最优解就是整个问题的最优解。
（二）动态规划的要素
一是阶段。动态规划法需要把所解决的问题恰当地分解成多个相互联系的阶段，从而按一定的次序去求解。在动态规划法中，描述阶段的变量叫做阶段变量，常用k来表示。阶段一般是根据时间或空间的自然特征来划分，其划分的主要原则是便于把问题的过程转化为多阶段决策的过程。[8]
二是状态。常用Sk来表示第k阶段的状态变量。在动态规划法中，状态具有下面的性质：如果阶段状态给定后，则该阶段之后过程的发展不再受该阶段以前阶段状态的影响，这个性质叫做动态规划的无后效性。[9]正因为动态规划法有该性质，在构建决策过程的动态规划模型时，要特别注意是否满足无后效性的要求。[10]
三是决策。动态规划法中的决策表示当过程处于某一阶段的某个状态时，可以做出的不同决定或者选择，从而确定紧接着阶段的状态。常用uk(sk)来表示第k阶段当状态为sk时的决策变量，它是状态变量的函数。
四是状态转移方程。状态转移方程是决定过程由一个状态转移到另一个状态的演变过程，一般是前后相邻两个状态的演变。在动态规划法里，如果第k阶段的状态变量sk的值给定，则其决策变量uk(sk)的值一经确定，第k+1阶段的状态变量Sk+1的值也就由状态转移方程确定。[11]Sk+1的值随sk的值和uk(sk)的值的变化而变化，这种描述由k阶段到第k+1阶段的状态转移规律的方程，就叫做状态转移方程。
四、动态规划在股票投资组合中的应用
（一）案例介绍
假设某投资者已选出四只股票，分别是股票1（中国船舶600150），股票2（贵州茅台600519），股票3（东方园林002310），股票4（桑德环境000826）。现该投资者欲将6000元投资于这四只股票，希望通过合理分配资金，确定最优投资组合，使获得的投资收益最大。为了更好的反应各个股票的收益率，本文采用个股在2010年7月到12月半年的实际交易数据代替文献[7]中的预测数据。
表1月收益率
投资各股票的投资额与所得收益之间的关系如下：
表2 股票收益
（二）动态规划在投资组合中的应用
1.符号介绍：
(1)S一投资总额
(2)n一投资组合中的项目数
(3)uk一决策变量，分配给第k个项目的投资额
(4)gk(uk)一阶段目标函数，对第k个项目投资U。所获得的收益(5)Sk一状态变量，分配给第k个至第n个项目的投资额
(6)Sk+1=Sk-uk状态转移方程
(7)fk(Sk)一将Sk万元分配给第k个至第n个项目时所获得的最大收益
由此，得到逆序动态规划方程：
fk(Sk)=max{gk(uk)+fk+1(Sk+1))，0≤uk≤Sk，k=n，n―l，…，1fn+1(Sn+1)=0
利用这个递推关系式，所得fl(S1)为所求问题的最大收益，此时的投资组合的即为最优投资组合。
2.应用动态规划求解
A.当k=4时，将S4（1000，2000，3000，40000，5000，60000）投资于第四只股票，由上表可得：
i.当S4=1000时，f4=83.6 ii.当S4=2000时，f4=13.4
iii.当S4=3000时，f4=288.3 iv.当S4=4000时，f4=-249.2
v.当S4=5000时，f4=1122.5 vi.当S4=6000时，f4=764.4
B.当k=3时，将S3（1000，2000，3000，40000，5000，60000）投资于第三，四只股票。
f3(S3)=max{g3(u3)+f4(S4))
i.当S3=1000时，最优方案（u3，u4）=（1，0），f3=191.7.即将1000元投资于第三只股票，第四只股票不投。
ii.当S3=2000时，最优方案（u3，u4）=（1，1），f3=275.3.即将1000元投资于第三只股票，1000元投资于第四只股票。
iii.当S3=3000时，最优方案（u3，u4）=（0，3），f3=288.3.即将3000元投资于第四只股票，第三只股票不投。
iv.当S3=4000时，最优方案（u3，u4）=（1，3），f3=480.即将1000元投资于第三只股票，3000元投资于第四只股票。
v.当S3=5000时，最优方案（u3，u4）=（0，5），f3=1122.5.即将5000元投资于第四只股票，第三只股票不投。
vi.当S3=6000时，最优方案（u3，u4）=（6，0），f3=1519.2.即将6000元投资于第三只股票，第四只股票不投。
C.当k=2时，将S2（1000，2000，3000，40000，5000，60000）投资于第二，三，四只股票。f2(S2)=max{g2(u2)+f3(S3))
i.当S2=1000时，最优方案（u2，u3，u4）=（0，1，0），f2=191.7.即将1000元投资于第三只股票，第二，四只股票不投。
ii.当S2=2000时，最优方案（u2，u3，u4））=（2，0，0），f2=297.2.即将2000元投资于第二只股票，第三，四只股票不投。
iii.当S2=3000时，最优方案（u2，u3，u4）=（2，1，0），f2=488.9.即将2000元投资于第二只股票，1000元投资于第三只股票，第四只股票不投。
iv.当S2=4000时，最优方案（u2，u3，u4）=（2，1，1），f2=572.5.即将2000元投资于第二只股票，1000元投资于第三只股票，1000元投资于第四只股票。
v.当S2=5000时，最优方案（u2，u3，u4）=（5，0，0），f2=1275.即将5000元投资于第二只股票，第三，四只股票不投。
vi.当S2=6000时，最优方案（u2，u3，u4）=（0，6，0），f2=1519.2.即将6000元投资于第三只股票，第二，四只股票不投。
D.当k=1时，将S1（1000，2000，3000，40000，5000，60000）投资于第一，二，三，四只股票。f1(S1)=max{g1(u1)+f2(S2))
i.当S1=1000时，最优方案（u1，u2，u3，u4）=（0，0，1，0），f1=191.7.即将1000元投资于第三只股票，第一，二，四只股票不投。
ii.当S1=2000时，最优方案（u1，u2，u3，u4）=（0，2，0，0），f1=297.2.即将2000元投资于第二只股票，第一，三，四只股票不投。
iii.当S1=3000时，最优方案（u1，u2，u3，u4）=（0，2，1，0），f1=488.9.即将2000元投资于第二只股票，1000元投资于第三只股票，第一，四只股票不投。
iv.当S1=4000时，最优方案（u1，u2，u3，u4）=（0，2，1，1），f1=572.5.即将2000元投资于第二只股票，1000元投资于第三只股票，1000元投资于第四只股票，第一只股票不投。
v.当S1=5000时，最优方案（u1，u2，u3，u4）=（0，5，0，0），f1=1275.即将5000元投资于第二只股票，第一，三，四只股票不投。
vi.当S1=6000时最优方案（u1，u2，u3，u4）=（0，0，6，0），f1=1519.2.即将6000元投资于第三只股票，第一，二，四只股票不投。
从以上的计算过程可知，将6000元全部投资于第三只股票，第一，二，四只股票不投资，即（u1，u2，u3，u4）=（0，0，6，0）为最优的投资组合，可使投资收益最大为1519.2元。
五、结束语
财务指标可以帮助投资者有效的分析上市公司的经营及盈利等能力，通过它对上市公司进行比较，理性的选择股票进行投资。动态规划方法可以帮助投资者在股票之间对资金进行合理分配，将二者完美的结合，可使投资组合获得最大收益。
参考文献
[1]曲金敏.财务分析指标体系浅淡[J].经济论坛,2006.
[2]高克志.财务风险识别指标体系简析[J].财务与会计,2009(11).
[3]李凌.财务指标在我国上市公司分析中的作用[J].企业技术开发,2009(12).
[4]左勇.企业财务指标局限与改进[J].财务通讯,2009(12).
[5]黄立波.我国现行财务分析指标体系的局限,原因及对策[J].当代经济,2007(8).
[6]段玉娟.动态投资组合保险理论数值分析和实证检验[D].西南交通大学,2008.
[7]王朝霞,张庆.用动态规划理论确定最优投资方案[J].商场现代化,2006(9).
[8]胡元木,白峰.动态规划模型在股票投资组合中的应用[J].山东社会科学.2009(9).
[9]钟庆,吴捷,黄武忠等.动态规划在电力建设项目投资决策中的应用[J].电网技术,2002,26(8):48一51.
[10]邢莉艳,李纪成.动态规划法在网络成本工期优化中的应用[J].山东科学,1999.
关键词:0/1背包问题;动态规划;最优决策序列
中图分类号:TP
文献标识码:A
文章编号:1672-3198(2010)05-0301-01
1 问题描述
一个学生每月生活费总额为300元,每月的花费项目有伙食费200元、电话费30元、牛奶费40元、零食费30元、书报费30元、其他20元,其中伙食费产生的效益是25,电话费产生效益是3,牛奶费产生的效益是4,零食费产生的效益是2,书报费产生的效益是2.5,其他费用产生的效益是1。
这个问题可以形式化的描述为一个0/1背包问题:
设M为背包容量,其值为300,6个物品的重量成一向量(w1, w2, w3, w4, w5, w6)=(20,30,30,30,40,200),其价值成另一向量(p1, p2, p3, p4, p5, p6)=(1,2,2.5,3,4,25)。要找出另一个6元向量(x1, x2, x3, x4, x5, x6),xi∈{(0,1)|1≤i≤6｝, xi=0表示不选该物品,xi=1表示选该物品。
由此,这个问题的要求为:Max∑nwixi
且满足以下两个约束条件:
(1)∑ni=1wixi≤M
(2)xi∈{0,1}1 ≤i≤6
也就是说对0/1背包问题,可以通过作出变量x1,x2,…,xn的一个决策序列来得到它的解,而对变量xi的决策就是决定它是取0值还是取1值。
2 问题分析
动态规划是指在多阶段决策过程的每一阶段,都可能有多种可供选择的决策,但必须从中选取一种决策,一旦各个阶段的决策选定之后,就构成了解决这一问题的一个决策序列。决策序列不同,所导致的问题的结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解决的决策序列,即最优决策序列。
无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。用动态规划方法有可能解决该问题,而解决问题的关键在于获取各阶段间的递推关系式。
前文提出的有效使用生活费的问题正是一个最优性原理成立的0/1背包问题。在获取这个问题的递推关系时将使用向后处理法来解决。
对0/1背包问题,可以通过作出变量x1,x2,……,xi的一个决策序列来得到它的解。而对变量X的决策就是决定它取0值还是取1值。假定决策这些X的次序为xn,xn-1,……, x1。在对xn作出决策之后,问题处于下列两种状态之一:背包的剩余容量是M,没产生任何效益;剩余容量是M―w,效益值增长了p。显然,剩余下来对xn-1,xn-2,……, x1的决策相对于决策x所产生的问题状态应该是最优的,否则xn,xn-1,……, x1 就不可能是最优决策序列。如果设fi(x)是KNAP(1,j,X)最优解的值。那末fn(M)就可表示为
fn(M)= max{fn-1(M),fn-1(M-wn)+pn｝(2.1)
对任意的fi()x,这里i>0,则有
fi(x)=max{fi-1(x),fi-1(M-wi)+pi｝(2.2)
为了能由前向后递推而最后求解出fn(M),需从f0(x)开始。对于所有的X≥0,有f0(x)=0,当X
在具体算法中会运用序偶这个概念。(pi,wi)就称为一对序偶。设Si-1是fi-1的所有序偶的集合。Si1是fi-1(S - wi)+ pi的所有序偶的集合。把序偶(pi,wi)加到Si-1 中的每一对序偶上就得到Si1。
Si1={(p,w)|(P-pi, W-wi)∈Si-1｝
在2.2式中,求fi(x)就相当于在支配规则下将Si-1和Si1归并成Sn。如果Si-1和Si1之一有一序偶(pi,wi),另一有序偶(这pk,wk ),并且在wi≥wk的同时有pi≤pk,那么序偶(pk,wk)就被舍弃。这其实就是一个求最大值的运算。
生成Sn以后,最优解fm(M)是由Sn的最后一对序偶的P值给出的,用最后的这对序偶回溯确定最优决策序列(x1, x2,……, xn)。
确定回溯的过程是这样的。如果已找出Sn的最末序偶(P1,W1 ),那末,使pixi=P1,wixi=W1的x1,x2,…,xn的决策值可以通过检索这些Si来确定。若(P1,W1)∈Sn-1,则置xn=0。若(P1,W1)Sn-1,则(P1-pn,W1-wn )∈Sn-1,并且置xn=1。然后,再判断留在Sn-1中的序偶(P1,W1)或者(P1-pn,W1-wn)是否属于Sn-2以确定xn-1的取值。依此类推,就可以得到最优决策序列(x1, x2,……, xn)。
3 算法描述
用算法实现上述过程时,主要有初始化、生成S,回溯确定最优决策序列三部分。
3.1 变量解释
(1)p(n)、w(n) 每件物品的效益和重量
(2)P(m)、W(m) S0、S1、……、Sn的效益和质量分别相邻的存放
(3)F(n)存入每个序偶集的第一个元素的位置
(4)l、h分别是当前处理的序偶集的第一个和最后一个序偶的位置
(5)next下一空位
(6)k当前处理的序偶集中正要考虑处理的序偶的位置
3.2 初始化
F(0)1; P(1)W(1)0 // S0
lh1// S0的首端与末端
F(1)next2// P和W中的第一个空位
3.3 成生Si过程
for i1 to n-1 do
k1
u在l≤r≤h中使得W(r)+wi≤M是最大的r
for j1 to u do// 生成Si及归并
(pp,ww) (P(j)+pi, W(j)+wi) // 生成Si1 中的下一个元素
//从Si-1中取元素来归并
while k≤h and W(k)
// Si-1中的序偶的w< Si1中的w,则Si-1中此对序偶归并到Si中
P(next) P(k); W(next) W(k)
nextnext+1;kk+1
repeat
if k≤h and W(k)=ww then ppmax(pp,P(k))
kk+1
endif
if pp>P(next-1) then (P(next),W(next) (pp,ww)
nextnext+1
endif
while k≤h and P(k)≤P(next-1) do//清除
kk+1
repeat
3.4 沿Sn-1,……,S1回溯确定xn,xi-1,……, x1
(tempP,tempW) 最优选择序偶
for in to 1 do
u0
//u是一个标识位,判断由最优选择序偶倒推回来的Si中的序偶在Si-1中是否存在,如果不存在u=0,则此时X[I]=1,如果存在u=1,则此时X[i]=0。//
lF[i-1];hF[i]-1;
forrl to h do
ifW[r]= tempW and P[r]= tempP
u1
endif
repeat
if (u==0) thenX[i]1
else X[i]0
endif
tempWtempW-WI[i]*X[i]; tempPtempP-PI[i]*X[i]
//为判断X[i-1]来倒推序偶(tempP,tempW)
repeat
参考文献
[1]余祥宣,崔国华,邹海明.计算机算法基础[M].武汉:华中科技大学出版社,2006,(4).
关键词： 大学新校区过街设施比选设置
一、我国国内大学新校区的特点
1.飞地式发展。
随着高等教育的普及，在全国各大高校普遍扩招的大背景下，高等院校对于学校基础设施也随之提出了要求，离开老校区，寻求新的发展场地，成为国内高校的普遍共识。而绝大多数新校区选址远离城市中心，配套设施落后，成为典型飞地式发展的代表。
2.占地规模大。
目前高校新校区占地规模庞大是学校发展的特点之一，在征地规模上大大超越老校区，少则千余亩，多则几千亩。据统计，临沂大学新校区占地7300亩，成为目前国内占地最大的校园。成因是多方面的，外部因素主要包括城市总体规划战略的要求和地价因素；自身因素包括在校人数增多，实验教学场地扩大，以及对景观空间的需求增大、学校形象的需要，等等。
3.建设周期长，工期要求紧。
由于征地面积巨大、资金短缺等原因，高校新校区的建设往往是分期实施，很难一步到位，很多情况下甚至会大大超出规划年限。以苏州大学独墅湖校区为例，预计2010年全部建设完工，到目前为止学校内还仍存有大片未开发用地，未开发用地占征地面积的1/4。
同时，校园建设不同于其他开发建设项目，校园内的公共设施通常要在9月份开学新老生进校前投入使用，因此施工压力巨大，往往造成施工工艺粗糙，各类验收审计未通过就直接投入使用的情况。此外，校园建设是集学习、休憩、居住、交通于一身的综合开发过程，因此教学楼建设的同时要兼顾食堂和宿舍等基本生活设施的建设，更增加了一次性投资，限制了工期。
4.功能分区明确。
功能分区是定义场所秩序最有效的手段，明确的功能分区一直是校园规划的主要方式。当今大学校园功能分区更强调功能区间通过符合建筑的连接、轴线的连接、公共空间的连接而形成网络状的区间整合效果。
在新校区建设中，因为用地规模扩大，校园尺度过大，出行时耗增加，交通方式因此改变，使用交通工具成为首选；同时，生活区与教学区的绝对分离造成了每个时段的建筑利用率起伏剧烈，校园空旷缺少人气，潮汐式交通时常发生。
二、过街设施的选择
根据以上新校区规划建设的特点，可以看到新校区建设存在若干问题。本文重点以苏州大学独墅湖校区为例，通过对现状问题的解读，分析上位规划的要求，以及学校发展需要，对过街设施进行比选设置，达到缩短交通时间，同时合理联系校园各部分空间的目的。
1.苏州大学独墅湖校区介绍
苏州大学独墅湖校区位于风景秀丽的苏州工业园区南部独墅湖高等教育区内，距校本部12千米，总建设用地约为1800亩。基地内地势平坦，河网纵横，具有江南水乡地貌特色，东部和南部为规划的城市干道，西临独墅湖，北部的金鸡湖大道为城市快速路，其东北角、金鸡湖大道北侧为规划城市交通枢纽，有城市轻轨通过，可直达上海。
独墅湖校区以文景路为界将校园分为南北两块。北部为一期校园，南部为二期校园。一期校园占地890亩，建筑面积约35万平方米。一期项目自2004年3月正式开工，如今已完全建成。二期占地640亩，已经建成的工程近20万平方米，其他工程项目正在建设之中。2005年7月1日，有关学院正式开始入驻独墅湖校区。［1］
2.过街设施提出的背景
苏州大学独墅湖校区是新时期大学新校区规划建设的典型，在功能布局、建筑特色、学习环境、生活品质等方面都达到了高水平。然而由于一二期校园被城市道路文景路一分为二，校园通勤状况一直是师生所诟病的。缺少便捷实用的校内联系通道引发的问题如下。
（1）学生出行安全系数和校内的安全系数低。由于上课和自习需要，人员流动频繁，由于一二期校园缺少便捷的校园内联系通道，师生通常取道校外道路松涛街。在校园外步行时间长、频率高，同时需要经过一个十字路口，因此师生遭遇危险状况的可能性比较大。据统计，独墅湖校区自2005年投入使用至今，松涛街文景路十字路口发生交通事故5起，皆与学生穿越道路有关。加之周边居民增多，商业兴起，今后车流量必然增大，成为学生的通勤隐患。同时由于出入校门频繁，保安人员长期处于高度紧张的状态，出入校园的管理没有办法严格实行，导致学生和外来人员混杂。据调查，2011年全年保卫科接受学生报案丢失笔记本电脑20余次，2012年2月外来学生在校园内自杀而引发惨剧，种种迹象对校内治响了警钟，严峻的事实对校内治安提出了新的要求。
（2）交通花费时间长。根据统计，一名学生从一期学生宿舍到达位于二期的某学院（直线距离最短的两个地点），平均步行时间为20分钟。然而一二期是前后而建，交通并不是一个距离的问题，而是交通流线的设置问题。因此产生了一个“神奇”的现象，明明在宿舍就能看到学院在马路的另一侧，却不得不绕一个大圈到达学院。由此可见，路途长是一个亟待解决的问题。
（3）公共空间利用不足。一期生活区西面有一个很具有景观价值的水公园，在规划中一是分割了宿舍区和教学区，达到功能有效分区的目的；二是为学生提供了游憩的好去处。但由于水公园南边因为道路分割的原因而过于偏僻，因而少有人问津。同时，水公园南面是位于二期的运动场，但两者有河流隔开，使得运动场地也无法为同学共享，充分使用。
（4）学生群体间的交流不足。由于两个生活区通勤不便，教室、图书馆、食堂和景观运动场地的资源共享也就不方便，这就造成了一二期学生群体的融合有一定障碍，在一二期校园往往可以看到完全不同的生活状态。在一个学校内，信息的交流却不同步，这种现象是值得思考的。
3.过街设施的比选设置
目前，过街方式主要分为两种：一种是路面过街，即通过在道路上设置斑马线，使行人直接穿越的过街方式；另一种是立体过街，即通过人行天桥和过街地道的设置，从根本上解决行人与车辆之间的冲突。每种过街方式的优劣在目前已经有了十分透彻的阐述，但对于大学校园语境中的研究尚未成熟，本文从实际的角度出发，在分析校园规划和城市规划的同时，对过街设施的选择提出建议。
（1）路面过街方式的选择。这是原规划中设想的过街方式，文景路在规划中是作为校园道路存在的。在实际施工中可以看到一二期的道路仍然是对接的，只是中间被文景路切割，没有开设校门。没有按照设计图纸施工在规划领域经常出现，不可避免的问题是原深入探讨的设计可行性被抹杀。如果一二期的设计道路接通，上述很多问题将不复存在。深究其原因，是校园规划与苏州工业园区（SIP）总体规划相悖而造成的，原设置为内部道路的文景路在报批时被否定；同时随着独墅湖高教区的人车流增多，路面过街存在交通安全问题，因此设置路面过街的可行性较差。
（2）立体过街方式的选择。现行人行天桥和人行地下通道的对比，可以从使用者心理、气候因素、社会效益、经济条件、景观条件和施工影响这六个方面进行量化分析［2］，已经较为成熟，因此不再赘述。以下主要通过政策、资金、校园布局这三个维度进行分析选择人行地下通道的合理性。
①政策因素。苏州工业园区是中国与新加坡政府共同投资，以新加坡城市发展模式开发的新城示范区，目前苏州市总体规划已将苏州工业园区纳入苏州东部新城发展的核心区域。在城市发展的大背景下，苏州大学独墅湖校区校园过街设施的建设必须符合城市规划要求，根据《苏州工业园区城市规划管理技术规定》（2011年版）第三十二条关于人行通道的设置要求，一般区域应提供行人优先交通设施（如行人专用通道及地下、半地下步行道路），尽量创造人车分离的步行环境。在与城市规划相协调的过程中，地下通道是更好的选择。
②资金因素。人行天桥与地下过街通道在比选的过程中，资金是决定性的因素。一般来说，人行地道比人行跳桥造价高出20%―40%［3］，在使用地道时，能源消耗和养护维修等方面都存在许多问题，因此地道的修建、维护成本高。2008年苏州大学与苏州工业园区政府第二次战略合作会议为校园安全考虑达成修建过街通道共识，并由苏州工业园区管委会与校方按1：1的出资方式联合共建。在苏州大学独墅湖校区的人行地道修建过程中，苏州工业园区管委会的介入无疑消除了成本矛盾。
③校园布局因素。校园建设作为一个不断在调整平衡的过程，最终的建设往往几易其稿，因此与原规划发生出入是时常发生的现象。最新的校区规划表明一个大型的学生活动中心已经在施工中，从建筑配套、疏散人流方面考虑，地下通道是较为合适的选择。
三、结语
校园规划是一个综合性的设计过程，“麻雀虽小，五脏俱全”，它要求学校应具有全盘考虑，分步骤实施的把握能力。在学校动态的发展过程中，如何衔接好历次规划因变动产生的问题，保留住历次规划的特色与理念是需要认真思考的。同时新校区的规划必须与上一层次的城市规划相协调，只有配套城市发展，才能达成既定目标，真正实现规划理想。
参考文献：
［1］苏州大学独墅湖校区http：//dsh.suda.省略/xqgl1.asp
关键词：人才培养模式；工业工程；动态规划
中图分类号：G640 文献标识码：A 文章编号：1002-4107（2013）02-0058-02
一、动态规划与人才培养
（一）动态规划
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要做出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。
这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程。在多阶段决策过程中，动态规划法的基本思路是从终点逐段向始点方向寻找最短路线，既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑，从而得到整个问题的最优解[1]。
（二）动态规划思想融入工业工程专业人才培养
动态规划法的基本思想告诉我们，每段决策的选取是从全局来考虑的，与该段选择的最优答案一般是不同的，这对专业人才培养有很大的启发。如果把人的整个成长过程看成全局问题，在学校阶段取得最好成绩只是该段决策最优，能否在学生今后的就业及成长过程中发挥最大作用，实现成才的最终目标即达到全局最优，还取决于学生未来从事岗位和工作领域的选择。这对工业工程人才培养格外重要。
现代工业工程是技术与管理相结合的交叉学科，它既有鲜明的工程属性，也有明显的管理特征[2]。由于这门学科技术与管理交叉的特点，使得工业工程专业人才的就业方向非常广泛，既可以进行技术类的工程设计，也可以从事管理类的企业管理与决策，还可以继续深造进行科研攻关，每个方向的工作岗位对人才素质的要求各不相同[3-5]。多元化的选择使得学生毕业求职时看似什么岗位都适合，但事实上什么技能也不完全具备，只能临时抱佛脚或者遭到社会的淘汰。因此，要想较好地完成个人成长及成才，依据动态规划法的基本思想应从终点逐段向始点方向寻找最短路线，在进行人才培养时也应该进行逆序求解，首先帮助学生确立成才目标及个人定位，然后自后向前寻找，从而帮助每个学生对当前大学阶段的努力方向和培养过程进行决策。
二、启发式的人才培养模式
基于上述理念，南京工业大学工业工程专业结合自身办学条件和课程设置提出了开放性、启发式的人才培养新思路。在引导学生对未来职业定位和自身特点进行分析思考的基础上明确就业目标，利用课堂教学和课余时间对学生进行专项能力培训，最后集中进行学业成果展示，如图1所示。
（一）启发式的人才测评和职业倾向测试
首先，在入学时的专业介绍中让学生明确工业工程目前的发展状况以及未来发展趋势，有意识地引导学生思考自身目标，进行自我认知。在大二阶段设置的组织行为学课程实验中，运用斯坦福―比纳量表对学生进行智商测试，该量表不仅测试成人智商水平，而且显示被测试者在语言、数学、空间、理解等方面的智商特点，帮助他们了解自己的智商水平与智力特点。运用卡特尔16相人格测试量表和明尼苏达多相人格测试对学生进行人格特征测试，帮助他们了解自己的人格、能力特质。在智商、人格测试的基础上，运用霍兰德职业倾向测试，帮助学生了解自己的职业兴趣以及适合从事的职业类型。对有创业愿望的大学生运用南加州大学创造力测验，帮助学生了解自己是否适合创业，启发学生对未来职业定位、自身特点和兴趣进行思考。
图1 工业工程人才培养模式
（二）针对不同类型职业倾向的学生进行专项能力培训
在对学生进行人才测评和职业倾向测试的基础上，在大三大四专业课学习阶段针对不同类型职业倾向的学生进行专项能力培训与强化，设立成长性、开放性的课程体系，使每个学生都可以自主选择参与其中一种或几种培养计划。
1.对工程设计能力相对突出的学生，进行工业工程设计能力强化培训。在学生已掌握的工业工程领域先进工程设计软件的基础上，进行企业实地调研，综合运用Flexsim、Proplanner、AutoCAD、Matlab、动作分析软件、流水线等软硬件进行工程设计与改善，并在培训结束后对设计作品和数据资料进行汇总刻盘，最终得到可以向用人单位展示的设计成果。
针对此类学生的培养，在大三大四每学期期末开设为期3周的课程设计进行强化培训，开放性实验也可为学生提供设计与实验的平台。此外，加强校企联合，尝试在毕业设计过程中组成团队深入企业（如沙钢集团）生产第一线进行团队毕业设计。在进行实地调研两个月的基础上，每个学生针对企业实际存在的问题进行分析解决，最后形成毕业设计。这样较长时间的让学生深入企业进行课题研究，让学生能够持续性地、效果可检验地深入企业第一线进行毕业设计，并联合各个教师的研究特长对学生进行全程指导，能够切实提高学生的工程设计能力，加强团队合作精神，打造适应市场需求的高素质人才，最终的团队设计成果以总报告的方式提交给企业，深受企业赞许，多名团队成员毕业后直接进入该企业工作。
2.对管理能力相对突出的学生，进行管理实践能力强化培训。每年全国都会召开工业工程应用案例大赛及现代物流技能大赛，利用此契机让每个学生都参与其中，综合课程所学的相关知识，对大赛中提出的案例进行分析解决，让每个学生都撰写相应的案例解决报告。这样每个同学都有可以参与全国大赛的机会，报告也可以作为学生就业时的独特成果向用人单位展示。
对自主创业意识和能力相对突出的学生，进行创业实战能力培训。通过参加学院每年举办的企业生产运营BOSS大奖赛和商道管理决策竞赛，组织参与听取学校创业讲座，增强其创业意识和决策能力，并结合市场情况指导其撰写详细的创业计划书。
在该模式的引导下，南京工业大学在校生多次获得全国商科院校技能大赛、大学生管理决策模拟大赛、IE亮剑等国内竞赛奖项，毕业生中也有多个创业团队出现。
3.对科研能力突出的同学，在课程中引入研究型教学[6]。教师以课程内容和学生的学识积累为基础，引导学生创造性地运用知识和能力，自主地观察问题、提出问题、分析问题和解决问题，在研讨中积累知识、培养能力和锻炼思维。
目前，我们选取“质量管理与可靠性”课程进行研究型教学试点，教师提出问题，引起学生思考，并牵头成立该课题的研究小组，引导他们在课后开展科研活动。目前课题组已经产生了丰硕的研究成果，以这些科研成果为基础，教师与本科生合作在《工业工程与管理》等核心期刊上发表了学术论文4篇。
三、开放性的学业成果全过程立体化展示
在以上培训的基础上，每个学生都具备了可以向用人单位展示的各种成果。我们建设开放性的“工业工程学生学业成果展示”网站，将每个学生本科四年期间的各种学业成果进行集中展示，包括工程设计作品、创新创业作品、案例设计成果、各类竞赛成绩等，以学生个人为标签，为全系学生建立个人网页，全过程、立体化地反映学生本科四年的学习成果。
成果主要将以各种可视化的方式进行有效展示，包括：个性化自我介绍（视频）、发表的论文成果、各种奖励证书、工业工程三大实习（认识实习、金工实习与生产实习）的现场多媒体展示、专业主干课程实验及课程设计作品、参与竞赛获奖、创新设计作品等，可以让学生亲自参与到网页内容编辑及页面设计中，充分利用各种多媒体工具和网络平台，将每个学生的比较优势展现出来。这种方式不仅能够提高学生的学习积极性、实践能力、创新能力，而且能够使企业快速、全面、立体地了解本专业每一个学生的独特能力，而不是仅靠一纸简历来平面地了解学生的情况。这种信息沟通方式既能有效促进本专业学生的就业，又加强了学校与用人单位的联系，双方可充分利用网络这个平台进行实时的动态交互。不仅企业通过这个平台了解到学生的能力，我们也可以通过这个平台随时了解用人单位的需求，进而调整改进教学活动和实践安排。
实践表明，自该方法实行以来，学校培养了一批特点突出、素质高的优秀毕业生，获得了学生及用人单位的一致好评。可以说，启发式、开放性、因材施教的培养方式无论在提高人才培养质量方面，还是在高等教育教学理论应用和人才培养方法方面都取得了一定成果，迈开了教学改革坚实的一步。
参考文献：
[1]吴祈宗.运筹学：第2版[M].北京：机械工业出版社，
2006.
[2]马如宏.工业工程专业课程设置探讨[J].教育与职业，
2006，（35）.
[3]郭绚霞.提高我国高校大学生就业力的途径[J].改革与
开放，2009，（7）.
[4]张忠，杨蕾.基于当前就业形势的工业工程专业教学改
革探析[J].装备制造技术，2009，（3）.
[5]杨振刚，陈建国.基于港式思路的IE专业人才培养新模
式[J].工业工程，2010，（6）.
关键词：群区理念；电梯；运行效率
1 电梯运行群区设计理念概述
建筑物内部的“交通”随着楼层的增加而频繁，电梯系统设计也更加复杂。当楼层超过15层以上，为使电梯运行更有效率，会将各楼层划分成数个群区，每一个群区有数个电梯，服务某一些固定的楼层。每个群区服务约6至10个楼层，越高层的群区服务楼层数应越少。群区电梯有数种不同的运行方式，通常各群区电梯从楼下主楼出发，直达其服务区的最低楼层，再以每层均停的方式服务其他各楼层。群区电梯对高层建筑而言，有如下的优点：一是高层群区的电梯不停靠低层区，可以节省乘客的时间，增加电梯运行效率，减少电梯购置数量。二是高层群区的电梯不停靠低层区，低楼层不需要电梯等待时间。底层群区的电梯不停靠高层区，电梯坑上面空间均可利用，因此群区设计可以增加建筑物可使用的楼板面积。三是低层区可以使用较低速的电梯，节省电梯购置费用。四是高层区乘客可以节省等待时间及在电梯内的等待时间。
不过群区设计只能适用于60层以下的高楼，如果超出这个高度，群区数过多，低楼层的空间将会因高楼乘客“借道”而被电梯坑沾满，60层以上的超高楼层建筑的电梯应利用空中大厅方式来运行。另外，大楼的交通被分隔，群区设计比较不适合专用办公大楼。建筑施工单位在进行规划时，除非事先决定电梯厂商，否则无法进行电梯规划。文章应用动态规划模式，来决定高层建筑物的群区电梯数及服务楼层、电梯容量及速度，以期使建筑物能在规划初期前，可确定高层建筑物的电梯是否应该划分群区、如何划分群区电梯的服务楼层以及各群区应设置的电梯数、电梯容量、电梯运行速度，以便在建筑施工前，即可预留电梯的坑道数和等待的楼板面积。
2 群区理念的电梯运行设计方法
电梯运行设计在高层建筑中扮演着十分重要的角色，可目前电梯设计方法的文献中，绝大多数只适用于中低层建筑每层暂停的电梯。这套电梯设计概念可分成六大步骤：一是假设电梯的数量、容量与速率；二是由大楼面积楼层数及使用性质，估计高峰5分钟乘客到达率及乘客数；三是计算电梯预停数及最高返回层；四是求出一周时间间距及输送能力；五是检查电梯的服务品质（一周时间，间距及输送能力）是否达到设计标准；六是如果不合标准，则回到第一步骤，重新假设电梯数量、容量及速度再进行计算，直到满意为止。这一方法只适用于低层建筑，为使电梯运行更有效率，高层建筑会将各楼层划分成数个群区，每一个群区有数个电梯，服务某些固定的楼层。有群区的电梯设计方式除了要决定电梯数、电梯及速度群区数等底层电梯的设计项目外，同时求解出最佳的群区数及各群区所服务的楼层，群区电梯设计参数、设计标准和一般无群区的设计大致相同，以动态规划方法求取最佳电梯群区服务楼层。一般的设计步骤如下：一是计算一周时间；二是计算每个群区中，其电梯群的装载时间；三是使用动态规划法来求解最佳的电梯区规划数及服务的楼层。上述的装载时间是一周时间的函数，是每个群区许多电梯的一周时间总和，用以衡量电梯运送乘客的能力。
文章的求解目标为在满足服务品质（一周时间，间距及输送能力）的限制下，使总成本为最低。求解方法是以动态规划法求的最佳高层建筑电梯的群区数、各群区电梯所服务的楼层范围以及电梯数量、容量与速度。动态规划法电梯运行模式涵盖电梯运行模式、总成本函数及动态规划求解三大部分。
一是电梯运行模式。电梯运行模式的目的是计算电梯运行时间，以检验电梯设计是否合乎服务水平，计算内容包括最高返回层、运转一周时间及出发间隔等，计算方法与一般底层电梯设计大致相同。其中，最高返回层的计算式为：
二是总成本函数。电梯总成本包括电梯设置成本。楼板成本、维护费用及乘客的时间成本。群区电梯设计目标是使电梯总成本为最小的情况下，求的最佳分区数与各分区的电梯数、电梯速度、容量及服务楼层。
三是动态规划方法求解。根据动态规划方法，假设G为动态规划的阶段，即大楼的群区数；Zg为动态规划的状态，即第g群区的最高服务楼层Z；C（Z）为服务前g个群区的Zg楼层的最低总成本；Bg（Xi，Zg）为第N个群区，其服务Xi至Zg层的成本。由既定的电梯数、速率及计算出的一周时间、出发间隔，可进而求出以货币单位表示的总成本，则服务第一个群区的最低总成本为：
以此类推，可得到回归关系，即Cg（Zg）=Min{Cg-1（Xg-1），Bg（Xg，Zg）}。
由于建筑物的最高楼层数Zn已知，因此从动态规划原则可求出各个群区的最佳服务楼层范围。
3 结束语
高层电梯采用群区设计时，不仅可以节省乘客时间，而且能够剩下较多的电梯坑道及等待大厅所占的空间，因而比无群区设计的总成本要低。文章建立的动态规划法电梯运行模式，主要是针对高层建筑物电梯的群区设计，可以在各群区不同的电梯服务楼层范围下，能迅速求出总成本最小情况下的最佳群区数与转乘楼层划分组合。当然，电梯的运行控制及乘客行为分析的动态效果并无法确切掌握，只能以诸多假设条件来加以约束。然而，模拟方法就可以辅助这方面的不足，以设计更真实的电梯运行状况。未来建议可以用模拟方法进行高层建筑群区电梯运行设计，并与动态规划方法进行比较。
参考文献
关键词：带式输送 结构方案 设计
中图分类号：TH222 文献标识码：A 文章编号：1672-3791（2012）11（b）-0075-02
现代散状物料运输的主要设备就是带式输送机，其在运输系统中占得比重是越来越高了，而优势方面也是越来越明显，所以在很多比较复杂的环境中也是需要这种特别高效的运输工具（环境有防洪的筑堤和震后重建的场所等方面），但是目前固定机架水平的转弯输送机还是很难程度上满足这些比较恶劣的环境要求的。拟设出一种可以较适应复杂环境的运输机，进而实现出了蜿蜒移动的带式输送机。采用结构模块化的设计方法来设计出蛇形输送机，并且运用动态寻优的方法和层次分析的方法来确定出最优的输送机机构方案[3]。
1 结构方案设计流程
新型的输送机设计方案可以分为各组合方案的评价、功能与构建映射、功能分解、以及总功能的确定这四个方面的额阶段。
1.1 黑箱法确定新型输送机的总功能
新型输送机的总功能：新型输送机行进过程中实现散体物料的运输。黑箱示意图如图2。
1.2 新型输送机的功能分解
功能分解的结果可以用树形结构表示，利用树结构方法对功能编码进行存储，通过遍历的方法进行功能的查找。多个并列的子功能构成了“或树”结构，相互依存的子功能构成了“与树”结构。用树形结构描述功能分解的优点是功能的层次分明，功能与构件的对应关系清楚明了，易于用计算机实现功能分解和组合。新型输送机的功能分解的树形结构如图5所示。
构件是功能的载体，是功能实现的手段，通过搜索构件数据库，获得子功能与构件的映射关系，有些子功能与构件是一一对应的，有的是一对多的关系。
2.3 动态规划寻优
3 新型输送机方案设计的实现
不同的原则，在新型输送机结构的动态规划问题输送机机功能分解得出四个功能元素视为相互关联的四个不同的阶段，每个阶段的功能元素的映射方案解决。权重的原则，程序解决以下和邻近的原则规划解决方案结合额定产品的最大为目标函数，反序求解方法使用动态规划的解空间优化。
根据评价模型的动态规划优化理论，解决问题，可以得出最佳的决定为。这一动态规划问题，该新型蛇形输送机结构优化程序的“移动”的功能元素对应的原则，程序解决方案选择“爬虫+轮式移动的（头车履带移动，其余汽车使用的轮式移动）的水平；将功能元件对应原理解决方案选择“跟踪差速转向缸辅助”；“垂直转弯”的功能元件对应原理解决方案选择“万向接头连接由重力垂直翻转”（垂直输送机是攀登，下坡条件）；“散装物料处理功能元素相应的程序设计的原理方案选择“工”型带式输送机。
4 结论
运用模块分析放来建立一个新型的输送机，同时与动态规划法相互运用到程序的评价体系当中，这样结果就证明出，运用一个最权重的方法确定最好的解决方案，符合实际，同时速度的优化模型，避免了组合爆炸留下的原因盲目搜索造成更多的功能。由于采取了一系列的专家知识，消除一个设计师的情感偏好因素影响的设计，但也不会发生，只是因为一个指标是不符合，就案件可能是最好的设计概念排除。实践证明，该设计方法可以应用于其他机构的方案设计。
参考文献
[1] Hyeon H R，Wong JP.Concurrent engineering：the manufacturing philosophy for the 90’s[J].Computer Industry Engineering，1991，21（1—4）：34-39.
[2] Wynne Hsu，Irenem·Y·Woon.Current research in the conceptual design of mechanical puter—Aided Design，1998，30（5）：377-389.
金盆水库是西安黑河引水工程的主要水源工程，是一项以西安市供水为主，兼顾周至、户县37万亩农田灌溉，还有发电、防洪和养鱼等多种功能的大型综合利用水利工程。如何合理的调度金盆水库，发挥其最大效益，对缓解西安市供水紧张的局面以及实现社会经济的可持续发展和人民生活稳步提高都具有极其重要的意义和价值。
水库优化调度是一典型的多维非线性函数优化问题，目前常用的方法有模拟法、动态规划及其系列算法、非线性规划等等。这些方法各具特色，但应用中也常有一些问题，模拟法不能对问题直接寻优，动态规划（DP）随着状态数目的增加会出现所谓“维数灾”问题，增量动态规划（IDP）可能收敛到非最优解，逐步优化算法（POA）需要一个好的初始轨迹才能收敛到最优解[1]。因此，这些方法还有待进一步的完善。
遗传算法（GA）作为一种借鉴生物界自然选择思想和自然基因机制的全局随机搜索算法，可模拟自然界中生物从低级向高级的进化过程，GA在优化计算时从多个初始点开始寻优，对所求问题没有太多的数学约束，而且优化求解过程与梯度信息无关[2]，因此在多个不同领域得到了广泛应用。而GA在水库优化调度方面GA应用相对较少[3]，马光文等[4]使用基于二进制编码的遗传算法对水库优化调度进行了研究。由于二进制编码存在的编码过长、效率低及需要反复的数据转换等问题，畅建霞、王大刚分别提出了基于整数编码的遗传算法[5-6]，并将GA与动态规划的计算结果进行了比较。
自适应遗传算法（AdaptiveGA，AGA）使得交叉概率Pc和变异概率Pm能够随个体适应度的大小以及群体适应度的分散程度进行自适应的调整，因而AGA能够在保持群体多样性的同时，保证遗传算法的收敛性。本文根据黑河金盆水库的具体情况，建立了水库长期优化调度的自适应遗传算法模型，并将其与动态规划的计算结果进行了比较。
2.水库优化调度数学模型的建立
金盆水库为多功能水库，其优化调度应使其达到城市供水量最大、灌溉缺水量最小、年发电量最大和弃水量最小等目标要求。但此多目标优化模型如果直接采用多维多目标动态规划或其它方法求解，则可能因为目标、状态、和决策变量较多的占用计算机内存和时间，因而有必要先做适当处理，将多目标问题转化为单目标，再进行求解。考虑到城市供水和灌溉用水要求保证率高，因此将水库优化调度目标定为年发电量最大，而将城市与灌溉供水当作约束条件进行处理。
这样，金盆水库优化调度的目标函数就可以描述为：在满足水库城市供水、灌溉用水和蓄水要求条件下，使水库年发电量最大。
目标函数：F=max（1）
上式中，N（k）为各时段的发电量。
约束条件：
①水量平衡约束：（2）
②水库蓄水量约束：（3）
③电站水头约束：（4）
④水轮机最大过流量约束：（5）
⑤电站出力约束；（6）
⑥城市供水约束：（7）
⑦灌溉供水约束：（8）
⑧非负约束。
其中，Nmin与Nmax分别为电站允许的最小及最大机组出力，Hmin与Hmax分别为电站最小及最大工作水头，qmax为机组过水能力，WCt、WIt分别为第t时段城市和灌溉供水量。DIt为第t时段灌溉需水量，DCt,max与DCt,min分别为第t时段城市需水上下限。
3.自适应遗传算法的实现
在水库优化调度中，水库的运行策列一般用发电引用流量序列来表示，而该序列又可以转换为水库水位或库容变化序列。对于水库优化调度的遗传算法可以理解为：在水位的可行变化范围内，随机生成m组水位变化序列,,…,，其中，m为群体规模，n为时段数，再通过一定的编码形式分别将其表示为称作染色体（个体）的数字串，在满足一定的约束条件下，按预定的目标函数评价其优劣，通过一定的遗传操作（选择、交叉和变异），适应度低的个体将被淘汰，只有适应度高的个体才有机会被遗传至下一代，如此反复，直至满足一定的收敛准则。
3.1个体编码
为简化计算，本文采用实数编码。个体的每一向量（基因）即为水库水位的真值。表示
为：（9）
式中，分别为时段t水库水位的最大值和最小值。m为控制精度的整数，Nrand为小于m的随机数。
3.2适应度函数
在遗传算法中，用适应度函数来标识个体的优劣。通过实践，采用如下适应度函数，效果更好。
（10）
式中为目标函数值，c为目标函数界值的保守估计，并且≥0,≥0。水库优化调度为约束优化问题，关于约束条件的处理，本文采用罚函数法,
（11）
式中，为原优化问题的目标函数值，M为罚因子，Wi为与第i个约束有关的违约值，p为违约数目。
3.3遗传操作
交叉运算交叉的目的是寻找父代双亲已有的但未能合理利用的基因信息。设x和y是两父代个体，则交叉产生的后代为=ax+(1-a)y和=ay+(1-a)x，这里，a为[0,1]内均匀分布的一个随机数。
变异运算通过变异可引入新的基因以保持种群的多样性，它在一定程度上可以防成熟前收敛的发生。具体方法为：个体Z的每一个分量Zi,i=0,1…,n以概率1/n被选择进行变异。设对分量ZK进行变异，其定义区间为（ZK,min,ZK,max）,则
=（12）
式中，Rand为0到1之间的随机数，rand（u）函数产生最大值为u的正整数。
3.3参数的自适应调整
遗传算法的参数中交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性，Pc越大，新个体产生的速度就越快。然而，Pc过大，遗传模式被破坏的可能性越大。对于变异概率Pm，如果Pm过小，不易形成新的个体；如果Pm过大，则遗传算法就成了纯粹的随机搜索算法。自适应遗传算法（AGA）使得Pc和Pm能够随适应度按如下公式自动调整：
Pc=（13）
Pm=（14）
式中，为群体中最大的适应度值；为每代群体的平均适应度值；为要交叉的两个个体中较大的适应度值；为要变异的的个体的适应度值。,,,为自适应控制参数，其变化区间为（0,1）。
综上所述，算法的运算步骤为：
(1)初始化，设置控制参数，产生初始群体；
(2)计算各个体的目标函数，应用(5)式进行适应度变换；
(3)按随机余数选择法对母体进行选择；
(4)对群体进行交叉和变异操作pc和pm分别按式(2)与(3)计算，得到新一代群体；
(5)检验新一代群体是否满足收敛准则，若满足，输出最优解，否则转向步骤2。
4.模型求解及成果分析
金盆水库坝高130米，总库容2亿方。该水库是以给西安供水为主（按照设计年均向西安供水3.05亿方），兼顾周至、户县共37万亩农田灌溉（年均灌溉供水1.23亿方），还有发电、防洪等多功能的大型综合利用水利工程。水库的特征参数为：正常蓄水位594m，死水位520m，电站出力系数8.0，装机容量2万KW，保证出力4611KW，水轮机过流能力32.6m3/s，汛限水位591米，汛期7-9月，以某中水年为例，入库径流已知，用上述算法按年发电量最大求解水库优化调度，结果见表一。
表一自适应遗传算法计算结果
Table1.Resultsbyadaptivegeneticalgorithm
月份
入库水量(108m3)
月末水位(m)
城市需水(108m3)
城市供水(108m3)
灌溉需水(108m3)
灌溉供水(108m3)
弃水(m3/s)
发电流量(m3/s)
水头(m)
出力
(KW)
7
1.5160
572.63
0.3050
0.3050
0.2301
0.2301
20.10
40.04
6437.88
8
1.3178
591.00
0.2898
0.2898
0.2196
0.2196
24.75
68.87
13637.35
9
0.6973
591.00
0.2593
0.2593
0.1342
0.1342
26.90
77.50
16679.24
10
0.8464
594.00
0.2410
0.2410
0.0000
0.0000
30.05
78.69
18918.95
11
0.2063
589.33
0.2349
0.2349
0.0879
0.0879
12.47
76.88
7667.76
12
0.1963
587.96
0.2257
0.2257
0.0440
0.0440
10.08
75.26
6069.95
1
0.1513
585.61
0.2257
0.2257
0.0000
0.0000
8.43
73.38
4947.77
2
0.1260
582.23
0.2349
0.2349
0.0000
0.0000
9.72
70.31
5467.50
3
0.3000
581.54
0.2410
0.2410
0.0810
0.0810
12.20
68.38
6673.10
4
0.3732
581.75
0.2440
0.2440
0.1206
0.1206
14.07
68.14
7671.54
5
0.2373
561.68
0.2593
0.2593
0.0226
0.0226
31.83
59.00
15023.79
6
0.1776
520.00
0.2898
0.2898
0.2900
0.2900
32.56
32.06
8350.21
注：年发电量E=8608.3万KW·h；POP=100；Gen=200；==0.85；==0.01。
作为比较，本文又使用了基本遗传算法（SGA）、动态规划法（DP）进行计算，其目标函数、约束条件完全相同。对应的计算结果见表二，其中，DP的离散点为300。
表二动态规划及基本遗传算法计算结果比较
parisonofResultsofDPandSGA
月份
动态规划（DP)计算结果
基本遗传算法（SGA）计算结果
月末水位(m)
弃水(m3/s)
发电流量(m3/s)
水头(m)
出力
(KW)
月末水位(m)
弃水(m3/s)
发电流量(m3/s)
水头
(m)
出力
(KW)
7
572.5
20.23
39.95
6466.38
572.65
20.08
40.05
6433.56
8
591
24.62
68.82
13553.20
591.00
24.77
68.88
13650.11
9
591
26.90
77.50
16679.20
591.00
26.90
77.50
16679.24
10
593.5
30.02
78.72
18905.40
594.00
30.05
78.69
18918.97
11
588.5
13.10
76.68
8037.72
589.33
12.46
76.88
7663.79
12
586.5
10.53
74.83
6303.83
587.96
10.09
75.26
6075.39
1
584.5
8.79
72.28
5084.92
585.21
8.85
73.20
5180.34
2
581.5
9.82
69.17
5434.83
581.83
9.88
69.90
5524.98
3
580.5
12.46
67.30
6706.82
581.04
12.39
67.93
6733.84
4
580.5
14.40
66.90
7705.63
580.87
14.66
67.46
7911.34
5
562
29.42
58.24
13706.00
561.62
30.56
58.38
14273.88
6
520
0.32
32.60
32.31
8426.54
520.00
32.50
32.02
8323.96
注：DP年发电量8568.9万KW·h；SGA年发电量8581.3万KW·h，POP=100,Gen=200。
比较表一和表二可见，动态规划在控制精度为0.5m时，优化结果为8568.9万KW·h，低于SGA的8581.3万KW·h和改进本文算法的8608.3万KW·h，主要是因为DP的离散点数较后两类算法少。为了说明本文算法的优越性，将其与SGA在不同的进化代数时分别进行10次计算，结果列于表三。
表三不同进化代数的两类算法年发电量比较比较
parisonofResultsoftheTwoAlgorithmsinDifferentGeneration
编号
本文算法（AGA）
基本遗传算法（SGA）
Gen=200
Gen=500
Gen=200
Gen=500
1
8607.1
8596.8
8374.1
8594.2
2
8597.5
8607.2
8581.6
8571.9
3
8604.7
8612.7
7957.2
8433.1
4
8601.2
8603.5
8593.4
8475.3
5
8596.6
8595.4
8599.1
8596.2
6
8606.8
8607.2
7837.2
8608.4
7
8608.3
8608.4
8365.9
7892.1
8
8525.4
8611.3
8521.5
8592.6
9
8605.9
8551.6
8575.3
8610.3
10
8603.4
8603.7
8121.6
8441.2
注：表中年发电量单位为万KW·h。
从上表可以看出，随着进化代数的增加，两算法计算结果都越接近最优解；无论是自适应遗传算法还是基本遗传算法，其计算结果明显优于动态规划；在进化代数相同时，AGA的计算结果优于SGA，并且未收敛次数也有明显减少，表明AGA能够有效加快收敛速度。
5.结论
本文建立了水库优化调度的自适应遗传算法模型，并将其用于黑河金盆水库优化调度。与动态规划相比，遗传算法能够从多个初始点开始寻优，能有效的探测整个解空间，通过个体间的优胜劣汰，因而能更有把握达到全局最优或准全局最优；自适应遗传算法通过参数的自适应调整，能更有效的反映群体的分散程度以及个体的优劣性，从而能够在保持群体多样性的同时，加快算法的收敛速度。
ApplicationofAdaptiveGeneticAlgorithmstotheoptimaldispatchingofJinpenreservoir
FuYongfeng1ShenBing1LiZhilu1ZhangXiqian1
(1Xi’anUniversityofTechnology,Xi’an710048,
2HeadquartersofHeiheWaterDiversionProject,Xi’an,710061)
AbstractBasedontheanalysisofthecharacteristicsituationofJinpenreservoir,acomprehensiveoptimaloperationmodelisdevelopedwithconsiderationofitsmulti-objectiveandnonlinearfeatures.Themodelissolvedbythethreemethodsofdynamicprogram,thesimplegeneticalgorithmandtheadaptivegeneticalgorithm.Itisshowedthattheadaptivegeneticalgorithm,withthecharacterofitsparametercanbeadjustedadaptivelyaccordingtothedispersiondegreeofpopulationandthefitnessvalueofindividuals,hasthefastestconvergencevelocityandthebestresultcomparedtoothertwoalgorithms.
Keywords:optimaloperation；geneticalgorithms；dynamicprogram
参考文献
[1]方红远,王浩,程吉林.初始轨迹对逐步优化算法收敛性的影响[J].水利学报,2002,11:27-30.
[2]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.
[3]RobinWardlawandmohdSharif.Evaluationofgeneticalgorithmsforoptimalreservoirsystemoperation[J].WaterResour.Plng.andMgmt.,1999,125(1):25-33.
[4]马光文,王黎.遗传算法在水电站优化调度中的应用[J].水科学进展,1997,8(3):275-280.
关键词：动态规划；贪心算法；启发式算法；构造解的结构；最短路径求解
1.引言
货运公司在运输货物时，由于货物大小、重量不一样，为了降低货物损失，必须按照一定顺序摆放；而位于路线不同点上的公司对货物种类、数量的需求有差异。为了实现货运公司的利润最大化以及客户需求被很好的满足，必须合理安排车辆以及车上所载货物，争取用最少车辆满足客户的需求和到达相应客户点时卸货的方便。
本文通过使用贪心算法，利用其最优子结构和贪心选择构造出贪心解，并且该贪心解是足以解决本问题，从而得出动态规划的最优解，最后使用启发式策略合理分配派车方案。
2.实例研究
2.1 问题描述
某地区有8个公司，某天某货运公司要派车将各公司所需的三种原材料A，B，C 从某港口分别运往这些公司。路线是唯一的双向道路。货运公司现有一种载重 6 吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次。每辆车平均需要用 15min的时间装车，到每个公司卸车时间平均为10min，运输车平均速度为 60km/h，每日工作不超过8h。车载重运费 1.8 元/吨公里，空载费用 0.4 元/公里。一个单位的原材料 A，B，C分别毛重4t、3t、1t，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量，需求量见下图。 在这些给定的条件下，求最佳的调度方案，使得成本最小。
2.2 问题假设
每辆车装车时彼此独立，不需等待；每辆车进出港口彼此独立，不会堵塞；运输道路充畅，不堵车；车行驶过程不发生突发事件；每家公司对货物种类和数量需求无时间上优先级，即当天满足即可；车辆不调头。
2.3优化方案及方法
2.3.1符号说明：W（i，j）：第i次送货到第j公司货物的重量；D（i，j）：第i次送货到第j公司货物的载重路径；N：出车次数；E（i，j）：第i次送货到第j公司的后产生的空载费用；A（i，j，k）：一辆车上载i单位A，j单位B，k单位C
2.3.2 模型的建立
（1）描述动态规划解的算法：费用组成由载重费用、空载费用、港口出车费用和固定出车费用组成，具体计算公式如下：1）固定出车费：6*20=120元；2）港口出车费：10*N；3）载重费用：1.8*W（i，j）*D（i，j），表示第i次送货到j公司载重费用，其总费用可在EXCEL里实现。4）空载费用：0.4*（60-D（i，j）），表示第i次送货到j公司后产生空载费用；其总费用可在EXCEL里实现；
（2）最优子结构描述：1）每次派车都应该充分发挥其运载能力；2）、每次派车的货物都尽可能的运往一个公司；3）、载重的路程应尽量按就近原则；4）、每次派车的货物种类或数量应尽量满足大部分的公司的货物种类和数量 需求。
（3）贪心选择：因为公司的位置和所需货物固定，影响其费用的仅为该公司的车次和运载方向；我们可以贪心的选择在最优子结构条件下，是该家公司所需车次最少，并合理选择其出车方向。在运输车满载的情况下有以下方案：A（1，0，2），A（0，0，6），A（0，2，0），A（0，1，3），所特别的是8家公司的B货物需求为18单位，恰可通过派车方案A（0，2，0）9次完成；下面则只讨论A和C货物的，A的需求为18单位C需求为26，若只用A（1，0，2）则C超出，则可以考虑（1，0，1）（1，0，0）（0，0，3）（0，0，2）（0，01），使每家公司可以用最少车次完成所需。下面是通过贪心选择的A和C的派车方案如下表一：
其中的每车次运输方向按载货路程的就近原则，我们通过表格很容易看出最优选择之一总是贪心的选择，那么贪心选择是安全的，可以最终得出最优的贪心解。
（4）合并最优子结构和贪心选择：通过表一我们可以得出5、6、7公司分别需要一辆车次来运2、3、1单位的的C，我们可以将以一车次的A（0，2，0）与之合并产生两次的A（0，1，3）则可以减少车次，最终得出A、B、C的最终运输方案如下（表2）：
（5）求最后贪心解：建立EXCEL表格，利用启发式算法合理安排派车方案，算出贪心解，即最后可以替代的动态规划解
3.结束语
对于本案例的解决，采用了贪心解直接给出了动态规划解。但最后给出的是贪心解的结构，从而得出的优化解只是在满足最优值的条件下一种解的结构，无法给出符合最优值的全部解的结构。在不考虑解的结构约束的情况下，是可取的，并不一定是最优值的解，但确很逼近该最优解，且这种贪心解的结构是合理的。（作者单位：南京农业大学）
参考文献
