時間：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.結束語
對于本案例的解決，采用了貪心解直接給出了動態規劃解。但最后給出的是貪心解的結構，從而得出的優化解只是在滿足最優值的條件下一種解的結構，無法給出符合最優值的全部解的結構。在不考慮解的結構約束的情況下，是可取的，并不一定是最優值的解，但確很逼近該最優解，且這種貪心解的結構是合理的。（作者單位：南京農業大學）
參考文獻
