線性規(guī)劃_單純形法ppt課件

1、實用優(yōu)化方法實用優(yōu)化方法第第2章線性規(guī)劃：單純形法章線性規(guī)劃：單純形法劉紅英劉紅英理學(xué)院數(shù)學(xué)系理學(xué)院數(shù)學(xué)系線性規(guī)劃：目標函數(shù)是線性的，約束條件是線性規(guī)劃：目標函數(shù)是線性的，約束條件是線性等式或不等式線性等式或不等式線性規(guī)劃線性規(guī)劃線性規(guī)劃的歷史線性規(guī)劃的歷史 淵源要追溯到淵源要追溯到Euler、Liebnitz、Lagrange等等 George Dantzig, Non Neumann(Princeton)和和Leonid Kantorovich在在1940s創(chuàng)建了線性規(guī)劃創(chuàng)建了線性規(guī)劃 1947年年, George Dantzig于發(fā)明了單純形法于發(fā)明了單純形法 1979年，年，L. Kh

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

3、 j 種食品的單價種食品的單價每單位第每單位第 j 種食品所含第種食品所含第 i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量食用第食用第 j 種食品的數(shù)量種食品的數(shù)量為了健康，每天必須食用第為了健康，每天必須食用第i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量 模型：模型：例例1. 1. 食譜問題食譜問題例例2. 運輸問題運輸問題產(chǎn)銷平衡產(chǎn)銷平衡/不平衡的運輸問題不平衡的運輸問題例例3. 目標值帶絕對值的問題目標值帶絕對值的問題假設(shè)：假設(shè)：現(xiàn)實：現(xiàn)實：轉(zhuǎn)化為：轉(zhuǎn)化為：例例4. 其它應(yīng)用其它應(yīng)用 數(shù)據(jù)包絡(luò)分析數(shù)據(jù)包絡(luò)分析(data envelope analysis, (data envelope analysis, DEA)DE

4、A) 網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題(Network flow)(Network flow) 博弈論博弈論(game theory)(game theory)等等線性規(guī)劃的一般形式線性規(guī)劃的一般形式線性規(guī)劃的標準形線性規(guī)劃的標準形(分析、算法分析、算法)*標準形的特征：極小化、等式約束、變量非負標準形的特征：極小化、等式約束、變量非負向量表示：向量表示：一般形式一般形式 標準形標準形轉(zhuǎn)化轉(zhuǎn)化稱稱 松弛松弛(slack)/盈余盈余(surplus)變量變量例例5. 5. 化成標準形化成標準形等價表示為等價表示為定義定義 設(shè)設(shè)B是是A 的的m個線性無關(guān)列組成的矩陣個線性無關(guān)列組成的矩陣. 置置所有與所有與B

5、無關(guān)列對應(yīng)的變量為零，稱所得方程組無關(guān)列對應(yīng)的變量為零，稱所得方程組的解是的解是Ax=b的基本解的基本解(basic solution) 稱稱B是基是基(basis)；稱與稱與B對應(yīng)的變量為基變量對應(yīng)的變量為基變量(basic variables)基本解與基變量基本解與基變量(*)其中其中滿秩假定：滿秩假定：mn，且，且A的行向量線性無關(guān)的行向量線性無關(guān)基本可行解基本可行解定義定義 稱稱 的非負基本解是標準形的基的非負基本解是標準形的基本可行解本可行解(basic feasible solution)(basic feasible solution)；例例6. 6. 基本可行解及幾何意義基本可

6、行解及幾何意義基本可行解的個數(shù)不超過基本可行解的個數(shù)不超過線性規(guī)劃的基本定理線性規(guī)劃的基本定理(*)i) 若有可行解，則必存在基本可行解；若有可行解，則必存在基本可行解；ii) 若有解，則必有某個基本可行解是最優(yōu)解若有解，則必有某個基本可行解是最優(yōu)解. 考慮線性規(guī)劃標準形，其中考慮線性規(guī)劃標準形，其中A是秩為是秩為m的的mn階階矩陣，則以下結(jié)論成立：矩陣，則以下結(jié)論成立：與凸性的關(guān)系與凸性的關(guān)系線性規(guī)劃的基本定理線性規(guī)劃的基本定理( (標準形標準形) )基本可行解基本可行解線性方程組線性方程組的基本性質(zhì)的基本性質(zhì)代數(shù)理論代數(shù)理論(與表述形式與表述形式有關(guān)有關(guān))設(shè)計算法設(shè)計算法極點極點凸集理論凸

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

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

9、規(guī)劃有解，則必有一個極點是最優(yōu)解若線性規(guī)劃有解，則必有一個極點是最優(yōu)解.iii) K的極點是有限集的極點是有限集.考慮線性規(guī)劃標準形，其中考慮線性規(guī)劃標準形，其中A是秩為是秩為m的的mn矩陣，令矩陣，令則則x是是 K 的極點當且僅當?shù)臉O點當且僅當x是線性規(guī)劃的基本可行是線性規(guī)劃的基本可行解解.例例2. 2. K有有2個極點個極點有有3個基本解，個基本解，2個可行個可行K 有有3個極點個極點有有3個基本解，均可行個基本解，均可行例例1. 1. 例例3. 3. Subject to5個極點個極點極點極點問題問題/ /作業(yè)作業(yè)考慮集合考慮集合證明這兩個集合的極點是一一對應(yīng)的！證明這兩個集合的極點是一

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

11、邊、面、甚至整個可行集整個可行集) ) 有頂點解有頂點解單純形法簡介單純形法簡介 適用形式：標準形適用形式：標準形(基本可行解基本可行解=極點極點) 理論基礎(chǔ)：線性規(guī)劃的基本定理！理論基礎(chǔ)：線性規(guī)劃的基本定理！ 基本思想：從約束集的某個極點基本思想：從約束集的某個極點/BFS開始，開始，依次移動到相鄰極點依次移動到相鄰極點/BFS，直到找出最優(yōu)，直到找出最優(yōu)解，或判斷問題無界解，或判斷問題無界. 初試化：如何找到一個初試化：如何找到一個BFS？ 判斷準則：何時最優(yōu)？何時無界？判斷準則：何時最優(yōu)？何時無界？ 迭代規(guī)則：如何從一個極點迭代規(guī)則：如何從一個極點/BFS迭代到相迭代到相鄰極點鄰極點/B

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

13、轉(zhuǎn)軸公式轉(zhuǎn)軸元轉(zhuǎn)軸元(pivot element)第二種解釋：第二種解釋：表格中第表格中第 i 列的數(shù)據(jù)用當前基表示列的數(shù)據(jù)用當前基表示 ai 時的系數(shù)時的系數(shù)轉(zhuǎn)軸例例1. 求下列方程組以求下列方程組以 為基變?yōu)榛兞康幕窘饬康幕窘廪D(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸x=(0,0,0,4,2,1)如何得到第一個規(guī)范形如何得到第一個規(guī)范形處置：處置：給表格附加給表格附加m個單位列向量開始迭代，用個單位列向量開始迭代，用A中的列依次替換這些單位列向量中的列依次替換這些單位列向量以下運算以下運算同例同例1 !例例2. 利用轉(zhuǎn)軸解方程組利用轉(zhuǎn)軸解方程組為了得到第一個規(guī)范形，形成增廣表格為了得到第一個規(guī)范形，形

14、成增廣表格2.BFS相鄰相鄰BFS(極點極點相鄰極點相鄰極點)問題：問題：確定出基變量，使轉(zhuǎn)軸后新規(guī)范形對應(yīng)確定出基變量，使轉(zhuǎn)軸后新規(guī)范形對應(yīng)BFS？設(shè)設(shè)x是是BFS, 且規(guī)范形如前，且假設(shè)且規(guī)范形如前，且假設(shè) aq 進基進基由于由于令令可否選取合適的可否選取合適的 使得使得 是是BFS ？所以所以確定離基變量確定離基變量至少有一個正元至少有一個正元例例3. 考慮線性方程組考慮線性方程組a4進基進基轉(zhuǎn)軸轉(zhuǎn)軸B=(a1,a2,a3)X=(4,3,1,0,0,0)a1進基進基x=(0,1,3,2,0,0)3. BFS目標值減小的相鄰目標值減小的相鄰BFS 將將Ax=b的任一解用非基變量表示；的任一

15、解用非基變量表示；設(shè)設(shè)x是是BFS，且規(guī)范形如前，則有，且規(guī)范形如前，則有問題：問題：確定進基變量，轉(zhuǎn)軸后使新確定進基變量，轉(zhuǎn)軸后使新BFS的目標值變??？的目標值變??？用非基變量表示用非基變量表示. 選取進基變量的依據(jù)選取進基變量的依據(jù) 將目標函數(shù)將目標函數(shù)相對相對/既約費用系數(shù)既約費用系數(shù)(relative/reduced cost coefficients)將將 Ax=b 的任一解的任一解 x 用非基變量表示為用非基變量表示為確定進基變量確定進基變量最優(yōu)性定理最優(yōu)性定理定理定理(BFS的提高的提高)相對費用系數(shù)的經(jīng)濟解釋！相對費用系數(shù)的經(jīng)濟解釋！(合成價格、相對價格合成價格、相對價格) 給

16、定目標值為給定目標值為z0的非退化基本可行解，且假定存的非退化基本可行解，且假定存在在 j 使得使得 rj 0，無可行解！，無可行解！ z*= 0，有可行解！，有可行解！ 基變量中無人工變量基變量中無人工變量x x 是是BFSBFS，B B 是對應(yīng)的基是對應(yīng)的基 基變量中有人工變量基變量中有人工變量驅(qū)趕人工變量出基驅(qū)趕人工變量出基假設(shè)第假設(shè)第 i 個基變量是人工變量，且當前單純形表個基變量是人工變量，且當前單純形表第第 i 行的前行的前n個數(shù)據(jù)是個數(shù)據(jù)是第第 i 個約束冗余；個約束冗余；刪除單純形表的第刪除單純形表的第 i 行數(shù)據(jù)行數(shù)據(jù)以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸得輔助問題

17、的一個新最優(yōu)得輔助問題的一個新最優(yōu)BFS，且基變量中少，且基變量中少1個人工變量！個人工變量！例例1. 給出下面系統(tǒng)的一個基本可行解，或者說明其無解給出下面系統(tǒng)的一個基本可行解，或者說明其無解引入人工變量引入人工變量目的：目的：輔助問題的輔助問題的初始表格！初始表格！BFS第一張第一張單純形表單純形表第二張第二張單純形表單純形表輔助問題的最優(yōu)值是輔助問題的最優(yōu)值是0. 0. 原問題的原問題的BFSBFS：例例2. 利用兩階段法求解下面的問題利用兩階段法求解下面的問題輔助問題輔助問題第第I階段：階段：輔助問題的最后一張單純形表輔助問題的最后一張單純形表原問題的初始表格：原問題的初始表格：原問題的

18、最優(yōu)解：原問題的最優(yōu)解：兩階段法可求任一線性規(guī)劃問題兩階段法可求任一線性規(guī)劃問題 第第I階段：啟動單純形法階段：啟動單純形法 構(gòu)造、求解輔助問題構(gòu)造、求解輔助問題 判斷原問題不可行、或可行判斷原問題不可行、或可行 可行時找到基本可行解及對應(yīng)規(guī)范形可行時找到基本可行解及對應(yīng)規(guī)范形 第第II階段：利用單純形法求原問題階段：利用單純形法求原問題 從上述從上述BFS出發(fā)，求解所給問題出發(fā)，求解所給問題 原問題無界或者有解原問題無界或者有解退化退化(degenerate)與循環(huán)與循環(huán)(cycling)退化問題退化問題 單純形法可能出現(xiàn)循環(huán)！單純形法可能出現(xiàn)循環(huán)！ 實際中經(jīng)常碰到退化問題，但很少出現(xiàn)循環(huán)實

19、際中經(jīng)常碰到退化問題，但很少出現(xiàn)循環(huán) 避免出現(xiàn)循環(huán)的措施：攝動法、避免出現(xiàn)循環(huán)的措施：攝動法、Bland法則、字典序法法則、字典序法 基本可行解是退化的當且僅當單純形表最后一列有基本可行解是退化的當且僅當單純形表最后一列有一個或者多個零！一次轉(zhuǎn)軸是退化的當且僅當目標函數(shù)一個或者多個零！一次轉(zhuǎn)軸是退化的當且僅當目標函數(shù)沒有發(fā)生變化！沒有發(fā)生變化！最小系數(shù)規(guī)則：最小系數(shù)規(guī)則： 進基變量：最小系數(shù)規(guī)則進基變量：最小系數(shù)規(guī)則 出基變量：最小指標規(guī)則出基變量：最小指標規(guī)則循環(huán)的例子循環(huán)的例子Beale循環(huán)循環(huán)定義：從某張單純形表開始返回到該單純形表的一串轉(zhuǎn)軸定義：從某張單純形表開始返回到該單純形表的一串

20、轉(zhuǎn)軸轉(zhuǎn)軸規(guī)則：選取進基變量和離基變量的明確規(guī)則轉(zhuǎn)軸規(guī)則：選取進基變量和離基變量的明確規(guī)則(可以選時！可以選時！)循環(huán)！循環(huán)！注：循環(huán)轉(zhuǎn)軸序列中所有注：循環(huán)轉(zhuǎn)軸序列中所有BFS都是退化的！是都是退化的！是同一個同一個BFS！第七張單純形表第七張單純形表避免循環(huán)的方法避免循環(huán)的方法 能進基的變量能進基的變量(使目標值減小使目標值減小)中選指標最小者進基中選指標最小者進基 攝動法攝動法(Dantzig，1954年年) Bland法則法則(Bland, 1977)最小指標法則最小指標法則 字典序法字典序法(Orden和和Wolfe，1954年年) 能出基的變量能出基的變量(保持可行保持可行)中選指標最

21、小者出基中選指標最小者出基美好愿望：構(gòu)造某種永遠不會產(chǎn)生循環(huán)的轉(zhuǎn)軸規(guī)則！美好愿望：構(gòu)造某種永遠不會產(chǎn)生循環(huán)的轉(zhuǎn)軸規(guī)則！前四張單純形表相同！前四張單純形表相同！利用利用Bland法則作為轉(zhuǎn)軸規(guī)則求解法則作為轉(zhuǎn)軸規(guī)則求解Beale的例子！的例子！最后一張單純形表最后一張單純形表/ /最優(yōu)單純形表最優(yōu)單純形表退化的線性規(guī)劃退化的基本可行解退化的線性規(guī)劃退化的基本可行解(幾何解釋幾何解釋) 對于標準形而言，當極點僅對應(yīng)一個基時，是非退化的；對于標準形而言，當極點僅對應(yīng)一個基時，是非退化的；當極點對應(yīng)多個基時，是退化的。當極點對應(yīng)多個基時，是退化的。6. 單純形法的矩陣形式單純形法的矩陣形式給定基給定基

22、 B 及對應(yīng)及對應(yīng)BFS (xB, 0), 其中其中xB=B-1b用非基變量表示目標函數(shù)：用非基變量表示目標函數(shù)：用非基變量表示基變量：用非基變量表示基變量：相對費用向量相對費用向量初始表格單純形表初始表格單純形表初始表格初始表格通常不是單純形表！通常不是單純形表！與基矩陣與基矩陣 B 對應(yīng)的單純形表對應(yīng)的單純形表7. 修正單純形法修正單純形法(Revised simplex method) 重要事實：重要事實： 通常僅有少數(shù)列發(fā)生轉(zhuǎn)軸通常僅有少數(shù)列發(fā)生轉(zhuǎn)軸(2m-3m) 核心問題：核心問題：如何更新當前基的逆如何更新當前基的逆新基的逆新基的逆理論上的表現(xiàn)理論上的表現(xiàn)表格實現(xiàn)表格實現(xiàn) 僅需原始數(shù)據(jù)僅需原始數(shù)據(jù)(c, A, b)和基和基 B 的逆矩陣的逆矩陣修正單純形法的計算步驟修正單純形法的計算步驟步步2 選取選取 q 滿足滿足步步3 計算計算 yq=B-1aq；假設(shè)；假設(shè)步步1 計算計算 。假設(shè)。假設(shè) 停；得最優(yōu)解停；得最優(yōu)解.步步0 給定給定BFS及對應(yīng)的及對應(yīng)的B-1。計算。計算核心計算：核心計算：B-1涉及到的計算：涉及到的計算： ， 停，問題無界；否則，選停，問題無界；否則，選 p 滿足滿足步步4 更新更新 B-1, B-1b和和 ，返步，返步1.基的轉(zhuǎn)換定理基的轉(zhuǎn)換定理左乘該矩陣等價