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

1、實(shí)用優(yōu)化方法實(shí)用優(yōu)化方法第第2章線性規(guī)劃：?jiǎn)渭冃畏ㄕ戮€性規(guī)劃：?jiǎn)渭冃畏▌⒓t英劉紅英理學(xué)院數(shù)學(xué)系理學(xué)院數(shù)學(xué)系線性規(guī)劃：目標(biāo)函數(shù)是線性的，約束條件是線性規(guī)劃：目標(biāo)函數(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ī)劃的一種有效方法種有效方法(第一個(gè)多項(xiàng)式時(shí)間算法橢球內(nèi)點(diǎn)法第一個(gè)多項(xiàng)式時(shí)間算法橢球內(nèi)點(diǎn)法) 1984年，年，Narendra Karmarkan發(fā)現(xiàn)了另一種求發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強(qiáng)解線性規(guī)劃的有效方法，已證明是單純形法的強(qiáng)有力的競(jìng)爭(zhēng)者有力的競(jìng)爭(zhēng)者(投影內(nèi)點(diǎn)法投影內(nèi)點(diǎn)法) 現(xiàn)在求解大規(guī)模、退化問(wèn)題最有效的是原對(duì)偶現(xiàn)在求解大規(guī)模、退化問(wèn)題最有效的是原對(duì)偶內(nèi)點(diǎn)法內(nèi)點(diǎn)法 問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最??？問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最?。?變量：變量：n種食品，種食品，m種營(yíng)養(yǎng)成份；第種營(yíng)養(yǎng)成份；第

3、 j 種食品的單價(jià)種食品的單價(jià)每單位第每單位第 j 種食品所含第種食品所含第 i 種營(yíng)養(yǎng)的數(shù)量種營(yíng)養(yǎng)的數(shù)量食用第食用第 j 種食品的數(shù)量種食品的數(shù)量為了健康，每天必須食用第為了健康，每天必須食用第i 種營(yíng)養(yǎng)的數(shù)量種營(yíng)養(yǎng)的數(shù)量 模型：模型：例例1. 1. 食譜問(wèn)題食譜問(wèn)題例例2. 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題產(chǎn)銷平衡產(chǎn)銷平衡/不平衡的運(yùn)輸問(wèn)題不平衡的運(yùn)輸問(wèn)題例例3. 目標(biāo)值帶絕對(duì)值的問(wèn)題目標(biāo)值帶絕對(duì)值的問(wèn)題假設(shè)：假設(shè)：現(xiàn)實(shí)：現(xiàn)實(shí)：轉(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èn)題網(wǎng)絡(luò)流問(wèn)題(Network flow)(Network flow) 博弈論博弈論(game theory)(game theory)等等線性規(guī)劃的一般形式線性規(guī)劃的一般形式線性規(guī)劃的標(biāo)準(zhǔn)形線性規(guī)劃的標(biāo)準(zhǔn)形(分析、算法分析、算法)*標(biāo)準(zhǔn)形的特征：極小化、等式約束、變量非負(fù)標(biāo)準(zhǔn)形的特征：極小化、等式約束、變量非負(fù)向量表示：向量表示：一般形式一般形式 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形轉(zhuǎn)化轉(zhuǎn)化稱稱 松弛松弛(slack)/盈余盈余(surplus)變量變量例例5. 5. 化成標(biāo)準(zhǔn)形化成標(biāo)準(zhǔn)形等價(jià)表示為等價(jià)表示為定義定義 設(shè)設(shè)B是是A 的的m個(gè)線性無(wú)關(guān)列組成的矩陣個(gè)線性無(wú)關(guān)列組成的矩陣. 置置所有與所有與B

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

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

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

8、面集！注：任一線性規(guī)劃的可行集是多面集！超平面超平面(hyperplane):(hyperplane):正正/ /負(fù)閉半空間：負(fù)閉半空間：極點(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.極點(diǎn)與基本可行解的等價(jià)性定理極點(diǎn)與基本可行解的等價(jià)性定理推論：推論：線性規(guī)劃基本定理線性規(guī)劃基本定理的的幾何形式幾何形式i) 若若K非空，則至少有一個(gè)極點(diǎn)非空，則至少有一個(gè)極點(diǎn).ii) 若線性

9、規(guī)劃有解，則必有一個(gè)極點(diǎn)是最優(yōu)解若線性規(guī)劃有解，則必有一個(gè)極點(diǎn)是最優(yōu)解.iii) K的極點(diǎn)是有限集的極點(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ī)劃的基本可行解解.例例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. 例例3. 3. Subject to5個(gè)極點(diǎn)個(gè)極點(diǎn)極點(diǎn)極點(diǎn)問(wèn)題問(wèn)題/ /作業(yè)作業(yè)考慮集合考慮集合證明這兩個(gè)集合的極點(diǎn)是一一對(duì)應(yīng)的！證明這兩個(gè)集合的極點(diǎn)是一

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

11、邊、面、甚至整個(gè)可行集整個(gè)可行集) ) 有頂點(diǎn)解有頂點(diǎn)解單純形法簡(jiǎn)介單純形法簡(jiǎn)介 適用形式：標(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)到相鄰極點(diǎn)依次移動(dòng)到相鄰極點(diǎn)/BFS，直到找出最優(yōu)，直到找出最優(yōu)解，或判斷問(wèn)題無(wú)界解，或判斷問(wèn)題無(wú)界. 初試化：如何找到一個(gè)初試化：如何找到一個(gè)BFS？ 判斷準(zhǔn)則：何時(shí)最優(yōu)？何時(shí)無(wú)界？判斷準(zhǔn)則：何時(shí)最優(yōu)？何時(shí)無(wú)界？ 迭代規(guī)則：如何從一個(gè)極點(diǎn)迭代規(guī)則：如何從一個(gè)極點(diǎn)/BFS迭代到相迭代到相鄰極點(diǎn)鄰極點(diǎn)/B

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

13、轉(zhuǎn)軸公式轉(zhuǎn)軸元轉(zhuǎn)軸元(pivot element)第二種解釋：第二種解釋：表格中第表格中第 i 列的數(shù)據(jù)用當(dāng)前基表示列的數(shù)據(jù)用當(dāng)前基表示 ai 時(shí)的系數(shù)時(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)如何得到第一個(gè)規(guī)范形如何得到第一個(gè)規(guī)范形處置：處置：給表格附加給表格附加m個(gè)單位列向量開始迭代，用個(gè)單位列向量開始迭代，用A中的列依次替換這些單位列向量中的列依次替換這些單位列向量以下運(yùn)算以下運(yùn)算同例同例1 !例例2. 利用轉(zhuǎn)軸解方程組利用轉(zhuǎn)軸解方程組為了得到第一個(gè)規(guī)范形，形成增廣表格為了得到第一個(gè)規(guī)范形，形

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

15、解用非基變量表示；設(shè)設(shè)x是是BFS，且規(guī)范形如前，則有，且規(guī)范形如前，則有問(wèn)題：?jiǎn)栴}：確定進(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ù)相對(duì)相對(duì)/既約費(fèi)用系數(shù)既約費(fèi)用系數(shù)(relative/reduced cost coefficients)將將 Ax=b 的任一解的任一解 x 用非基變量表示為用非基變量表示為確定進(jìn)基變量確定進(jìn)基變量最優(yōu)性定理最優(yōu)性定理定理定理(BFS的提高的提高)相對(duì)費(fèi)用系數(shù)的經(jīng)濟(jì)解釋！相對(duì)費(fèi)用系數(shù)的經(jīng)濟(jì)解釋！(合成價(jià)格、相對(duì)價(jià)格合成價(jià)格、相對(duì)價(jià)格) 給

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

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

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

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

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

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

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