實用文檔最優化方法課程論文引言在我們以前學習的《運籌學》中不難發現，線性規劃是其的一個重要分支，它是研究在滿足一組線性約束條件下，使某一線性目標函數達到最優的問題。1947年G.B.Dantzig（丹齊克）提出了求解一般線性規劃的方法——單純形法以后，線性規劃的理論趨向成熟，實際應用領域日益廣泛和深入。隨著計算機能夠初級成千上萬個約束條件和決策變量的線性規劃之后，線性規劃的應用領域更加廣泛了，目前線性規劃已成為現代科學管理的重要手段之一，并在國防、科技、農業、工業、商業、交通運輸、換將工程、經濟計劃、管理決策和教育等領域得到了廣泛應用。本文將會介紹單純形法和對偶單純形法的理論知識及其發展，并列舉單純形法和對偶單純形法在我們日常生活中的應用實例，談論這一理論的重要性。一．單純形法的產生和發展求線性規劃問題最優解的單純形法是由G.B.Dantzig（丹齊克）在1947年提出的，這是20世紀數學界最重大的成果之一，由于這一方法的有效性，幾十年來一直在幾乎所有的領域得到廣泛的應用。近年來，對于大規模的線性規劃問題，盡管它受到了內點算法的挑戰，但單純形法還是收到廣大用戶的青睞。當最優化問題中的目標函數與約束函數都是變量的線性函數時稱為線性規劃。工程與管理科學中大量的問題都是變量數目成百上千，乃至上萬或數十萬的線性規劃問題。學習和研究線性規劃的求解方法，不僅可以用于求解大量的實際線性規劃問題，而且可以用于非線性最優化問題的求解，這是因為當用迭代法求一個非線性最優化問題時，如果我們在迭代點對問題中的有關函數取局部線性近似，所的問題就是一個線性規劃問題。單純形法同其他的數值求解方法一樣是一種迭代法，它根據線性規劃問題的特點在問題可行域的頂點中逐步確定問題的最優解。在每一個是基本可行解的迭代點（即頂點），如果它不是最優的，單純形法從與該頂點相連接的邊中確定一個使目標函數值下降的邊，沿該邊移動可以確定一個與該頂點相鄰且目標函數又優于該頂點的新頂點（新的基本可行解）。由于可行域的頂點數是有限的，如果每一次的移動都能使目標函數值下降，則經過有限次的移動方法必須終止于問題的一個最優頂點。考察標準形線性規劃問題設作為一個基本可行解，單純形法首先檢驗它的最優性。如果它不是最優的，確定與該頂點相連的一條使目標函數下降的邊；接下來確定沿這條邊移動可以到達另一個更優的相鄰頂點，也就是得出一個新的基本可行解。為了更進一步的理解單純形法，我們在《運籌學》中學習了單純形表，在下面的例子中將會提到。雖然單純形法是求解線性規劃問題的最有效的方法，但是在很多情況下不能直接用或效率不高，因此人們就開始尋找更有效解決問題的方法。從而對單純形法進行了改進的發展。二階段法對于如下形式的線性規劃問題，不能直接應用單純形法來求解。為此，Dantzig引進松弛變量來把線性規劃問題進行轉化，即大M法。然后，利用單純形法求出原問題的一個基本可行解，再利用單純形法求出原問題的最優解。這樣兩次應用單純形法求解線性規劃問題叫做二階段法。擾動法和Bland法前面討論的利用單純形法求解線性規劃問題是約束線性函數非退化的情況下得到。約束線性函數退化的情況下，可能出現循環現象，如果出現循環現象，可以用擾動法。擾動法的主要思想是如果對常數項做一個擾動，使變動以后得到的線性規劃問題是非退化的，則可以單純形法求解。經過有限次的迭代可得到新問題的解。再把b重新變回來，從而得到原問題的解。換句話說，擾動就相當于增加松弛變量。R.G.Bland于1976年提出一個避免循環的方法。此方法的思想是:利用單純形法求解線性規劃問題中查看檢驗數時，如果幾個檢驗數是正的，則選擇下標最小的非基變量作進基變量。同時基變量中選擇下標最小的作離基變量。Bland的理論價值很高，但計算效率低。改進的單純形法改進的單純形法是Dantzig于1954年提出的，利用單純形法求解線性規劃問題時，經過每次換基，整個單純形表都要重新制作，導致計算效率低。故為了提高效率，只關注檢驗數、進基向量和離基向量。這樣，雖然關注的數據少了，但關注的內容不變，因此大大提高了計算的有效性而確保找到最優解。到現在為止，有很多改進的單純形法出現，其主要思想就是采取更簡捷方法來觀察檢驗數、進基向量和離基向量，從而提高計算效率。二．單純形法的應用單純形法的應用十分廣泛，下面我們舉一個在決策方面的用用問題。決策是為實現某一目標,運用科學的理論與方法,系統的分析主觀條件,提出各種方案,從中選擇出一個能最佳實現目標的最優方案,以達到最佳的經濟效果和社會效果的過程。因此一個決策問題的成立,必須具備下列的條件:有明確的目標(包括總目標和分目標)。存在兩個以上為實現同一目標可相互替代的策略或方案。在不同的自然情況下,各策略的實施結果可依據一定的理論與方法估計出來。在各種策略中只能確定一個行動方案。所謂確定型決策指的是決策者對決策目標的未來發展有十分清楚的了解,其有關條件都能準確的實例,每種決策只可能有一種后果。確定型決策除必須具備決策問題的4個必備條件外,它還應該有一個特定的條件,即決策對象所處的自然狀態是確定的。確定型決策的關鍵在于人們如何正確估計自然狀態,在實踐中人們往往由于無法了解唯一存在著的自然狀態而使決策失誤。因此從某種意義上說,確定型決策的成敗很大程度上依賴于預測的準確性。本文介紹一種線性規劃決策方法來定量評價投標備選項目,為承包商做出正確投標決策提供理論依據。下面以某承包商要在同一時間內對兩個不同的項目進行投資決策的例子來說明如何求解此類問題。某建設工程承包公司準備同時承包兩個項目A和B,但是現在要求其每年消耗的總人工費、機械費和材料費不超過150萬元,總耗項目措施費及其他建設費不超過100萬元,兩個項目每年分別的消耗費用見表2。如若項目A每年能獲得利潤200萬元,項目B每年能獲得利潤100萬元。請問兩個項目的工期各自控制在多久,可以使該承包商在充分利用有限資金的條件下獲利最多?表：費用定額（萬元/年）確定決策變量,建立線性規劃的數學模型先設變量:為項目A的工期;為項目B的工期;為對兩個不等式約束引入的非負松弛變量。再寫出其約束條件:最后寫出目標函數:用單純形解法尋求初始解表：初始單純形表注:選擇，作為基變量；選對應的變量進基；選對應的基變量出基；表中的“↑”表示該列為主元列,“←”表示該行為主元行,“（）”表示該括號中的數字為該表的主元素。用單純形解法尋求最優解表：最終單純形表注:所有的檢驗數均為非正值,即說明該表已經成為最優表。通過找主元、做初等變換得時的最優為:,即是=20/19年=1.053年=385天,=90/38年=2.368年=865天,,相對應的目標函數最大值為=447.37萬元。即該承包商的最佳投標方案為:必須將A項目的工期控制在385天,B項目的工期控制在865天內,最后可以獲利447.37萬元。三．對偶單純形法的產生與單純形法相對應的還有對偶單純形法，對偶理論是最優化中很重要的理論。對每一個線性規劃問題，可以構造另一個與之相應且密切的線性規劃問題，如果前者稱為原是問題，后者就稱為對偶問題。線性規劃的原始問題和對偶問題無論從數學的角度還是從經濟的角度都有十分密切的關系。四．單純形法所面臨的的問題單純形法從其產生日起，因為其能有效的解決各類線性規劃問題而得到越來越廣泛的應用。隨著線性規劃問題規模的擴大，對單純形法性能的了解也變得十分必要。大量的統計分析和理論研究表明單純形法求解線性規劃問題的平均迭代次數是問題約束個數的一個不大的倍數。但是我們假設所需的運算工作量的階數是以冪指數計算的，那么按照我們現在計算機的工作效率，得到結果將會是年后的事了。雖然這是人為設想的最壞情況，但這方面的研究工作者卻提出了兩個問題：對線性規劃問題是否存在時間復雜性是多項式的算法；如果存在多項式時間算法，如何設計這樣的算法。對于第一個問題，前蘇聯數學家Khachiyan在1979年作出了正面回答，提出了橢球算法求不等式問題的解，并證明了算法的時間復雜性是多項式的。利用對偶理論，線性規劃問題可以轉化成不等式問題，這就明確回答了對線性規劃存在多項式算法，但是計算的實際表明，橢球算法的效果要比單純形法差得多，不是一個又實用價值的算法。對于第二個問題的回答始于在美國貝爾工作室工作的印度數學家Karmarkar在1984年的杰出工作。他對線性規劃的求解提出了一個具有多項式時間復雜度的內點算法。現如今，內點算法已經成為求解大規模線性規劃問題的有效算法之一。我們已經知道，求線性規劃問題解的單純形法在問題的基本可行解中確定最優解，在幾何上，每次迭代都是沿著可行域的邊界從一個頂點到另一個更好的頂點移動來實現。而內點算法卻完全不同，他是從可行域中的一個嚴格內點開始，產生一個使目標函數值逐步改善的嚴格內點序列，并最終收斂于問題的最優解。五．單純形法的引申提起單純形法，就不能不說靈敏度分析。所謂靈敏度分析是指在一個線性規劃問題的有關數據，如果價值系數向量，或約束的右端向量，或約束系數矩陣的某些元素發生變化或存在某種程度的誤差時，分析最優解所受的影響，并如何從原有的最優解確定變化后的最優解。而在實際問題提煉而成的線性規劃問題，由于環境、條件、時間以及具體要求等各種可能因素的變化，導致相關數據的變化；其次這些實際數據大部分是通過觀測，測量和統計出來的，出現誤差是常有的、難免的。因此利用靈敏度分析確定數據有誤差或數據發生變化后線性規劃問題的最優解是十分必要的。以工廠生產3種產品A,B,C，有5種生產方案為例簡單的介紹一下靈敏度分析，下面給出兩個表：表：每組方案生產產品的數量及單位售價品種組別單位售價/元12345產量A3244010B612145C265184表：每組方案耗費的資源及生產費用資源組別資源限制12345耗時人工工時/h0461280h/天機器工時/h1121150h/天每組生產費用481930447其中，該工廠與某單位簽訂合同，規定每天供應A產品至少一個，求收益最大的組合方案。首先設為各種方案的組數（），為A產品的剩余變量，分別為工人工時和機器工時的松弛變量，工廠收益為。經過整理，我們可以得到如下線性規劃：利用單純形法解上述模型，下面給出最后結果：表1：最優單純形表2030405450002026100.410-0.2-0.20.43016011.40.50-0.20.3-0.6458000.2-0.510.4-0.11.2OBJ=136020305912.54580.54400-19-7.50-8-0.5-44影子價格在線性規劃中，某一種資源的影子價格是指在當前最優解的基礎上，該資源減少一個（很小）單位時目標函數的變化率。而松弛變量的機會成本就是這個資源的影子價格。分析：從表一可以看出，的機會成本為8。由于是產品A的剩余變量，所以產品A的影子價格為，它的經濟意義是：如果多生產A產品1個單位，則將使目標函數減少8元。反之，如果少生產A產品1個單位，則將使目標函數數值增加8元，因此，A產品的訂購合同不合理。我們通過單純形表可以看出是機器的松弛變量，它的影子價格為44，所以機器的租費上限應為44元。基變量價值系數的靈敏度分析我們不難看出，當某一基變量的價值系數從變化為時，將會引起所有非基變量的機會成本發生變化，從而導致所有非基變量檢驗數隨之都發生變化，則原線性規劃的最優解結構將會發生變化。為了保證所有非基變量的檢驗數仍然滿足最有檢驗的條件，所以基變量的價值系數的變化范圍應該滿足分析：根據表一可以看出，第2組生產方案為基變量，生產組數為16。我們不難求的對應的價值系數的變化范圍為，如果第二組的生產費用提高2元，改組的純收益將會降低2元，因為超出了變化范圍的下限，所以原生產方案需要做調整。如果變為28，的檢驗數將變為1，這說明將成為基變量替代。非基變量價值系數的靈敏度分析我們在計算單純形表是不難發現，當某一非基變量的價值系數從變化為時，僅僅引起非基變量本身的檢驗數發生變化，卻不會導致其他非基本兩的檢驗數發生變化，故而保持該非基變量的檢驗數為正的條件是這個式子的經濟意義是，在多產品的生產問題中，可能有某一種產品不在最優生產計劃中，如果它的價值系數