2 最優(yōu)化方法-線性規(guī)劃-單純形法ppt課件

1、實(shí)用優(yōu)化方法實(shí)用優(yōu)化方法線性規(guī)劃：單純形法線性規(guī)劃：單純形法1.2線性規(guī)劃線性規(guī)劃：目標(biāo)函數(shù)是線性的，約束條件是目標(biāo)函數(shù)是線性的，約束條件是線性等式或不等式線性等式或不等式線性規(guī)劃線性規(guī)劃3線性規(guī)劃的歷史線性規(guī)劃的歷史淵源要追溯到淵源要追溯到Euler、Liebnitz、Lagrange等等George Dantzig, Von Neumann(Princeton)和和Leonid Kantorovich在在1940s創(chuàng)建了線性規(guī)劃創(chuàng)建了線性規(guī)劃1947年年, George Dantzig發(fā)明了單純形法發(fā)明了單純形法1979年，年，L. Khachain找到了求解線性規(guī)劃的一種有效方法找到了求

2、解線性規(guī)劃的一種有效方法(第一個(gè)多項(xiàng)式時(shí)第一個(gè)多項(xiàng)式時(shí)間算法間算法橢球內(nèi)點(diǎn)法橢球內(nèi)點(diǎn)法)1984年，年，Narendra Karmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強(qiáng)有力的競爭者證明是單純形法的強(qiáng)有力的競爭者(投影內(nèi)點(diǎn)法投影內(nèi)點(diǎn)法)現(xiàn)在求解大規(guī)模、退化問題最有效的是現(xiàn)在求解大規(guī)模、退化問題最有效的是原對偶內(nèi)點(diǎn)法原對偶內(nèi)點(diǎn)法4567 問題：確定食品數(shù)量，滿足營養(yǎng)需求，花費(fèi)最??？問題：確定食品數(shù)量，滿足營養(yǎng)需求，花費(fèi)最小？ 變量：變量：n種食品，種食品，m種營養(yǎng)成份；第種營養(yǎng)成份；第 j 種食品的單價(jià)種食品的單價(jià)每單位第每單位第

3、j 種食品所含第種食品所含第 i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量食用第食用第 j 種食品的數(shù)量種食品的數(shù)量為了健康，每天必須食用第為了健康，每天必須食用第i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量 模型：模型：例例1. 1. 食譜問題食譜問題8例例2. 運(yùn)輸問題運(yùn)輸問題產(chǎn)銷平衡產(chǎn)銷平衡/不平衡的運(yùn)輸問題不平衡的運(yùn)輸問題9例例3. 其它應(yīng)用其它應(yīng)用數(shù)據(jù)包絡(luò)分析數(shù)據(jù)包絡(luò)分析(data envelope analysis, DEA)網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題(Network flow)博弈論博弈論(game theory)等等10線性規(guī)劃的一般形式線性規(guī)劃的一般形式11線性規(guī)劃的標(biāo)準(zhǔn)形線性規(guī)劃的標(biāo)準(zhǔn)形(分析、算法分析、算法)

4、標(biāo)準(zhǔn)形的特征：標(biāo)準(zhǔn)形的特征：極小化極小化、等式約束等式約束、變量非負(fù)變量非負(fù)向量表示：向量表示：12一般形式一般形式 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形轉(zhuǎn)化轉(zhuǎn)化稱稱 松弛松弛(slack)/盈余盈余(surplus)變量；變量；自由變量自由變量13例例5. 5. 化成標(biāo)準(zhǔn)形化成標(biāo)準(zhǔn)形等價(jià)表示為等價(jià)表示為14定義：定義： 給定含有給定含有n個(gè)變量，個(gè)變量，m個(gè)方程的線性方程組個(gè)方程的線性方程組Ax=b，設(shè)，設(shè)B是由是由A 的列組成的任一非奇的列組成的任一非奇異異mm子陣，則如果置子陣，則如果置x的所有與的所有與B無關(guān)的無關(guān)的n-m個(gè)分量為零后，所得方程組的解是個(gè)分量為零后，所得方程組的解是Ax=b關(guān)關(guān)于基于基B的基本

5、解的基本解(basic solution) ，稱，稱x中與基中與基B對應(yīng)的分量為基變量對應(yīng)的分量為基變量(basic variables)退化基本解：退化基本解：基本解中如果有一個(gè)或多個(gè)基變量的值為零基本解中如果有一個(gè)或多個(gè)基變量的值為零基本解與基變量基本解與基變量其中其中滿秩假定：滿秩假定：m n矩陣矩陣A滿足滿足mn，且，且A的行向量線性無關(guān)的行向量線性無關(guān) 在滿秩假定下，方程組在滿秩假定下，方程組Ax=b總有解，且至少有一個(gè)基本總有解，且至少有一個(gè)基本 解解15基本可行解基本可行解定義定義 稱稱 的非負(fù)基本解是的非負(fù)基本解是標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形的基本可行解的基本可行解( (basic feasi

6、ble solution)；約束系統(tǒng)約束系統(tǒng) 16線性規(guī)劃的基本定理線性規(guī)劃的基本定理i) 若標(biāo)準(zhǔn)型有可行解，則必有基本可行解；若標(biāo)準(zhǔn)型有可行解，則必有基本可行解；ii) 若標(biāo)準(zhǔn)型有最優(yōu)解，則必有最優(yōu)基本可行解。若標(biāo)準(zhǔn)型有最優(yōu)解，則必有最優(yōu)基本可行解。 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中A是秩為是秩為m的的mn階階矩陣，則以下結(jié)論成立：矩陣，則以下結(jié)論成立：基本可行解的個(gè)數(shù)不超過基本可行解的個(gè)數(shù)不超過17與凸性的關(guān)系與凸性的關(guān)系線性規(guī)劃的基本定理線性規(guī)劃的基本定理( (標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) )基本可行解基本可行解線性方程組的基線性方程組的基本性質(zhì)本性質(zhì)代數(shù)理論代數(shù)理論(與與表述形式有關(guān)

7、表述形式有關(guān))設(shè)計(jì)算法設(shè)計(jì)算法極點(diǎn)極點(diǎn)凸集理論凸集理論幾何理論幾何理論( (與表述形式與表述形式無關(guān)無關(guān)) )直觀理解直觀理解18凸性凸性( (凸集及性質(zhì)凸集及性質(zhì)) )幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集合中幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集合中性質(zhì)性質(zhì) 定義定義 是凸集是凸集(convex set)，如果對，如果對S中任意中任意 兩兩 點(diǎn)點(diǎn) x , y 和和(0,1)中的任一數(shù)中的任一數(shù) 滿足滿足 19一些重要的凸集一些重要的凸集有限個(gè)閉半空間的交集有限個(gè)閉半空間的交集多面集多面集(polyhedral convex set):推推廣廣平面上：多邊形平面上：多邊形注：任一線性

8、規(guī)劃的可行集是注：任一線性規(guī)劃的可行集是多面集多面集！超平面超平面(hyperplane):正正/ /負(fù)閉半空間：負(fù)閉半空間：20極點(diǎn)極點(diǎn)幾何上：極點(diǎn)即不能位于連接該集合中其它兩點(diǎn)的開線段上的點(diǎn)幾何上：極點(diǎn)即不能位于連接該集合中其它兩點(diǎn)的開線段上的點(diǎn)定義定義 稱凸集稱凸集C中的點(diǎn)中的點(diǎn) x 是是C的極點(diǎn)，如果存在的極點(diǎn)，如果存在 C 中的點(diǎn)中的點(diǎn) y, z 和某和某 ，有有則必有則必有 y=z.21極點(diǎn)與基本可行解的等價(jià)性定理極點(diǎn)與基本可行解的等價(jià)性定理推論：推論：i) 若若K非空，則至少有一個(gè)極點(diǎn)非空，則至少有一個(gè)極點(diǎn).ii) 若線性規(guī)劃有最優(yōu)解，則必有一個(gè)極點(diǎn)是最優(yōu)解若線性規(guī)劃有最優(yōu)解，則

9、必有一個(gè)極點(diǎn)是最優(yōu)解.iii) Ax=b對應(yīng)的約束集對應(yīng)的約束集K最多有有限個(gè)極點(diǎn)最多有有限個(gè)極點(diǎn).考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中A是秩為是秩為m的的mn矩陣，令矩陣，令則則x是是 K 的極點(diǎn)，當(dāng)且僅當(dāng)?shù)臉O點(diǎn)，當(dāng)且僅當(dāng)x是線性規(guī)劃的基本可行解是線性規(guī)劃的基本可行解.（線性規(guī)劃基本定理的幾何形式）（線性規(guī)劃基本定理的幾何形式）22例例2. 2. K有有2個(gè)極點(diǎn)個(gè)極點(diǎn)有有3個(gè)基本解，個(gè)基本解，2個(gè)可行個(gè)可行K 有有3個(gè)極點(diǎn)個(gè)極點(diǎn)有有3個(gè)基本解，均可行個(gè)基本解，均可行例例1. 1. 23例例3. 3. Subject to5個(gè)極點(diǎn)個(gè)極點(diǎn)極點(diǎn)極點(diǎn)24線性規(guī)劃解的線性規(guī)劃解的幾何特征幾

10、何特征唯一唯一 解解(頂點(diǎn)頂點(diǎn))！25線性規(guī)劃解的線性規(guī)劃解的幾何特征幾何特征無界無界：沒有有限最優(yōu)解：沒有有限最優(yōu)解不可行不可行：沒有可行解：沒有可行解無解無解可行集：多邊形可行集：多邊形( (二維二維) )多邊集多邊集( (高維空間高維空間) )給出給出有效的代數(shù)刻畫有效的代數(shù)刻畫和和嚴(yán)謹(jǐn)?shù)膸缀蚊枋鰢?yán)謹(jǐn)?shù)膸缀蚊枋?，從理論上證實(shí)上述幾何特征，從理論上證實(shí)上述幾何特征，并并尋求有效算法尋求有效算法有解：有解：唯一解唯一解/ /多個(gè)解多個(gè)解( (整條邊、面、甚至整個(gè)可行集整條邊、面、甚至整個(gè)可行集) ) 有頂點(diǎn)解有頂點(diǎn)解26頂點(diǎn)頂點(diǎn)一條邊一條邊無無(下下)界界27線性規(guī)劃問題解的幾種情況線性規(guī)劃

11、問題解的幾種情況28單純形法簡介單純形法簡介適用形式：標(biāo)準(zhǔn)形適用形式：標(biāo)準(zhǔn)形(基本可行解基本可行解=極點(diǎn)極點(diǎn))理論基礎(chǔ)：線性規(guī)劃的理論基礎(chǔ)：線性規(guī)劃的基本定理基本定理！基本思想：從約束集的基本思想：從約束集的某個(gè)極點(diǎn)某個(gè)極點(diǎn)/BFS開始，依次移動(dòng)到開始，依次移動(dòng)到相鄰極點(diǎn)相鄰極點(diǎn)/BFS，直，直到找出最優(yōu)解，或判斷問題無界到找出最優(yōu)解，或判斷問題無界.初始化：如何找到一個(gè)初始化：如何找到一個(gè)BFS？判斷準(zhǔn)則：何時(shí)最優(yōu)？何時(shí)無界？判斷準(zhǔn)則：何時(shí)最優(yōu)？何時(shí)無界？迭代規(guī)則：如何從一個(gè)極點(diǎn)迭代規(guī)則：如何從一個(gè)極點(diǎn)/BFS迭代到相鄰極點(diǎn)迭代到相鄰極點(diǎn)/BFS？291.轉(zhuǎn)軸轉(zhuǎn)軸(基本解基本解相鄰基本解相鄰

12、基本解)滿秩假定：滿秩假定：A是行滿秩的是行滿秩的30規(guī)范形規(guī)范形(canonical form)基變量基變量基本解基本解非基變量非基變量等價(jià)變形等價(jià)變形不妨設(shè)不妨設(shè) 線性無關(guān)線性無關(guān) 一般地：一般地：次序可以打亂！次序可以打亂！只要有只要有m個(gè)單位列個(gè)單位列31規(guī)范形的轉(zhuǎn)換問題規(guī)范形的轉(zhuǎn)換問題 什么時(shí)候可以替換？什么時(shí)候可以替換？ 替換后替換后新規(guī)范形新規(guī)范形是什么？是什么？ 替換問題替換問題假設(shè)在上述規(guī)范形中，想用假設(shè)在上述規(guī)范形中，想用32轉(zhuǎn)軸轉(zhuǎn)軸(pivot) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ，可以替換，可以替換 替換后，新規(guī)范形的系數(shù)替換后，新規(guī)范形的系數(shù)轉(zhuǎn)軸公式轉(zhuǎn)軸公式轉(zhuǎn)軸元轉(zhuǎn)軸元(pivot

13、element)33轉(zhuǎn)軸例例1. 求下列方程組以求下列方程組以 為基變量的基本解為基變量的基本解34轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸x=(0,0,0,4,2,1)352.BFS相鄰相鄰BFS(極點(diǎn)極點(diǎn)相鄰極點(diǎn)相鄰極點(diǎn))問題：問題：確定出基變量，使轉(zhuǎn)軸后新規(guī)范形對應(yīng)確定出基變量，使轉(zhuǎn)軸后新規(guī)范形對應(yīng)BFS？設(shè)設(shè)x是是BFS, 且規(guī)范形如前，且且規(guī)范形如前，且假設(shè)假設(shè) aq 進(jìn)基進(jìn)基因?yàn)橐驗(yàn)榱盍羁煞襁x取合適的可否選取合適的 使得使得 是是BFS ？所以所以36確定離基變量確定離基變量至少有一個(gè)正元至少有一個(gè)正元37例例3. 考慮線性方程組考慮線性方程組a4進(jìn)基進(jìn)基轉(zhuǎn)軸轉(zhuǎn)軸B=(a1,a2,a3)X=(4,

14、3,1,0,0,0)x=(0,1,3,2,0,0)383. BFS目標(biāo)值減小的相鄰目標(biāo)值減小的相鄰BFS 將將Ax=b的任一解用非基變量表示；的任一解用非基變量表示；設(shè)設(shè)x是是BFS，且規(guī)范形如前，則有，且規(guī)范形如前，則有問題：問題：確定進(jìn)基變量，轉(zhuǎn)軸后使新確定進(jìn)基變量，轉(zhuǎn)軸后使新BFS的目標(biāo)值變?。康哪繕?biāo)值變小？用非基變量表示用非基變量表示. 選取進(jìn)基變量的依據(jù)選取進(jìn)基變量的依據(jù) 將將目標(biāo)函數(shù)目標(biāo)函數(shù)39相對相對/既約費(fèi)用系數(shù)既約費(fèi)用系數(shù)(relative/reduced cost coefficients)將將 Ax=b 的任一解的任一解 x 用非基變量表示為用非基變量表示為度量變量相對于

15、給定基的費(fèi)用度量變量相對于給定基的費(fèi)用40確定進(jìn)基變量確定進(jìn)基變量最優(yōu)性定理最優(yōu)性定理定理定理(BFS的提高的提高)相對費(fèi)用系數(shù)的經(jīng)濟(jì)解釋！相對費(fèi)用系數(shù)的經(jīng)濟(jì)解釋！(合成價(jià)格、相對價(jià)格合成價(jià)格、相對價(jià)格) 給定目標(biāo)值為給定目標(biāo)值為z0的非退化基本可行解，且假定存在的非退化基本可行解，且假定存在 j 使得使得 rj 0，無可行解！無可行解！ z*= 0，有可行解！有可行解！ 基變量中無人工變量基變量中無人工變量x 是是BFS，B 是對應(yīng)的基是對應(yīng)的基 基變量中有人工變量基變量中有人工變量驅(qū)趕人工變量出基驅(qū)趕人工變量出基假設(shè)第假設(shè)第 i 個(gè)基變量是人工變量，且當(dāng)前單純形表個(gè)基變量是人工變量，且當(dāng)前

16、單純形表第第 i 行的前行的前n個(gè)數(shù)據(jù)是個(gè)數(shù)據(jù)是第第 i 個(gè)約束冗余；個(gè)約束冗余；刪除單純形表的第刪除單純形表的第 i 行數(shù)據(jù)行數(shù)據(jù)以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸得輔助問題的一個(gè)新最優(yōu)得輔助問題的一個(gè)新最優(yōu)BFS，且基變量中少，且基變量中少1個(gè)人工變量！個(gè)人工變量！57例例1. 給出下面系統(tǒng)的一個(gè)基本可行解，或者說明其無解給出下面系統(tǒng)的一個(gè)基本可行解，或者說明其無解引入人工變量引入人工變量目標(biāo)：目標(biāo)：輔助問題的初輔助問題的初始表格！始表格！BFS58第一張第一張單純形表單純形表第二張第二張單純形表單純形表注意基變量整列包括末行z在內(nèi)除了基變量其他元素都是059輔助問題的最優(yōu)值

17、是輔助問題的最優(yōu)值是0. 0. 原問題的原問題的BFS：60兩階段法可求任一線性規(guī)劃問題兩階段法可求任一線性規(guī)劃問題 第第I階段：啟動(dòng)單純形法階段：啟動(dòng)單純形法 構(gòu)造、求解輔助問題構(gòu)造、求解輔助問題 判斷原問題不可行、或可行判斷原問題不可行、或可行 可行時(shí)找到基本可行解及對應(yīng)規(guī)范形可行時(shí)找到基本可行解及對應(yīng)規(guī)范形 第第II階段：利用單純形法求原問題階段：利用單純形法求原問題 從上述從上述BFS出發(fā)，求解所給問題出發(fā)，求解所給問題 原問題無界或者有解原問題無界或者有解61例例2. 利用兩階段法求解下面的問題利用兩階段法求解下面的問題輔助問題輔助問題第第I階段：階段：先構(gòu)造輔助向量z=x4+x56

18、2輔助問題的最后一張單純形表輔助問題的最后一張單純形表原問題的初始表格：原問題的初始表格：得到輔助問題的最后一張單純形表后，去掉輔助變量，將原始問題的z帶入表格，啟動(dòng)單純形法63原問題的最優(yōu)解：原問題的最優(yōu)解：646. 修正單純形法修正單純形法(Revised simplex method) 重要事實(shí)：重要事實(shí)： 通常僅有少數(shù)列發(fā)生轉(zhuǎn)軸通常僅有少數(shù)列發(fā)生轉(zhuǎn)軸(2m-3m) 核心問題：核心問題：如何更新當(dāng)前基的逆如何更新當(dāng)前基的逆新基的逆新基的逆理論上的表現(xiàn)理論上的表現(xiàn)表格實(shí)現(xiàn)表格實(shí)現(xiàn) 僅需原始數(shù)據(jù)僅需原始數(shù)據(jù)(c, A, b)和基和基 B 的逆矩陣的逆矩陣657. 單純形法的矩陣形式單純形法的矩陣形式給定基給定基 B 及對應(yīng)及對應(yīng)BFS (xB, 0), 其中其中xB=B-1b用非基變量表示目標(biāo)函數(shù)：用非基變量表示目標(biāo)函數(shù)：用非基變量表示基變量：用非基變量表示基變量：相對費(fèi)用向量相對費(fèi)用向量66初始表格單純形表初始表格單純形表初始表格初始表格通常不是單純形表！通常不是單純形表！與基矩陣與基矩陣 B