線性規(guī)劃求解演示文稿

線性規(guī)劃求解演示文稿99/081*當(dāng)前1頁，總共46頁。（優(yōu)選）線性規(guī)劃求解99/082*當(dāng)前2頁，總共46頁。（4）基：設(shè)A為線性規(guī)劃模型約束條件系數(shù)矩陣（mn，m<n），而B為其mm子矩陣，若|B|≠0，則稱B為該線性規(guī)劃模型的一個基。（5）基變量：基中每個向量所對應(yīng)的變量稱為基變量。（6）非基變量：模型中基變量之外的變量稱為非基變量。（7）基解（基解）：令模型中所有非基變量X非基=0后，由模型約束方程組 n

aijxj=bi(i=1,2,……,m)得到的一組解。

j=1（8）基本可行解（基可行解）：在基解中，同時又是可行解的解稱為基可行解。（9）可行基：對應(yīng)于基可行解的基稱為可行基。99/083*當(dāng)前3頁，總共46頁。Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0

Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T

等。設(shè)B=

1001，令，則|B|=1≠0,令x1=x2=0，則x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基變量令B=1110

x1x3

，則令x2=x4=0，則x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解標(biāo)準(zhǔn)化99/084*當(dāng)前4頁，總共46頁。復(fù)習(xí)思考題：

1.可行解和可行域有怎樣的關(guān)系？

2.一個標(biāo)準(zhǔn)化LP模型，最多可有多少個基？

3.基解是如何定義的？怎樣才能得到基解？

4.可行解、基解、基可行解三者之間有什么關(guān)系？在LP模型中是否一定存在？

5.什么是可行基？99/085*當(dāng)前5頁，總共46頁。1.2

線性規(guī)劃問題的圖解方法*利用作圖方法求解。例：maxz=2x1+3x2 s.t2x1+2x212----------①

x1+2x28----------② 4x116----------③ 4x212----------④ x10,x20

99/086*當(dāng)前6頁，總共46頁。x1x222468460①②④③Z=6Z=0(4,2)Zmax99/087*當(dāng)前7頁，總共46頁。AAB唯一解無窮多解無界解無可行解99/088*當(dāng)前8頁，總共46頁。步驟：（1）作平面直角坐標(biāo)系，標(biāo)上刻度； （2）做出約束方程所在直線，確定可行域； （3）做出一條目標(biāo)函數(shù)等值線，判定優(yōu)化方向； （4）沿優(yōu)化方向移動，確定與可行域相切的點(diǎn)，確定最優(yōu) 解，并計(jì)算最優(yōu)值。討論一：模型求解時，可得到如下幾種解的狀況： （1）唯一最優(yōu)解：只有一點(diǎn)為最優(yōu)解點(diǎn)，簡稱唯一解； （2）無窮多最優(yōu)解：有許多點(diǎn)為最優(yōu)解點(diǎn)，簡稱無窮多解； （3）無界最優(yōu)解：最優(yōu)解取值無界，簡稱無界解 ； （4）無可行解：無可行域，模型約束條件矛盾。討論二：LP模型求解思路： （1）若LP模型可行域存在，則為一凸形集合； （2）若LP模型最優(yōu)解存在，則其應(yīng)在其可行域頂點(diǎn)上找到； （3）頂點(diǎn)與基本解、基本可行解的關(guān)系：99/089*當(dāng)前9頁，總共46頁。復(fù)習(xí)思考題：1.LP模型的可行域是否一定存在?2.圖解中如何去判斷模型有唯一解、無窮多解、無界解和無可行解？3.LP模型的可行域的頂點(diǎn)與什么解具有對應(yīng)關(guān)系？4.你認(rèn)為把所有的頂點(diǎn)都找出來，再通過比較目標(biāo)函數(shù)值大小的方式找出最優(yōu)解，是否是最好的算法？為什么？99/0810*當(dāng)前10頁，總共46頁。1.3

單純形法的基本原理（SimplexMethod）

兩個概念： （1）凸集：對于集合C中任意兩點(diǎn)連線上的點(diǎn)，若也在C內(nèi)，則稱C為凸集。

或者，任給X1C，X2C，X=X1+(1-)X2

C(0<<1)，則C為凸集。凸集非凸集99/0811*當(dāng)前11頁，總共46頁。（2）頂點(diǎn)：凸集中不成為任意兩點(diǎn)連線上的點(diǎn)，稱為凸集頂點(diǎn)?；蛘?，

設(shè)C為凸集，對于XC，不存在任何X1C，X2C，且X1≠X2，使得X=X1+(1-)X2C，(0<<1)，則X為凸集頂點(diǎn)。XXXXX99/0812*當(dāng)前12頁，總共46頁。定理1：若線性LP模型存在可行解，則可行域?yàn)橥辜?。證明：設(shè)maxz=CX st. AX=b X0并設(shè)其可行域?yàn)镃，若X1、X2為其可行解，且X1≠X2，則X1C，X2C，即AX1=b，AX2=b，X10，X20，又X為X1、X2連線上一點(diǎn)，即X=X1+(1-)X2C，(0<<1)，∴AX=AX1+(1-)AX2=b+(1-)b=b,(0<<1)，且X0，

∴XC，

∴C為凸集。

三個基本定理：99/0813*當(dāng)前13頁，總共46頁。引理：線性規(guī)劃問題的可行解X=(x1,x2,······,xn)T為基本可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量線性獨(dú)立。證：（1）必要性：X基本可行解X的正分量所對應(yīng)的系數(shù)列向量線性獨(dú)立可設(shè)X=(x1,x2,······,xk,0,0,······,0)T，若X為基本可行解，顯然，由基本可行解定義可知x1,x2,······,xk所對應(yīng)的系數(shù)列向量P1,P2,······,Pk應(yīng)該線性獨(dú)立。（2）充分性：X的正分量所對應(yīng)的系數(shù)列向量線性獨(dú)立X為基本可行解若A的秩為m，則X的正分量的個數(shù)km；當(dāng)k=m時，則x1,x2,······,xk的系數(shù)列向量P1,P2,······,Pk恰好構(gòu)成基，∴X為基本可行解。當(dāng)k<m時，則必定可再找出m-k個列向量與P1,P2,······,Pk一起構(gòu)成基，∴X為基本可行解。99/0814*當(dāng)前14頁，總共46頁。證：用反證法X非基本可行解X非凸集頂點(diǎn)（1）必要性：X非基本可行解X非凸集頂點(diǎn)不失一般性，設(shè)X=(x1,x2,······,xm,0,0,······,0)T，為非基本可行解，∵X為可行解，∴pjxj=b，j=1n即

pjxj=b······(1)j=1m又

X是非基本可行解，∴P1,P2,······,Pm線性相關(guān)，即有1P1+2P2+······+mPm=0，其中1，2，······，m不全為0，兩端同乘≠0，得1P1+2P2+······+mPm=0，······（2）定理2：線性規(guī)劃模型的基本可行解對應(yīng)其可行域的頂點(diǎn)。99/0815*當(dāng)前15頁，總共46頁。由(1)+(2)得(x1+1)P1+(x2+2)P2+······+(xm+m)Pm=b由(1)-(2)得(x1-1)P1+(x2-

2)P2+······+(xm

-m)Pm=b令X1=(x1+1，x2+2，······，xm+m，0，·····，0)T

X2=(x1-

1，x2-

2，······，xm-

m，0，·····，0)T取充分小,使得xj

j0，則X1、X2均為可行解，但X=0.5X1+(1-0.5)X2，∴X是X1、X2連線上的點(diǎn)，∴X非凸集頂點(diǎn)。99/0816*當(dāng)前16頁，總共46頁。（2）充分性：X非凸集頂點(diǎn)X非基本可行解設(shè)X=(x1,x2,······,xr,0,0,······,0)T為非凸集頂點(diǎn)，則必存在Y、Z兩點(diǎn)，使得X=Y+(1-)Z，(0<<1)，且Y、Z為可行解或者xj=yj+(1-)zj(0<<1)，（j=1,2,······,n)，yj0，zj0∵>0,1->0，當(dāng)xj=0，必有yj=zj=0∴

pjyj=j=1n

pjyj=b······(1)j=1r

pjzj=j=1n

pjzj=b······(2)j=1r

(yj-zj)pj=0j=1r,(1)-(2),得即(y1-z1)P1+(y2-z2)P2+······+(yr

-zr)Pr=099/0817*當(dāng)前17頁，總共46頁?！遈、Z為不同兩點(diǎn)，∴yj-zj不全為0，∴

P1,P2,······,Pr線性相關(guān)，∴X非基本可行解。99/0818*當(dāng)前18頁，總共46頁。34O(3,3)C(4,2)662X1+2X2+X3=124X2+X5=124X1+X4=16XA=(0,3,6,16,0)TXO=(0,0,12,16,12)TXB=(3,3,0,4,0)TXC=(4,2,0,0,4)TXD=(4,0,4,0,12)TADBX1X299/0819*當(dāng)前19頁，總共46頁。z1=CX1=CX0-C=zmax-C

，z2=CX2=CX0+C=zmax+C∵z0=zmaxz1

，z0=zmaxz2

，∴z1=z2=z0

，即X1

、X2也為最優(yōu)解，若X1、X2仍不是頂點(diǎn)，可如此遞推，直至找出一個頂點(diǎn)為最優(yōu)解。從而，必然會找到一個基本可行解為最優(yōu)解。定理3：若線性規(guī)劃模型有最優(yōu)解，則一定存在一個基本可行解為最優(yōu)解。證：設(shè)X0=(x10,x20,······,xn0)T是線性規(guī)劃模型的一個最優(yōu)解，

z0=zmax=CX0 若X0非基本可行解，即非頂點(diǎn)，只要取充分小，則必能找出X1=X0-0

，X2=X0

+0

，即X1

、X2為可行解，99/0820*當(dāng)前20頁，總共46頁。單純形法的計(jì)算步驟：初始基本可行解新的基本可行解最優(yōu)否？STOPYN99/0821*當(dāng)前21頁，總共46頁。1．初始基本可行解的確定：設(shè)模型nmaxz=cjxj

j=1ns.t.aijxjbi

（i=1,2,……,m)

j=1xj0（j=1,2,……,n)

n mmaxz=cjxj+0·xsi

j=1 I=1ns.t.aijxj+xsi=bi

（i=1,2,……,m)

j=1xj0，xsi0

（j=1,2,……,n;i=1,2,……,m)化標(biāo)準(zhǔn)形∴初始基本可行解X=(0,0,······,0,b1,b2,······,bm)T，n個099/0822*當(dāng)前22頁，總共46頁。2．從一個基本可行解向另一個基本可行解轉(zhuǎn)換不失一般性，設(shè)基本可行解X0=(x10,x20,······,xm0,0,······,0)T，前m個分量為正值，秩為m，其系數(shù)矩陣為P1P2……PmPm+1……Pj……Pnb10……0 a1,m+1·····a1j

·····a1n

b1

0

1……0 a2,m+1·····a2j

·····a2n b200……1 am,m+1·····amj

·····amn

bm…………………………………………………………∴

pjxj0=j=1n

pixi0=b······(1)i=1m99/0823*當(dāng)前23頁，總共46頁。又P1P2……Pm為一個基，任意一個非基向量Pj可以以該組向量線性組合表示，即

Pj

=a1jP1+a2jP2+······+amj

Pm ，即

Pj

=

aij

pi

，

移項(xiàng)，兩端同乘>0，有(Pj-

aij

pi

)=0·········(2)i=1mi=1m(1)+(2)：(xi0-

aij)Pi+

Pj=b，取充分小，使所有xi0-

aij

0，從而i=1mX1=(x10-

a1j

,x20-

a2j,······,xm0-

amj,0,······,,······,0)T也是可行解。當(dāng)取

=min—aij

>0=—，則X1的前m個分量至少有一個xL1為0。xi0aijaljxL0i∴P1

,P2,······,PL-1,PL+1,······Pm,Pj線性無關(guān)。99/0824*當(dāng)前24頁，總共46頁?！郮1

也為基本可行解。3.最優(yōu)解的判別依題義z0=cjxj0

=cixi0

i=1mj=1nz0=cjxj1

=ci(xi0-

aij)

+

cj

i=1mj=1n

=ci(xi0-

aij)

+(cj

-

ciaij)=z0+

ji=1mi=1m99/0825*當(dāng)前25頁，總共46頁。因>0，所以有如下結(jié)論：(1)對所有j，當(dāng)j0

，有z1z0，即z0為最優(yōu)值，X0為最優(yōu)解；(2)對所有j，當(dāng)j0

，但存在某個非基變量k=0，則對此Pk作為新基向量得出的解X1

，應(yīng)有z1=

z0，故z1

也為最優(yōu)值，從而X1為最優(yōu)解，且為基本可行解，∴X0、X1連線上所有的點(diǎn)均為最優(yōu)解，因此該線性規(guī)劃模型

具有無窮多解；(3)若存在某個j

0，但對應(yīng)aij0，則因當(dāng)時，有z1，∴該線性規(guī)劃模型具有無界解。99/0826*當(dāng)前26頁，總共46頁。1.4 單純形法的計(jì)算及示例1.4.1單純形法幾何解釋---頂點(diǎn)尋優(yōu)例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x23標(biāo)準(zhǔn)化s.tx1+x2+x3=3 x1+2x24 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4) （1）初始基本可行解的選擇：-----坐標(biāo)原點(diǎn)處 令x1=x2=0,由

x1+x2+x3=3

x1+2x2+x4=4

（2）是否為最優(yōu)解的判定:-----計(jì)算檢驗(yàn)數(shù) 若

x1↑1,則

x3↓1,x4↓1,

σ1=2-（01+01）=2 σj=△z=cj-zj=cj-ciaij，稱σj為檢驗(yàn)數(shù)。x3=3-(x1+x2)x4=4-(x1+2x2)

解得X=(0,0,3,4)T99/0827*當(dāng)前27頁，總共46頁。若

x2↑1,則

x3↓1,x4↓2,

σ2=3-(01+02)=3 ****當(dāng)所有檢驗(yàn)數(shù)均有σj

0時，則為最優(yōu)解。****（3）找新的頂點(diǎn)（基本可行解）： 直觀看，x2↑1,則z↑3，∴應(yīng)找A點(diǎn)，即增加x2。x2可增加多少？需要保證x3=3-(x1+x2)0

x4=4-(x1+2x2)0， ∴

x2=min（3/1，4/2），從而 x3=1-(x1/2-x4

/2）

x2=2-(x1/2+x4/2)

令x1=x4=0，則新的基本可行解為X=(0，2，1，0)T重復(fù)上述過程，直至所有檢驗(yàn)數(shù)

σj

0。99/0828*當(dāng)前28頁，總共46頁。繼續(xù)迭代：找新的頂點(diǎn)（基本可行解）： 若x1↑1,則z↑1/2，∴應(yīng)找B點(diǎn)，即增加x1。

x1可增加多少？需要保證x3=1-(x1/2-x4/2)0

x2=2-(x1/2+x4/2)0， ∴

x1=min（2，4），從而 x1=2-(2x3-x4)

x2=1-(-x3+x4), 則新的基本可行解為X=(2，1，0，0)T若

x1↑1,則

x3↓1/2,x2↓1/2,

σ1=2-（01/2+31/2）=1/2若

x4↑1,則

x3↓-1/2,x2↓1/2,

σ4=0-（0(-1/2)+31/2）=-3/2σ3=-1, σ4=-1, zmax=799/0829*當(dāng)前29頁，總共46頁。①②O

C

A

BX1X2(0,2)(3,0)(2,1)3499/0830*當(dāng)前30頁，總共46頁。Cj→x1x2x3x4XBbCB1 1 1 01 2 012 3 0 034x3x400cj-zj23003/1=34/2=21/2 0 1 -1/21/2 1 01/2x3x212cj-zj1/2 00-3/203241 0 2 -10 1 -11x1x221cj-zj0 0 -1 -1231.4.2單純形法計(jì)算：θi99/0831*當(dāng)前31頁，總共46頁。單純形法計(jì)算過程總結(jié)：（1）化標(biāo)準(zhǔn)形，列初始單純形表；（2）計(jì)算檢驗(yàn)數(shù)：σj=△z=cj-zj=cj-ciaij（3）最優(yōu)性判斷：當(dāng)所有檢驗(yàn)數(shù)均有σj

0時，則為最優(yōu)解。否則 迭代求新的基本可行解。（4）迭代： 入基變量：取max{σj0}=

σk→xk 出基變量：取min{θi=bi/aikaik>0}=θl

→x(l)

主元素：[alk] 新單純表：pk=單位向量注：當(dāng)所有檢驗(yàn)數(shù)σj

0時，若存在非基變量檢驗(yàn)數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。i=1m99/0832*當(dāng)前32頁，總共46頁。例：minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23標(biāo)準(zhǔn)化s.tx1+x2

-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4)

maxz=-2x1-3x2+0x3-Mx4-Mx5

s.tx1+x2

-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5) 引進(jìn)人工變量，及M——非常大正系數(shù)，模型轉(zhuǎn)變?yōu)檫@種處理方法稱為大M法，以下則可完全按單純形法求解。1．大M法1.5單純形法進(jìn)一步討論99/0833*當(dāng)前33頁，總共46頁。Cj→x1x2x3x4XBbCB1 1 -1 101 2 001

-2 -3 0 -M-M

34x4x5-M-Mcj-zj-2+2M-3+3M-M03/1=34/2=21/2 0 -1 1-1/21/2 1 001/2x4x212cj-zj-1/2+M/2

0-M

0

3/2-M/2-M-3241 0 -2 2-10 1 1-11x1x221cj-zj0 0 -1 1-M1-M-2-3θix5099/0834*當(dāng)前34頁，總共46頁。說明：

當(dāng)所有j0

，但存在人工變量x人=0，則可以判定該模型有無可行解。采用大M法求解線性規(guī)劃模型時，如果模型中各個系數(shù)與M的值非常接近時，若手工計(jì)算時，不會出現(xiàn)任何問題。如果利用計(jì)算機(jī)程序求解，則大M表現(xiàn)為一個較大的數(shù)字，由于綜合計(jì)算的影響，導(dǎo)致檢驗(yàn)數(shù)出現(xiàn)符號誤差，引起判斷錯誤，從而使大M方法失效。在這種情況下，可采用下面的兩階段法進(jìn)行計(jì)算。99/0835*當(dāng)前35頁，總共46頁。2．兩階段法：

例：minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23標(biāo)準(zhǔn)化s.tx1+x2

-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4)

obj:maxz=-x4-x5

s.tx1+x2

-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5) (1)

第一階段，構(gòu)造判斷是否存在可行解的模型：

用單純形法求解，若zmax=0，表明該模型有可行解，則可進(jìn)入第二階段，求原模型最優(yōu)解。99/0836*當(dāng)前36頁，總共46頁。Cj→x1x2x3x4XBbCB1 1 -1 101 2 001

0 0 0 -1-1

34x4x5-1-1cj-zj2

3-103/1=34/2=21/2 0 -1 1-1/21/2 1 001/2x4x212cj-zj

1/20-101-10241 0 -2 2-10 1 1-11x1x221cj-zj0 0 0 -1-100θix5099/0837*當(dāng)前37頁，總共46頁。

(2)第二階段，將原目標(biāo)函數(shù)引入最終單純形表，繼續(xù)迭代：

maxz=-2x1-3x2+0x3Cj→x1x2x3XBbCB11 0 0 0 -1

-2 -3 0 21x1x2-2-3cj-zj0

0-199/0838*當(dāng)前38頁，總共46頁。1.4.3程序求解（1）用LINDO軟件求解（2）用EXCEL工具求解使用EXCEL中數(shù)據(jù)處理工具———規(guī)劃求解。99/0839*當(dāng)前39頁，總共46頁。1.6改進(jìn)單純形法單純形法迭代過程可用矩陣變換描述如下：設(shè)

maxz=CXst AXb X0分解

maxz=CBXB+CNXN+0XSst BXB+NXN+IXS=b XB,XN,,XS0約束方程兩端同乘B-1，則可得如下表達(dá)式：式中，B——最終表中基對應(yīng)的矩陣，

N——初始表與最終表中均為非基對應(yīng)的矩陣，

I——單位矩陣A=[BN]

maxz=CBXB+CNXN+0XSst B-1BXB+B-1NXN+B-1XS=B-1

b XB,XN,,XS0——對應(yīng)最終單純形表的模型99/0840*當(dāng)前40頁，總共46頁。用單純形表表示如下：XS=bB N IXB=b′I N′

B-1初始表

XB

XN

XS

cj-zj0,······,0

N

S最終表

XB

XN

XS

cj-zj

B

N 0,······,0表中，b′=B-1bN′=B-1N

或者Pj′=B-1PjN′=CN-CBB-1

N或者j′=Cj-CBB-1

PjS′=-CBB-1········99/0841*當(dāng)前41頁，總共46頁。⑴化標(biāo)準(zhǔn)形：B-1

new

=I，XB=b，⑵求檢驗(yàn)數(shù)：N

=CN-CBB-1

new

N，S

=-CBB-1

new

⑶最優(yōu)性判別：①所有

0，X人≠0，無可行解；②所有

0，X人=0，存在

N=0，無窮多解；③所有

0，X人=0，不存在N=0，唯一解；④否則(存在

>0)，轉(zhuǎn)⑷，⑷取max

xk

，為換入變量，計(jì)算Pk′=B-1

new

Pk，若Pk′

0無界解,

否則，計(jì)算i=bi/aik|aik>0

，取min

xL為換出變量，⑸令改進(jìn)單純形法計(jì)算步驟：99/0842*當(dāng)前42頁，總共46頁。D=1·······-a1k/aLk······00·······1/aLk······00·······-amk