1、遼寧師范大學本科生畢業(yè)論文(設計)文獻綜述表格填寫說明論文題目整數(shù)線性規(guī)劃匈牙利法多核并行算法研究綜述完成時間年 月曰學院計算機與信息技術學院專業(yè)計算機科學與技術(師范)學生蘇元賀學號 20081807010105指導教師鄭曉薇職稱教授查 閱 的 主 要 文 獻多核系列教材編寫組.多核程序設計.清華大學出版社，2007.9周偉明，多核計算與程序設計M.武漢.華中科技大學出版社,2008.陳國良，安虹，陳凌等.并行算法實踐.北京：高等教育出版社，2004 年奎因著，陳文光，武永衛(wèi)等譯.MPI與OpenMP并行程序設計：C語言版.清華大學出版社，2004.10于秀林.多元統(tǒng)計分析.北京：中國統(tǒng)計出

2、版社，1999林齊寧.決策分析.北京：北京郵電大學出版社，2003楊麗英，吳成東等.多目標追逐問題的一種混合整數(shù)線性規(guī)劃解.機械工 程學報，2008.10張?zhí)禚Q.整數(shù)線性規(guī)劃問題解法探究.湖州職業(yè)技術學院學報， 2005, 4文獻綜述1介紹1.1并行計算：并行計算(parallel computing) 是指，在并行機上，將個應用分解成多個子任務， 分配給不同的處理器，各個處理器之間相互協(xié)同，并行地執(zhí)行子任務，從而達到加速求 解速度，或者求解應用問題規(guī)模的目的。由此，為了成功開展并行計算，必須具備三個基本條件：并行機。并行機至少包含兩臺或多處理機，這些處理機通過互連網(wǎng)絡相互連接，互 通信。應用

3、問題必須具有并行度。也就是說，應用可以分解為多個子任務，這些子任務可 以并行地執(zhí)行。將一個應用分解為多個子任務的過程，稱為并行算法的設計。并行編程。在并行機提供的并行編程環(huán)境上，具體實現(xiàn)并行算法，編制并行程序， 并運行該程序，從而達到并行求解應用問題的目的。1.2什么是整數(shù)線性規(guī)劃：1)整數(shù)規(guī)劃(Integer Programming):要求全部或部分決策變量的取值為整數(shù)的規(guī)劃問 題。整數(shù)線性規(guī)劃(Integer Linear Programming ILP):要求全部或部分決策變量的取 值為整數(shù)的線性規(guī)劃問題。全(純)整數(shù)規(guī)劃：全部決策變量的取值都為整數(shù)?；旌险麛?shù)規(guī)劃則僅要求部分決策變量的取

4、值為整數(shù)。0-1整數(shù)規(guī)劃:要求決策變量只取0或1值。-1 -例題：設甲、乙兩種貨物裝運箱數(shù)分別為X1和x2。顯然，x1、x2都要求為整數(shù)，于是可建立整數(shù)規(guī)劃模型如下： TOC o 1-5 h z max z = 20 x1+10 x2(1)5x1+4x2W24(2)2x1+5x2W13(3)x1, x230(4)x1, x2為整數(shù)(5)1.3整數(shù)線性規(guī)劃的匈牙利算法根據(jù)題干的到效率矩陣步驟一：產(chǎn)生每行的零元素。方法：從每行中找出最小的元素，與對應的每行元素相減步驟二：產(chǎn)生位于每列的零元素方法：再找出矩陣每列的最小元素，再分別從各列中減去。步驟三：判斷零元素是否位于不同行、不同列。方法：首先從行

5、開始試指派，只有一個零元素時，對零元素打括號，并對所在列畫直 線。而有多個零元素，或零元素已被畫去，則轉下一行；行分析完畢后，然后從列開始 試指派，對每列只有一個零元素時，打括號，并畫去其所在的行。步驟四：繼續(xù)創(chuàng)造零元素。方法：從未被畫去的元素中，找到一個最小的元素虹對行的操作：選擇行位勢ui，如果行被直線覆蓋，則ui=0；如果未被覆蓋，ui=k；列的操作：列位勢vj，如果列被直線覆蓋，vj=-k；如果未被覆蓋，vj=0。產(chǎn)生新的效率矩陣：bij= aij -ui-vj步驟五：繼續(xù)判斷零元素是否位于不同行、不同列。方法：首先從行開始試指派，只有一個零元素時，對零元素打括號，并對所在列畫直 線。

6、而有多個零元素，或零元素已被畫去，則轉下一行；行分析完畢后，然后從列開始 試指派，對每列只有一個零元素時，打括號，并畫去其所在的行。步驟六：獲得最后結果。方法：對于打括號的零元素處進行指派，即可獲得最短時間。并行程序設計的不足及原因由上述的并行程序設計方法中可以得知，設計一種新語言雖然有比較強的并行性描 述能力，但是兼容性不好，不易推廣，因此現(xiàn)在采用該方法的系統(tǒng)較少。對現(xiàn)有的順序 語言加以擴展，提供并行性描述機制，該方法具有兼容性好、編程簡便等特點，現(xiàn)在常 常被采用。不改變現(xiàn)有順序語言，而由用戶提供的函數(shù)庫、類庫或并行化編譯系統(tǒng)等方 法實現(xiàn)并行程序設計。該方法簡單靈活，易于推廣。2.1現(xiàn)狀：并

7、行軟件的發(fā)展落后于并行硬件；和串行系統(tǒng)的應用軟件相比，現(xiàn)今的并行系統(tǒng)應用軟件甚少且不成熟；并行軟件的缺乏是發(fā)展并行計算的主要障礙；而且這種狀態(tài)仍在繼續(xù)。2.2原因是并行程序設計不但包含了串行程序設計，而且還包含了更多的富有挑戰(zhàn)性的問題。串行程序設計僅有一個普遍被接受的馮*諾依曼模型，而并行計算模型雖有好多，但 沒有一個被共同認可。并行程序設計對環(huán)境工具的要求遠比串行程序設計先進得多。串行程序設計比較適合于自然習慣，且人們在過去積累了大量的編程知識和寶貴的 軟件財富。至今并行算法范例不能被很好地理解和廣泛地接受；并行程序設計是建立在 不同的計算模型上的，而它們沒有能像馮.諾依曼模型那樣被普遍接受和認可。發(fā)展趨勢及應用前景隨著時代的進步，我們需要不斷調(diào)整研究方向。目前并行算法研究的新走向是：并 行算法研究內(nèi)容不斷拓寬，并行計算被納入研究范疇；與廣大用戶領域結合，注重應用， 強調(diào)走到用戶中去，為用戶解決問題；重視新的、非常規(guī)計算模式，如神經(jīng)計算、量子 計算等，這些模式能夠解決某類特定問題，有其自身的優(yōu)越性。目前并行編程類型逐漸匯聚于兩類:用于PVP，SMP和DSW的共享變量的單地址空間 模型和用于MPP和機群的消息傳遞的多地址空間模型。并行編程模型逐漸匯聚于三類標 準模型:數(shù)據(jù)并