線性規(guī)劃及其單純形求解方法

線性規(guī)劃及其單純形求解方法第1頁(yè)，共40頁(yè)，2023年，2月20日，星期二

線性規(guī)劃是運(yùn)籌學(xué)中發(fā)展較快、應(yīng)用較廣和比較成熟的一個(gè)分支。它在實(shí)際應(yīng)用中日益廣泛與深入,已經(jīng)被廣泛地應(yīng)用到工業(yè)、農(nóng)業(yè)、商業(yè)與交通運(yùn)輸規(guī)劃，工程技術(shù)的優(yōu)化設(shè)計(jì)，以及企業(yè)管理等各個(gè)領(lǐng)域。在地理學(xué)領(lǐng)域，線性規(guī)劃，作為傳統(tǒng)的計(jì)量地理學(xué)方法之一，是解決有關(guān)規(guī)劃、決策和系統(tǒng)優(yōu)化問(wèn)題的重要手段。第2頁(yè)，共40頁(yè)，2023年，2月20日，星期二線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的標(biāo)準(zhǔn)形式及方法線性規(guī)劃的解及其性質(zhì)線性規(guī)劃問(wèn)題的求解方法——單純形法應(yīng)用實(shí)例:農(nóng)場(chǎng)種植計(jì)劃模型第1節(jié)線性規(guī)劃及其單純形求解方法第3頁(yè)，共40頁(yè)，2023年，2月20日，星期二

（一）線性規(guī)劃模型之實(shí)例線性規(guī)劃研究的兩類(lèi)問(wèn)題：某項(xiàng)任務(wù)確定后，如何統(tǒng)籌安排，以最少的人力、物力和財(cái)力去完成該項(xiàng)任務(wù)；面對(duì)一定數(shù)量的人力、物力和財(cái)力資源，如何安排使用，使得完成的任務(wù)最多。它們都屬于最優(yōu)規(guī)劃的范疇。以下為一些實(shí)例。一、線性規(guī)劃的數(shù)學(xué)模型第4頁(yè)，共40頁(yè)，2023年，2月20日，星期二運(yùn)輸問(wèn)題假設(shè)某種物資（譬如煤炭、鋼鐵、石油等）有m個(gè)產(chǎn)地，n個(gè)銷(xiāo)地。第i產(chǎn)地的產(chǎn)量為ai（i=1，2，…，m），第j

銷(xiāo)地的需求量為bj(j=1,2，…，n)，它們滿(mǎn)足產(chǎn)銷(xiāo)平衡條件。如果產(chǎn)地i到銷(xiāo)地j的單位物資的運(yùn)費(fèi)為Cij，要使總運(yùn)費(fèi)達(dá)到最小，可這樣安排物資的調(diào)運(yùn)計(jì)劃：第5頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

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

而且使

第6頁(yè)，共40頁(yè)，2023年，2月20日，星期二資源利用問(wèn)題

假設(shè)某地區(qū)擁有m種資源，其中，第i種資源在規(guī)劃期內(nèi)的限額為bi(i=1，2，…，m)。這m種資源可用來(lái)生產(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)品的單價(jià)為cj(j=1，2，…，n)。試問(wèn)如何安排這幾種產(chǎn)品的生產(chǎn)計(jì)劃，才能使規(guī)劃期內(nèi)資源利用的總產(chǎn)值達(dá)到最大?第7頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

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

第8頁(yè)，共40頁(yè)，2023年，2月20日，星期二合理下料問(wèn)題

用某種原材料切割零件A1，A2,…,Am的毛坯，現(xiàn)已設(shè)計(jì)出在一塊原材料上有B1，B2，…，Bn種不同的下料方式，如用Bj下料方式可得Ai種零件aij個(gè)，設(shè)Ai種零件的需要量為bi個(gè)。試問(wèn)應(yīng)該怎樣組織下料活動(dòng)，才能使得既滿(mǎn)足需要，又節(jié)約原材料？第9頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

求一組整數(shù)變量xj(j=1，2，…，n)，使得第10頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

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

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

以及非負(fù)約束條件

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

(j=1，2，…，n)的值，使第12頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

AX≤(≥，＝)b

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

其中第13頁(yè)，共40頁(yè)，2023年，2月20日，星期二

二、線性規(guī)劃的標(biāo)準(zhǔn)形式及方法

(一）線性規(guī)劃的標(biāo)準(zhǔn)形式

在討論與計(jì)算時(shí)，需要將線性規(guī)劃問(wèn)題的數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式，即在約束條件xj≥0（j=1，2，…，n）

下，求一組未知變量xj（j=1，2，…，n）的值，使第14頁(yè)，共40頁(yè)，2023年，2月20日，星期二其縮寫(xiě)形式為：在約束條件

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

下，求一組未知變量（j

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

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

或第15頁(yè)，共40頁(yè)，2023年，2月20日，星期二（二）化為標(biāo)準(zhǔn)形式的方法

具體的線性規(guī)劃問(wèn)題，需要對(duì)目標(biāo)函數(shù)或約束條件進(jìn)行轉(zhuǎn)換，化為標(biāo)準(zhǔn)形式。目標(biāo)函數(shù)化為標(biāo)準(zhǔn)形式的方法

如果其線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)為

minZ

=CX

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

Z′

則目標(biāo)函數(shù)的標(biāo)準(zhǔn)形式為max

Zˊ=-CX第16頁(yè)，共40頁(yè)，2023年，2月20日，星期二約束方程化為標(biāo)準(zhǔn)形式的方法

若第k個(gè)約束方程為不等式，即

引入松弛變量,K個(gè)方程改寫(xiě)為則目標(biāo)函數(shù)標(biāo)準(zhǔn)形式為第17頁(yè)，共40頁(yè)，2023年，2月20日，星期二三、線性規(guī)劃的解及其性質(zhì)

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

可行解與最優(yōu)解滿(mǎn)足約束條件（即滿(mǎn)足線性約束和非負(fù)約束）的一組變量為可行解。所有可行解組成的集合稱(chēng)為可行域。使目標(biāo)函數(shù)最大或最小化的可行解稱(chēng)為最優(yōu)解。

第18頁(yè)，共40頁(yè)，2023年，2月20日，星期二基本解與基本可行解

在線性規(guī)劃問(wèn)題中，將約束方程組的m×n階矩陣A寫(xiě)成由n個(gè)列向量組成的分塊矩陣第19頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

第20頁(yè)，共40頁(yè)，2023年，2月20日，星期二

如果是方程組的解,則就是方程組的一個(gè)解，它稱(chēng)之為對(duì)應(yīng)于基B的基本解，簡(jiǎn)稱(chēng)基解。滿(mǎn)足非負(fù)約束條件的基本解，稱(chēng)為基本可行解。對(duì)應(yīng)于基本可行解的基，稱(chēng)為可行基。第21頁(yè)，共40頁(yè)，2023年，2月20日，星期二

線性規(guī)劃問(wèn)題的以上幾個(gè)解的關(guān)系，可用下圖來(lái)描述：第22頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

凸集和頂點(diǎn)

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

第23頁(yè)，共40頁(yè)，2023年，2月20日，星期二線性規(guī)劃解的性質(zhì)

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

②可行解集S中的點(diǎn)X是頂點(diǎn)的充要條件是基本可行解。

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

因此線性規(guī)劃的最優(yōu)解只需從其可行解集的有限個(gè)頂點(diǎn)中去尋找。第24頁(yè)，共40頁(yè)，2023年，2月20日，星期二四、線性規(guī)劃問(wèn)題的求解方法——單純形法

（一）單純形表

根據(jù)以上討論，令則基變量，非基變量，則有變形得第25頁(yè)，共40頁(yè)，2023年，2月20日，星期二相應(yīng)地，記目標(biāo)函數(shù)記為則對(duì)應(yīng)于基B的基本解為第26頁(yè)，共40頁(yè)，2023年，2月20日，星期二最優(yōu)解的判定當(dāng)時(shí)，則由目標(biāo)函數(shù)式可看出：對(duì)應(yīng)于B的基本可行解為最優(yōu)解，這時(shí)，B也被稱(chēng)為最優(yōu)基。由于與等價(jià)，故可得。最優(yōu)解的判定定理

對(duì)于基B

，若，且,則對(duì)應(yīng)于基B

的基本解為最優(yōu)解，B為最優(yōu)基。第27頁(yè)，共40頁(yè)，2023年，2月20日，星期二在上式中，稱(chēng)系數(shù)矩陣

為對(duì)應(yīng)于基B的單純形表，記為T(mén)(B)?；?qū)δ繕?biāo)函數(shù)與約束不等式運(yùn)用矩陣變形得第28頁(yè)，共40頁(yè)，2023年，2月20日，星期二如果記以及則第29頁(yè)，共40頁(yè)，2023年，2月20日，星期二(二)單純形法的計(jì)算步驟

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

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

（2）若檢驗(yàn)系數(shù)中，有些為正數(shù)，但其中某一正的檢驗(yàn)系數(shù)所對(duì)應(yīng)的列向量的各分量均非正，則線性規(guī)劃問(wèn)題無(wú)解。（3）若檢驗(yàn)系數(shù)中，有些為正數(shù)，且它們所對(duì)應(yīng)的列向量中有正的分量，則需要換基、進(jìn)行迭代運(yùn)算。第30頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

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

第31頁(yè)，共40頁(yè)，2023年，2月20日，星期二例1：用單純形方法求解線性規(guī)劃問(wèn)題

解：首先引入松弛變量，把原問(wèn)題化為標(biāo)準(zhǔn)形式

第32頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

第2步，判別。在初始單純形表中b01=2,b02=3，所以B1不是最優(yōu)基，進(jìn)行換基迭代。第3步，選主元。根據(jù)選主元法則，確定主元項(xiàng)。第4步，換基，得一新基。表5.1.1第33頁(yè)，共40頁(yè)，2023年，2月20日，星期二

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

第6步，因檢驗(yàn)系數(shù)有正數(shù)b01=1，重復(fù)以上步驟可得對(duì)應(yīng)于

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

Z=15。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1310-1/53/5表5.1.2表5.1.3第34頁(yè)，共40頁(yè)，2023年，2月20日，星期二

五、應(yīng)用實(shí)例:農(nóng)場(chǎng)種植計(jì)劃模型

某農(nóng)場(chǎng)I、II、III等耕地的面積分別為100hm2、300hm2和200hm2，計(jì)劃種植水稻、大豆和玉米，要求3種作物的最低收獲量分別為190000kg、130000kg和350000kg。I、II、III等耕地種植3種作物的單產(chǎn)如表5.1.4所示。若3種作物的售價(jià)分別為水稻1.20元/kg，大豆1.50元/kg，玉米0.80元/kg。那么，（1）如何制訂種植計(jì)劃，才能使總產(chǎn)量最大？（2）如何制訂種植計(jì)劃，才能使總產(chǎn)值最大？第35頁(yè)，共40頁(yè)，2023年，2月20日，星期二表5.1.4不同等級(jí)耕地種植不同作物的單產(chǎn)(單位:kg/hm2