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

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

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

（一）線性規(guī)劃模型之實(shí)例線性規(guī)劃研究的兩類問題：某項(xiàng)任務(wù)確定后，如何統(tǒng)籌安排，以最少的人力、物力和財力去完成該項(xiàng)任務(wù)；面對一定數(shù)量的人力、物力和財力資源，如何安排使用，使得完成的任務(wù)最多。它們都屬于最優(yōu)規(guī)劃的范疇。以下為一些實(shí)例。一、線性規(guī)劃的數(shù)學(xué)模型第4頁，共40頁，2023年，2月20日，星期二運(yùn)輸問題假設(shè)某種物資（譬如煤炭、鋼鐵、石油等）有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的單位物資的運(yùn)費(fèi)為Cij，要使總運(yùn)費(fèi)達(dá)到最小，可這樣安排物資的調(diào)運(yùn)計劃：第5頁，共40頁，2023年，2月20日，星期二

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

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

而且使

第6頁，共40頁，2023年，2月20日，星期二資源利用問題

假設(shè)某地區(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)值達(dá)到最大?第7頁，共40頁，2023年，2月20日，星期二

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

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

第8頁，共40頁，2023年，2月20日，星期二合理下料問題

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

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

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

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

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

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

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

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

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

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

AX≤(≥，＝)b

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

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

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

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

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

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

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

下，求一組未知變量（j

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

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

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

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

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

minZ

=CX

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

Z′

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

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

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

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

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

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

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

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

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

第20頁，共40頁，2023年，2月20日，星期二

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

線性規(guī)劃問題的以上幾個解的關(guān)系，可用下圖來描述：第22頁，共40頁，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)，則稱X(0)為S的頂點(diǎn)或極點(diǎn)。

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

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

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

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

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

（一）單純形表

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

對于基B

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

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

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

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

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

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

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

第4步，在基B中調(diào)進(jìn)Ps，換出Pjr，得到一個新的基第5步，在單純形表上進(jìn)行初等行變換，使第s列向量變?yōu)閱挝幌蛄浚值靡粡埿碌膯渭冃伪?。?步，轉(zhuǎn)入上述第2步。

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

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

第32頁，共40頁，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頁，共40頁，2023年，2月20日，星期二

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

第6步，因檢驗(yàn)系數(shù)有正數(shù)b01=1，重復(fù)以上步驟可得對應(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頁，共40頁，2023年，2月20日，星期二

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

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