《線性規(guī)劃理論方法及應(yīng)用研究》6500字（論文）

線性規(guī)劃理論方法及應(yīng)用研究目錄TOC\o"1-2"\h\u18047線性規(guī)劃理論方法及應(yīng)用研究 16191一、線性規(guī)劃理論及方法的發(fā)展進程 228534二、線性規(guī)劃的主要內(nèi)容 332456（一）線性規(guī)劃問題及其數(shù)學(xué)模型 325297（二）線性規(guī)劃模型的具體分析及應(yīng)用Excel求解線性規(guī)劃問題 419562三、現(xiàn)階段成果的評價 811127四、發(fā)展前景的預(yù)測 925590（6）數(shù)學(xué)軟件的研發(fā)和運籌學(xué)發(fā)展之間仍然存在較大的差距。 932246結(jié)語 1022575參考文獻 10摘要：運籌學(xué)是包含多種學(xué)科的綜合性學(xué)科，是最早形成的一門軟科學(xué)。它把科學(xué)的方法、技術(shù)和工具應(yīng)用到包括一個系統(tǒng)管理在內(nèi)的各種問題上，以便為那些掌管系統(tǒng)的人們提供最佳的解決問題的辦法。它用科學(xué)的方法研究與某一系統(tǒng)的最優(yōu)管理有關(guān)的問題。它能幫助決策人解決那些可以用定量方法和有關(guān)理論來處理的問題。關(guān)鍵詞：運籌學(xué)；線性規(guī)劃；發(fā)展；應(yīng)用在中國的戰(zhàn)國時代，曾經(jīng)有過一個流傳后世并被引為經(jīng)典的賽馬比賽，這就是大家都熟知的田忌賽馬。這個故事說明在現(xiàn)有的條件下，經(jīng)過適當?shù)幕I劃、安排，選擇一個最好的方案，就會取得最好的效果?？梢?，籌劃安排是十分重要的。這種在古代就已經(jīng)產(chǎn)生的經(jīng)過策劃安排取得好的結(jié)果的思想，就是古代的運籌學(xué)思想。運籌學(xué)是包含多種學(xué)科的綜合性學(xué)科，是最早形成的一門軟科學(xué)。它把科學(xué)的方法、技術(shù)和工具應(yīng)用到包括一個系統(tǒng)管理在內(nèi)的各種問題上，以便為那些掌管系統(tǒng)的人們提供最佳的解決問題的辦法。它用科學(xué)的方法研究與某一系統(tǒng)的最優(yōu)管理有關(guān)的問題。它能幫助決策人解決那些可以用定量方法和有關(guān)理論來處理的問題。現(xiàn)在普遍認為，運籌學(xué)是近代應(yīng)用數(shù)學(xué)的一個分支，主要是將生產(chǎn)、管理等事件中出現(xiàn)的一些帶有普遍性的運籌問題加以提煉，然后利用數(shù)學(xué)方法進行解決。前者提供模型，后者提供理論和方法。運籌學(xué)主要研究經(jīng)濟活動和軍事活動中能用數(shù)量來表達的有關(guān)策劃、管理方面的問題。當然，隨著客觀實際的發(fā)展，運籌學(xué)的許多內(nèi)容不但研究經(jīng)濟和軍事活動，有些已經(jīng)深入到日常生活當中去了。運籌學(xué)可以根據(jù)問題的要求，通過數(shù)學(xué)上的分析、運算，得出各種各樣的結(jié)果，最后提出綜合性的合理安排，以達到最好的效果。線性規(guī)劃是運籌學(xué)的其中一個理論，如果約束條件和目標函數(shù)都是呈線性關(guān)系的就叫線性規(guī)劃。要解決線性規(guī)劃問題，從理論上講都要解線性方程組，因此解線性方程組的方法，以及關(guān)于行列式、矩陣的知識，就是線性規(guī)劃中非常必要的工具。線性規(guī)劃及其解法—單純形法的出現(xiàn)，對運籌學(xué)的發(fā)展起了重大的推動作用。許多實際問題都可以化成線性規(guī)劃來解決，而單純形法有是一個行之有效的算法，加上計算機的出現(xiàn)，使一些大型復(fù)雜的實際問題的解決成為現(xiàn)實。一、線性規(guī)劃理論及方法的發(fā)展進程1939年，蘇聯(lián)學(xué)者Kantorovich為前蘇聯(lián)政府解決優(yōu)化問題時提出了極值問題，并且提出了解乘數(shù)法的新方法，可惜他的工作在當時并未引起足夠的重視。事實上，他所提出的問題正是線性規(guī)劃的雛形。與此同時，美國的線性規(guī)劃卻獲得了飛快的發(fā)展。1941年，Hitchcock提出運輸問題；1945年，Stigler提出了營養(yǎng)問題；1945年，Koopmans提出了經(jīng)濟問題。而奠定線性規(guī)劃整套理論方法的，還要說是G.B.Dantzig，他被譽為“線性規(guī)劃之父”。他在1947年擔(dān)任美國空軍審計官的數(shù)學(xué)顧問，為找到解決問題的機制化工具，提出了“在一組線性方程或不等式約束下，求某一線性形式極小值問題的數(shù)學(xué)模型”，這便是“線性規(guī)劃”（linearprogramming）這一經(jīng)典優(yōu)化模型。而“線性規(guī)劃”這一名字的由來是在之后1948年，Koopmans和Dantzig在海灘散步時共同想出的。1947年夏天，Dantzig提出了單純形算法。這個算法在后來被評為20世紀最偉大的算法之一。盡管單純形法(Simplexmethod)作為解決線性規(guī)劃的有效方法在學(xué)術(shù)界具有統(tǒng)治地位，但是1971年，Klee和Minty兩位學(xué)者構(gòu)造出一個例子，該例子下單純形法的運作需要訪問指數(shù)數(shù)量級別的頂點，也就是說，在最壞情況下，單純形法是一個指數(shù)時間算法(exponential-timealgorithm)。Dantzig在得知這個消息后感嘆到他的噩夢到來了，單純形法并不是在任何情況下都是高效可行的。那么，是否有更加高效的算法，比如多項式時間算法(polynomial-timealgorithm)，來解決線性規(guī)劃問題呢？8年后，即1979年，L.G.Khachiyan發(fā)明了橢球算法(ellipsoidmethod)，這是第一個解決線性規(guī)劃問題的多項式時間算法。但是，這個算法雖然理論上是多項式時間運行，但是算法被證明是不切實際的，這個算法的杰出貢獻是在理論層面告訴世人，線性規(guī)劃是可以用多項式時間算法來解決的，同時也啟發(fā)了學(xué)者在更加深入的優(yōu)化領(lǐng)域進行算法開發(fā)。1984年，N.Karmarkar發(fā)明了內(nèi)點算法(interiorpointmethod)，這是線性規(guī)劃第一個實際可用的多項式時間算法。二、線性規(guī)劃的主要內(nèi)容（一）線性規(guī)劃問題及其數(shù)學(xué)模型1.線性規(guī)劃的模型決定于它的定義線性規(guī)劃的定義是：求一組變量的值，在滿足一組約束條件下，求得目標函數(shù)的最優(yōu)解。根據(jù)這個定義,就可以確定線性規(guī)劃模型的基本結(jié)構(gòu)。（1）變量變量又叫未知數(shù)，它是實際系統(tǒng)的未知因素,也是決策系統(tǒng)中的可控因素，一般稱為決策變量，常引用英文字母加下標來表示,如X,X，X，X等。（2）目標函數(shù)將實際系統(tǒng)的目標，用數(shù)學(xué)形式表現(xiàn)出來，就稱為目標函數(shù)，線性規(guī)劃的目標函數(shù)是求系統(tǒng)目標的數(shù)值，即極大值，如產(chǎn)值極大值、利潤極大值或者極小值，如成本極小值、費用極小值、損耗極小值等等。（3）約束條件約束條件是指實現(xiàn)系統(tǒng)目標的限制因素。它涉及到企業(yè)內(nèi)部條件和外部環(huán)境的各個方面,如原材料供應(yīng)、設(shè)備能力、計劃指標、產(chǎn)品質(zhì)量要求和市場銷售狀態(tài)等等，這些因素都對模型的變量起約束作用，故稱其為約束條件。約束條件的數(shù)學(xué)表示形式為三種，即≥、＝、≤.線性規(guī)劃的變量應(yīng)為正值，因為變量在實際問題中所代表的均為實物，所以不能為負。2.在經(jīng)濟管理中，線性規(guī)劃使用較多的是下述幾個方面的問題：（1）投資問題—確定有限投資額的最優(yōu)分配,使得收益最大或者見效快。（2）計劃安排問題—確定生產(chǎn)的品種和數(shù)量,使得產(chǎn)值或利潤最大，如資源配制問題。（3）任務(wù)分配問題—分配不同的工作給各個對象（勞動力或機床)，使產(chǎn)量最多、效率最高，如生產(chǎn)安排問題。（4）下料問題—如何下料，使得邊角料損失最小。（5）運輸問題—在物資調(diào)運過程中，確定最經(jīng)濟的調(diào)運方案。（6）庫存問題—如何確定最佳庫存量,做到即保證生產(chǎn)又節(jié)約資金等等。3.應(yīng)用線性規(guī)劃建立數(shù)學(xué)模型的三步驟：（1）明確問題，確定問題，列出約束條件。（2）收集資料，建立模型。（3）模型求解（最優(yōu)解），進行優(yōu)化后分析。其中，最困難的是建立模型，而建立模型的關(guān)鍵是明確問題、確定目標，在建立模型過程中花時間、花精力最大的是收集資料。4.線性規(guī)劃的數(shù)學(xué)模型的一般形式為:目標函數(shù)max（min）z=c1X+c2X+…+cnXn滿足約束條件：a11X+a12X,+…+a1nXn≤(＝，≥）b1a21X+a22X,+…+a2nXn≤（＝,≥)b2………………….am1X+am2X+…+amnXn≤(＝，≥)bmX，X，…,Xn≥0線性規(guī)劃模型的矩陣形式：目標函數(shù)max（min）Z=CX約束條件AX≤(＝,≥)b其中，C=(c1，c2，…,cn），X=(X，X，…Xn）Tb=(b1，b2，…bm)Ta11，a12，…a1nA=a21，a22,…a2n…………am1，am2,…amn（二）線性規(guī)劃模型的具體分析及應(yīng)用Excel求解線性規(guī)劃問題我們來看生產(chǎn)計劃問題：生產(chǎn)計劃是控制生產(chǎn)裝置運行的命令，要利用有限的資源獲得最大的經(jīng)濟效益,就必須制定最佳生產(chǎn)計劃。隨著公司生產(chǎn)裝置的不斷增多，生產(chǎn)計劃的制定變得越來越復(fù)雜.采用現(xiàn)代管理技術(shù)，建立數(shù)學(xué)模型，利用電子計算機求解,很容易得出最優(yōu)生產(chǎn)計劃。下面舉一案例說明（本案例出自《運籌學(xué)》，林齊寧,北京郵電大學(xué)出版社，2003年，P7)某工廠計劃用現(xiàn)有的銅、鉛兩種資源生產(chǎn)A、B兩種型號的電纜。A、B兩種型號的電纜單位售價分別為6萬元和4萬元。市場對A型電纜的需要量無限制,而對B電纜的最大需求量為7單位。生產(chǎn)單位產(chǎn)品A、B兩種型號電纜對銅、鉛的消耗量及可利用的銅、鉛數(shù)量如下表所示：表1：基本信息表

A型電纜B型電纜資源提供限量消耗：銅（噸）2110消耗：鉛（噸）118產(chǎn)品需要限量

7

售價(萬元）64

工廠應(yīng)該如何讓安排生產(chǎn)，才能使工廠總收入最大？解答過程如下：（1）決策變量設(shè)x1，x2分別代表A、B兩種型號電纜的生產(chǎn)量,f(x）為工廠總收入。（2）目標函數(shù)本問題的目標是工廠收益最大值Maxf（x)=6Xl+4X2（3）約束條件：A型電纜B型電纜資源提供限量消耗：銅（噸）2110消耗：鉛（噸）118產(chǎn)品需要限量7售價(萬元）64則上述問題可以用如下數(shù)學(xué)模型(線性規(guī)劃模型）來表示：Obj:Maxf（x）=6Xl+4X22Xl+X2≤10銅資源約束s.t.Xl+X2≤8鉛資源約束X2≤7產(chǎn)量數(shù)量約束Xl，X2≥0產(chǎn)量質(zhì)量約束用Excel輔助計算求解。首先，根據(jù)問題建立電子表格模型具體步驟如下：（1）收集問題的數(shù)據(jù)。（2）在電子表格的數(shù)據(jù)單元格中輸入數(shù)據(jù)。（3）確定對活動水平需要作出的決策并且指定可變單元顯示這些決策。（4）確定對這些決策的約束條件并引入需具體化這些約束條件的輸出單元格。（5）選擇要輸入目標單元格的完全績效測度。（6）使用SUMPRODUCT函數(shù)為每個輸出單元格（包括目標單元格）輸入合適的值。然后,建立了起電子表格模型：再進行規(guī)劃求解：規(guī)劃求解的選項對話框：最后,保存求解結(jié)果:最終結(jié)果如下圖所示:可以利用Excel中的“規(guī)劃求解”功能可以直接到“敏感性分析”,利用該報告可以很方便地進行靈敏度分析：敏感性報告的內(nèi)容由兩部分組成：（1）位于報告上部的“可變單元格"部分反映了目標函數(shù)中的系數(shù)變化對最優(yōu)解產(chǎn)生的影響.第一列“單元格”是指決策變量所在單元格地址。第二列“名字”是這些決策變量的名稱.第三列“終值”是決策變量的終值,即最優(yōu)解。第四列是“遞減成本”,它的絕對值表示目標函數(shù)中決策變量的系數(shù)必須改進多少，才能得到該決策變量的正數(shù)解.第五列“目標式系數(shù)”是指目標函數(shù)中的系數(shù)。第六列與第七列分別是“允許的增量"和“允許的減量”它們表示目標函數(shù)中的系數(shù)在允許的增量和減量范圍內(nèi)變化時，最優(yōu)解不變。（2）位于報告下部的“約束”部分反映了約束條件右端值變化目標值產(chǎn)生的影響。目標函數(shù)系數(shù)同時變動的情況：當各個系數(shù)變動的百分比之和小于100％時，最優(yōu)解不發(fā)生變化;當各個系數(shù)變動的百分比之和等于100％時，最優(yōu)解不發(fā)生變化；當各個系數(shù)變動的百分比之和大于100％時，不能確定最優(yōu)解的變化，可能改變，也可能不變.約束右端值同時變動：當各個右端值變動的百分比之和小于100％時,影子價格有效;當各個右端值變動的百分比之和等于100%時，影子價格有效；當各個右端值變動的百分比之和大于100％時,不能保證影子價格依然有效。三、現(xiàn)階段成果的評價公司生產(chǎn)的復(fù)雜性使得手編計劃的工作極其復(fù)雜,手編計劃的工作量大，而且更為重要的是很難甚至無法實現(xiàn)優(yōu)化，會給公司造成很大的機會損失。采用線性規(guī)劃模型制定公司計劃和進行決策分析是可行的、必要的.在這個效率優(yōu)先的時代,眾多領(lǐng)域中，但凡涉及最優(yōu)解的問題，首先考慮的方法即是線性規(guī)劃。要建立一個切合實際的線型規(guī)劃模型，需要工程技術(shù)人員、財務(wù)管理人員等的通力配合，否則會失去很多有用的信息。線性規(guī)劃作為運籌學(xué)的一個分支發(fā)展至今，從建立模型到求的最優(yōu)解的整個過程,都有一套發(fā)展較為完備的體系和理論.涉及到生產(chǎn)計劃以及類似的問題時，線性規(guī)劃顯然是首選的方法。然而，線性規(guī)劃并不是沒有其因為方法本身或者問題本身超出方法談到的要求所產(chǎn)生的某些局限性。非常明顯的一點是,線性規(guī)劃模型實質(zhì)上還是一個靜態(tài)的模型.事實上，隨著約束條件的變化，目標函數(shù)中的一些指標常常并非一成不變。舉例來說,在考慮生產(chǎn)計劃，即如何選擇產(chǎn)業(yè)結(jié)構(gòu)使生產(chǎn)成本最低的時候，成本系數(shù)實質(zhì)上是一個會根據(jù)產(chǎn)業(yè)結(jié)構(gòu)和模式之變化而難以絕對保持靜態(tài)的變量，這就勢必導(dǎo)致模型的理想化。另一方面，生產(chǎn)過程也不是一個絕對靜態(tài)的過程，即產(chǎn)業(yè)結(jié)構(gòu)本身，或者說約束條件中的每一項指標，也會產(chǎn)生某些動態(tài)的過程，即它并非可以完全按照單純形法中矩陣變換的簡單方法去解決.一旦考慮到時間軸上的某些變化，問題的復(fù)雜程度就不是線性規(guī)劃模型多能夠做到了的?？偟膩碚f，線性規(guī)劃模型是一種比較機械性的模型，這種機械性決定它在某種意義上不可避免的局限性。四、發(fā)展前景的預(yù)測運籌學(xué)作為一門新興學(xué)科，一門處于年青發(fā)展時期的學(xué)科，在理論研究和應(yīng)用研究的諸多方面，無論廣度和深度來說都有著無限滾廣闊的前景?，F(xiàn)在的問題是，運行后學(xué)今后究竟應(yīng)該朝哪個方向發(fā)展？這是運籌學(xué)界普遍關(guān)心的問題。關(guān)于運籌學(xué)將往哪個方向發(fā)展，從70年代起就在西方運籌學(xué)界引起過爭論，至今還沒有一個統(tǒng)一的結(jié)論。美國前運籌學(xué)會主S.Bonder認為，運籌學(xué)應(yīng)在三個領(lǐng)域發(fā)展：運籌學(xué)應(yīng)用、運籌科學(xué)、運籌數(shù)學(xué)，并強調(diào)在協(xié)調(diào)發(fā)展的同時重點發(fā)展前兩者。這是由于運籌數(shù)學(xué)在70年代已形成一個強有力的分支，對問題的數(shù)學(xué)描述已相當完善，卻忘掉了運籌學(xué)的原有特色，忽視了對多學(xué)科的橫向交叉聯(lián)系和解決實際問題的研究?，F(xiàn)在，運籌學(xué)工作者面臨的大量新問題是：經(jīng)濟、技術(shù)、社會、生態(tài)和政治因素交叉在一體的復(fù)雜系統(tǒng)，所以從70年代末80年代初，不少運籌學(xué)家提出“要注意研究大系統(tǒng)”，“要從運籌學(xué)到系統(tǒng)分析”。由于研究大系統(tǒng)的時間范圍有可能很長，還必須與未來學(xué)緊密結(jié)合起來；面臨的問題大多是涉及技術(shù)、經(jīng)濟、社會、心理等綜合因素，在運籌學(xué)中除了常用的數(shù)學(xué)方法，還引入了一些非數(shù)學(xué)的方法和理論。如美國運籌學(xué)家T.L.Saaty于70年代末期提出的層次分析法（AHP），可以看作是解決非結(jié)構(gòu)問題的一個嘗試。針對這種狀況，P.B.Checkland從方法論上對此進行了劃分。他把傳統(tǒng)的運籌學(xué)方法稱為硬系統(tǒng)思考，認為它適合解決那種結(jié)構(gòu)明確的系統(tǒng)的戰(zhàn)術(shù)及技術(shù)問題，而對于結(jié)構(gòu)不明確的、有人參與活動的系統(tǒng)就要采用軟系統(tǒng)思考的方法。借助電子計算機，研究軟系統(tǒng)的概念和運用方法應(yīng)是今后運籌學(xué)發(fā)展的一個方向。但不管怎么爭論，運籌學(xué)未來發(fā)展也必出現(xiàn)以下的特點：（1）運籌學(xué)的理論研究將會得到進一步系統(tǒng)地、深入地發(fā)展。（2）運籌學(xué)跨學(xué)科的特點必將進一步延伸和發(fā)展。（3）運籌學(xué)沿原有的分支向前發(fā)展。（4）一些非數(shù)學(xué)的方法和理論將引入運籌學(xué)這是因為研究的問題大多涉及技術(shù)、經(jīng)濟、社會、心理綜合因素的研究，而這種問題是非結(jié)構(gòu)性的問題（如研究世界性的問題、研究國家政策等），運用通常地、精巧的數(shù)學(xué)方法很難解決。（5）接均問題的過程將變?yōu)闆Q策者和分析者共同參與、發(fā)揮其創(chuàng)造性的過程。（6）數(shù)學(xué)軟件的研發(fā)和運籌學(xué)發(fā)展之間仍然存在較大的差距。中國運籌學(xué)學(xué)會從中國數(shù)學(xué)學(xué)會獨立出來也說明了運籌學(xué)雖然已數(shù)學(xué)為基礎(chǔ)，但同數(shù)學(xué)學(xué)科有本質(zhì)的不同。運籌學(xué)家除了推動運籌學(xué)基本理論的發(fā)展，還要對社會肩負起與數(shù)學(xué)家不同的責(zé)任。而1994年美國運籌學(xué)會和管理科學(xué)學(xué)會的合并成立TNFORMF，是國際運籌學(xué)界的一件大事。目前，運籌學(xué)和管理學(xué)的合并也引起了包括中國在內(nèi)的世界各國的極大關(guān)注。運籌學(xué)未來的發(fā)展會出現(xiàn)在更多的社會發(fā)展領(lǐng)域?？傊\籌學(xué)發(fā)展的前景是光明的，道路是曲折的。結(jié)語近二十年來，信息科學(xué)、生命科學(xué)等現(xiàn)代高科技對人類社會產(chǎn)生了巨大影響，運籌學(xué)工作者還關(guān)注到其中一些運籌學(xué)起作用的新的工作方向。例如，將全局最優(yōu)化、圖論、神經(jīng)網(wǎng)絡(luò)等運籌學(xué)理論及方法應(yīng)用于分子