《運籌學線性規(guī)劃實驗報告》5800字（論文）

緒論1.1研究背景在中國的戰(zhàn)國時代，曾經有過一個流傳后世并被引為經典的賽馬比賽，這就是大家都熟知的田忌賽馬。這個故事說明在現(xiàn)有的條件下，經過適當?shù)幕I劃、安排，選擇一個最好的方案，就會取得最好的效果。可見，籌劃安排是十分重要的。這種在古代就已經產生的經過策劃安排取得好的結果的思想，就是古代的運籌學思想。運籌學因為涉及學科較多，將所有方法和技巧都囊括在系統(tǒng)管理中，通過正確的管理方法為人們提供解決辦法，所以這種形式決定了它具有很強的綜合性。在通過前期理論研究與方法優(yōu)化，讓人們在具體的實踐過程中有具體的數(shù)據和科學的方法為依據，使得問題得以改善和解決，這種科學的管理方法也廣為推廣和使用，解決了人們生活中的許多具體問題。運籌學是一個數(shù)學學科的細分，將具體生活中反復出現(xiàn)的涉及運籌的問題進行綜合分析再加以整理，再用科學的方法去解決問題，具備普世意義，不僅解決了生產生活中的難題，同時將問題進行歸納，總結方法。運籌學研究的方向隨著科學的發(fā)展和社會的進步，不再僅限經濟與軍事，而是在經過時間的推移，滲透到人們的生活中，從曾經用數(shù)字表現(xiàn)經濟管理方針中出現(xiàn)的問題，到如今生活中處處體現(xiàn)運籌學。因為它的綜合性與廣泛性，切實將數(shù)學中的數(shù)字運用，在經過計算后得出的結論進行科學的分析與總結，從而全方位更完善地提出方法。而線性規(guī)劃就屬于運籌學中的細分內容，當出現(xiàn)的限制因素與需要解決問題的目標存在線性關系，那么我們將這樣的情況稱為線性規(guī)劃。那么，要解決線性問題最重要的方法需要依靠方程組，同時也會涉及到其他數(shù)學學科相關知識，這是解決線性規(guī)劃的關鍵。總而言之，線性規(guī)劃以及解決線性規(guī)劃問題的方法都是統(tǒng)籌學中必不可少的重要組成部分，也是我們生活中解決問題不可或缺的辦法。單純形法讓數(shù)學學科中出現(xiàn)的復雜問題簡單化，同時也能將方法融入到具體的計算與實踐中，使其具有可實施性。1.2線性規(guī)劃理論及方法的發(fā)展進程1939年，蘇聯(lián)學者Kantorovich為前蘇聯(lián)政府解決優(yōu)化問題時提出了極值問題，并且提出了解乘數(shù)法的新方法，可惜他的工作在當時并未引起足夠的重視。事實上，他所提出的問題正是線性規(guī)劃的雛形。與此同時，美國的線性規(guī)劃卻獲得了飛快的發(fā)展。1941年，Hitchcock提出運輸問題；1945年，Stigler提出了營養(yǎng)問題；1945年，Koopmans提出了經濟問題。而奠定線性規(guī)劃整套理論方法的，還要說是G.B.Dantzig，他被譽為“線性規(guī)劃之父”。他在1947年擔任美國空軍審計官的數(shù)學顧問，為找到解決問題的機制化工具，提出了“在一組線性方程或不等式約束下，求某一線性形式極小值問題的數(shù)學模型”，這便是“線性規(guī)劃”（linearprogramming）這一經典優(yōu)化模型。而“線性規(guī)劃”這一名字的由來是在之后1948年，Koopmans和Dantzig在海灘散步時共同想出的。1947年夏天，Dantzig提出了單純形算法。這個算法在后來被評為20世紀最偉大的算法之一。盡管單純形法(Simplexmethod)作為解決線性規(guī)劃的有效方法在學術界具有統(tǒng)治地位，但是1971年，Klee和Minty兩位學者構造出一個例子，該例子下單純形法的運作需要訪問指數(shù)數(shù)量級別的頂點，也就是說，在最壞情況下，單純形法是一個指數(shù)時間算法(exponential-timealgorithm)。Dantzig在得知這個消息后感嘆到他的噩夢到來了，單純形法并不是在任何情況下都是高效可行的。那么，是否有更加高效的算法，比如多項式時間算法(polynomial-timealgorithm)，來解決線性規(guī)劃問題呢？8年后，即1979年，L.G.Khachiyan發(fā)明了橢球算法(ellipsoidmethod)，這是第一個解決線性規(guī)劃問題的多項式時間算法。但是，這個算法雖然理論上是多項式時間運行，但是算法被證明是不切實際的，這個算法的杰出貢獻是在理論層面告訴世人，線性規(guī)劃是可以用多項式時間算法來解決的，同時也啟發(fā)了學者在更加深入的優(yōu)化領域進行算法開發(fā)。1984年，N.Karmarkar發(fā)明了內點算法(interiorpointmethod)，這是線性規(guī)劃第一個實際可用的多項式時間算法。1.3線性規(guī)劃問題及其數(shù)學模型1.3.1線性規(guī)劃的模型決定于它的定義究竟什么是線性規(guī)劃呢？從本質上來說，也就是將變化的量值，賦予所以可行的前提，最后求得的解也是最完美的解。這也奠定了線性規(guī)劃模型在這一基礎上的雛形。首先，這種變量由于其特殊性，處于一直變化的狀態(tài)，那么它在實際系統(tǒng)中就是未知的，但也是這種未知決定了預知范圍內的可控因素；其次，將這種目標函數(shù)通過數(shù)學形式表現(xiàn)出來，求出具體的數(shù)值，也就是極值，這種極值隨著目標要求而變大或變小。當所需目標為最大時，使生產總值最大，利益最大化時，這個極值即為最大值，當所需目標為最小時，使消耗值最小，所需成本為最小時，這個極值為最小。最后，所有具體目標的實現(xiàn)也需要分析其內部原因與外部因素導致的結果，所有環(huán)節(jié)中產生的問題都成為影響最后結果的關鍵。需要結合實際問題進行具體分析，從而使問題得到解決，而這種不可控因素會對結果產生一定的影響，我們也稱之為約束條件。而這種線性規(guī)劃在實際運用中為具體的值，所以它的變量一定是正值1.3.2線性規(guī)劃在實際管理過程中的經濟問題（1）投入：做好前期計劃與資源分配，正確分析投入比與產出比，讓利益最大化。（2）實際計劃：根據實際計劃決定具體生產，其目的是追求最終的產值。（3）具體實踐：將需要完成的任務進行具體分配，桉需分配或按勞分配，使最終產值最大。（4）物料使用：有關具體下料問題，使在具體使用過程中利用最多損耗最小，堅持不浪費原則。（5）物資調度：在具體運輸過程中，制定經濟可行方針，節(jié)省資源。（6）清理庫存：根據前期的計劃安排確定好庫存，維護好正常的生產運轉，同時能夠節(jié)省資源。1.3.3線性規(guī)劃建立數(shù)學模型的具體實施舉措（1）發(fā)現(xiàn)問題，解決問題，列舉所有可行方針政策以及限制因素；（2）整理數(shù)據，確定模型建立方法；（3）求出最優(yōu)解，并根據模型結果進行優(yōu)化那么，在這個過程中最關鍵也是最重要的一步就是建立模型的過程，而建立模型的前提條件是需要找到問題，明確目標，那么這就需要各種理論數(shù)據作為支撐，所以數(shù)據資料的收集尤其重要，所有過程環(huán)環(huán)相扣，相輔相成，缺一不可。1.3.4線性規(guī)劃的數(shù)學模型的一般形式目標函數(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,…amn1.4線性規(guī)劃理論的評價公司任何復雜的生產計劃決定了其注定無法保持單純，復雜的計劃隨之而來的會產生巨大的工作量，也導致這一目標完全無法落實到現(xiàn)實，最后反而功虧一簣，無功而返。從這一論點出發(fā)，我們也發(fā)現(xiàn)線性規(guī)劃理論在實際的運用中起到的無法忽視的作用。注定了這一理論基礎在實踐過程中是非常必要的.在這個效率優(yōu)先的時代,眾多領域中，但凡涉及最優(yōu)解的問題，首先考慮的方法即是線性規(guī)劃。要建立一個切合實際的線型規(guī)劃模型，需要工程技術人員、財務管理人員等的通力配合，否則會失去很多有用的信息。線性規(guī)劃作為運籌學的一個分支發(fā)展至今，從建立模型到求的最優(yōu)解的整個過程,都有一套發(fā)展較為完備的體系和理論.涉及到生產計劃以及類似的問題時，線性規(guī)劃顯然是首選的方法。然而，線性規(guī)劃并不是沒有其因為方法本身或者問題本身超出方法談到的要求所產生的某些局限性。非常明顯的一點是,線性規(guī)劃模型實質上還是一個靜態(tài)的模型.事實上，隨著約束條件的變化，目標函數(shù)中的一些指標常常并非一成不變。舉例來說,在考慮生產計劃，即如何選擇產業(yè)結構使生產成本最低的時候，成本系數(shù)實質上是一個會根據產業(yè)結構和模式之變化而難以絕對保持靜態(tài)的變量，這就勢必導致模型的理想化。另一方面，由于生產過程中外部條件與內部因素的影響，導致一些新的動態(tài)產生，所以生產過程不存在完全的靜止，任何的影響都會賦予它新的變化。即它并非可以完全按照單純形法中矩陣變換的簡單方法去解決.一旦考慮到時間軸上的某些變化，問題的復雜程度就不是線性規(guī)劃模型多能夠做到了的?？偟膩碚f，線性規(guī)劃模型具有單一性，相對其他模型缺少靈活性，所以也導致了其在解決實際問題中缺少堅實的理論基礎做后盾，從而不夠全面開闊。一2研究方法2.1綜述法通過網絡途徑搜索、收集運籌學線性規(guī)劃相關的歷史文獻資料，梳理線性規(guī)劃理論及方法的發(fā)展進程，深入理解線性規(guī)劃問題及其數(shù)學模型的相關內容。2.2實驗法運用實驗的方法解決中產生的問題，從而找到運籌學線性規(guī)劃理論以及數(shù)學模型的建設方法，那么這里需要能夠靈活運用軟件來處理相關數(shù)學模型，將理論建立在數(shù)學模型的實踐中，運用這樣的方法來找到問題的答案，并對目標變量系數(shù)的靈敏度分析和約束方程中常數(shù)項進行靈敏度分析，用分析出來的數(shù)據解答復雜的實際問題。3實例分析【實驗目的及要求】目的：通過實驗掌握實際問題建立線性規(guī)劃模型的方法，熟練運用運籌學軟件3.0，在軟件中處理模型，運用單純形法求解線性規(guī)劃問題，并對目標變量系數(shù)的靈敏度分析和約束方程中常數(shù)項進行靈敏度分析，用分析出來的數(shù)據解答復雜的實際問題。要求：（1）根據實際問題，建立線性規(guī)劃模型，并用軟件求解。（2）對結果進行分析?！緦嶒炘怼烤€性規(guī)劃單純形表上作業(yè)法、靈敏度分析。【實驗環(huán)境】（使用的系統(tǒng)平臺和用到的軟件）使用管理運籌學軟件3.0分析?！緦嶒瀮热荨俊緦嶒炦^程】（實驗的具體步驟、記錄、數(shù)據、分析）（1）實際問題實驗室原計劃生產兩種不同的產品，不同的產品需要消耗的原料不同，下圖為不同產品三種原料資源限制。實驗室生產不同的產品所用原料不同，獲得的利潤也不同。當每單位生產產品1和產品2分別可以獲利50元和100元，那么實驗室需要分別生產多少產品才能使利益最大化？產品I產品II資源限制原料A11300kg原料B21400kg原料C01250kg（2）運籌學模型這個問題可以用數(shù)學線性規(guī)劃模型來描述。把實驗室生產的產品I數(shù)量和產品II數(shù)量用變量x1,x2來表示，稱x1,x2為決策變量。把實驗室所要求的最大利潤的目標用x1,x2的線性函數(shù)形式來表示：maxz=50x1+100x2。其中，z為目標函數(shù)。整理問題中的一些約束條件，得到的規(guī)劃模型：maxz=50x1+100x2，約束條件：x1+x2≤300，2x1+x2≤400，x2≤250，x1≥0，x2≥0。（3）軟件求解1）在軟件中建立線性規(guī)劃模型打開管理運籌學軟件3.0，選擇“線性規(guī)劃-線性規(guī)劃”，把線性規(guī)劃模型導入到軟件內，導入內容包括四個部分：數(shù)據、決策變量、目標函數(shù)、約束條件。如圖所示：2）線性規(guī)劃單純形表上作業(yè)在工具菜單中點擊“解決”，出現(xiàn)規(guī)劃求解窗口，點擊“開始”，進行單純形法分析，點擊“下一步”，進行迭代分析。如圖所示：為了方便運算，引入了松弛變量x3，x4，x5,軟件把模型標準化了，標準形式為maxz=50x1+100x2，+0·x3+0·x4+0·x5，約束條件：x1+x2+x3=300，2x1+x2+x4=400，x2+x5=250，x1≥0，x2≥0，x3≥0，x4≥0，x5≥0。圖中迭代次數(shù)為1時，沒有進行迭代，求得初始基本可行解為x1=0，x2=0，x3=300，x2=400，x5=500，此時，z=0，即天天工廠沒有生產產品也沒有獲利。迭代次數(shù)為1時，進行第一次迭代，獲得的基本可行解為x1=0，x2=250，x3=50，x4=150，x5=0，此時，z=25000，cj-zj＞0，此解不是最優(yōu)解。迭代次數(shù)為2時，進行第二次迭代，獲得的基本可行解為x1=50，x2=250，x30，x4=50，x5=0，此時，z=27500，cj-zj≤0，此解是最優(yōu)解。即天天工廠生產50單位產品I和250單位產品II時獲利最大，最大利潤為27500元。3）優(yōu)化結果及靈敏度分析完成線性規(guī)劃單純形表作，點擊“×”，彈出結果輸出窗口。設目標變量系數(shù)分別為c1，c2,約束方程中常數(shù)項分別為b1，b2，b3。如圖所示：圖中包括目標函數(shù)最優(yōu)分析、對偶問題分析、目標變量系數(shù)的靈敏度分析和約束方程中常數(shù)項的靈敏度分析。目標變量系數(shù)的靈敏度分析，給出了目標系數(shù)的當前值和上下限，當0≤c1≤100，c2≥50時最優(yōu)解不變；約束方程中常數(shù)項的靈敏度分析，給出了約束條件的當前值和上下限，當250≤b1≤325,b2≥350,200≤b1≤300時最優(yōu)解不變。4結果分析與總結從以上分析中，可以發(fā)現(xiàn)工廠生產50單位產品I和250單位產品II時獲利最大，最大利潤為27500元。如果工廠每單位產品I獲利0~100元，每單位產品II獲利50元以上時，獲利最大組合不變；消耗A原料250~325kg，消耗B原料350kg以上，消耗C材料200~300kg時，獲利最大組合不變。此次實驗是對管理運籌學軟件3.0的實踐運用，實驗素材選取于課本，是對課本知識的檢驗。管理運籌學是一門偏難的學科，如何結合實際生活是學習的重點，學習非常有挑戰(zhàn)性。通過這次實驗的模型的建立與求解，對實際問題進行數(shù)理分析等等實踐操作，我更加認識到這門學科十分深奧。運籌學作為數(shù)學學科基礎，但歸根結底還是與數(shù)學這一學科有著很大區(qū)別，因此運籌學也作為