運(yùn)籌學(xué)02單純形法

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)形式：

maxz=Σcjxj(1)s.t.Σaijxj=bii=1,2,…,m(2)xj≥0j=1,2,…,n(3)可行域：由約束條件(2)、(3)所圍成的區(qū)域；可行解：滿足(2)、(3)條件的解X=(x1，x2，…，xn)T為可行解；基：設(shè)A是約束條件方程組的m×n維系數(shù)矩陣,其秩為m，B是A中m×m階非奇異子矩陣，則稱B為線性規(guī)劃問(wèn)題的一個(gè)基。設(shè)復(fù)習(xí):線性規(guī)劃問(wèn)題解的概念B=

=(p1,p2,…,pm)

a11a12…a1m

a21a22…a2m

…

…

…

am1am2…amm

1基向量、非基向量、基變量、非基變量：

稱pj(j=1,2,…,m）為基向量，其余稱為非基向量； 與基向量pj(j=1,2,…,m）對(duì)應(yīng)的xj稱為基變量，其全體寫成XB=（x1，x2，…，xm）T；否則稱為非基變量，其全體經(jīng)常寫成XN?；猓簩?duì)給定基B,設(shè)XB是對(duì)應(yīng)于這個(gè)基的基變量

XB=(x1，x2，…，xm)T；

令非基變量xm+1=xm+2=…=xn=0，由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T

稱為基解?；尚薪猓核袥Q策變量滿足非負(fù)條件(xj≥0)的基解,

稱作基可行解?？尚谢夯尚薪馑鶎?duì)應(yīng)的基底稱為可行基。2寫出下述線性規(guī)劃問(wèn)題對(duì)應(yīng)的基、基變量、基解、基可行解和可行基。3定理2：X是線性規(guī)劃問(wèn)題的基可行解的充要條件是它對(duì)應(yīng)于可行域D的頂點(diǎn)。（線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)于可行域D的頂點(diǎn)。）定理3：若可行域有界,線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu).4§3單純形法（SimplexMethod）例子：求解線性規(guī)劃問(wèn)題線性規(guī)劃問(wèn)題的最優(yōu)解，可以從基可行解中找到

圖解法有局限性；

枚舉法計(jì)算量大；§3.1單純形法的引入0Q4Q31123234Q2Q1X1X2x1+2x2=84x1=164x2=125解:

首先:將該問(wèn)題化成標(biāo)準(zhǔn)形第二:

找初始可行解(即一個(gè)頂點(diǎn))。系數(shù)矩陣A=(p1p2p3p4p5)矩陣形式6

因?yàn)閜3，p4，

p5線性獨(dú)立，故B=(p3,p4,p5)構(gòu)成一個(gè)基底，對(duì)應(yīng)的基變量x3，x4，x5解出來(lái)為（用非基變量表示基變量）

x3=8-x1-2x2x4=16-4x1(a)x5=12-4x2

將(a)代入目標(biāo)函數(shù)中得z=0+2x1+3x2令非基底變量x1=x2=0，則有z=0。這時(shí)得到一個(gè)基可行解X(0)=(0,0,8,16,12)T---原點(diǎn)第三:判別從目標(biāo)函數(shù)中得知，非基底變量的系數(shù)為正，因此，將非基變量換入基底后可使目標(biāo)函數(shù)增大，轉(zhuǎn)入第四步7第四:換基底(旋轉(zhuǎn)迭代)

確定換入變量：由于z=0+2x1+3x2

中非基底變量x2系數(shù)貢獻(xiàn)最大3，故換入基底為x2。換入變量已定，必須從x3，x4，x5換出一個(gè)，并且要保證其余均是非負(fù)的，即x3，x4，x50。

x3=8-2x2

0

x4=160

x5=12-4x20

由此，只要選擇x2=min(8/2，-，12/4)=3，對(duì)應(yīng)基底變量x5=0，從而確定用x2和x5對(duì)調(diào)，即將x5

換出。有

x3

=2-x1+1/2x5

x4=16-4x1(b)x2=3-1/4x5

8

將(b)代入目標(biāo)函數(shù)中得z=9+2x1-3/4x5

令非基變量為零，又得到另一個(gè)基可行解

X(1)=(0,3,2,16,0)T–頂點(diǎn)Q4

返回第三步：非基變量x1的系數(shù)是正的，還可增大，X(1)

不是最優(yōu)解。重復(fù)上述步驟。由于x1的系數(shù)是正的，從而x1為轉(zhuǎn)入變量，再由x3=2-x1

0

x4=16-4x1

0

x2=30

9只要選

x1=min{2，16/4，-}=2上式就成立，因?yàn)閤1=2時(shí)，基變量x3=0，從而由x1換出x3，得

x1=2-x3+1/2x5

4x1+x4=16

(c)x2=3-1/4x5高斯消去法（行變換）得

x1=2-x3+1/2x5

x4=8-2x5+4x3x2=3-1/4x5

10代入目標(biāo)函數(shù)中，得

z=13-2x3+1/4x5令非基變量x3=x5=0，又得到另一個(gè)基可行解X(2)X(2)=(2,3,0,8,0)T–新頂點(diǎn)Q3

同理，返回第三步，再迭代，x5作為轉(zhuǎn)入變量

x1=2+1/2x5

0

x4=8-2x50

x2=3-1/4x5

0

11只要取x5=min{-，8/2，12}=4就有上式成立。x5=4時(shí)，x4=0，故決定用x5換x4x1=4-1/4x4

x5=4-1/2x4+2x3x2=2+1/8x4–1/2x3

代入得z=14-3/2x3–1/8x4

，令x3，x4=0得z=14。新基可行解為

X(3)=(4,2,0,0,4)T–為最優(yōu)解，新頂點(diǎn)Q2最優(yōu)目標(biāo)值z(mì)=14。12從實(shí)際例子中分析單純形法原理的基本框架為

第一步：將線性規(guī)劃模型變換成標(biāo)準(zhǔn)型，確定一個(gè)初始可行解（頂點(diǎn)）。

第二步：對(duì)初始基可行解最優(yōu)性判別，若最優(yōu)，停止；否則轉(zhuǎn)下一步。

第三步：從初始基可行解向相鄰的基可行解（頂點(diǎn)）轉(zhuǎn)換，且使目標(biāo)值有所改善—目標(biāo)函數(shù)值增加，重復(fù)第二和第三步直到找到最優(yōu)解。13§3.2初始可行基的確定設(shè)線性規(guī)劃問(wèn)題：14

為了確定初始基可行解，首先要找出初始可行基，其方法如下：從Pj(j=1,2,…,n)中一般能直接觀察到存在一個(gè)初始可行基

確定初始可行基的幾種方法：

形式的不等式

形式的不等式=的情形觀察“小加大減+人造”15

約束是≤形式的不等式，可以利用化標(biāo)準(zhǔn)型的方法，左端加一個(gè)松弛變量，經(jīng)過(guò)整理，重新對(duì)xj及aij（i=1,2,…,m；j=1，2，…，n）進(jìn)行調(diào)整編號(hào)，則可得下列方程組“小加”16x1+a1,m+1xm+1+…+a1nxn=b1x2+a2,m+1xm+1+…+a2nxn=b2

……

xm+am,m+1xm+1+…+amnxn=bmxj≥0，j=1,2,…,n顯然得到一個(gè)m×m單位矩陣注意：aij和bi已經(jīng)變化17移項(xiàng)整理得

x1=b1-a1,m+1xm+1-…-a1nxn

x2=b2–a2,m+1xm+1-…-a2nxn

……

xm=bm–am,m+1xm+1-…-amnxn

令xm+1=xm+2=…=xn=0，可得

xi=bi

（i=1，2，…，m）

又因bi≥0，所以得到一個(gè)初始基可行解：

X（0）=（x1x2…

xm0…0)T

=(b1b2…

bm0…0)T18非基向量可以用基向量的線性組合表示將(3)式乘以一個(gè)正的數(shù)

>0,得到記初始基可行解為X(0),有該解滿足約束方程,即§3.3從初始基可行解轉(zhuǎn)換為另一基可行解19(4)式和(1)式相加,整理后得到由(5)式可以找到滿足約束方程的另一個(gè)點(diǎn)X(1),其中是點(diǎn)X(1)的第j個(gè)坐標(biāo)值20要使X(1)是一個(gè)基本可行解,則要求并且這m個(gè)等式中至少要有一個(gè)等號(hào)成立當(dāng)時(shí),(6)式必然成立當(dāng)時(shí),令因此有所以X(1)中的正分量最多有m個(gè),可證明m個(gè)向量P1,…,Ps-1,Ps+1,…,Pm,Pj線性無(wú)關(guān),按照式(7)確定

值,X(1)就是一個(gè)新的基可行解.21線性規(guī)劃解的四種可能：1、有唯一解；2、無(wú)窮多最優(yōu)解；3、無(wú)界解；4、無(wú)可行解。何時(shí)達(dá)最優(yōu)解,何種最優(yōu)解？§3.4

最優(yōu)性檢驗(yàn)和判別定理22將基本可行解X(0)和X(1)分別代入目標(biāo)函數(shù)得由此

j稱做檢驗(yàn)數(shù),是對(duì)線性規(guī)劃問(wèn)題的解進(jìn)行最優(yōu)性檢驗(yàn)的標(biāo)志.23最優(yōu)解的判別定理：且對(duì)一切的j=m+1,...,n有則X(0)

為最優(yōu)解。若是一個(gè)基可行解，24無(wú)窮多最優(yōu)解判別定理：若是一個(gè)基可行解，且對(duì)一切的j=m+1,...,n有又存在某個(gè)非基變量的檢驗(yàn)數(shù)則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。25無(wú)界解的判別定理：26§3.5基變換換入變量的確定:max(

j>0)=k,j=m+1,…,n;xk是換入變量(也可任選).換出變量的確定:

確定換出變量的原則是保持解的可行性,就是說(shuō)要使原基可行解的某一正分量xs變成零,同時(shí)保持其它的分量均非負(fù)(換基原則)min(xi/aij|aij>0)=xs/asj=,s{1,2,…,m}(最小比值準(zhǔn)則,或

準(zhǔn)則)§3.6旋轉(zhuǎn)運(yùn)算在確定換入變量xk和換出變量xs以后，要把xk所對(duì)應(yīng)的系數(shù)列向量pk變成單位向量，為此,只要對(duì)系數(shù)矩陣的增廣陣進(jìn)行“行”的初等變換即可。行變換的定義：27(第s行)*1/ask得:當(dāng)is時(shí),(第i行)-(第s行)*aik28經(jīng)過(guò)初等變換后,新的增廣矩陣是29§4單純形法的計(jì)算步驟和單純形表約束方程組和目標(biāo)函數(shù)組成n+1個(gè)變量,m+1個(gè)方程的方程組該方程組對(duì)應(yīng)的增廣矩陣是30確定初始單純形表后可以得到初始基可行解x0,

若有某個(gè)非基底變量xk對(duì)應(yīng)的檢驗(yàn)數(shù)

k=(ck-zk)>0,則當(dāng)前解不是最優(yōu)解，取使目標(biāo)增長(zhǎng)最大的非基底變量進(jìn)入基底。根據(jù)確定xk為換入變量根據(jù)確定xs為換出變量將xk對(duì)應(yīng)的列向量Pk=(a1k,,…,ask,…,ank)T變換為aik=0，is

aik=1，i=s重復(fù)上述步驟直到所有的檢驗(yàn)數(shù)滿足最優(yōu)條件，得最優(yōu)解。31§5單純形法的進(jìn)一步討論

人工變量法（確定初始可行基）：原約束方程：AX=b加入人工變量：xn+1，，xn+m

人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，經(jīng)過(guò)基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中還有某個(gè)非零的人工變量，原問(wèn)題無(wú)可行解。321、大M法方法：在約束條件中，加入人工變量后，要求目標(biāo)函數(shù)不受影響？目標(biāo)函數(shù)中人工變量的系數(shù)?。?M）。理由：目標(biāo)函數(shù)實(shí)現(xiàn)最大化，就必須將人工變量從基變量中換出，否則目標(biāo)函數(shù)就不可能取得最大化。例1：用大M法求解如下線性規(guī)劃問(wèn)題33111-211000113-4120-1103/21-20[1]000110M16xx4

x3103-20100-110[1]00-11-211-2010001-3x11x21x341001/3-2/32/3-5/310100-11-2900102/3–4/3-7/3

-31100

MM

-10001M-1M+1zj-cj

0001/31/3M-1/3M-2/3zj-cj0x41x21x312[3]001-22-5410100-11-21-2010001cj0MMX4X6X7

b

CBXBX1X2X3X4X5X6X7

i-3+6M1-M1-3M0M00cj-zj

-11-M00M03M-1cj-zj34最優(yōu)解是目標(biāo)函數(shù)為-2。

352、兩階段法第一階段：建立一個(gè)輔助線性規(guī)劃并求解，以此判斷原線性規(guī)劃是否存在可行解。輔助線性規(guī)劃問(wèn)題：目標(biāo)函數(shù)取成所有的人工變量之和，并對(duì)目標(biāo)函數(shù)取極小化，約束條件依然為原問(wèn)題的以單位矩陣作為可行基的標(biāo)準(zhǔn)型的約束條件。所有人工變量都變成非基變量，目標(biāo)函數(shù)值為0，原問(wèn)題存在基可行解。轉(zhuǎn)到第二階段。若目標(biāo)函數(shù)值不為0，至少有一個(gè)人工變量不能從基變量中轉(zhuǎn)出，原問(wèn)題沒(méi)有可行解。停止。第二階段：從第一階段最優(yōu)表格中去掉人工變量，將目標(biāo)函數(shù)系數(shù)換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，用單純形法計(jì)算，直到得到最優(yōu)解為止。36第一階段：求解輔助規(guī)劃問(wèn)題37

111-211000113-4120-1103/21-20[1]000110106xx4

x3103-20100-110[1]00-11-211-2010001

00000

11

0000011zj-cj0x40x20x312[3]001-22-5410100-11-21-2010000cj011X4X6X7

b

CBXBX1X2X3X4X5X6X7

i6-1-30100cj-zj

0-100103cj-zj3812[311-20100-3112xx1

x341001/3-2/310100-190012/3-4/3

-31100cj011X4X2X3

b

CBXBX1X2X3X4X5

i-1000