線性規(guī)劃模型的建立及投入—產(chǎn)出模型研究

1、長江師范學院本科畢業(yè)論文·線性規(guī)劃模型的建立及投入產(chǎn)出模型研究1 引言數(shù)學對于當代世界的科技、經(jīng)濟、軍事發(fā)展有著至關重要的作用，可以說是起到了決定性的主要力量，數(shù)學應用的領域的廣泛性就是最好的力證。我們每天每時每刻都在運用數(shù)學，也在接受數(shù)學的惠贈。不論是在每天的經(jīng)濟貿(mào)易的往來中，還是在科學方面的運用，例如智能化科技、航空航天、交通運輸、醫(yī)藥衛(wèi)生、農(nóng)業(yè)生產(chǎn)，甚至軍事科技戰(zhàn)略支持，時時事事都用到了數(shù)學，這些應用展現(xiàn)了數(shù)學的無窮力量和魅力。數(shù)學作為一門學科，也是一門科學，從它產(chǎn)生開始就不斷的發(fā)展和完善，但是數(shù)學的發(fā)展是無窮盡的。經(jīng)過了幾千年的發(fā)展，數(shù)學學科的分支越來越多，應用的方面愈加廣泛

2、。數(shù)學也從理論研究開始向現(xiàn)實應用進行轉(zhuǎn)變。數(shù)學分支的高等代數(shù)學科的成熟，分化出了線性代數(shù)，線性代數(shù)與現(xiàn)代社會科技生活的結合，催生了“線性規(guī)劃”，用以解決人們面臨的各種實際問題。線性規(guī)劃（Linear Programming），是一種輔佐人們進行科學生產(chǎn)和優(yōu)化管理的方法，英文簡寫L P。它的研究很早就開始進行，發(fā)展的過程迅速，并且它的運用廣泛，經(jīng)過長期的發(fā)展，計算方法趨于成熟。被大量的運用于軍事戰(zhàn)備、經(jīng)濟、生產(chǎn)經(jīng)營管理和工程等方面。在各種經(jīng)濟活動中，賺取利潤是人們的首要目標，而提升經(jīng)濟利潤一般是通過兩種方法：一種是在技術方面進行改善，比如改善工藝技術，倡導使用新的原料和設備；第二種是生產(chǎn)組織與計

3、劃的改良，也就是合理地分配資源。線性規(guī)劃的研究目的：在一定的限制條件下，根據(jù)實際的情況合理分配物力、人力等資源，促使經(jīng)濟效益達到最佳。要對線性規(guī)劃問題進行研究，就需要針對實際情況，建立數(shù)學模型，其方法如下：（1）依據(jù)指標因素的制約，找到?jīng)Q策變量，也就是制約條件；（2）確定目標函數(shù)，由決策變量與指標之間的函數(shù)變量關系來確立；（3）找出決策變量因受約束而必須要滿足的條件。諾貝爾經(jīng)濟學獎獲得者列昂惕夫，他創(chuàng)造了經(jīng)濟數(shù)學模型研究的新世紀。提出了許多和經(jīng)濟相關的數(shù)學模型，比如“交易模型”。交易模型：其內(nèi)容是一個國家的經(jīng)濟由多個部門構成，如各種制造、交通、娛樂和服務業(yè)。假設我們知道每個部門年度的總產(chǎn)出，并

4、精確知道該總產(chǎn)出是如何在其他經(jīng)濟部門進行分配或“交易”的。稱一個部門產(chǎn)出的總貨幣價值為該產(chǎn)出的價格。那么將有下面的論斷：有一個能夠指派給每個部門總產(chǎn)出的價格，使得每個部門的總收入恰等于它的總支出，由此能達到各生產(chǎn)部門的平衡。本文首先介紹線性規(guī)劃，了解線性規(guī)劃的起源、發(fā)展，以及線性規(guī)劃在現(xiàn)代社會生活中的應用。其次講授了幾種常見的線性模型，以及線性模型的表達形式，如標準形式、矩陣形式、向量形式、簡寫形式。了解了相當?shù)慕夥?，會解決一般的線性規(guī)劃問題。最后，在了解了相當?shù)木€性解法后，在此基礎上提出交易模型和投入-產(chǎn)出模型，并通過相關例題給出相應的解法，以此來認識投入產(chǎn)出模型。2 線性規(guī)劃2.1線性規(guī)劃

5、問題的由來線性規(guī)劃在20世紀初開始出現(xiàn)，在20世紀中得到發(fā)展，在二戰(zhàn)后期基本完善，冷戰(zhàn)時期獲得進一步發(fā)展并走向成熟。其方法與理論，在二戰(zhàn)時期的軍事作戰(zhàn)上發(fā)揮了重大作用；發(fā)展至今，與當今社會需求結合，線性規(guī)劃在經(jīng)濟決策、科學研究方面也得到了廣泛的運用和發(fā)展。類似于“線性規(guī)劃”的運籌學思想在我國古代也有，產(chǎn)生得很早，并且得到了許多的應用。如“系統(tǒng)考慮，全局統(tǒng)籌”的哲學思想，在各代思想家的觀念之中都有體現(xiàn)，其中不乏以軍事家孫子為代表的杰出人物。大家耳熟能詳?shù)囊灿袆顚埩嫉姆Q贊，“運籌帷幄，決勝千里”。對線性規(guī)劃理論和方法做出重要貢獻的外國科學家主要有：喬治丹澤格（），他在1947年提出了單純形法，

6、是一種用以求解線性規(guī)劃問題的方法。該算法在實際中受到了廣泛的重視，并被列為20世紀的十大算法之一?？低新寰S奇在1939年提出了“乘數(shù)解法”的求解方法，這是一種類似于線性規(guī)劃的數(shù)學模型。1960年，最佳資源利用的經(jīng)濟計算正式發(fā)表，這本書在國際上受到了廣泛的關注，康托洛維奇因此成就獲得了諾貝爾獎。至今，線性規(guī)劃的方法在國際上廣泛應用，其作用領域愈加寬廣。對經(jīng)濟問題的分析，對科學技術的輔助，對軍事戰(zhàn)備的籌劃，線性規(guī)劃已經(jīng)滲透到當今時代的各個領域。2.2線性規(guī)劃問題的應用范圍線性規(guī)劃方法的應用領域非常廣泛，在各種領域，只要存在能夠用多種的方法來解決的現(xiàn)實問題，都可以利用線性規(guī)劃來求取最佳方案。（1）企

7、業(yè)營銷策劃一旦產(chǎn)品對于用戶而言具有使用的價值，就會有市場貿(mào)易，但是有市場并不能保證市場貿(mào)易交流都能盈利。要想在同行業(yè)的競爭中的優(yōu)勝，除了要提高產(chǎn)品的質(zhì)量、降低生產(chǎn)的成本，提供優(yōu)質(zhì)的服務外，還需要有能夠獲利的營銷策劃，這就需要用到線性規(guī)劃。（2）產(chǎn)品生產(chǎn)計劃在通常的企業(yè)中，生產(chǎn)常常需要同營銷計劃相結合，但生產(chǎn)目標卻不能單一的隨著營銷計劃而執(zhí)行。 這是由于產(chǎn)品的發(fā)展具備兩個基本的驅(qū)動力：一個是市場的需求，另一個則是在技術方面的革新。市場需求具有技術的盲目性，技術革新具有市場的盲目性，單靠某一個單一的因素來制定生產(chǎn)計劃，極有可能導致企業(yè)走向失敗。于是在技術驅(qū)動和市場牽引的諸因素之間，需要進行某些優(yōu)化

8、選擇。（3）物流管理在物流成本占總成本比例相對較高的商業(yè)行業(yè)，需要優(yōu)化物流策劃方案，如若不然，獲得的利潤將被物流費用所侵吞。（4）理財與投資產(chǎn)品經(jīng)營只是企業(yè)經(jīng)營的一個方面，另一個方面是資本與資產(chǎn)經(jīng)營。如何理財、如何投資，已經(jīng)成為企業(yè)經(jīng)營者必須面對的問題。在這些問題中，資產(chǎn)的運作和資本的運作卻是高風險，高回報的業(yè)務。如果計劃得好，則能獲得高收入；反之，則會造成巨大的損失。因此，優(yōu)化與運籌在該領域發(fā)揮著巨大的作用。另外，在人事管理、綜合評價、設計優(yōu)化、宏觀經(jīng)濟調(diào)控、城市管理、農(nóng)業(yè)種植等等方面，規(guī)劃和統(tǒng)籌都可以發(fā)揮重要作用。簡言之，只要能使用線性約束條件，都可以用線性方法求取一個最好的方案解決具體問

9、題。但當方程中含有二次或者二次以上方冪的變量，或者變量不跟隨其他因素的變化而改變，以及變量不具有確定性取值規(guī)則的問題，則不屬于線性規(guī)劃的范疇。2.3求解線性規(guī)劃問題的基本原則求解線性規(guī)劃問題大致遵循如下原則：第一步，也是規(guī)劃過程中最為關鍵的一步：提出問題，進行抽象。這一步涉及確定優(yōu)化目標、明確約束條件，找到?jīng)Q策的變量和已知資源的參數(shù)。如果在這個步驟中出現(xiàn)錯誤，那么整個規(guī)劃就會變得毫無意義，也就會導致后面的步驟無法進行。因此，一定要對該問題進行全面的了解和控制，明確已知和未知的因素，精確約束條件，明確規(guī)劃目標。第二步，建立科學合理的數(shù)學模型。根據(jù)第一步的結果，參照規(guī)劃模型的構成原則，把決策變量、

10、約束條件和資源參數(shù)之間的關系，用恰當?shù)臄?shù)學式子表達出來，并確定建立上述各要素之間嚴格的數(shù)學關系。第三步，求解和檢驗結論。即用數(shù)學方法對數(shù)學模型進行求解，并對所求得的解進行驗證；依靠與問題相關的專業(yè)知識對解進行檢驗，當結果與實際情況不符時，就要及時返回檢查，看數(shù)學模型是否錯誤，或者輸入的數(shù)據(jù)是否有誤。第四步，分析解的靈敏度。常規(guī)情況下，線性規(guī)劃的問題隨著某些資源變化會發(fā)生相應的改變。通過運用科學的算法，確定各種參量的變化范圍，知道最優(yōu)解受哪些參數(shù)變化的影響。最后，把各個步驟獲得的準確解帶入到實際問題中去驗證。如果實際問題的各種制約因素發(fā)生了改變，則應當立刻回到第一步，修改抽象條件，重建數(shù)學模型，

11、重新求解，以便及時調(diào)整規(guī)劃內(nèi)容，適應變化了的新情況。3 線性規(guī)劃問題的數(shù)學模型3.1線性規(guī)劃模型的建立解決規(guī)劃問題是根據(jù)實際情況，在各種約束條件下求解，得到資源最合理的利用和調(diào)配的一種方式。它的基本方法是：為使預期的指標達到最優(yōu)，必須要滿足一定的限制條件。其研究內(nèi)容主要為兩個方面：一個是資源的總量已確定，如何合理的利用、分配，使任務實現(xiàn)得最多；二是任務資源數(shù)量已經(jīng)確定，通過策劃，能夠用最少的資源去完成任務。前一個方面是求極大的問題，后一方面是求極小問題。線性規(guī)劃問題的一般性表達，其數(shù)學模型如下： (1) s.t. (2) 稱為決策變量 稱為目標函數(shù)系數(shù) () 稱為約束右端系數(shù) 稱為約束系數(shù)其中

12、式（1）為目標函數(shù)，式（2）為限制條件 。線性規(guī)劃問題的表達形式多種多樣，現(xiàn)給出如下標準形式：（1）標準形式 (2) 記號簡寫式 （3）矩陣形式 式中, （4）向量形式 式中C,X,b,0的含義與矩陣的表達式相同，而 即。 將非標準形式化為標準形式的情況（3種基本情況）（1）目標函數(shù)為求極小值Min Z=CX, 則作Z=-CX, 即Max Z=-CX(2) 右端項小于0則將兩端同乘（-1），不等號方向改變，然后再將不等式改為等式（3） 約束條件為不等式倘使限制條件為“”，則可在不等式左側加上非負松馳變量，使其轉(zhuǎn)化為“”；若限制條件為“”，則在不等式的左側減去一個松弛變量，使其轉(zhuǎn)化為“”。3.2

13、線性規(guī)劃模型的求解方法3.2.1圖解法由于圖解法的局限性，使得使用圖解法的時候僅適合于含有兩個決策變量的具體問題。在平面內(nèi)建立直角坐標系，使每個決策變量的取值在一個數(shù)軸上表示出來，可行解就成為平面上的點，可行域就是平面上滿足不等式組的公共區(qū)域，從而最優(yōu)解必定是落在這個平面區(qū)域內(nèi)或者邊界上的點。根據(jù)目標函數(shù)在這個平面區(qū)域內(nèi)的取值找出使目標函數(shù)取得最優(yōu)值的點。當線性規(guī)劃問題的規(guī)模較大時，圖解法就不再適用。在面臨只具有兩三個變量的規(guī)劃問題時，可以使用圖解法。圖解法的特點是操作簡單、圖形清晰易懂。舉例只有兩個變量的情況。在平面上作圖，可以對只含有兩個變量的問題進行求解，方法如下： （1）在直角坐標系上

14、作圖，以X1為橫坐標，X2為縱坐標，在坐標軸上選取適當?shù)膯挝婚L度。由于變量非負，可知所有解均落在在第一象限。 （2）根據(jù)約束條件在坐標系上作圖，可以得到滿足限制條件的可行域。 （3）通過畫圖可以確定函數(shù)變化的方向，即增大或者變小。 （4）函數(shù)圖象存在一個交點，這個交點就是使目標函數(shù)達到最優(yōu)解的最優(yōu)點。下面來講解一個實例：例1某個木材廠廠生產(chǎn)木床和衣柜這兩種家具，要用到實木和板木這兩種木料，實木有72，板木有56，每制作一張木床和衣柜所需木料下表已給出。假設生產(chǎn)一張木床可賺取60元，一個衣柜可盈利100元。那么在現(xiàn)有情況下，要制作多少木床和衣柜，能盈利最大？ 表31 產(chǎn) 品木材(單位)實木板木

15、木 床0.180.08 衣 柜0.090.28解：假定要制作木床x張，衣柜y個，獲利為z元，可知模型為： , 圖31這個問題只含有兩個變量，能夠用圖解法進行求解，先在坐標系上作出可區(qū)域，如上坐標系的陰影部分所示。再作直線，即。通過把直線平移到的位置，直線經(jīng)過點M，距離原點達到最大值，此時取最大值，為了得到M點坐標解方程組，得：于是可知M點坐標為，則制作木床張，衣柜個，能夠使得盈利達到最大31000元。3.2.2單純形法數(shù)學家喬治丹澤格（），在1947年首先提了單純形法。單純形法的基本方法是：先找出一個基本可行解，對它進行驗證，看是不是最優(yōu)解；如若不是，則按照一定的法則轉(zhuǎn)變到另一個改進的基本可行

16、解，再驗證；假使仍然不是，則再轉(zhuǎn)換，按此方法重復進行。由于基本可行解的個數(shù)有限，因此經(jīng)過有限次轉(zhuǎn)變后必能得到問題的最優(yōu)解。在問題沒有最優(yōu)解的時候，也可以用這種方法來進行驗證。例：求下列線性規(guī)劃問題的最優(yōu)解 解：化為標準形式 （1）首先：確定一個基本的可行解。 （2）這里m=3，3階可逆方陣，可以看出，的系數(shù)列向量是線性獨立的，這些向量構成一個基，對應的基變量為，。，為非基變量。用非基變量把基變量表示出來，由(2)得： （3）將(3)代入目標函數(shù)得令非基變量，代入(3)，得到一個基可行解X(0)，X(0)=(0,0,160,15,4)。其次：把當前基可行解進行優(yōu)化；因為仍為非基變量，故，則(3)

17、式變?yōu)?， 由可知， min=3，所以當時，第一個減少到0，所以出基,則X(1)=(3,0,70,0,1)Z(1)=15此時非基變量為,用非基變量表示基變量，代入(3) （4）將(4)代入目標函數(shù)得最后：繼續(xù)迭代進基，仍為非基變量，令，則(4)式表示為 由可知，min=5，所以當時，首先減少到0，所以出基則X(2)=(2,5, 0,0,2)Z(2)=20此時非基變量為,用非基變量表示基變量，代入(4) （5）將(5)代入目標函數(shù)得此時若非基變量,的值增加，只能使Z值下降所以X(2)為最優(yōu)解，。4 投入產(chǎn)出模型4.1交易模型假定一個國家的經(jīng)濟由各種部門共同構成，如各種制造業(yè)、交通、娛樂業(yè)和服務業(yè)

18、。假設我們知道每個部門年度的總產(chǎn)出，并精確知道該總產(chǎn)出是如何在其他經(jīng)濟部門進行分配或“交易”的。稱一個部門產(chǎn)出的總貨幣價值為該產(chǎn)出的價格。那么將有下面的結論：有一個能夠指向給各個生產(chǎn)部門總產(chǎn)出的價格，恰好每個部門的總收入等于它的總支出，這個價格叫做平衡價格。這就是列昂惕夫提出的“交易模型”。下面的例子說明如何求平衡價格。例1 若煤炭、電力和鋼鐵三個部門能夠構成一個國家的經(jīng)濟，各分配如表，圖表的每一豎列的數(shù)表示該部門總產(chǎn)出的比重。在第二列，將電力的產(chǎn)出分配：40%給煤炭部門，50%給鋼鐵部門，剩下的10%自己留作運轉(zhuǎn)費用。所有的產(chǎn)出都要進行分配，則每一列的之和等于1。表41 部門的產(chǎn)出分配采購部

19、門 煤炭 電力 鋼鐵 0.0 0.4 0.6 煤炭 0.6 0.1 0.2 電力 0.4 0.5 0.2 鋼鐵 煤炭、電力和鋼鐵部門年度總產(chǎn)出的價格用，表示。如果可以，就能夠求平衡價格，使得每個部門的收支達到平衡。解：一個部門下的一列是它的產(chǎn)出的分配去處，每行表示它獲得了哪幾個部門的投入。因為相應部門的總產(chǎn)出價格為和，所以煤炭部門必須支付電力部門美元，支付鋼鐵部門美元，因此煤炭部門一共要支出美元。要使總收入等于總支出，則有 （1）在表的第二行：電力部門用美元購買煤炭，美元購買電力，美元購買鋼鐵。電力部門的收支如果要達到平衡，則 （2）從第三行可得出最后條件： （3）要求解方程（1）、（2）、（

20、3），將所有未知量移到方程的左邊并合并同類項。 接下來進行行化簡。 通解是，為自由變量。這個經(jīng)濟問題的平衡價格向量為可見，對于任意非負的的取值，都可以求得一種平衡價格。4.2投入產(chǎn)出模型假使一個國家的經(jīng)濟由m個部門構成，m個部門分別提供服務和生產(chǎn)商品。令x為產(chǎn)出向量，它列出了每個部門一年中的產(chǎn)出。存在一些開放部門不生產(chǎn)產(chǎn)品或服務，只進行消費，d向量代表最終需求，該向量列出了經(jīng)濟體系中的各種非生產(chǎn)部門所需求的服務和商品。d代表消費者需求、超額生產(chǎn)、出口或者其他外部需要。由于消費的需要，各種生產(chǎn)部門進行商品的制造，在這個過程中，生產(chǎn)商品的部門也存在需求，需要這些產(chǎn)品的一部分作為生產(chǎn)的投入。各個部門

21、之間都存在利益關系，生產(chǎn)和最終需求之間的聯(lián)系也還不清楚。假想是否存在某一生產(chǎn)水平x恰好滿足這一生產(chǎn)水平的總需求，則 總產(chǎn)出x=中間需求+最終需求d （1）該模型的假設：每個部門都有一個單位消費向量，該向量表出了這個部門的單位產(chǎn)出應當需要的投入。投入和產(chǎn)出都不用具體的單位來衡量，只以百萬美元作單位表述。要求商品和服務的價格為常數(shù)，這就是投入產(chǎn)出模型?，F(xiàn)在舉一個列子，假設經(jīng)濟體系由農(nóng)業(yè)、服務業(yè)和制造業(yè)三個部門構成，單位消費向量，如下所示：表42購買自制造業(yè)農(nóng)業(yè)服務業(yè)制造業(yè)0.500.400.20農(nóng)業(yè)0.200.300.10服務業(yè)0.100.100.30例1 如果制造業(yè)決定生產(chǎn)100單位的產(chǎn)品，它將

22、消費多少？解：計算 100=100=為生產(chǎn)100單位產(chǎn)品，制造業(yè)需要消費制造業(yè)其他部門的50單位產(chǎn)品，20單位農(nóng)業(yè)產(chǎn)品，10單位服務業(yè)產(chǎn)品。 若制造業(yè)決定生產(chǎn)單位產(chǎn)品，則需消費掉的中間需求是，相應的，若和表示農(nóng)業(yè)和服務業(yè)的計劃產(chǎn)出，則和為它們的對應中間需求。三個部門的中間需求為 中間需求=+= （2） 這里C是消耗矩陣，即 （3）方程（1）、（2）產(chǎn)生列昂惕夫模型。列昂惕夫投入產(chǎn)出模型或生產(chǎn)方程 x = + d （4） 總產(chǎn)出 中間需求 最終需求 把x寫成（是單位矩陣），應用矩陣代數(shù)，可把（4）重寫成 （5）例2 運用矩陣（3），令最終需求是農(nóng)業(yè)30單位，制造業(yè)50單位，服務業(yè)20單位，那么生

23、產(chǎn)水平x是多少。解：（5）中系數(shù)矩陣為為解方程（5），對增廣矩陣做行變換矩陣的最后一列四舍五入到整數(shù)，服務業(yè)需生產(chǎn)78單位，農(nóng)業(yè)需生產(chǎn)119單位，制造業(yè)需要生產(chǎn)約226單位。在例1和例2中，交易模型和投入產(chǎn)出模型都是用的矩陣形式來表達的，并且運用的是線性方程組和矩陣代數(shù)的方法進行求解的。對線性方程組的系數(shù)和常量構成的增廣矩陣進行行化簡得到最后的解，用自由變量把基本變量表示出來，就得到了通解。所以，對于任意一組自由變量的取值，都能得到一組可行解，再根據(jù)實際的情況，確定出一組最合適的取值，就能得到最佳的方案策劃。對于投入產(chǎn)出模型，運用矩陣乘向量，得到一個新的矩陣，并進行求解，就能得到各種供求關系，

24、確定各個生產(chǎn)部門的投入和產(chǎn)出，根據(jù)生產(chǎn)目標選擇合適的策劃方案。5 總結本篇論文是在大學本科課程學習結束后，并運用在大學期間所有習得的知識與技能，傾注自己的辛勤與努力，積極開拓思維而寫出的畢業(yè)論文設計。本科學習課程主要是高等代數(shù)，而本文所講的線性規(guī)劃又是運籌學的內(nèi)容，本科課程不涉及，但是在課余學習的線性代數(shù)及其應用，講授的線性代數(shù)又是解決線性規(guī)劃的一個主要工具。因此，本文據(jù)此而展開：首先，通過介紹線性規(guī)劃，了解了線性規(guī)劃的起源，知道了線性規(guī)劃的應用范圍非常廣泛，并且總結了線性規(guī)劃的基本求解原則；其次，講述了線性規(guī)劃模型。線性規(guī)劃模型見之于社會生活的方方方面面，粗略介紹了線性規(guī)劃模型的建立方法，習得了線性規(guī)劃模型的解法。主要是圖解法和單純形法。最后，在習得了相當?shù)木€性規(guī)劃知識后，提出了交易模型和投入產(chǎn)出模型，并給出例題進行了講解。交易模型和投入產(chǎn)出模型對于解決現(xiàn)實生活中的問題具有巨大的作用，幫助人們解決各種生產(chǎn)和經(jīng)濟問題。筆者通過本文介紹了各種線性規(guī)劃模型，主要是交易模型和投入產(chǎn)出模型，希望讀者通過閱讀本文能夠了解一些線性規(guī)劃的知識，并能運用線性規(guī)劃的方法解決現(xiàn)實問題。至此，