第八章 地理系統(tǒng)線性規(guī)劃

第八章地理系統(tǒng)的線性規(guī)劃

(LinerProgramming，LP)

線性規(guī)劃是運籌學中發(fā)展較快、應用較廣和比較成熟的一個分支。它在實際應用中日益廣泛與深入,已經(jīng)被廣泛地應用到工業(yè)、農(nóng)業(yè)、商業(yè)與交通運輸規(guī)劃，工程技術的優(yōu)化設計，以及企業(yè)管理等各個領域。在地理學領域，線性規(guī)劃，作為傳統(tǒng)的計量地理學方法之一，是解決有關規(guī)劃、決策和系統(tǒng)優(yōu)化問題的重要手段。線性規(guī)劃的數(shù)學模型線性規(guī)劃的標準形式及方法線性規(guī)劃的解及其性質線性規(guī)劃問題的求解方法——圖解法線性規(guī)劃問題的求解方法——單純形法應用實例:農(nóng)場種植計劃模型

（一）線性規(guī)劃模型之實例線性規(guī)劃研究的兩類問題：某項任務確定后，如何統(tǒng)籌安排，以最少的人力、物力和財力去完成該項任務；面對一定數(shù)量的人力、物力和財力資源，如何安排使用，使得完成的任務最多。它們都屬于最優(yōu)規(guī)劃的范疇。以下為一些實例。一、線性規(guī)劃的數(shù)學模型合理運輸問題設有兩個煤礦A1，A2，其最少產(chǎn)煤量分別為23萬噸和27萬噸，他們的產(chǎn)煤量應充分供保證應B1,B2,B3三個城市的需求，這三個城市的需煤量最少分別為17萬噸、18萬噸和15萬噸，而從兩個煤礦到各個城市的運費見運費表。問應如何合理調(diào)運才能使總運費最省？

城市煤礦B1B2B3發(fā)量A1X11X12X1323A2X21X22X2327收量17181550

城市煤礦B1B2B3A1506070A260110160運煤量表運費表1.運輸問題假設某種物資（譬如煤炭、鋼鐵、石油等）有m個產(chǎn)地，n個銷地。第i產(chǎn)地的產(chǎn)量為ai（i=1，2，…，m），第j

銷地的需求量為bj(j=1,2，…，n)，它們滿足產(chǎn)銷平衡條件。如果產(chǎn)地i到銷地j的單位物資的運費為Cij，要使總運費達到最小，可這樣安排物資的調(diào)運計劃：

設xij表示由產(chǎn)地i供給銷地j的物資數(shù)量，則上述問題可以表述為：

求一組實值變量xij(i=1，2，…，m；j=1，2，…，n)，使其滿足

而且使

資源合理利用問題某工廠以銅、電力和勞動日為主要原料生產(chǎn)A、B，現(xiàn)有資源數(shù)、生產(chǎn)每單位產(chǎn)品所需要原料數(shù)以及每單位產(chǎn)品可得利潤數(shù)如下表所示。單位產(chǎn)品所需原料A(公斤)B（公斤）現(xiàn)有資源銅（噸）94360電力（千瓦）45200勞動日（個）310300單位利潤（千瓦）7122.資源利用問題

假設某地區(qū)擁有m種資源，其中，第i種資源在規(guī)劃期內(nèi)的限額為bi(i=1，2，…，m)。這m種資源可用來生產(chǎn)n種產(chǎn)品，其中，生產(chǎn)單位數(shù)量的第j種產(chǎn)品需要消耗的第i種資源的數(shù)量為aij(i=1，2，…，m；j=1,2,…,n)，第j種產(chǎn)品的單價為cj(j=1，2，…，n)。試問如何安排這幾種產(chǎn)品的生產(chǎn)計劃，才能使規(guī)劃期內(nèi)資源利用的總產(chǎn)值達到最大?

設第j種產(chǎn)品的生產(chǎn)數(shù)量為xj(j=1，2，…，n)，則上述資源問題就是：

求一組實數(shù)變量xj(j=1，2，…，n)，使其滿足

問題1.如何下料最節(jié)省?鋼管下料原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標準是什么？按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？合理切割模式2.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1兩種標準1.原料鋼管剩余總余量最小xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標1（總余量）模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015整數(shù)約束：

xi為整數(shù)目標1（總余量）按模式2切割12根,按模式5切割15根，余料27米

最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27xi為整數(shù)鋼管下料(問題1)以上兩個模型均是一般整數(shù)線性規(guī)劃

目標2（總根數(shù)）鋼管下料問題1約束條件不變xi為整數(shù)當余料沒有用處時，通常以總根數(shù)最少為目標合理下料問題

用某種原材料切割零件A1，A2,…,Am的毛坯，現(xiàn)已設計出在一塊原材料上有B1，B2，…，Bn種不同的下料方式，如用Bj下料方式可得Ai種零件aij個，設Ai種零件的需要量為bi個。試問應該怎樣組織下料活動，才能使得既滿足需要，又節(jié)約原材料？

設采用Bj方式下料的原材料數(shù)為xj，則上述問題可表示為：

求一組整數(shù)變量xj(j=1，2，…，n)，使得

（二）線性規(guī)劃的數(shù)學模型

以上例子表明，線性規(guī)劃問題具有以下特征：①每一個問題都用一組未知變量（x1，x2，…，xn）表示某一規(guī)劃方案，其一組定值代表一個具體的方案，而且通常要求這些未知變量的取值是非負的。②每一個問題的組成部分：一是目標函數(shù)，按照研究問題的不同，常常要求目標函數(shù)取最大或最小值；二是約束條件，它定義了一種求解范圍，使問題的解必須在這一范圍之內(nèi)。③每一個問題的目標函數(shù)和約束條件都是線性的。

由此可以抽象出線性規(guī)劃問題的數(shù)學模型，一般形式為：在線性約束條件

以及非負約束條件

xj≥0（j=1，2，…，n）下，求一組未知變量xj

(j=1，2，…，n)的值，使

采用矩陣形式可描述為：在約束條件

AX≤(≥，＝)b

X≥0下，求未知向量，使得Z=CX→max(min)

其中

二、線性規(guī)劃的標準形式及方法

(一）線性規(guī)劃的標準形式

在討論與計算時，需要將線性規(guī)劃問題的數(shù)學模型轉化為標準形式，即在約束條件xj≥0（j=1，2，…，n）

下，求一組未知變量xj（j=1，2，…，n）的值，使其縮寫形式為：在約束條件

x≥0（j=1，2，…，n）

下，求一組未知變量（j

=1，2，…，n）的值，使得

常記為如下更為緊湊的形式

或（二）化為標準形式的方法

具體的線性規(guī)劃問題，需要對目標函數(shù)或約束條件進行轉換，化為標準形式。目標函數(shù)化為標準形式的方法

如果其線性規(guī)劃問題的目標函數(shù)為

minZ

=CX

顯然有minZ=max(-Z)=max

Z′

則目標函數(shù)的標準形式為max

Zˊ=-CX約束方程化為標準形式的方法

若第k個約束方程為不等式，即

引入松弛變量,K個方程改寫為則目標函數(shù)標準形式為三、線性規(guī)劃的解及其性質

(一)線性規(guī)劃的解

可行解與最優(yōu)解滿足約束條件（即滿足線性約束和非負約束）的一組變量為可行解。所有可行解組成的集合稱為可行域。

使目標函數(shù)最大或最小化的可行解稱為最優(yōu)解。

基本解與基本可行解

在線性規(guī)劃問題中，將約束方程組的m×n階矩陣A寫成由n個列向量組成的分塊矩陣

如果B是A中的一個階的非奇異子陣，則稱B為該線性規(guī)劃問題的一個基。不失一般性，不妨設則稱為基向量，與基向量相對應的向量為基變量，而其余的變量為非基變量。

如果是方程組的解,則就是方程組的一個解，它稱之為對應于基B的基本解，簡稱基解。滿足非負約束條件的基本解，稱為基本可行解。對應于基本可行解的基，稱為可行基。

線性規(guī)劃問題的以上幾個解的關系，可用下圖來描述：

(二)線性規(guī)劃解的性質

凸集和頂點

①凸集：若連接n維點集S中的任意兩點X(1)和X(2)之間的線段仍在S中，則S為凸集。②頂點：若凸集S中的點X(0)不能成為S中任何線段的內(nèi)點，則稱X(0)為S的頂點或極點。

線性規(guī)劃解的性質

①線性規(guī)劃問題的可行解集（可行域）為凸集。

②可行解集S中的點X是頂點的充要條件是基本可行解。

③若可行解集有界，則線性規(guī)劃問題的最優(yōu)值一定可以在其頂點上達到。

因此線性規(guī)劃的最優(yōu)解只需從其可行解集的有限個頂點中去尋找。四、線性規(guī)劃問題的求解方法——圖解法

線性規(guī)劃的圖解法(解的幾何表示)：對于只有兩個決策變量的線性規(guī)劃問題，可以二維直角坐標平面上作圖表示線性規(guī)劃問題的有關概念，并求解。一般的2維線性規(guī)劃問題Max(Min)z=c1x1

+c2x2s.t.a11x1+a12x2≤(=,≥)b1

a21x1+a22x2≤(=,≥)b2

...am1x1+am2x2

≤(=,≥)bm

x1，x2≥0

圖解法求解線性規(guī)劃問題的步驟如下：(1)建立直角坐標系：分別取決策變量x1,x2

為坐標向量。

圖解法求解2維線性規(guī)劃（2）繪制可行域：對每個約束（包括非負約束）條件，作出其約束半平面（不等式）或約束直線（等式）。各半平面與直線交出來的區(qū)域若存在，其中的點為此線性規(guī)劃的可行解。稱這個區(qū)域為可行集或可行域。然后進行下步。否則若交為空，那么該線性規(guī)劃問題無可行解。圖解法求解2維線性規(guī)劃

（3）繪制目標函數(shù)等值線，并移動求解：目標函數(shù)隨著取值不同，為一族相互平行的直線。首先，任意給定目標函數(shù)一個值，可作出一條目標函數(shù)的等值線（直線）；然后，確定該直線平移使函數(shù)值增加的方向(直線的法方向)；最后，依照目標的要求平移此直線。圖解法求解2維線性規(guī)劃(4)結果若目標函數(shù)等值線能夠移動到既與可行域有交點又達到最優(yōu)的位置，此目標函數(shù)等值線與可行域的交點即最優(yōu)解（一個或多個），此目標函數(shù)的值即最優(yōu)值。否則，目標函數(shù)等值線與可行域將交于無窮遠處，此時稱無有限最優(yōu)解。圖解法求解2維線性規(guī)劃

例:某工廠擁有A、B、C三種類型的設備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設備可利用的時數(shù)如下表所示：

產(chǎn)品甲產(chǎn)品乙設備能力（h）設備A3265設備B2140設備C0375利潤（元/件）15002500

問題：工廠應如何安排生產(chǎn)可獲得最大的總利潤？用圖解法求解。解：設變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。根據(jù)前面分析，可以建立如下的線性規(guī)劃模型：

Max

z=1500x1

+2500x2

s.t.3x1+2x2

≤65(A)

2x1+x2

≤40(B)

3x2

≤75(C)

x1,x2≥0(D,E)按照圖解法的步驟：（1）以決策變量x1

，x2

為坐標向量作平面直角坐標系；（2）對每個約束（包括非負約束）條件作出直線（A、B、C、D、E），并通過判斷確定不等式所決定的半平面。各約束半平面交出來的區(qū)域即可行集或可行域如下圖陰影所示。第2步圖示(1)分別作出各約束半平面2x1+x2

≤40

3x2

≤75x1

≥0X2≥03x1+2x2

≤65

第2步圖示(2)各約束半平面的交－可行域（3）任意給定目標函數(shù)一個值（例如37500）作一條目標函數(shù)的等值線，并確定該等值線平移后值增加的方向（向上移動函數(shù)值增大），平移此目標函數(shù)的等值線，使其達到既與可行域有交點又不可能使值再增加的位置，得到交點(5,25)T，即最優(yōu)解。此目標函數(shù)的值為70000。第3步圖示作出目標函數(shù)等值線函數(shù)值增大第3步圖示(2)求出最優(yōu)解根據(jù)上面的過程我們得到這個線性規(guī)劃的最優(yōu)解x1=5、x2=25，最優(yōu)值z=70000即最優(yōu)方案為生產(chǎn)甲產(chǎn)品5件、乙產(chǎn)品25件，可獲得最大利潤為70000元。線性規(guī)劃的解有如下幾種情況：

1、存在有限最優(yōu)解：唯一最優(yōu)解；無窮多個最優(yōu)解

2、無有限最優(yōu)解（無界解）

3、無可行解（可行域空）

例：在線性規(guī)劃模型中，如果目標函數(shù)變?yōu)椋?/p>

Maxz=1500x1

+1000x2

那么，最優(yōu)情況下目標函數(shù)的等值線與直線（A）重合。這時，最優(yōu)解有無窮多個，是從點(5,25)T到點(15,10)T線段上的所有點，最優(yōu)值為32500。如下圖所示：

無窮多解的情況(15,10)T

例：在線性規(guī)劃模型中,如果約束條件（A）、（C）變?yōu)椋?/p>

3x1

+2x2

≥65(A’）

3x2

≥75(C’）并且去掉（D、E）的非負限制。那么，可行域成為一個上無界的區(qū)域。這時，沒有有限最優(yōu)解，如下圖所示：

無有限解的情況

例：在線性規(guī)劃模型中，如果增加約束條件（F）為：

x1

+x2≥40

（F）那么，可行域成為空的區(qū)域。這時，沒有可行解，顯然線性規(guī)劃問題無解。如下圖所示：

無可行解的情況

根據(jù)以上例題，進一步分析討論可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況

1.可行域為封閉的有界區(qū)域

(a)有唯一的最優(yōu)解；

(b)有無窮多個最優(yōu)解；

2.可行域為封閉的無界區(qū)域

(c)有唯一的最優(yōu)解；

(d)有無窮多個最優(yōu)解；

(e)目標函數(shù)無界(即雖有可行解，但在可行域中，目標函數(shù)可以無限增大或無限減少)，因而沒有有限最優(yōu)解。

3.可行域為空集

(f)沒有可行解，原問題無最優(yōu)解

五、線性規(guī)劃問題的求解方法——單純形法

（一）單純形表

根據(jù)以上討論，令則基變量，非基變量，則有變形得相應地，記目標函數(shù)記為則對應于基B的基本解為最優(yōu)解的判定當時，則由目標函數(shù)式可看出：對應于B的基本可行解為最優(yōu)解，這時，B也被稱為最優(yōu)基。由于與等價，故可得。最優(yōu)解的判定定理

對于基B

，若，且,則對應于基B

的基本解為最優(yōu)解，B為最優(yōu)基。在上式中，稱系數(shù)矩陣

為對應于基B的單純形表，記為T(B)?；驅δ繕撕瘮?shù)與約束不等式運用矩陣變形得如果記以及則(二)單純形法的計算步驟

第1步，找出初始可行基，建立初始單純形表。第2步，判別檢驗所有的檢驗系數(shù)

（1）如果所有的檢驗系數(shù),則由最優(yōu)性判定定理知，已獲最優(yōu)解，即此時的基本可行解就是最優(yōu)解。

（2）若檢驗系數(shù)中，有些為正數(shù)，但其中某一正的檢驗系數(shù)所對應的列向量的各分量均非正，則線性規(guī)劃問題無解。（3）若檢驗系數(shù)中，有些為正數(shù)，且它們所對應的列向量中有正的分量，則需要換基、進行迭代運算。

第3步，選主元。在所有大于零的檢驗數(shù)中選取最大的一個b0s，對應的非基變量為xs，對應的列向量為若則確定brs為主元項。

第4步，在基B中調(diào)進Ps，換出Pjr，得到一個新的基第5步，在單純形表上進行初等行變換，使第s列向量變?yōu)閱挝幌蛄?，又得一張新的單純形表。?步，轉入上述第2步。

例1：用單純形方法求解線性規(guī)劃問題

解：首先引入松弛變量，把原問題化為標準形式

具體步驟如下：第1步，確定初始單純形表。x1x2x3x4-z02300x3121310x492101

第2步，判別。在初始單純形表中b01=2,b02=3，所以B1不是最優(yōu)基，進行換基迭代。第3步，選主元。根據(jù)選主元法則，確定主元項。第4步，換基，得一新基。

第5步，進行初等行變換，得B2下的新單純形表x1x2x3x4-z-1210-10x241/311/30x455/30-1/31

第6步，因檢驗系數(shù)有正數(shù)b01=1，重復以上步驟可得對應于

B3=[p2,p3]的單純形表，檢驗各檢驗數(shù)可知得最優(yōu)解X1=3,X2=3,X3=0,X4=0:目標函數(shù)最大值為

Z=15。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1310-1/53/5

六、應用實例:農(nóng)場種植計劃模型

某農(nóng)場I、II、III等耕地的面積分別為100hm2、300hm2和200hm2，計劃種植水稻、大豆和玉米，要求3種作物的最低收獲量分別為190000kg、130000kg和350000kg。I、II、III等耕地種植3種作物的單