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

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