最優化方法課程設計線性規劃模型理論與發展學院：理學院班級：信息102班學號：姓名：1理論與發展線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法.在經濟管理、交通運輸、工農業生產等經濟活動中，提高經濟效果是人們不可缺少的要求，而提高經濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產工藝，使用新設備和新型原材料.二是生產組織與計劃的改進，即合理安排人力物力資源.線性規劃所研究的是：在一定條件下，合理安排人力物力等資源，使經濟效果達到最好.一般地，求線性目標函數在線性約束條件下的最大值或最小值的問題，統稱為線性規劃問題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變量、約束條件、目標函數是線性規劃的三要素.在企業的各項管理活動中，例如計劃、生產、運輸、技術等問題，線性規劃是指從各種限制條件的組合中，選擇出最為合理的計算方法，建立線性規劃模型從而求得最佳結果。解線性規劃問題有很多種方法，內點法、單純形法、對偶單純形法等等，而具體求解則可用圖解法等。法國數學家J.-B.-J.傅里葉和C.瓦萊一普森分別于1832和1911年獨立地提出線性規劃的想法，但未引起注意。1939年蘇聯數學家口.B.康托羅維奇在《生產組織與計劃中的數學方法》一書中提出線性規劃問題，也未引起重視。1947年美國數學家G.B.Dantzing提出求解線性規劃的單純形法，為這門學科奠定了基礎。1947年美國數學家J.von諾伊曼提出對偶理論，開創了線性規劃的許多新的研究領域，擴大了它的應用范圍和解題能力。1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域，為此與康托羅維奇一起獲1975年諾貝爾經濟學獎。50年代后對線性規劃進行大量的理論研究，并涌現出一大批新的算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題，1956年A.塔克提出互補松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的算法研究。由于數字電子計算機的發展，出現了許多線性規劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規劃問題。1979年蘇聯數學家L.G.Khachian提出解線性規劃問題的橢球算法，并證明它是多項式時間算法。1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間算法。用這種方法求解線性規劃問題在變量個數為5000時只要單純形法所用時間的1/50。現已形成線性規劃多項式算法理論。50年代后線性規劃的應用范圍不斷擴大。2模型建立（一）結構線性規劃的模型決定于它的定義，線性規劃的定義是：求一組變量的值，在滿足一組約束條件下，求得目標函數的最優解。根據這個定義，就可以確定線性規劃模型的基本結構。（1） 變量。變量又叫未知數，它是實際系統的未知因素，也是決策系統中的可控因素，一般稱為決策變量，常引用英文字母加下標來表示，如X，X，X，l2 3Xmn等。（2） 目標函數。將實際系統的目標，用數學形式表現出來，就稱為目標函數。線性規劃的目標函數是求系統目標的數值，即極大值，如產值極大值、利潤極大值或者極小值，如成本極小值、費用極小值、損耗極小值等等。（3） 約束條件。約束條件是指實現系統目標的限制因素。（二）建立模型而應用線性規劃建立數學模型的三步驟：明確問題，確定問題，列出約束條件。收集資料，建立模型。模型求解(最優解)，進行優化后分析。其中，最困難的是建立模型，而建立模型的關鍵是明確問題、確定目標，在建立模型過程中花時間、花精力最大的是收集資料。所建立的數學模型具有以下特點：1、 每個模型都有若十個決策變量(x1，x2,x3……，xn)，其中n為決策變量個數。決策變量的一組值表示一種方案，同時決策變量一般是非負的。2、 目標函數是決策變量的線性函數，根據具體問題可以是最大化血ax)或最小化(min)，二者統稱為最優化(opt)。3、 約束條件也是決策變量的線性函數。當我們得到的數學模型的目標函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。線性規劃的數學模型的一般形式為：目標函數max(min)z-cX+cX+...+cX11 2 2 nn滿足約束條件：aX+aX+...+aX<(-,>)bTOC\o"1-5"\h\z11 1 12 2 1nn 1aX+aX+...+aX<(-,>)b21 1 22 2 2nn 2aX+aX+...+aX<(-,>)bm1 1m2 2 mnn mX],X2，...,X>0線性規劃模型的矩陣形式：目標函數max(min)z-cX約束條件AX<(-,>)b其中，c-(c,c,...,c),X-(X,X,...,X)T，b-(b,b,...,b)t1 2n 1 2 n 1 2m(aa???a)ii12inA=aa???a21???22??????2n???.amiam2???a/mn/3實例為了具體的了解線性規劃問題，可以舉一個實例，我們來看生產計劃問題：生產計劃是控制生產裝置運行的命令，要利用有限的資源獲得最大的經濟效益，就必須制定最佳生產計劃。隨著公司生產裝置的不斷增多，生產計劃的制定變得越來越復雜。采用現代管理技術，建立數學模型，利用電子計算機求解，很容易得出最優生產計劃。下面舉一案例說明：某工廠計劃用現有的木材、鋼鐵兩種資源生產A、B、C三種型號的零件。A、B、C三種型號的零件單位售價分別為2萬元、3萬元和4萬元。市場對A型零件的需要量無限制，對B零件的最大需求量為7單位，對C零件的最大需求量是10單位。生產單位產品A、B、C兩種型號零件對木材、鋼鐵的消耗量及可利用的木材、鋼鐵數量如下表所示：表1：基本信息表A型零件B型零件C型零件資源提供限量消耗：木材(噸)21112消耗：鋼鐵(噸)32110產品需要限量710售價(萬元)642工廠應該如何讓安排生產，才能使工廠總收入最大?4求解解答過程如下：(1)決策變量設匚x,x分別代表A、B、C三種型號零件的生產量，f(x)為工廠總收入。1 2 3(2)目標函數本問題的目標是工廠收益最大值maxf(x)=6x+4x+2x（3）約束條件:A型零件B型零件C型零件資源提供限量消耗：木材（噸）21112消耗：鋼鐵（噸）32110產品需要限量710售價（萬元）642則上述問題可以用如下數學模型（線性規劃模型）來表示:maxf(x)=6x+4x+2x2x1+x2+x3<12木材資源約束3x+2x+x<10鋼鐵資源約束1 2 3%<7產量數量約束x3<10產量質量約束x,x,x>01 2 3我們可以用Excel輔助計算求解，也可用matlab，lingo等軟件，這里我們用excel示例一下。首先，建立了起電子表格模型：理零件B型零件C型零件資源消耗總量資源提供限量消耗：木材（噸）211012消耗：鋼鐵（噸）321010產品需要限量710生產量售價（萬兀）642工廠總收入0再進行規劃求解:

最后，保存求解結果:規劃求解結冥規劃求解鏘!1—解r可滿足所有的約束及最憂狀兄報告運算結果報告后保留規劃求解的解 Siittig.......極限值報告還原初值□返回"規劃求解網"對話框 制作報告大綱確定 取消 ，報告創建指定的報告類型r并將每個報告瞄在工柞簿單獨的工作表中.最終結果如下圖所示:

ABCDEFA型零件B型零件C型零件資源消耗總量資源捏供限量消耗：木材（噸）2111212消耗：鋼鐵（噸）3211010產品需要限量710生產量107售價（力兀）642工廠總收入20可以還利用Excel中的“規劃求解”功能可以直接到“敏感性分析”利用該報告可以很方便地進行靈敏度分析：WfSOffice個人版敏感性報告工作表：[Bookl]Sheetl報告南建立：10/17/20139:20:51PI可戈單兀格單元格名稱終遞涯值成本目標式系數允許的增量允許的誠量$B$5生產量建零件1 0600$C$5生產量B型零件0 0400$D$5生產量C型零件7 0200約束終陰影約束允許的允許的單元格名稱值價格限制值增量誠量$E$2消耗：刃R材（噸）資源消耗總量12 0124.6666666672$E$3消瓦車M鐵（噸）資源消耗總量10 2101.22.8敏感性報告的內容由兩部分組成：（1）位于報告上部的“可變單元格”部分反映了目標函數中的系數變化對最優解產生的影響。第一列“單元格”是指決策變量所在單元格地址。第二列“名字”是這些決策變量的名稱。第三列“終值”是決策變量的終值，即最優解。第四列是“遞減成本”，它的絕對值表示目標函數中決策變量的系數必須改進多少，才能得到該決策變量的正數解。第五列“目標式系數”是指目標函數中的系數。第六列與第七列分別是“允許的增量”和“允許的減量”它們表示目標函數中的系數在允許的增量和減量范圍內變化時，最優解不變。(2)位于報告下部的“約束”部分反映了約束條件右端值變化目標值產生影響。目標函數系數同時變動的情況：當各個系數變動的百分比之和小于100%時，最優解不發生變化；當各個系數變動的百分比之和等于100%時，最優解不發生變化；當各個系數變動的百分比之和大于100%時，不能確定最優解的變化，可能改變，也可能不變。約束右端值同時變動：當各個右端值變動的百分比之和小于100%時，影子價格有效；當各個右端值變動的百分比之和等于100%時，影子價格有效；當各個右端值變動的百分比之和大于100%時，不能保證影子價格依然有效。5結果與分析公司生產的復雜性使得于編計劃的工作極其復雜，手編計劃的工作量大，而且更為重要的是很難甚至無法實現優化，會給公司造成很大的機會損失。采用線性規劃模型制定公司計劃和進行決策分析是可行的、必要的。在這個效率優先的時代，眾多領域中，但凡涉及最優解的問題，首先考慮的方法即是線性規劃。要建立一個切合實際的線型規劃模型，需要工程技術人員、財務管理人員等的通力配合，否則會失去很多有用的信息。線性規劃作為運籌學的一個分支發展至今，從建立模型到求的最優解的整個過程，都有一套發展較為完備的體系和理論。涉及到生產計劃以及類似的問題時，線性規劃顯然是首選的方法。然而，線性規劃并不是沒有其因為方法本身或者問題本身超出方法談到的要求所產生的某些局限性。非常明顯的一點是，線性規劃模型實質上還是一個靜態的模型。事實上，隨著約束條件的變化，目標函數中的一些指標常常并非一成不變。舉例來說，在考慮生產計劃，即如何選擇產業結構使生產成本最低的時候，成本系數實質上是一個會根據產業結構和模式之變化而難以絕對保持靜態的變量，這