線性規(guī)劃并行化若干問題的研究.pdf

1、線性規(guī)劃問題最早是由George.B.Dantzig在1947年以前設想出來的.1949年G.B.Dantzig提出了用于求解線性規(guī)劃問題的一個有效的方法—單純形方法.在1984年,N.Karmarkar的"投影尺度法"使線性規(guī)劃出現(xiàn)真正的突破.這種新算法不僅在理論上優(yōu)越于單純形法,而且也顯示出對求解大規(guī)模實際問題的巨大潛力.Karmarkar算法再一次真正地不同于單純形法,它是從可行域的內部逼近一個最優(yōu)解.這一內點法已成為近幾年來令人

2、感興趣的研究焦點.自Karmarkar算法產(chǎn)生起,不斷有許多學者致力于改進,完善及推廣這一類方法,并統(tǒng)稱這種類型的算法為內點算法.本文主要做了以下幾方面工作:(1)介紹了并行編程的環(huán)境,包括集群系統(tǒng)簡介,自強2000簡介和MPI簡介.(2)介紹了線性規(guī)劃的歷史,線性規(guī)劃的數(shù)學模型,以及如何把一般線性劃劃問題轉換成線性規(guī)劃的標準型,并詳細分析了一個原-對偶內點算法的計算步驟.(3)提出了一種基于QR分解的并行原-對偶內點算法,包括原-對偶