工程優(yōu)化方法 第五章

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

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

B、C、D四種不同的設(shè)備上加工。按工藝資料規(guī)定，單件產(chǎn)品在不同設(shè)備上加工所需要的臺(tái)時(shí)如下表所示，企業(yè)決策者應(yīng)如何安排生產(chǎn)計(jì)劃，使企業(yè)總的利潤(rùn)最大？線性規(guī)劃問(wèn)題的應(yīng)用當(dāng)前第6頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)解：設(shè)x1、x2分別為甲、乙兩種產(chǎn)品的產(chǎn)量，則數(shù)學(xué)模型為：線性規(guī)劃問(wèn)題的應(yīng)用當(dāng)前第7頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)第五章線性規(guī)劃本章主要內(nèi)容：§1線性規(guī)劃的簡(jiǎn)介和應(yīng)用舉例§2線性規(guī)劃的數(shù)學(xué)模型及圖解法§3線性規(guī)劃的基本概念和基本性質(zhì)§4單純形法§5線性規(guī)劃的對(duì)偶理論與對(duì)偶單純形法當(dāng)前第8頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)目標(biāo)函數(shù)：約束條件：線性規(guī)劃數(shù)學(xué)模型的一般形式線性規(guī)劃問(wèn)題的數(shù)學(xué)模型當(dāng)前第9頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

線性規(guī)劃的數(shù)學(xué)模型由三個(gè)要素構(gòu)成決策變量Decisionvariables目標(biāo)函數(shù)Objectivefunction約束條件Constraints當(dāng)前第10頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)目標(biāo)函數(shù)：約束條件：線性規(guī)劃問(wèn)題的數(shù)學(xué)模型其特征是：(1)問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；(2)問(wèn)題的約束條件是一組多個(gè)決策變量的線性不等式或等式。

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

從線性規(guī)劃數(shù)學(xué)模型的一般形式看當(dāng)前第11頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

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

0(i=1,2,···,m)當(dāng)前第12頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)線性規(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ù)矩陣當(dāng)前第13頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)線性規(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)形的其它形式當(dāng)前第14頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎ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)形的其它形式當(dāng)前第15頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

一般情況下

,為正整數(shù),分別表示約束條件的個(gè)數(shù)和決策變量的個(gè)數(shù),為價(jià)值向量,

為決策向量,通常

為已知常數(shù)。

實(shí)際上，具體問(wèn)題的線性規(guī)劃數(shù)學(xué)模型是各式各樣的,需要把它們化成標(biāo)準(zhǔn)型,并借助于標(biāo)準(zhǔn)型的求解方法進(jìn)行求解。稱m為線性規(guī)劃的階數(shù),稱n為線性規(guī)劃的維數(shù)。線性規(guī)劃的標(biāo)準(zhǔn)形當(dāng)前第16頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

（1）目標(biāo)函數(shù)求最小值；（2）決策變量非負(fù)；（3）約束條件都是等式；（4）常數(shù)項(xiàng)（右端向量）非負(fù)線性規(guī)劃標(biāo)準(zhǔn)形的特點(diǎn)當(dāng)前第17頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(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)換當(dāng)前第18頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

若約束方程組為不等式約束條件為“”形式的不等式,則在“”號(hào)的左邊加入非負(fù)的松弛變量;把原“”形的不等式變?yōu)榈仁?

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式稱為松弛變量相應(yīng)的松弛變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)取值為0。如何化成標(biāo)準(zhǔn)形當(dāng)前第19頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

約束方程的轉(zhuǎn)換：由不等式轉(zhuǎn)換為等式稱為剩余變量相應(yīng)的剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)取值為0。如何化成標(biāo)準(zhǔn)形當(dāng)前第20頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

若存在取值無(wú)約束的變量，可令

其中：

變量的轉(zhuǎn)換若，可令，顯然如何化成標(biāo)準(zhǔn)形當(dāng)前第21頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)例1:

試將如下線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形任何形式的線性規(guī)劃問(wèn)題都可以化成標(biāo)準(zhǔn)形?，F(xiàn)舉例如下：如何化成標(biāo)準(zhǔn)形當(dāng)前第22頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)解：令x3=x4-x5,x4,x50,

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

,(2)式左端減去非負(fù)剩余變量x7,則可將上述線性規(guī)劃問(wèn)題化成如下的標(biāo)準(zhǔn)形:如何化成標(biāo)準(zhǔn)形當(dāng)前第23頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)例2:

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

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

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

x1,x2≥0

解：引進(jìn)4個(gè)新的非負(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)型當(dāng)前第24頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)線性規(guī)劃問(wèn)題求解線性規(guī)劃問(wèn)題，就是從滿足約束條件(2)的方程組中找出一個(gè)解，使目標(biāo)函數(shù)(1)達(dá)到最大值（或者最小值）。線性規(guī)劃的圖解法線性規(guī)劃的基本概念當(dāng)前第25頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)線性規(guī)劃的圖解法線性規(guī)劃的基本概念

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

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

目標(biāo)函數(shù)等值線(Objectivefunctionline)----位于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值。當(dāng)前第26頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)例3

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

對(duì)于簡(jiǎn)單的線性規(guī)劃問(wèn)題---只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題,我們通過(guò)圖解法可以對(duì)它進(jìn)行求解。當(dāng)前第27頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)求圖解法的步驟：建立坐標(biāo)系，將約束條件在圖上表示確立可行域繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向確定最優(yōu)解：當(dāng)求目標(biāo)函數(shù)的最大值時(shí)，沿著目標(biāo)函數(shù)值增大的方向平移等值線，當(dāng)平移直線剛要離開(kāi)可行域時(shí)的“最后交點(diǎn)”，即為最優(yōu)解(既滿足約束，又使目標(biāo)函數(shù)值最大的點(diǎn))。當(dāng)求目標(biāo)函數(shù)的最小值時(shí)，沿著目標(biāo)函數(shù)值減小的方向平移等值線，當(dāng)平移直線剛要離開(kāi)可行域時(shí)的“最后交點(diǎn)”，即為最優(yōu)解(既滿足約束，又使目標(biāo)函數(shù)值最大的點(diǎn))。線性規(guī)劃的圖解法當(dāng)前第28頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)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)平移直線剛要離開(kāi)可行域時(shí)的“最后交點(diǎn)”時(shí)，“最后交點(diǎn)”即為最優(yōu)解。繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向當(dāng)前第29頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)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)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏蚓€性規(guī)劃的圖解法繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向確定最優(yōu)解：沿著目標(biāo)函數(shù)值增大的方向平移等值線，當(dāng)平移直線剛要離開(kāi)可行域時(shí)的“最后交點(diǎn)”時(shí)，“最后交點(diǎn)”即為最優(yōu)解。當(dāng)前第30頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)246x1x2246無(wú)界解(無(wú)最優(yōu)解)例4x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ線性規(guī)劃的圖解法確定最優(yōu)解：沿著函數(shù)值增大的方向平移等值線，與可行域時(shí)的“最后交點(diǎn)”為最優(yōu)解。繪制目標(biāo)函數(shù)的等值線族，確定目標(biāo)函數(shù)增大和減小的方向當(dāng)前第31頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)x1x2O10203040102030405050無(wú)可行解(即無(wú)最優(yōu)解)例5線性規(guī)劃的圖解法當(dāng)前第32頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

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

(1)可行域要畫正確

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

(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)線性規(guī)劃的圖解法當(dāng)前第33頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)x1x2o（7.6，2）D可行域可行域是凸多邊形可行域是凸多邊形，有界集當(dāng)前第34頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)246x1x2246x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)可行域是凸多邊形但無(wú)界可行域是凸多邊形當(dāng)前第35頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)x1x2O10203040102030405050可行域是空集可行域是空集當(dāng)前第36頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)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)解在可行域的一個(gè)頂點(diǎn)當(dāng)前第37頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(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)解這種情形為有無(wú)窮多最優(yōu)解可行域

若在兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則在這兩點(diǎn)的連線上的任一點(diǎn)都是最優(yōu)解。線性規(guī)劃的最優(yōu)解若存在，定在可行域的某頂點(diǎn)最優(yōu)解在可行域的某頂點(diǎn)當(dāng)前第38頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)246x1x2246無(wú)界解(無(wú)最優(yōu)解)x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ可行域無(wú)界，最優(yōu)解無(wú)界無(wú)最優(yōu)解（可行域無(wú)界）當(dāng)前第39頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)x1x2O10203040102030405050無(wú)可行解(即無(wú)最優(yōu)解)無(wú)最優(yōu)解（無(wú)可行解）可行域是空集，無(wú)最優(yōu)解當(dāng)前第40頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

（1）線性規(guī)劃的所有可行解構(gòu)成的可行域一般是凸多邊形，有些可行域是無(wú)界的；（2）若存在最優(yōu)解，則一定在可行域的某頂點(diǎn)得到；（3）若在兩個(gè)頂點(diǎn)上同時(shí)得到最優(yōu)解，則在這兩點(diǎn)的連線上的任一點(diǎn)都是最優(yōu)解。（4）若可行域無(wú)界，則可能發(fā)生最優(yōu)解無(wú)界的情況；（5）若可行域是空集，此時(shí)無(wú)最優(yōu)解。由圖解法可看到當(dāng)前第41頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

上述理論具有普遍意義，對(duì)于兩個(gè)以上變量的線性規(guī)劃問(wèn)題都成立。圖解法雖然直觀、簡(jiǎn)便等優(yōu)點(diǎn)，在變量多的情況下，即在多維的情況下，它就無(wú)能為力了。因此，需要介紹一種代數(shù)方法----單純型法，為了以后介紹方便討論，需要研究一下線性規(guī)劃的簡(jiǎn)單性質(zhì)和簡(jiǎn)單概念。由圖解法可看到當(dāng)前第42頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)第五章線性規(guī)劃本章主要內(nèi)容：§1線性規(guī)劃的簡(jiǎn)介和應(yīng)用舉例§2線性規(guī)劃的數(shù)學(xué)模型及圖解法§3線性規(guī)劃的基本概念和基本性質(zhì)§4單純形法§5線性規(guī)劃的對(duì)偶理論與對(duì)偶單純形法當(dāng)前第43頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)可行解（或容許解）:

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

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

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

線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形為：線性規(guī)劃的基本概念當(dāng)前第44頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)基:

假設(shè)A

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

m,B是矩陣A

中由m

列構(gòu)成的非奇異子矩陣(B的行列式的值不為0），則稱B是線性規(guī)劃問(wèn)題的一個(gè)基。

稱Pj(j=1,2,···,m)為基向量,與基向量Pj

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

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

個(gè)線性無(wú)關(guān)的列向量組成,不失一般性,可假設(shè):當(dāng)前第45頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

為了進(jìn)一步討論線性規(guī)劃問(wèn)題的解,研究Ax=b的求解問(wèn)題。假設(shè)該方程組系數(shù)矩陣A

的秩為m,因m<n,所以它有無(wú)窮多個(gè)解。假設(shè)前m

個(gè)變量的系數(shù)列向量是線性無(wú)關(guān)的，這時(shí)Ax=b可改寫為：線性規(guī)劃的基本概念當(dāng)前第46頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)方程組(2.1)的一個(gè)基是B=(P1,P2,···,Pm),

Pj=(a1j,···,amj)T,(j=1,2,···,m),設(shè)xB

是對(duì)應(yīng)于這個(gè)基的基向量,即：

xB=(x1,x2,···,xm)T

5.基本解：

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

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

為基本解。線性規(guī)劃的基本概念當(dāng)基本解中有一個(gè)或者一個(gè)以上的基變量是0時(shí)，稱這個(gè)基本解是退化的基本解。當(dāng)前第47頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)基本可行解:

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

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

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

約束方程組Ax=b基本解的數(shù)目至多是Cnm

個(gè).一般地講,基本可行解的數(shù)目要小于基本解的數(shù)目,至多相等.

以上提到的幾種解的概念,可用如下圖來(lái)表示:基解可行解基本可行解線性規(guī)劃的基本概念當(dāng)前第48頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)例求解:約束方程的系數(shù)矩陣為2×5矩陣r(A)=2，2階子矩陣有10個(gè)，其中基矩陣只有9個(gè)，即線性規(guī)劃的基本概念的所有基矩陣。當(dāng)前第49頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)線性規(guī)劃的基本概念取定基,矩陣

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

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

從而得到一個(gè)基本解不是可行解不是可行基當(dāng)前第50頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)線性規(guī)劃的基本概念取定基矩陣相應(yīng)的基變量是x4,x5,非基變量是x1,x2,x3,

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

從而得到一個(gè)基本解可行解是可行基基本可行解當(dāng)前第51頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)極點(diǎn)：設(shè)S是凸集，

,不存在S

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

和

，及

，使

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

，其秩為m,且

,,則x為凸集的一個(gè)頂點(diǎn)的充要條件是

x為的一個(gè)基本可行解。R是凸集

線性規(guī)劃的基本性質(zhì)闡明了基本可行解與可行域的頂點(diǎn)之間一一對(duì)應(yīng)的關(guān)系當(dāng)前第52頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)推論1：若線性規(guī)劃的可行域R={x

|Ax=b,x

0}是非空的，則它至少有一個(gè)頂點(diǎn)。推論2:

若線性規(guī)劃存在有限的最優(yōu)解，則至少存在一個(gè)

R的頂點(diǎn)是有限最優(yōu)解。推論3:

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

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

(線性規(guī)劃問(wèn)題的基本定理)(1)

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

若線性規(guī)劃問(wèn)題存在最優(yōu)解,則一定存在最優(yōu)的基本可行解?；究尚薪?/p>

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

R的頂點(diǎn)基本可行解最多個(gè)線性規(guī)劃問(wèn)題若有最優(yōu)解,必定在某頂點(diǎn)取到當(dāng)前第53頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)根據(jù)以上討論得到如下的結(jié)論：

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

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

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

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

線性規(guī)劃的基本性質(zhì)當(dāng)前第54頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

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

的數(shù)目相當(dāng)大時(shí)，這種辦法實(shí)際上是行不通的。因此，我們還要繼續(xù)討論一種方法，通過(guò)逐步迭代保證能逐步改進(jìn)并最終求出最優(yōu)解。

線性規(guī)劃的基本性質(zhì)當(dāng)前第55頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)作業(yè):P1575.15.2當(dāng)前第56頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)極點(diǎn)：設(shè)S是凸集，

,不存在S

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

和

，及

，使

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

，其秩為m,且

,,則x為凸集的一個(gè)頂點(diǎn)的充要條件是

x為的一個(gè)基本可行解。

線性規(guī)劃的基本性質(zhì)當(dāng)前第57頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)Ox1x28060②④①90最優(yōu)解Q2(75,15)Q1Q3Q4Q5Q6Q7Q8①②③③當(dāng)前第58頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)推論1：若線性規(guī)劃的可行域R={x

|Ax=b,x

0}是非空的，則它至少有一個(gè)頂點(diǎn)。推論2:

若線性規(guī)劃存在有限的最優(yōu)解，則至少存在一個(gè)

R的頂點(diǎn)是有限最優(yōu)解。推論3:

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

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

(線性規(guī)劃問(wèn)題的基本定理)(1)

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

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

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

R的頂點(diǎn)基本可行解最多個(gè)線性規(guī)劃問(wèn)題若有最優(yōu)解,必定在某頂點(diǎn)取到當(dāng)前第59頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

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

的數(shù)目相當(dāng)大時(shí)，這種辦法實(shí)際上是行不通的。因此，我們還要繼續(xù)討論一種方法，通過(guò)逐步迭代保證能逐步改進(jìn)并最終求出最優(yōu)解。

線性規(guī)劃的基本性質(zhì)當(dāng)前第60頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)61從定理1和2知，尋求最優(yōu)解，就可從基本可行解（頂點(diǎn)）出發(fā)，在基本可行解（頂點(diǎn)）之間變換，如果L.P.有最優(yōu)解，則最優(yōu)解一定可在某一基本可行解（頂點(diǎn)）上得到。這個(gè)方法可用來(lái)求有任意多個(gè)變量的線性規(guī)劃模型！Ox1x2Q2(75,15)60②③④④①最優(yōu)解Q1Q3Q4Q5Q6Q7Q8當(dāng)前第61頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)第五章線性規(guī)劃本章主要內(nèi)容：§1線性規(guī)劃的簡(jiǎn)介和應(yīng)用舉例§2線性規(guī)劃的數(shù)學(xué)模型及圖解法§3線性規(guī)劃的基本概念和基本性質(zhì)§4單純形法§5線性規(guī)劃的對(duì)偶理論與對(duì)偶單純形法當(dāng)前第62頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)1947年,美國(guó)學(xué)者GeorgeDantzig(丹齊格)提出了求解線性規(guī)劃的單純形法,為線性規(guī)劃的推廣奠定了基礎(chǔ)。從可行域的一個(gè)頂點(diǎn)(基本可行解)開(kāi)始,轉(zhuǎn)移到另一個(gè)頂點(diǎn)(另一個(gè)基本可行解);轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善(逐步變優(yōu))當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí),問(wèn)題也就得到了最優(yōu)解?；舅枷雴渭冃畏ó?dāng)前第63頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)對(duì)于標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題(簡(jiǎn)寫為L(zhǎng)P):A=(aij)mn,rank(A)=m

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

設(shè)求基本解基本可行解令xN=0是基本解。若當(dāng)前第64頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)相應(yīng)的目標(biāo)函數(shù)值為記

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

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

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

找改進(jìn)的基本可行解：當(dāng)前第65頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)設(shè)x是任意可行解，目標(biāo)函數(shù)f在點(diǎn)x處的值為單純形法的基本原理記是非基變量的指標(biāo)集相應(yīng)于矩陣A的分解A=[B,N],B稱為基矩陣x可寫為當(dāng)前第66頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)對(duì)任意一個(gè)可行解處的目標(biāo)函數(shù)值為單純形法的基本原理其中是非基變量的下標(biāo)集，以及xk就從非基變量變成了基變量式(1)中，如果則，x(0)是最優(yōu)解；

如果則令xk由0變?yōu)檎龜?shù)時(shí)，f就在變??；(xk是進(jìn)基變量)當(dāng)前第67頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)對(duì)任意一個(gè)可行解處的目標(biāo)函數(shù)值為單純形法的基本原理xk就從非基變量變成了基變量(xk

是進(jìn)基變量)根據(jù)（1）,當(dāng)取值相同時(shí)，越大，目標(biāo)函數(shù)下降越多，因此選擇(進(jìn)基變量)。

式(1)中，如果有多個(gè)則記令xk由0變?yōu)檎龜?shù)時(shí)，f在變?。划?dāng)前第68頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)1.確定進(jìn)基變量xk

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

就是進(jìn)基變量

當(dāng)由零變?yōu)檎龜?shù)后，函數(shù)值變小當(dāng)前第69頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)新得到的點(diǎn)是

因?yàn)榛兞總€(gè)數(shù)總是為m,所以一個(gè)進(jìn)基之后還必須有一個(gè)離基。下面我們來(lái)考慮如何選擇離基變量。單純形法的基本原理在新得到的點(diǎn)，目標(biāo)函數(shù)值是基變量原則：保證新得到的點(diǎn)是基本可行解當(dāng)前第70頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)原則：保證新得到的點(diǎn)是基本可行解當(dāng)時(shí)，取任何正值時(shí)，總成立對(duì)某個(gè)i,當(dāng)時(shí)，取任何正值時(shí)，總成立2.確定離基變量

單純形法的基本原理而當(dāng)時(shí)，為了保證取因此，為使，應(yīng)令

取值后，原來(lái)的基變量就是離基變量，于是得到新的基本可行解當(dāng)xk趨于正無(wú)窮時(shí)，目標(biāo)函數(shù)值趨于負(fù)無(wú)窮，因此解無(wú)界當(dāng)前第71頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)重復(fù)以上過(guò)程，可以進(jìn)一步改進(jìn)基本可行解，直到所有的時(shí)為止。單純形法的基本原理基變量基變量非基變量非基變量初始的基本可行解改進(jìn)的基本可行解目標(biāo)函數(shù)值減小了進(jìn)基變量的確定離基變量的確定f0

是最優(yōu)值,當(dāng)前的基本可行解是最優(yōu)解當(dāng)前第72頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)最優(yōu)解判別定理

稱為判別數(shù)或檢驗(yàn)數(shù)。單純形法的基本原理所有的就可以作為最優(yōu)解的一個(gè)判別條件

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

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

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

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

注：對(duì)于退化情形，可能出現(xiàn)循環(huán)迭代，我們?cè)诤竺鎸⒁C明，如果最優(yōu)解存在，只要采取一定的措施，也能做到有限步收斂。單純形法的收斂性當(dāng)前第77頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)使用表格形式的單純形方法記，則標(biāo)準(zhǔn)形式等價(jià)于1.構(gòu)造單純形表標(biāo)準(zhǔn)形式的線性規(guī)劃標(biāo)準(zhǔn)形式繼續(xù)等價(jià)于當(dāng)前第78頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)把約束方程的系數(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階的單位矩陣xBf當(dāng)前第79頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)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初始單純形表……………………………………………………使用表格形式的單純形方法1.構(gòu)造單純形表

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

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

的位置對(duì)換，當(dāng)前第80頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)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)?(yk

=B-1

pk

)把pk變成對(duì)應(yīng)的單位向量？當(dāng)前第81頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)對(duì)應(yīng)的新的目標(biāo)函數(shù)值即為：使用表格形式的單純形方法2.高斯主元消去法以yrk

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

行每個(gè)元素除以yrk

:將第r

行每個(gè)元素乘以–yik/yrk

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

i≠r)將第r

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

/yrk

加到檢驗(yàn)數(shù)行當(dāng)前第82頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)經(jīng)過(guò)Gauss消元后，針對(duì)于新基B1

的基本可行解為：使用表格形式的單純形方法2.高斯主元消去法當(dāng)前第83頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)步驟3：在所有j>0,j∈RN

中，若有一個(gè)j

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

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

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

為進(jìn)基變量。當(dāng)前第84頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)確定xr

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

為主元素進(jìn)行Gauss消元，轉(zhuǎn)步驟2。使用表格形式的單純形方法3.單純形表的單純形法的算法步驟當(dāng)前第85頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)例1.

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

1.寫出線性規(guī)劃的標(biāo)準(zhǔn)型使用表格形式的單純形方法3.單純形表的算例A中存在4階單位矩陣選取作為基變量，得到一個(gè)基本可行解當(dāng)前第86頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

2.max{1,

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

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

x6

221000120100400010040001x3x4x5x61281612

23c

-2-30000

64--30000

cB0000當(dāng)前第87頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)4.

以“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加到檢驗(yàn)數(shù)行當(dāng)前第88頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

那一行相對(duì)應(yīng)，所以x4為離基變量；故x1對(duì)應(yīng)列與x4對(duì)應(yīng)行的相交處的1為主元素；當(dāng)前第89頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)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加到檢驗(yàn)數(shù)行x3x4x5x2

0100-1/26

20000-3/4010001/434000101610010-1/22324--這行不變這行不變退化現(xiàn)象：有兩個(gè)或更多的相同時(shí)，在相同對(duì)應(yīng)的變量中選擇下標(biāo)最大的那個(gè)基變量為離基變量當(dāng)前第90頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)因?yàn)?與x3

，

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

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

8.max{6}=1/4=6,所以x6為進(jìn)基變量.當(dāng)前第91頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)xBx1x2x3x4x5

x6

x3x1x5x2c

-2-30000

cB0-20-30

01-201/22

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

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

對(duì)應(yīng)的變量中選擇下標(biāo)最小的那個(gè)基變量為進(jìn)基變量，這樣會(huì)避免出現(xiàn)“死循環(huán)”的現(xiàn)象。當(dāng)前第92頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎ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加到檢驗(yàn)數(shù)行x3x1x5x20

01-201/22

000-201/4010001/43000-412810010-1/224--412第3行的1/4加到該行第3行的-1/8加到該行所有檢驗(yàn)數(shù)都小于等于0，當(dāng)前的基本可行解是最優(yōu)解當(dāng)前第93頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)xBx1x2x3x4x5

x6

x3x1x6x2c

-2-30000

cB0-20-30

01-1-1/400

000-3/2-1/800101/2-1/802000-21/21410001/404所有檢驗(yàn)數(shù)都小于等于0，當(dāng)前的基本可行解x=(4,2,0,0,0,4)T是最優(yōu)解原問(wèn)題的最優(yōu)解是x=(4,2)T，最優(yōu)值是f=2*4+3*2=14當(dāng)前第94頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)例2.利用單純形算法求解如下的線性規(guī)劃問(wèn)題。解：

1.化為標(biāo)準(zhǔn)型得到：A中存在3階單位矩陣選取作為基變量，得到一個(gè)基本可行解當(dāng)前第95頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

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

x2x3

x4x5

x6

x4x5x6c

1-21000

cB0001

1-210010-12-1-12-400142-14010810--2000當(dāng)前第96頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)4.

以“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倍加到檢驗(yàn)數(shù)行當(dāng)前第97頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)

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

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

那一行相對(duì)應(yīng)，所以x5為離基變量；故x3對(duì)應(yīng)列與x5對(duì)應(yīng)行的相交處的2為主元素；當(dāng)前第98頁(yè)\共有177頁(yè)\編于星期日\(chéng)22點(diǎn)7.

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

x4x5x2c

1-2