最優(yōu)化方法線性規(guī)劃單純形法

最優(yōu)化方法線性規(guī)劃單純形法目前一頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃：目標函數(shù)是線性的，約束條件是線性等式或不等式線性規(guī)劃目前二頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃的歷史淵源要追溯到Euler、Liebnitz、Lagrange等GeorgeDantzig,VonNeumann(Princeton)和LeonidKantorovich在1940’s創(chuàng)建了線性規(guī)劃1947年,GeorgeDantzig發(fā)明了單純形法1979年，L.Khachain找到了求解線性規(guī)劃的一種有效方法(第一個多項式時間算法－橢球內(nèi)點法)1984年，NarendraKarmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強有力的競爭者(投影內(nèi)點法)現(xiàn)在求解大規(guī)模、退化問題最有效的是原－對偶內(nèi)點法目前三頁\總數(shù)七十六頁\編于二十一點目前四頁\總數(shù)七十六頁\編于二十一點目前五頁\總數(shù)七十六頁\編于二十一點目前六頁\總數(shù)七十六頁\編于二十一點◎問題：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？◎變量：n種食品，m種營養(yǎng)成份；－第j種食品的單價－每單位第j種食品所含第i種營養(yǎng)的數(shù)量

－食用第j種食品的數(shù)量－為了健康，每天必須食用第i種營養(yǎng)的數(shù)量◎模型：例1.食譜問題目前七頁\總數(shù)七十六頁\編于二十一點例2.運輸問題產(chǎn)銷平衡/不平衡的運輸問題目前八頁\總數(shù)七十六頁\編于二十一點

例3.其它應(yīng)用

數(shù)據(jù)包絡(luò)分析(dataenvelopeanalysis,DEA)網(wǎng)絡(luò)流問題(Networkflow)博弈論(gametheory)等目前九頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃的一般形式目前十頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃的標準形(分析、算法)標準形的特征：極小化、等式約束、變量非負向量表示：目前十一頁\總數(shù)七十六頁\編于二十一點一般形式標準形轉(zhuǎn)化稱松弛(slack)/盈余(surplus)變量；自由變量目前十二頁\總數(shù)七十六頁\編于二十一點例5.化成標準形等價表示為目前十三頁\總數(shù)七十六頁\編于二十一點定義：給定含有n個變量，m個方程的線性方程組Ax=b，設(shè)B是由A的列組成的任一非奇異m×m子陣，則如果置x的所有與B無關(guān)的n-m個分量為零后，所得方程組的解是Ax=b關(guān)于基B的基本解(basicsolution)，稱x中與基B對應(yīng)的分量為基變量(basicvariables)退化基本解：基本解中如果有一個或多個基變量的值為零基本解與基變量其中滿秩假定：m×n矩陣A滿足m<n，且A的行向量線性無關(guān)在滿秩假定下，方程組Ax=b總有解，且至少有一個基本解目前十四頁\總數(shù)七十六頁\編于二十一點基本可行解定義稱的非負基本解是標準形的基本可行解(basicfeasiblesolution)；約束系統(tǒng)目前十五頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃的基本定理i)若標準型有可行解，則必有基本可行解；ii)若標準型有最優(yōu)解，則必有最優(yōu)基本可行解。

考慮線性規(guī)劃標準形，其中A是秩為m的m×n階矩陣，則以下結(jié)論成立：基本可行解的個數(shù)不超過目前十六頁\總數(shù)七十六頁\編于二十一點與凸性的關(guān)系線性規(guī)劃的基本定理(標準形)基本可行解線性方程組的基本性質(zhì)代數(shù)理論(與表述形式有關(guān))設(shè)計算法極點凸集理論幾何理論(與表述形式無關(guān))直觀理解目前十七頁\總數(shù)七十六頁\編于二十一點凸性(凸集及性質(zhì))幾何解釋：連接集合中任兩點的線段仍含在該集合中性質(zhì)

定義是凸集(convexset)，如果對S中任意兩點x,y和(0,1)中的任一數(shù)滿足目前十八頁\總數(shù)七十六頁\編于二十一點一些重要的凸集有限個閉半空間的交集多面集(polyhedralconvexset):推廣平面上：多邊形注：任一線性規(guī)劃的可行集是多面集！超平面(hyperplane):正/負閉半空間：目前十九頁\總數(shù)七十六頁\編于二十一點極點幾何上：極點即不能位于連接該集合中其它兩點的開線段上的點定義稱凸集C中的點x是C的極點，如果存在C中的點y,z和某，有則必有y=z.目前二十頁\總數(shù)七十六頁\編于二十一點極點與基本可行解的等價性定理推論：i)若K非空，則至少有一個極點.ii)若線性規(guī)劃有最優(yōu)解，則必有一個極點是最優(yōu)解.iii)Ax=b對應(yīng)的約束集K最多有有限個極點.

考慮線性規(guī)劃標準形，其中A是秩為m的m×n矩陣，令則x是K

的極點，當且僅當x是線性規(guī)劃的基本可行解.（線性規(guī)劃基本定理的幾何形式）目前二十一頁\總數(shù)七十六頁\編于二十一點例2.

K

有2個極點有3個基本解，2個可行K有3個極點有3個基本解，均可行例1.目前二十二頁\總數(shù)七十六頁\編于二十一點例3.Subjectto5個極點－極點目前二十三頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃解的幾何特征唯一解(頂點)！目前二十四頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃解的幾何特征無界：沒有有限最優(yōu)解不可行：沒有可行解無解可行集：多邊形(二維)→多邊集(高維空間)給出有效的代數(shù)刻畫和嚴謹?shù)膸缀蚊枋?，從理論上證實上述幾何特征，并尋求有效算法有解：唯一解/多個解(整條邊、面、甚至整個可行集)

有頂點解目前二十五頁\總數(shù)七十六頁\編于二十一點頂點一條邊無(下)界目前二十六頁\總數(shù)七十六頁\編于二十一點線性規(guī)劃問題解的幾種情況目前二十七頁\總數(shù)七十六頁\編于二十一點單純形法簡介適用形式：標準形(基本可行解=極點)理論基礎(chǔ)：線性規(guī)劃的基本定理！基本思想：從約束集的某個極點/BFS開始，依次移動到相鄰極點/BFS，直到找出最優(yōu)解，或判斷問題無界.初始化：如何找到一個BFS？判斷準則：何時最優(yōu)？何時無界？迭代規(guī)則：如何從一個極點/BFS迭代到相鄰極點/BFS？目前二十八頁\總數(shù)七十六頁\編于二十一點1.轉(zhuǎn)軸(基本解→相鄰基本解)滿秩假定：A是行滿秩的目前二十九頁\總數(shù)七十六頁\編于二十一點規(guī)范形(canonicalform)基變量基本解非基變量等價變形不妨設(shè)線性無關(guān)一般地：次序可以打亂！只要有m個單位列目前三十頁\總數(shù)七十六頁\編于二十一點規(guī)范形的轉(zhuǎn)換問題⊙什么時候可以替換？⊙替換后新規(guī)范形是什么？◎替換問題假設(shè)在上述規(guī)范形中，想用目前三十一頁\總數(shù)七十六頁\編于二十一點轉(zhuǎn)軸(pivot)◎當且僅當，可以替換◎替換后，新規(guī)范形的系數(shù)轉(zhuǎn)軸公式－轉(zhuǎn)軸元(pivotelement)目前三十二頁\總數(shù)七十六頁\編于二十一點轉(zhuǎn)軸例1.求下列方程組以為基變量的基本解目前三十三頁\總數(shù)七十六頁\編于二十一點轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸x=(0,0,0,4,2,1)目前三十四頁\總數(shù)七十六頁\編于二十一點2.

BFS→相鄰BFS(極點→相鄰極點)◎問題：確定出基變量，使轉(zhuǎn)軸后新規(guī)范形對應(yīng)BFS？設(shè)x是BFS,且規(guī)范形如前，且假設(shè)

aq

進基因為令可否選取合適的使得是BFS

？所以目前三十五頁\總數(shù)七十六頁\編于二十一點確定離基變量至少有一個正元目前三十六頁\總數(shù)七十六頁\編于二十一點例3.

考慮線性方程組a4進基轉(zhuǎn)軸B=(a1,a2,a3)X=(4,3,1,0,0,0)x=(0,1,3,2,0,0)目前三十七頁\總數(shù)七十六頁\編于二十一點3.BFS→目標值減小的相鄰BFS⊙將Ax=b的任一解用非基變量表示；設(shè)x是BFS，且規(guī)范形如前，則有◎問題：確定進基變量，轉(zhuǎn)軸后使新BFS的目標值變??？用非基變量表示.——選取進基變量的依據(jù)⊙將目標函數(shù)目前三十八頁\總數(shù)七十六頁\編于二十一點相對/既約費用系數(shù)(relative/reducedcostcoefficients)將Ax=b

的任一解x用非基變量表示為度量變量相對于給定基的費用目前三十九頁\總數(shù)七十六頁\編于二十一點確定進基變量◎最優(yōu)性定理◎定理(BFS的提高)◎相對費用系數(shù)的經(jīng)濟解釋！(合成價格、相對價格)

給定目標值為z0的非退化基本可行解，且假定存在j使得rj<0，則

i)如果用aj替換基中某列得到了新的BFS，則新解處的目標值比z0嚴格小.

ii)如果任何替換都產(chǎn)生不了新的BFS，則問題無界.

◆退化基本可行解：某個或某些基變量取零的基本可行解！問題：基本可行解與基的對應(yīng)關(guān)系？目前四十頁\總數(shù)七十六頁\編于二十一點4.計算過程－單純形法單純形表：BFS對應(yīng)規(guī)范形的表格＋既約費用系數(shù)和BFS目標值的相反數(shù)目前四十一頁\總數(shù)七十六頁\編于二十一點單純形法的步驟步0形成與初始BFS對應(yīng)的初始表格.

通過行變換求出第一張單純形表.步1若對每個j都有，停；當前BFS是最優(yōu)的.步2選取q滿足步4以為轉(zhuǎn)軸元進行轉(zhuǎn)軸，更新單純形表，返步1.步3若，停，問題無界；否則，選p滿足轉(zhuǎn)軸規(guī)則：進基變量：最小相對費用系數(shù)規(guī)則；出基變量：最小指標規(guī)則！目前四十二頁\總數(shù)七十六頁\編于二十一點例1.

化標準形轉(zhuǎn)軸得標準形的初始表格/第一張單純形表目前四十三頁\總數(shù)七十六頁\編于二十一點轉(zhuǎn)軸0↓-2↓-4↓-27/5轉(zhuǎn)軸目前四十四頁\總數(shù)七十六頁\編于二十一點最優(yōu)解：最優(yōu)值：原問題的極大值：目前四十五頁\總數(shù)七十六頁\編于二十一點退化(degenerate)與循環(huán)(cycling)◎退化問題⊙單純形法可能出現(xiàn)循環(huán)！⊙實際中經(jīng)常碰到退化問題，但很少出現(xiàn)循環(huán)⊙避免出現(xiàn)循環(huán)的措施：攝動法、Bland法則、字典序法

基本可行解是退化的當且僅當單純形表最后一列有一個或者多個零！一次轉(zhuǎn)軸是退化的當且僅當目標函數(shù)沒有發(fā)生變化！目前四十六頁\總數(shù)七十六頁\編于二十一點最小系數(shù)規(guī)則：◎進基變量：最小系數(shù)規(guī)則◎出基變量：最小指標規(guī)則循環(huán)的例子Beale循環(huán)定義：從某張單純形表開始返回到該單純形表的一串轉(zhuǎn)軸轉(zhuǎn)軸規(guī)則：選取進基變量和離基變量的明確規(guī)則目前四十七頁\總數(shù)七十六頁\編于二十一點目前四十八頁\總數(shù)七十六頁\編于二十一點目前四十九頁\總數(shù)七十六頁\編于二十一點

循環(huán)！注：循環(huán)轉(zhuǎn)軸序列中所有BFS都是退化的！是同一個BFS！第七張單純形表目前五十頁\總數(shù)七十六頁\編于二十一點避免循環(huán)的方法⊙如果有多個費用系數(shù)是負的，選取下標最小的相對費用系數(shù)對應(yīng)的變量為進基變量◎攝動法(Charnes，1952年)◎

Bland法則(Bland,1977)－最小指標法則◎字典序法(Dantzig,

Orden和Wolfe，1954年)⊙如果最小正比值在多個指標處取得，取下標最小者對應(yīng)的變量為進基變量美好愿望：構(gòu)造某種永遠不會產(chǎn)生循環(huán)的轉(zhuǎn)軸規(guī)則！目前五十一頁\總數(shù)七十六頁\編于二十一點前四張單純形表相同！利用Bland法則作為轉(zhuǎn)軸規(guī)則求解Beale的例子！目前五十二頁\總數(shù)七十六頁\編于二十一點最后一張單純形表/最優(yōu)單純形表目前五十三頁\總數(shù)七十六頁\編于二十一點單純形法的收斂性◎

非退化線性規(guī)劃：任一基本可行解非退化

對非退化線性規(guī)劃，從任一基本可行解出發(fā)，利用單純形法可在有限步內(nèi)得到最優(yōu)解或判斷問題無界.◎收斂性定理：目前五十四頁\總數(shù)七十六頁\編于二十一點5.兩階段法如何啟動單純形法－人工變量◎目標判斷Ax=b,x≥0是否有界；有解時找一個基本可行解；⊙給有需要的行乘以-1，使得b≥0◎方法(x,y)=(0,b)是基本可行解！故可以(0,b)為初始BFS，利用單純形法求解輔助問題假設(shè)最后得最優(yōu)解(x,y)、最優(yōu)值z*和最優(yōu)基B⊙構(gòu)造輔助問題人工變量目前五十五頁\總數(shù)七十六頁\編于二十一點得到原問題的基本可行解◎z*>0，無可行解！◎z*=0，有可行解！⊙

基變量中無人工變量→x

是BFS，B是對應(yīng)的基⊙

基變量中有人工變量→驅(qū)趕人工變量出基假設(shè)第i個基變量是人工變量，且當前單純形表第i行的前n個數(shù)據(jù)是第i

個約束冗余；刪除單純形表的第i

行數(shù)據(jù)以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸得輔助問題的一個新最優(yōu)BFS，且基變量中少1個人工變量！目前五十六頁\總數(shù)七十六頁\編于二十一點例1.

給出下面系統(tǒng)的一個基本可行解，或者說明其無解引入人工變量目標：輔助問題的初始表格！BFS目前五十七頁\總數(shù)七十六頁\編于二十一點第一張單純形表第二張單純形表注意基變量整列包括末行z在內(nèi)除了基變量其他元素都是0目前五十八頁\總數(shù)七十六頁\編于二十一點輔助問題的最優(yōu)值是0.原問題的BFS：目前五十九頁\總數(shù)七十六頁\編于二十一點兩階段法－可求任一線性規(guī)劃問題◎

第I階段：啟動單純形法

→構(gòu)造、求解輔助問題→判斷原問題不可行、或可行

→可行時找到基本可行解及對應(yīng)規(guī)范形⊙第II階段：利用單純形法求原問題

→從上述BFS出發(fā)，求解所給問題

→原問題無界或者有解目前六十頁\總數(shù)七十六頁\編于二十一點例2.

利用兩階段法求解下面的問題輔助問題第I階段：先構(gòu)造輔助向量z=x4+x5目前六十一頁\總數(shù)七十六頁\編于二十一點輔助問題的最后一張單純形表原問題的初始表格：得到輔助問題的最后一張單純形表后，去掉輔助變量，將原始問題的z帶入表格，啟動單純形法目前六十二頁\總數(shù)七十六頁\編于二十一點原問題的最優(yōu)解：目前六十三頁\總數(shù)七十六頁\編于二十一點6.修正單純形法(Revisedsimplexmethod)◎重要事實：⊙通常僅有少數(shù)列發(fā)生轉(zhuǎn)軸(2m-3m)◎

核心問題：如何更新當前基的逆→新基的逆理論上的表現(xiàn)表格實現(xiàn)⊙僅需原始數(shù)據(jù)(c,A,b)和基B

的逆矩陣目前六十四頁\總數(shù)七十六頁\編于二十一點7.單純形法的矩陣形式給定基B

及對應(yīng)BFS(xB,0),其中xB=B-1b用非基變量表示目標函數(shù)：用非基變量表示基變量：相對費用向量目前六十五頁\總數(shù)七十六頁\編于二十一點初始表格－單純形表初始表格通常不是單純形表！與基矩陣B

對應(yīng)的單純形表目前六十六頁\總數(shù)七十六頁\編于二十一點修正單純形法的計算步驟步2選取q滿足步3計算yq=B-1aq；若步1計算