物流運(yùn)籌學(xué)郝海熊德國chap2-線性規(guī)劃3-22單純形法

2.2單純形法單純形法是解決線性規(guī)劃問題的根本方法，其原理出自線性代數(shù)的矩陣?yán)碚?，是可按現(xiàn)代計(jì)算機(jī)標(biāo)準(zhǔn)程序求解線性規(guī)劃模型的一般方法，分為代數(shù)形式的單純形法和表格形式的單純形法。前者提供根本算法所依據(jù)的邏輯規(guī)那么，適用于在電子計(jì)算機(jī)上進(jìn)行求解運(yùn)算；后者將變量和數(shù)據(jù)列成表格，是本章采用的方法。2.2.1線性規(guī)劃的有關(guān)概念

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為其中A是m×n矩陣，且秩r(A)=m，亦即A中至少有一個(gè)滿秩m×m子矩陣。

解滿足系統(tǒng)約束條件的決策向量X=(x1,x2,…,xn)T稱為線性規(guī)劃的解。

可行解滿足符號(hào)約束條件的解X=(x1,x2,…,xn)T稱為線性規(guī)劃的可行解。

1/29/202412.2單純形法可行域全體可行解的集合稱為線性規(guī)劃的可行域，一般記作D={X|AX=b,X≥0}。最優(yōu)解使目標(biāo)函數(shù)到達(dá)最小值〔或最大值〕的可行解X*=(x1*,x2*,…,xn*)T稱為線性規(guī)劃的最優(yōu)解。最優(yōu)值最優(yōu)解的目標(biāo)函數(shù)值稱為線性規(guī)劃的最優(yōu)值。

基假設(shè)A中m×m子矩陣B滿足r(B)=m,那么稱B是線性規(guī)劃問題的一個(gè)基。也就是說，矩陣B是由A的m個(gè)線性無關(guān)列向量所構(gòu)成，不妨設(shè)為：稱Pj(j=1,2,…,m)為基向量。1/29/202422.2單純形法

基變量、非基變量與其基向量Pj(j=1,2,…,m)相對(duì)應(yīng)的變量Xj(j=1,2,…,m)為基變量，其他決策變量稱為非基變量。根本解記基變量為XB=(x1,x2,…,xn)T，非基變量為XN=

(xm+1,xm+2,…,xn)T，稱滿足方程

組的解XB=B-1b且XN=0為根本解。根本可行解假設(shè)根本解XB=

B-1b≥0，那么稱該解為根本可行解，也稱為基可行解，B為可行基。注與基有關(guān)的概念都是相

對(duì)的。1/29/20243【例2.8】求出下面線性規(guī)劃的所有根本解,并指出那些是基可行解.2.2單純形法解將線性規(guī)劃模型化為標(biāo)準(zhǔn)型：其中系數(shù)矩陣1/29/20244由于X1≥0，所以也

是根本可行解。2.2單純形法即B1是一個(gè)基，

相應(yīng)的線性規(guī)劃根本解為X1=(15/4,3/4,0,0)，求其他根本解的過程見下表。1/29/202452.2單純形法根本解與根本可行解表基基向量基變量非基變量基本解基可行解X1=(15/4,3/4,0,0)是X2=(4,0,3,0)是X3=(5,0,0,-6)不是X4=(0,12,-45,0)不是X5=(0,3,0,18)是

X1=(0,0,15,24)是

一般來說，如果線性規(guī)劃具有n個(gè)變量m個(gè)約束，則基本解的數(shù)量小于或等于，當(dāng)然基可行解的數(shù)量更不會(huì)超過個(gè)。1/29/202462.2單純形法2.2.2單純形法的理論根底根本概念

凸集設(shè)D是n維歐氏空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)

的連線上的一切點(diǎn)（即集合D中任意兩個(gè)點(diǎn)其連線上的所有點(diǎn)也都是集合D中的點(diǎn)）；則稱D為凸集。

從直觀上說，凸集沒有凹入部分，其內(nèi)部沒有孔洞。凸組合設(shè)是n維歐氏空間中的k個(gè)點(diǎn)，若存在，且使

，則稱x為的凸組合。

頂點(diǎn)設(shè)D是凸集，若且x不能用D中不同的兩點(diǎn)

的線性組合表示為，則稱x為D的一個(gè)頂點(diǎn)（或極點(diǎn)）。

S1S2S31/29/202472.2單純形法根本定理定理2.1假設(shè)線性規(guī)劃問題存在可行域，那么可行域是凸集。定理2.2線性規(guī)劃可行域D中的點(diǎn)X是頂點(diǎn)的充要條件為X是基可行解。定理2.3假設(shè)線性規(guī)劃有最優(yōu)解，那么最優(yōu)解一定可以在可行域的頂點(diǎn)上得到。【例2.9】指出例2.8中的線性規(guī)劃根本解與其可行域頂點(diǎn)的對(duì)應(yīng)關(guān)系。解見下表的說明及圖示。1/29/202482.2單純形法根本解與其對(duì)應(yīng)的頂點(diǎn)基

變量基本解基可行解頂點(diǎn)X1=(15/4,3/4,0,0)是X2=(4,0,3,0)是X3=(5,0,0,-6)不是X4=(0,12,-45,0)不是X5=(0,3,0,18)是

X1=(0,0,15,24)是1/29/202492.2單純形法但當(dāng)m,n較大時(shí)，計(jì)算工作繁瑣龐大，這種方法還是行不通的，所以還要繼續(xù)討論如何有效地找到最優(yōu)解的方法，這就是下面介紹的單純形法。線性規(guī)劃問題的所有解構(gòu)成的集合是凸集，凸集的每一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)基可行解，由于基可行解的個(gè)數(shù)是有限的（它不大于個(gè)），所以頂點(diǎn)的個(gè)數(shù)也是有限的。若線性規(guī)劃問題有最優(yōu)解，必在可行域某頂點(diǎn)上得到，可采用“枚舉法”找出所有基可行解，然后一一進(jìn)行比較，最終就可能找到最優(yōu)解。2.2.3單純形法的計(jì)算步驟單純形法是從可行域的一個(gè)基可行解出發(fā)〔頂點(diǎn)〕，判斷該解是否為最優(yōu)解，如果不是就轉(zhuǎn)移到另一個(gè)較好的基可行解，如果目標(biāo)函數(shù)到達(dá)最優(yōu)，那么已得到最優(yōu)解，否那么，繼續(xù)轉(zhuǎn)移到其它較好的基可行解。由于基可行解〔頂點(diǎn)〕的數(shù)目是有限的，所以經(jīng)過有限次數(shù)的迭代轉(zhuǎn)換后就能求出最優(yōu)解，如以下圖所示。1/29/202410否是否是2.2單純形法確定初始基可行解判

斷解是否最

優(yōu)是

否有無界

解搜索使目標(biāo)函數(shù)

改善的基可行解結(jié)束單純形法求解步驟流程圖定理2.4定理2.5定理2.6初始基可行解確實(shí)定1〕假設(shè)給定問題標(biāo)準(zhǔn)化后〔且b≥0〕，系數(shù)矩陣A中存在m個(gè)線性無關(guān)的單位列向量，那么以這m個(gè)單位列向量構(gòu)成的單位矩陣B作為初始基，那么XB=B-1b=b≥0，其他xj=0就是初始基可行解?！纠?.10】求下面問題的初始

基可行解1/29/2024112.2單純形法解將線性規(guī)劃標(biāo)準(zhǔn)化，添加松弛變量x3,x4，得由于有兩個(gè)單位列向量,可取為初始基，則

就是初始基可行解。

1/29/2024122.2單純形法2〕假設(shè)給定問題標(biāo)準(zhǔn)化后(b≥0)系數(shù)矩陣中不存在m個(gè)線性無關(guān)的單位列向量，那么在某些約束左端加一個(gè)非負(fù)的人工變量構(gòu)建一些單位列向量，人工創(chuàng)造一個(gè)單位矩陣，參見后面的大M法。

單純形法的求解定理

線性規(guī)劃的標(biāo)準(zhǔn)型為不妨設(shè)B=(P1,P2,…,Pm)是其中一個(gè)基，將有關(guān)矩陣和向量分塊，記A=(B,N),C=(CB,CN),X=(XB,XN)T為求線性規(guī)劃的根本最優(yōu)解，先要求線性規(guī)劃的根本可行解，這樣就需將約束中的基變量用非基變量表示出來。其中A是m×n矩陣，且r(A)=m。1/29/2024132.2單純形法用B-1左乘約束方程AX=b的兩端，得：

將其代入目標(biāo)函數(shù)得:稱為非基變量xj的檢驗(yàn)數(shù)，記為表示該變量增加或減少一個(gè)單位所引起目標(biāo)函數(shù)值的變化，它可以用來判斷xj將變成基變量后能否改進(jìn)目標(biāo)函數(shù)值1/29/2024142.2單純形法上面過程也可以通過線性方程組消元實(shí)現(xiàn):線性方程組其變量為整理得方程組為便于求解，其增廣矩陣見下表常數(shù)項(xiàng)zXBXNb0BN(1)0-1CBCN(2)用B-1左乘方程組(1)的兩端,將XB的系數(shù)化為單位矩陣,得下表常數(shù)項(xiàng)zXBXNB-1b0B-1B=EB-1N(3)0-1CBCN1/29/202415常數(shù)項(xiàng)zXBXNB-1b0B-1B=EB-1N(3)0-1CBCN(2)2.2單純形法將方程組(3)左乘-CB加到方程(2)兩邊，得下表常數(shù)項(xiàng)zXBXNB-1b0B-1B=EB-1N-CBB-1b-1CB-CBB-1B=OCN-CBB-1N(4)注意(4)中基變量XB、非基變量XN的系數(shù)，他們形式結(jié)構(gòu)相似，當(dāng)前者CB-CBB-1B=O時(shí)，后者CN-CBB-1N即為檢驗(yàn)數(shù)的矩陣形式，也就是說，用消元法將目標(biāo)函數(shù)中基變量的系數(shù)化為零的同時(shí)，就會(huì)得到非基變量的檢驗(yàn)數(shù)。事實(shí)上，CB-CBB-1B也可看成基向量的檢驗(yàn)數(shù)，應(yīng)用消元法后，當(dāng)基向量的檢驗(yàn)數(shù)變?yōu)榱銜r(shí)，非基變量的系數(shù)CN-CBB-1N就是其檢驗(yàn)數(shù)。1/29/2024162.2單純形法線性規(guī)劃單純形法求解有下述定理：

定理2.4（最優(yōu)解判定定理）對(duì)某基可行解XB=B-1b其他xj=0，若所有的，則該解為最優(yōu)解。定理2.5（無界解判定定理）若對(duì)某可行基B,存在

且，則該線性規(guī)劃問題有無界解。

定理2.6〔換基迭代定理〕1）給定某可行基B,對(duì)矩陣A的行列來說,通過下面步驟：

①確定進(jìn)基變量：，選擇k列的非基變量xk為進(jìn)基變量；

②按最小比值原則確定出基變量：

（最小值不唯一時(shí)任選一個(gè)行標(biāo)l作為），其中(B-1b)i表示向量B-1b的第i個(gè)元素，選擇l行對(duì)應(yīng)的基變量xl為出基變量，那么Pk替換B中出基變量所在的列后就能得到一個(gè)新的可行基。

1/29/2024172.2單純形法2）對(duì)線性方程組AX=b的增廣矩陣實(shí)施初等行變換：

①第l行元素同除以主元alk，使主元變?yōu)?；

②使主元所在列的其它元素變?yōu)?，這樣就得到可行基

對(duì)應(yīng)的基可行解，并且所對(duì)應(yīng)的目標(biāo)函數(shù)值增加。

單純形表為便于表達(dá)單純形法的計(jì)算過程，上述計(jì)算過程可以在單純形表上完成。每個(gè)可行基B都可構(gòu)造出一個(gè)單純形表，一般將其化為單位矩陣后再列出單純形表，見下表

1/29/2024182.2單純形法CBXBB-1bc1c2…cmcm+1…cnθx1x2…xmxm+1…xnc1x1b110…0a1m+1…a1nc2X2b201…0a2m+1…a2n……………………………cmxmbm00…1amm+1…amm檢驗(yàn)數(shù)σ00…0σm+1…σn表中：XB一列記錄基變量；CB一列跟蹤基變量對(duì)應(yīng)的價(jià)值系數(shù)；B-1b為基可行解；其余各列為B-1Pj(j=1,2,…,n)，最后一行是每個(gè)變量對(duì)應(yīng)的檢驗(yàn)數(shù)。大方框中元素就是增廣矩陣，這樣求解線性規(guī)劃就可以在單純形表中實(shí)現(xiàn)，單純形表包含了線性規(guī)劃求解的全部信息。1/29/2024192.2單純形法【例2.11】用單純形法求例2.8的最優(yōu)解b2100x1x2x3x4153510246201BXBNXN153510246201EB-1NB-1b填入下面初始單純形表：1/29/2024202.2單純形法CBXBB-1b2100θx1x2x3x4153510246201檢驗(yàn)數(shù)σx3x4002154[]檢驗(yàn)數(shù)σx3x102411/301/63041-1/21/3-1/33/412[]檢驗(yàn)數(shù)σ

x2x1123/4011/4-1/815/410-1/125/24-1/24-7/24X*=(15/4,3/4)z*=33/41/29/2024212.2單純形法【例2.13】用單純形法求解線性規(guī)劃解將線性規(guī)劃標(biāo)準(zhǔn)化，得1/29/2024222.2單純形法CBXBB-1b24000θx1x2x3x4x54-12100101201021-1001檢驗(yàn)數(shù)σ檢驗(yàn)數(shù)σx3x4x50002425-[]x2x4x54002-1/211/200620-11041/201/2014-2-38[]1/29/2024232.2單純形法CBXBB-1b24000θx1x2x3x4x54x22-1/211/200-0x4620-11030x541/201/2018檢驗(yàn)數(shù)σ4-2檢驗(yàn)數(shù)σ[]x2x1x54207/2011/41/40310-1/21/205/2003/4-1/410-2X1*=(3,7/2,0,0,5/2)

z*=2014-10/3[]值得注意的是，在最終單純形表中，除基變量的檢驗(yàn)數(shù)為零外，非基變量x3的檢驗(yàn)數(shù)也為零，意味著假設(shè)讓x3取值變化不會(huì)使目標(biāo)函數(shù)值有所改變。這時(shí)如果讓x3進(jìn)基并繼續(xù)迭代，就會(huì)得到另一個(gè)根本可行解。1/29/2024242.2單純形法CBXBB-1b24000θx1x2x3x4x54x27/2011/41/40142x1310-1/21/20-0x55/2003/4-1/4110/3檢驗(yàn)數(shù)σ0-2檢驗(yàn)數(shù)σ[]x2x1x34208/30101/3-1/314/31001/32/310/3001-1/34/30-2X2*=(14/3,8/3,10/3,0,0)

z*=20根據(jù)最優(yōu)解的定義，使目標(biāo)函數(shù)到達(dá)最大值的任一可行解都是一個(gè)最優(yōu)解。所以該線性規(guī)劃有多個(gè)最優(yōu)解，其最優(yōu)解的一般表達(dá)式為這種情況為線性規(guī)劃問題具有多重最優(yōu)解。一般說來，但凡在最優(yōu)單純形表中出現(xiàn)檢驗(yàn)數(shù)為零的非基變量，就存在多個(gè)最優(yōu)解。1/29/2024252.2單純形法2.2.4單純形法的進(jìn)一步討論單純形法的求解根底是能夠找到線性規(guī)劃的可行解，如何找到這個(gè)可行解呢？這里學(xué)習(xí)構(gòu)造初始可行解的大M法

大M法在用單純形法求解線性規(guī)劃問題時(shí)，首先要確定一個(gè)初始可行基〔一般是單位矩陣〕。假設(shè)其系數(shù)矩陣中已有一個(gè)單位矩陣，那么可以作為初始可行基；假設(shè)不存在單位矩陣，那么可以采用在每個(gè)約束等式中人為地添加一個(gè)非負(fù)變量〔稱為人工變量〕的方法，來構(gòu)造另外一個(gè)線性規(guī)劃問題，下面通過實(shí)例說明如何使用大M法。【例2.14】求解線性規(guī)劃1/29/2024262.2單純形法解將線性規(guī)劃標(biāo)準(zhǔn)化，得它的系數(shù)矩陣為在第二、三個(gè)約束方程的左邊添加人工變量x6,x7≥0

，就構(gòu)成一個(gè)系數(shù)矩陣中含有單位矩陣的新的線性規(guī)劃問題:

矩陣中A有一個(gè)單位矩陣列，但不含有單位矩陣。1/29/2024272.2單純形法

只有當(dāng)所添加的人工變量取值為0時(shí)，該線性規(guī)劃才和原規(guī)劃等價(jià)。為此，在目標(biāo)函數(shù)中對(duì)人工變量的價(jià)值系數(shù)進(jìn)行懲罰，使其在求解過程中取值為零，最好為非基變量，所以在求max問題中，人工變量在目標(biāo)函數(shù)中的系數(shù)均為-M；在min問題中，人工變量在目標(biāo)函數(shù)中的系數(shù)均為M，這里M是一個(gè)任意大的正數(shù)。大M法也叫罰系數(shù)法，利用大M法的關(guān)鍵在于如何能夠盡快將人工變量替換出基。

添加人工變量后構(gòu)成的新的線性規(guī)劃為:-Mx6-Mx71/29/2024282.2單純形法添加人工變量后構(gòu)成的新的線性規(guī)劃為:-Mx6-Mx7這樣，就可以將人工變量視為基變量，得到一個(gè)初始基可行解，就可用單純形法進(jìn)行迭代計(jì)算。如果假設(shè)經(jīng)假設(shè)干次迭代，人工變量被全部替換出了基，那么原問題的約束條件得到恢復(fù)，同時(shí)也有了一個(gè)根本可行解，原規(guī)劃單純形求解的初始條件就已具備，可繼續(xù)采用單純形表求解。1/29/2024292.2單純形法CBXBB-1b3-1-100-M-Mθx1x2x3x4x5x6x7111-2110003-4120-1101-2010001檢驗(yàn)數(shù)σ檢驗(yàn)數(shù)σx4x6x70-M-M3-6MM-13M-1-M111.51x4x6x30[]-M-11-2010001103-20100-110100-11-21M-1-M1-2M-1-[]1/29/2024302.2單純形法CBXBB-1b3-1-100-M-Mθx1x2x3x4x5x6x70x4103-20100-1--Mx