線性規(guī)劃在數(shù)學(xué)建模中的應(yīng)用.docx

1、.線性規(guī)劃在數(shù)學(xué)建模中的應(yīng)用摘要：線性規(guī)劃是運(yùn)籌學(xué)中發(fā)展較快、應(yīng)用廣泛、 方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法，英文縮寫LP。它是運(yùn)籌學(xué)的一個(gè)重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營管理和工程技術(shù)等方面。 為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。本文在閱讀了大量材料的基礎(chǔ)上， 集中體現(xiàn)了線性規(guī)劃是如何應(yīng)用到數(shù)學(xué)建模中去的。并且在利用數(shù)學(xué)建模的思想以線性規(guī)劃為工具可以解決哪些實(shí)際問題，為我們的生活提供哪些便利。 本文大體上可分為三章， 第一章主要對(duì)線性規(guī)劃和數(shù)學(xué)建模這兩個(gè)理論

2、做簡(jiǎn)要描述。并且敘述這兩個(gè)理論的發(fā)展歷程，以及研究的背景及意義。第二章主要介紹線性規(guī)劃在數(shù)學(xué)建模中的應(yīng)用，其中包括現(xiàn)在性規(guī)劃在物流運(yùn)輸中的應(yīng)用， 線性規(guī)劃在經(jīng)濟(jì)生活中的應(yīng)用，以及線性規(guī)劃在現(xiàn)代管理中的應(yīng)用，并且配備了相應(yīng)的例子。 第三章主要討論線性規(guī)劃在實(shí)際應(yīng)用方面應(yīng)注意哪些細(xì)節(jié)，并對(duì)第二章的數(shù)學(xué)模型進(jìn)行優(yōu)化，以及對(duì)最優(yōu)解方面的討論。關(guān)鍵詞：線性規(guī)劃數(shù)學(xué)模型物流運(yùn)輸經(jīng)濟(jì)生活現(xiàn)代管理Abstract:Linear programmingis developedrapidlyand widely applied in operationalresearch, the method is an im

3、portant branch of mature, it is one of the scientificmanagement of auxiliary people mathematical method. Study of linear objectivefunctionunderthelinearconstraintconditionextremumproblemsofmathematics theory and method of LP abbreviations. It is an important branch of.operational research, widely us

4、ed in military, economic analysis, managementand engineering technology, etc. For reasonable use of the limited manpowerand material resources, financial resources and other resources to make theoptimal decision, provide the scientific basis.In this paper, on the basis of reading a lot of material,

5、how concentrated thelinear programming is applied to the mathematical modeling. And in using theideas of mathematicalmodelingby means of linear programmingcan solvepractical problems, which provide which is convenient for our life. The article ingeneral can be divided into three chapters, the first

6、chapter mainly on linearprogramming and mathematical modeling the two theories are described briefly.And the development of the two theories, as well as the researchbackgroundand significance. The second chapter mainly introduces the application of linearprogramminginmathematicalmodeling,includingth

7、eplanningintheapplication of logistics transportation, now the application of linear programmingin economic life, as well as the application of linear programming in the modernmanagement,and equippedwith correspondingexamples. The third chaptermainly discuss details which should be paid attention to

8、 in practical application oflinear programming,andoptimizethe mathematicalmodelofthesecondchapter, and the optimal solution for the discussion.Keywords:LinearprogrammingMathematicalmodelLogisticstransportation The economic lifeModern management.第一章 緒論1.1 研究背景以及意義1.1.1 研究背景1.1.2 研究意義研究線性規(guī)劃在數(shù)學(xué)建模中的應(yīng)用其理

9、論意義主要在于利用數(shù)學(xué)建模的手段，為線性規(guī)劃更好的應(yīng)用于顯示生活中提供理論依據(jù)。而為了更好的完成這項(xiàng)工作，需要查閱大量的相關(guān)資料，理論意義也在于總結(jié)整理前人的研究成果，并在某種程度上加以創(chuàng)新， 如線性規(guī)劃在數(shù)學(xué)建模中的約束條件，什么情況下利用線性規(guī)劃進(jìn)行數(shù)學(xué)建模更為合理等。研究線性規(guī)劃在數(shù)學(xué)建模中的現(xiàn)實(shí)意義有很多，因?yàn)橐粋€(gè)數(shù)學(xué)理論要想應(yīng)用到現(xiàn)實(shí)中去就必須要建立數(shù)學(xué)模型去解決。而線性規(guī)劃作為運(yùn)籌學(xué)中的一個(gè)重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營管理和工程技術(shù)等方面。為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。因此，研究線性規(guī)劃在數(shù)學(xué)建模中的應(yīng)用就可以將數(shù)學(xué)理論更好

10、的，更有效的，更完美的運(yùn)用到現(xiàn)實(shí)生活中去，為我們的生活提供便利。.第二章線性規(guī)劃理論簡(jiǎn)述2.1 理論的淵源及演進(jìn)過程（ 1）線性規(guī)劃理論發(fā)展的萌芽期法國數(shù)學(xué)家 J.- B.- J.傅里葉和 C.瓦萊普森分別于1832 和 1911 年獨(dú)立地提可解的問題會(huì)有一個(gè)簡(jiǎn)單多邊形的可行域出線性規(guī)劃的想法，但未引起注意。 二十幾年后，1939 年蘇聯(lián)數(shù)學(xué)家 .康托羅維奇在 生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書中提出線性規(guī)劃問題， 也未引起重視。 此后的十幾年中， 線性規(guī)劃只是作為一個(gè)還不成形的思想并未引起世界的重視。（ 2）線性規(guī)劃理論發(fā)展的成長(zhǎng)期1947 年美國數(shù)學(xué)家G.B.Dantzing 提出求解線性規(guī)劃

11、的單純形法，為這門學(xué)科奠定了基礎(chǔ)。同年， 1947 年美國數(shù)學(xué)家J.von 諾伊曼提出對(duì)偶理論 ,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。1951 年美國經(jīng)濟(jì)學(xué)家 T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975 年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。（ 3）線性規(guī)劃理論發(fā)展的成熟期50 年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954 年 C.萊姆基提出對(duì)偶單純形法， 1954 年 S.加斯和 T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題， 1956 年 A.塔克提出互補(bǔ)松弛定理， 1960年 G.B.丹齊克和 P.沃爾夫提出分解

12、算法等。 線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、 隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。 由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX， OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問題。1979 年蘇聯(lián)數(shù)學(xué)家 L.G.Khachian.提出解線性規(guī)劃問題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法。1984 年美國貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問題在變量個(gè)數(shù)為5000 時(shí)只要單純形法所用時(shí)間的 1/50 ?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。由于單純形法是求解線性規(guī)劃模型的常用方法，

13、 并且其在求解線性規(guī)劃模型上使用相當(dāng)廣泛，因此國內(nèi)外對(duì)于單純形法的研究成果可體現(xiàn)國內(nèi)外對(duì)線性規(guī)劃在數(shù)學(xué)建模中的研究進(jìn)程。2.2 國外有關(guān)研究的綜述1983 年，S.Smale再次給出了 Borgwardt 在 1982 年證明的單純形法平均多項(xiàng)式時(shí)間復(fù)雜類似的結(jié)果，這些結(jié)果都表明此算法雖然在最壞情況下是“差”算法，但是，它的平均復(fù)雜性是“好”的。1992 年， J.J.Forrest和 D.Goldfarb 給出了 steepest.edge 規(guī)則的若干變形和與之相應(yīng)的遞推公式，數(shù)值實(shí)驗(yàn)結(jié)果表明單純形法與當(dāng)時(shí)正處于發(fā)展勢(shì)頭強(qiáng)勁之際的內(nèi)點(diǎn)法確實(shí)存在不分高低和難分伯仲的競(jìng)爭(zhēng)狀態(tài)。2002 年， R

14、.E.Bixby在“Solving real-world linear programs:a decade and more ofprogress”文章中總結(jié)了對(duì)偶單純形法從 20 世界 90 年代以后的新進(jìn)展，并指出它已經(jīng)成為最有效的求解線性規(guī)劃問題的方法之一【1】。2.3 國內(nèi)研究的綜述國內(nèi)有關(guān)學(xué)者們對(duì)于單純形法的各方面研究成果也不計(jì)其數(shù)，依照目前已經(jīng)公開發(fā)表的資料來看：【2 】郭秀英在“線性規(guī)劃單純形法迭代法則的改進(jìn)”文章中提出一種當(dāng)進(jìn)、 出變量唯一不變時(shí)的可減少迭代次數(shù)的判斷進(jìn)、出變量的新法則，并驗(yàn)證了其有效性。.【 3】陳曉杰在“生產(chǎn)問題中單純形解法的改進(jìn)”文章中針對(duì)線性規(guī)劃在生產(chǎn)問

15、題中的具體應(yīng)用模型，結(jié)合線性規(guī)劃的三個(gè)參數(shù)之間的某些關(guān)系以及他們對(duì)非基變量檢驗(yàn)數(shù)的影響，提出一種通過某些特定變量的進(jìn)出基運(yùn)算可以達(dá)到簡(jiǎn)化單純形求解運(yùn)算的可行方法。【 4】呂林霞等人在“線性規(guī)劃模型的單純形法初始可行基選擇研究”文章中提出可以利用矩陣初等行變換來直接判斷和尋找問題初始可行基的一種可行方法。張勁松等再“含自由變量 LP 問題的改進(jìn)單純形法”【 5】文章中針對(duì)含自由變量的LP問題，通過研究自由變量在其迭代過程中的運(yùn)算規(guī)律，提出一種改進(jìn)算法并且驗(yàn)證了其可以提高運(yùn)算速度和節(jié)省存貯空間的有效性?！?6】董兵等再“一種改進(jìn)的單純形最優(yōu)化法”文章中給出了一種求解法獲得的的基解仍然非原問題可行，

16、也非對(duì)偶可行的一類規(guī)劃問題初始可行的一般方法。謝震等在“單純形法的計(jì)算機(jī)程序化算法改進(jìn)” 【 7】文章中，通過其對(duì)計(jì)算機(jī)程序所作的改進(jìn)工作，使得單純形法在空間上和時(shí)間上的復(fù)雜度效率均降到。2.4 本人對(duì)以上綜述的評(píng)價(jià)從資料上來看雖然線性規(guī)劃模型理論起源于國外，但是其在國內(nèi)得到了較好的發(fā)展。其中國內(nèi)學(xué)者在簡(jiǎn)化單純形法的求解過程方面貢獻(xiàn)卓著，而外國學(xué)者在討論哪種方法是求解線性規(guī)劃模型的最優(yōu)方法上做了深入的研究。.第二章 線性規(guī)劃在數(shù)學(xué)建模中的應(yīng)用.2.1 線形規(guī)劃在物流運(yùn)輸模型中的應(yīng)用現(xiàn)在物流業(yè)面臨的新問題是：(1)認(rèn)定所給問題確實(shí)是一個(gè)線性規(guī)劃問題；(2)把它建立起線性數(shù)學(xué)模型；(3)并能夠完成

17、具體實(shí)務(wù)的全部工作。第一個(gè)問題實(shí)質(zhì)上是具體實(shí)務(wù)究竟?jié)M足什么條件才能應(yīng)用線性規(guī)劃的方法。一般地說，必須有：一定要滿足將目標(biāo)表為最小化或最大化的要求； 一定要有達(dá)到目標(biāo)的不同方法，且必須要有選擇的可能性；要求的目標(biāo)是有限制條件的； 必須將約束條件用數(shù)學(xué)表示為線性等式或線性不等式，并將目標(biāo)函數(shù)化為線性函數(shù)。實(shí)例 2.1：車輛調(diào)度問題物流部門承接的運(yùn)輸千萬種，并往往是幾十種物資同時(shí)調(diào)運(yùn)。為此，只有一種物資的數(shù)學(xué)模型求最優(yōu)調(diào)運(yùn)方案方法，在多種物質(zhì)運(yùn)輸情況下就不能直接使用。原因是：在調(diào)度汽車去完成運(yùn)輸任務(wù)時(shí)，免不了要出現(xiàn)空駛現(xiàn)象。例如某車隊(duì)有一天要完成如表2 所示的運(yùn)輸任務(wù)，各地問的距離如表3，問應(yīng)怎樣安

18、排汽車去完成這些任務(wù)才能做到最省?分析：滿車路線和方向顯然是固定的，但空車的路程、方向卻沒有固定。如把木材從火車站運(yùn)到建筑工地卸下后，空車即可去火車站裝煤， 也可去文具公司裝紙張?？哲嚨淖叻ú煌?，空駛的數(shù)當(dāng)然也不同，這就產(chǎn)生了車輛調(diào)度問題。車輛調(diào)度問題主要解決的是： 怎樣安排車輛去完成所有的運(yùn)輸任務(wù)并使空駛的數(shù)最小。物資調(diào)運(yùn)問題是“怎樣才能使物資運(yùn)輸?shù)臄?shù)最小”；這就是說把空車看成是一.批貨物 (卸幾噸貨物就看成是幾噸空車)，則把車輛調(diào)度問題轉(zhuǎn)化為物資調(diào)運(yùn)問題。把空車看成是貨物，其發(fā)、收(產(chǎn)、銷 )點(diǎn)及發(fā)、收 (產(chǎn)、銷 )量按如下的方法決定：(1)若某點(diǎn)的卸貨總量大于裝貨總量，則該點(diǎn)是空車的發(fā)點(diǎn)

19、，其發(fā)量等于卸貨總量與裝貨總量之差。如學(xué)校卸貨總量為4，裝貨為 0，故學(xué)校是發(fā)點(diǎn)，發(fā)量為 4。(2)若某點(diǎn)裝貨總量大于卸貨總量，則該點(diǎn)是空車的收點(diǎn)，其收量也是二者之差。（ 3)如果某點(diǎn)的卸貨總量等于裝貨總量，如此點(diǎn)不存在空車則不予考慮。為此，車輛調(diào)度問題可作為物資調(diào)運(yùn)問題來處理。 即空車的流向應(yīng)怎樣才能使車輛調(diào)度合理 ?其主要步驟如下： 確定空車的收發(fā)點(diǎn)和收發(fā)量，并列表； 確定空車調(diào)運(yùn)的數(shù)學(xué)模型，并求解；根據(jù)所得解并結(jié)合具體情況合理調(diào)派車輛。解：收點(diǎn)：火車站、文具公司、糧店；發(fā)點(diǎn)：建筑工地、鋼廠、學(xué)校。表1 運(yùn)輸任務(wù)起點(diǎn)終點(diǎn).建筑工地鋼廠學(xué)?；疖囌?58文具公司374糧店71013表 2運(yùn)輸任

20、務(wù)貨物裝貨點(diǎn)卸貨點(diǎn)車數(shù)木材火車站建筑工地4煤火車站鋼廠2紙張文具公司學(xué)校2面粉糧店學(xué)校2表 3 空車收發(fā)運(yùn)距空車收點(diǎn)運(yùn)距（單位）空車數(shù)量火車站文具公司糧店建筑工地9374鋼廠52102空車發(fā)送學(xué)校84134空車數(shù)量622約束條件為：.x11x12x134x21x22x232x31x32x334x11x21x316x12x22x322xij0(i 1,2,3; j1,2,3,4)min S 9x11 3x127x135x212 x2210 x23 8x31 4x32 13 x33用單純形法的程序在計(jì)算機(jī)上可得：鋼廠、學(xué)校分別向火車站發(fā)2t 空車，建筑工地向文具公司和糧店發(fā)2t空車?？哲噰嵐飻?shù)最

21、小是：min S32722284562.2 利用線性規(guī)劃模型在經(jīng)濟(jì)生活中的應(yīng)用星星規(guī)劃問題是經(jīng)濟(jì)數(shù)學(xué)的一個(gè)重要分支，在實(shí)踐中有著廣泛的應(yīng)用， 不僅許多實(shí)際課題屬于線性規(guī)劃問題， 而且運(yùn)籌學(xué)忠的一些分支中的問題也可以轉(zhuǎn)化為線性規(guī)劃問題來計(jì)算，因此線性規(guī)劃問題在最有化學(xué)科中占有重要地位。表 4 各種產(chǎn)品的資源消耗量勞動(dòng)力原 材 料勞動(dòng)成本產(chǎn)值產(chǎn)品設(shè)備臺(tái)時(shí)/ 工時(shí)（kg）（元 /kg ）（元 /kg ）A152030260472B201049180512C302545385544資源限額80001200015000120000.實(shí)例 2：?jiǎn)挝簧a(chǎn)成本最大增值問題某工廠在計(jì)劃期內(nèi)要生產(chǎn)三種A，B，C

22、產(chǎn)品，假定產(chǎn)品暢銷，已知生產(chǎn)的固定成本為 10000 元，即生產(chǎn)期內(nèi)固定資產(chǎn)損耗量。并且生產(chǎn)單位所需要的勞動(dòng)力、設(shè)備臺(tái)時(shí)、原材料、變動(dòng)成本以及差值如表4 所示。廠方規(guī)定總生產(chǎn)成本不要超過 130000 元，問應(yīng)該如何安排生產(chǎn)才能使得產(chǎn)出率最大？建立數(shù)學(xué)模型：設(shè)工廠在計(jì)劃期內(nèi)生產(chǎn)A，B，C 三種產(chǎn)品的數(shù)量分別為x 1 ， x2 ， x3 顯然成本產(chǎn)出率的表達(dá)式是：477x1 512x2544x3（1）260x1280x2385x310000且 A，B，C 三種產(chǎn)品的數(shù)量受 4 種資源量的限制：勞動(dòng)力量的限制：15x120x230x38000 （ 2）設(shè)備臺(tái)時(shí)的限制：20 x110x225 x31

23、2000 （3）原材料的限制：30 x140x245x315000 （4）變動(dòng)成本的限制：260x1280x2385x3120000 （5）此外 A，B，C 三種產(chǎn)品的產(chǎn)量不能為負(fù)數(shù)，即x1, x2 , x30 。綜上所述，本文的問題就是在條件（2）至（5）以及未知數(shù)非負(fù)的條件下求得未知數(shù)使得（ 1）最大，（ 1）成為目標(biāo)函數(shù)。（ 2）至（ 5）稱為約束條件，和工業(yè)資源配置一樣的還有農(nóng)業(yè)生產(chǎn)計(jì)劃安排問題。.2.3 線性規(guī)劃在現(xiàn)代管理中的應(yīng)用表 5 人工工時(shí)及單位產(chǎn)品利潤利潤/ 百車間產(chǎn)品設(shè)備人工元A323.5甲B636C637乙D426實(shí)例 3：某企業(yè)有某企業(yè)有兩個(gè)車間，各生產(chǎn)兩種產(chǎn)品，生產(chǎn)這

24、些產(chǎn)品所需的設(shè)備臺(tái)時(shí)，人工工時(shí)及單位產(chǎn)品利潤如下表所示。現(xiàn)在企業(yè)具有設(shè)備102 臺(tái)時(shí)，人工工時(shí)46，計(jì)劃部門將設(shè)備及人工進(jìn)行如下分配，劃部門將設(shè)備及人工進(jìn)行如下分配:分給甲車間設(shè)備臺(tái)時(shí)48，人工工時(shí)26;分給乙車間設(shè)備臺(tái)時(shí)54，人工工時(shí) 20。問計(jì)劃部門如此進(jìn)行分配是否合理?解設(shè) x1 ， x2 分別為 A,B 兩種產(chǎn)品的計(jì)劃產(chǎn)量，x3 ， x4 分別為 C,D 產(chǎn)品的計(jì)劃產(chǎn)量。分別建立兩個(gè)車間的生產(chǎn)組織的數(shù)學(xué)模型并求解。甲車間的生產(chǎn)組織模型為max S13.5x16x2.3 x16 x 248s.t 2 x13 x 226x10, x 20先將模型標(biāo)準(zhǔn)化，再用單純性法求得最優(yōu)單純型矩陣：00

25、1-1- 50-2T(B1*) 012-16310-124由此得甲車間的最優(yōu)生產(chǎn)方案為：生產(chǎn)A 產(chǎn)品 4 單位，生產(chǎn) B 產(chǎn)品 6 單位，最大利潤為 max S150設(shè)備臺(tái)時(shí)和人工工時(shí)的影子價(jià)格分別為y1 , y*1122乙車間的生產(chǎn)組織模型為max S27x36x46x34x454s.t 2x32x420x30, x40先將模型標(biāo)準(zhǔn)化，再用單純形法求得最優(yōu)單純形矩陣01- 2- 670 -2*) 101-17T(B220113322于是原問題的最優(yōu)解為： x184 ， x224 ，最優(yōu)值 Smax 244.8由 T(B*) 還可求得三種原料 B1、B2、B3的影子價(jià)格分別為：.y10, y2

26、0.12, y30.72由 y10 可知，現(xiàn)有原料B1 有剩余，增加此種原料不僅不能增加總利潤，相反還會(huì)占用工廠的資金。故工廠決策者可以按不低于市場(chǎng)價(jià)格將剩余原料B1轉(zhuǎn)讓出去，增加收入。由 y20.12 可知，原料 B2 增加一噸，最大利潤將增加0.12萬元。因此，當(dāng)該工廠的產(chǎn)品不是國家計(jì)劃產(chǎn)品，而市場(chǎng)上原料B2 的實(shí)際價(jià)格又低于 0.12 萬元 / 噸時(shí)，工廠就可以把一部分資金買進(jìn)原料B2 來擴(kuò)大生產(chǎn)， 使利潤增加。反之，當(dāng)市場(chǎng)上 B2 實(shí)際價(jià)格大于影子價(jià)格時(shí)， 工廠就應(yīng)賣出部分原料B2 ，縮小生產(chǎn)規(guī)模。 此時(shí)生產(chǎn)利潤雖然會(huì)減少些，但加上賣出原料的收入， 總經(jīng)濟(jì)收入還是會(huì)比原來多一些。對(duì)于原料B3 也可作類似分析。第三章結(jié)論綜上