線性規(guī)劃大學(xué)畢業(yè)論文分析

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

2、.其解決問題的關(guān)鍵是建立符合實(shí)際情況的數(shù)學(xué)模型，即線性規(guī)劃模型.在各種經(jīng)濟(jì)活動(dòng)中，常采用線性規(guī)劃模型進(jìn)行科學(xué)、定量分析，安排生產(chǎn)組織與計(jì)劃，實(shí)現(xiàn)人力物力資源的最優(yōu)配置，獲得最佳的經(jīng)濟(jì)效益.目前，線性規(guī)劃模型被廣泛應(yīng)用與經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等領(lǐng)域.本文主要介紹線性規(guī)劃的兩種基本解法即圖解法和單純形法，并討論了這兩種方法的優(yōu)缺點(diǎn)和在一些實(shí)際問題中的應(yīng)用.關(guān)鍵詞: 線性規(guī)劃；圖解法；單純形法；數(shù)學(xué)模型；應(yīng)用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 線性規(guī)劃的基本概念 HYPERLINK l _Toc232231956 1.1.1 線性規(guī)劃簡介 HYPERLINK l _Toc232231956 1.1.2線性規(guī)劃由來的時(shí)間簡史 HYPERLINK l _Toc232231952 1.2 線性規(guī)劃的研究目的及意義 HYPERLINK l _Toc232231951 第2章 線性規(guī)劃問題的數(shù)學(xué)模型 HYP

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

10、oc232231956 3.1.2 如何實(shí)現(xiàn)線性規(guī)劃在企業(yè)管理中的應(yīng)用 HYPERLINK l _Toc232231955 3.2線性規(guī)劃在企業(yè)生產(chǎn)計(jì)劃中的應(yīng)用 HYPERLINK l _Toc232231955 3.3線性規(guī)劃在運(yùn)輸問題中的應(yīng)用 HYPERLINK l _Toc232231966 結(jié)論 HYPERLINK l _Toc232231968 參考文獻(xiàn)第1章 緒論 1.1 線性規(guī)劃的基本概念 1.1.1 線性規(guī)劃簡介線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支,它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法.在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)

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

12、39年蘇聯(lián)數(shù)學(xué)家.康托羅維奇在生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書中提出線性規(guī)劃問題，也未引起重視.1947年美國數(shù)學(xué)家G.B.Dantzing提出求解線性規(guī)劃的單純型法，為這門學(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).50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法.例如，1954年C.萊姆基提出對(duì)偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，19

13、56年A.塔克提出互補(bǔ)松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等.線性規(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.現(xiàn)已形成線性規(guī)劃

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

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

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

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

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

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

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

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

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

23、-x2 （3）x5=4-x1將(3)代入目標(biāo)函數(shù)得Z=5x1+2x2+0令非基變量x1=x2=0,代入(3),得到一個(gè)基可行解X(0)X(0)=(0,0,160,15,4)第二步：從當(dāng)前基可行解轉(zhuǎn)換為更好的基可行解；從數(shù)學(xué)角度看，x1,x2的增加將會(huì)增加目標(biāo)函數(shù)值，從目標(biāo)函數(shù)值中x1,x2前的系數(shù)看，x1前的系數(shù)大于x2前的系數(shù)，所以讓x1從非基變量轉(zhuǎn)為基變量，稱為進(jìn)基變量，怎樣確定離基變量：因?yàn)閤2仍為非基變量，故x2=0則(3)式變?yōu)閤3=160-30 x1 160/30=16/3x4=15-5x1 15/5=3x5=4-x1 4/1=4min=3，所以當(dāng)x1=3時(shí)，x4第一個(gè)減少到0，所

24、以x4出基,則X(1)=(3,0,70,0,1)Z(1)=15此時(shí)非基變量為x2,x4,用非基變量表示基變量，代入(3)x3=70-14x2+6x4x1=3-1/5x2-1/5x4 （4）x5=1+1/5x2+1/5x4將(4)代入目標(biāo)函數(shù)得Z=15+x2-x4第三步：繼續(xù)迭代x2進(jìn)基，x4仍為非基變量，令x4=0，則(4)式表示為x3=70-14x2 70/145x1=3-1/5x2 3/(1/5)15x5=1+1/5x2min=5，所以當(dāng)x2=5時(shí)，x3首先減少到0，所以x3出基則X(2)=(2,5, 0,0,2)Z(2)=20此時(shí)非基變量為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)代入目標(biāo)函數(shù)得Z=20-1/14x3-4/7x4此時(shí)若非基變量x3,x4的值增加，只能使Z值下降所以X(2)為最優(yōu)解，Z*=20, X*=(2,5, 0,0,2)第三章 線性規(guī)劃模型在實(shí)際問題中的應(yīng)用3.1 線性規(guī)劃在企業(yè)管理中的應(yīng)用 3.1.1 線性規(guī)劃在企業(yè)管理中的應(yīng)用范圍 線性規(guī)劃在企業(yè)管理中的應(yīng)用廣泛，主要有以下八種形式：1.產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、物力、財(cái)力等，是獲利最大.2.勞動(dòng)力安排 ：用最少的勞動(dòng)力來滿足工作的需要.3.運(yùn)輸問題 ：如何制定運(yùn)輸方案，使總運(yùn)費(fèi)

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

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

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

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

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

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

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

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

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

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

36、 姜啟源. 數(shù)學(xué)模型（第二版）M. 高等教育出版社, 1993 4 夏少剛， 劉心. 線性規(guī)劃求基可行解的一種方法J. 運(yùn)籌學(xué)學(xué)報(bào)，2008. 5 胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用M.哈爾濱：哈爾濱工業(yè)大學(xué)出版社，1998.2：105-109 6 現(xiàn)代應(yīng)用數(shù)學(xué)手冊(cè)運(yùn)籌學(xué)與最優(yōu)化理論卷M.北京：清華大學(xué)出版社，1998：68-89 7 姜啟源,謝金星,葉俊. 數(shù)學(xué)模型M. 北京:高等教育出版社，2003.8 8 劉來福, 增文藝. 數(shù)學(xué)模型與數(shù)學(xué)建模M. 北京師范大學(xué)出版社, 2006 9 管梅谷，鄭漢鼎.線性規(guī)劃.濟(jì)南:山東科學(xué)技術(shù)出版社,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語言編譯器的設(shè)計(jì)與實(shí)現(xiàn) 我們?cè)O(shè)計(jì)的編譯程序涉及到編譯五個(gè)階段中的三個(gè)，即詞法分析器、語法分析器和中間代碼生成器。編譯程序的輸出結(jié)果包括詞法分析后的二元式序列、變量名表、狀態(tài)棧分析過程顯示及四元式序列程序，整個(gè)編譯程序分為三部分：(1) 詞法分析部分(2) 語法分析處理及四元式生成部分 (3) 輸出顯示部分一詞法分析器設(shè)計(jì) 由于我們規(guī)定的程序語句中涉及單詞較少，故在詞法分析階段忽略了單詞輸入錯(cuò)誤的檢查，而將編譯程序的重點(diǎn)放在中間代碼生成階段。詞法分析器的功能是輸入源程序，輸出單詞符號(hào)。我們規(guī)定輸出的單詞符號(hào)格式為如下的二元式： (單詞種別，單

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函數(shù)說明 讀取函數(shù) readline( )、readch( )詞法分析包含從源文件讀取字符的操作，但頻繁的讀文件操作會(huì)影響程序執(zhí)行效率，故實(shí)際上是從源程序文件” source.dat ”中讀取一行到輸入緩沖區(qū)，而詞法分析過程中每次讀取一個(gè)字符時(shí)則是通過執(zhí)行 readch( )從輸入緩沖區(qū)獲得的；若緩沖區(qū)已被讀空，則再執(zhí)行readline( )從 source.da

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

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

43、轉(zhuǎn)移目標(biāo)的正確填入。1. 控制語句的 SLR 分析表1 設(shè)計(jì)過程如下： 將擴(kuò)展文法GS S1）S if e S else S2）S while e S3）S L 4）S a;5）L S6）L SL用_CLOSURE方法構(gòu)造LR(0)項(xiàng)目規(guī)范簇為：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òu)造文法G中非終

45、結(jié)符的FOLLOW集如下：FOLLOW(S) = # S if e S else S得FOLLOW(S) = else S L 得FOLLOW(L) = 3) S S 得FOLLOW(S) = else , # L S 因?yàn)镕IRST(S) = ，所以FOLLOW(S) = else , #, 在（）項(xiàng)目規(guī)范簇中，只有9有“移進(jìn)歸約”沖突，L SL SL因?yàn)镕OLLOW(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 個(gè)移進(jìn)狀態(tài)（ 即 Si）；-1表示出錯(cuò)；ACC 表示分析成功；而 100106 對(duì)應(yīng) 7 個(gè)歸約產(chǎn)生式：S SS if e S else SS while e SS L S a;L SL SL2. 算術(shù)表達(dá)式的 LR 分析表 2 設(shè)計(jì)如下：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.布爾表達(dá)式的 SLR 分析表3 設(shè)計(jì)如下：（過程略）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 分析表控制語義加工的實(shí)現(xiàn)：當(dāng)掃描 LR 分析表的當(dāng)前狀態(tài)為歸約狀態(tài)時(shí)，則在調(diào)用與該狀態(tài)對(duì)應(yīng)的產(chǎn)生式進(jìn)行歸約的同時(shí)，調(diào)用相應(yīng)的

55、語義子程序進(jìn)行有關(guān)的翻譯工作?，F(xiàn)在對(duì) LR 分析器的分析棧加以擴(kuò)充，使得每個(gè)文法符號(hào)之后都跟著它的語義值。為了清晰起見，我們把這個(gè)棧的每一項(xiàng)看成由三部分組成：狀態(tài) state ，文法符號(hào) syl 和語義值 val。編譯程序?qū)崿F(xiàn)算術(shù)表達(dá)式、布爾表達(dá)式及程序語句的語義加工時(shí)，都是按這種狀態(tài)棧加工方式進(jìn)行的。例如：( 5 + 3 ) * 6的分析過程序號(hào)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）步操作后的狀態(tài)棧為 023，根據(jù)棧頂狀態(tài)“ 3”和現(xiàn)行輸入符號(hào)“ +”（ input 欄字符串的第一個(gè)字符）查分析表 ACTION3，+=R4，即按第（4）個(gè)產(chǎn)生式 En 來進(jìn)行歸約；由于產(chǎn)生式右部僅含一項(xiàng)，故去掉狀態(tài)棧棧頂“3”；此時(shí) 2 變?yōu)樾碌臈ｍ敔顟B(tài)，再查（ 2，E）的下一狀態(tài) s：GOTO2

57、,E=6，即將狀態(tài) 6 和文法符號(hào) E 壓棧，最后得到第（ 4）步的狀態(tài)。第（ 7）步操作后也是如此，當(dāng)前狀態(tài)棧為 02647，根據(jù)棧頂狀態(tài) 7 和現(xiàn)行輸入符號(hào)“ ）”查分析表 ACTION7，）=R1，即按第（1）個(gè)產(chǎn)生式 EE1+E2進(jìn)行歸約；由于產(chǎn)生式右部有三項(xiàng)，故去掉狀態(tài)棧棧頂?shù)?647 三項(xiàng)；此時(shí) 2 變?yōu)樾碌臈ｍ敔顟B(tài)，再查（ 2，E）的下一狀態(tài) s：GOTO2，E=6,即將狀態(tài) 6 和文法符號(hào) E 壓棧，最后得到第（8）步的狀態(tài)。三中間代碼生成器設(shè)計(jì)：布爾表達(dá)式 布爾表達(dá)式在程序語言中有兩個(gè)基本作用：一是用作控制語句（ 如 if -else 或 while語句）的條件式；二是用于邏

58、輯演算，計(jì)算邏輯值。布爾表達(dá)式是由布爾算符（ &、| 、?。┳饔糜诓紶栕兞浚?或常數(shù)）或關(guān)系表達(dá)式而形成的。關(guān)系表達(dá)式的形式是 E1 rop E2，其中 rop 是關(guān)系符（ 如或），E1和 E2是算術(shù)式。在這里，我們只考慮前面給定文法所產(chǎn)生的布爾表達(dá)式：BB &B | B | B | ! B | (B) | i rop i | i遵照我們的約定，布爾算符的優(yōu)先順序（ 從高到低）為：!、&、|，并假定&和|都服從左結(jié)合規(guī)則。所有關(guān)系符的優(yōu)先級(jí)都是相同的，而且高于任何布爾算符，低于任何算術(shù)算符，關(guān)系算符不得結(jié)合。表達(dá)式的真、假出口的確定：考慮表達(dá)式 B1 | B2 ，若 B1為真，則立即知道 B

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

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