工程優(yōu)化第章文檔ppt第1頁，共42頁。根據(jù)以上討論得到如下的結論：結論1：線性規(guī)劃的可行域是凸集,它可以是有界的,也可以是無界的區(qū)域;僅有有限個頂點。

結論2：線性規(guī)劃的每一個基本可行解對應于可行域的一個頂點.若線性規(guī)劃問題有最優(yōu)解,必定可在某頂點取到。結論3：如果一個線性規(guī)劃存在多個最優(yōu)解,那么至少有兩個相鄰的頂點處是線性規(guī)劃的最優(yōu)解。結論4：如果有一個頂點處可行解的目標值比其它相鄰頂點的可行解的目標值小的話，那么它就是最優(yōu)解。

線性規(guī)劃的基本性質(zhì)第2頁，共42頁。

可行域的頂點個數(shù)是有限的(不超過Cnm

個)，采用“枚舉法”找出所有基本可行解，然后一一比較它們的目標函數(shù)值的大小，最終可以找到最優(yōu)解。但當m、n的數(shù)目相當大時，這種辦法實際上是行不通的。因此，我們還要繼續(xù)討論一種方法，通過逐步迭代保證能逐步改進并最終求出最優(yōu)解。線性規(guī)劃的基本性質(zhì)第3頁，共42頁。1947年,美國學者GeorgeDantzig(丹齊格)提出了求解線性規(guī)劃的單純形法,為線性規(guī)劃的推廣奠定了基礎。從可行域的一個頂點(基本可行解)開始,轉移到另一個頂點(另一個基本可行解);轉移的條件是使目標函數(shù)值得到改善(逐步變優(yōu))當目標函數(shù)達到最優(yōu)值時,問題也就得到了最優(yōu)解?；舅枷雴渭冃畏ǖ?頁，共42頁。對于標準線性規(guī)劃問題(簡寫為LP):A=(aij)m

n,rank(A)=m

單純形法的基本原理將A分解成[B,N],使B為基矩陣,N為非基矩陣設求基本解基本可行解令xN=0是基本解。若第5頁，共42頁。相應的目標函數(shù)值為記現(xiàn)在分析如何從一個基本可行解x(0)出發(fā)，求一個改進的基本可行解x(1)。單純形法的基本原理假設已知一個基本可行解x(0)若初始基本可行解x(0)不是最優(yōu)解，找一個新的基本可行解。任意可行解xx?形式并保證是基本可行解x(1)找改進的基本可行解：第6頁，共42頁。設x是任意可行解，目標函數(shù)f在點x處的值為單純形法的基本原理記是非基變量的指標集相應于矩陣A的分解A=[B,N],B稱為基矩陣x可寫為第7頁，共42頁。對任意一個可行解處的目標函數(shù)值為單純形法的基本原理其中是非基變量的下標集，以及xk就從非基變量變成了基變量式(1)中，如果則，x(0)是最優(yōu)解；如果則令xk由0變?yōu)檎龜?shù)時，f就在變?。?xk是進基變量)第8頁，共42頁。對任意一個可行解處的目標函數(shù)值為單純形法的基本原理xk就從非基變量變成了基變量(xk

是進基變量)根據(jù)（1）,當取值相同時，越大，目標函數(shù)下降越多，因此選擇(進基變量)。式(1)中，如果有多個則記令xk由0變?yōu)檎龜?shù)時，f在變小；第9頁，共42頁。1.確定進基變量xk

假設記和是m維列向量，，把按分量寫出，即單純形法的基本原理取此時方程組的解變?yōu)閷膞k

就是進基變量

當由零變?yōu)檎龜?shù)后，函數(shù)值變小第10頁，共42頁。新得到的點是因為基變量個數(shù)總是為m,所以一個進基之后還必須有一個離基。下面我們來考慮如何選擇離基變量。單純形法的基本原理在新得到的點，目標函數(shù)值是基變量原則：保證新得到的點是基本可行解第11頁，共42頁。原則：保證新得到的點是基本可行解當時，取任何正值時，總成立對某個i,當時，取任何正值時，總成立2.確定離基變量

單純形法的基本原理而當時，為了保證取因此，為使，應令取值后，原來的基變量就是離基變量，于是得到新的基本可行解當xk趨于正無窮時，目標函數(shù)值趨于負無窮，因此解無界第12頁，共42頁。重復以上過程，可以進一步改進基本可行解，直到所有的時為止。單純形法的基本原理基變量基變量非基變量非基變量初始的基本可行解改進的基本可行解目標函數(shù)值減小了進基變量的確定離基變量的確定f0

是最優(yōu)值,當前的基本可行解是最優(yōu)解第13頁，共42頁。最優(yōu)解判別定理稱為判別數(shù)或檢驗數(shù)。單純形法的基本原理所有的就可以作為最優(yōu)解的一個判別條件若在極大化問題中,對于某個基本可行解,所有則這個基本可行解是最優(yōu)解。若在極小化問題中,對于某個基本可行解,所有則這個基本可行解是最優(yōu)解。第14頁，共42頁。步驟1：找出初始可行基B，由，求得，令，確定初始基本可行解。計算目標函數(shù)值。步驟2：對于所有非基變量，計算判別數(shù),令若，則對于所有非基變量，對基變量的判別數(shù)總是零，停止計算，當前的基本可行解是最優(yōu)解。否則，進行下一步。單純形法的算法步驟稱為單純形乘子由，得到.第15頁，共42頁。步驟3：由,得到,若，即的每一個分量均非正數(shù)，則停止計算，問題不存在有限最優(yōu)解。否則，進行轉步驟4。步驟4：確定下標r

為離基變量，為進基變量。用替換，得到新的基矩陣B,返回步驟1。注：對于極大化問題，可以給出類似的步驟，只是確定進基和離基變量的準則不同。對于極大化問題，應令單純形法的算法步驟第16頁，共42頁。以極小化問題為例每次迭代必出現(xiàn)下列三種情形之一(1).這時當前的基本可行解就是最優(yōu)解。(2).這種情形下，我們知道取任何正數(shù)，總能得到可行解。所以當無限增大時，目標函數(shù)趨于負無窮，因此解無界。(3)，不小于零。這時求出新的基本可行解，經(jīng)迭代使目標函數(shù)下降。單純形法的收斂性第17頁，共42頁。如果迭代過程中各個基本可行解都是非退化的，即基變量的取值都是正的，則各次迭代得到的基本可行解互不相同。由于基本可行解的個數(shù)有限，因此經(jīng)有限次迭代一定可以達到最優(yōu)解。收斂性定理：對于非退化問題，單純形方法經(jīng)有限次迭代或達到最優(yōu)基本可行解，或得出無界的結論。注：對于退化情形，可能出現(xiàn)循環(huán)迭代，我們在后面將要證明，如果最優(yōu)解存在，只要采取一定的措施，也能做到有限步收斂。單純形法的收斂性第18頁，共42頁。使用表格形式的單純形方法記，則標準形式等價于1.構造單純形表標準形式的線性規(guī)劃標準形式繼續(xù)等價于第19頁，共42頁。把約束方程的系數(shù)置于表中，就得到了所謂的單純形表1列cBTB-1

bB-1b右端m行B-1NIm0xNxBfn-m列m列1列1行-cBT

B-1N+cNT01目標函數(shù)值負的判別數(shù)基變量的值使用表格形式的單純形方法1.構造單純形表A中存在m階的單位矩陣xBf為了出現(xiàn)判別數(shù)，最后1行乘以-1負的目標值判別數(shù)第20頁，共42頁。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.構造單純形表

xk是進基變量，是離基變量；主元把xk

所對應的列向量pk變成所對應的列向量，即是單位向量。把xk和

的位置對換，第21頁，共42頁。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)?把pk變成對應的單位向量？第22頁，共42頁。對應的新的目標函數(shù)值即為：使用表格形式的單純形方法2.高斯主元消去法以yrk

為主元素進行Gauss消元:將第r行每個元素除以yrk

:將第r行每個元素乘以–yik/yrk

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

i≠r)將第r行每個元素乘以–(zk–ck)

/yrk

加到檢驗數(shù)行第23頁，共42頁。經(jīng)過Gauss消元后，針對于新基B1的基本可行解為：使用表格形式的單純形方法2.高斯主元消去法第24頁，共42頁。步驟3：在所有

j>0,j∈RN中，若有一個

j對應的系數(shù)列向量

yj0，則此問題沒有有限最優(yōu)解，停止計算，否則轉步驟4；使用表格形式的單純形方法3.單純形表的單純形法的算法步驟步驟1：找出初始可行基，確定初始基本可行解，建立初始單純形表；步驟2：檢查對應于非基變量的檢驗數(shù)

j=zj-cj,j∈RN,若所有

j0,j∈RN,則已得到最優(yōu)解,停止計算;否則轉步驟3步驟4：根據(jù)max{

j|

j>0,j∈RN}=

k,確定xk

為進基變量。第25頁，共42頁。確定xr為離基變量(即為新基的非基變量),轉步驟6；步驟5：再根據(jù)步驟6：以yrk為主元素進行Gauss消元，轉步驟2。使用表格形式的單純形方法3.單純形表的單純形法的算法步驟第26頁，共42頁。例1.利用單純形算法求解如下的線性規(guī)劃問題。解：1.寫出線性規(guī)劃的標準型使用表格形式的單純形方法3.單純形表的算例A中存在4階單位矩陣選取作為基變量，得到一個基本可行解第27頁，共42頁。2.max{1,

2}=3=2,所以x2為進基變量.3.p2的坐標有正分量存在，因為3與x6

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

x6

221000120100400010040001x3x4x5x61281612

23c

-2-30000

64--30000

cB0000第28頁，共42頁。4.

以“4”為主元素Gauss消去，進行行初等變換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加到檢驗數(shù)行第29頁，共42頁。5.max{1}=2=1,所以x1為進基變量.6.p1的坐標有正分量存在，因為2與x4

那一行相對應，所以x4為離基變量；故x1對應列與x4對應行的相交處的1為主元素；第30頁，共42頁。7.

以“1”為主元素Gauss消元，進行行初等變換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加到檢驗數(shù)行x3x4x5x2

0100-1/26

20000-3/4010001/434000101610010-1/22324--這行不變這行不變退化現(xiàn)象：有兩個或更多的相同時，在相同對應的變量中選擇下標最大的那個基變量為離基變量第31頁，共42頁。因為4與x3

，

x5那一行相對應，所以x5為離基變量;故x6對應列與x5對應行的相交處的2為主元素；9.p6的坐標有正分量存在，8.max{6}=1/4=6,所以x6為進基變量.第32頁，共42頁。xBx1x2x3x4x5

x6

x3x1x5x2c

-2-30000

cB0-20-30

01-201/22

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

這時出現(xiàn)了退化問題。即有兩個或更多的

相同時，在相同

對應的變量中選擇下標最大的那個基變量為換出變量；同時如果出現(xiàn)有兩個或更多的檢驗數(shù)σ相同時，在相同σ對應的變量中選擇下標最小的那個基變量為進基變量，這樣會避免出現(xiàn)“死循環(huán)”的現(xiàn)象。第33頁，共42頁。10.

以“2”為主元素Gauss消元，進行行初等變換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加到檢驗數(shù)行x3x1x5x20

01-201/22

000-201/4010001/43000-412810010-1/224--412第3行的1/4加到該行第3行的-1/8加到該行所有檢驗數(shù)都小于等于0，當前的基本可行解是最優(yōu)解第34頁，共42頁。xBx1x2x3x4x5

x6

x3x1x6x2c

-2-30000

cB0-20-30

01-1-1/400

000-3/2-1/800101/2-1/802000-21/21410001/404所有檢驗數(shù)都小于等于0，當前的基本可行解x=(4,2,0,0,0,4)T是最優(yōu)解原問題的最優(yōu)解是x=(4,2)T，最優(yōu)值是f=2*4+3*2=14第35頁，共42頁。例2.利用單純形算法求解如下的線性規(guī)劃問題。解：1.化為標準型得到：A中存在3階單位矩陣選取作為基變量，得到一個基本可行解第36頁，共42頁。2.max{2}=2=2,所以x2為進基變量.3.p2的坐標有正分量存在，因為2與x6

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

x2x3

x4x5

x6

x4x5x6c

1-21000

cB0001

1-210010-12-1-12-400142-14010810--2000第37頁，共42頁。4.

以“2”為主元素進行Gauss消去，即進行行初等變換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倍加到檢驗數(shù)行第38頁，共42頁。5.max{3}=3=3,所以x3

為進基變量.6.p3的坐標有正分量存在，因為5與x5

那一行相對應，所以x5為離基變量；故x3對應列與x5對應行的相交處的2為主元素；第39頁，共42頁。7.

以“2”為主元素進行Gauss消去，即進行