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

最優(yōu)化方法線性規(guī)劃單純形法現(xiàn)在是1頁\一共有76頁\編輯于星期三線性規(guī)劃：目標(biāo)函數(shù)是線性的，約束條件是線性等式或不等式線性規(guī)劃現(xiàn)在是2頁\一共有76頁\編輯于星期三線性規(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)點法現(xiàn)在是3頁\一共有76頁\編輯于星期三現(xiàn)在是4頁\一共有76頁\編輯于星期三現(xiàn)在是5頁\一共有76頁\編輯于星期三現(xiàn)在是6頁\一共有76頁\編輯于星期三◎問題：確定食品數(shù)量，滿足營養(yǎng)需求，花費最小？◎變量：n種食品，m種營養(yǎng)成份；－第j種食品的單價－每單位第j種食品所含第i種營養(yǎng)的數(shù)量

－食用第j種食品的數(shù)量－為了健康，每天必須食用第i種營養(yǎng)的數(shù)量◎模型：例1.食譜問題現(xiàn)在是7頁\一共有76頁\編輯于星期三例2.運輸問題產(chǎn)銷平衡/不平衡的運輸問題現(xiàn)在是8頁\一共有76頁\編輯于星期三

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

數(shù)據(jù)包絡(luò)分析(dataenvelopeanalysis,DEA)網(wǎng)絡(luò)流問題(Networkflow)博弈論(gametheory)等現(xiàn)在是9頁\一共有76頁\編輯于星期三線性規(guī)劃的一般形式現(xiàn)在是10頁\一共有76頁\編輯于星期三線性規(guī)劃的標(biāo)準(zhǔn)形(分析、算法)標(biāo)準(zhǔn)形的特征：極小化、等式約束、變量非負向量表示：現(xiàn)在是11頁\一共有76頁\編輯于星期三一般形式標(biāo)準(zhǔn)形轉(zhuǎn)化稱松弛(slack)/盈余(surplus)變量；自由變量現(xiàn)在是12頁\一共有76頁\編輯于星期三例5.化成標(biāo)準(zhǔn)形等價表示為現(xiàn)在是13頁\一共有76頁\編輯于星期三定義：給定含有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總有解，且至少有一個基本解現(xiàn)在是14頁\一共有76頁\編輯于星期三基本可行解定義稱的非負基本解是標(biāo)準(zhǔn)形的基本可行解(basicfeasiblesolution)；約束系統(tǒng)現(xiàn)在是15頁\一共有76頁\編輯于星期三線性規(guī)劃的基本定理i)若標(biāo)準(zhǔn)型有可行解，則必有基本可行解；ii)若標(biāo)準(zhǔn)型有最優(yōu)解，則必有最優(yōu)基本可行解。

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

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

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

的極點，當(dāng)且僅當(dāng)x是線性規(guī)劃的基本可行解.（線性規(guī)劃基本定理的幾何形式）現(xiàn)在是21頁\一共有76頁\編輯于星期三例2.

K

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

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

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

aq

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

？所以現(xiàn)在是35頁\一共有76頁\編輯于星期三確定離基變量至少有一個正元現(xiàn)在是36頁\一共有76頁\編輯于星期三例3.

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

的任一解x用非基變量表示為度量變量相對于給定基的費用現(xiàn)在是39頁\一共有76頁\編輯于星期三確定進基變量◎最優(yōu)性定理◎定理(BFS的提高)◎相對費用系數(shù)的經(jīng)濟解釋！(合成價格、相對價格)

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

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

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

◆退化基本可行解：某個或某些基變量取零的基本可行解！問題：基本可行解與基的對應(yīng)關(guān)系？現(xiàn)在是40頁\一共有76頁\編輯于星期三4.計算過程－單純形法單純形表：BFS對應(yīng)規(guī)范形的表格＋既約費用系數(shù)和BFS目標(biāo)值的相反數(shù)現(xiàn)在是41頁\一共有76頁\編輯于星期三單純形法的步驟步0形成與初始BFS對應(yīng)的初始表格.

通過行變換求出第一張單純形表.步1若對每個j都有，停；當(dāng)前BFS是最優(yōu)的.步2選取q滿足步4以為轉(zhuǎn)軸元進行轉(zhuǎn)軸，更新單純形表，返步1.步3若，停，問題無界；否則，選p滿足轉(zhuǎn)軸規(guī)則：進基變量：最小相對費用系數(shù)規(guī)則；出基變量：最小指標(biāo)規(guī)則！現(xiàn)在是42頁\一共有76頁\編輯于星期三例1.

化標(biāo)準(zhǔn)形轉(zhuǎn)軸得標(biāo)準(zhǔn)形的初始表格/第一張單純形表現(xiàn)在是43頁\一共有76頁\編輯于星期三轉(zhuǎn)軸0↓-2↓-4↓-27/5轉(zhuǎn)軸現(xiàn)在是44頁\一共有76頁\編輯于星期三最優(yōu)解：最優(yōu)值：原問題的極大值：現(xiàn)在是45頁\一共有76頁\編輯于星期三退化(degenerate)與循環(huán)(cycling)◎退化問題⊙單純形法可能出現(xiàn)循環(huán)！⊙實際中經(jīng)常碰到退化問題，但很少出現(xiàn)循環(huán)⊙避免出現(xiàn)循環(huán)的措施：攝動法、Bland法則、字典序法

基本可行解是退化的當(dāng)且僅當(dāng)單純形表最后一列有一個或者多個零！一次轉(zhuǎn)軸是退化的當(dāng)且僅當(dāng)目標(biāo)函數(shù)沒有發(fā)生變化！現(xiàn)在是46頁\一共有76頁\編輯于星期三最小系數(shù)規(guī)則：◎進基變量：最小系數(shù)規(guī)則◎出基變量：最小指標(biāo)規(guī)則循環(huán)的例子Beale循環(huán)定義：從某張單純形表開始返回到該單純形表的一串轉(zhuǎn)軸轉(zhuǎn)軸規(guī)則：選取進基變量和離基變量的明確規(guī)則現(xiàn)在是47頁\一共有76頁\編輯于星期三現(xiàn)在是48頁\一共有76頁\編輯于星期三現(xiàn)在是49頁\一共有76頁\編輯于星期三

循環(huán)！注：循環(huán)轉(zhuǎn)軸序列中所有BFS都是退化的！是同一個BFS！第七張單純形表現(xiàn)在是50頁\一共有76頁\編輯于星期三避免循環(huán)的方法⊙如果有多個費用系數(shù)是負的，選取下標(biāo)最小的相對費用系數(shù)對應(yīng)的變量為進基變量◎攝動法(Charnes，1952年)◎

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

Orden和Wolfe，1954年)⊙如果最小正比值在多個指標(biāo)處取得，取下標(biāo)最小者對應(yīng)的變量為進基變量美好愿望：構(gòu)造某種永遠不會產(chǎn)生循環(huán)的轉(zhuǎn)軸規(guī)則！現(xiàn)在是51頁\一共有76頁\編輯于星期三前四張單純形表相同！利用Bland法則作為轉(zhuǎn)軸規(guī)則求解Beale的例子！現(xiàn)在是52頁\一共有76頁\編輯于星期三最后一張單純形表/最優(yōu)單純形表現(xiàn)在是53頁\一共有76頁\編輯于星期三單純形法的收斂性◎

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

對非退化線性規(guī)劃，從任一基本可行解出發(fā)，利用單純形法可在有限步內(nèi)得到最優(yōu)解或判斷問題無界.◎收斂性定理：現(xiàn)在是54頁\一共有76頁\編輯于星期三5.兩階段法如何啟動單純形法－人工變量◎目標(biāo)判斷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)造輔助問題人工變量現(xiàn)在是55頁\一共有76頁\編輯于星期三得到原問題的基本可行解◎z*>0，無可行解！◎z*=0，有可行解！⊙

基變量中無人工變量→x

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

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

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

行數(shù)據(jù)以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸得輔助問題的一個新最優(yōu)BFS，且基變量中少1個人工變量！現(xiàn)在是56頁\一共有76頁\編輯于星期三例1.

給出下面系統(tǒng)的一個基本可行解，或者說明其無解引入人工變量目標(biāo)：輔助問題的初始表格！BFS現(xiàn)在是57頁\一共有76頁\編輯于星期三第一張單純形表第二張單純形表注意基變量整列包括末行z在內(nèi)除了基變量其他元素都是0現(xiàn)在是58頁\一共有76頁\編輯于星期三輔助問題的最優(yōu)值是0.原問題的BFS：現(xiàn)在是59頁\一共有76頁\編輯于星期三兩階段法－可求任一線性規(guī)劃問題◎

第I階段：啟動單純形法

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

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

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

→原問題無界或者有解現(xiàn)在是60頁\一共有76頁\編輯于星期三例2.

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

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

的逆矩陣現(xiàn)在是64頁\一共有76頁\編輯于星期三7.單純形法的矩陣形式給定基B

及對應(yīng)BFS(xB,0),其中xB=B-1b用非基變量表示目標(biāo)函數(shù)：用非基變量表示基變量：相對費用向量現(xiàn)在是65頁\一共有76頁\編輯于星期三初始表格－單純形表初始表格通常不是單純形表！與基矩陣B

對應(yīng)的單純形表現(xiàn)在是66頁\一共有76頁\編輯于星期三修正單純形法的計算步驟步2選取q滿足步3計算yq=B-1aq；若步1計算