動態規劃思想范文

導語：如何才能寫好一篇動態規劃思想，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務員之家整理的十篇范文，供你借鑒。

篇1

關鍵詞：萬州、生態涵養規劃、多規協同

中圖分類號： G322 文獻標識碼： A

0 引言

2013年9月13日至14日，重慶市委四屆三次全會召開。會議審議通過了《關于科學劃分功能區域、加快建設五大功能區的意見》。渝東北地區被劃為生態涵養發展區，這個以三峽庫區為主的區域，面臨著新的發展要求。除了要實現生態涵養的要求，更有要實現社會經濟迅速發展，庫區社會和諧穩定的要求。渝東北生態涵養區各區縣都迅速提出了各自的生態涵養發展的思路與規劃，但是總體仍然是發展戰略性規劃，產業和社會經濟發展與環保要求居多。而區縣相對較小的地理空間，需要更具體的空間落地規劃和實施指導，不能夠簡單照搬重慶直轄市全域主體功能區劃分的方式來落實規劃意圖，而要探索以實施導向的區縣生態涵養規劃編制思路，引導規劃有效實施。本文結合萬州區生態涵養發展規劃編制的探索來進行分析。

1、渝東北生態涵養區的背景與要求

1.1背景

重慶首次將全域劃分為都市功能核心區、都市功能拓展區、城市發展新區、渝東北生態涵養發展區、渝東南生態保護發展區“五大功能區”，并根據各自定位，在產業布局、人口分布、生態建設等方面作出了調整。五個功能區域在更大的空間格局和區域范圍內優化資源配置，以更好地推動重慶大都市區的發展和建設；劃分生態涵養發展區和生態保護發展區，是為了正確處理加快發展與保護生態的關系；明確各區域功能定位、發展重點和發展方向，目的是強化五大區域聯動，更好地突出整體性、互補性和聯動性，實現全市一盤棋發展，引導形成主體功能明確、板塊之間聯動、資源配置優化、整體效能提升的區域一體化發展格局。在五個功能區域劃分基礎上，進一步完善考核機制，充分發揮考核評價的引導和激勵作用。

渝東北生態涵養發展區包含11個區縣，以萬州為核心，包括1個大城市（萬州），10個中小城市，196個小城鎮，面積約3.39萬平方公里。截止2011年底，該區域戶籍人口為1096萬人，常住人口為833萬人，城鎮人口為325萬人，城鎮化率為39.02%，城鎮人口占全市比重20.24%。該區域地區生產總值為1723.56億元，占全市域比重17.03%。該區域是國家重點生態功能區和農產品主產區，長江流域重要生態屏障和長江上游特色經濟走廊，長江三峽國際黃金旅游帶和特色資源加工基地。需要把生態文明建設放在更加突出的地位，引導人口相對聚集和超載人口梯度轉移，著力涵養保護好三峽庫區的青山綠水，提高基本公共服務水平。

1.2要求

在五大功能區的劃分中，也對渝東北生態涵養區提出了以下重點要求：

一是把萬州作為重點開發區加快建設，發展特色產業集群，承接周邊地區人口轉移，建成三峽庫區經濟中心，帶動形成萬（州）開（縣）云（陽）特色產業板塊。

二是增強梁平縣、豐都縣、墊江縣、忠縣、開縣等國家農產品主產縣農業綜合生產能力，推進縣城及市級特色工業園區開發，構建農產品特色經濟板塊。

三是增強城口縣、云陽縣、奉節縣、巫山縣、巫溪縣等國家重點生態功能縣生態產品供給能力，因地制宜發展資源環境可承載的特色產業，構建特色旅游經濟帶。

四是根據資源環境承載能力，培育壯大有資源依托、環保水平高、吸納就業多的特色優勢產業，重點發展特色資源加工、機械加工、輕紡食品、生物醫藥、清潔能源、商貿物流等。嚴格控制并逐步淘汰落后產業。大力發展特色效益農業。大力發展生態旅游、人文旅游，加快建成長江三峽國際黃金旅游帶，把旅游業打造成為支柱產業。

2 萬州生態涵養發展規劃編制的探索

2.1萬州生態涵養發展的基礎

萬州是重慶第二大城市，地處三峽庫區腹心。目前該流域內蘊藏著全國1/3的水資源和3/5的水能資源，擁有全國1/2的內河通航里程，是我國水資源配置的戰略水源地、實施能源戰略的主要基地、珍稀水生生物的天然寶庫、連接東中西部的“黃金水道”和改善我國北方生態與環境的重要支撐點，具有十分重要的戰略地位。萬州區幅員面積3457平方公里，境內山丘起伏，最高點海拔1760米，最低點海拔120米，中山、低山、丘陵面積占90%以上，少平壩和臺地，且零星散布。境內河流、溪澗切割深，落差大，呈枝狀分布，均屬長江水系。境內流域面積100平方公里以上的河流有共13條，溪溝93條，總水域面積為108.66平方公里。在不計基本農田的因素下，萬州全區適宜建設用地約為 71.1平方公里，較適宜建設用地約為 475.1 平方公里。萬州適合進行城市建設用地的承載力約為190萬人左右。通過GIS分析，得出鐵峰山、方斗山、七曜山以及長江沿線是低安全格局區域，是保障生態安全的最基本保障，是城市發展建設中不可逾越的生態底線，需要重點保護和嚴格限制。

2.2萬州生態涵養發展的總體思路與空間布局

規劃到2020年基本形成生態涵養發展的總體格局，功能區劃清晰，發展重點突出，特色鮮明，生態環境明顯好轉，對主要森林、水源、景區、生物多樣性保護較好，形成重點生態涵養保護區域的新發展態勢。形成以中心城區及各鎮鄉的合理城鎮體系結構，新農村聚居點為主的鄉村居住空間體系，人口分布更加科學，城鄉低碳綠色建設和宜居水平大幅提升?；窘ǔ沙青l一體化的公共服務設施和基礎設施體系。社會事業更加發展，文化內涵更加濃郁，實現“看得見山，望得見水，記得住鄉愁?！?/p>

全區生態涵養發展形成“一核、兩軸、多點”的重點開發空間格局，形成四帶五片保育與涵養的生態保護空間格局，總體形成開發與保護有機結合，城鄉空間一體的生態涵養發展的新空間結構。

一核 ―― 中心城區

兩軸 ――長江和318國道兩條重點發展軸線

多點 ―― 41個鎮鄉小城鎮和若干鄉村聚居區、特色產業項目、旅游、能源基地，圍繞各中心，與生態環境有機融合的點狀網絡結構

生態保護空間格局：

四帶――長江及沿線、鐵峰山脈、方斗山脈、七曜山脈等四片重點生態保障區

五片――甘寧龍沙武陵片、分水李河片、白羊太安片、龍駒羅田白土片、余家后山片等五片主要集中生態保育發展片區

圖1開發空間格局規劃圖

2.3萬州生態涵養發展功能區類型與空間布局

在全區生態安全格局分析基礎上，按照不同國土空間所承擔發展與涵養方面的不同特點與職責，宜建則建，宜養則養，將全區國土空間劃定為城市建設區、城鎮建設區、鄉村聚居區、農業保養區、生態保障區五類功能區域，對各類分區進行詮釋、定義，在不同功能區綜合落實城鄉建設規劃、土地利用規劃、生態環境保護規劃、社會事業發展規劃和產業空間布局規劃的主要要求，實現“五規合一”協同。

城市建設區以城市綜合發展為主，促進產業和社會事業充分發展，引導區域人口集聚，是最主要的城市生產生活空間。

城鎮建設區以城鎮特色發展為主，優化空間布局，緩解生境壓力，促進人口集聚，適度發展第二產業和商業服務業等第三產業，是主要的城鎮生活空間。

鄉村聚居區以農村人口聚居為主，新建與改造相結合，節約資源能源，提高人居環境質量，可適當發展鄉村旅游等第三產業，是主要的農村生活空間。

農業保養區以發展生態農業為主，引導人口有序轉移，主要發展特色農業、觀光休閑等產業，是主要的農業性生產空間

生態保障區以生態涵養為主，加強生態建設和環境保護，適當發展旅游度假等第三產業，是主要的生態空間。

2.4鎮鄉生態涵養涵養發展的引導與管控

對全區53個鎮鄉街道的國土空間結合其具體情況科學劃定功能區域，分別明確各區引導建設內容與禁止建設內容，既要充分發揮各鎮鄉資源優勢，又要落實區域生態環境建設、社會經濟發展的要求。部分鎮鄉街道擁有前述5類功能區，部分也只擁有其中的幾種。各鎮鄉街道規劃以發展規劃圖、生態涵養管控（負面清單）圖及發展管控說明（表）進行表達，如下圖案例。

圖2龍沙鎮生態涵養規劃圖

2.5規劃的實施與運用

本規劃探索實施的路徑。規劃提出經政協協商，黨委政府審議，人大審批后實施，嚴格執行，不得隨意調整或突破。對禁止性要求等要重點監督。原則上3年修編一次,修編前對實施情況應進行評估。具體建設時還應按照土地利用、城鄉規劃建設、環境保護等規劃的要求，相關法律法規規定及程序進行。

要求各鎮鄉街道要加強規劃的實施，在招商引資、項目選址等活動時要對照本規劃，作為宏觀指導要求。在城市規劃、小城鎮規劃、土地利用規劃等規劃進行動態調整時，要以本規劃作為中觀指導依據。項目審批時，要以本規劃作為具體的審批規劃依據。

同時也要加強生態補償機制的研究、制度設計與實施。探索完善生態涵養發展指標評價體系。

3 實施導向的區縣生態涵養發展規劃方法與思路

萬州生態涵養發展規劃的編制，在以下實施導向的重點編制思路與方法探索，為直轄市區縣主體功能區規劃向實施層面探索提供了有益的支撐。

3.1多規協同的規劃

生態涵養發展是區縣域發展思路的調整，空間布局的優化。而傳統的城鄉建設規劃、國土規劃、社會經濟發展規劃等各自引導著發展和項目實施。為了生態涵養發展規劃意圖的落實，就必須要協同各大規劃的重點要求，協調各大規劃在空間落地等方面的一些矛盾，在新的生態涵養發展思路下形成新戰略、新布局，同時又探索把生態涵養規劃的要求，反轉到城鄉建設規劃、國土規劃等傳統法定規劃的更新落實，實現動態的有機融合狀態。

3.2生態規劃要點把控

生態涵養發展規劃中“生態”是重點。而各規劃中涉及到的生態要素眾多，規劃綜合時既要考慮實現產業轉型、城鄉空間布局優化、生態環境保護等重大內容，更要重點關注關鍵生態要素的管控，主要有水源地及相關區域，集中林地，自然保護區，風景名勝區、森林公園、濕地等，石漠化、地災點等生態修復區域。規劃既要加強保護，也要通過人為的建設，形成更優的生態空間結構和發展應用模式。

3.3鎮鄉生態規劃的管控

鎮鄉是規劃實施的重要單元。當區縣城成為發展的重點區域，項目的建設、生產運行有較嚴格的控制。而鎮鄉成為生態涵養的重要空間，一是鎮鄉小城鎮發展中容易忽視環境類基礎設施建設，也是環境污染小企業的重點集聚地，人居環境較差。二是在農業生產過程中，不注重對生態意義重要的資源保護，部分農業、畜禽養殖等造成面源污染。本次規劃強化將各區域層面規劃意圖、法規要求結合鎮鄉實際情況，細化到每個鎮鄉街道空間，重點強調了生態管控的要素與要求，并以鎮鄉領導、管理者容易懂，便于使用的圖表方式來表達，明白每塊國土空間適合干什么，不能干什么，運用于發展戰略布局、招商引資等工作情況，大大增強實用性。

3.4 GIS的空間規劃疊加與分析

在規劃技術方法上，加強了GIS的空間規劃疊加與分析技術的應用。首先是GIS技術對全域生態本底進行分析，重點對山脈、水系、森林和需要控制的景源、地災點進行分析，結合地形坡度等進行分析，綜合評判生態安全格局，成為規劃研究的基礎。再者對各大規劃（如城規、國土、交通、環保等）的要求分解并轉化為空間發展布局或管控要素線，進行綜合疊加來推導方案，并與生態基礎分析疊加評估，增強了規劃的科學性。

3.5非法定規劃的實施應用探索

作為非法定規劃，其應用方式與保障路徑必須在規劃初期就應該設計好，才能夠保障有較強的實施性。關鍵點一是要通過黨委政府審議、人大審批等方式，獲得有類似準法定規劃的權威性，二是要設計好評估、檢查、監督機制，有一定獎懲的規則，以保障有足夠的實施自覺性。

篇2

【關鍵詞】動態規劃；高維；優化方法；渠道工程

目前，動態規劃的“維數災”問題受到計算機高速存儲量和計算時間的限制，在求解高維問題時，常遇困難.近40年來，各國學者對動態規劃的計算方法進行了多方面的探索，提出了各種方法，如旨在減少維數的拉格朗日乘子法[1]、動態規劃逐次漸近法[2]，聚合法[3]，旨在減少離散狀態數的離散微分動態規劃法[4]、雙狀態動態規劃法[5]、狀態增量動態規劃法[6]和不離散狀態直接求解以減少計算量的微分動態規劃[7]（要求目標函數、約束條件三階可微）以及H.R.Howson等人1975年提出的以減少階段數為手段的漸進優化法[7].這些方法雖然一定程度上減輕了“維數災”，但進展并不很大.作者在對大型渠道工程系統優化設計研究時也遇到了這些問題，本文另辟其徑，采用文獻[8～12]中的系統試驗選優基本思想，來求解高維動態規劃問題，則可在該領域內取得突破性的進展。

1. 大中型渠道工程優化設計的高維動態規劃模型及求解方法

1.1大中型渠道工程優化設計的高維動態規劃模型。文獻[13]提出了大中型渠道工程系統的定性定量混合系統動態規劃模型，模型的決策變量為各渠段縱坡（Ii）和各渠段的定性方案（Si），目標函數為工程計算分析期內的總支出費用，并考慮首末水位、不沖不淤、渠道最小水位銜接和工程總投資約束. 為了進一步提高模型決策的精度，在文獻[13]的模型基礎上，再考慮以下約束：

1.1.1填挖土方量約束。若獲得滿足約束條件，且使文獻[13]目標函數最小的解，而渠道工程的填方量大于挖方量，附近又沒有土方資源，此時文獻[13]中模型獲得的解就不一定為最優解，因此，還應加上填挖方量約束方程。

1.2求解方法?？紤]全部約束條件，則模型為四維問題，該模型的求解工作量、難度比文獻[13]的二維問題大大增加了，為此本文在模型的求解方面進行了一定的探討，提出了高維動態規劃的試驗選優方法。

1.2.1基本原理。本文對高維動態規劃的降維傳統技術之一——拉格朗日乘子法[1]進行了修正，提出了廣義拉氏方法，使加入到目標函數中去的約束檢驗在計算迭代過程中進行，而不是傳統的計算迭代結束后檢驗，因而不管拉格朗日乘子取值多少，采用廣義拉氏方法的解均為滿足約束條件的可行解.此時的問題就轉化為尋找最優拉氏乘子的問題，根據數學模型和拉氏乘子的物理意義，容易知道拉氏乘子的取值范圍，在此基礎上則可采用部分試驗選優方法[8～12]（如正交試驗法）確定最優的乘子值。

1.4實例分析。采用文獻[13]算例，有關主要參數和可能的定性方案見表1.通過計算分析u2，u3，u4的取值范圍均取為[0，2.4]，選用L9（34）型正交表對所選的9個uj組合進行了對應的一維動態規劃問題求解，其最優解和采用DDDP法求解結果目標值相差5.6%，對uj進一步離散選用L25（56）型正交表選擇對應25個uj組合進行對應的一維動態規劃問題求解分析，其最優解和采用DDDP法求解結果基本相同，此時占用計算機的運算時間不到DDDP法的1/6，有關計算主要成果摘要見表2和表3。

2. 結論

（1）尋求高維動態規劃的求解方法是近40年國內外眾多學者久攻不下的系統科學重大研究的課題.目前經典方法一般僅能求解3～5維問題，其它近似方法也只能求解數拾維問題.本文提出的試驗選優方法可以使較高維數的高維動態規劃問題求解成為可能.本文的試驗方法主要針對正交試驗法而言的，對于采用其它部分試驗選優方法進行優化分析，還有待于進一步探討。

（2）本文提出的大型渠道工程優化設計的高維動態規劃模型對大型調水工程優化設計具有較為重要的參考價值。

參考文獻

[1]Leon C， Mary W C.Introduction to Dynimic Programming.PergamonmPress， 1981， 197～207.

[2]Bellman R E， Dreyfus S E. Applied Dynamic Programming.Princeton Unversity Press， 1962， 293～3852.

[3]Turgeon A. A decomposition method for the long＼|term schednling of reservoirs in series. Water resources research， 1981，17（6）.

[4]Heidar M，Chow V T， et al. Disrete differential dynamic programming approach to water resource optimization.Water resources research， 1971，17（2）.

[5]Ozden M. A binary state DP algorithm for operation problem of multireservoir system. Water resource resecrch.1984，20（1）.

[6]Larson R E. State increment dynamic prorgamming.Management science 19， 1973，1452～1458.

[7]白憲臺，多維動態規劃.北京：水利電力出版社，1988，43～52.

[8]程吉林，金兆森，大系統模擬試驗選優方法及應用.水利學報，1993，（11）.

[9]程吉林，孫學華，模擬技術、正交設計、層次分析及其在灌區優化規劃中的應用.水利學報，1990，（9）.

[10]程吉林.某些特殊路徑問題的正交表法.系統工程，1991，（2）.

[11]程吉林.介紹一種大系統優化的知識模型.系統工程理論和實踐，1992，（4）.

[12]Jilin C， et al. Optimal test theory of large scale system and applying in irrigation district scheme.System science and system engineering，（ICCSSE'93）Edited by Zheng Weimin， International Academic Publishers Press， 1993， 348～356.

[13]Jilin C， et al. A dynamic programming medol of mixture system for conveyance canal engineering.Journal of system science and system engineering， 1993，4（2）.

[14]高侖彥.正交及回歸設計方法.北京：冶金工業出版社，1985.

[15]北京大學力學系概率統計組.關于正交設計的優良性.應用數學學報，1977，（1～2）.

篇3

動態規范是算法里一種非常重要的方法,是求解決策過程最優化的數學方法。動態規劃自問世以來,在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題,用動態規劃方法比用其他方法求解更為方便。

本文通過對經典的01背包問題的求解,從動態規劃的角度進行闡述,通過案例對該算法的計算過程進行了直觀的描述,并對該算法進行了一定的優化,最后指出該算法的優缺點。

[關鍵詞]背包 動態規劃 時間復雜度 空間復雜度

[中圖分類號]TP31[文獻標識碼]A[文章編號]1009-5349(2010)05-0121-03

前言

背包問題是一個經典的動態規劃模型,很多關于算法的教材都把它作為一道例題,該問題既簡單又容易理解,而且在某種程度上還能夠揭示動態規劃的本質。

將具有不同重量和價值的物體裝入一個有固定載重量的背包,以獲取最大價值,這類問題被稱為背包問題。

背包問題可以擴展出很多種問題,而01背包問題是最常見、最有代表性的背包問題。

一、問題描述

給定一個載重量為M的背包及n個物體,物體i的重量為wi、價值為pi,1≤i≤n,要求把這些物體裝入背包,使背包內的物體價值總量最大。此處我們討論的物體是不可分割的,通常稱這種物體不可分割的背包問題為01背包問題。

二、基本思路

01背包問題的特點是:每種物體只有一件,可以選擇放或者不放。假設:xi表示物體i被裝入背包的情況,xi=0,1。當xi=0時,表示物體沒有被裝入背包;當xi=1時,表示物體被裝入背包。根據問題的要求,有如下的約束方程(1)和目標函數(2):

三、利用動態規劃法求解01背包問題

(一)動態規劃算法的基本思想

動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中,可能會有許多可行解。每一個解都對應于一個值,我們希望找到具有最優值的解。動態規劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題,先求解子問題,然后從這些子問題的解得到原問題的解。與分治法不同的是,適合于用動態規劃求解的問題,經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題,則分解得到的子問題數目太多,有些子問題被重復計算很多次。如果我們能夠保存已解決的子問題的答案,而在需要時再找出已求得的答案,這樣就可以避免大量的重復計算,節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到,只要它被計算過,就將其結果填入表中,這就是動態規劃法的基本思路。具體的動態規劃算法多種多樣,但它們具有相同的填表格式。

(二)算法設計

假定背包的載重量范圍為0～m。類似于資源分配那樣,令optpi(j)表示在前i個物體中,能夠裝入載重量為j的背包所得的最大價值,j=1,2,……,m。顯然,此時在前i個物體中,有些物體可以裝入背包,有些物體不能裝入背包。于是,可以得到下面的動態規劃函數:

(4)式表明:把前面i個物體裝入載重量為0的背包,或者把0個物體裝入載重量為j的背包,得到的價值都為0。(5)式表明:當第i個物體的重量大于背包的載重量時,裝入前i個物體得到的最大價值,與裝入前i-1個物體得到的最大價值一樣,即第i個物體沒有裝入背包。(6)式表明:當第i個物體的重量小于背包的載重量時,如果第i個物體裝入背包,背包中物體的價值,等于把前i-1個物體裝入載重量為j-wi的背包所得到的價值與第i個物體的價值pi之和;如果第i個物體沒有裝入背包,則背包中物體的價值,等于把前i-1個物體裝入載重量為j的背包,卻不裝入第i個物體所取得的價值。顯然,這兩種裝入方法,在背包中所取得的價值不一定相同,因此,取這兩者中的最大值,作為把前面i個物體裝入載重量為j的背包所取得的最優價值。

該算法可分為n階段:

第一階段,只裝入一個物體,計算在不同載重量的背包情況下,所取得的最大價值;

第二階段,裝入前兩個物體,按(5)式和(6)式計算在不同載重量的背包情況下,取得的最大價值;

……

第n階段,裝入前n個物體,按(5)式和(6)式計算在不同載重量的背包情況下,取得的最大價值,而在背包載重量為M時,所得結果就是我們想要的結果。

為了確定具體哪個物體裝入背包,從optpn(m)的值向前倒推。有如下遞推關系式:

(7)式表明:如果optpi(j)大于optpi-1(j),則物體i被裝入背包;如果optpi(j)等于optpi-1(j),表明i物體未被裝入背包。按照該關系式,i從n到1依次類推,直到確定第一個物體是否被裝入背包為止,就能確定裝入背包的具體物體。

(三)存儲結構

該算法需要將每一個物體的重量和價值分別存儲起來,并針對不同載重量的背包對物體分別計算,故考慮使用數組來實現。對于物體i,用weight[i]來表示重量、用p[i]表示價值,解向量用x[i]表示物體i是否被放入,上面提到的optpi(j)則用二維數組相應的optp[i][j]來表示,物體個數n,背包載重量為m。

(四)算法實現

initial knapsack_dynamic(initial optp[][],weight[],p[],x[],n,m)

{

initial i,j,value;

//根據(4)式初始化第0列及解向量X

//解向量初始值設置為false,表示起初所有物體均未放入背包

for(i = 0; i

{

optp[i][0] = 0;

x[i] = FALSE;

}

//根據(4)式初始化第0行

for(i = 0; i

{

optp[0][i] = 0;

}

//利用(5)(6)式計算optp[i][j]

for(i = 1; i

{

for(j = 1; j

{

optp[i][j] = optp[i-1][j];

if((j >= weight[i]) && (optp[i-1][j - weight[i]]+p[i]) > optp[i-1][j])

optp[i][j] = optp[i-1][j-weight[i]] + p[i];

}

}

//確定裝入背包的具體物體

j = m;

for(i = n; i > 0; i--)

{

if(optp[i][j] > optp[i-1][j])

{

x[i] = TRUE;

j = j - weight[i];

}

}

//value就是所要求的值

value = optp[n][m];

return value;

}

1.案例分析

現有載重量為10的背包,有四個物體A、B、C、D,其重量分別為4、2、5、3,價值分別為4、3、5、8,要求放入物體使背包所獲價值最大。

用optp[i][j]來存儲這四個物體在不同載重量的背包下所獲的價值,計算過程如下表所示:

2.時間空間復雜度

該算法中,矩陣optp的大小為(m+1)×(n+1),物體的重量、價值和解向量大小都等于物體個數n,故該算法的空間復雜度為O(nm)。對物體重量、價值的初始化(算法實現略)所需時間都為n,解向量和矩陣第0行初始化時間為n,矩陣第0列初始化時間為m,對矩陣optp的計算所需時間為n×m,解向量X的確定時間為n,故整個算法的時間復雜度為O(nm)。

(五)算法優化

在上述算法中,時間復雜度不能再繼續優化了,但是空間復雜度是可以繼續優化的。

上述算法中,存儲optp使用的是二維數組,其大小為(m+1)×(n+1),但是仔細觀察發現,optp[i][j]只與optp[i-1][j]和optp[i-1][j - weight[i]]有關,與optp[k][l](k=1,2,……,i-2,i+1,……n,j=1,2,……,m)無關,故可考慮只用一維數組_optp來存儲,_optp[j]相當于optp[i][j]。而考慮到optp[i][j]是由optp[i][j]和optp[i-1][j - weight[i]]共同計算得到的,故該算法中的j循環要從后往前計算,_optp[]的計算算法設計如下所示:

for(i = 1; i

{

for(j = m; j >= 1; j--)

{

if((j >= weight[i]) && (_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

上述例子中,相應的_optp[j]計算結果如下表所示:

}

}

上述例子中,相應的_optp[j]計算結果如下表所示:

顯然,對于物體i,_optp[j]的計算不會影響到_optp[0,1,……,weight[i]-1],故上述算法可繼續優化為:

for(i = 1; i

{

for(j = m; j >= weitht[i]; j--)

{

if((_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

對于01背包問題,常見的要求有兩種:一種是恰好裝滿背包、另一種則沒有要求,針對這兩種問法,可從初始化上來區分。

當要求恰好裝滿背包時,初始化時將_optp[0]設為0,其他_optp[1,2,……,m]全部設為-∞,這樣就可保證最終得到的_optp[n]是一種恰好裝滿的最優解,此時可以把初始化理解成沒有任何物體可放時,只有容量為0的背包能被價值為0的nothing“恰好裝滿”;當沒有這個限制時,初始化時應將_optp[0,1,……,m]都設為0,此時可以理解為任何一個背包都有一個合法的解“什么都不裝”,這個解的價值為0。

當優化后,空間復雜度變為O(m),計算所需時間為:

當weitht[i]較大時,可以節省很多時間。

動態規劃的缺點:對于01背包問題,用動態規劃方法解很容易理解,但是這種方法有一些弊端,從上述算法可以看出:當物體的重量較大時,所需的物理空間較大;當物體的重量不是整數時,無法利用數組來存儲該結構。

四、結束語

在日常生活中,01背包問題有很多應用,比如如何利用有限空間的手提包,裝入外出旅行的各種必需品。

篇4

關鍵詞:背包算法;優先策略;動態規劃;棧操作

中圖分類號:TP274文獻標識碼:B

文章編號:1004-373X(2010)02-128-03

Design and Analysis of Knapsack Problem

YU Miao

(Anshan Meteorological Bureau of Liaoning Province,Anshan,114004,China)

Abstract:Knapsack problem is typical problem in computer science and its solution is a hot spot in algorithms design and verification.The solutions for the knapsack problems,algorithms design and verification with three different means:preference strategy,dynamic programming and recursion.Correctness of these three algorithms are proved,in the complexity analysis,the complexity of space and time in preference strategy is lowest,while the dynamic programming has obvious superiority.

Keywords:knapsack problem;preference strategy;dynamic programming;stack peration

0 引 言

算法研究是計算機科學的重要組成部分,有觀點認為 “計算機科學是一門研究算法的科學”[1,2],無論這種觀點是否全面,都足以說明算法研究在計算機科學發展中所具有的重要作用及地位。算法研究是通過程序來實踐的。程序=算法+數據結構[3,4],這一大家都熟知的公式更加表明算法研究不是單純的數學問題,必須通過 “實踐”掌握算法的實質。這里對 “背包問題”采用優先策略、動態規劃及遞歸三種不同方法進行求解、算法設計及驗證,并通過各種算法予以實現。本文研究、分析了實現 “背包問題”算法的實質。

1 問題描述

一旅行者攜帶背包去登山,已知所能隨身攜帶的背包重量限度為 b,現有n種物品可供選擇裝入背包。第i種物品重量為ai,其重要性價值指標為ci,旅行者應如何選擇攜帶各種物品,以使總價值最大[5,6]。

“背包問題”的數學模型為:

max z=∑ni=1cixi

約束條件為:

∑ni=1aixi≤b,ai>0,ci>0,

xi=0或1, 1≤i≤n

2 優先策略的算法設計

按重量a1≥a2≥a3≥a4≥…≥an對xi進行調整,作為待選隊列[7,8]。

假設前面已經選擇了s個,即jr1,jr2,…,jrs為最優選擇的前s件物品,則應滿足:

cr1,cr2,…,crs,且∑si=1 ai

對后面等待選擇的物品jk來說,與之對應的ak無疑滿足:

ak≤ari, i=1,2,…,s

即所選擇的物品重量比其所有待選擇的物品重量大。因此,對待選擇的物品是否被選中將分為:∑si=1ari+ak≤b和∑si=1ari+ak>b 兩種情況。

(1) 對于∑si=1ari+ak≤b的情況,將xk插入已選擇的J隊列中,然后根據ci的大小找到其相應的位置。

(2) 對于∑si=1ari+ak>b的情況,有:

① 若存在ck≥cri,則將xk插入并按ci排序后,將jri從已選擇的隊列中刪除并插入按ci從大到小、重量從小到大地排序到二次篩選隊列中。

② 若存在ck

③ 當待選隊列為空時,選擇隊列從s到1與從二次篩選隊列中選擇的元素進行優化選擇。若存在:

∑n-s-mj=1aj+∑s-1i=1ari≤b, ∑n-s-1j=1cj>cri

將組合的各元素Xi插入已選擇的J隊列中,然后根據 ci的大小找到其相應的位置:jri,jr2,…,jrs。

④ 當③中已完成對首元素組合的篩選后,此時的J隊列為最優選擇。

3 動態規劃法的算法設計

動態規劃的基礎是最優化原理,其關鍵問題是建立動態規劃的數學模型(狀態轉移方程)。主要步驟是:劃分階段,確定階段的狀態;確定決策變量、權函數以及指標函數;建立狀態轉移方程;根據動態規劃的最優化原理建立遞歸方程;自底向上遞推逐步求解。

(1) 劃分階段k:將供選擇的物品按 1,2,…,n排序,每個階段可裝入一種物品;

(2) 確定決策變量:xk裝入第k種物品的件數;背包中允許裝入前k種物品的總重量;

(3) 建立狀態轉移方程:sk=sk-1+akxk;

決策集合為:

D(sk-1)={xk|0≤xk≤[sk/xk],xk∈Z}

(4) 建立遞歸方程:

fk(sk)=maxxk=0,1,…,\{fk-1(sk-1- xkak+ ck)}

f0(0)=0

(5) 遞推求解:逐步計算出f1(s1),f2(s2),…,fn(sn)最后求得,fn(a)即為所求的最大價值。

4 遞歸的算法設計

遞歸算法的基本思想是假設用布爾函數 knap(s,n) 表示 n件物品放入可容質量為 s的背包中是否有解,當knap函數的值為真時,說明問題有解,相反當值為假時,無解。這里可以通過輸入s和n的值,進行以下幾種情況的討論。

(1) 當s=0時,可知問題有解,即函數knap(s,n)的值為true。

(2) 當s

(3) 當s>0且n0且n≥1 時,才符合實際情況,這時又分為兩種情況。即:

篇5

關鍵詞：管網設計；直接及間接優化；設計方法

中圖分類號：S276 文獻標識號：A 文章編號：2306-1499（2013）06-（頁碼）-頁數

目前，對于城市排水管道系統優化設計問題，已開發了一些水力計算程序和優化算法如直接優化法、動態規劃法、遺傳算法等，并在設計過程中得到一定應用，并能顯著提高設計水平和設計效率。下面就排水管網優化方法及特點做一簡要介紹。

1.直接優化設計方法及優缺點

在管線平面布置己定情況下的污水管網各個參數的優化設計，被分為直接優化法和間接優化法。直接優化法是根據排水管道系統性能指標的變化，通過直接對各種方案或可調參數的選擇、計算和比較，來得到最優解或滿意解，它具有直接、直觀和容易驗證的優點。直接優化法主要包括電子表格法和兩相優化法。電子表格法是利用“電子表格”統計數據和分析數據的功能進行管網優化的。它提供了一種啟發式費用估算方法，利用這種方法，用戶可尋找最小費用的設計。兩相優化法是當設計流量確定后，在滿足約束條件的前提下，選取最小流速和最大充滿度進而得到最優管徑和最小坡度，最大限度的降低管道埋深。其算法與人工計算基本相同，即按污水流動方向，先計算支管后計算干管和主干管，通過從上游至下游依次對各設計管段進行計算，繼而完成一條管道及整個管網的計算。

2.間接優化法

間接優化法對其中的某些條件適當取舍，把問題簡化、抽象為容易解決的數學模型，通過計算得出最優解線性規劃法是優化技術中最常用的一種方法。它對于污水管網設計計算模型中的約束條件和目標函數的非線性，分別用它們的一級泰勒展開式代替，將之化為線性規劃問題，用線性規劃的解作為問題的近似解，反復迭代，使迭代點序列逼近非線性規劃的最優解。它的缺點是把管徑當作連續變量來處理，存在計算管徑與市售規格管徑相矛盾的問題。把非線性函樹轉為線性函數，前期準備工作量大，且難以保證結果的計算精度?；旌险麛狄巹澐?，作為線性規劃法發展形式，克服了線性規劃的部分缺點，可以解出離散的標準管徑，但由于整形變量過多，往往難以求解，從而應用受到限制。

2.1非線性規劃法

非線性規劃法是為了適應排水管道系統優化設計計算模型中目標函數和約束條件的非線性特征而提出來的。它可以優化選擇排水管道的直徑和埋深，以及中途泵站的位置。其假定管徑是離散的，易于對目標函數和約束條件進行敏感性分析。但是該方法極大地限制了目標函數和約束條件的形式。

2.2罰函數離散優化法

罰函數離散優化法將排水工程的特點與罰函數離散思想相聯系，可以排除不合理的設計方案，以管系末端管底標高為全局控制因素，建立與目標函數的可行解對應關系，并通過同時進行整體控制與局部控制的水力計算方法，遍歷目標函數的可行解及局部最優解，從而得到管系的全局最優設計方案。該方法由于對管道系統的各種可行解進行遍歷，在解決大型管網問題時，必然存在運行時間長和內存占用量大的缺點。

2.3動態規劃法

動態規劃法是目前在國內外廣泛應用的排水管道優化設計計算方法。它的基本思想是認為排水管道是一個多階段的決策過程，通過對研究課題劃分階段，尋求最優路線來進行優化設計。它在應用中分為兩支：一支是以各節點埋深做為狀態變量，通過坡度決策進行全方位搜索，其優點是直接利用標準管徑，優化結果與初始解無關，且能控制計算精度，但要求狀態點的埋深間隔很小，使存儲量和計算時間大為增加。為了節省運算時間，引入了逆差動態規劃法。逆差動態規劃法是在動態規劃法的基礎上引入了縮小范圍的迭代過程，可以顯著地減小計算時間和存儲量，但在迭代過程中可能遺漏最優解，而且在復雜地形條件處理跌水，緩坡情況時受到限制。另一支是以管徑為狀態變量，通過流速和充滿度決策進行搜索的動態規劃法。由于標準管徑的數目有限，較以節點埋深為決策變量方法在計算機存儲和計算時間上有顯著優勢。最初的動態規劃對每一管段選取的一組標準管徑中并不全是可行管徑，因此發展出可行管徑法?？尚泄軓椒ㄍㄟ^數學分析，對每一管段的管徑采用滿足約束條件的最大和最小管徑及其之間的標準管徑，構成可行管徑集合，進而應用動態規劃計算?？尚泄軓椒ㄊ沟脙灮嬎憔鹊靡蕴岣?，并顯著減少了計算工作量和計算機存儲量。盡管動態規劃法是解決多階段決策問題最優化的一種有效方法，但其狀態變量均應滿足“無后效性”的特點。“無后效性”是指當給定某一階段的狀態時，在以后各階段的行進要不受當前各階段狀態的影響。從前面的分析可知，在排水管道系統設計計算時，前一管段的設計結果將直接影響到后續管段設計參數的選用，無論是利用節點埋深還是管短管徑作為狀態變量，都沒有充足的證據能夠狀態變量的“無后效性”。因此利用動態規劃法求出的污水管道優化設計方案并不一定是真正的最優方案。

3.優化設計的遺傳算法

遺傳算法是近幾年迅速發展起來的一項優化技術，是一種模擬自然界生物進化過程的全局隨機優化算法。遺傳算法借助于生物進化機制與遺傳學原理，按照自然選擇和適者生存的原則，利用簡單的編碼技術和繁殖機制，模擬自然界生物群體優勝劣汰的進化過程，使待優化問題逐步從初始解進化到問題的最優解。簡單易用、靈活方便、通用性強以及隱含并行性等特點使遺傳算法比傳統優化方法具有更大的優越性，為解決復雜系統優化問題提供了一種通用框架，成為解決函數優化、網絡優化、組合優化等許多工程優化問題的重要技術之一。是進化算法的一個重要分枝。利用這一進化理論同樣可以作為排水工程實踐中的尋優方法。應用遺傳算法進行污水管網優化設計的關鍵在于確定合適的編碼方式以及將實際問題的優化目標函數轉換為遺傳算法的個體適應度函數。

目前，遺傳算法與神經網絡的結合越來越受到人們的關注，并且己經形成了一種新穎的遺傳神經網絡研究領域。近年來，該領域的研究非常活躍，并取得了不少成果，這為遺傳神經網絡更為廣泛深入的應用帶來了充滿希望的前景。目前主要的結合方式是將遺傳算法用于神經網絡權值的優化和拓撲結構的設計。用遺傳算法優化神經網絡權值是在網絡結構已經確定的前提下進行的，無需計算梯度信息，遺傳算法就能夠發現神經網絡連接權值的一個接近全局最優的權值集，這使得用遺傳算法優化神經網絡權值對那些大而復雜、誤差梯度信息很難獲取或根本不可用的問題特別具有吸引力。如果神經網絡誤差的梯度信息容易獲取，則把遺傳算法與基于梯度信息的BP算法相結合的方法可以提高權值訓練算法的性能。

4.結語

優化設計系統將設計人員計算量大大降低，把設計人員從查閱圖表的繁雜過程中解脫出來，加快設計進度，與此同時，整個排水管道系統得到了優化設計。研究標明，優化后的排水工程大約可以降低約10%的工程造價。應用各種優化算法進行排水管網的優化設計在實際工程優化設計中有較大的推廣應用潛力，可以為工程設計優化和科學的方案決策提供科學的參考依據，能夠達到節省工程投資和提高設計質量的良好效果。當然，排水管網的優化算法要想被廣大工程技術廣泛接受，一方面需要設計人員勇于嘗試和應用新技術、新方法，另一方面也需要開發出能夠將合適的優化算法和傳統計算方法有效融合在一起的計算機輔助設計軟件，以促進新方法在實際工程設計過程中推廣應用。

參考文獻

篇6

關鍵詞：0-1背包；動態規劃

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2007)17-31378-02

The Dynamic Programming Algorithms of 0-1 Knapsack Problem Based on Visual C++

CHEN Zi-li, PAN Yan-yan

(Fujian Communication Technology College,Fuzhou 350007,China)

Abstract:The 0-1knapsack problem is a classic NP problem.In this paper,the 0-1 knapsack problem and its algorithm is analyzd ,the algorithms is based on Dynamic Programming.And carry out that algorithms in the Visual C++.

Key words:0-1 Knapsack;Dynamic Programming

1 0-1背包問題

0-1背包問題是：已知n個物品的重量及其價值分別為Wi>0和Pi>0，背包的容量假設設為Ci>0，如何選擇哪些物品裝入背包可以使得在背包的容量約束限制之內所裝物品的價值最大？

2 幾種解法的比較

2.1 動態規劃算法

動態規劃可以把困難得多階段決策變換為一系列相互聯系比較容易的單階段問題。對于背包問題可以對子過程用枚舉法求解，而且約束條件越多，決策的搜索范圍越小，求解也越容易。

2.2 回溯法

回溯法需要為問題定義一個解空間，這個解空間必須至少包含問題的一個解（可能是最優的）。使用遞歸回溯法解決背包問題的優點在于它算法思想簡單， 而且它能完全遍歷搜索空間，肯定能找到問題的最優解；但是由于此問題解的總組合數有2n個，因此，隨著物件數 n 的增大，其解的空間將以2n級增長，當 n 大到一定程度上，用此算法解決背包問題將是不現實的。

2.3 貪心算法

使用貪心方法求解時計算的復雜度降低了很多。貪心算法是一種不要求最優解，只希望得到較為滿意解的方法。一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪心方法常以當前情況為基礎作最優選擇，而不是考慮各種可能的整體情況，所以貪心算法不需要回溯。但是，對于某些情況，實際上有解，而該算法不能找到解。

2.4 分枝-限界法

分枝界限是另一種系統地搜索解空間的方法，與回溯法的主要區別在于對E節點的擴充方式。每個活節點有且僅有一次會變成E節點。當一個節點變為E節點是，則生成從該節點移動一步即可到達的所有新節點。在生產的節點中，拋棄那些不可能導出可行解的節點，其余節點加入到活節點表，然后從表中選擇一個節點作為下一個E節點。從活節點表中取出所選擇的節點并進行擴充，直到找到解或活動表為空，擴充才結束。

2.5 遺傳算法

遺傳算法是一類借鑒生物自然選擇和自然遺傳機制的隨機化的搜索算法。它適用于處理傳統搜索方法難于解決的復雜和非線性問題。遺傳算法是一種群體型操作，該操作以群體中所有個體為對象。選擇、交叉和變異是遺傳算法的三個主要算子，它們構成了遺傳算法的主要操作。使用遺傳算法解決物件數較大的背包問題，它具有收斂快、搜索速度快的特點。然而在一般情況下，使用基本遺傳算法解決背包問題時，得到問題的近似解也不能滿足逼近最優解的要求。

下面介紹用動態規劃算法實現0-1背包問題的求解。

3 動態規劃算法

3.1 0-1背包問題的描述

3.2 最優子結構性質

0-1背包問題具有最優子結構性質。設(y1,y2,…,yn)是所給0-1背包問題的一個最優解。則

3.3 遞歸關系

設所給0-1背包問題的子問題：

的最優解值為m(i.j),即m(i.j)是背包容量為j,可選擇物品為i,i+1,…,n時0-1背包問題的最優值。由0-1背包問題的最優子結構性質，就可以建立計算m(i.j)的遞歸式如下：

4 C++實現算法

#include

#include

#include

int min(int w,int c)

{int temp;

if (w

else

temp=c;

return temp;}

int max(int w,int c)

{int temp;

if (w>c)temp=w;

else temp=c;

return temp;}

void knapsack(int v[],int w[],int c,int ,int**m)

//求最優值

{int jmax=min(w[n]-1,c);

for(int j=0;j

m[n][j]=0;

for(int jj=w[n];jj

m[n][jj]=v[n];

for(int i=n-1;i>1;i--){ //遞歸部分

jmax=min(w[i]-1,c);

for(int j=0;j

m[i][j]=m[i+1][j];

for(int jj=w[i];jj

m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);}

m[1][c]=m[2][c];

if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);

cout

for(int l=2;l

for(int j=0;j

{cout

cout

int traceback(int **m,int w[],int c,int n,int x[])

//回代，求最優解

{cout

for(int i=1;i

if(m[i][c]==m[i+1][c]) x[i]=0;

else {x[i]=1;

c-=w[i];}

x[n]=(m[n][c])?1:0;

for(int y=1;y

{cout

return x[n];}

void main(){

int n,c;

int**m;

cout

cin>>n>>c;

int *v=new int[n+1];

cout

for(int i=1;i

cin>>v[i];

int *w=new int[n+1];

cout

for(int j=1;j

cin>>w[j];

int *x=new int[n+1];

m=new int*[n+1];//動態的分配二維數組

for(int p=0;p

m[p]=new int[c+1];}

knapsack(v,w,c,n,m);

traceback(m,w,c,n,x);}

5 測試

在Visual C++ 下對該算法進行測試 ：例：背包的容量c＝10，物品個數n＝5，w＝{2,2,6,5,4},

v＝{6,3,5,4,6}。

輸出結果： 1 1 0 0 1

背包的總重量：8

背包的總價值：15

6 算法分析

上述算法Knapsack需要O (nc)計算時間，traceback需要O（n）計算時間。采用動態規劃算法解決0-1背包問題，并通過編程在Visual C++下進行測試得到了較好的結果，證明了算法的正確性。但是，算法還是有缺陷的，當c很大時，算法需要計算的時間較多，還需改進。

參考文獻：

[1]王曉東.計算機算法設計與分析[M].北京:電子工業出版社,2004.

[2]劉玉娟,王相海.0-1背包2問題的兩種擴展形式及其解法[J].計算機應用研究,2006.

[3]楊曉紅.基于Visual C++的0-1背包問題的貪婪算法[J].科技資訊導報,2007.

[4]黃波,蔡之華.0/1背包問題及其解法研究[J].電腦知識與技術,2007.

篇7

隨著AlphaGo（圍棋人工智能程序）在2016年初擊敗了世界圍棋冠軍后，人工智能技術的研發與討論繼續走向一個新的高峰，而語音識別技術則是其核心內容。

本文主要基于語音識別技術的語音解碼模塊進行討論，從其涉及技術、設計、實現進行全面描述。運用解碼器進行解碼操作，通過搜索算法在解碼端尋找最優詞串，搭建和訓練聲學模型，并提高語音識別率。本項目基于一個完整的Android軟件作為依托，但由于篇幅有限，本文重點討論離線語音包、搭建語言模型、以及語音解碼模塊的設計過程。

1.項目背景

語音識別技術是能夠將人的語音信號轉換成機器可以識別的指令的一種方法，通過指令來控制機器的正常運轉。語音識別的任務主要包括：孤立詞識別、關鍵詞識別、連續語音識別等。

市面上的離線語音識別一直不成熟，識別慢、識別率低等問題一直被人詬病。本項目離線語音識別部分是基于Sphinx-4自行訓練得到的聲學模型和語言模型，在小詞匯量識別方面盡量提高其識別率。

2.需求分析

一個成熟的語音識別系統可以劃分為特征提取、聲學模型訓練、語言模型訓練和解碼器四個重要組成部分；而離線端語音解碼模塊，包括了對原始語音進行信號處理、特征提取、通過Viterbi動態規劃算法搜索最優結果、語義分析及輸出文本結果等步驟。

1、 原始信號處理：獲取通過麥克風按鈕接收到的原始音頻數據，過濾非必要信息以及背景噪音對語音前端點和后端點進行截取，對語音信號分割成若干個進行分析；

2、 特征提?。焊鶕phinxbase語音系統給出的接口，提取出語音信號的關鍵特征，并將其生成一個序列，以供解碼處理時搜索這個隱式序列，得出結果；

3、 算法搜索最優序列：根據Viterbi算法設計出計算序列中出現概率最大的詞串的方法，搜索出每一幀語音信號的最優路徑，輸出結果；

4、 語義分析及輸出識別結果：根據孤立的關鍵詞判斷搜索出來的語音結果屬于哪一個應用場景，如“打電話”、“發短信”、“上一頻道”、“下一頻道”等等孤立詞；

離線語音解碼模塊流程如下圖2-1所示：

3.系統設計

3.1.特征提取

特征提取的主要目的是減少語音噪聲靜音等無用的雜訊，獲取必要的訊號數據，將數據轉換成電腦可以識別的數字信號，以便作識別和語義分析。

本語音識別技術模塊基于Sphinx4語音識別系統進行開發的，其中聲音的預處理是利用MATLAB這一便于算法開發的軟件來實現對語音信號進行數字處理與分析，也可稱為特征處理。其包括對原語音信號進行預加重處理，然后需要進行分幀和加窗、采樣和量化、端點檢測等。

其中，包括：預加重處理、分幀、量化處理以及語音端點檢測等過程。如下3-1所示：

3.2. 基于動態規劃的Viterbi算法

動態規劃算法的基本思想是將問題分解成若干個子問題，求解子問題，最后從子問題的解中得到原問題的解。通常利用動態規劃算法解決問題的步驟是先找出最優解的性質，刻畫最優解的結構特征，然后遞歸定義出最優解，用自底向上的方法計算出最優路徑，最后根據計算出來的最優值信息，構造最優解。圖下圖3-2所示：

因此，基于動態規劃的Viterbi算法的整體設計思路如下：

1、 對于每一個語音狀態要設置一個三元組作為記錄：（prob，v_path，v_prob），這里聲明的prob是從最初狀態的到當前狀態的所有路徑的出現概率相加的結果，其中最優的路徑為viterbi路徑，v_path代表的就是viterbi路徑，而v_prob代表的則是此路徑出現的概率；

2、 算法開始后，初始化一個Map集合，把每一種語音狀態都映射進三元組中

3、 設置三重for循環，計算從當前語音狀態到下一階段的過渡概率會出現什么變化，所有下一狀態判斷完之后，從集合中遍歷找出最優結果，即出現概率最大的路徑；

4、 保留每一幀語音在某個狀態的最優路徑，輸出結果。

4.總結

語音識別技術的核心是HMM技術（隱式馬爾科夫模型），而本文主要基于語音識別技術的語音解碼模塊進行討論，從其涉及技術、設計、實現進行全面描述，對離線解碼模塊中的特征提取、以及使用動態規劃的Viterbi算法實現搜索最優序列進行了詳細介紹。模塊基本實現完成，但仍有很多值得提升和完善空間，今后可以使用更先進的算法進行優化。

參考文獻

[1] 朱元濤.Android應用開發范例大全[M]. 清華大學出版社.2015.

[2] 郭霖. 第一行代碼 Android [M]. 人民郵電出版社. 2014.

[3] 何紅輝，關愛民.Android 源碼設計模式解析與實戰 [M]. 人民郵電出版社. 2015.

[4] Android Studio Applicati [M]. 進口原版圖書.

[5] The Definitive Guide to Sqlite [M]. Apress.

[6] 李興華.Android開發實戰經典[M].清華大學出版社.2012.

[7] Android開發實戰[M].清華大學出版社.2013.

[8] 趙卓君.Java語言程序設計高級教程[M].北京.清華大學出版社.2010.

[9] 朱少民.軟件測試方法和技術（第2版）[M].北京.清華大學出版社.2010.

[10] UML和模式應用[M].機械工業出版社.2006.

篇8

關鍵詞：市政給排水；管道設計；優化設計

引言

城市普遍存在水質污染的問題，致使城市水環境遭受到嚴重破壞，水質型缺水的區域不斷擴大，水資源供需失衡，這一問題已對城市中居民的生活，健康及城市現代化進程構成了危害，嚴重威脅到城市的水系統以及城市的可持續發展。隨著城市化進程的發展，城市市政自來水給排水工程是城市舉出設施的重要組成部分之一，如何降低市政自來水管道減少爆管漏水等問題帶來的水資源的浪費，有效提高城市自來水供排水管道的效率和輸水能力，為城市居民日常生活和城市建設提供經濟實惠、安全可靠的水資源保障，如何改善市政自來水給排水管道的設計是必要的。

1.市政給排水工程的結構設計

1.1市政給排水工程的結構設計

在市政給排水工程中，根據工程的埋設深度。工程管道規格、材質以及地下水位和試驗壓力等綜合指標，對管道的強度和剛度進行計算及復核，提供給排水的管道等級、壁厚以及結構配筋圖。通常采用的加固措施有混凝土、管廊包管等，對于一些必須要滿足剛度和強度要求的管道應該及時采取加固方法來進行加固，而且在施工過程中根據計算采用具體的加強加固措施，加固的具體方法和方式應根據經濟指標和實際情況來確定。

1.2市政給排水工程的結構形式

在市政給排水工程中，排水專業確定管道的結構形式，一般來說，結構專業應根據管道的工作環境。結構用途以及水文地質情況等經濟指標等從專業角度提出參考意見。特殊地段以及特殊情況的非承壓管也采用鋼管等形式當污水管道；而對于口徑較大時應采用現澆鋼筋混凝土箱涵，或采用盾構結構形式。

2.市政給排水管道對于城市的意義

在市政基礎設施建設和完善中，給排水管道的鋪設和維修護養對城市有著極其重要的影響。給水管道關系整個城市的生活和工業用水的供給，而排水管道則關系城市污水的排出和雨水等可能造成市內積水的多余水量及時排空。在這樣一種背景下，市政給排水工程的完善程度和施工質量對城市居民生活將會產生重要的影響。

另外，市政管道的鋪設有些是在城市生活區和工業區劃定建成后或者建設過程中開始施工，在不破壞原有市政建筑的前提下完成新的給排水管道的鋪設，便對施工技術提出了一定的要求。同時，給排水工程質量的要求也必然要求我們加強對施工技術的嚴格控制。只有在高質量標準要求下完成的工程才能減少使用過程中的一些問題，從而減少給排水工程維修護養的經濟成本。

3.市政排水管網優化設計

3.1管線的平面優化布置

排水管網的布置原則是既要使工程量最小，又要使水流暢通、節省能量。正確的定線是合理經濟的設計管網的先決條件。定線的基本原則是：干管支管的設計盡量采用直線布局，不要拐彎；定線應盡量利用地勢，使污水在重力作用下流入污水廠；設計時應盡量減少管道埋深；在管道的中途盡量減少提升泵站的設置。在早期的研究中，設計方法為假定每一段管徑相同，以挖方費用為優選依據，選擇一初始布置方案，然后通過算法逐步進行調整。后來又引入了排水線的概念，將排水區域內與最終出水口節點相距同樣可行管數的節點用一根排水線連接起來。這樣把問題轉化為最短路問題，可用動態規劃法求解。但此方法把尋優的范圍被限制，使人們在設計過程中很容易把最優方案排除。后來，人們把城市排水系統排水布置抽象為由點和線構成的決策圖，從圖論中尋找方法。1986年發展到利用三種權值來解決問題。三種權值是各管段地面坡度的倒數；各管段的管長；各管段在滿足最小覆土條件下，按最小坡度設計時的挖方量。分別對這三種權值運用最短路生成樹算法求管線平面布置方案，再進行管徑、埋深和提升泵站的優化設計，最后取投資費用最小的平面布置方案作為最優設計方案。

3.2已定平面布置下的管道系統優化設計

排水管道優化設計主要是指：對于某一設計管段，當設計流量確定后，在滿足設計規范要求的管徑和坡度的多種組合中，取得管材費用與敷設費用的平衡。在排水管線平面布置已定情況下，對于管段管徑，埋深的優化設計，國內外做了大量研究工作。

（1）線性規劃法和非線性規劃法。a線性規劃法，是針對排水管網設計計算中的約束條件和目標函數的非線性，分別用其一級泰勒公式展開式代替，用線性規劃的解作為問題的近似解，反復迭代，使迭代序列逼近非線性規劃的最優解。缺點是把管徑當作連續變量來處理，存在計算管徑與市售管徑不一致的矛盾，且前期準備工作量大，以后發展的整數規劃法，雖然在一定程度上解決了線性規劃的缺點，但是其整型變量比較多，難以求解。b非線性規劃法適應了計算模型中目標函數和變量的非線性特征，可以優化選擇管道的直徑和埋深，但極大限制了目標函數和約束條件的形式。

（2）動態規劃法。動態規劃法是目前國內外比較常用的一種方法，基本思想是把排水管道設計看作一個多階段的過程，通過對設計過程進行階段劃分來對管道進行優化設計。其應用主要分為兩方面。a以節點埋深為狀態變量，通過坡度決策進行全方位搜索。其優點是直接采用標準管徑，結果與初始管徑無關，且能控制計算深度，但要求狀態點之間的埋深間隔很小，使存儲量和時間間隔大為增加。因此在此基礎上引入了擬差動態規劃法，在動態規劃法的基礎上引入了縮小范圍的迭代過程，但應用有一定的局限性。b以管徑為狀態變量，通過流速和充滿度決策。由于可使用的標準管徑數目有限，因此在計算速度和存儲量上都有很大優勢。以后又發展出了可行管徑法。此法使優化計算精度得以提高，并顯著減少了計算工作量和計算機存儲量。盡管動態規劃法是解決多階段決策問題的一種有效方法，但在排水管道系統設計計算時，前一段的設計結果將直接影響到后續管段設計參數的選用，因此利用動態規劃法求出的污水管道優化設計方案也并不一定是真正的最優方案。

（3）直接優化法。直接優化法是直接對各種方案或可調參數的選擇設計計算和比較來得到最優解，具有直觀和容易驗證的優點。主要方法有：a電子表格法是一種啟發式的費用估算方法，允許用戶尋找最小費用設計，能得出比動態規劃法要好的結果而且更符合設計規范的要求。b兩相優化法是設計流量確定后，在滿足約束條件的前提下，選取最經濟流速和最大充滿度進而得到最優管徑和最小坡度，最大限度地降低管道埋深.直接優化法的算法與人工算法基本相同，但受設計人員的能力所限，所得結果不盡相同，所以所求結果不一定是最優解。

（4）遺傳算法。遺傳算法是進化算法一個分支，是模擬生物學中的自然遺傳變異機制而提出的隨機優化算法。遺傳算法在解決中小型管道系統優化設計問題時可以求得最優設計方案。但解決大型管道系統問題時，只能求得趨近于最優解的設計方案，在排水管道系統優化設計中，不論采用何種方法，都以設計規范為基本要求，同時使費用達到最小。

4.結束語

在整個市政基礎建設工作中，各專業一環扣一環，最重要的是市政排水管道工程是隱蔽工程，維修起來比較麻煩，有的甚至是無法維修，并且維修費用較大，因此，在設計施工過程中，必須有效避免這些常見問題，加強對排水管道工程的質量控制，消除工程質量缺陷，切實保障人民的利益。

參考文獻：

[1]韋從勝，蔣全華.市政給排水管道設計[J].技術與市場，2011，（7）.

篇9

關鍵詞：0-1背包；回溯

中圖分號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）36-0076-02

The B_tracking Algorithm of 0-1 Knapsack Problem Based on C#

CHEN Zi-li

（Fujian Chuanzheng Communications College， Fuzhou 350007， China）

Abstract： The 0-1knapsack problem is a classic NP problem. In this paper， the 0-1 knapsack problem and its algorithm is analyzed， the algorithms is based on B_tracking algorithm. And carry out the algorithms in the C#.

Key words： 0-1 Knapsack； b_tracking algorithm

1 0-1背包思想

0-1背包問題的思想：如果n個物品的重量和價值分別為[wi>0]和[pi>0]，背包的大小設置成[ci>0]，應該怎樣往背包中放置物品可以達到最大值或者最佳裝載方式？[5]

在實際進行裝包操作時，規定每種物品只能載入一次，而且每種物品只能執行載入或者不載入操作，則把該問題叫做0-1背包問題。

給定[wi]>0，c>0，[vi]>0，[1≤i≤n]，尋求一個n元0-1向量[（x1，x2，...，xn），xi∈{0，1}，][1≤i≤n]，使得[i=1nwixi≤c]，而且[i=1nvixi]是最值。

[maxi=1nvixi] [i=1nwixi≤cxi∈{0.1}，1≤i≤n]

2 幾種解法的比較

2.1 回溯法

回溯法就是為問題聲明一個解集合，這個集合存在一個可能是最優的解。遞歸回溯法算法思想非常簡單，能夠對搜索空間進行遍歷，必然可以找到背包問題的最優解，缺點是背包問題解集合將隨著物品數量n的變大以2的幾何級數增長，當n大到一定程度上，要遍歷搜索空間需耗費大量的時間和資源，因此當物件數過多的時候，就很難依靠回溯法來求解。

2.2 動態規劃算法

動態規劃指的是把復雜的多階段問題分解成相對簡單的單階段問題。對于背包問題可以用窮舉法對子過程進行求解，并且決策的搜索范圍會因為條件的增多而變小，這樣求解也更簡單。

2.3 貪心算法

貪心方法的使用可以降低求解時計算的復雜度。貪心算法不是片面追求最優解，因此不理會所有情況，所以不象回溯法那樣進行遍歷，一般情況下，就以目前情形最為最優的 。

2.4 分枝限界法

分枝界限與回溯法拓展E節點的方法不一樣，為另一種全面地遍歷解集合的方法，按這種算法，任何活節點只可能一次改變為E節點。當某節點一旦改變成E節點，會同時產生一些新節點（也就是分枝），新產生的節點是從原節點跳轉一步實現的。產生的新節點里，只留下有希望得到行得通解的節點，添加到活節點表，剩下的拋棄。接著從活節點表里挑選節點再進行拓展，最后就可以得到最后解，并且活動表清空了。

3 回溯算法

回溯法為一種在問題的結果空間樹T上查詢問題答案的算法?；厮莘ㄔ谌拷獾慕Y果空間樹中，依照深度優先的方法，從根節點開始查詢結果空間樹。算法搜索至結果空間樹的每個節點時，先看看是不是不存在結果。假設確定不存在，那么忽略該子樹，繼續向其父節點進行回溯，反之，使用該子樹，仍然以深度優先的方法進行查詢。當回溯法來尋找結果時，一定要回溯到頂點，并且，頂點節點的全部子樹都查找完才停止。這樣，按照深度優先的策略全面查詢問題的結果的算法叫做回溯法，可以解決組合數很多的情況。

假設選取回溯法來解決0-1背包問題，可以用在采取子集數表示0-1背包問題的結果集合。執行查找結果空間樹時，如果左節點是能用的節點，查找行為轉到它的左子樹。那什么時候進入右邊的子樹查找呢？那就是只有在右邊子樹里有希望找找最優解的時候，才轉到右邊子樹查詢。要不然就把右子樹刪除。此過程由上界函數來完成。假定r是現在還沒有使用的剩下物品總價值，cp是現在已有的價值，yestp為目前最優的價值。那么在cp+r

要使上界函數的計算更方便，不妨讓物品按照重量價值進行降序排序。執行的時候，由函數fanwei來尋找最新節點的上界。只有在要進入右邊子樹時，才計算上界函數fanwei，由此判斷是不是要將右子樹刪除。轉到左子樹時不要查找上界，這時候上界和基類節點的上界是一樣的。

4 算法實現

int n；//物品數量

double c；//背包容量

double[] v=new double[100]；//各個物品的價值

double[] w=new double[100]；//各個物品的重量

double cw = 0.0；//當前背包重量

double cp = 0.0；//當前背包中物品價值

double yestp = 0.0；//當前最優價值

double[] perp=new double[100]；//單位物品價值排序后

int[] order=new int[100]；//物品編號

int[] put= new int[100]；//設置是否裝入

//按單位價值排序

public void knapsack（）

{ int i，j；

int temporder = 0；

double temp = 0.0；

for（i=1；i

perp[i]=v[i]/w[i]；

for（i=1；i

{ for（j=i+1；j

if（perp[i]

{temp = perp[i]；

perp[i]=perp[i]；

perp[j]=temp；

temporder=order[i]；

order[i]=order[j]；

order[j]=temporder；

temp = v[i]；

v[i]=v[j]；

v[j]=temp；

temp=w[i]；

w[i]=w[j]；

w[j]=temp； }}}

//回溯函

public void b_track（int i）

{ double fanwei（int i）；

if（i>n）

{ yestp = cp；

return； }

if（cw+w[i]

{ cw=cw+w[i]；

cp= cp+v[i]；

put[i]=1；

b_track（i+1）；

cw=cw-w[i]；

cp=cp-v[i]； }

if（fanwei（i+1）>yestp）//符合條件搜索右子數

b_track（i+1）； }

//計算上界函數

public double fanwei（int i）

{double leftw= c-cw；

double b = cp；

while（i

{ leftw-=w[i]；

b+=v[i]；

i++；}

if（i

b+=v[i]/w[i]*leftw；

return b； }

static void Main（string[] args）

{int i；

Console.WriteLine（"請輸入物品的數量和容量："）；

n=Convert.ToInt32（Console.ReadLine（））；

c= Convert.ToDouble（Console.ReadLine（））；

Console.WriteLine （"請輸入物品的重量和價值："）；

for（i=1；i

{ Console.WriteLine （"第{0}個物品的重量："，i）；

w[i]=Convert.ToDouble（Console.ReadLine（））；

Console.WriteLine （"價值是："）；

v[i]=Convert.ToDouble（Console.ReadLine（））；

order[i]=i； }

knapsack（）；

b_track（1）；

Console.WriteLine （"最有價值為："+yestp）；

Console.WriteLine （"需要裝入的物品編號是："）；

for（i=1；i

{if（put[i]==1）

printf（"%d "，order[i]）； }

return 0； }

5 測試

在VS2010下對該算法進行測試 ，例如背包的最大容量c=10，要放入的物品個數n=5，重量w={2，6，2，5，4}，價值v={5，6，3，4，6}。

輸出結果： 1 0 1 0 1

背包的總價值：15

背包的總重量：8

6 算法分析

因為尋找上界函數fanwei需要O（n）時間，當復雜度最壞時有O（2n）個右邊派生節點需要求解上界函數，因此，用回溯法來計算0-1背包問題的時間復雜度是O（n2n）。回溯法能得到0-1背包的最優解。另一方面回溯法是以樹當成基礎的算法，所以其空間開銷很多。

參考文獻：

[1] 王曉東. 計算機算法設計與分析[M].北京： 電子工業出版社，2004.

[2] 賀毅朝， 田海燕. 基于動態規劃法求解動態0-1背包問題[J].計算機科學，2012 ，39（7）：237-241..

[3] 徐穎. 回溯法在0-1背包問題中的應用[J].軟件導刊，2008（12）.

篇10

關鍵詞：運籌學；規劃論；EXCEL軟件

中圖分類號G642.4 文獻標志碼：A 文章編號：1674-9324（2014）10-0278-03

一、引言

運籌學是一門應用科學，可以為決策者選擇最優決策提供定量依據。運籌學經過多年的發展已經成為體系，包括規劃論（線性規劃、整數規劃、目標規劃、動態規劃和非線性規劃）、圖論與網絡、排隊論、存儲論、對策論和決策論等[1]。傳統的運籌學主要是以講授理論為主，尤其是比較枯燥的數學理論。近年來，運籌學改革不斷提高其應用性，減少枯燥的理論。此外，隨著運籌學計算機支撐技術的迅速發展，運籌學應用得到極大的推動，運籌學實驗教學提上日程，因此開設運籌學的實驗課程勢在必行。秦必瑜[2]和石磊[3]在運籌學的課程改革中都提出要增加軟件應用。我院運籌學教學團隊多年致力于運籌學的教改研究，在提出應用軟件的基礎上，進一步開設了除理論課程外的專門實踐課程，將理論課上學習到的內容使用軟件來進行求解。

國內運籌學的實驗教學已經有很大進展，目前運籌學經常使用的軟件主要有lingo[4][5]、WinQSB[6]、MATLAB[7]等。近年來，美國高校運籌學（管理科學）的思想、內容、方法和手段發生根本轉變，開始使用“電子表格”這一全新的教學方法。在運籌學中使用EXCEL已經成為運籌學教學的一個新潮流。EXCEL軟件使用方便，不需要重新安裝和學習新軟件的使用方法，一般的PC機上都安裝有EXCEL軟件，因此使用方便、應用廣泛。但是目前將EXCEL在運籌學中的應用并不多，李雪虎[8]給出用EXCEL求解運輸問題和網絡最優化問題的例子；魏杰羽[9]闡述了用EXCEl求解運輸問題的過程；而張輝[10]給出了使用EXCEL求解線性規劃問題的例子。在運籌學的體系中，內容遠遠不止這些，即使規劃論的內容也不止這些。本文中探討將EXCEL應用于運籌學規劃論的內容中。運籌學規劃論包括線性規劃、整數規劃、目標規劃、動態規劃和非線性規劃，由于非線性規劃一般不屬于本科教學的范圍，因此這里主要用EXCEL求解線性規劃、目標規劃、整數規劃、動態規劃模型，其中每個部分的模型均來自清華大學編寫的運籌學教材[1]，此為我院教學的教材。本文使用EXCEL求解教材中的案例，進行應用分析。

二、EXCEL在規劃論教學中的應用

（一）使用EXCEL求解線性規劃模型

Maxz=2x11+3x12

對于如下線性規劃問題，模型1

s.t.x1+2x2≤84x1≤164x2≤16x1，x2≥0

采用EXCEL求解該問題包括以下步驟：

第一步：模型輸入

1.在EXCEL表格中輸入數據，輸入目標函數的系數和約束條件的系數

2.標識數據，可以用不同顏色標識不同類型的數據

3.計算中間數據，數據、公式分離，顯示出完整模型

第二步：模型求解

1.安裝“規劃求解”工具。在“工具”中選擇“加載宏”，選中“規劃求解”，確定后，工具菜單中可顯示“規劃求解”選項，選擇工具-規劃求解。

2.設置參數，選擇目標，輸入約束條件；選擇選項中的“使用線性函數”和“假定非負”，點擊求解（見下圖）。

根據以上求解結果，可以知道兩個決策變量的取值分別為4和2，目標值最優為14。

3.求解出結果后，選中“敏感性報告”，點擊確定。得到線性規劃的求解結果以及敏感性報告，可以在此基礎上進行靈敏度分析，可與理論教學中的靈敏度分析進行對比，將理論教學與實踐教學相結合。

根據上面的敏感性報告可以知道，此問題所需要的三種資源的影子價格分別是1.5，0.125和0，根據這個結果可知當最優情況下，第一和第二種資源已經全部用光。

運輸問題是線性規劃的一種特殊情況，因此用EXCEL求解運輸問題的模型和過程是完全相同的，在此不做贅述。

（二）使用EXCEL求解整數規劃模型

這里的整數規劃其實指的都是整數線性規劃，該模型與線性規劃模型唯一的區別就是增加了整數約束，在求解過程中與線性規劃模型的區別就在于約束條件上。比如模型1中，如果要求所有的變量均為整數，則在EXCEL中做如下設置：

（三）使用EXCEL求解目標規劃模型

這里的目標規劃主要是指線性目標規劃，即其每個目標都是線性的，其所有約束也是線性的。線性目標規劃的求解可以認為是一般線性規劃的延伸，但是卻與一般線性規劃有很大區別。目標規劃中的約束條件有優先順序，而且不一定能夠同時滿足所有的目標，因此其求解過程需要考慮優先級，首先考慮第一優先級的偏差最小化作為目標函數，求出最優解。在第二步的時候將第二優先級的偏差最小化作為目標函數，并將第一目標的最優偏差作為約束條件放到第二步的模型中，以此類推直到最后一個目標。下面以模型2為例進行說明：

min P■d■■+P■d■■+P■（2d■■+d■■）

模型2

s.t.x1+x2+d■■+d■■=40x1+x2+d■■-d■■=50x1+d■■-d■■=24x2+d■■-d■■=30x1，x2，d■■，d■■≥0，i=1，L 4

在EXCEL求解過程中，首先求解第一優先級，以第一優先級作為目標，形成模型

min p1d■■

s.t.x1+x2+d■■+d■■=40x1+x2+d■■-d■■=50x1+d■■-d■■=24x2+d■■-d■■=30x1，x2，d■■，d■■≥0，i=1，L 4

這是一個典型的線性規劃問題，可用EXCEL求解，基本模型如下圖：

第一優先級可以獲得最優，在此基礎上求第二優先級，第二優先級的模型是在原模型基礎上，將目標函數變化為第二優先級，并且將第一優先級的結果作為第二優先級計算的約束條件。

min p2d■■

s.t.x1+x2+d■■-d■■=40x1+x2+d■■-d■■=50x1+d■■-d■■=24x2+d■■-d■■=30d■■=0x1，x2，d■■，d■■≥0，i=1，L 4

使用EXDEL求解的過程如圖所示：

以此類推，可以求得目標規劃的滿意解。

三、結論

該文介紹了如何使用EXCEL軟件求解線性規劃、目標規劃、整數規劃和動態規劃，而運籌學中的內容不止這些，因此下一步工作是要將EXCEL用于求解運籌學中除了規劃論外的其他模型。

參考文獻：

[1]運籌學教材編寫組.運籌學[M].北京：清華大學出版社，2005.

[2]秦必瑜，付海燕.管理類專業運籌學課程教學改革研究[J].中國林業教育，2010，28（3）：57-59.

[3]石磊，蔡定教.關于運籌學課程教學改革的幾點思考[J].廣西教育學院學報，2010，（2）：108-110.

[4]梁桂航，王健，李棟，趙萬勝，林紅旗.Lingo軟件在物流工程運籌學教學過程中的應用[J].物流技術，2010，（12）：226-228.

[5]萬義國，游小青.優化建模軟件LINGO在運籌學中的應用[J].山西建筑，2007，33（15）：367-368.

[6]許巖.淺談《管理運籌學》課程教學中WINQSB軟件的應用[J].現代計算機，2013，（3）0：28-31.

[7]張明，王文文.Matlab在經管類運籌學教學中的探索與實踐[J].大學教育，2012，（7）：81-89.

[8]李雪虎.EXCEl軟件在物流運籌學教學中應用探索[J].物流科技，2012，（8）：108-111.

[9]魏杰羽.EXCEl在物流運籌課程中的應用[J].物流工程與管理，2012，（5）：201-203.

[10]張輝如何試用EXEL軟件求解運籌學模型[J].現代企業文化，2009，（11）：144-145.