最優(yōu)化計算方法(工程優(yōu)化)第5章

線性規(guī)劃的簡介和應(yīng)用舉例線性規(guī)劃的數(shù)學(xué)模型和圖解法線性規(guī)劃的基本概念和基本性質(zhì)單純形法關(guān)于單純形法的說明和補(bǔ)充線性規(guī)劃的對偶理論與對偶單純形法第5章線性規(guī)劃線性規(guī)劃就是一個線性函數(shù)在線性等式或不等式約束條件下的極值問題，是最簡單的約束優(yōu)化問題理論最為成熟、應(yīng)用最為廣泛的一種數(shù)學(xué)規(guī)劃方法運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個重要分支廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營管理和工程技術(shù)等方面為合理地利用有限的人力、物力、財力等資源作出最優(yōu)決策，提供科學(xué)的依據(jù)。線性規(guī)劃的概述法國數(shù)學(xué)家傅里葉和瓦萊-普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家康托羅維奇在《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》一書中提出線性規(guī)劃問題，也未引起重視。1947年美國數(shù)學(xué)家G.B.丹齊格提出線性規(guī)劃的一般數(shù)學(xué)模型和求解線性規(guī)劃問題的通用方法--單純形法，為這門學(xué)科奠定了基礎(chǔ)。1947年美國數(shù)學(xué)家J.von諾伊曼提出對偶理論,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。1951年美國經(jīng)濟(jì)學(xué)家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎。線性規(guī)劃的發(fā)展50年代后對線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如1954年，C.萊姆基提出對偶單純形法1954年，S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題1956年，A.塔克提出互補(bǔ)松弛定理1960年G.B.丹齊格和P.沃爾夫提出分解算法等

1979年蘇聯(lián)數(shù)學(xué)家哈奇揚(yáng)提出解線性規(guī)劃問題的橢球算法，并證明它是多項式時間算法。

線性規(guī)劃的發(fā)展1984年美國貝爾電話實驗室的印度數(shù)學(xué)家卡馬卡提出解線性規(guī)劃問題的新的多項式時間算法。用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50?，F(xiàn)已形成線性規(guī)劃多項式算法理論。線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。線性規(guī)劃的發(fā)展線性規(guī)劃通常解決下列兩類問題：當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源(如資金、設(shè)備、原標(biāo)材料、人工、時間等)去完成確定的任務(wù)或目標(biāo)(2)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益(如產(chǎn)品量最多、利潤最大)線性規(guī)劃問題的數(shù)學(xué)模型例某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品。這些產(chǎn)品分別要在A、

B、C、D四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺時如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計劃，使企業(yè)總的利潤最大？

設(shè)備產(chǎn)品ABCD利潤(元)

甲21402

乙22043

有效臺時1281612線性規(guī)劃問題的應(yīng)用解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：線性規(guī)劃問題的應(yīng)用目標(biāo)函數(shù)：約束條件：線性規(guī)劃數(shù)學(xué)模型的一般形式線性規(guī)劃問題的數(shù)學(xué)模型目標(biāo)函數(shù)：約束條件：線性規(guī)劃問題的數(shù)學(xué)模型

線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints目標(biāo)函數(shù)：約束條件：線性規(guī)劃問題的數(shù)學(xué)模型其特征是：(1)問題的目標(biāo)函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；(2)問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

從線性規(guī)劃數(shù)學(xué)模型的一般形式看

線性規(guī)劃問題可能有各種不同的形式。目標(biāo)函數(shù)有實現(xiàn)最大化也有實現(xiàn)最小化的;

約束條件可以是“”、“”、“=”。決策變量有時有非負(fù)限制有時沒有。為便于今后討論，我們規(guī)定線性規(guī)劃問題的標(biāo)準(zhǔn)形為：線性規(guī)劃問題的標(biāo)準(zhǔn)形bi

0(i=1,2,···,m)線性規(guī)劃標(biāo)準(zhǔn)形的矩陣形式記c=(c1,c2,···,cn)T

x=(x1,x2,···,xn)T

b=(b1,b2,···,bm)T

A=(aij)m*n線性規(guī)劃的標(biāo)準(zhǔn)形的其它形式也可寫作稱A=(aij)m*n是約束方程組的系數(shù)矩陣線性規(guī)劃標(biāo)準(zhǔn)形的向量形式記c=(c1,c2,···,cn)T,

x=(x1,x2,···,xn)T

b=(b1,b2,···,bm)T

Pj=(a1j,a2j,···,amj)T

j=1,2,···,n

線性規(guī)劃的標(biāo)準(zhǔn)形的其它形式線性規(guī)劃標(biāo)準(zhǔn)形的向量形式記c=(c1,c2,···,cn)T

x=(x1,x2,···,xn)Tb=(b1,b2,···,bm)T

Ai=(ai1,ai2,···,ain)

i=1,2,···,m線性規(guī)劃的標(biāo)準(zhǔn)形的其它形式

一般情況下

,為正整數(shù),分別表示約束條件的個數(shù)和決策變量的個數(shù),

具體問題的線性規(guī)劃數(shù)學(xué)模型是各式各樣的,需要把它們化成標(biāo)準(zhǔn)型,并借助于標(biāo)準(zhǔn)型的求解方法進(jìn)行求解。稱m為線性規(guī)劃的階數(shù),稱n為線性規(guī)劃的維數(shù)。線性規(guī)劃的標(biāo)準(zhǔn)形為價值向量,

為決策向量,b為右端向量，為已知常數(shù)。

（1）目標(biāo)函數(shù)求最小值；（2）決策變量非負(fù)；（3）約束條件都是等式；（4）常數(shù)項（右端向量）非負(fù)線性規(guī)劃標(biāo)準(zhǔn)形的特點(diǎn)如何化成標(biāo)準(zhǔn)形若目標(biāo)函數(shù)是:maxz=cTx,

只需將目標(biāo)函數(shù)的最大值變換為求目標(biāo)函數(shù)的最小值,即maxz=min

(-z)。令zˊ=-z,于是得到：

min

zˊ=-cTx.

目標(biāo)函數(shù)的轉(zhuǎn)換

若約束方程組為不等式

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式稱為松弛變量相應(yīng)的松弛變量在目標(biāo)函數(shù)中的價值系數(shù)取值為0。如何化成標(biāo)準(zhǔn)形則在“”號的左邊加入非負(fù)變量;把原“”形的不等式變?yōu)榈仁?約束條件為“”形式的不等式,

約束條件為“”形式的不等式,則可在“”號的左端減去一個非負(fù)變量。

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式稱為剩余變量相應(yīng)的剩余變量在目標(biāo)函數(shù)中的價值系數(shù)取值為0。如何化成標(biāo)準(zhǔn)形

若存在取值無約束的變量，

變量的轉(zhuǎn)換若，如何化成標(biāo)準(zhǔn)形可令其中：可令，顯然例1:

試將如下線性規(guī)劃問題化成標(biāo)準(zhǔn)形任何形式的線性規(guī)劃問題都可以化成標(biāo)準(zhǔn)形?，F(xiàn)舉例如下：如何化成標(biāo)準(zhǔn)形解：令x3=x4-x5,x4,x50,

(1)式左端加上非負(fù)松弛變量x6

,(2)式左端減去非負(fù)剩余變量x7,則可將上述線性規(guī)劃問題化成如下的標(biāo)準(zhǔn)形:如何化成標(biāo)準(zhǔn)形例2:

化為標(biāo)準(zhǔn)形。

maxz=2x1+3x2s.t.2x1+2x2≤12

x1+2x2≤84x2≤124x1≤16

x1,x2≥0

解：引進(jìn)4個新的非負(fù)變x3,x4,x5,x6使不等式變?yōu)榈仁?標(biāo)準(zhǔn)形為：minzˊ

=-2x1-3x2+0·x3+0·x4+0·x5+0·x6

s.t.2x1+2x2+x3=12

x1+2x2+x4=184x2+x5=124x1+x6=16

x1,x2,x3,x4,x5,x6≥0如何化成標(biāo)準(zhǔn)型線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件(2)的方程組中找出一個解，使目標(biāo)函數(shù)(1)達(dá)到最大值（或者最小值）。線性規(guī)劃的圖解法線性規(guī)劃的基本概念線性規(guī)劃的圖解法線性規(guī)劃的基本概念

可行解(FeasibleSolution)----任一滿足約束條件的一組決策變量的數(shù)值；

目標(biāo)函數(shù)等值線(Objectivefunctonline)----位于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值。

可行域(FeasibleRegion)----所有可行解組成的集合，也稱為可行解集；例3

用圖解法求解線性規(guī)劃問題線性規(guī)劃的圖解法

對于簡單的線性規(guī)劃問題---只有兩個決策變量的線性規(guī)劃問題,我們通過圖解法可以對它進(jìn)行求解。

求圖解法的步驟：建立坐標(biāo)系，將約束條件在圖上表示確立可行域繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向確定最優(yōu)解：當(dāng)求目標(biāo)函數(shù)的最大值時，沿著目標(biāo)函數(shù)值增大的方向平移等值線，當(dāng)平移直線剛要離開可行域時的“最后交點(diǎn)”，即為最優(yōu)解(既滿足約束，又使目標(biāo)函數(shù)值最大的點(diǎn))。當(dāng)求目標(biāo)函數(shù)的最小值時，沿著目標(biāo)函數(shù)值減小的方向平移等值線，當(dāng)平移直線剛要離開可行域時的“最后交點(diǎn)”，即為最優(yōu)解(既滿足約束，又使目標(biāo)函數(shù)值最大的點(diǎn))。線性規(guī)劃的圖解法x1x2ox1-1.9x2=3.8(≤)x1+1.9x2=3.8(≥)x1-1.9x2=-3.8(≥)x1+1.9x2=11.4(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2x1+x2

（7.6，2）DmaxZminZ此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域線性規(guī)劃的圖解法建立坐標(biāo)系，將約束條件在圖上表示確立可行域確定最優(yōu)解：沿著目標(biāo)函數(shù)值增大的方向平移等值線，當(dāng)平移直線剛要離開可行域時的“最后交點(diǎn)”時，“最后交點(diǎn)”即為最優(yōu)解。繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向x1x2ox1-1.9x2=3.8(≤)x1+1.9x2=3.8(≥)x1-1.9x2=-3.8(≥)x1+1.9x2=11.4(≤)（7.6，2）DL0：0=3x1+5.7x2

maxZ（3.8，4）34.2=3x1+5.7x2

藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏蚓€性規(guī)劃的圖解法繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向確定最優(yōu)解：沿著目標(biāo)函數(shù)值增大的方向平移等值線，當(dāng)平移直線剛要離開可行域時的“最后交點(diǎn)”時，“最后交點(diǎn)”即為最優(yōu)解。246x1x2246無界解(無最優(yōu)解)例4x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ線性規(guī)劃的圖解法確定最優(yōu)解：沿著函數(shù)值增大的方向平移等值線，與可行域時的“最后交點(diǎn)”為最優(yōu)解。繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向x1x2O10203040102030405050無可行解(即無最優(yōu)解)例5線性規(guī)劃的圖解法

圖解法簡單、直觀，便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義。通過圖解法了解線性規(guī)劃有幾種解的形式(唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解)

作圖的關(guān)鍵有三點(diǎn)：

(1)可行域要畫正確

(2)目標(biāo)函數(shù)增加的方向不能畫錯

(3)目標(biāo)函數(shù)的直線怎樣平行移動線性規(guī)劃的圖解法x1x2o（7.6，2）D可行域可行域是多邊形可行域是多邊形，有界集246x1x2246x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)可行域是多邊形，但無界可行域是多邊形x1x2O10203040102030405050可行域是空集可行域是空集x1x2o17.2=2x1+x2

Lo：0=2x1+x2

（7.6，2）DmaxZminZ此點(diǎn)是唯一最優(yōu)解可行域線性規(guī)劃的最優(yōu)解若存在，定在可行域的某頂點(diǎn)最優(yōu)解唯一，最優(yōu)解在可行域的一個頂點(diǎn)x1x2o（7.6，2）DL0：0=3x1+5.7x2

maxZ（3.8，4）34.2=3x1+5.7x2

藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(yōu)解可行域

若在兩個頂點(diǎn)同時得到最優(yōu)解，則在這兩點(diǎn)的連線上的任一點(diǎn)都是最優(yōu)解。線性規(guī)劃的最優(yōu)解若存在，定在可行域的某頂點(diǎn)最優(yōu)解在可行域的某頂點(diǎn)246x1x2246無界解(無最優(yōu)解)x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ可行域無界，最優(yōu)解無界無最優(yōu)解（可行域無界）x1x2O10203040102030405050無可行解(即無最優(yōu)解)無最優(yōu)解（無可行解）可行域是空集，無最優(yōu)解

（1）線性規(guī)劃的所有可行解構(gòu)成的可行域一般是多邊形（兩維以上的多邊形是多面體），有些可行域是無界的；（2）若存在最優(yōu)解，則一定在可行域的某頂點(diǎn)得到；（3）若在兩個頂點(diǎn)上同時得到最優(yōu)解，則在這兩點(diǎn)的連線上的任一點(diǎn)都是最優(yōu)解。（4）若可行域無界，則可能發(fā)生最優(yōu)解無界的情況；（5）若可行域是空集，此時無最優(yōu)解。由圖解法可看到

上述理論具有普遍意義，對于兩個以上變量的線性規(guī)劃問題都成立。圖解法雖然直觀、簡便等優(yōu)點(diǎn)，在變量多的情況下，即在多維的情況下，它就無能為力了。因此，需要介紹一種代數(shù)方法----單純形法，為了以后介紹方便討論，需要研究一下線性規(guī)劃的簡單性質(zhì)和概念。由圖解法可看到可行解（或容許解）:

滿足約束條件的解x=(x1,x2,···,xn)T

稱為線性規(guī)劃的可行解;可行域：所有可行解的集合稱為可行解集或可行域。3.最優(yōu)解:

使得目標(biāo)函數(shù)取到最小值的可行解稱為線性規(guī)劃的最優(yōu)可行解，簡稱為最優(yōu)解或者解。

線性規(guī)劃的標(biāo)準(zhǔn)形為：線性規(guī)劃的基本概念

上述理論具有普遍意義，對于兩個以上變量的線性規(guī)劃問題都成立。圖解法雖然直觀、簡便等優(yōu)點(diǎn)，在變量多的情況下，即在多維的情況下，它就無能為力了。因此，需要介紹一種代數(shù)方法----單純形法，為了以后介紹方便討論，需要研究一下線性規(guī)劃的簡單性質(zhì)和概念。由圖解法可看到可行解（或容許解）:

滿足約束條件的解x=(x1,x2,···,xn)T

稱為線性規(guī)劃的可行解;可行域：所有可行解的集合稱為可行解集或可行域。3.最優(yōu)解:

使得目標(biāo)函數(shù)取到最小值的可行解稱為線性規(guī)劃的最優(yōu)可行解，簡稱為最優(yōu)解或者解。

線性規(guī)劃的標(biāo)準(zhǔn)形為：線性規(guī)劃的基本概念基:

假設(shè)A

是約束方程組的系數(shù)矩陣,秩為

m,

一定存在m階非奇異子矩陣B()，是線性規(guī)劃的一個基，也稱為基矩陣。

稱Pj(j=1,2,···,m)為基向量,線性規(guī)劃的基本概念矩陣B是由m

個線性無關(guān)的列向量組成,則A中稱B是不失一般性,可假設(shè):與基向量Pj

相對應(yīng)的變量xj

(j=1,2,···,m)為基變量,其他的變量稱為非基變量。

為了進(jìn)一步討論線性規(guī)劃的解,研究Ax=b的求解問題。設(shè)A

的秩為m,則B=(P1,P2,···,Pm)是一個基，線性規(guī)劃的基本概念因m<n,所以它有無窮多個解。即xB=(x1,x2,···,xm)T,

則Ax=b可改寫為：不妨假設(shè)A=(P1,P2,···,Pn)中前m

列線性無關(guān)，設(shè)xB

是對應(yīng)于基B的基變量,5.基本解：

若令(2.1)式中的非基變量xm+1=···=xn=0,

求出一個解x=(x1,x2,···,xm,0,···,0)T,這個解的非0分量的數(shù)目不大于方程個數(shù)m,稱x

為基本解。線性規(guī)劃的基本概念當(dāng)基本解中有一個或者一個以上的基變量是0時，稱這個基本解是退化的基本解；否則稱為非退化的基本解?；究尚薪?

滿足非負(fù)約束條件的基本解稱為基本可行解.

基本可行解的非0分量的數(shù)目不大于m,都是非負(fù)的。7.可行基:

基本可行解對應(yīng)的基稱為可行基.

約束方程組Ax=b基本可行解的數(shù)目以上提到的幾種解的概念,可用如下圖來表示:基解可行解基本可行解線性規(guī)劃的基本概念至多是

個.基本可行解的個數(shù)不超過基本解的個數(shù)，基本解至多

個例求解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個，其中基矩陣只有9個，即線性規(guī)劃的基本概念的所有基矩陣和基本解。線性規(guī)劃的基本概念取定基矩陣,

相應(yīng)的基變量是x1,x4,非基變量是x2,x3,x5,

在約束條件中令非基變量x2,x3,x5都取0，從中解出基變量

從而得到一個基本解不是可行解不是可行基線性規(guī)劃的基本概念取定基矩陣相應(yīng)的基變量是x4,x5,非基變量是x1,x2,x3,

在約束條件中令非基變量x1,x2,x3,都取0，從中解出基變量

從而得到一個基本解可行解是可行基.基本可行解對于其他基矩陣對應(yīng)的基本解，可以類似的求出。閉半空間：稱

為正閉半空間，稱

為負(fù)閉半空間。

H+和H-統(tǒng)稱為閉半空間。多面體或多面凸集：有限個閉半空間的交多胞形或多面凸體：有界且非空的多面體。

線性規(guī)劃的基本性質(zhì)閉半空間是凸的多胞形極點(diǎn)：設(shè)S是凸集，

,不存在S

中的另外兩個點(diǎn)

和

，及

，使

,則稱x是凸集S的極點(diǎn)，或稱頂點(diǎn)。定理：設(shè)

,秩為m,且

則x為凸集的頂點(diǎn)的充要條件是

R是凸集

線性規(guī)劃的基本性質(zhì)闡明了基本可行解與可行域的頂點(diǎn)之間一一對應(yīng)的關(guān)系x為的一個基本可行解。推論1：若線性規(guī)劃的可行域R={x

|Ax=b,x

0}是非空的，推論2:

若線性規(guī)劃存在有限的最優(yōu)解，推論3:

線性規(guī)劃的可行域R有有限多個頂點(diǎn)。

線性規(guī)劃的基本性質(zhì)定理

(線性規(guī)劃的基本定理)(1)

若線性規(guī)劃存在可行解,則一定存在基本可行解;(2)

若線性規(guī)劃存在最優(yōu)解,則一定存在最優(yōu)的。基本可行解

R的頂點(diǎn)基本可行解

R的頂點(diǎn)基本可行解最多個若線性規(guī)劃存在最優(yōu)解,必定在某頂點(diǎn)取到可行域R的頂點(diǎn)基本可行解則它至少有一個頂點(diǎn)。R的頂點(diǎn)是有限最優(yōu)解。則至少存在一個根據(jù)以上討論得到如下的結(jié)論：

結(jié)論1：線性規(guī)劃的可行域是凸集,它可以是有界的,也可以是無界的區(qū)域;僅有有限個頂點(diǎn)(至多)。

結(jié)論2：線性規(guī)劃的每一個基本可行解對應(yīng)于可行域的一個頂點(diǎn).若線性規(guī)劃有最優(yōu)解,必定可在某頂點(diǎn)取到。

結(jié)論3：如果一個線性規(guī)劃存在多個最優(yōu)解,那么至少有兩個相鄰的頂點(diǎn)處是線性規(guī)劃的最優(yōu)解。

結(jié)論4：如果有一個頂點(diǎn)處可行解的目標(biāo)值比其它相鄰頂點(diǎn)的可行解的目標(biāo)值小的話，那么它就是最優(yōu)解。

線性規(guī)劃的基本性質(zhì)

可行域的頂點(diǎn)個數(shù)是有限的(不超過Cnm

個)，采用“枚舉法”找出所有基本可行解，然后一一比較它們的目標(biāo)函數(shù)值的大小，最終可以找到最優(yōu)解。但當(dāng)m、n的數(shù)目相當(dāng)大時，這種辦法實際上是行不通的。

線性規(guī)劃的基本性質(zhì)因此，我們還要繼續(xù)討論一種方法，通過逐步迭代保證能逐步改進(jìn)并最終求出最優(yōu)解。1947年,美國學(xué)者GeorgeDantzig(丹齊格)提出了求解線性規(guī)劃的單純形法,為線性規(guī)劃的推廣奠定了基礎(chǔ)。從可行域的一個頂點(diǎn)(基本可行解)開始,轉(zhuǎn)移到另一個頂點(diǎn)

(另一個基本可行解);

轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善(逐步變優(yōu))

當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時,也就得到了最優(yōu)解?；舅枷雴渭冃畏▽τ跇?biāo)準(zhǔn)線性規(guī)劃問題(簡寫為LP):A=(aij)mn,rank(A)=m

單純形法的基本原理將A分解成[B,N],使B為基矩陣,N為非基矩陣，

設(shè)求基本解是基本可行解。令xN=0是基本解。若相應(yīng)的目標(biāo)函數(shù)值為記

現(xiàn)在分析如何從一個基本可行解x(0)出發(fā)，求一個改進(jìn)的基本可行解x(1)

。單純形法的基本原理假設(shè)已知一個基本可行解x(0)，

若初始基本可行解x(0)不是最優(yōu)解，找一個新的基本可行解。任意可行解xx?形式找到基本可行解并使x(1)

找改進(jìn)的基本可行解：設(shè)x是任意可行解，目標(biāo)函數(shù)f在點(diǎn)x處的值為單純形法的基本原理記是非基變量的指標(biāo)集相應(yīng)于矩陣A的分解A=[B,N],給定一個基矩陣Bx可寫為對任意一個可行解處的目標(biāo)函數(shù)值為單純形法的基本原理其中是非基變量的指標(biāo)集，以及xk就從非基變量變成了基變量在(1)中，如果則，x(0)是最優(yōu)解；

如果此時令(xk是進(jìn)基變量)f就在變??；當(dāng)xk由0變此時x是基本可行解x(0)為正數(shù)時，對任意一個可行解處的目標(biāo)函數(shù)值為單純形法的基本原理xk就從非基變量變成了基變量(xk

是進(jìn)基變量)

如果有多個則記令當(dāng)xk由0變?yōu)檎龜?shù)時，f在變??；1.確定進(jìn)基變量xk

假設(shè)記和是m維列向量，，把按分量寫出，即單純形法的基本原理取此時方程組的解變?yōu)閷?yīng)的xk

就是進(jìn)基變量

當(dāng)由零變?yōu)檎龜?shù)后，函數(shù)值變小新得到的點(diǎn)是

因為基變量個數(shù)總是為m,所以一個進(jìn)基之后還必須有一個離基。下面我們來考慮如何選擇離基變量。單純形法的基本原理在新得到的點(diǎn)，目標(biāo)函數(shù)值是基變量原則：保證新得到的點(diǎn)是基本可行解原則：保證新得到的點(diǎn)是基本可行解如果，取任何正值時，總成立如果為保證只須2.確定離基變量

單純形法的基本原理如果存在多個i，使得為保證只須每個

取值后，原來的基變量當(dāng)xk趨于正無窮時，目標(biāo)函數(shù)值趨于負(fù)無窮，因此解無界因此，因此，由某個正數(shù)變?yōu)?，就是離基變量，于是得到新的基本可行解重復(fù)以上過程，可繼續(xù)改進(jìn)基本可行解，直到所有非基變量對應(yīng)的時為止。單純形法的基本原理基變量基變量非基變量非基變量初始的基本可行解改進(jìn)的基本可行解目標(biāo)函數(shù)值減小了進(jìn)基變量的確定離基變量的確定f0

是最優(yōu)值,當(dāng)前的基本可行解是最優(yōu)解最優(yōu)解判別定理定義：稱為判別數(shù)或檢驗數(shù)。單純形法的基本原理非基變量對應(yīng)的就可以作為最優(yōu)解的一個判別條件

若在極大化問題中,對于某個基本可行解,所有則這個基本可行解是最優(yōu)解。

若在極小化問題中,對于某個基本可行解,所有則這個基本可行解是最優(yōu)解。步驟1：找出初始可行基B，由，求得，令，確定初始基本可行解。計算目標(biāo)函數(shù)值。步驟2：對于所有非基變量，計算判別數(shù),令若，則對于所有非基變量，對基變量的判別數(shù)總是零，停止計算，當(dāng)前的基本可行解是最優(yōu)解。否則，進(jìn)行下一步。單純形法的算法步驟稱為單純形乘子由，得到.步驟3：由,得到,若，即的每一個分量均非正數(shù)，則停止計算，問題不存在有限最優(yōu)解。否則，進(jìn)行轉(zhuǎn)步驟4。步驟4：確定下標(biāo)r

為離基變量，為進(jìn)基變量。用替換，得到新的基矩陣B,返回步驟1。注：對于極大化問題，可以給出類似的步驟，只是確定進(jìn)基和離基變量的準(zhǔn)則不同。對于極大化問題，應(yīng)令單純形法的算法步驟以極小化問題為例每次迭代必出現(xiàn)下列三種情形之一(1).這時當(dāng)前的基本可行解就是最優(yōu)解。(2).這種情形下，我們知道取任何正數(shù)，總能得到可行解。所以當(dāng)無限增大時，目標(biāo)函數(shù)趨于負(fù)無窮，因此解無界。(3)，不小于零。這時求出新的基本可行解，經(jīng)迭代使目標(biāo)函數(shù)下降。單純形法的收斂性

如果迭代過程中各個基本可行解都是非退化的，即基變量的取值都是正的，則各次迭代得到的基本可行解互不相同。由于基本可行解的個數(shù)有限，因此經(jīng)有限次迭代一定可以達(dá)到最優(yōu)解。收斂性定理：對于非退化問題，單純形方法經(jīng)有限次迭代或達(dá)到最優(yōu)解，或得出無界的結(jié)論。

注：對于退化情形，可能出現(xiàn)循環(huán)迭代，我們在后面將要證明，如果最優(yōu)解存在，只要采取一定的措施，也能做到有限步收斂。單純形法的收斂性使用表格形式的單純形方法記，則標(biāo)準(zhǔn)形式等價于1.構(gòu)造單純形表標(biāo)準(zhǔn)形式的線性規(guī)劃標(biāo)準(zhǔn)形式繼續(xù)等價于把約束方程的系數(shù)置于表中，就得到了所謂的單純形表.1列cBTB-1

bB-1b右端m行B-1NIm0xNxBfn-m列m列1列1行cBT

B-1N-cNT01目標(biāo)函數(shù)值判別數(shù)基變量的值使用表格形式的單純形方法1.構(gòu)造單純形表A中若存在m階的單位矩陣表格容易構(gòu)造xBfzk-ckymkyrky1k

……

zj-cj…zm+1–cm+10…0…0……ymj…ymm+11…0…0

……

…

……yrj…yrm+10…1…0

……

…

……y1j…y1m+10…0…1初始單純形表……………………………………………………使用表格形式的單純形方法1.構(gòu)造單純形表

xk是進(jìn)基變量，是離基變量；主元把xk

所對應(yīng)的列向量pk變成所對應(yīng)的列向量，即是單位向量。把xk和

的位置對換，zk-ckymkyrky1k

……

zj-cj…zm+1–cm+10…0…0……ymj…ymm+11…0…0

……

…

……yrj…yrm+10…1…0

……

…

……y1j…y1m+10…0…1……………………………………………………使用表格形式的單純形方法2.高斯主元消去法主元將yrk

變?yōu)?，yik(

i≠r)以及zk–ck都變?yōu)?把pk變成對應(yīng)的單位向量？作業(yè):P1575.15.2對應(yīng)的新的目標(biāo)函數(shù)值即為：使用表格形式的單純形方法2.高斯主元消去法以yrk

為主元素進(jìn)行Gauss消元:將第r

行每個元素除以yrk

:將第r

行每個元素乘以–yik/yrk

加到第i行(i=1,···,m,

i≠r)將第r

行每個元素乘以–(zk–ck)

/yrk

加到檢驗數(shù)行經(jīng)過Gauss消元后，針對于新基B1

的基本可行解為：使用表格形式的單純形方法2.高斯主元消去法步驟3：在所有j>0,j∈RN

中，若有一個j

對應(yīng)的系數(shù)列向量

yj0，則此問題沒有有限最優(yōu)解，停止計算，否則轉(zhuǎn)步驟4；使用表格形式的單純形方法3.單純形表的單純形法的算法步驟步驟1：找出初始可行基，確定初始基本可行解，建立初始單純形表；步驟2：檢查對應(yīng)于非基變量的檢驗數(shù)j=zj-cj,j∈RN,若所有

j0,j∈RN,則已得到最優(yōu)解,停止計算;否則轉(zhuǎn)步驟3步驟4：根據(jù)max{j|j>0,j∈RN}=k,確定xk

為進(jìn)基變量。確定xr

為離基變量(即為新基的非基變量),轉(zhuǎn)步驟6；步驟5：再根據(jù)步驟6：以yrk

為主元素進(jìn)行Gauss消元，轉(zhuǎn)步驟2。使用表格形式的單純形方法3.單純形表的單純形法的算法步驟例1.

利用單純形算法求解如下的線性規(guī)劃問題。解：

1.寫出線性規(guī)劃的標(biāo)準(zhǔn)型使用表格形式的單純形方法3.單純形表的算例A中存在4階單位矩陣選取作為基變量，得到一個基本可行解

2.max{1,

2}=3=2,所以x2為進(jìn)基變量.3.p2的坐標(biāo)有正分量存在，因為3與x6

那一行相對應(yīng)，所以x6為離基變量；故x2對應(yīng)列與x6對應(yīng)行的相交處的4為主元素；xBx1x2x3x4x5

x6

221000120100400010040001x3x4x5x61281612

23c

-2-30000

64--30000

cB00004.

以“4”為主元素Gauss消去，進(jìn)行行初等變換xBx1x2x3x4x5

x6

x3x4x5x2c

-2-30000

cB000-3

0100-1/26

20000-3/4324--010001/434000101610010-1/22這行除以4xBx1x2x3x4x5x6

221000120100400010040001x3x4x5x61281612

23c

-2-30000

64--30000

cB0000這行不變第4行的-1/2加到這行第4行的-1/2加到這行第4行的-3/4加到檢驗數(shù)行

5.max{1}=2=1,所以x1為進(jìn)基變量.6.p1的坐標(biāo)有正分量存在，因為2與x4

那一行相對應(yīng)，所以x4為離基變量；故x1對應(yīng)列與x4對應(yīng)行的相交處的1為主元素；7.

以“1”為主元素Gauss消元，進(jìn)行行初等變換xBx1x2x3x4x5

x6

x3x1x5x2c

-2-30000

cB0-20-30

01-201/22

000-201/44--412010001/43000-412810010-1/22第2行的-4倍加到該行xBx1x2x3x4x5x6

c

-2-30000

cB000-3第2行的-2倍加到該行第4行的-2加到檢驗數(shù)行x3x4x5x2

0100-1/26

20000-3/4010001/434000101610010-1/22324--這行不變這行不變退化現(xiàn)象：有兩個或更多的相同時，在相同對應(yīng)的變量中選擇下標(biāo)最大的那個基變量為離基變量因為4與x3

，

x5那一行相對應(yīng)，所以x5為離基變量;故x6對應(yīng)列與x5對應(yīng)行的相交處的2為主元素；

9.p6的坐標(biāo)有正分量存在，

8.max{6}=1/4=6,所以x6為進(jìn)基變量.xBx1x2x3x4x5

x6

x3x1x5x2c

-2-30000

cB0-20-30

01-201/22

000-201/44--412010001/43000-412810010-1/22注：

這時出現(xiàn)了退化問題。即有兩個或更多的相同時，在相同對應(yīng)的變量中選擇下標(biāo)最大的那個基變量為換出變量；同時如果出現(xiàn)有兩個或更多的檢驗數(shù)σ相同時，在相同σ

對應(yīng)的變量中選擇下標(biāo)最小的那個基變量為進(jìn)基變量，這樣會避免出現(xiàn)“死循環(huán)”的現(xiàn)象。10.

以“2”為主元素Gauss消元，進(jìn)行行初等變換xBx1x2x3x4x5x6

x3x1x6x2c

-2-30000

cB0-20-30

01-1-1/400

000-3/2-1/800101/2-1/802000-21/21410001/404該行除以2xBx1x2x3x4x5

x6

c

-2-30000

cB0-20-3第3行的-1/4倍加到該行第3行的-1/8加到檢驗數(shù)行x3x1x5x20

01-201/22

000-201/4010001/43000-412810010-1/224--412第3行的1/4加到該行第3行的-1/8加到該行所有檢驗數(shù)都小于等于0，當(dāng)前的基本可行解是最優(yōu)解xBx1x2x3x4x5

x6

x3x1x6x2c

-2-30000

cB0-20-30

01-1-1/400

000-3/2-1/800101/2-1/802000-21/21410001/404所有檢驗數(shù)都小于等于0，當(dāng)前的基本可行解x=(4,2,0,0,0,4)T是最優(yōu)解原問題的最優(yōu)解是x=(4,2)T，最優(yōu)值是f=2*4+3*2=14例2.利用單純形算法求解如下的線性規(guī)劃問題。解：

1.化為標(biāo)準(zhǔn)型得到：A中存在3階單位矩陣選取作為基變量，得到一個基本可行解

2.max{2}=2=2,所以x2為進(jìn)基變量.3.p2的坐標(biāo)有正分量存在，因為2與x6

那一行相對應(yīng)，所以x6為離基變量；故x2對應(yīng)列與x6對應(yīng)行的相交處的2為主元素；建立單純形表xBx1

x2x3

x4x5

x6

x4x5x6c

1-21000

cB0001

1-210010-12-1-12-400142-14010810--20004.

以“2”為主元素進(jìn)行Gauss消去，即進(jìn)行行初等變換xBx1x2x3x4x5

x6

x4x5x6c

1-21000

cB0001

1-210010-12-1-12-400142-14010810--2000xBx1x2x3x4x5

x6

x4x5x2c

1-21000

cB00-23/2

0010-1/2800300-1-1/21-2001/223/202011/210--5--這行除以2第3行的1/2加到該行第3行的-1/2加到該行第3行的-1倍加到檢驗數(shù)行

5.max{3}=3=3,所以x3

為進(jìn)基變量.6.p3的坐標(biāo)有正分量存在，因為5與x5

那一行相對應(yīng)，所以x5為離基變量；故x3對應(yīng)列與x5對應(yīng)行的相交處的2為主元素；7.

以“2”為主元素進(jìn)行Gauss消去，即進(jìn)行行初等變換xBx1x2x3x4x5x6

x4x5x2c

1-21000

cB00-2xBx1x2x3x4x5x6

x4x3x2c

1-21000

cB01-23/2

0010-1/28-9/4000-3/2-7/4110011123/401011/45第2行加到該行這行除以2這行不變第2行的-3/2倍加到檢驗數(shù)行3/2

0010-1/283/202011/210-1/21-2001/22--5--00300-1所有檢驗數(shù)都小于等于0，當(dāng)前的基本可行解是最優(yōu)解xBx1x2x3x4x5

x6

x4x3x2c

1-21000

cB01-23/2

0010-1/28-9/4000-3/2-7/4110011123/401011/45檢驗數(shù)全部小于等于0，于是得到最優(yōu)解：

x=(0,12,5,8)T目標(biāo)函數(shù)的最小值為：f=-19例3.利用單純形算法求解如下的線性規(guī)劃問題。解：

x6

，x7

，x5對應(yīng)的是單位矩陣，可選擇作為基變量，建立單純形表，利用主元消去法，進(jìn)行迭代。minx6+x7

s.t.x1

+x2

-

x3

+x6

=

2x1-x2

-

x4

+x7

=1x1+x5=3xj≥0,j=1,2,…,7xBx1x2x3x4x5x6

x7

11-100101-10-10011000100x6x7x5213

20-1-1000cB110minx6+x7

s.t.x1

+x2

-

x3

+x6

=

2x1-x2

-

x4

+x7

=1x1+x5=3xj≥0,j=1,2,……,7c

000001

1

此時的基矩陣B不是單位矩陣，檢驗數(shù)能否從表格中直接計算？答案是肯定的！第二個問題：單純性方法的例3xBx1x2x3x4x5x6

x7

11-100101-10-10011000100x6x7x5213

20-1-100002

-1101-11-10-1