Simplexmethod及其在數(shù)學(xué)建模中的應(yīng)用

1、線性規(guī)劃理論在數(shù)學(xué)建模中的應(yīng)用前 言 線性規(guī)劃模型是運(yùn)籌學(xué)中的一個(gè)重要分支，其基本解法但出行飯法則是處理運(yùn)籌學(xué)模型的一種重要方法。主要用于研究解決有限資源的最佳分配問題，即如何對(duì)有限的資源做出最佳方式的調(diào)配和最有利的使用，一邊最充分地發(fā)揮資源的效能去獲取最佳經(jīng)濟(jì)效益。從數(shù)學(xué)的角度來說，就是在對(duì)決策變量施加一組線性等式，不等式以及符號(hào)的約束下，求決策變量的線性目標(biāo)函數(shù)的最大化或最小化。與其他的數(shù)學(xué)分支相比，線性規(guī)劃是一個(gè)相當(dāng)年輕有非?；钴S的應(yīng)用數(shù)學(xué)分支。自提出了一般線性規(guī)劃問題求解的方法單純形法之后，線性規(guī)劃在理論上趨向成熟，在應(yīng)用日益廣泛與深入。特別是在電子計(jì)算機(jī)能處理成千上萬(wàn)個(gè)約束條件和決策

2、變量的線性規(guī)劃問題之后,線性規(guī)劃的適用領(lǐng)域更加廣泛了。從解決技術(shù)問題的最優(yōu)化設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃和管理決策等領(lǐng)域都可發(fā)揮重要作用。線性規(guī)劃的廣泛應(yīng)用以及所涉及到的數(shù)學(xué)理論和計(jì)算方法，都引起了專業(yè)人員和學(xué)者們很大的興趣。 在大量閱讀相關(guān)文獻(xiàn)的基礎(chǔ)上，本文就這些問題作了詳盡的綜述。并將這一最優(yōu)化方法運(yùn)用于解決實(shí)際問題，與相關(guān)單位合作完成的兩個(gè)項(xiàng)目中均充分涉及到了上述方法。第1章 線性規(guī)劃概述1、 線性規(guī)劃發(fā)展簡(jiǎn)史作為運(yùn)籌學(xué)的一個(gè)重要分支，線性規(guī)劃問題是最早研究、理論較為完整、應(yīng)用極其廣泛的一門數(shù)學(xué)規(guī)劃學(xué)科。1939年，前蘇聯(lián)科學(xué)家兼經(jīng)濟(jì)學(xué)家康托洛維奇發(fā)飆了生產(chǎn)組織與計(jì)

3、劃中的數(shù)學(xué)方法一書，第一次詳細(xì)的介紹了線性規(guī)劃問題。1947年，美國(guó)貝爾電話公司工程師G.B.Dantzig提出了單純形法，從而實(shí)現(xiàn)性規(guī)劃在理論上趨于成熟，在實(shí)際應(yīng)用中日益廣泛與深入。G.B.Dantzig還對(duì)線性規(guī)劃理論的提煉和算法改進(jìn)做出了卓越的貢獻(xiàn)，在1950年到1960年間，線性規(guī)劃理論得到了進(jìn)一步的發(fā)展和豐富。1975年，瑞典皇家科學(xué)院把經(jīng)濟(jì)學(xué)的諾貝爾獎(jiǎng)授予了L.V.Kantorovic和T.C.Koopmans，以獎(jiǎng)勵(lì)他們對(duì)資源最優(yōu)分配理論的貢獻(xiàn)。1979年，L.G.Kanchian證明了Shor,Judin和Nemirovskii的“橢球法”。這種方法與逐次替代的單純形法是根本不

4、同的，橢圓球法是在一個(gè)多項(xiàng)式的時(shí)間限界內(nèi)找到線性規(guī)劃的一個(gè)最優(yōu)解。遺憾的是橢圓球法在理論上并不能在實(shí)踐應(yīng)用中得以實(shí)現(xiàn)。上世紀(jì)80年代，N.的“投影尺度法”使線性規(guī)劃出現(xiàn)了真正的突破。這種新算法不僅在理論上優(yōu)越于單純Katmarkar形法，而且也顯示出對(duì)求解大規(guī)模實(shí)際問題的巨大潛力。Katmarkar算法不同于單純形法，他是從可行域的內(nèi)部去逼近一個(gè)最優(yōu)解。以內(nèi)點(diǎn)發(fā)已經(jīng)成為人們近幾十年的研究的焦點(diǎn)。1985年，E.Barmes和R.Vanderbei,M.Meketon和B.Freefman重新提出（原來）仿射尺度算法來解標(biāo)準(zhǔn)的線性規(guī)劃問題，并給出了算法的收斂性證明。后來，Adler等人提出了類似

5、的對(duì)偶仿射尺度算法用來解對(duì)偶仿射尺度算法。近二十年，線性規(guī)劃在國(guó)內(nèi)也有了較大的發(fā)展，主要是針對(duì)單純形法和內(nèi)點(diǎn)法的改進(jìn)以及在各個(gè)學(xué)科的交叉研究，各個(gè)領(lǐng)域的具體應(yīng)用。1997年，中科院的楊德莊提出的核心算法，姚侗、何金瞳提出的直接搜索迭代算法，萬(wàn)朝燕，李曉峰等人提出的利用K-T條件和KS函數(shù)來解線性規(guī)劃的方法，彭躍輝等人的原始基線算法，高培旺、范國(guó)兵的外點(diǎn)單純性算法涂為員的優(yōu)面算法，胡鐵松等人應(yīng)用神經(jīng)網(wǎng)絡(luò)求解線性規(guī)劃問題的解等?？傊?，線性規(guī)劃繼單純形法提出經(jīng)歷了幾十年的發(fā)展，理論日益趨于成熟，應(yīng)用日益廣泛，特別是電子計(jì)算機(jī)能處理成千上萬(wàn)個(gè)約束條件和決策變量的線性規(guī)劃問題之后線性規(guī)劃的適用領(lǐng)域更為廣

6、泛，從解決技術(shù)問題的最優(yōu)設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、軍事、經(jīng)濟(jì)計(jì)劃和管理決策等領(lǐng)域也發(fā)揮各自作用。2、 線性規(guī)劃問題的數(shù)學(xué)模型凡滿足以下三個(gè)條件的問題，就叫做線性規(guī)劃問題：(1) 可用一些變量表示問題的待定方案，這些變量的一組定值就代表一個(gè)具體的方案。因此，可將這些變量稱為決策變量，并往往要求它們?yōu)榉秦?fù)的。(2) 存在一定的約束條件，這些約束條件都能用關(guān)于決策變量的線性等式或不等式來表示。(3) 有一個(gè)期望達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))來表示。根據(jù)具體問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化，線性規(guī)劃就是研究并解決上述問題的一種理論和方法。滿足以上三個(gè)條件的數(shù)學(xué)模

7、型稱為線性規(guī)劃的數(shù)學(xué)模型，簡(jiǎn)稱線性規(guī)劃模型。(1) 線性規(guī)劃的一般形式線性規(guī)劃問題的一般形式為：求一維向量，使得 (1.1) (1.2)其中：，(i=1,2,m;j=1,2,n)為已知常數(shù)，式(1.1)稱為目標(biāo)函數(shù)，式(1.2)稱為約束條件，特別呈為非負(fù)約束條件。以上給出的是線性規(guī)劃問題的一般形式。對(duì)于不同的問題而言，目標(biāo)函數(shù)可以是求極大值或求極小值；約束條件可以是線性不等組，或者線性等式組，或者兩者兼而有之，變量可以有非負(fù)限制，也可沒有，為了研究問題的方便，人們給出了下面形式的所謂標(biāo)準(zhǔn)形式。 (二) 線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式為： (1.3)其中要求假設(shè)，否則將方程兩邊同乘以(

8、-1)，將右端化為非負(fù)數(shù)。用矩陣描述線性規(guī)劃得標(biāo)準(zhǔn)形式為其中 ， (1.4)稱A為約束條件的維系數(shù)矩陣，簡(jiǎn)稱為系數(shù)矩陣，b為資源向量，C為價(jià)值向量，X為決策向量。以后，我們提到的標(biāo)準(zhǔn)線性規(guī)劃問題，記為(LP)。(3) 線性規(guī)劃問題的一般理論對(duì)于（1.4）式所示的標(biāo)準(zhǔn)線性規(guī)劃問題(LP)，凡是滿足該問題所有約束條件的向量x，我們就稱之為(LP)的可行解。而使得達(dá)到最小值的可行解，稱之為(LP)的最優(yōu)解，記為；所對(duì)應(yīng)的目標(biāo)函數(shù)值稱之為最優(yōu)值，記為。另外，約束條件A為維矩陣，不妨設(shè)其秩為m，即視其為滿秩矩陣。若B為矩陣A中的一個(gè)m階非奇異子矩陣，則稱B為(LP)的一個(gè)基。構(gòu)成B的每個(gè)列向量均稱之為基

9、向量，而以基向量為系數(shù)的相應(yīng)變量為基變量，其他變量稱為非基變量。在約束條件的各個(gè)約束方程中，令非基變量為0，所得的解稱為基本解。滿足非負(fù)約束的基本解，稱為基本可行解，簡(jiǎn)稱基解，相應(yīng)的基稱為可行基。關(guān)于標(biāo)準(zhǔn)線性規(guī)劃問題(LP)的解，有下面兩個(gè)基本性質(zhì)：1. 若(LP)有可行解，則它也一定有基本可行解。2. 若(LP)有最優(yōu)解，則它也一定有基本可行解是最優(yōu)解。由以上這兩條性質(zhì)，我們可以知道，若想求出(LP)的最優(yōu)解，不必考慮其所有可行解，只需考慮(LP)的滿足非負(fù)約束的基解(即基本可行解)即可。一個(gè)具有m個(gè)獨(dú)立約束方程，n個(gè)決策變量的線性規(guī)劃問題，其基本可行解的數(shù)目最多為個(gè)。這樣，既可縮小考慮問題

10、的范圍，又不會(huì)漏掉要求的解。因此，以后我們求解(LP)時(shí)，只考慮其滿足非負(fù)約束條件的基本可行解。第2章 單純形法概論單純形法的基本思路就是：先找到一個(gè)初始基可行解，如果不是最優(yōu)解，設(shè)法轉(zhuǎn)換到另一個(gè)基本可行解，并使目標(biāo)函數(shù)值不斷減小，直至找到最優(yōu)解為止。1、 單純形方法基本步驟（1） 單純形法的開始-尋找初始基本可行解要求解一個(gè)給定的線性規(guī)劃問題，單純形法是從尋找一個(gè)初始基可行解開始的。確定初始基可行解的一般方法是根據(jù)不同形式的約束條件添加一些變量來獲得初始可行基，在此基礎(chǔ)上利用單純形法的邏輯來求出初始基可行解。文獻(xiàn)【22】中P22-23給出了具體的操作方法。比較常用的初始化方法有兩階段法和大M

11、法【22】。（二）單純形法的停止-最優(yōu)性檢驗(yàn)及解得判別對(duì)線性規(guī)劃問題的求解結(jié)果可能出現(xiàn)唯一最優(yōu)解、無窮多最優(yōu)解、無界解（即無最優(yōu)解）、無可行解四種情況，為此需要建立對(duì)解得判別準(zhǔn)則。（3） 單純形法的迭代-向改進(jìn)方向移動(dòng)所謂向該機(jī)方向移動(dòng)，也就是設(shè)法從已有的基可行解轉(zhuǎn)換到贏一個(gè)基可行解具體做法就是從原可行基中換一個(gè)列向量（要保證線性相關(guān)），得到一個(gè)新的可行基。為了達(dá)到這個(gè)目的，需要確定進(jìn)基變量和離基變量，讓它們相應(yīng)的系數(shù)列向量進(jìn)行對(duì)換，得到一個(gè)新的基可行解，即找到一個(gè)迭代主元進(jìn)行Gauss消元變換。如何確定迭代主元呢？課件文獻(xiàn)【23】。這樣，通過確定初始基可行解，檢驗(yàn)是否為最優(yōu)解，若不是，則設(shè)法

12、轉(zhuǎn)換到另一個(gè)基可行解，并使得目標(biāo)函數(shù)值不斷減小，直至出現(xiàn)以上四種解得情況之一為止。由于一個(gè)給定的線性規(guī)劃問題，其基可行解的數(shù)目總是有限的，若迭代不出現(xiàn)循環(huán)，則最終必可出現(xiàn)以上四種解的情況之一。（4） 計(jì)算步驟綜上，對(duì)于一個(gè)給定的線性規(guī)劃問題，單純形法的計(jì)算步驟如下：SETP1 找出初始可行基，確定初始可行解。SETP2 檢驗(yàn)各非基變量的檢驗(yàn)數(shù)，若0，則已得最優(yōu)解，停止計(jì)算；否則，轉(zhuǎn)SETP3。SETP3 若有某個(gè)對(duì)應(yīng)的的系數(shù)中對(duì)所有 均有，則此問題無最優(yōu)解，停止計(jì)算；否則，轉(zhuǎn)SETP4。SETP4 令，確定為進(jìn)基變量，然后，令確定為離基量；以元素為迭代主元進(jìn)行Gauss消元，可得一個(gè)新的可行基

13、以及相應(yīng)的新的基可行解和檢驗(yàn)數(shù)行，然后轉(zhuǎn)到STEP2。2、 單純形法的進(jìn)一步討論用單純形法解決線性規(guī)劃問題時(shí)，第一步就是要尋找一個(gè)初始可行基。在將線性規(guī)劃問題化為標(biāo)準(zhǔn)型后，如果系數(shù)矩陣中含有單位矩陣，則可以找到一個(gè)初始可行基。但在實(shí)際問題中，并不一定都能直接找到初始可行基，這就需要引入人工變量，用大M法或兩階段法來確定初始可行基。但采用大M法，當(dāng)用計(jì)算機(jī)求解時(shí)，由于每一臺(tái)計(jì)算機(jī)都有一定字長(zhǎng)的限制，于是只能用很大的數(shù)來代替充分大的M，這樣就可能造成計(jì)算上的錯(cuò)誤。本文就從引入人工變量和不引入人工變量?jī)蓚€(gè)方面進(jìn)行兩階段法的討論。（1） 引入人工變量的方法在線性規(guī)劃問題中引入人工變量，把問題變?yōu)榧s束方

14、程組的系數(shù)矩陣中含有單位矩陣，用以作為人造基，然后按單純性方法進(jìn)行換基迭代，求得最優(yōu)解或判定無可行解。1. 線性規(guī)劃問題中的兩階段法在利用線性規(guī)劃的單純形法求解時(shí)，首先，要在線性規(guī)劃問題中引入人工變量，把問題變?yōu)榧s束方程組的系數(shù)矩陣中含有單位陣。用以作為人造基，然后按單純性方法進(jìn)行換基迭代，求得最優(yōu)解或判定無最優(yōu)解，這種方法稱為兩階段法。第一階段是判斷原線性規(guī)劃問題是否存在基本可行解。一般地 （I）上式稱為原問題。在（I）中加入人工變量，構(gòu)造輔助問題（II）注意到，在（I）中加入的人工變量的個(gè)數(shù)m正好是（I）問題中約束方程組中含有方程的個(gè)數(shù)。第二階段是由第一階段最后求得原問題（I）的一個(gè)可行基

15、開始，運(yùn)用單純形法，求得原問題（I）的最優(yōu)解或判定原問題（I）無可行解。2. 線性規(guī)劃問題中兩階段飯的簡(jiǎn)便算法有些線性規(guī)劃問題，引進(jìn)松弛變量化成標(biāo)準(zhǔn)型后，約束條件方程組的系數(shù)矩陣并不含m階單位矩陣，這樣就給單純形解法的換基迭代帶來了困難。線性規(guī)劃在利用兩階段法階這類問題時(shí)，尤其是一些具體的實(shí)際問題，對(duì)于加入的人工變量 應(yīng)該根據(jù)問題盡可能的少，使人工變量的個(gè)數(shù)小于（或等于）m。本文就線性規(guī)劃問題的原問題（I）在加入人工變量y中，如何根據(jù)所給問題盡可能的少引入人工變量，通過例子來說明線性規(guī)劃問題兩階段法的簡(jiǎn)便計(jì)算法。需要注意的是盡可能少引入人工變量y的同時(shí)，保證使問題（II）的約束條件方程組的系數(shù)

16、矩陣中有一個(gè)可行基，這就要根據(jù)實(shí)際問題，靈活運(yùn)用兩階段法，看下面的例子。解線性規(guī)劃問題：引入松弛變量，將問題化為標(biāo)準(zhǔn)形式：?jiǎn)栴}（I）沒有一個(gè)現(xiàn)成的可行基，因此要用兩階段法解，引進(jìn)下面的輔助問題。一般的問題（I）中約束條件的方程組含有3個(gè)方程就要引入3個(gè)人工變量，而人工變量越多，線性規(guī)劃問題中的變量就越多，計(jì)算量就越大。因此，我們根據(jù)（I）中的具體問題盡可能少的引入人工變量y。再此問題中注意到第一個(gè)方程中松弛變量前的系數(shù)為+1，且其它兩個(gè)方程中不含有，為使技術(shù)簡(jiǎn)單，只引入兩個(gè)人工變量、。 輔助問題（II）有一現(xiàn)成的可行基,基變量為和，對(duì)應(yīng)于基的單純性表為： 10 0 0 0 1 2 2 0 -1

17、0 1 0 0 2 1 1 0 09 0 0 0 2 3 -1 1 04 0 1 0 0 2 1 0 -16 0 0 1 1 0 1 0 0檢驗(yàn)數(shù)有正數(shù)，進(jìn)行換基迭代，得對(duì)應(yīng)于新基的單純性表如下： 0 0 0 1 2 2 0 -1-9 1 0 0 2 1 1 0 0 0 0 0 2 3 -1 1 04 0 1 0 0 2 1 0 -1 0 0 1 1 0 1 0 0檢驗(yàn)數(shù)仍有正數(shù)，繼續(xù)換基迭代，得對(duì)應(yīng)于新基的單純性表。 0 0 0 0 -5 1 1 0 0 0 3 -1 -1 0 0 1 0 2 0 0 0 1 0 0 1 0 0 檢驗(yàn)數(shù)仍有正數(shù)，繼續(xù)換基迭代，得對(duì)應(yīng)于新基的單純形表。 0 0

18、 -1 -1 0 0 0 0 0-11 1 0 0 0 0 0 04 0 0 1 0 1 0 0 1 0 2 0 0 0 1 單純表中檢驗(yàn)數(shù)已全非正，所以基為輔助問題（II）的最優(yōu)基，minZ=0，同時(shí)基的基變量無人工變量，所以為問題（I）的可行基，對(duì)應(yīng)的單純形表為： -11 0 0 0 04 1 0 0 1 0 1 0 2 0 0 1 檢驗(yàn)數(shù)已全非正，故為問題（I）的最優(yōu)基，對(duì)應(yīng)的最優(yōu)解為：目標(biāo)函數(shù)最小值為。所以原線性規(guī)劃問題的最優(yōu)解為，目標(biāo)函數(shù)最大值為。由上面的解題過程，我們看到對(duì)于線性規(guī)劃問題約束方程組的系數(shù)矩陣中不含有m階單位矩陣，求初始可行基的方法。問題化為（I）以后，注意約束條件的

19、結(jié)構(gòu)，盡可能少的引入人工變量y，方法靈活一些，可使線性規(guī)劃問題中兩階段法的解題過程簡(jiǎn)單明了。（2） 不引入人工變量的方法采用兩階段法，要把原線性規(guī)劃問題化為兩個(gè)線性規(guī)劃問題來求解，這勢(shì)必會(huì)增大計(jì)算量，使得計(jì)算過程繁瑣、冗長(zhǎng)，并且計(jì)算機(jī)的存儲(chǔ)量也隨之增加。我們?cè)O(shè)想，對(duì)無現(xiàn)成可行基的線性規(guī)劃問題可否不引入人工變量，而像用初等變換求解線性方程組那樣直接找出原問題的可行基呢？答案是肯定的。事實(shí)上，一個(gè)基可行解就是約束方程組的一個(gè)自由變量取零時(shí)的非負(fù)特解。1. 對(duì)（1.3）線性規(guī)劃標(biāo)準(zhǔn)型，由文獻(xiàn)【23】的分析知，可直接通過對(duì)約束條件的系數(shù)矩陣A進(jìn)行一系列初等變換，變?yōu)楹衜階的單位陣的形式?；谶@一思想

20、，在文獻(xiàn)【22】中作者在求解線性規(guī)劃問題時(shí)，通過對(duì)其約束條件的系數(shù)矩陣和增廣矩陣秩的討論，得出原問題的一個(gè)可行基，進(jìn)而得出基變量，然后進(jìn)過一系列代換，最終列出單純性表，利用常規(guī)單純形法求出原問題的最優(yōu)解。這一思想是值得我們借鑒的，但作者的求結(jié)果稱軍事通過立體來說明的，并沒有給出明確的算法，且列出單純性表前的一系列準(zhǔn)備工作過于零散和繁瑣。文獻(xiàn)【24】對(duì)其求解過程作了進(jìn)一步的改進(jìn)，所有的計(jì)算均統(tǒng)一在單純性表下完成，且給出了明確的算法。2. 改進(jìn)的線性規(guī)劃兩階段算法通過以上的分析可將原算法改為下列的簡(jiǎn)化算法：(1)，若，且，此時(shí)第行為矛盾方程，原問題無可行解，停止計(jì)算。若，且，則第行乘以（-1）后轉(zhuǎn)

21、入，否則直接轉(zhuǎn)（3）。(2) 從第一行開始，考慮所有的項(xiàng)，選取其中一項(xiàng)，以其中對(duì)應(yīng)的變量為基變量，確定出主列為第列。(3) 若有幾個(gè)同時(shí)達(dá)到最小，選其中下標(biāo)最小的為主行。(4)以為主元進(jìn)行迭代，得表2。（5）以此類推，對(duì)其他各行重(2)(5)步，一般重復(fù)m次就可得到一個(gè)明顯的可行基。（6）按照單純形法計(jì)算出檢驗(yàn)數(shù)和目標(biāo)函數(shù)值CBb此后完全與常規(guī)單純形法相同，通過對(duì)檢驗(yàn)數(shù)正負(fù)的考察來判斷是否為最優(yōu)解。若是，停止計(jì)算。若否，確定出進(jìn)基及出基變量，進(jìn)行迭代，直至結(jié)束。例：用改進(jìn)的簡(jiǎn)化算法求解maxz-3x1+x3 j解：化為標(biāo)準(zhǔn)型后列出下列迭代表格，見表。表用改進(jìn)單純形法求解例題的迭代表cj-301

22、00CBXBbx1x2x3x4x541111041-21-10-1-903100-j-301000x441111041-21-10-119031003j-301000x433021110x21-21-10-1-6604031j-301000x41100x2301-9-3x10000-21-003111x3010x2-10-3x10000-21-00-在表中，所有的檢驗(yàn)數(shù) 0(j=1,2,3,4,5）故已得到原問題的最優(yōu)解X=(0, )r ，最優(yōu)值z(mì)=.比較線性規(guī)劃兩階段法和本文的改進(jìn)算法，很容易發(fā)現(xiàn)后者有以下優(yōu)點(diǎn)：（）避免了引進(jìn)輔助問題造成的運(yùn)算量增大，可明顯提高計(jì)算效率。（）可直觀地判斷線性

23、規(guī)劃問題是否有可行基，若有才進(jìn)行換基迭代，克服了引進(jìn)輔助問題的盲目性。（）可以簡(jiǎn)化計(jì)算程序，便于上機(jī)操作。并且與文獻(xiàn)相比，本文的優(yōu)勢(shì)也是顯而易見的，它更加簡(jiǎn)單直觀，易于操作，而且將求可行基、換基迭代的過程統(tǒng)一于一張表下進(jìn)行，解的情況一目了然。三、單純形法在計(jì)算機(jī)上的實(shí)現(xiàn)對(duì)于以上的單純形法的基本原理及解線性規(guī)劃問題的主要步驟，當(dāng)變量個(gè)數(shù)及約束個(gè)數(shù)較大時(shí)，用手算是不可能的?，F(xiàn)在已有了不少用來求解線性規(guī)劃問題的數(shù)學(xué)軟件。如LINGO就是一種專門用來求解數(shù)學(xué)規(guī)劃的軟件包，其求解線性規(guī)劃的過程是采用單純形法。LINGO軟件可以用來求解線性規(guī)劃、整數(shù)規(guī)劃和二次規(guī)劃，具體求解過程可以參照文獻(xiàn)23。第三章單純

24、形法在數(shù)學(xué)建模中的應(yīng)用在農(nóng)業(yè)土地結(jié)構(gòu)優(yōu)化研究中的應(yīng)用虎林縣位于黑龍江省東部的完達(dá)山南麓，地理坐標(biāo)處于北緯45°23至46°36，東經(jīng)132°11至139°56之間。以鳥蘇里江為界與俄羅斯聯(lián)邦隔水相望。占地面積平方公里，是全國(guó)面積的千分之一，人口萬(wàn)。土地作為人類生存最基本的自然資源，它與人類的生息、延續(xù)密切相關(guān)。虎林縣由于土地供需日趨嚴(yán)重，為了合理的利用和珍惜每一寸土地，促進(jìn)土地結(jié)構(gòu)的優(yōu)化利用，發(fā)展本縣經(jīng)濟(jì)，保護(hù)生態(tài)環(huán)境，因此，運(yùn)用線性規(guī)劃對(duì)虎林縣土地結(jié)構(gòu)進(jìn)行優(yōu)化研究，并提出土地結(jié)構(gòu)調(diào)整的方案，對(duì)合理利用土地和充分挖掘土地生產(chǎn)潛力具有重大的現(xiàn)實(shí)和深遠(yuǎn)的戰(zhàn)略

25、意義。（一）農(nóng)業(yè)土地結(jié)構(gòu)優(yōu)化的原則對(duì)虎林的土地結(jié)構(gòu)進(jìn)行優(yōu)化研究時(shí)，首先應(yīng)堅(jiān)持因地制宣、因時(shí)制宜的原則，益農(nóng)則農(nóng)，宣林則林，宜牧則牧，按照自然規(guī)律辦事，充分體現(xiàn)該縣土地利用結(jié)構(gòu)的地域差異。其次，應(yīng)堅(jiān)持經(jīng)濟(jì)效益的原則，用最小的投入，或最大的收益，充分發(fā)揮該縣土地生產(chǎn)優(yōu)勢(shì)；。第三應(yīng)堅(jiān)持保護(hù)生態(tài)環(huán)境的原剛防止土地污染，裨益當(dāng)代，造福子孫。具體調(diào)整時(shí)，要把人口增長(zhǎng)、經(jīng)濟(jì)發(fā)展與土地資源的數(shù)量、質(zhì)量結(jié)合起來，充分挖掘各類土地的生產(chǎn)潛力，吧綜合開發(fā)利用和區(qū)域整治保護(hù)結(jié)合起來，協(xié)調(diào)好人地關(guān)系，建立起不同地域不同層次的復(fù)合宏觀用地結(jié)構(gòu)來。（二）建立農(nóng)業(yè)土地結(jié)構(gòu)優(yōu)化的數(shù)學(xué)模型模型的一般形式本縣采用的線性規(guī)劃模型是：

26、求在滿足約束條件下使目標(biāo)函數(shù)取得最大時(shí)的一系列變量（其中有些變量只能取整數(shù)），因此，模型的一般形式為：maxZ=cjxj設(shè)置變量由于虎林縣地面溝壑縱橫，支離破碎，相對(duì)高差大，降水少麗集中，往往產(chǎn)生很大的坡面徑流，造成嚴(yán)重的水土流失。因此，在土地利用上應(yīng)堅(jiān)持與生物措施相結(jié)合，治坡與治溝相結(jié)合，做到梯田、川地、灘地同步，喬木、灌木、草地齊進(jìn)。根據(jù)上述要求，設(shè)置如下變量：X1、X2、X3、X4丘為各等地面積；X5、X6為森林、牧草地面積；X1、X2、X3分別為規(guī)劃期內(nèi)，二等地升一等地（靠興修水利工程）、三等地升二等地（靠修梯田）、四等地升三等地（靠改良土壤）面積；X4為四等地退林地面積：X5為退牧草

27、地面積；X6為牧草地造林面積。規(guī)劃期內(nèi)線性規(guī)劃模型2010年規(guī)劃期模型（）各等地土地的約束條件在虎林縣土地評(píng)價(jià)中，已知該縣現(xiàn)有總耕地55萬(wàn)畝，其中一等地面積15.3萬(wàn)畝，二等地面積20.2萬(wàn)畝，三等地面積11.5萬(wàn)畝，四等地面積萬(wàn)畝，林地面積337.9萬(wàn)畝，牧草地面積萬(wàn)畝。由此可得出下列方程式；一等地：X1-X1，二等地：X2-X2+X1，三等地：X3-X3+X2，四等地：X43+X4+X5，森林地：X5一X4一X6，牧草地：6一X5X6。（）投資約束條件在2010年前的規(guī)劃期內(nèi)，考慮到虎林縣的具體情況，靠興修各種水利設(shè)施，來增加水地面積，新增每萬(wàn)畝水地需要投資萬(wàn)元；大搞平整土地，修建梯田，新

28、增每萬(wàn)宙梯田需投資萬(wàn)元；靠改良土壤，增施有機(jī)肥，新增每畝需投資萬(wàn)元，靠采取各種措施，封山育林，新增每萬(wàn)畝森林地需要投資萬(wàn)元；對(duì)于改良現(xiàn)有牧草地，進(jìn)行人工種草，新增每萬(wàn)畝牧草地需投資萬(wàn)元；在自然條件優(yōu)越的牧草地上進(jìn)行植樹造林，新增每萬(wàn)畝森林需要投資10萬(wàn)元，為了能改變虎林縣的舊貌，在規(guī)劃期內(nèi)，該縣可以自籌資金和國(guó)家支援資金大約為萬(wàn)元。因此，虎林縣規(guī)劃期內(nèi)的投資約束方程是（其中彈性指標(biāo)為）：0.6X1+0.45X2+0.23+0.1X4+0.25X5+0.1X610。（）勞動(dòng)力約束條件該縣在規(guī)劃期內(nèi)擴(kuò)大水地每萬(wàn)母需投入15萬(wàn)個(gè)工，修筑梯田每萬(wàn)畝需投入萬(wàn)個(gè)工，改良土壤每萬(wàn)畝需投入萬(wàn)個(gè)工，造林每萬(wàn)畝需

29、投入萬(wàn)個(gè)工，種草每萬(wàn)畝需投入萬(wàn)個(gè)工，根據(jù)虎林縣實(shí)際情況，預(yù)計(jì)年該縣農(nóng)村勞動(dòng)力可達(dá)萬(wàn)人，可提供勞動(dòng)力萬(wàn)個(gè)（按每年個(gè)天計(jì)），除牧、副業(yè)尉工外，年大約可提供農(nóng)、林、水土保持用工百萬(wàn)一百萬(wàn)個(gè)工，由此可以建立起農(nóng)田需要投工與可能提供投工的方程式來（彈性指標(biāo)為）：0.15X1+0.2X2+0.05X3+0.05X4+0.04X5+0.05X6140.68。（）糧食需求約束條件根據(jù)虎林縣人口規(guī)劃得知，該縣年人口可達(dá)到萬(wàn)人，用該人口數(shù)字乘以全國(guó)人均消費(fèi)標(biāo)準(zhǔn)（糧食標(biāo)準(zhǔn)），就可得出虎林縣年時(shí)對(duì)糧食總需求為萬(wàn)斤，即一萬(wàn)噸。在充分挖掘本縣土地生產(chǎn)潛力的基礎(chǔ)上，預(yù)計(jì)該縣到年，一等地單產(chǎn)可達(dá)斤畝，將它們換算成為萬(wàn)噸萬(wàn)畝為

30、單位。因此有（彈性指標(biāo)0.72）方程：0.5X1+0.4X2+0.276X3+0.175X410.1（）電力供應(yīng)約束條件虎林縣一等地中包括水澆地的用電量比較大，每萬(wàn)畝需用電萬(wàn)度，二等地需用電萬(wàn)度，三等地需用電萬(wàn)度，四等地需用店萬(wàn)度。根據(jù)虎林縣電力工業(yè)局規(guī)劃，年度國(guó)家可提供5.455.75百萬(wàn)度。因此可以獲得需電與用電之間的平衡方程式（彈性指標(biāo)0.3）：0.18X1+0.08X2+0.05X3+0.035.45（）各種災(zāi)年最低限量約束條件危害本縣農(nóng)業(yè)生產(chǎn)的主要自然災(zāi)害是春旱、夏秋旱、夏澇和霜凍，它們可以使農(nóng)作物分別減產(chǎn)、。按照每年人均最低需要量一公斤計(jì)，全縣萬(wàn)人大約需要糧食一萬(wàn)噸。為了保證出現(xiàn)自

31、然災(zāi)害的情況下，滿足該縣最低需要量，從而避免出現(xiàn)不必要的風(fēng)險(xiǎn)，可以建立起災(zāi)年糧食生產(chǎn)和需求量之間的平衡方程（彈性指標(biāo)為0.725）：春 旱：0.375X1+0.3X2+0.206X3+0.131X45.8，夏秋旱：0.3X1+0.24X2+0.166X3+0.105X45.8，夏秋澇：0.275X1+0.22X2+0.152X3+0.096X45.8霜凍：0.35X1+0.28X2+0.193X3+0.123X45.8（）有機(jī)肥施用約束條件根據(jù)虎林縣統(tǒng)計(jì)資料獲知，該縣耕地中一等地每萬(wàn)畝需施用有機(jī)肥料萬(wàn)噸，二等地每萬(wàn)畝需施有機(jī)肥萬(wàn)噸，三等地每萬(wàn)畝需施有機(jī)肥萬(wàn)噸，四等地每萬(wàn)畝需施有機(jī)肥萬(wàn)噸，預(yù)計(jì)年

32、可獲有機(jī)肥料噸，至少可得萬(wàn)噸，因此有（彈性指標(biāo)為2.0）：4.8X1+4X2+3.2X3+2.4X4212.8（）生態(tài)環(huán)境約束條件根據(jù)虎林農(nóng)業(yè)、林業(yè)、畜牧業(yè)發(fā)展規(guī)劃可知，到年該縣的森林、草地、果園及四旁綠化等面積將不會(huì)少于萬(wàn)畝這一約束條件，我們可以建立起如下方程式：5655。（）目標(biāo)函數(shù)根據(jù)虎林縣的自然環(huán)境條件、勞動(dòng)力生產(chǎn)水平和機(jī)械化程度，預(yù)計(jì)到年各等林地及牧草每萬(wàn)畝凈增產(chǎn)分別為萬(wàn)元、萬(wàn)元、萬(wàn)元、萬(wàn)元、萬(wàn)元和萬(wàn)元。目標(biāo)函數(shù)應(yīng)該是規(guī)劃年內(nèi)諍增產(chǎn)值的極大值，這個(gè)凈增產(chǎn)值等于規(guī)劃年內(nèi)各等土地凈增產(chǎn)值扣除規(guī)劃期內(nèi)各項(xiàng)投資額的回收值。因此，可以建立起如下方程式（資本回收?。篗axZ=2781+1842

33、+1583+1334+315+2906-0.6X1-0.45X2-0.2X3-0.1X4-0.025X5-0.1X6。虎林縣年規(guī)劃期模型在年規(guī)劃期預(yù)測(cè)結(jié)果的基礎(chǔ)上，綜合考慮所設(shè)置各變量系數(shù)與常數(shù)項(xiàng)到年的變化情況，可以建立如下規(guī)劃模型：一等地：X1-X117.06，二等地：X2-X2+X122.64，三等地：X3-X3+X28，四等地：X43+X4+X55.6，林地：X5-X4-X639，草地：X6-X5+X116，投資：0.6X1+0.45X2+0.2X3+0.1X4+0.025X5+0.1X612，勞動(dòng)力：0.15X1+0.2X2+0.05X3+0.05X4+0.04X5+0.05X668.

34、3，糧食：0.5X1+0.4X2+0.276X3+0.175X412.5，電力：0.18X1+0.08X2+0.05X3+0.03X45.62，春旱：0.375X1+0.3X2+0.206X3+0.131X46.43，夏秋旱：0.3X1+0.24X2+0.166X3+0.105X46.43，夏秋澇：0.275X1+0.22X2+0.152X3+0.096X46.43，霜凍：0.35X1+0.28X2+0.193X3+0.123X46.43，有機(jī)肥料：4.8X1+4X2+3.2X3+2.4X4214.4，生態(tài)：X5+X656.4.目標(biāo)函數(shù)值：Max=293X1+192X2+168X3+139X4

35、+41X5+295X6-0.6X1-0.45X2-0.2X3-0.1X4-0.025X5-0.1X6。（三）計(jì)算結(jié)果和分析利用計(jì)算機(jī)求的結(jié)果（見表）并對(duì)計(jì)算結(jié)果進(jìn)行綜合分析與評(píng)價(jià)。為了能充分的說明本規(guī)劃期模型的可靠性及科學(xué)性，現(xiàn)與2004年對(duì)比表如下：200420102015一等地面積15.317.0818二等地面積22.6424.1三等地面積11.588.1四等地面積85.63.7由二等地升為一等地面積1.780.94由三等地升為二等地面積4.22.4由四等地升為三等地面積0.70.5由四等地退林地面積1.00.9由四等地退草地面積0.70.5由牧草地造林面積0.40.1森林地面積37.93

36、940牧草地面積15.41616.4凈增產(chǎn)值1352016763.0217916.44本規(guī)劃模型是在滿足虎林縣各項(xiàng)約束條件下來獲得取提高土地生產(chǎn)潛力，達(dá)到最大生態(tài)效益和經(jīng)濟(jì)效益。在各規(guī)劃期末，該縣一等地面積將分別由2004年的15.3萬(wàn)畝增至17.06萬(wàn)畝和18萬(wàn)畝；二等地面積將分別由2004年的11.5萬(wàn)畝減至8萬(wàn)畝和6.1萬(wàn)畝。這樣，三等地逐漸被一、二等地所取代，這不僅有利于充分發(fā)揮虎林縣土地生產(chǎn)潛力，而且還可以為水土保持工作創(chuàng)造一個(gè)有益條件。四等地面積將分別由2004年的8萬(wàn)畝減至5.6萬(wàn)畝和3.7萬(wàn)畝，該類土地由于自然條件差，多分布于陡坡和急陡坡上，為了能珍惜每寸土地，使得土地的效益盡

37、可能地發(fā)揮出來，我們將此類地的一部分改造為三等地，一部分進(jìn)行造林綠化，另一部分為牧草地，為發(fā)展畜牧業(yè)提供草場(chǎng)。森林面積將由2004年的37.9萬(wàn)畝增至40萬(wàn)畝；草地面積將分別由2004年的15.4萬(wàn)畝分別增至16萬(wàn)畝和16.4萬(wàn)畝。植被覆蓋率將由2004年的30.6%增至31.8%和32.4%，水土流失面積將會(huì)有明顯的減少。因亂墾濫伐造成的土地惡性生態(tài)循環(huán)也會(huì)逐步向良性循環(huán)過渡，農(nóng)業(yè)生產(chǎn)也會(huì)逐步向穩(wěn)產(chǎn)、高產(chǎn)方向發(fā)展。如果這一規(guī)劃方案能夠付諸于實(shí)施，該縣的土地資源凈增值將會(huì)從2004年的1350萬(wàn)元提高到2010年的16763.02萬(wàn)元和2015年的17916.44萬(wàn)元。此時(shí)，虎林縣的人民將會(huì)過

38、上豐衣足食、安居樂業(yè)的生活，農(nóng)村的經(jīng)濟(jì)狀況及農(nóng)村人口人均收入就可以達(dá)到小康水平。 參考文獻(xiàn)1L.V.Kantorovick.Mathematicalm ethods ofo rganizing and planning production.Publication House of the Leningrad state unibesity,Lenningrad,1993.2G:Bdantzig.Linear programing and Extensions,Princeton university press,Princeton,NewJerey,1996,126.3L.G.K hachi

39、an.Apolynomiala lgorithm in linear programming.Sovier Mathematics Doklady,1979,20:191-194.4N.Karmar.A new polynomial time algorithm for linear programming.Proceeding of the 16thAnnual ACM symposium on the Theory of computing,1984,302-311.5N.Karmar.A new polynomial time algorithm for linear binatoria

40、l,1984,4:373-395.6I.Adler,N.Karmar.An implementation of Karmas algorithm for linear programming.Mathematical,1989,44:297-355.7E.R.Varnes.A vatiation of Karmarkars algorithm for solving linear programming.Mathematical programming.1986,36:174-182.8R.V anderbei,M.S.Meketon,and B.A.Freedman.A modification of karmarkars linear programming algorithm.Algorithmica.1986,1:395-407.9I.Adler,N.Karmarkar,M.G.C.Re