線性規(guī)劃求解

線性規(guī)劃求解2006/08第1章線性規(guī)劃----1-第1頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----2-1.1.4 線性規(guī)劃問題解的有關(guān)概念設模型nmaxz=cjxj

j=1ns.t.aijxj=bi

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

j=1xj≥0（j=1,2,……,n)（1）可行解：滿足所有約束方程和變量符號限制條件的一組變量的取值。（2）可行域：全部可行解的集合稱為可行域。（3）最優(yōu)解：使目標函數(shù)達到最優(yōu)值的可行解。第2頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----3-（4）基：設A為線性規(guī)劃模型約束條件系數(shù)矩陣（mn，m<n），而B為其mm子矩陣，若|B|≠0，則稱B為該線性規(guī)劃模型的一個基。（5）基變量：基中每個向量所對應的變量稱為基變量。（6）非基變量：模型中基變量之外的變量稱為非基變量。（7）基解（基解）：令模型中所有非基變量X非基=0后，由模型約束方程組 n

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

j=1（8）基本可行解（基可行解）：在基解中，同時又是可行解的解稱為基可行解。（9）可行基：對應于基可行解的基稱為可行基。第3頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----4-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

等。設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,——非基本可行解——基本可行解標準化第4頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----5-復習思考題：

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

2.一個標準化LP模型，最多可有多少個基？

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

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

5.什么是可行基？第5頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----6-1.2

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

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

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

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

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

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

C(0<<1)，則C為凸集。凸集非凸集第11頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----12-（2）頂點：凸集中不成為任意兩點連線上的點，稱為凸集頂點?；蛘?，

設C為凸集，對于XC，不存在任何X1C，X2C，且X1≠X2，使得X=X1+(1-)X2C，(0<<1)，則X為凸集頂點。XXXXX第12頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----13-定理1：若線性LP模型存在可行解，則可行域為凸集。證明：設maxz=CX st. AX=b X0并設其可行域為C，若X1、X2為其可行解，且X1≠X2，則X1C，X2C，即AX1=b，AX2=b，X10，X20，又X為X1、X2連線上一點，即X=X1+(1-)X2C，(0<<1)，∴AX=AX1+(1-)AX2=b+(1-)b=b,(0<<1)，且X0，

∴XC，

∴C為凸集。

1.3.2

三個基本定理：第13頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----14-引理：線性規(guī)劃問題的可行解X=(x1,x2,······,xn)T為基本可行解的充要條件是X的正分量所對應的系數(shù)列向量線性獨立。證：（1）必要性：X基本可行解X的正分量所對應的系數(shù)列向量線性獨立可設X=(x1,x2,······,xk,0,0,······,0)T，若X為基本可行解，顯然，由基本可行解定義可知x1,x2,······,xk所對應的系數(shù)列向量P1,P2,······,Pk應該線性獨立。（2）充分性：X的正分量所對應的系數(shù)列向量線性獨立X為基本可行解若A的秩為m，則X的正分量的個數(shù)km；當k=m時，則x1,x2,······,xk的系數(shù)列向量P1,P2,······,Pk恰好構(gòu)成基，∴X為基本可行解。當k<m時，則必定可再找出m-k個列向量與P1,P2,······,Pk一起構(gòu)成基，∴X為基本可行解。第14頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----15-證：用反證法X非基本可行解X非凸集頂點（1）必要性：X非基本可行解X非凸集頂點不失一般性，設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ī)劃模型的基本可行解對應其可行域的頂點。第15頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----16-由(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連線上的點，∴X非凸集頂點。第16頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----17-（2）充分性：X非凸集頂點X非基本可行解設X=(x1,x2,······,xr,0,0,······,0)T為非凸集頂點，則必存在Y、Z兩點，使得X=Y+(1-)Z，(0<<1)，且Y、Z為可行解或者xj=yj+(1-)zj(0<<1)，（j=1,2,······,n)，yj0，zj0∵>0,1->0，當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=0第17頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----18-∵Y、Z為不同兩點，∴yj-zj不全為0，∴

P1,P2,······,Pr線性相關(guān)，∴X非基本可行解。第18頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----19-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)TADBX1X2第19頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----20-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仍不是頂點，可如此遞推，直至找出一個頂點為最優(yōu)解。從而，必然會找到一個基本可行解為最優(yōu)解。定理3：若線性規(guī)劃模型有最優(yōu)解，則一定存在一個基本可行解為最優(yōu)解。證：設X0=(x10,x20,······,xn0)T是線性規(guī)劃模型的一個最優(yōu)解，

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

，X2=X0

+0

，即X1

、X2為可行解，第20頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----21-單純形法的計算步驟：初始基本可行解新的基本可行解最優(yōu)否？STOPYN第21頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----22-1．初始基本可行解的確定：設模型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)化標準形∴初始基本可行解X=(0,0,······,0,b1,b2,······,bm)T，n個0第22頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----23-2．從一個基本可行解向另一個基本可行解轉(zhuǎn)換不失一般性，設基本可行解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=1m第23頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----24-又P1P2……Pm為一個基，任意一個非基向量Pj可以以該組向量線性組合表示，即

Pj

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

Pm ，即

Pj

=

aij

pi

，

移項，兩端同乘>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也是可行解。當取

=min—aij

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

,P2,······,PL-1,PL+1,······

Pm,Pj線性無關(guān)。第24頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----25-∴X1

也為基本可行解。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=1m第25頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----26-因>0，所以有如下結(jié)論：(1)對所有j，當j0

，有z1

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

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

，應有z1=z0，故z1

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

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

0，但對應aij0，則因當時，有z1，∴該線性規(guī)劃模型具有無界解。第26頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----27-1.4 單純形法的計算及示例1.4.1單純形法幾何解釋---頂點尋優(yōu)例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x23標準化s.tx1+x2+x3=3 x1+2x24 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4) （1）初始基本可行解的選擇：-----坐標原點處 令x1=x2=0,由

x1+x2+x3=3

x1+2x2+x4=4

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

x1↑1,則

x3↓1,x4↓1,

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

解得X=(0,0,3,4)T第27頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----28-若

x2↑1,則

x3↓1,x4↓2,

σ2=3-(01+02)=3 ****當所有檢驗數(shù)均有σj

0時，則為最優(yōu)解。****（3）找新的頂點（基本可行解）： 直觀看，x2↑1,則z↑3，∴應找A點，即增加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重復上述過程，直至所有檢驗數(shù)

σj

0。第28頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----29-繼續(xù)迭代：找新的頂點（基本可行解）： 若x1↑1,則z↑1/2，∴應找B點，即增加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=7第29頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----30-①②O

C

A

BX1X2(0,2)(3,0)(2,1)34第30頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----31-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單純形法計算：θi第31頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----32-單純形法計算過程總結(jié)：（1）化標準形，列初始單純形表；（2）計算檢驗數(shù)：σj=△z=cj-zj=cj-ciaij（3）最優(yōu)性判斷：當所有檢驗數(shù)均有σj

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

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

→x(l)

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

0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。i=1m第32頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----33-例：minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23標準化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) 引進人工變量，及M——非常大正系數(shù)，模型轉(zhuǎn)變?yōu)檫@種處理方法稱為大M法，以下則可完全按單純形法求解。1．大M法1.5單純形法進一步討論第33頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----34-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θix50第34頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----35-說明：

當所有j0

，但存在人工變量x人=0，則可以判定該模型有無可行解。采用大M法求解線性規(guī)劃模型時，如果模型中各個系數(shù)與M的值非常接近時，若手工計算時，不會出現(xiàn)任何問題。如果利用計算機程序求解，則大M表現(xiàn)為一個較大的數(shù)字，由于綜合計算的影響，導致檢驗數(shù)出現(xiàn)符號誤差，引起判斷錯誤，從而使大M方法失效。在這種情況下，可采用下面的兩階段法進行計算。第35頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----36-2．兩階段法：

例：minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23標準化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，表明該模型有可行解，則可進入第二階段，求原模型最優(yōu)解。第36頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----37-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/2

0-101-10241 0 -2 2-10 1 1-11x1x221cj-zj0 0 0 -1-100θix50第37頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----38-

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

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

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

0-1第38頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----39-1.4.3程序求解（1）用LINDO軟件求解（2）用EXCEL工具求解使用EXCEL中數(shù)據(jù)處理工具———規(guī)劃求解。第39頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----40-1.6改進單純形法單純形法迭代過程可用矩陣變換描述如下：設

maxz=CXst AXb X0分解

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

N——初始表與最終表中均為非基對應的矩陣，

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

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

b XB,XN,,XS0——對應最終單純形表的模型第40頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----41-用單純形表表示如下：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········第41頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----42-⑴化標準形：B-1

new

=I，XB=b，⑵求檢驗數(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

，為換入變量，計算Pk′=B-1

new

Pk，若Pk′

0無界解,

否則，計算i=bi/aik|aik>0

，取min

xL為換出變量，⑸令改進單純形法計算步驟：第42頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----43-D=1·······-a1k/aLk······00·······1/aLk······00·······-amk/aLk······1

······

······

······xL計算B-1

new=DB-1old，

b′=B-1

newb轉(zhuǎn)⑵。注：D矩陣為單位矩陣中出基變量所在單位向量以上述列向量代換。實例演算如下：第43頁，共48頁，2023年，2月20日，星期二2006/08第1章線性規(guī)劃----44-例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x23標準化s.tx1+x2+x3=3 x1+2x24 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4) x1 x2 x3 x4b1 1 1 031 2 0 14

⑴初始解：B-1

new=I，XB=(x3,，x4)T=(3，4)T,N=(1，2)=(2，3)，

計算P2′=B-1

new

P2=(1，2)T，∴換入變量：max

x2

，換出變量：i