1、畢業論文（設計）課題名稱 線性規劃模型的求解及應用 學 院 理 學 院 專 業 數學與應用數學 （S） 班 級 2010 級 數學2班 指導教師 學生姓名 佳木斯大學教務處線性規劃模型的求解及應用吳烈東佳木斯大學理學院數學系2014年6月摘 要線性規劃是運籌學的一個重要分支，它輔助人們進行科學管理，是國際應用數學、經濟、計算機科學界所關注的重要研究領域.線性規劃主要研究有限資源最佳分配問題，即如何對有限的資源進行最佳地調配和最有利地使用，以便最充分發揮資源的效能來獲取最佳的經濟效益.線性規劃運用數學語言描述某些經濟活動的過程，形成數學模型，以一定的算法對模型進行計算，為制定最優計劃方案提供依據

2、.其解決問題的關鍵是建立符合實際情況的數學模型，即線性規劃模型.在各種經濟活動中，常采用線性規劃模型進行科學、定量分析，安排生產組織與計劃，實現人力物力資源的最優配置，獲得最佳的經濟效益.目前，線性規劃模型被廣泛應用與經濟管理、交通運輸、工農業生產等領域.本文主要介紹線性規劃的兩種基本解法即圖解法和單純形法，并討論了這兩種方法的優缺點和在一些實際問題中的應用.關鍵詞: 線性規劃；圖解法；單純形法；數學模型；應用AbstractLinear programming is an important branch of operations research, which assist people

3、 to scientific management is an important area of research internationally applied mathematics, economics, computer science communitys concerns. The main study of linear programming optimal allocation of limited resources, namely how to limited resources optimally deploy and most advantageously used

4、 in order to most fully effective resources to get the best value for money.Linear programming using mathematical language to describe the process of certain economic activities, the formation of mathematical models to a certain algorithm to calculate the model to provide a basis for the formulation

5、 of the optimal plan for. The key to solve the problem is to create a mathematical model in line with the actual situation, namely linear programming model. In various economic activities, often using linear programming model for scientific, quantitative analysis, organization and planning for produ

6、ction to achieve the optimal allocation of human and material resources, to get the best value for money. At present, the linear programming model is widely used in economic management, transportation, industrial and agricultural production and other fields.This paper describes two basic solution th

7、at graphical method for linear programming and the simplex method, and discuss the advantages and disadvantages of both methods and applications in a number of practical problems.Key words: Linear Programming；Graphic method; simplex method; mathematical model; Application目 錄 TOC o 1-3 h z u HYPERLIN

8、K l _Toc232231948 摘 要 HYPERLINK l _Toc232231949 Abstract HYPERLINK l _Toc232231950 第1章 緒論 HYPERLINK l _Toc232231952 1.1 線性規劃的基本概念 HYPERLINK l _Toc232231956 1.1.1 線性規劃簡介 HYPERLINK l _Toc232231956 1.1.2線性規劃由來的時間簡史 HYPERLINK l _Toc232231952 1.2 線性規劃的研究目的及意義 HYPERLINK l _Toc232231951 第2章 線性規劃問題的數學模型 HYP

9、ERLINK l _Toc232231952 2.1 線性規劃模型的建立 HYPERLINK l _Toc232231955 2.2 線性規劃模型的求解方法 HYPERLINK l _Toc232231956 2.2.1圖解法 HYPERLINK l _Toc232231957 2.2.2單純形法 HYPERLINK l _Toc232231951 第3章 線性規劃在實際問題中的應用 HYPERLINK l _Toc232231952 3.1 線性規劃在企業管理中的應用 HYPERLINK l _Toc232231956 3.1.1 線性規劃在企業管理中的應用范圍 HYPERLINK l _T

10、oc232231956 3.1.2 如何實現線性規劃在企業管理中的應用 HYPERLINK l _Toc232231955 3.2線性規劃在企業生產計劃中的應用 HYPERLINK l _Toc232231955 3.3線性規劃在運輸問題中的應用 HYPERLINK l _Toc232231966 結論 HYPERLINK l _Toc232231968 參考文獻第1章 緒論 1.1 線性規劃的基本概念 1.1.1 線性規劃簡介線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支,它是輔助人們進行科學管理的一種數學方法.在經濟管理、交通運輸、工農業生產等經濟活動中，提高經濟

11、效果是人們不可缺少的要求，而提高經濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產工藝，使用新設備和新型原材料.二是生產組織與計劃的改進，即合理安排人力物力資源.線性規劃所研究的是：在一定條件下，合理安排人力物力等資源，使經濟效果達到最好.一般地，求線性目標函數在線性約束條件下的最大值或最小值的問題，統稱為線性規劃問題.滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域.決策變量、約束條件、目標函數是線性規劃的三要素.1.1.2 線性規劃由來的時間簡史 法國數學家J.- B.- J.傅里葉和C.瓦萊普森分別于1832和1911年獨立地提出線性規劃的想法，但未引起注意.19

12、39年蘇聯數學家.康托羅維奇在生產組織與計劃中的數學方法一書中提出線性規劃問題，也未引起重視.1947年美國數學家G.B.Dantzing提出求解線性規劃的單純型法，為這門學科奠定了基礎.1947年美國數學家J.von諾伊曼提出對偶理論,開創了線性規劃的許多新的研究領域，擴大了它的應用范圍和解題能力.1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域，為此與康托羅維奇一起獲1975年諾貝爾經濟學獎.50年代后對線性規劃進行大量的理論研究，并涌現出一大批新的算法.例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題，19

13、56年A.塔克提出互補松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等.線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、隨機規劃和非線性規劃的算法研究.由于數字電子計算機的發展，出現了許多線性規劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規劃問題.1979年蘇聯數學家L. G. Khachian提出解線性規劃問題的橢球算法，并證明它是多項式時間算法.1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間算法.用這種方法求解線性規劃問題在變量個數為5000時只要單純形法所用時間的1/50.現已形成線性規劃

14、多項式算法理論.50年代后線性規劃的應用范圍不斷擴大. 建立線性規劃模型的方法第2章 線性規劃問題的數學模型2.1 線性規劃模型的建立線性規劃是合理利用、調配資源的一種應用數學的方法.它的基本思路是在滿足一定的約束條件下，使預定的目標達到最優.它的研究內容可歸納為兩個方面：一是系統的任務資源數量已定，精細安排，用最少的資源去實現這個任務；二是資源數量已定，如何合理利用、調配，使任務完成的最多.前者是求極小，后者是求極大.線性規劃的一般定義如下： 對于求取一組變量 Xj（j=1,2,n)，使之既滿足線性約束條件，又使具有線性特征的目標函數取得極值的一類最優化問題稱為線性規劃問題.線性規劃模型建立

15、需具備以下條件：一是最優目標.問題所要達到的目標能用線性函數來描述，且能夠使用極值 （最大或最小） 來表示.二是約束條件.達到目標的條件是有一定限制的，這些限制可以用決策變量的線性等式或線性不等式來表示.三是選擇條件，有多種方案可以供選擇，以便從中找出最優方案.線性規劃問題的一般數學模型如下： QUOTE (1) QUOTE QUOTE s.t. QUOTE QUOTE QUOTE (2) QUOTE QUOTE QUOTE 稱為決策變量 QUOTE 稱為目標函數系數 QUOTE ( QUOTE ) 稱為約束右端系數 QUOTE 稱為約束系數其中式（1）為目標函數，式（2）稱為約束條件 . 由

16、于目標函數和約束條件內容和形式上的差別，線性規劃問題有多種表達式，為了便于討論和制定統一的算法，規定標準形式如下：（1）標準形式 (2) 記號簡寫式 （3）矩陣形式 式中 QUOTE , QUOTE （4）向量形式 式中C,X,b,0的含義與矩陣的表達式相同，而 QUOTE 即A=（ QUOTE ） 將非標準形式化為標準形式的情況（3種基本情況）（1）目標函數為求極小值minZ=CX, 則作Z=-CX, 即maxZ=-CX(2)右端項小于0 只需要將兩端同乘（-1），不等號改變方向，然后再將 不等式改為等式（3）約束條件為不等式 若約束條件為“ QUOTE ”則在不等式左側增加一個非負松馳變量

17、，使其轉化為“”；若約束條件為“”，則在不等式左側減去一個非負剩余變量（也稱松馳變量），使其轉化為“”.2.2 線性規劃模型的求解方法 2.2.1圖解法線性規劃可以在一定條件下合理安排人力、 物力等資源 ,使經濟效果達到最好.一般來說 ,求線性目標函數在線性約束條件下的最大值或最小值的問題 ,統稱為線性規劃問題.滿足線性約束條件的解叫做可行解 ,由所有可行解組成的集合叫做可行域.決策變量、 約束條件、 目標函數是線性規劃的三要素.然而圖解法不適合解大規模的線性規劃的問題，局限性比較大.但對于只有兩個或者三個變量的線性規劃問題 ,可以用圖解法求最優解 ,也就是作出約束條件的可行域 ,利用圖解的方

18、法求出最優解 ,其特點是過程簡潔、 圖形清晰，簡單易懂.下面僅做只有兩個變量的線性規劃問題. 只含兩個變量的線性規劃問題，可以通過在平面上作圖的方法求解，步驟如下：（1）以變量x1為橫坐標軸，x2為縱坐標軸，適當選取單位坐標長度建立平面坐標直角坐標系.由變量的非負性約束性可知，滿足該約束條件的解均在第一象限內.（2）圖示約束條件，找出可行域（所有約束條件共同構成的圖形）.（3）畫出目標函數等值線，并確定函數增大（或減小）的方向.（4）可行域中使目標函數達到最優的點即為最優解.下面舉出一個實例來說明：例1某木器廠生產圓桌和衣柜兩種產品，現有兩種木料，第一種有72，第二種有56，假設生產每種產品都

19、需要用兩種木料，生產一張圓桌和一個衣柜分別所需木料如下表所示.每生產一張圓桌可獲利60元,生產一個衣柜可獲利100元.木器廠在現有木料條件下,圓桌和衣柜各生產多少,才使獲得利潤最多?產 品木料(單位)第 一 種第 二 種圓 桌0.180.08衣 柜0.090.28解：設生產圓桌張,生產衣柜個,利潤總額為元,則由已知條件得到的線性規劃模型為： QUOTE , QUOTE 72, 圖2-1這是二維線性規劃，可用圖解法解，先在xy坐標平面上作出滿足約束條件的平面區域,即可行域S，如上圖所示.再作直線,即,把直線平移至的位置時,直線經過可行域上點,且與原點距離最遠,此時取最大值，為了得到M點坐標解方程

20、組,得;于是知點坐標為(350,100)，從而得到使利潤總額最大的生產計劃，即生產圓桌350張,生產衣柜100個,能使利潤總額達到最大值31000元.這表明，當資源數量已知,經過合理制定生產計劃,可使效益最好,這就是用圖解法解線性規劃來解決生產計劃安排的問題之一. 2.2.2 單純形法單純形是美國數學家G.B.丹齊克于1947年首先提出來的.它的理論根據是：線性規劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到.頂點所對應的可行解稱為基本可行解.單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優解；若不是，則按照一定法則轉換到另一改進

21、的基本可行解，再鑒別；若仍不是，則再轉換，按此重復進行.因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解.如果問題無最優解也可用此法判別.1953年美國數學家G.B.丹齊克為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法.其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數.這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了在計算機上的存儲量.1954年美國數學家C.萊姆基提出對偶單純形法.單純形法是從原始問題的一個可行解通過迭代轉到另一個可行解，直到檢驗數滿足最優性條件為止.對偶單純

22、形法則是從滿足對偶可行性條件出發通過迭代逐步搜索原始問題的最優解.在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失.本節內容只對一般單形法的進行探討.下面舉出一個實際例子來做介紹例：求下列線性規劃問題的最優解 解：化為標準形式 （1）第一步：確定一個初始基可行解；基可行解就是滿足非負條件的基本解，因此要在約束矩陣A中找出一個可逆的基矩陣. （2）這里m=3，3階可逆方陣，可以看出x3,x4,x5的系數列向量是線性獨立的，這些向量構成一個基)，對應的基變量為x3,x4,x5，x1,x2為非基變量.將基變量用非基變量表示，由(2)得：x3=160-30 x1-20 x2x4=15-5x1

23、-x2 （3）x5=4-x1將(3)代入目標函數得Z=5x1+2x2+0令非基變量x1=x2=0,代入(3),得到一個基可行解X(0)X(0)=(0,0,160,15,4)第二步：從當前基可行解轉換為更好的基可行解；從數學角度看，x1,x2的增加將會增加目標函數值，從目標函數值中x1,x2前的系數看，x1前的系數大于x2前的系數，所以讓x1從非基變量轉為基變量，稱為進基變量，怎樣確定離基變量：因為x2仍為非基變量，故x2=0則(3)式變為x3=160-30 x1 160/30=16/3x4=15-5x1 15/5=3x5=4-x1 4/1=4min=3，所以當x1=3時，x4第一個減少到0，所

24、以x4出基,則X(1)=(3,0,70,0,1)Z(1)=15此時非基變量為x2,x4,用非基變量表示基變量，代入(3)x3=70-14x2+6x4x1=3-1/5x2-1/5x4 （4）x5=1+1/5x2+1/5x4將(4)代入目標函數得Z=15+x2-x4第三步：繼續迭代x2進基，x4仍為非基變量，令x4=0，則(4)式表示為x3=70-14x2 70/145x1=3-1/5x2 3/(1/5)15x5=1+1/5x2min=5，所以當x2=5時，x3首先減少到0，所以x3出基則X(2)=(2,5, 0,0,2)Z(2)=20此時非基變量為x3,x4,用非基變量表示基變量，代入(4)x2

25、=5-1/14x3+3/7x4x1=2+1/70 x3-2/7x4 （5）x5=2-1/70 x3+2/7x4將(5)代入目標函數得Z=20-1/14x3-4/7x4此時若非基變量x3,x4的值增加，只能使Z值下降所以X(2)為最優解，Z*=20, X*=(2,5, 0,0,2)第三章 線性規劃模型在實際問題中的應用3.1 線性規劃在企業管理中的應用 3.1.1 線性規劃在企業管理中的應用范圍 線性規劃在企業管理中的應用廣泛，主要有以下八種形式：1.產品生產計劃：合理利用人力、物力、財力等，是獲利最大.2.勞動力安排 ：用最少的勞動力來滿足工作的需要.3.運輸問題 ：如何制定運輸方案，使總運費

26、最少.4.合理利用線材問題 ：如何下料，使用料最少.5.配料問題 ：在原料供應的限制下如何獲得最大利潤.6.投資問題 ：從投資項目中選取方案，是投資回報最大.7.庫存問題 ：在市場需求和生產實際之間，如何控制庫存量從而獲得更高利益.8.最有經濟計劃問題 ：在投資和生產計劃中如何是風險最小.3.1.2如何實現線性規劃在企業管理中的應用在線性規劃應用前要建立經濟與金融體系的評價標準及企業的計量體系，摸清企業的資源.首先通過建網、建庫、查詢、數據采集、文件轉換等，把整個系統的各有關部分的特征進行量化，建立數學模型，即把組成系統的有關因素與系統目標的關系，用數學關系和邏輯關系描述出來，然后白較好的數學

27、模型編制成計算機語言，輸入數據，進行計算，不同參數獲取的不同結果與實際進行分析對比，進行定量，定性分析，最終作出決策.3.2線性規劃在企業生產計劃中的應用 一：應用線性規劃來進行生產計劃問題分析，首先需要弄清楚以下幾點：1.必須明確目標函數.生產計劃的經濟分析是一種定量分析方法，它以企業利潤作為評價目標值，所尋求的目標是使企業利潤最大化的生產計劃決策，因此，企業利潤最大化應是生產計劃決策分析的目標函數.2.必須明確約束條件.企業的生產能力，原材料，設備使用，市場需求狀況等諸多制約因素與生產計劃分析密切相關，稱為生產計劃分析中目標函數的約束條件.約束條件對生產計劃分析的影響較大，在不同條件下，決

28、策分析的結論則會不同.比如，就市場需求和企業生產能力之間的關系而言，企業所處狀態可有三種類型:能力不足狀態，即市場對產品的需求超過了企業的生產能力;能力過剩狀態，即企業生產能力超過了市場需要:中間狀態，即供求平衡的狀態，或者有時處于不足狀態，有時又處于過剩狀態.3.必須明確單件利潤.單件利潤不僅牽扯到產品的單件收入，還要牽扯到生產所耗費的各項成本及費用. 二、建立生產計劃決策分析的線性規劃模型生產計劃決策分析的基本方法是以利潤最大化作為優化目標，明確未知變量，確定約束條件，建立線性規劃模型，最終實現企業效益最大化的生產計劃.其一般模式: 目標函數為利潤P=銷售收入R-(成本+費用)C.在各種約

29、束條件下，使目標函數達到最大值.分析企業實際生產過程中的日產量情況，設模型的未知變量為企業生產的產品種類日產量 QUOTE QUOTE 建立生產計劃決策分析線性規劃模型的過程如下:( 1 )目標函數企業進行生產計劃決策的目標值是企業利潤最大化.現假設生產各種產品所獲得的銷售收入R;與所耗費的產品成本和費用C;均已知，則可以得出生產計劃問題的目標函數為: QUOTE ( 2 )原材料約束無論是生產何種產品都需要消耗一定的原材料，在企業實際中若需耗用多種原材料則可根據原材料的種類，增添相應約束條件即可，建立約束不等式: QUOTE 上式中， QUOTE 分別為生產第1,2， QUOTE ，n種產品

30、的單件原材料消耗， QUOTE 為企業每可用的原材料總量.（3）生產能力約束. 此約束具體表現為企業的可用工作時間或可用設備，而企業在一定時期內的可用工作是有限的，所以可建立如下的約束不等式： QUOTE 上式中， QUOTE 分別為生產第1,2， QUOTE 種產品的單件消耗工時， QUOTE 為企業的日可用的工時、料總量.（4）市場需求約束 為了說明問題的方便，假設企業生產的產品市場都有需求，即 QUOTE ,無上限約束.若第j種產品市場需求有限，最大需求為 QUOTE ,則可增加約束 QUOTE .（5）非負約束因為生產實際中最多即為不生產產品，所以所有變量 QUOTE 綜上所述，建立生

31、產計劃決策分析的線性規劃模型如下： QUOTE QUOTE QUOTE s. t QUOTE QUOTE QUOTE 3.3 線性規劃在運輸問題中的應用運輸是物流活動的核心環節，線性規劃是運輸問題的常用數學模型，利用數學知識可以得到優化的運輸方案.運輸問題的提出源于如何物流活動中的運輸路線或配送方案是最經濟或最低成本的.運輸問題解決的是已知產地的供應量，銷地的需求量及運輸單價，如何尋找總配送成本最低的方案；運輸問題包含產銷平衡運輸問題和產銷不平衡運輸問題；通常將產銷不平衡問題轉化為產銷平衡問題來處理；運輸問題的條件包括需求假設和成本假設.需求假設指每一個產地都有一個固定的供應量所有的供應量都必

32、須配送到目的地.與之類似，每一個目的地都有一個固定的需求量，整個需求量都必須有出發地滿足；成本假設指從任何一個產地到任何一個銷地的配送成本和所配送的數量的線性比例關系.產銷平衡運輸問題的一般提法是：假設某物資有m個產地 QUOTE ;各地產量分別為 QUOTE 物資從產地 QUOTE 運往銷地 QUOTE 的單位運價為 QUOTE ,滿足：.其數學模型為：Min Z= QUOTE 產地約束s.t QUOTE 銷地約束 （a） QUOTE ( QUOTE 非負約束1：產銷不平衡運輸問題分兩種情況：（1）總產量大于總銷量，既滿足，此時其數學模型與表達式(a)基本相同，只需將表達式（a）中的產地約束

33、條件 QUOTE 改為 QUOTE .（2）總產量小于總銷量，既滿足，此時其數學模型與表達式(a)也基本相同，只需將表達式（a）中的產地約束條件 QUOTE 改為 QUOTE .2.運輸問題的解決策略 現實生產的情況往往比較復雜，許多實際問題不一定完全符合運輸問題的假設，可能一些特征近似但其中的一個或者幾個特征卻并不符合運輸問題條件.一般來說，如果一個問題中涉及兩大類對象之間的聯系或往來，且該問題能提供運輸問題所需要的三類數據:供應量、需求量、單位運價，那么這個問題(不管其中是否涉及運輸)經適當約束條件的處理后，基木都可以應用運輸問題模型來解決.例如:（1）追求的目標是效益最大而非成木最低，此

34、時僅將表達式(a)中目標函數中的“Min Z”改為“Max Z”即可.（2）部分(或全部)的供應量(產量)代表的是從產地提供的最大數量(而不是一個固定的數值)，此時只需將表達式(a)中的產地約束中部分(或全部)的“ QUOTE ”改成“ QUOTE ”即可.(3)部分(或全部)的需求量(銷量)代表的是銷地接收的最大數量(而不是一個固定的數值)，此時只需將表達式(a)中的銷地約束條件中的“ QUOTE ”部分(或全部)改成“ QUOTE ”即可.(4)某些目的地的同時存在最大需求和最小需求，此時的解決辦法是將表達式(a)中的相應的銷地約束中的“ QUOTE ”一個式子分解成最大需求和最小需求的兩

35、個式子即可. 結 論如今，線性規劃的求解方法有很多，許多學者都對原先的求解方法進行了不斷的改進，計算機時代的發展也加快了解決復雜線性規劃問題的速度。這就使得線性規劃在實際生活中的應用更加的廣泛。目前，中國經濟正在快速的發展過程中，其發展的速度已經超過了發達國家在相同的時期發展速度。隨著中國進入了WTO，中國經濟正在熔入世界經濟的大的市場并不斷的適應和改進自己的各個方面的制度，與此同時世界各國都在不斷的發展自己 。所以線性規劃在經濟領域的應用顯得非常重要。參考文獻 1 寧宣熙，運籌學實用教程M . 北京：科學出版社，2003. 2 胡運權，運籌學基礎及應用M.北京：清華大學出版社，2004. 3

36、 姜啟源. 數學模型（第二版）M. 高等教育出版社, 1993 4 夏少剛， 劉心. 線性規劃求基可行解的一種方法J. 運籌學學報，2008. 5 胡運權.運籌學基礎及應用M.哈爾濱：哈爾濱工業大學出版社，1998.2：105-109 6 現代應用數學手冊運籌學與最優化理論卷M.北京：清華大學出版社，1998：68-89 7 姜啟源,謝金星,葉俊. 數學模型M. 北京:高等教育出版社，2003.8 8 劉來福, 增文藝. 數學模型與數學建模M. 北京師范大學出版社, 2006 9 管梅谷，鄭漢鼎.線性規劃.濟南:山東科學技術出版社,1983.10 SCHERER C， WEILAND S. L

37、inear matrix inequalities inontril D . delft University of Tdchnology,2005.4 BOYD S, CHAOUI L El,FERON E. etal. Linear mattrix inequalities in systems and control theory M . Philadlphia:SIAM Books1994 11ACKLEY D H. A connectionist machine for genetic hillclimbingM.Boston, USA:Kluwer Academic; Publis

38、shers,1987.附錄資料：不需要的可以自行刪除C語言編譯器的設計與實現 我們設計的編譯程序涉及到編譯五個階段中的三個，即詞法分析器、語法分析器和中間代碼生成器。編譯程序的輸出結果包括詞法分析后的二元式序列、變量名表、狀態棧分析過程顯示及四元式序列程序，整個編譯程序分為三部分：(1) 詞法分析部分(2) 語法分析處理及四元式生成部分 (3) 輸出顯示部分一詞法分析器設計 由于我們規定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯誤的檢查，而將編譯程序的重點放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號。我們規定輸出的單詞符號格式為如下的二元式： (單詞種別，單

39、詞自身的值)#define ACC -2#define syl_if 0#define syl_else 1#define syl_while 2#define syl_begin 3#define syl_end 4#define a 5#define semicolon 6#define e 7#define jinghao 8#define s 9#define L 10#define tempsy 11#define EA 12#define EO 13#define plus 14#define times 15#define becomes 16#define op_and 17#

40、define op_or 18#define op_not 19#define rop 20#define lparent 21#define rparent 22#define ident 23#define intconst 24函數說明 讀取函數 readline( )、readch( )詞法分析包含從源文件讀取字符的操作，但頻繁的讀文件操作會影響程序執行效率，故實際上是從源程序文件” source.dat ”中讀取一行到輸入緩沖區，而詞法分析過程中每次讀取一個字符時則是通過執行 readch( )從輸入緩沖區獲得的；若緩沖區已被讀空，則再執行readline( )從 source.da

41、t 中讀取下一行至輸入緩沖區。掃描函數 scan( ) 掃描函數 scan( )的功能是濾除多余空格并對主要單詞進行分析處理，將分析得到的二元式存入二元式結果緩沖區。變量處理 find（ ）變量處理中首先把以字母開頭的字母數字串存到 spelling 數組中，然后進行識別。識別過程是先讓它與保留關鍵字表中的所有關鍵字進行匹配，若獲得成功則說明它為保留關鍵字，即將其內碼值寫入二元式結果緩沖區；否則說明其為變量，這時讓它與變量名表中的變量進行匹配（ 變量匹配函數 find（ ） ），如果成功，則說明該變量已存在并在二元式結果緩沖區中標記為此變量（ 值填為該變量在變量名表中的位置），否則將該變量登記

42、到變量名表中，再將這個新變量存入二元式緩存數組中。數字識別 number( ) 數字識別將識別出的數字填入二元式結果緩存數組。顯示函數 顯示函數的功能在屏幕上輸出詞法分析的結果（ 即二元式序列程序），同時給出二元式個數及源程序行數統計。二語法分析器設計 語法分析器的核心是三張 SLR 分析表以及針對這三張 SLR 分析表進行語義加工的語義動作。編譯程序中語法分析處理及四元式生成部分主要是以二元式作為輸入，并通過 SLR 分析表對語法分析處理過程進行控制，使四元式翻譯的工作有條不紊的進行，同時識別語法分析中的語法錯誤。在處理 if 和 while 語句時，需要進行真值或假值的拉鏈和返填工作，以便

43、轉移目標的正確填入。1. 控制語句的 SLR 分析表1 設計過程如下： 將擴展文法GS S1）S if e S else S2）S while e S3）S L 4）S a;5）L S6）L SL用_CLOSURE方法構造LR(0)項目規范簇為：I0： S SS if e S else SS while e S S L S a ;I1: S SI2: S ife S else SI3: S while e SI4: S L L S L SL S if e S else SS while e S S L S a ; I5: S a; I6: S if e S else S S if e S el

44、se SS while e S S L S a ; I7: S while e S S if e S else SS while e S S L S a ; I8: S L I9: L S L SL L SL L S S if e S else SS while e S S L S a ; I10: S a ; I11: S if e S else SI12: S while e S I13: S L I14: S SL I15: S if e S else S S if e S else SS while e S S L S a ; I16: S if e S else S 構造文法G中非終

45、結符的FOLLOW集如下：FOLLOW(S) = # S if e S else S得FOLLOW(S) = else S L 得FOLLOW(L) = 3) S S 得FOLLOW(S) = else , # L S 因為FIRST(S) = ，所以FOLLOW(S) = else , #, 在（）項目規范簇中，只有9有“移進歸約”沖突，L SL SL因為FOLLOW(L) FIRST(L) = 所以可以用方法解決以上沖突，最后我們得到的分析表如下：ACTIONGOTO ifElsewhilea;e#SL0S2S3S4S511ACC2S63S74S2S3S4S5985S106S2S3S4S5

46、117S2S3S4S5128S139S2S3S4R5S591410R4R4R4111512R2R2R213R3R3R314R615S2S3S4S51616R1R1R1static int action2011=/* 0 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 1, -1,/* 1 */ -1, -1, -1, -1, -1, -1, -1, -1,ACC, -1, -1,/* 2 */ -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1,/* 3 */ -1, -1, -1, -1, -1, -1, -1, 7, -1, -1, -

47、1,/* 4 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 9, 8,/* 5 */ -1, -1, -1, -1, -1, -1, 10, -1, -1, -1, -1,/* 6 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 11, -1,/* 7 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 12, -1,/* 8 */ -1, -1, -1, -1, 13, -1, -1, -1, -1, -1, -1,/* 9 */ 2, -1, 3, 4,105, 5, -1, -1, -1, 9, 14,/* 10*/ -1,

48、104, -1, -1,104, -1, -1, -1,104, -1, -1,/* 11*/ -1, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,/* 12*/ -1,102, -1, -1,102, -1, -1, -1,102, -1, -1,/* 13*/ -1,103, -1, -1,103, -1, -1, -1,103, -1, -1,/* 14*/ -1, -1, -1, -1,106, -1, -1, -1, -1, -1, -1,/* 15*/ 2, -1, 3, 4, -1, 5, -1, -1, -1, 16, -1,/* 16*/ -

49、1,101, -1, -1,101, -1, -1, -1,101, -1, -1;其中，前 9 列為 action 值，后 2 列為 goto 值；016 表示 17 個移進狀態（ 即 Si）；-1表示出錯；ACC 表示分析成功；而 100106 對應 7 個歸約產生式：S SS if e S else SS while e SS L S a;L SL SL2. 算術表達式的 LR 分析表 2 設計如下：S EE E+EE E*EE (E)E i （過程略）ACTIONGOTOI+*()#E0S3S211S4S5ACC2S3S263R4R4R4R44S3S275S3S286S4S5S97R1

50、R5R1R18R2R2R2R29R3R3R3R3static int action1107=/* 0 */ 3, -1, -1, 2, -1, -1, 1,/* 1 */ -1, 4, 5, -1, -1,ACC, -1,/* 2 */ 3, -1, -1, 2, -1, -1, 6,/* 3 */ -1,104,104, -1,104,104, -1,/* 4 */ 3, -1, -1, 2, -1, -1, 7,/* 5 */ 3, -1, -1, 2, -1, -1, 8,/* 6 */ -1, 4, 5, -1, 9, -1, -1,/* 7 */ -1,101, 5, -1,101,

51、101, -1,/* 8 */ -1,102,102, -1,102,102, -1,/* 9 */ -1,103,103, -1,103,103, -1;3.布爾表達式的 SLR 分析表3 設計如下：（過程略）S BB iB i rop iB ( B )B ! BA B &B ABO B |B OBACTIONGOTOiRop()!&|#BAO0S1S4S513781S2R1R1R1R12S33R2R2R2R24S1S4S511785S1S4S56786R4S9S10R47S1S4S514788S1S4S515789R5R5R510R7R7R711S12S9S1012R3R3R3R313S9

52、S10ACC14R6S9S10R615R8S9S10R8static int action21611=/* 0 */ 1, -1, 4, -1, 5, -1, -1, -1, 13, 7, 8,/* 1 */ 1, 2, -1,101, -1,101,101,101, -1, -1, -1,/* 2 */ 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,/* 3 */ -1, -1, -1,102, -1,102,102,102, -1, -1, -1,/* 4 */ 1, -1, 4, -1, 5, -1, -1, -1, 11, 7, 8,/* 5 */

53、 1, -1, 4, -1, 5, -1, -1, -1, 6, 7, 8,/* 6 */ -1, -1, -1,104, -1, 9, 10,104, -1, -1, -1,/* 7 */ 1, -1, 4, -1, 5, -1, -1, -1, 14, 7, 8,/* 8 */ 1, -1, 4, -1, 5, -1, -1, -1, 15, 7, 8,/* 9 */ 105, -1,105, -1,105, -1, -1, -1, -1, -1, -1,/*10 */ 107, -1,107, -1,107, -1, -1, -1, -1, -1, -1,/*11 */ -1, -1,

54、-1, 12, -1, 9, 10, -1, -1, -1, -1,/*12 */ -1, -1, -1,103, -1,103,103,103, -1, -1, -1,/*13 */ -1, -1, -1, -1, -1, 9, 10,ACC, -1, -1, -1,/*14 */ -1, -1, -1,106, -1, 9, 10,106, -1, -1, -1,/*15 */ -1, -1, -1,108, -1, 9, 10,108, -1, -1, -1;LR 分析表控制語義加工的實現：當掃描 LR 分析表的當前狀態為歸約狀態時，則在調用與該狀態對應的產生式進行歸約的同時，調用相應的

55、語義子程序進行有關的翻譯工作。現在對 LR 分析器的分析棧加以擴充，使得每個文法符號之后都跟著它的語義值。為了清晰起見，我們把這個棧的每一項看成由三部分組成：狀態 state ，文法符號 syl 和語義值 val。編譯程序實現算術表達式、布爾表達式及程序語句的語義加工時，都是按這種狀態棧加工方式進行的。例如：( 5 + 3 ) * 6的分析過程序號STATEValsylinput10-#( 5 + 3 ) * 6 #202-#(5 + 3 ) * 6 #3023-#(5+ 3 ) * 6 #4026-5#(E+ 3 ) * 6 #50264-5-#(E+3 ) * 6 #602643-5-#(

56、E+3 ) * 6 #702647-5-3#(E+E) * 6 #8026-8#(E) * 6 #90269-8-#(E)* 6 #1001-8#E* 6 #11015-8-#E* 6 #120153-8-#E*6#130158-8-6#E*E#1401-48#E#15ACC在分析過程中，第（3）步操作后的狀態棧為 023，根據棧頂狀態“ 3”和現行輸入符號“ +”（ input 欄字符串的第一個字符）查分析表 ACTION3，+=R4，即按第（4）個產生式 En 來進行歸約；由于產生式右部僅含一項，故去掉狀態棧棧頂“3”；此時 2 變為新的棧頂狀態，再查（ 2，E）的下一狀態 s：GOTO2

57、,E=6，即將狀態 6 和文法符號 E 壓棧，最后得到第（ 4）步的狀態。第（ 7）步操作后也是如此，當前狀態棧為 02647，根據棧頂狀態 7 和現行輸入符號“ ）”查分析表 ACTION7，）=R1，即按第（1）個產生式 EE1+E2進行歸約；由于產生式右部有三項，故去掉狀態棧棧頂的 647 三項；此時 2 變為新的棧頂狀態，再查（ 2，E）的下一狀態 s：GOTO2，E=6,即將狀態 6 和文法符號 E 壓棧，最后得到第（8）步的狀態。三中間代碼生成器設計：布爾表達式 布爾表達式在程序語言中有兩個基本作用：一是用作控制語句（ 如 if -else 或 while語句）的條件式；二是用于邏

58、輯演算，計算邏輯值。布爾表達式是由布爾算符（ &、| 、！）作用于布爾變量（ 或常數）或關系表達式而形成的。關系表達式的形式是 E1 rop E2，其中 rop 是關系符（ 如或），E1和 E2是算術式。在這里，我們只考慮前面給定文法所產生的布爾表達式：BB &B | B | B | ! B | (B) | i rop i | i遵照我們的約定，布爾算符的優先順序（ 從高到低）為：!、&、|，并假定&和|都服從左結合規則。所有關系符的優先級都是相同的，而且高于任何布爾算符，低于任何算術算符，關系算符不得結合。表達式的真、假出口的確定：考慮表達式 B1 | B2 ，若 B1為真，則立即知道 B

59、也為真；因此，B1的真出口也就是整個 B 的真出口。若 B1?為假，則 B2必須被計值，B2的第一個四元式就是 B1的假出口。當然，B2的真、假出口也就是整個 B的真、假出口。類似的考慮適用于對 B1 & B2的翻譯，我們將 B1 | B2和 B1 & B2 的翻譯用下圖表示，在自下而上的分析過程中，一個布爾式的真假出口往往不能在產生四元式的同時就填上。我們只好把這種未完成的四元式的地址（ 編號）作為 B 的語義值暫存起來，待到整個表達式的四元式產生完畢之后再來回填這個未填入的轉移目標。條件語句對條件語句 if e S1 else S2 中的布爾表達式 e，其作用僅在于控制對 S1和 S2的選

60、擇。因此，作為轉移條件的布爾式e，我們可以賦予它兩種“ 出口”：一是“ 真”出T口，出向 S1；一是“ 假”出口，出向 S2。于是，e的代碼F條件語句可以翻譯成如圖的一般形式。非終結符 e 具有兩項語義值 e _TC 和e_FC，它們分別指出了尚待回填真、S2的代碼假出口的四元式串。e 的“ 真”出口只有在往回掃描到if時才能知道，而它圖 3-2 條件語句的代碼結構 的“ 假”出口則需到處理過 S1并且到達 else 才能明確。這就是說，必須把 e_FC 的值傳下去，以便到達相應的 else時才進行回填。另外，當 S1語句執行完時意味著整個 if-else 語句也已執行完畢；因此，在 S1的編