最優(yōu)化結(jié)課論文

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