動態(tài)規(guī)劃精品(七篇)

序論：寫作是一種深度的自我表達(dá)。它要求我們深入探索自己的思想和情感，挖掘那些隱藏在內(nèi)心深處的真相，好投稿為您帶來了七篇動態(tài)規(guī)劃范文，愿它們成為您寫作過程中的靈感催化劑，助力您的創(chuàng)作。

篇(1)

【關(guān)鍵詞】動態(tài)規(guī)劃；矩陣連乘問題；最優(yōu)子結(jié)構(gòu)；遞歸算法；重疊子問題

1.動態(tài)規(guī)劃

動態(tài)規(guī)劃[1]是運(yùn)籌學(xué)的一個分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法――動態(tài)規(guī)劃。動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用，例如庫存管理、資源分配、設(shè)備更新、排序、裝載等問題。

動態(tài)規(guī)劃是一種將復(fù)雜的問題分解為更小的、相似的子問題，并存儲子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。

1.1 基本思想

動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨(dú)立的，可以用一個表來記錄所有已解決的子問題的答案，不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時間算法。[2]

1.2 求解問題特征

動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。

1.2.1 最優(yōu)子結(jié)構(gòu)

原問題的最優(yōu)解包含著其子問題的最優(yōu)解，這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。

1.2.2 子問題重疊

遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次，這種性質(zhì)稱為子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常不同的子問題個數(shù)隨問題的大小呈多項(xiàng)式增長。因此用動態(tài)規(guī)劃算法只需要多項(xiàng)式時間，從而獲得較高的解題效率。

1.3 設(shè)計(jì)步驟

3.總結(jié)

動態(tài)規(guī)劃方法中每步所作的選擇往往依賴于相關(guān)子問題的解，因而只有在解出相關(guān)子問題后才能做出選擇所以動態(tài)規(guī)劃，算法通常是以自底向上的方式解各子問題的解進(jìn)而求出原問題的解。動態(tài)規(guī)劃是一種很靈活的算法設(shè)計(jì)方法，在動態(tài)規(guī)劃算法的設(shè)計(jì)中，類似的技巧還有很多。要掌握動態(tài)規(guī)劃的技巧，有兩條途徑：一是要深刻理解動態(tài)規(guī)劃的本質(zhì)，這也是為什么一開始就探討它的本質(zhì)的原因；二是要多實(shí)踐，不但要多應(yīng)用，還要學(xué)會從應(yīng)用中探尋規(guī)律，總結(jié)技巧。運(yùn)用動態(tài)規(guī)劃算法解決的還有很多現(xiàn)實(shí)問題，如背包問題、最長公共子序列問題、凸多邊形最優(yōu)三角剖分問題、電路布線等問題，在本文中沒有介紹。動態(tài)規(guī)劃算法雖然復(fù)雜，但只要掌握它的本質(zhì)特征并多加練習(xí)，就可以靈活運(yùn)用，并加以擴(kuò)展，來提高程序的時效性。

參考文獻(xiàn)

[1]百度百科.http：//

[2]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析（第四版）[M].北京：電子工業(yè)出版社，2012.

篇(2)

關(guān)鍵詞：動態(tài)規(guī)劃；裝載問題；JAVA語言

中圖分類號：TP31 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）10-2401-03

Abstract： How to load goods to get maximum economic benefits by manufacturers is a sub-problem divided from logistics distribution.In this paper，the sub-problem is abstracted a 0-1 knapsack problem.We create a mathematical model based on dynamic programming algorithm，and analyze the advantages of the algorithm.Then we use JAVA language to solve the problem.After setting some test datum， the final results show that the dynamic programming method has efficiency，and can be applied widely.

Key words： Dynamic programming； Loading problems； JAVA language

隨著經(jīng)濟(jì)的不斷發(fā)展，各廠商在滿足客戶需求的條件下，利用物流技術(shù)，從備貨、裝箱、配送、存儲等物流配載技術(shù)網(wǎng)中尋求省時省力的方法，使得資源使用效率得到提高，同時降低了廠商的成本[1]。

問題提出：某廠商每周向校園超市運(yùn)輸一次商品，在小型貨車容量不變且不能超載的約束下，如何裝載商品，使產(chǎn)生的經(jīng)濟(jì)效益最大化？該問題是廠家所關(guān)心的，也是本文的關(guān)注點(diǎn)。運(yùn)用動態(tài)規(guī)劃方法解決此問題，能夠較好地控制企業(yè)的人力資源成本和運(yùn)輸成本，從而提高商業(yè)的競爭力。

1 動態(tài)規(guī)劃算法簡介

動態(tài)規(guī)劃（dynamic programming）[2]產(chǎn)生于20世紀(jì)50年代，由美國數(shù)學(xué)家R.E.Bellman等人提出。動態(tài)規(guī)劃的思想是把一個問題劃分為具有相關(guān)性的若干子問題來解決，并將各個子問題求解答案和求解方法進(jìn)行保存。如果在之后的處理過程中還需要用到已解決的子問題，則直接調(diào)用答案，從而避免重復(fù)的計(jì)算，節(jié)省了時間。

在解決實(shí)際問題中，我們需要動態(tài)規(guī)劃出適當(dāng)?shù)募s束條件和遞推關(guān)系，并在各單階段中尋找互相聯(lián)系的因素，依次將每一階段所得的最優(yōu)結(jié)果進(jìn)行存儲。這種階段劃分、自下向上的求解方式需要建立表或數(shù)組才能有效實(shí)施。如圖1所示：

基于動態(tài)規(guī)劃法解決的問題需要滿足一定的條件，例如：（1）滿足無后效性，即子問題的下一狀態(tài)只與現(xiàn)在狀態(tài)有關(guān)；（2）滿足最優(yōu)性子結(jié)構(gòu)，得出子問題的最優(yōu)解；（3）原問題可以劃分出多個擁有關(guān)聯(lián)的子問題[3]。

2 模型的建立

廠商向校園超市運(yùn)輸商品的問題：已知廠商共有N件商品，每件商品擁有固定的Id號，Id=i的商品重量為Wi，產(chǎn)生的經(jīng)濟(jì)效益為Vi，貨車的最大載重量為N?，F(xiàn)假設(shè)一個n維向量Xi=（X1，X2，...Xn）∈{0，1}n，當(dāng)Xi=1時表明相應(yīng)Id的商品裝入車中；當(dāng)Xi=0時表明商品未裝入車中。最終得出的結(jié)果為[maxi=1nViXi]，即最大效益值，約束條件為[maxi=1nWiXi]≤N。貨車的載重量是有限的，在這個上限內(nèi)盡可能裝下商品使經(jīng)濟(jì)效益越高越好。通過以上分析，此問題恰好可以抽象為一個重量集合、經(jīng)濟(jì)效益集合與貨車載重量分別是Wi={W1，W2，...Wn}，Vi={V1，V2，...Vn}和N的0-1KP問題。

在0-1背包問題中，物品價值與體積不隨背包容量的變化而變化[4]。舉例說明：假設(shè)有N=3個物品，總?cè)萘繛?0，體積V[i]={2，4，6}分別對應(yīng)價值P[i]={3，7，4}，設(shè)數(shù)組B[i][j]，表示在背包容量為j的條件下，放入第i個物品后的最大價值。如下表1所示：

動態(tài)規(guī)劃算法易于編程的實(shí)現(xiàn)，雖然需要一定的空間存儲其產(chǎn)生的結(jié)果，但是它的高效性能在測試中體現(xiàn)出來。

4 測試數(shù)據(jù)

假設(shè)廠商貨車載重量為上述的1534，他們所建Commodity表中總共有50件商品，其Id、weight、value的數(shù)據(jù)分別如下所示：

最終得出經(jīng)濟(jì)效益最大值為1904，如圖3所示。

5 結(jié)束語

本文從實(shí)際出發(fā)，給出廠商向校園超市運(yùn)輸商品時的裝載問題，結(jié)合一個有效的算法――動態(tài)規(guī)劃算法，利用JAVA語言得以實(shí)現(xiàn)。動態(tài)規(guī)劃法有較好的效率和速度，不僅能用于解決裝箱問題，而且能夠運(yùn)用于物流配載中的路徑規(guī)劃、資源分配等實(shí)際問題，優(yōu)化了企業(yè)資源管理，提高經(jīng)濟(jì)效益，降低資源成本，能夠應(yīng)用于更多的科學(xué)領(lǐng)域中。

參考文獻(xiàn)：

[1] 謝天保，雷西玲，席文玲.物流配送中心配載車輛調(diào)度問題研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，36：237-240.

[2] 陳大偉，孫瑞志，向勇，史銀雪.基于流程模式的工作流靜態(tài)規(guī)劃方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011（1）：129-132，137.

篇(3)

【關(guān)鍵詞】數(shù)學(xué)模型 動態(tài)規(guī)劃 多階段投資決策

一. 引言

多階段決策問題是投資者在連續(xù)的幾個投資階段中每個階段里都進(jìn)行投資， 其目的是使得到最后一個投資階段結(jié)束時， 投資者進(jìn)行多次投資的收益總和盡可能大， 這些投資階段之間是相互關(guān)聯(lián)的， 面對眾多的投資項(xiàng)目， 如何合理的安排資金成為決策部門關(guān)心的焦點(diǎn)， 而動態(tài)規(guī)劃方法的關(guān)鍵在于正確寫出基本遞推關(guān)系式， 首先將問題的過程分成幾個相互聯(lián)系的階段， 恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)， 從而把一個大問題化成一族同類型的子問題， 然后逐個求解， 即從邊界條件開始， 逐階段遞推求優(yōu)， 在每個子問題求解過程中均利用了它前面的子問題的最優(yōu)結(jié)果， 依次進(jìn)行， 最后一個子問題所得到的最優(yōu)解就是整個問題的最優(yōu)解.

二. 動態(tài)規(guī)劃在多階段投資組合中的應(yīng)用

1.案列介紹

假設(shè)某公司決定將60萬元投資4個工廠， 該公司希望通過合理分配資金確定最優(yōu)組合，使所獲得的投資收益最大， 經(jīng)調(diào)查各個工廠所獲得收益和投資額如圖所示.

投資額與收益額 （單位： 萬元）

2.建立動態(tài)規(guī)劃模型

由于動態(tài)規(guī)劃問題的特殊性， 我們將它看作一個多階段決策問題， 分階段來解決， 為此， 我引入以下各參數(shù)：

（1）s――投資總額

（2）n――投資組合中的項(xiàng)目數(shù)

（3）uk――決策變量，分配給第K個項(xiàng)目的資金

（4）sk――狀態(tài)變量，分配給前k個工廠的資金

（5）sk-1=sk-uk――分配給前k-1個工廠的資金

（6）gk（uk）――階段目標(biāo)函數(shù)，對第 個項(xiàng)目投資 所獲得的收益

（7）fk（s）――目標(biāo)函數(shù)，以數(shù)量為 的資金分配給前 個工廠所得到的最大利潤值

當(dāng)k=1時，

當(dāng)1

3. 利用動態(tài)規(guī)劃模型求解

第一階段： 求f1（s） ， 則

第二階段： 求 ，

最優(yōu)策略為（40，20）， 此時最大利潤值f2（60）=120萬元.

同理可得其他f2（u2）及最優(yōu)策略

第三階段： 求f3（u3），

同理可求得其他f3（u3）的值

第四階段： 求f4（60）， 即問題最優(yōu)策略

所以最優(yōu)策略為（20，0，30，10）， 最大利潤為160萬元.

4.模型的意義分析

本文針對多階段資產(chǎn)投資問題， 以最終的總收益盡可能大為決策目標(biāo)的資產(chǎn)投資組合問題的一個多階段動態(tài)規(guī)劃決策模型， 利用動態(tài)規(guī)劃的順序法求得多階段投資的整休最優(yōu)投資組合.

參考文獻(xiàn)：

[1]胡元木，白峰. 動態(tài)規(guī)劃模型在股票投資組合中的應(yīng)用， 山東社會科學(xué)， 2009；09（39）.

篇(4)

【關(guān)鍵詞】配電網(wǎng)；動態(tài)規(guī)劃技術(shù)；恢復(fù)供電

當(dāng)前，智能電網(wǎng)的發(fā)展在一定程度上帶動了電網(wǎng)技術(shù)的發(fā)展，并且成為了電網(wǎng)技術(shù)發(fā)展的重要方向。實(shí)際上，智能電網(wǎng)的重要組成部分在于智能配電網(wǎng)，智能配電網(wǎng)的主要特征為擁有完備的自愈能力，同時還能夠最大程度的減少電網(wǎng)故障給用戶帶來的影響。而配電網(wǎng)故障的恢復(fù)是智能配電網(wǎng)自愈功能實(shí)現(xiàn)的重要過程，配電網(wǎng)故障恢復(fù)問題主要指配電網(wǎng)發(fā)生故障以后，在故障定位與故障隔離的基礎(chǔ)之上，應(yīng)用一定的故障恢復(fù)策略對其進(jìn)行操作，從而確保供電的平穩(wěn)與正常。

一、對最佳路徑的分析

配電網(wǎng)故障區(qū)域恢復(fù)供電的最佳路徑事實(shí)上是在故障情況下的配電網(wǎng)絡(luò)重構(gòu)。主要的目的在于，能夠快速的將非故障區(qū)域供電恢復(fù)，與此同時，還能夠有效的滿足線路負(fù)載容量的要求以及線損最小等各個方面的條件?，F(xiàn)階段，在配網(wǎng)自動化領(lǐng)域中研究最多的在于怎樣能夠快速的實(shí)現(xiàn)故障隔離以及快速的恢復(fù)費(fèi)故障區(qū)域的供電技術(shù)方法，因此，在恢復(fù)路徑的最優(yōu)化選擇方面出現(xiàn)了較多的研究。

一般而言，配電網(wǎng)故障區(qū)域恢復(fù)供電的路徑為多目標(biāo)最佳路徑問題，現(xiàn)階段在最佳路徑問題的研究上較多的便是城市交通網(wǎng)絡(luò)中的最短路徑問題的研究。由于問題解決的思路存在著極大的不同點(diǎn)，因此最短路徑問題能夠被分為單元最短路徑算法與基于啟發(fā)式搜索最短路徑算法[1]。這與鄧群，孫才新，周駁仍凇恫捎枚態(tài)規(guī)劃技術(shù)實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電》一文中的觀點(diǎn)極為相似。其中，單元最短路徑算法主要體現(xiàn)在幾個方面，即：

第一，在GIS空間查詢語言方面的最短路徑。該職工路徑的研究方法在當(dāng)前還停留在理論研究方面，例如在MAX中定義了一套空間查詢語言，該套語言對其完備性給予了相關(guān)證明，同時通過舉證的方式，對范圍查詢與時態(tài)查詢等進(jìn)行了應(yīng)用分析。

雖然，對于GIS空間發(fā)展研究GeoSQL為一種有效的處理最短路徑的手段，但是GIS受到數(shù)據(jù)庫技術(shù)發(fā)展的制約與影響，導(dǎo)致實(shí)際的應(yīng)用領(lǐng)域和背景的不同，使其和商用之間還有很長的一段距離。

第二，在功能模塊思想路徑方面，需要按照不同的分類方法實(shí)施，而單元最短路徑問題的算法能夠被分為很多種，例如神經(jīng)網(wǎng)絡(luò)法與基于人工智能的啟發(fā)式搜索算法等，對于不同的背景應(yīng)用需求和具體軟件應(yīng)用的環(huán)境，各種算法在空間的復(fù)雜程度與時間的復(fù)雜程度等都有明顯的體現(xiàn)[2]，這與李振坤，周偉杰，錢嘯等在《有源配電網(wǎng)孤島恢復(fù)供電及黑啟動策略研究》一文中有著相似的觀點(diǎn)。并且各種算法在故障恢復(fù)方法中各具特色。

另外，啟發(fā)式搜索最短路徑算法也是一種有效的手段。基于啟發(fā)式方向策略最短路徑算法，其中包括空間有效方向的可控參數(shù)法，該方法能夠有效的調(diào)節(jié)相關(guān)系數(shù)，在有效方向上路徑無效的時候，能夠確保得到有效的路徑。

二、最佳路徑的選擇方法分析

事實(shí)上，配電網(wǎng)故障區(qū)域恢復(fù)供電的最佳路徑并不是簡單的路徑問題，而是多目標(biāo)最佳路徑問題。為此，在研究配電網(wǎng)非故障區(qū)域恢復(fù)供電的最佳路徑過程中，需要對其展開綜合的分析。

首先，在多目標(biāo)分析方面，通常在選擇配電網(wǎng)非故障區(qū)域恢復(fù)供電最佳路徑的時候，最為重視的目標(biāo)為：

第一，在恢復(fù)供電路徑的過程中，饋線負(fù)荷不能過載，同時，還需要確?；謴?fù)區(qū)域的電壓質(zhì)量能夠與實(shí)際規(guī)定的標(biāo)準(zhǔn)要求相吻合。當(dāng)供電質(zhì)量可靠性最高的時候，那么恢復(fù)的時間將會很短[3]；這與鄧?yán)ビ?，汪鳳嬌，饒杰等在《智能配電網(wǎng)有功自治互動建模研究》一文中的觀點(diǎn)極為相似。另外，供電過程中，線損最低，證明開關(guān)拉合的次數(shù)最少，同時現(xiàn)場的操作點(diǎn)也會最少。

第二，在動態(tài)規(guī)劃技術(shù)恢復(fù)供電的最短路徑方面需要明確，動態(tài)規(guī)劃主要是運(yùn)籌學(xué)的一個分支，它是求解決策過程的最優(yōu)的數(shù)學(xué)方式。早在很久以前，就已經(jīng)有研究人員對多階段過程轉(zhuǎn)化問題轉(zhuǎn)化為一系列的單階段問題，并且逐一進(jìn)行求解，這標(biāo)志著解決這類過程優(yōu)化問題的新方法的創(chuàng)立，即動態(tài)規(guī)劃技術(shù)。

本文主要將一典型的復(fù)雜配電網(wǎng)絡(luò)作為研究例子，該連通系包括10個電源點(diǎn)，8個分支點(diǎn)，同時聯(lián)絡(luò)開關(guān)有16個。將其加入到配網(wǎng)潮流方向和典型的運(yùn)動方式中，將聯(lián)絡(luò)開關(guān)和電源點(diǎn)作為定點(diǎn)，那么可以將其分為26個定點(diǎn)。盡管從數(shù)量上頂點(diǎn)比較多，但是由于存在著較為復(fù)雜的網(wǎng)絡(luò)關(guān)系，使得該問題成為一個極為簡單的最短路徑問題[4]。這與楊建在《配電網(wǎng)無功補(bǔ)償系統(tǒng)的關(guān)鍵技術(shù)研究》一文中的觀點(diǎn)有著相似之處。加之恢復(fù)路徑主要指費(fèi)故障區(qū)域相關(guān)的聯(lián)絡(luò)開關(guān)與相應(yīng)路由，為此我們可以將其理解為從不同電源點(diǎn)出發(fā)到各個聯(lián)絡(luò)開關(guān)的最短路徑問題，這樣一來，故障恢復(fù)工作的實(shí)施便簡單的多。

總結(jié)

本文主要從兩個方面左手，共同分析了采用動態(tài)規(guī)劃技術(shù)實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電的方法與效果，一方面著手于最佳路徑的分析，另一方面著手于最佳路徑的選擇方法。從這兩個方面可以看出，利用動態(tài)規(guī)劃技術(shù)去實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電是一種可行的方法。但是，受到歷史原因的影響，我國城市配電網(wǎng)絡(luò)還缺少標(biāo)準(zhǔn)的規(guī)范要求，導(dǎo)致配電網(wǎng)常常出現(xiàn)一些事故。因此，恢復(fù)配電網(wǎng)供電已經(jīng)成為當(dāng)務(wù)之急。隨著科技的發(fā)展，智能配電網(wǎng)已經(jīng)被廣泛的應(yīng)用在供電方面，這為平穩(wěn)供電提供了一定的保障，同時也為恢復(fù)配電網(wǎng)故障供電創(chuàng)建了良好的環(huán)境與條件等。

參考文獻(xiàn)

[1]鄧群，孫才新，周駁.采用動態(tài)規(guī)劃技術(shù)實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電[J].重慶大學(xué)學(xué)報（自然科學(xué)版），2006，29（3）：40-44.

[2]李振坤，周偉杰，錢嘯等.有源配電網(wǎng)孤島恢復(fù)供電及黑啟動策略研究[J].電工技術(shù)學(xué)報，2015，30（21）：67-75.

[3]鄧?yán)ビ?，汪鳳嬌，饒杰等.智能配電網(wǎng)有功自治互動建模研究[J].機(jī)電工程技術(shù)，2014，（2）：4-7.

[4]楊建.配電網(wǎng)無功補(bǔ)償系統(tǒng)的關(guān)鍵技術(shù)研究[D].中南大學(xué)，2002，（12）：56-78.

篇(5)

關(guān)鍵詞：最短路徑；動態(tài)規(guī)劃；C 語言編程

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）09-2191-03

1 概述

數(shù)學(xué)源于生活，又服務(wù)于生活.它是一門研究現(xiàn)實(shí)世界中的數(shù)量關(guān)系與空間形式的學(xué)科.當(dāng)今社會，隨著物質(zhì)水平的不斷提高，生活需求的不斷擴(kuò)大，自然資源的不斷開發(fā)利用.像天然氣管道鋪設(shè)問題，廠區(qū)布局問題，旅行費(fèi)用最小問題等都已成為我們平時經(jīng)濟(jì)生活中的普遍問題.它們其實(shí)都可以化歸為最短路線問題，而最短路問題實(shí)質(zhì)上是一個組合優(yōu)化問題[1]。

動態(tài)規(guī)劃方法主要是研究與解決多階段決策過程的最優(yōu)化問題，它將求解分成多階段進(jìn)行，不但求出了全過程的解，還能求出后部子過程的一組解，在求解一些生活實(shí)際問題時，更顯其優(yōu)越性。為了快速、簡單的計(jì)算最短路徑，節(jié)約運(yùn)輸時間與成本，該文利用動態(tài)規(guī)劃的思想編寫了C語言程序，解決物流運(yùn)輸過程中多地點(diǎn)的最短路徑的選擇問題。

2 最短路徑問題

2.1 最短路徑問題算法的基本思想

在求解網(wǎng)絡(luò)圖上節(jié)點(diǎn)間最短路徑的方法中，目前國內(nèi)外一致公認(rèn)的較好算法有迪杰斯特拉（Dijkstra）及弗羅伊德（Floyd）算法。這兩種算法中，網(wǎng)絡(luò)被抽象為一個圖論中定義的有向或無向圖，并利用圖的節(jié)點(diǎn)鄰接矩陣記錄點(diǎn)間的關(guān)聯(lián)信息。在進(jìn)行圖的遍歷以搜索最短路徑時，以該矩陣為基礎(chǔ)不斷進(jìn)行目標(biāo)值的最小性判別，直到獲得最后的優(yōu)化路徑[2]。

Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點(diǎn)之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結(jié)點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復(fù)雜度為[On3]，雖然與重復(fù)執(zhí)行Dijkstra算法n次的時間復(fù)雜度相同，但其形式上略為簡單，且實(shí)際運(yùn)算效果要好于前者。

2.2 最短路徑問題算法的基本步驟[3]

這樣經(jīng)過有限次迭代則可以求出[v1]到[vn]的最短路線。

（2）Floyd算法的基本步驟

（3）動態(tài)規(guī)劃算法基本步驟

我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃[1]。在解決多個階段決策問題時采用動態(tài)規(guī)劃法是一個很有效的措施，同時易于實(shí)現(xiàn)。

根據(jù)動態(tài)規(guī)劃的基本概念，可以得到動態(tài)規(guī)劃的基本步驟：1）確定問題的決策對象。2）對決策過程劃分階段。3）對各階段確定狀態(tài)變量。4）根據(jù)狀態(tài)變量確定費(fèi)用函數(shù)和目標(biāo)函數(shù)。5）建立各階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程。

根據(jù)動態(tài)規(guī)劃的基本模型，確定用動態(tài)規(guī)劃方法解題的基本思路，是將一個[n]階段決策問題轉(zhuǎn)化為一次求解[n]個具有遞推關(guān)系的單階段的決策問題，以此來簡化計(jì)算過程.其一般步驟如下：

用于衡量所選決策優(yōu)劣的函數(shù)稱為指標(biāo)函數(shù).指標(biāo)函數(shù)有有階段的指標(biāo)函數(shù)和過程的指標(biāo)函數(shù)之分.階段的指標(biāo)函數(shù)是對應(yīng)某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個階段的某種效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]來表示某一階段的決策的最短路徑。過程的指標(biāo)函數(shù)是指從狀態(tài)[xn（k=1，2，...，n）]出發(fā)至過程最終，當(dāng)采取某種子策略時，按預(yù)定的標(biāo)準(zhǔn)得到的效益值。這個值既與[xk]本身的狀態(tài)值有關(guān)，又與[xk]以后所選取的策略有關(guān)，它是兩者的函數(shù)值，記作[dk，nxk，uk，xk+1，uk+1，…xn，un]。過程的指標(biāo)函數(shù)又是它所包含的各階段指標(biāo)函數(shù)的函數(shù)。本文研究的過程的的指標(biāo)函數(shù)是其各階段指標(biāo)函數(shù)的和的形式.當(dāng)[xk]的值確定后，指標(biāo)函數(shù)的值就只同k階段起的子策略有關(guān)。對應(yīng)于從狀態(tài)[xk]出發(fā)的最優(yōu)子策略的效益值記作[fkxk]，于是在最短路問題中，有[fkxk=mindk，n]。動態(tài)規(guī)劃求解最短路徑程序流程圖如圖2所示。

3 最短路徑態(tài)規(guī)劃實(shí)際應(yīng)用舉例

設(shè)某物流配送網(wǎng)絡(luò)圖由12個配送點(diǎn)組成，點(diǎn)1為配送中心起點(diǎn)，12為終點(diǎn)，試求自終點(diǎn)到圖中任何配送點(diǎn)的最短距離。圖中相鄰兩點(diǎn)的連線上標(biāo)有兩點(diǎn)間的距離[4]。

首先用動態(tài)規(guī)劃法來討論圖3的最短路徑，由圖可知：

1）集合[ξ4]中有點(diǎn)9、10、11，它們在一步之內(nèi)可到達(dá)點(diǎn)12；

2）集合[ξ3]中有點(diǎn)6，7，8，它們不超過兩步就可達(dá)到點(diǎn)12；

3）集合[ξ2]中包括點(diǎn) 2、3、4、5，不超過三步就可到達(dá)點(diǎn)12；

4）集合[ξ1]中包括點(diǎn)1，不超過四步可到達(dá)點(diǎn)12；

按照動態(tài)規(guī)劃法類推，得到最優(yōu)路徑長為16，徑路通過點(diǎn)為1，2，7，10，12和1，3，6，10，12。

根據(jù)動態(tài)規(guī)劃算法編寫C語言計(jì)算程序[5] [6]，計(jì)算得到實(shí)驗(yàn)結(jié)果如下圖4所示：

由圖4可以看出程序得到的結(jié)果與本文推出的結(jié)果一樣。證明了本文編寫的C語言程序是正確的。

4 結(jié)束語

綜上所述，用動態(tài)規(guī)劃解決多階段決策問題效率高，而且思路清晰簡便，同時易于實(shí)現(xiàn).我們可以看到，動態(tài)規(guī)劃方法的應(yīng)用很廣泛，已成功解決了許多實(shí)際問題，具有一定的實(shí)用性。此種算法我們用動態(tài)規(guī)劃思想來編程，并解決相應(yīng)的問題，其在 VC 環(huán)境下實(shí)現(xiàn)，能方便快速的計(jì)算出到達(dá)目的地的最短距離及路徑，節(jié)省更多的運(yùn)輸時間與成本。不過，該文只考慮了動態(tài)規(guī)劃算法在生活中的簡單運(yùn)用，在實(shí)際生活中可能存在多個目的地或者更復(fù)雜的情況.因此我們可以考慮將其進(jìn)行改進(jìn)或者結(jié)合啟發(fā)式算法，使之更好的運(yùn)用在實(shí)際生活中，這有待于以后的繼續(xù)研究。

參考文獻(xiàn)：

[1] 杜彥娟.利用動態(tài)規(guī)劃數(shù)學(xué)模型求解最短路徑[J].煤炭技術(shù)，2005（1）：94-95.

篇(6)

關(guān)鍵詞： 虛擬機(jī)； 動態(tài)規(guī)劃； 分配； 定價

中圖分類號： TN911?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）21?0159?05

A virtual machine allocation method based on dynamic planning

WANG Yan1， SUN Maosheng2， ZHU Junwu2， 3

（1. Center of Informatization， Xuzhou University of Technology， Xuzhou 221018， China；

2. School of Information Engineering， Yangzhou University， Yangzhou 225009， China；

3. Department of Computer Science and Technology， University of Guelph， Guelph NIG2K8， Canada）

Abstract： The dynamic allocation mechanism based on combination auction makes the cloud auctioneer allocate the cloud resource efficiently according to the market requirement， and brings high benefit for the auctioneer. The existing method uses the greed method to allocate the virtual machine resource， and allocates the resource for the high tender?density users optimally. Ho?wever this local optimal selection can′t bring the global optimal solution. A DP?VMPA （dynamic planning based virtual machine provision allocation） method is proposed， which takes the maximal social welfare as target function， uses CA?DP allocation algorithm to find out the obtained users set of resource. The VCG mechanism is used to price for the users. An application example shows that the DP?VMPA method can allocate the virtue machine resources efficiently， and bring a high benefit for the auctioneer.

Keywords： virtue machine； dynamic planning； allocation； pricing

0 引 言

當(dāng)下云拍賣商們大都使用基于固定價格機(jī)制的方法分配和賣出云資源，例如Windows Azure[1]和Amazon EC2[2]。顯然這種分配和定價體制有不少缺點(diǎn)，首先它不能保證資源的有效分配，那些對資源估價高的用戶并不總能如愿獲得請求資源，其次云拍賣商的利潤偏低[3?4]?；谂馁u的機(jī)制可以有效地解決如上問題，它權(quán)衡用戶請求的資源量及對資源的估價，決定對用戶的分配及定價。

拍賣機(jī)制分靜態(tài)拍賣和動態(tài)拍賣，靜態(tài)機(jī)制需要拍賣商提前供應(yīng)虛擬機(jī)資源并且不能改變資源量，動態(tài)拍賣下，拍賣商可以使用虛擬化技術(shù)，根據(jù)用戶需求量動態(tài)配置各類虛擬資源，并將它們按單位虛擬機(jī)實(shí)例賣出，保證資源的高效利用?，F(xiàn)有的方法大都使用貪婪算法[3?5]決定用戶的分配。它對用戶的投標(biāo)價值密度由高到低排序，在資源容量內(nèi)依次選擇價值密度高的投標(biāo)，將資源分配給用戶，這種啟發(fā)式的策略并不總能獲得最優(yōu)解。

通常WDP問題是個NP完全問題，可以對虛擬機(jī)供應(yīng)與分配問題VMPA進(jìn)行客觀描述，給出目標(biāo)函數(shù)，然后使用基于組合拍賣的動態(tài)規(guī)劃算法（CA?DP Allocation Algorithm）求出分配最優(yōu)解。DP算法是先把問題分成多個子問題（一般地，每個子問題是互相關(guān)聯(lián)和影響的），再依次研究逐個問題的決策。動態(tài)規(guī)劃方法設(shè)計(jì)算法的主要思路使用最優(yōu)性原理找出遞推關(guān)系， 再找最優(yōu)決策序列。定價方案上采用基于最優(yōu)分配的VCG（Vickrey?Clarke?Groves）機(jī)制，即用分配給該用戶的資源對其余用戶的社會損失給其定價。

本文根據(jù)虛擬機(jī)分配問題的目標(biāo)函數(shù)，提出DP?VMPA Mechanism （Dynamic Programming Mechanism that solves VMPA problem），采用CA?DP allocation algorithm解決分配問題，同時使用VCG定價機(jī)制決定用戶的支付。這個機(jī)制能保證資源的有效利用，并為提供商帶來更高的利潤。

1 相關(guān)工作

Zaman等人首先詳細(xì)介紹了基于固定價格的分配機(jī)制[3]，然后提出兩種基于拍賣的靜態(tài)虛擬機(jī)分配機(jī)制CA?GREEDY機(jī)制和CA?LP機(jī)制，并將它們與Fixed?Price機(jī)制比較，相比于固定價格機(jī)制，基于拍賣的機(jī)制能更有效地分配虛擬機(jī)資源，提高拍賣商利益。CA?LP機(jī)制在分配資源和增大收益方面表現(xiàn)突出，CA?GREEDY機(jī)制因其快速有效的分配性能被廣泛認(rèn)可。文獻(xiàn)[4]中，拍賣商結(jié)合虛擬化技術(shù)對資源實(shí)現(xiàn)動態(tài)配置，使用CA?PROVISION機(jī)制分配虛擬機(jī)資源。本文嘗試將此機(jī)制與靜態(tài)分配下的CA?GREEDY機(jī)制比較，實(shí)驗(yàn)表明，動態(tài)分配下，拍賣商根據(jù)市場需求動態(tài)供應(yīng)資源，可以保證資源的高效利用，增大拍賣商的利潤。它還通過設(shè)置保留價格進(jìn)一步提升拍賣商的收益。文獻(xiàn)[6]提出一種有效投標(biāo)策略，幫助云計(jì)算用戶生成最佳投標(biāo)（請求的虛擬機(jī)資源組合和對這組資源的估價）。這種投標(biāo)策略能夠幫助用戶高效地完成云計(jì)算任務(wù)，提高執(zhí)行效用。資源的有效利用也使得拍賣商收益增加。Nejad在文獻(xiàn)[5]中提出動態(tài)虛擬機(jī)資源的啟發(fā)式貪婪分配算法，它詳細(xì)描述了用戶對多類虛擬機(jī)資源CPU、內(nèi)存和容量的請求數(shù)量，然后根據(jù)各類資源稀缺性參數(shù)重新定義價值密度，按貪婪算法進(jìn)行資源分配。文獻(xiàn)[3?5]均采用貪婪法分配資源，貪婪法一步步的構(gòu)造局部最優(yōu)解，使得最終分配解保持可行性且能產(chǎn)生較大效益。

Garfinkel提出了集分割算法解決組合拍賣下的分配問題[7]；Nisan將Winner集決定問題表示成一個標(biāo)準(zhǔn)的混合整數(shù)規(guī)劃問題[8]，提出使用商用軟件和一些簡單算法求解該問題。Sandholm在文獻(xiàn)[9]提出使用軟件CPLEX可以高效地解決WDP問題，使資源充分利用。Fujisima推薦CASS軟件來處理更大規(guī)模的WDP[10]。將組合拍賣下的分配借助各類軟件的整數(shù)規(guī)劃實(shí)現(xiàn)，這是完全可行的，不過這些軟件無法用算法描述，另外它們只能給出最優(yōu)分配集合，對用戶的定價問題卻無法解決。文獻(xiàn)[11]在眾包分配與定價問題中介紹了4種可行的機(jī)制：OPT，GREEDY，VCG和TruTeam，并通過實(shí)驗(yàn)比較各個機(jī)制，得出結(jié)論VCG機(jī)制和TruTeam機(jī)制均能高效利用資源，同時證明其滿足個體理性和真實(shí)性。

2 動態(tài)虛擬機(jī)供應(yīng)與分配問題

通過虛擬化技術(shù)的應(yīng)用，云計(jì)算提供商可以將計(jì)算資源動態(tài)配置成任意類型的虛擬機(jī)組合。一個云拍賣商向用戶提供[m]類虛擬機(jī)實(shí)例資源，[VM1，VM2，…，][VMm。]虛擬機(jī)類型[VMi]的計(jì)算能力表示為[wi，]其中[w1]=1，[w1

考慮有[n]個用戶[u1，u2，…，un]向云提供商請求虛擬機(jī)。用戶[uj]向拍賣商提交一組投標(biāo)[Bj=（rj1，…，rmj，vj），]其中[rij]是請求的虛擬機(jī)[VMi]的數(shù)量，[vj]是單位時間內(nèi)用戶[j]得到虛擬機(jī)愿意最大支付的金額。拍賣商階段性的組織拍賣分配虛擬機(jī)，一單位時間即這輪拍賣的拍賣商的分配與定價決策到下輪拍賣的決策之間的時間間隔。為了定義云提供商獲得的利益，定義[P={p1，p2，…，pn}，]其中用[pj]表示用戶[j]獲得請求的資源時需要支付的金額，通常小于[vj]；將分配問題的解定義為[x=（x1，x2，…，xn）]，分配向量中的元素[xj∈{0，1}，][xj=1]表示用戶[j]得到虛擬機(jī)組合，反之[xj=0]表示用戶未得到；集合[W=uj1≤j≤n，xj=1]作為投標(biāo)勝利用戶集。[sj=][i=1mwirij]表示用戶[uj]請求的單位計(jì)算資源的數(shù)量，其中單位資源也就是一個[VM1]類型的虛擬機(jī)實(shí)例。

定義1：動態(tài)虛擬機(jī)供應(yīng)與分配問題可以形式化描述為：

[maxj=1nxjpj]

[s.t. j=1nxjsj≤Mxj∈0，10≤pj≤vj]

式中：約束條件（1） 表明成功投標(biāo)的用戶請求的虛擬機(jī)資源總量不得超過拍賣商所擁有的資源量；式（2）表示規(guī)定分配向量[xj]的取值范圍；式（3）表示此不等式保證用戶的支付金額不超過用戶對其請求資源的最大估價，也就是確保用戶的效用[Uj=vj-pj]不為負(fù)。組合拍賣的最優(yōu)方案應(yīng)該是最大化云拍賣商的利益，但很難找出一個客觀函數(shù)描述它，通常尋找最大化社會總福利（成功獲得虛擬機(jī)資源的用戶投標(biāo)總價值）作為解決組合拍賣問題的方案。這種分配方案決定了拍賣商對每類虛擬機(jī)的配置，計(jì)算[ki=j=1nxjrij，]即[VMi]類虛擬機(jī)需要供應(yīng)的數(shù)量為[ki]。

定義2：真實(shí)的（Truthful， Incentive Compatible）假定任意用戶[j]其在真實(shí)報價情形下獲得的效用為[u1，]任意虛假報價下獲得的效用為[u2，]若給定機(jī)制中[u1-u2≥0，]則稱該機(jī)制是Truthful的。即用戶只有通過向機(jī)制提交真實(shí)的估價，他才能獲得最大效用。真實(shí)性使得用戶在投標(biāo)決策時不需考慮復(fù)雜的投標(biāo)策略，更不需考慮其他用戶的投標(biāo)方案。

定義3：個體理性（Individual Rationality），即在一機(jī)制中，對每個用戶[j]，用戶的效用[Uj=vj-pj]大于等于0，則稱用戶[j]是個體理性的。

3 基于組合拍賣的動態(tài)虛擬機(jī)供應(yīng)與分配機(jī)制

本文提出的DP?VMPA Mechanism決定了獲得虛擬機(jī)的Winner用戶集和這個集合中每個用戶的定價。這種組合拍賣機(jī)制能有效分配虛擬機(jī)資源，為拍賣商帶來更高的收益（Efficient）。

Algorithm 1：DP?VMPA Mechanism

Input：[M；m；wi：1，…，m；]

Output：[W；P；ki：1，…，m；]

1.{phase： Collect [Bids]}

a.Initialize [BNΦ]

b.For [j]=[1，2，…，n，]

Collect bid [Bj=（rj1，…，rjm，vj）] from user [uj]

c.[BNBN?{Bj}]

2.{phase 2： Winner Determination and Provision}

（[W，][BestValue]） = CA?DP（[BN，][M]） //Algorithm 3

For [i=1，…，m，]

[kij：uj∈Wrij]

3.{phase 3：[Payment]}

For all [j∈W]

（[W，][BestValue]） = CA?DP（[BN-{uj}，][M]） //Algorithm 3

[pjBestValue-（BestValue-vj）]

For all [j?W，]

[pj0]

Return （[W；P；ki：1，…，m]）

動態(tài)規(guī)劃求解虛擬機(jī)供應(yīng)與分配機(jī)制（DP?VMPA）如上，機(jī)制被云提供商階段性的調(diào)用，運(yùn)行該機(jī)制需要提供三個輸入?yún)?shù)：虛擬機(jī)資源總量[M，]虛擬機(jī)的類型數(shù)量[m]和相應(yīng)的虛擬機(jī)權(quán)重[wi，]輸出三個參數(shù)：成功獲得虛擬機(jī)資源的用戶集合[W，]用戶支付向量[P]以及提供商對每類虛擬機(jī)的供應(yīng)數(shù)量[ki]。

動態(tài)規(guī)劃機(jī)制也分為三個階段。第一階段，拍賣商收集用戶的投標(biāo)，所有用戶的投標(biāo)構(gòu)成集合[BN。]第二階段使用動態(tài)規(guī)劃分配算法（算法3給出CA?DP分配算法）決定獲得資源的Winner集合，求出該集合下產(chǎn)生的最大社會總價值[BestValue]，同時決定出拍賣商的虛擬機(jī)供應(yīng)方案。第三階段，使用VCG機(jī)制求出Winner集合每個用戶應(yīng)當(dāng)支付的金額，即用戶[j]不參與拍賣所能得到的最大價值總和減去用戶[j]參與拍賣并獲得資源時其他用戶的價值量總和，未獲得虛擬機(jī)的用戶支付量為0。

Algorithm 2： CA?DP allocation algorithm

Input：[BN，M]

Output：[W，BestValue]

1.Initialize [BNΦ，nsize（BN），] [bestValues[n+1][M+1]]

2.For [j=0，1，…，n，]

[sji=1mwirij]

For [h=0，1，…，M，]

If [h=0j=0] then [bestValues[i][j]0]

Else

If [sj>h]then [bestValues[j][h]bestValues[j-1][h]]

Else[bestValues[j][h]][max{bestValues[j-1][h]，bestValues[j-1]]

[[h-sj]+vj}]

3.[hM]

4.For [j]=[n，…，1]

If [bestValues[j][h]>bestValues[j-1][h]]

then [WW?{uj}，][hh-sj]

5.[BestValuebestValues[n][M]]

Return （[W，][BestValue]）

基于組合拍賣的動態(tài)規(guī)劃分配算法如上所述，該算法需要提供兩個參數(shù)，即所有參與投標(biāo)的用戶集合[BN]和虛擬機(jī)資源總量[M。]運(yùn)行算法可以得到兩個值，即最優(yōu)分配下的投標(biāo)成功用戶集合[W]和對應(yīng)的最大估價之和BestValue。

組合拍賣問題的最優(yōu)解結(jié)構(gòu)：可以將組合拍賣分配問題的求解過程看作是進(jìn)行一系列的決策過程，即決定哪些用戶應(yīng)該獲得虛擬機(jī)資源，哪些用戶不該獲得請求資源。如果一個問題的最優(yōu)解包含了用戶[n]，即[xn=1，]那么其余[（x1，x2，…，xn-1）]一定構(gòu)成子問題1，2，[…]，[n-1]在云提供商擁有虛擬機(jī)資源為[M-sj]時的最優(yōu)解。如果這個最優(yōu)解不包含物品[n]，即[xn=0，]那么其余[（x1，x2，…，xn-1）]一定構(gòu)成子問題1，2，[…]，[n-1]在資源量為[M]時的最優(yōu)解。

那么根據(jù)上述分析的最優(yōu)解的結(jié)構(gòu)性質(zhì)，遞歸地定義問題最優(yōu)解。[bestValues[j][h]]表示虛擬機(jī)資源量為[h]時，前[j]個用戶導(dǎo)致的最優(yōu)解的總價值，那么總有：

[bestValues[j][h]=bestValues[j-1][h]，sj>hmaxbestValues[j-1][h]， bestValues[j-1][h-sj]+vj，sj≤h]

當(dāng)用戶[j]請求的資源量大于[h]時，[bestValues[j][h]]由虛擬機(jī)資源量為[h]時，前[j-1]個用戶最優(yōu)解的總價值決定；當(dāng)用戶[j]請求的資源量不大于[h]時，通過比較不允許[j]獲得資源的總價值[bestValues[j-1][h]]和允許[j]獲得請求的資源產(chǎn)生的總價值[bestValues[j-1][h-sj]+vj]，總價值高的作為[bestValues[j][h]]的最優(yōu)解價值。顯然最終要求的是[bestValues[j][h]]。

求出最優(yōu)解下的總價值后，可以通過回溯找出所有成功獲得虛擬機(jī)資源的用戶，即通過比較虛擬機(jī)資源量為[h]時，前[j-1]個用戶最優(yōu)解的總價值[bestValues[j-1][h]]和虛擬機(jī)資源量為[h]時，前[j]個用戶最優(yōu)解的總價值[bestValues[j][h]]，來得出用戶[j]能否獲得請求資源?；厮菪枰獜腫j=n]，[h=M]處開始，直至[j=1]，[h=0，]并將結(jié)果保存在集合[W]中。

命題1 DP?VMPA機(jī)制的時間復(fù)雜度為[O（nnM）]

證明：CA?DP分配算法中遞歸求最優(yōu)解，使用兩個for循環(huán)對[j=0，1，…，n]和[h=0，1，…，M]下每種狀態(tài)求出最優(yōu)解，時間復(fù)雜度為[O（nM），]回溯法求投標(biāo)成功用戶集合[W]只需遍歷一個for循環(huán)，其時間復(fù)雜度為[O（n），]總共時間復(fù)雜度為[O（nM）]。使用VCG機(jī)制對Winner集中每個用戶求支付金額，對每個用戶需要調(diào)用CA?DP分配算法，最壞時間復(fù)雜度為[O（nnM）]。

命題2 DP?VMAP機(jī)制是Truthful的

證明：證明真實(shí)性（Truthful），首先證明其分配單調(diào)性（Monotone），即用戶可以通過增大對請求的虛擬機(jī)組合的估價[vj]，或者減少請求的虛擬機(jī)資源總量[sj]來增加獲得請求資源的幾率，所以說機(jī)制是單調(diào)性的。

其次證明支付金額為臨界價格（Critical Value），動態(tài)規(guī)劃機(jī)制求出分配最優(yōu)解的前提下，使用VCG機(jī)制對投標(biāo)成功的用戶定價，用戶[j]不參與拍賣所能得到的最大價值總和減去用戶[j]參與拍賣時其他用戶的價值量總和，求出的支付金額[pj]是臨界價值。

命題3 DP?VMAP機(jī)制滿足個體理性

證明：對獲得資源的每個用戶[pj=BestValue-][（BestValue-vj），]因?yàn)閯討B(tài)規(guī)劃基于最優(yōu)分配，所以公式中[bestValue≤bestValue，]即證[Uj=vj-pj=bestValue-][bestValue≥0]。未獲得虛擬機(jī)的用戶[Uj=0，]所以綜上機(jī)制滿足個體理性。

4 應(yīng)用案例及分析

假定[n=4，][M=8，]4個用戶的請求虛擬機(jī)數(shù)量和報價：（3，3），（2，4），（4，1），（1，2），[bestValue[j][c]]取值如表1所示（[j=]0或[c=0，][bestValue[j][c]]=0）。

時間復(fù)雜度：基于組合拍賣的動態(tài)規(guī)劃分配算法中，根據(jù)最優(yōu)解結(jié)構(gòu)性質(zhì)，對[j∈[0，n]]和[c∈[0，M]]每種狀態(tài)下使用遞歸式求出最優(yōu)解，使用兩個for循環(huán)，其時間復(fù)雜度為[O（nM）]?；厮莘ㄇ笸稑?biāo)成功用戶集合[W]只需遍歷一個for循環(huán)，其時間復(fù)雜度為[O（n），]總共時間復(fù)雜度為[O（nM）]。

空間復(fù)雜度：動態(tài)規(guī)劃求最優(yōu)解需要構(gòu)造（n+1）×（[M+1]）的二維數(shù)組，用于存儲[（j，c）]下的最大價值[bestValue[j][c]，]空間復(fù)雜度為[O（nM）]。

5 結(jié) 論

為了解決虛擬機(jī)動態(tài)分配問題，提出一種基于動態(tài)規(guī)劃的虛擬機(jī)分配機(jī)制。這種機(jī)制以最大社會福利為目標(biāo)函數(shù)，遞歸求解最優(yōu)分配下的用戶集，并使用VCG機(jī)制對用戶資源定價。DP?VMPA機(jī)制能夠使更多的用戶完成應(yīng)用，高效利用虛擬機(jī)資源，明顯增大了拍賣商的收益。這個機(jī)制時間復(fù)雜度較高，不建議對大規(guī)模用戶參與的虛擬機(jī)分配問題使用該機(jī)制，后續(xù)工作將圍繞對CA?DP分配函數(shù)進(jìn)行優(yōu)化處理，并對VCG機(jī)制進(jìn)行改進(jìn)，使得定價機(jī)制更加簡易高效。

參考文獻(xiàn)

[1] Microsoft. Windows azure platform [EB/OL]. [2015?09?11]. http：///windowsazure/.

[2] Amazon. Amazon elastic compute cloud （Amazon EC2） [EB/OL]. [2016?01?17]. http：///ec2/.

[3] ZAMAN S， GROSU D. Combinatorial auction?based allocation of virtual machine instances in clouds [J]. Journal of parallel and distributed computing， 2013， 73（4）： 495?508.

[4] ZAMAN S， GROSU D. Combinatorial auction?based dynamic VM provisioning and allocation in clouds [C]// Proceedings of 2011 Third IEEE International Conference on Cloud Computing Technology and Science. [S.l.]： IEEE， 2011： 107?114.

[5] NEJAD M M， MASHAYEKHY L， GROSU D. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds [J]. IEEE transactions on parallel & distribu?ted systems， 2014， 26（2）： 594?603.

[6] ZAMAN S， GROSU D. Efficient bidding for virtual machine instances in clouds [C]// Proceedings of 2011 IEEE International Conference on Cloud Computing. [S.l.]： IEEE， 2011： 41?48.

[7] GARFINKEL R S， NEMHAUSER G L. The set partitioning problem： set covering with equality constraints [J]. Operations research， 1969， 17（5）： S40?S47.

[8] NISAN N. Bidding and allocation in combinatorial auctions [C]// Proceedings of 2000 2nd ACM Conference on Electronic Commerce. New York： ACM， 2001： 1?12.

[9] SANDHOLM T. Algorithm for optimal winner determination in combinatorial auctions [J]. Artificial intelligence， 2002， 135（1/2）： 1?54.

篇(7)

Abstract： In this paper， cascade reservoirs flood control scheduling optimization model is constructed， M method is used to simulate the water flow state of cascade reservoirs. This model is an aftereffect dynamic programming model. This paper discusses the corresponding method， points out a kind of multi-dimensional dynamic programming recursive solution. And the instance analysis shows that the model has certain scientific nature， the results of it are representative， the calculation method by the discussion is quick， and the maneuverability is strong. It is a kind of high efficient calculation model and calculation method.

關(guān)鍵詞：梯級水庫；優(yōu)化調(diào)度；動態(tài)模型；規(guī)劃；求解

Key words： cascade reservoir；optimal operation；dynamic model；programme；solve

中圖分類號：TV622 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2016）01-0219-03

0 引言

當(dāng)前，中國已經(jīng)建有各種水庫8.6萬個，大規(guī)模水庫482個，中規(guī)模水庫3000個。中國的大部分水庫并不是獨(dú)立的個體，而是融入梯級水庫群里，可謂聯(lián)系緊密。在梯級開發(fā)的流域內(nèi)修筑一個新的建筑抑或采取一類防洪舉措，都能對梯級水庫群帶去一定的改變。梯級水庫構(gòu)建完成以后，河流洪水的特征以及區(qū)域構(gòu)成都將產(chǎn)生改變，特別是在上游擁有調(diào)水功能的水庫，洪水的時間、空間分布將產(chǎn)生顛覆性的改變。在工程的防洪設(shè)計(jì)的同時，假如工程上游擁有調(diào)水以及蓄水能力較強(qiáng)的業(yè)已修建完成抑或近段時間就要修建完成的梯級水庫抑或梯級水庫群，就要權(quán)衡到水庫調(diào)節(jié)洪水的功用與對下游設(shè)計(jì)斷面的作用。假如設(shè)計(jì)規(guī)劃針對的是洪水調(diào)節(jié)功能健全的水庫建筑，而且要擔(dān)負(fù)下游防洪的職責(zé)；那必須研討該建筑對下游防洪的效益。

1 水庫防洪任務(wù)和目標(biāo)

通常情況下，水庫在汛期遇到洪水的時候防洪要分成三種：一種是工程自身的防洪需要，通常用壩前水位顯示；一種是庫區(qū)防洪需求，通常是由于庫區(qū)淹水抑或庫尾回水而引發(fā)，淹水范疇和水庫壩前水位、入庫流量相關(guān)，在庫區(qū)防洪標(biāo)準(zhǔn)既定的情況下（相應(yīng)的入庫規(guī)劃洪水給定），庫區(qū)防洪也由壩前水位顯示；一種是擔(dān)負(fù)下游防洪區(qū)的防洪工作，一般是以河道安全泄洪量標(biāo)識，抑或依照堤防安全高程和水位流量的相關(guān)數(shù)據(jù)，核算出河道安全流量。

并且，水庫自身的防洪功能在全部水庫中都能夠體現(xiàn)，在上述三種防洪需求中，下游防洪工作應(yīng)讓水庫盡可能頻繁削峰，阻攔或儲蓄洪水；庫區(qū)以及大壩防洪需求，需要水庫盡可能下泄，讓壩前水位下降，保護(hù)水庫庫區(qū)淹水導(dǎo)致的財物耗損；并且騰出防洪庫容，用來調(diào)蓄后續(xù)洪水。所以，兩者有著一定的矛盾；另外，防洪級別不一而足，下游以及庫區(qū)的防洪準(zhǔn)則比大壩防洪準(zhǔn)則要寬松，然而下游以及庫區(qū)防洪標(biāo)準(zhǔn)孰高孰低，要根據(jù)實(shí)際狀況確定。進(jìn)而為明確防洪需求孰先孰后、調(diào)整防洪需求以及防洪和發(fā)電功能的發(fā)揮奠定了基礎(chǔ)。

2 水庫防洪調(diào)度現(xiàn)狀分析

2.1 傳統(tǒng)水庫防洪調(diào)度策略

常規(guī)調(diào)度方法是一種半經(jīng)驗(yàn)和半理論的方法，借助水庫的防洪能力圖、防洪調(diào)度圖等經(jīng)驗(yàn)性圖表進(jìn)行調(diào)度。具體來講，目前主要有以下調(diào)度策略：

①最大削峰標(biāo)準(zhǔn)。

就是說：洪峰流量要盡可能縮減。

②最小災(zāi)害肆虐時間標(biāo)準(zhǔn)。

就是說：防洪管控截面流量越過允許范疇內(nèi)的安全流量的時間盡可能縮短。

③最強(qiáng)防洪安全標(biāo)準(zhǔn)。

就是說：在迎合下游防洪管控截面安全泄量的前提下，盡量下泄，以保存防洪庫容，預(yù)防以后更大規(guī)模洪水的侵襲。

①與②把下游防洪需求放在非關(guān)鍵位置，所以使用在大規(guī)模洪峰過境的情況；③則應(yīng)用在小型洪水的排泄中。

2.2 存在的問題

傳統(tǒng)調(diào)度策略主要是將線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等應(yīng)用于水庫防洪調(diào)度中。這些防洪調(diào)度技術(shù)為水庫防洪調(diào)度提供了一種解決辦法，但是難以適應(yīng)實(shí)時防洪形勢的變化，并且難以模擬調(diào)度人員的經(jīng)驗(yàn)知識。并且傳統(tǒng)調(diào)度方法未能徹底解決以下幾個矛盾：

①設(shè)計(jì)與實(shí)際運(yùn)用不相適應(yīng)的矛盾。

運(yùn)行階段由于水文資料的積累，特別是發(fā)生了幾次特大洪水以后，人們對本流域水文規(guī)律認(rèn)識加深。將運(yùn)行后的資料加入原設(shè)計(jì)所依據(jù)的水文系列，導(dǎo)致洪水統(tǒng)計(jì)參數(shù)有了明顯變化，因而設(shè)計(jì)洪水也有變化。如按原設(shè)計(jì)確定的汛限水位進(jìn)行洪水調(diào)節(jié)計(jì)算，最高庫水位超過了原設(shè)計(jì)最高洪水位，則說明原設(shè)計(jì)標(biāo)準(zhǔn)偏低。

②水庫本身安全與下游防洪安全的矛盾。

這是水庫汛期控制運(yùn)用的主要任務(wù)。當(dāng)水庫上、下流域普降大暴雨，水庫本身防洪安全與下游防洪安全的矛盾非常突出，具體表現(xiàn)為從下游防洪出發(fā)，要求水庫多蓄水、少泄水，而從水庫安全出發(fā)則要求水庫水、多泄水。解決這一問題的關(guān)鍵在于：分析矛盾，掌握規(guī)律，研究預(yù)報，確定出水庫何時開閘，泄流量多大，何時關(guān)閘等一套合理的蓄泄原則。在汛期按照預(yù)定的泄流方式調(diào)度水庫時應(yīng)達(dá)到如下要求：如果某次洪水與下游防洪標(biāo)準(zhǔn)相當(dāng)，則應(yīng)保證下游河道的泄流量在允許安全泄量以下或相等；如果某次洪水與原設(shè)計(jì)或校核洪水相當(dāng)，則水庫調(diào)洪最高水位以不超過設(shè)計(jì)或校核洪水位為原則；如果某次洪水為可能最大洪水，亦應(yīng)采取有效措施確保大壩安全。

③防洪與興利的矛盾。

我國北方年降水大部分集中在汛期，而汛期內(nèi)降水又集中于幾場暴雨。為了水庫防洪安全，整個汛期庫水位降的較低，不敢蓄水，導(dǎo)致許多水庫，尤其是北方以灌溉、供水、發(fā)電為主的大型多年調(diào)節(jié)水庫，汛后無水可蓄。解決防洪與興利矛盾的關(guān)鍵是對未來水文規(guī)律的了解和預(yù)測， 如果對未來的來水情況能夠準(zhǔn)確預(yù)測，水庫的調(diào)度運(yùn)用就變得簡單，防洪與興利的矛盾就會迎刃而解。但是目前中長期水文預(yù)報還不可靠，未達(dá)到可利用的程度，防洪與興利的矛盾將長期存在，伴隨著整個防洪調(diào)度過程。

3 梯級水庫防洪優(yōu)化調(diào)度模型

權(quán)衡到如圖1中的梯級水庫防洪調(diào)度疑問。

水庫1與水庫2不但要滿足施工自身的防洪需求，還要權(quán)衡到庫區(qū)鐵道防洪需求以及下游縣級市的防洪需求。如果上游水庫1入庫洪水流程能夠測出，兩個水庫間的洪水流程也能夠預(yù)先知道，在迎合下游縣級市防洪需求的基礎(chǔ)上，以兩水庫聯(lián)手調(diào)節(jié)和儲蓄一段洪水時的調(diào)洪庫容最小化為優(yōu)化標(biāo)準(zhǔn)，找到洪水在體積水庫的最合適時段以及空間調(diào)配方法，就是說訂立兩水庫的最優(yōu)防洪調(diào)度模式。

假定3小時為單位時限，將洪水流程分成T個時段（t=1，2，…，T），I1t以及ILt分別顯示上游水庫入庫洪水流程以及區(qū)間洪水流程；O1t以及O2t則分開顯示水庫出庫流量；V1.t+1以及V2.t+1則是第t時間段末庫容，構(gòu)建下面的數(shù)學(xué)模型。

3.1 目標(biāo)函數(shù)

梯級水庫調(diào)用的總調(diào)洪水庫容極小值是：

通過這樣的處置以后，能夠看到：動態(tài)規(guī)劃順序遞推法求解梯級水庫防洪調(diào)度模型，這類換算辦法筆者將其叫做簡易化二維動態(tài)規(guī)劃算法；換算的難度稍微增長，然而換算量沒有顯著提升。

5 案例分析

5.1 案例概述

以漢江流域某個梯級水庫防洪調(diào)度情況為例子，這兩個梯級水庫一個是季調(diào)節(jié)能力水庫，一個是不完全年調(diào)節(jié)能力水庫，核定洪水位下的防洪庫容不大，對100年才遭遇一次抑或之下的洪水，這個梯級水庫洪區(qū)區(qū)域構(gòu)成是上游、區(qū)間、全流域型三種，以第三類為防洪重點(diǎn)。

5.2 水庫防洪優(yōu)化調(diào)度過程

針對50年一遇的洪水，在汛期來臨前運(yùn)用上述優(yōu)化調(diào)度模型對該梯級水庫進(jìn)行全流域優(yōu)化調(diào)度后，對洪峰及洪水流量進(jìn)行了有效的調(diào)節(jié)，圖2即為洪水來臨時洪水和調(diào)節(jié)后的出庫流量流程。

從圖2看出，第一時段的洪水來臨的時候應(yīng)適度增大泄量預(yù)泄，騰出一些庫容，本時段重點(diǎn)是看洪水入庫的時候水庫的起調(diào)水位；第二時段應(yīng)管控水庫泄量，該時段重點(diǎn)是水庫應(yīng)管控泄流量多寡，其呈現(xiàn)出了蓄水以及防水的沖突抑或庫區(qū)防洪和下游防洪需求的沖突，是一類高層級協(xié)調(diào)課題；第三時段――水庫水位消落，其重點(diǎn)是水庫泄流量多寡，它對水庫水位的消落速率有極大影響。而且，以上游水庫出庫流量多寡最為關(guān)鍵――當(dāng)產(chǎn)生區(qū)間抑或全流域型洪水的時候，要由上游水庫攔擋洪水再騰出庫容。

5.3 優(yōu)化調(diào)度效果

總的來說，未調(diào)節(jié)前，該汛期出現(xiàn)了2個洪峰，出庫水量巨大，使得下游面臨非常大的防空壓力。對汛期洪水進(jìn)行優(yōu)化調(diào)度后，在庫區(qū)只出現(xiàn)了1個洪峰，并且出庫水量始終在可控范圍內(nèi)，大大減輕了下游的防洪壓力。

6 結(jié)束語

綜上，利用上面列出的算式，能夠?qū)μ菁壦畮旆篮閮?yōu)化調(diào)度的動態(tài)規(guī)劃給出有建設(shè)性的意見；而通過兩庫聯(lián)手調(diào)節(jié)洪水的模式，能夠極有成效地管控洪峰，并且能夠優(yōu)化梯級水庫布局，保護(hù)沿河流域的居民生命財產(chǎn)安全。

參考文獻(xiàn)：

[1]原文林，吳澤寧，黃強(qiáng)，等.梯級水庫短期發(fā)電優(yōu)化調(diào)度的協(xié)進(jìn)化粒子群算法應(yīng)用研究[J].系統(tǒng)工程理論與實(shí)踐，2012，32（5）：1136-1142.

[2]楊侃，鄭姣，郝永懷，等.三角函數(shù)選擇算子的遺傳算法在梯級水庫優(yōu)化調(diào)度中的應(yīng)用[J].天津大學(xué)學(xué)報，2012，45（2）：167-172.

[3]周興波，陳祖煜，黃躍飛，等.特高壩及梯級水庫群設(shè)計(jì)安全標(biāo)準(zhǔn)研究Ⅲ：梯級土石壩連潰風(fēng)險分析[J].水利學(xué)報，2015（7）：765-772.

[4]周建平，王浩，陳祖煜，等.特高壩及其梯級水庫群設(shè)計(jì)安全標(biāo)準(zhǔn)研究Ⅰ：理論基礎(chǔ)和等級標(biāo)準(zhǔn)[J].水利學(xué)報，2015（5）：505-514.