講課教案3單純形原理

§3

單純形法(Simplex

Method)本節(jié)重點(diǎn)：檢驗(yàn)數(shù)的概念和計(jì)算最優(yōu)性判別基變換（換入變量和換出變量的確定）旋轉(zhuǎn)變換3．1

基本思想x1Q14對(duì)于一個(gè)標(biāo)準(zhǔn)型LP問(wèn)題，從一個(gè)初始基可行解出發(fā)，判斷其是否為最優(yōu)解，若是則結(jié)束；否則求一個(gè)與其“相鄰”的、改進(jìn)的基可行解。再判斷這個(gè)解是否最優(yōu)，若是則結(jié)束，否則再求一個(gè)“相鄰”的、改進(jìn)的基可行解……直至得到一個(gè)基最優(yōu)解。x24x1=1624x

=12x1+2x2=8Q302x1+3x2=0Q43Q

(4,2)2如例1，OQ1Q2或

O

Q4Q3Q2max

z

=

CX(LP)

s.t.

x

?

0

AX

=

b為說(shuō)明其基本步驟，先考慮A中有單位矩陣或其變形的標(biāo)準(zhǔn)型問(wèn)題。s.t

.=

85+

x

=

1224

x2

44

x

+

x

=

16如例1max

z

=

2x1+3x2

x1

+

2

x2

+

x3

x1

,,

x5

?

0又如max

z

=

3x1-x2-x3+

x4

-

2

x5

=

12-

x5

=

1=

13

x11s.t.-

2

x

+

x1

53x2

x

,

,

x

?

0不失一般性，在推導(dǎo)過(guò)程中，考慮有如下約束方程組的問(wèn)題：x1‘+a1m+1xm+1+…+a1nxn=b1‘+

a2m+1xm+1+…+a2nxn=b2…

…xm+

amm+1xm+1+…+amnxn=bm

‘x2即nj=m+1iij

ja

x

=

bix

+'‘(

i=1，…,m)3．2求初始基可行解‘因

bi

?

0

(

i=1，…,m),故取初始基為B(0)=(P

，P

，…,P

)，1

2

mx1，…,xm

為基變量?？傻贸跏蓟尚薪?Z

=c

b

+c

b‘

‘1

1

2

2m

m‘+…+c

b

=X(0)=(b1

，b

，…,b

，0，…,0)‘

‘

‘

T2

mmi

ic

bi

=1‘B(0)=(P3

,P4

,P5)X(0)=(0，0，8，16，12)TZ0=0基向量的下標(biāo)視約束方程而異，不一定是1,2,…,m。如例1max

z

=

2x1+3x2s.t

.2154+

x4

x=

84

x

+

x

=

16=

12

x1

+

2

x2

+

x3

x1

,,

x5

?

03．3最優(yōu)性檢驗(yàn)將X(0)是否為最優(yōu)解？如何檢驗(yàn)？nij

ji

ia

xx

=

b

-j=m+1''(

i=1，2，…,m)代入目標(biāo)函數(shù)中消去基變量：n

m

n

nij

j

j

ji

ij

j

c

xz

=

c

x

=j=m+1''-

a x

)

+c

(bj=1mi=1nj=m+1m=

i

i

j

i

ij

ji=1

j=m+1

i=1''c

a

)xc

b

+

(c

-mi=1'令s

j

=

c

j

-

ciaij

=

c

j

-

z

j

，又mi

=1z

0

=

cibi'n則

z

=

z0

+

s

j

x

jj=m+1——z

與當(dāng)前非基變量的關(guān)系nz

=

z0

+

s

j

x

j——z

與當(dāng)前非基變量的關(guān)系j=m+1由此可知，若存在s

j

>0(m+1

￡

j

￡

n)，則有xj

>0，其它非基變量仍為零的可行解，其目標(biāo)函數(shù)值z(mì)

=z0

+s

j

x

j

>z0

,這說(shuō)明當(dāng)前解不是最優(yōu)解。若所有s

j

￡

0(m+1

￡

j

￡

n)，則z0

為可行解所能取得的目標(biāo)函數(shù)最大值，說(shuō)明當(dāng)前解是最優(yōu)解。故稱(chēng)s

j

為檢驗(yàn)數(shù)。將基變量的系數(shù)0

也視為其檢驗(yàn)數(shù)，可得：最優(yōu)性判別定理：若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù)s

j

￡

0(j=1，2，…,n)，則此解是最優(yōu)解，否則不是最優(yōu)解。注意：xj的檢驗(yàn)數(shù)是當(dāng)z表示為非基變量的函數(shù)時(shí)目標(biāo)函數(shù)中xj的系數(shù)。基變量的檢驗(yàn)數(shù)為零。例1中z

=2x1+3x2

，x1

，x2為非基變量，s1=2>0，s2=3>0，X(0)不是最優(yōu)解。無(wú)窮多最優(yōu)解判別定理：X

(0)

=

(b'

,

b'

,,

b'

,0,,0)T1

2

m若B的一個(gè)基可行解，且對(duì)一切的j=m+1,...,n有為對(duì)應(yīng)于基s

j

￡

0,則線(xiàn)性規(guī)劃又存在某個(gè)非基變量的檢驗(yàn)數(shù)=

0,s

m+k問(wèn)題又無(wú)窮多最優(yōu)解。證明：xm

+

k非基變量新基可行解X

(1)新的目標(biāo)函數(shù)值不變換入X

(1)，聯(lián)線(xiàn)上的所有點(diǎn)均是最優(yōu)解。參見(jiàn)P17X

(

0

)

,兩個(gè)最優(yōu)解無(wú)界解的判別定理：1

2

m若

X

(0)

=

(b'

,b'

,,

b'

,0,,0)T為對(duì)應(yīng)于基B的一個(gè)基可行解，有一個(gè)sm+k

>0,

并且對(duì)i=1,...,m有ai,m+k

￡

0,那么線(xiàn)性規(guī)劃問(wèn)題具有無(wú)界解（無(wú)最優(yōu)解）。證明：構(gòu)造新的解i

im

+k(1)ji

,m

+kx(1)

=b'=

l=0,

j

=m

+1,,

n且j m

+k,

l

>0,-

la'x

(1)xi=1,2,…m驗(yàn)證可行性：因?yàn)閍

i

,

m

+k

<=

0,

l

>

0sm+k

>0,lfi

￥

fi

+￥z

=

z0

+lsm+k無(wú)可行解的判別：待以后將完人工變量法以后再講。x1x2+a1,m+1’xm+1+…+a1n’xn=b1’+a2,m+1’xm+1+…+a2n’xn=b2’……xm

+am,m+1’xm+1+…+amn’xn=bm’xj≥0，j=1,2,…,n將

X

(1)

代入到目標(biāo)函數(shù)中得每一個(gè)aij和bi均帶“撇”3．4

基變換j求一個(gè)改進(jìn)的、“相鄰”的可行基，一個(gè)基變量將變成非基變量（換出），一個(gè)非基變量將變成基變量（換入）。1．換入變量的確定一般，當(dāng)max

{s

j

|s

j

>0}=sk，取xk

為換入變量。例1

中，s2>s1，可取x2

為換入變量。x1b1b2?

a1kxk?

a2kxkx2…=b1-

a1kxk

?

0=b2-

a2kxk

?

0……

…xm=

bm-

amkxk

?

0bm?

amkxk2.換出變量的n確定xi

=bi

-aijx

j

(i

=1,2,,m)中，令xk>0

，j=m+1在而xj

=0(m+1

￡

j

￡

n，j

?

k)，要保持xi

?

0

(

i=1，2，…,m)，即必須likkab=

lk

ikax

￡

min

bi

a

0于是，當(dāng)

x為換出變量。lllk=

blk,

x

=

0,

xa若所有則xk

可取無(wú)窮大，問(wèn)題無(wú)最優(yōu)解。aik

￡

0,X(1)=(b

-abl2，b

-alk

lk1

1k

a

2kabl，…,0，…,

b

-alkm

mk

abl，0，…,0，

bl

，0，…，0)Talk為一個(gè)新的基可行解。新基為

B(1)=(

P1，…,

Pl-1，

Pk

，Pl+1，…,Pm)換出變量確定方法:lik

alkibb一般，計(jì)算q

=miniaika

>

0

=，第

l

個(gè)約束對(duì)應(yīng)的基變量為換出變量。例1

中，當(dāng)前解X(0)，x2

為換入變量。要使x3

=8

–

2x2

?

0x4

=16

?

0x5

=12

–

4x2

?

02x

最多取值q

=

min{8/2,-,12/4}

=

3

=x2=3，x5=0，故第3個(gè)約束中的x5

是換出變量.新的基

B(1)

=

(P3

，P4

,

P2

)，新的解

X(1)=(0，3，2，16，0)T32b3a3.5

旋轉(zhuǎn)變換由此形式很容易知新的基可行解和非基變量的檢驗(yàn)數(shù)。重復(fù)3.2~3.5步驟，直至某X(k)對(duì)應(yīng)的檢驗(yàn)數(shù)均小于等于零，X(k)就是最優(yōu)解。最優(yōu)性判別定理：若基可行解對(duì)應(yīng)的檢驗(yàn)數(shù)

j

￡

0

(

j=1，2，sj…,n)，則此解是最優(yōu)解，否則不是最優(yōu)解。換入變量的確定方法：一般，當(dāng)max

{s

j

|s

j

>0}=sk，取xk

為換入變量。換出變量確定方法:lik

alkibb一般，計(jì)算q

=miniaika

>

0

=，第

l

個(gè)約束對(duì)應(yīng)的基變量為換出變量。結(jié)論:以alk

為主元素的旋轉(zhuǎn)變換：(

l

)

:alk即'ljlk

a

，aaljl=

b'lklabiklka(i)-(

l

)

*a(i=1,2,…,m,i?l):*aik

b'ilkli'ijiklkijabab

-alj即

a

-

*a

a

，klka(0)-

(

l

)

*s

:k*s

-z'lkl'jklkjaba-

z

-alj即s

- *s

s

，§4單純形法的計(jì)算步驟本節(jié)重點(diǎn)：?jiǎn)渭冃伪恚ㄌ貏e是檢驗(yàn)數(shù)行）單純形法的計(jì)算步驟大M法兩階段法解的存在情況判別cjfic1…cmcm+1…cnqICBXBbx1…xmxm+1…xnc1c2x1x2b1b210………00a1,m+1a2,m+1…………a1na2nq1

q2…cmxmbm0…1am,m+1…amnqm-z-z

值0…0sm+1…snXB

列——基變量，CB

列——基變量的價(jià)值系數(shù)(目標(biāo)函數(shù)系數(shù))cj

行——價(jià)值系數(shù)，b

列——方程組右側(cè)常數(shù)q

列——確定換入變量時(shí)的比率計(jì)算值下面一行——檢驗(yàn)數(shù)，中間主要部分——約束方程系數(shù)4．1

單純形表用表格法求解LP，規(guī)范的表格——單純形表如下：計(jì)算步驟找出初始可行基，確定初始基可行解，建立初始單純形表。檢驗(yàn)各非基變量xj的檢驗(yàn)數(shù)，若sj

￡

0，j=m+1，…，n；則已得到最優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)入下一步。在sj

>

0，j=m+1，…，n中，若有某個(gè)sk對(duì)應(yīng)xk的系數(shù)列向量Pk￡

0，則此問(wèn)題是無(wú)界解，停止計(jì)算。否則，轉(zhuǎn)入下一步。根據(jù)max(sj

>0)=sk，確定xk為換入變量，按q

規(guī)則計(jì)算q

=min{bi/aik\aik>0}可確定第l行的基變量為換出變量。轉(zhuǎn)入下一步。以alk為主元素進(jìn)行迭代(即用高斯消去法或稱(chēng)為旋轉(zhuǎn)變換)，把xk

所對(duì)應(yīng)的列向量變換為(0，0，…，1，…，0)T，將X

列中B的第l

個(gè)基變量換為xk，得到新的單純形表，返回(2)。用單純形方法求解max

z=40x1+45x2+24x3.s.t1

2

3x

,

x

,x

?

03x1+3x2

+2x3

￡120

2x1

+3x2

+

x3

￡100max

z

=

2x1+

3x2s.t.

x1

+

2

x2

￡

84

x1￡164

x2

￡12x1，x2

?0cjfi23000qCB

XBbx1x2x3x4x5000x3x4x58161214020(

4)1000100014-3-z023000例1的初始單純形表：cjfi23000qCB

XBbx1x2x3x4x5003x3x4x22163140001100010-1/201/424--z-

92000-3/4X(0)=(0，0，8，16，12)T，

z0

=0cjfi23000qCB

XBbx1x2x3x4x5203x1x4x22831000011-40010-1/221/4-412-z-1300-201/4cjfi23000qCB

XBbx1x2x3x4x5003x3x4x22163(

1

)40001100010-1/201/424--z-92000-3/4X(1)=(0，3，2，16，0)T，

z1

=9Max

z

=

20x1

+

8x2

+

6x3￡

503x3

￡

1508x1

+

3x2

+

2x3

￡

25011

2x1,

x2

,

x3

?

04x

+2x

+

x練習(xí)§5

單純形法的進(jìn)一步討論幾種情況一、目標(biāo)函數(shù)為Min的情形三種處理方法：令Z’=

-Z

===> Max

Z’=

-CX

；求MinZ，當(dāng)所有檢驗(yàn)數(shù)cj-zj>=0時(shí)為最優(yōu)，否則要迭代，換入檢驗(yàn)數(shù)最小的那個(gè)變量，確定換出變量的方法和前面Max的情形一樣；規(guī)定檢驗(yàn)數(shù)為zj-cj，其余過(guò)程和前面Max的情形一樣。二、約束方程為“>=”或“=”的情形（加人工變量）人工變量法（確定初始可行基）：221

1

n

+2amn

xn

+

=

bma2

n

xn

+

xx

+a=

b1=

ba1n

xn

+

xn

+1a11

x1

+am1

x1

+

xn

+mx1

,,

xn

?

0,

xn

+1

,,

xn

+m

?

0人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，經(jīng)過(guò)基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中還有某個(gè)非零的人工變量，原問(wèn)題無(wú)可行解。原約束方程：AX=b加入人工變量：xn+1，…，xn+m例8min

z

=-3x1+x2+x3s.t.

x1

-

2

x2

+

x3

￡

113+

x

=

111

2

3

x1

,

x2

,x3

?

0-

2

x-

4

x

+

x

+

2

x

?

3標(biāo)準(zhǔn)型：max z’

=3x1-x2-x3s.t.=

1x1

-

2

x2

+

x3

+

x4

=

113+

x1-

2

x

x1

,

,

x5

?

05-

x

=

331

2-

4

x

+

x

+

2

x其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變x6,x7,=

11x1

-

2

x2

+

x3

+

x47+

x

=

11

361

2

3

5-

4

x

+

x

+

2

x

-

x

+

x

=

3x-

2

x

+

x1

,

,

x7

?

0這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，11，0，3，1)T不滿(mǎn)足原來(lái)的約束條件。如何使得可從

X(0)開(kāi)始，經(jīng)迭代逐步得到x6=0，x7=0的基可行解，從而求得問(wèn)題的最優(yōu)解，有兩種方法：第一階段：以人工變量之和最小化為目標(biāo)函數(shù)。

min

w

=x6+x7只要原問(wèn)題有可行解，該最小化問(wèn)題的最優(yōu)目標(biāo)函數(shù)值就是0，解得的最優(yōu)解x6=0，x7=0，對(duì)應(yīng)原問(wèn)題一個(gè)基可行解。反之若該問(wèn)題的最優(yōu)解目標(biāo)函數(shù)值大于零，則說(shuō)明原問(wèn)題無(wú)可行解。第二階段：以第一階段的最優(yōu)解(不含人工變量)為初始解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。5.3

兩階段法例8

試用兩階段法求解線(xiàn)性規(guī)劃問(wèn)題minz

=-3x1+x2+x3

x1

-

2

x2

+

x3

￡

11s.t.1+

x

=

1-

2

x1

2

3-

4

x

+

x

+

2

x

?

33

x1

,

x2

,

x3

?

0解：先在上述線(xiàn)性規(guī)劃問(wèn)題的約束方程中加入人工變量，給出第一階段的數(shù)學(xué)模型為：min

w

=

x6+x7x1-2x2+x3+x4-4

x1+

x2+2x3

-x5

+

x6=11=3-2x1

+

x3

+

x7

=1x1，…，

x7

?0第一階段的單純形表如下：cj0000011qCBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-21012[1]1000-10010001113/216-1-30100010x4x6x3101130-2-2[1]00011000-10010-1-21—1—0-100103000x4x2x3121130-2010001100-2-10210-5-204——00000111第一階段求得的結(jié)果是w

=0,最優(yōu)解是（0,1,1,12,0,0,0）T因人工變量x6=x7=0，所以(0,1,1,12,0)T

是原線(xiàn)性規(guī)劃問(wèn)題的基可行解。第二階段運(yùn)算:cj-31100qCBXBbx1x2x3x4x5011x4x2x31211[3]0-2010001100-2-104——σj-10001-311x1x2x34191000100011/302/3-2/3-1-4/3σj20001/31/3用兩階段法求下面線(xiàn)性規(guī)劃問(wèn)題的解Max Z=2x1+

x

2+

x

3s.t. 4x1+2x2+

2x

3≥42x1+4x2

≤204x1+8x2+

2x

3≤16x1，x2，x

3≥05.4

線(xiàn)性規(guī)劃問(wèn)題解的討論一、無(wú)可行解max

z=2x1+4x2x1

+x2

￡102x1

+x2

?

40x1

,x2

?0人工變量不能從基底換出，此時(shí)原線(xiàn)性規(guī)劃問(wèn)題無(wú)可行解。x1x2-cjfi0000-1CBXBbx1x2x3x4x5q0X310[1]1100101x540210-1140/2cj-zj210-10Z0=-0x11011100-1x5200-1-2-11cj-zj0-1-2-10Z1=-4020兩階段法二、退化問(wèn)題基可行解的正分量個(gè)數(shù)小于約束條件個(gè)數(shù)m。右側(cè)常數(shù)中有零時(shí)，初始解就是退化解。單純形法計(jì)算中，計(jì)算q

值時(shí)有兩個(gè)以上比值同為最小，這樣在下一次迭代中就會(huì)出現(xiàn)零值的基變量，出現(xiàn)退化解。一般，出現(xiàn)退化情況時(shí)，不必特殊處理，一般不會(huì)出現(xiàn)由于死循環(huán)得不到最優(yōu)解的情況。勃蘭特規(guī)則(P35)可避免死循環(huán)。例:max

z=3x1+4x2x1

+x2

￡402x1+x2￡60x1-x2

=0x1

,x2

?0此題初始解是退化的。最優(yōu)解也是退化解。退化解迭代中，當(dāng)換入變量取零值時(shí)目標(biāo)函數(shù)值沒(méi)有改進(jìn)，x1x2c

j

→3400-MθCBXBbx1x2x3x4x50x340111000x4602101-1-Mx50[1]-1001c

j

-

z

j3+M4-M0000x3400[2]100x46003013x101-100c

j

-

z

j07004x220011/200x4000-3/213x120101/20c

j

-

z

j00-3.500x30001-1/34x2200101/33x1201001/3c

j

-

z

j000-7/3三、有無(wú)窮多最優(yōu)解的情況最優(yōu)解中有非基變量的檢驗(yàn)數(shù)等于零的情況。以這種非基變量作為換入變量，迭代可求得另一基最優(yōu)解。任一最優(yōu)解可表示為所有基最優(yōu)解的凸組合。例

max

z=3x1+5x23x1

+5x2

￡15如果將x

換入基底，得1另一解，由可行域凸性易知，有兩個(gè)最優(yōu)解必有無(wú)窮多組最優(yōu)解當(dāng)非基底變量的檢驗(yàn)數(shù)中有取零值，或檢驗(yàn)數(shù)中零的個(gè)數(shù)大于基變量個(gè)數(shù)時(shí)，有無(wú)窮多解。qCBXB

b0002x1

+ x2

￡52x1+2x2

￡11x1

,x2

?03

5

0

0

0x1

x2

x3

x4

x53511/25000Z

=0x3153[5

]100x4521010x51122001cj-zj35000x233/511/500x427/50-1/510x554/50-2/501cj-zj00-100Z1=15x1x2四、無(wú)（有）界解max

z=x1+x2-2x1+x2

￡4x1-

x2

￡2-3x1+x2￡3x1

,x2

?0若檢驗(yàn)數(shù)有大于0，而對(duì)應(yīng)系數(shù)列中元素全部小于或等于零（無(wú)換出變量）則原問(wèn)題有無(wú)界解。練習(xí)：寫(xiě)出單純形表,分析檢驗(yàn)數(shù)與系數(shù)關(guān)系并畫(huà)圖驗(yàn)證。線(xiàn)性規(guī)劃解除有唯一最優(yōu)解的情況外，還有如下幾種情況無(wú)可行解退化無(wú)窮多解無(wú)界解人工基可行檢驗(yàn)數(shù)檢驗(yàn)數(shù)大變量解中非中零的于零，但不能零元素個(gè)數(shù)多對(duì)應(yīng)列元從基個(gè)數(shù)小于基變素小于等底中換出于基變量數(shù)量的個(gè)數(shù)于零，無(wú)換出變量單純形法小結(jié)根據(jù)實(shí)際問(wèn)題給出數(shù)學(xué)模型,列出初始單純形表,進(jìn)行標(biāo)準(zhǔn)化,見(jiàn)表變量xj≥0xj≤0xj

無(wú)約束不需要處理令xj′=-xj;xj′≥0令xj=xj′-xj″;xj