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

實(shí)用優(yōu)化方法

第2章線性規(guī)劃：?jiǎn)渭冃畏?/p>

劉紅英理學(xué)院數(shù)學(xué)系實(shí)用優(yōu)化方法

第2章線性規(guī)劃：?jiǎn)渭冃畏?/p>

劉紅英1線性規(guī)劃：目標(biāo)函數(shù)是線性的，約束條件是線性等式或不等式線性規(guī)劃線性規(guī)劃：目標(biāo)函數(shù)是線性的，約束條件是線性規(guī)劃2線性規(guī)劃的歷史淵源要追溯到Euler、Liebnitz、Lagrange等GeorgeDantzig,NonNeumann(Princeton)和LeonidKantorovich在1940’s創(chuàng)建了線性規(guī)劃1947年,GeorgeDantzig于發(fā)明了單純形法1979年，L.Khachain找到了求解線性規(guī)劃的一種有效方法(第一個(gè)多項(xiàng)式時(shí)間算法－橢球內(nèi)點(diǎn)法)1984年，NarendraKarmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強(qiáng)有力的競(jìng)爭(zhēng)者(投影內(nèi)點(diǎn)法)現(xiàn)在求解大規(guī)模、退化問(wèn)題最有效的是原－對(duì)偶內(nèi)點(diǎn)法線性規(guī)劃的歷史淵源要追溯到Euler、Liebnitz、La3線性規(guī)劃單純形法-課件4線性規(guī)劃單純形法-課件5線性規(guī)劃單純形法-課件6◎問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最小？◎變量：n種食品，m種營(yíng)養(yǎng)成份；－第j種食品的單價(jià)－每單位第j種食品所含第i種營(yíng)養(yǎng)的數(shù)量

－食用第j種食品的數(shù)量－為了健康，每天必須食用第i種營(yíng)養(yǎng)的數(shù)量◎模型：例1.食譜問(wèn)題◎問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最??？◎變量：n7例2.運(yùn)輸問(wèn)題產(chǎn)銷平衡/不平衡的運(yùn)輸問(wèn)題例2.運(yùn)輸問(wèn)題產(chǎn)銷平衡/不平衡的運(yùn)輸問(wèn)題8

例3.目標(biāo)值帶絕對(duì)值的問(wèn)題

假設(shè)：事實(shí)：轉(zhuǎn)化為：

例3.目標(biāo)值帶絕對(duì)值的問(wèn)題

假設(shè)：事實(shí)：轉(zhuǎn)化為：9

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

數(shù)據(jù)包絡(luò)分析(dataenvelopeanalysis,DEA)網(wǎng)絡(luò)流問(wèn)題(Networkflow)博弈論(gametheory)等

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

數(shù)據(jù)包絡(luò)分析(dataenvelope10線性規(guī)劃的一般形式線性規(guī)劃的一般形式11線性規(guī)劃的標(biāo)準(zhǔn)形(分析、算法)*****標(biāo)準(zhǔn)形的特征：極小化、等式約束、變量非負(fù)向量表示：線性規(guī)劃的標(biāo)準(zhǔn)形(分析、算法)*****標(biāo)準(zhǔn)形的特征：極小化12一般形式標(biāo)準(zhǔn)形轉(zhuǎn)化稱

松弛(slack)/盈余(surplus)變量一般形式標(biāo)準(zhǔn)形轉(zhuǎn)化稱松弛(slack)/盈余(13例5.化成標(biāo)準(zhǔn)形等價(jià)表示為例5.化成標(biāo)準(zhǔn)形等價(jià)表示為14定義設(shè)B是A的m個(gè)線性無(wú)關(guān)列組成的矩陣.置所有與B無(wú)關(guān)列對(duì)應(yīng)的變量為零，稱所得方程組的解是Ax=b的基本解(basicsolution)稱B是基(basis)；稱與B對(duì)應(yīng)的變量為基變量(basicvariables)基本解與基變量(*****)其中滿秩假定：m<n，且A的行向量線性無(wú)關(guān)定義設(shè)B是A的m個(gè)線性無(wú)關(guān)列組成的矩陣.置所有與B無(wú)15基本可行解定義稱的非負(fù)基本解是標(biāo)準(zhǔn)形的基本可行解(basicfeasiblesolution)；例6.基本可行解及幾何意義基本可行解的個(gè)數(shù)不超過(guò)基本可行解定義稱的非負(fù)基本解是標(biāo)準(zhǔn)形的基本可行解16線性規(guī)劃的基本定理(*****)i)若有可行解，則必存在基本可行解；ii)若有解，則必有某個(gè)基本可行解是最優(yōu)解.考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中A是秩為m的m×n階矩陣，則以下結(jié)論成立：線性規(guī)劃的基本定理(*****)i)若有可行解，則必存在基17與凸性的關(guān)系線性規(guī)劃的基本定理(標(biāo)準(zhǔn)形)基本可行解線性方程組的基本性質(zhì)代數(shù)理論(與表述形式有關(guān))設(shè)計(jì)算法極點(diǎn)凸集理論幾何理論(與表述形式無(wú)關(guān))直觀理解與凸性的關(guān)系線性規(guī)劃的基本定理(標(biāo)準(zhǔn)形)基本可行解線性方程組18凸性(凸集及性質(zhì))幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集合中性質(zhì)定義是凸集(convexset)，如果對(duì)S中任意兩點(diǎn)x,y和(0,1)中的任一數(shù)滿足凸性(凸集及性質(zhì))幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集19一些重要的凸集有限個(gè)閉半空間的交集多面集(polyhedralconvexset):推廣平面上：多邊形注：任一線性規(guī)劃的可行集是多面集！超平面(hyperplane):正/負(fù)閉半空間：一些重要的凸集有限個(gè)閉半空間的交集多面集(polyhedra20極點(diǎn)幾何上：極點(diǎn)即不能位于連接該集合中其它兩點(diǎn)的開(kāi)線段上的點(diǎn)定義稱凸集C中的點(diǎn)x是C的極點(diǎn)，如果存在C中的點(diǎn)y,z和某，有則必有y=z.極點(diǎn)幾何上：極點(diǎn)即不能位于連接該集合中其它兩點(diǎn)的開(kāi)線段上的點(diǎn)21極點(diǎn)與基本可行解的等價(jià)性定理推論：線性規(guī)劃基本定理的幾何形式i)若K非空，則至少有一個(gè)極點(diǎn).ii)若線性規(guī)劃有解，則必有一個(gè)極點(diǎn)是最優(yōu)解.iii)K的極點(diǎn)是有限集.

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

的極點(diǎn)當(dāng)且僅當(dāng)x是線性規(guī)劃的基本可行解.極點(diǎn)與基本可行解的等價(jià)性定理推論：線性規(guī)劃基本定理的i)若22例2.

K有2個(gè)極點(diǎn)有3個(gè)基本解，2個(gè)可行K有3個(gè)極點(diǎn)有3個(gè)基本解，均可行例1.例2.K有2個(gè)極點(diǎn)有3個(gè)基本解，2個(gè)可行K有3個(gè)極點(diǎn)有23例3.Subjectto5個(gè)極點(diǎn)－極點(diǎn)問(wèn)題/作業(yè)考慮集合證明這兩個(gè)集合的極點(diǎn)是一一對(duì)應(yīng)的！例3.Subjectto5個(gè)極點(diǎn)－極點(diǎn)問(wèn)題/作業(yè)考慮集合24線性規(guī)劃問(wèn)題解的幾種情況線性規(guī)劃問(wèn)題解的幾種情況25線性規(guī)劃解的幾何特征唯一解(頂點(diǎn))！線性規(guī)劃解的唯一解(頂點(diǎn))！26頂點(diǎn)一條邊無(wú)(下)界頂點(diǎn)一條邊無(wú)(下)界27線性規(guī)劃解的幾何特征無(wú)界：沒(méi)有有限最優(yōu)解不可行：沒(méi)有可行解無(wú)解可行集：多邊形(二維)→多邊集(高維空間)給出有效的代數(shù)刻畫和嚴(yán)謹(jǐn)?shù)膸缀蚊枋?，從理論上證實(shí)上述幾何特征，并尋求有效算法有解：唯一解/多個(gè)解(整條邊、面、甚至整個(gè)可行集)有頂點(diǎn)解線性規(guī)劃解的幾何特征無(wú)界：沒(méi)有有限最優(yōu)解無(wú)解可行集：多邊形(28單純形法簡(jiǎn)介適用形式：標(biāo)準(zhǔn)形(基本可行解=極點(diǎn))理論基礎(chǔ)：線性規(guī)劃的基本定理！基本思想：從約束集的某個(gè)極點(diǎn)/BFS開(kāi)始，依次移動(dòng)到相鄰極點(diǎn)/BFS，直到找出最優(yōu)解，或判斷問(wèn)題無(wú)界.初試化：如何找到一個(gè)BFS？判斷準(zhǔn)則：何時(shí)最優(yōu)？何時(shí)無(wú)界？迭代規(guī)則：如何從一個(gè)極點(diǎn)/BFS迭代到相鄰極點(diǎn)/BFS？單純形法簡(jiǎn)介適用形式：標(biāo)準(zhǔn)形(基本可行解=極點(diǎn))初試化：如何291.轉(zhuǎn)軸(基本解→相鄰基本解)滿秩假定：A是行滿秩的1.轉(zhuǎn)軸(基本解→相鄰基本解)滿秩假定：30規(guī)范形(canonicalform)基本解基變量非基變量等價(jià)變形不妨設(shè)線性無(wú)關(guān)一般地：次序可以打亂！只要有m個(gè)單位列規(guī)范形(canonicalform)基本解基變量非基變量等31規(guī)范形的轉(zhuǎn)換問(wèn)題⊙什么時(shí)候可以替換？⊙替換后新規(guī)范形是什么？◎替換問(wèn)題假設(shè)在上述規(guī)范形中，想用規(guī)范形的轉(zhuǎn)換問(wèn)題⊙什么時(shí)候可以替換？⊙替換后新規(guī)范形是什32轉(zhuǎn)軸(pivot)◎當(dāng)且僅當(dāng)，可以替換◎替換后，新規(guī)范形的系數(shù)轉(zhuǎn)軸公式－轉(zhuǎn)軸元(pivotelement)第二種解釋：表格中第i列的數(shù)據(jù)－用當(dāng)前基表示ai時(shí)的系數(shù)轉(zhuǎn)軸(pivot)◎當(dāng)且僅當(dāng)，可以替換◎替換后33轉(zhuǎn)軸例1.求下列方程組以為基變量的基本解轉(zhuǎn)軸例1.求下列方程組以為基變量的基本解34轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸x=(0,0,0,4,2,1)轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸x=(0,0,0,4,2,1)35如何得到第一個(gè)規(guī)范形處理：給表格附加m個(gè)單位列向量開(kāi)始迭代，用A中的列依次替換這些單位列向量以下運(yùn)算同例1!例2.

利用轉(zhuǎn)軸解方程組為了得到第一個(gè)規(guī)范形，形成增廣表格如何得到第一個(gè)規(guī)范形處理：給表格附加m個(gè)單位列向量開(kāi)始迭代，362.BFS→相鄰BFS(極點(diǎn)→相鄰極點(diǎn))◎問(wèn)題：確定出基變量，使轉(zhuǎn)軸后新規(guī)范形對(duì)應(yīng)BFS？設(shè)x是BFS,且規(guī)范形如前，且假設(shè)

aq進(jìn)基因?yàn)榱羁煞襁x取合適的使得是BFS？所以2.BFS→相鄰BFS(極點(diǎn)→相鄰極點(diǎn))◎問(wèn)題：確定出基變37確定離基變量至少有一個(gè)正元確定離基變量至少有一個(gè)正元38例3.

考慮線性方程組a4進(jìn)基轉(zhuǎn)軸B=(a1,a2,a3)X=(4,3,1,0,0,0)a1進(jìn)基x=(0,1,3,2,0,0)例3.考慮線性方程組a4進(jìn)基轉(zhuǎn)軸B=(a1,a2,a3)a393.BFS→目標(biāo)值減小的相鄰BFS⊙將Ax=b的任一解用非基變量表示；設(shè)x是BFS，且規(guī)范形如前，則有◎問(wèn)題：確定進(jìn)基變量，轉(zhuǎn)軸后使新BFS的目標(biāo)值變?。坑梅腔兞勘硎?——選取進(jìn)基變量的依據(jù)⊙將目標(biāo)函數(shù)3.BFS→目標(biāo)值減小的相鄰BFS⊙將Ax=b的任一解用40相對(duì)/既約費(fèi)用系數(shù)(relative/reducedcostcoefficients)將Ax=b

的任一解x用非基變量表示為相對(duì)/既約費(fèi)用系數(shù)(relative/reducedcos41確定進(jìn)基變量◎最優(yōu)性定理◎定理(BFS的提高)◎相對(duì)費(fèi)用系數(shù)的經(jīng)濟(jì)解釋！(合成價(jià)格、相對(duì)價(jià)格)給定目標(biāo)值為z0的非退化基本可行解，且假定存在j使得rj<0，則

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

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

◆退化基本可行解：某個(gè)或某些基變量取零的基本可行解！問(wèn)題：基本可行解與基的對(duì)應(yīng)關(guān)系？確定進(jìn)基變量◎最優(yōu)性定理◎定理(BFS的提高)◎相對(duì)費(fèi)用系數(shù)424.計(jì)算過(guò)程－單純形法單純形表：BFS對(duì)應(yīng)規(guī)范形的表格＋既約費(fèi)用系數(shù)和BFS目標(biāo)值的相反數(shù)單純形表可以提供計(jì)算所需的所有信息！4.計(jì)算過(guò)程－單純形法單純形表：BFS對(duì)應(yīng)規(guī)范形的表格＋單43如何得到第一張單純形表◎用轉(zhuǎn)軸運(yùn)算(初等行變換)將最后一行與基變量對(duì)應(yīng)的元素化為零，即得第一張單純形表！◎初始表格：BFS對(duì)應(yīng)規(guī)范形的表格＋[c0]如何得到第一張單純形表◎用轉(zhuǎn)軸運(yùn)算(初等行變換)將◎初始44例1.

化標(biāo)準(zhǔn)形轉(zhuǎn)軸得標(biāo)準(zhǔn)形的初始表格/第一張單純形表例1.化標(biāo)準(zhǔn)形轉(zhuǎn)軸得標(biāo)準(zhǔn)形的初始表格/第一張單純形表45轉(zhuǎn)軸0↓-2↓-4↓-27/5轉(zhuǎn)軸轉(zhuǎn)軸0轉(zhuǎn)軸46最優(yōu)解：最優(yōu)值：原問(wèn)題的極大值：最優(yōu)解：最優(yōu)值：原問(wèn)題的極大值：47單純形法的步驟步0形成與初始BFS對(duì)應(yīng)的初始表格.通過(guò)行變換求出第一張單純形表.步1若對(duì)每個(gè)j都有，停；當(dāng)前BFS是最優(yōu)的.步2選取q滿足步4以為轉(zhuǎn)軸元進(jìn)行轉(zhuǎn)軸，更新單純形表，返步1.步3若，停，問(wèn)題無(wú)界；否則，選p滿足轉(zhuǎn)軸規(guī)則：進(jìn)基變量：最小相對(duì)費(fèi)用系數(shù)規(guī)則；出基變量：最小指標(biāo)規(guī)則！單純形法的步驟步0形成與初始BFS對(duì)應(yīng)的初始表格.步148單純形法的收斂性◎非退化線性規(guī)劃：任一基本可行解非退化

對(duì)非退化線性規(guī)劃，從任一基本可行解出發(fā)，利用單純形法可在有限步內(nèi)得到最優(yōu)解或判斷問(wèn)題無(wú)界.◎收斂性定理：?jiǎn)渭冃畏ǖ氖諗啃浴蚍峭嘶€性規(guī)劃：任一基本可行解非退化495.如何啟動(dòng)單純形法－人工變量◎目標(biāo)判斷Ax=b,x≥0是否有界；有解時(shí)找一個(gè)基本可行解；⊙給有需要的行乘以-1，使得b≥0◎方法(x,y)=(0,b)是基本可行解！故可以(0,b)為初始BFS，利用單純形法求解輔助問(wèn)題假設(shè)最后得最優(yōu)解(x,y)、最優(yōu)值z(mì)*和最優(yōu)基B⊙構(gòu)造輔助問(wèn)題人工變量5.如何啟動(dòng)單純形法－人工變量◎目標(biāo)判斷Ax=b50得到原問(wèn)題的基本可行解◎z*>0，無(wú)可行解！◎z*=0，有可行解！⊙基變量中無(wú)人工變量→x

是BFS，B是對(duì)應(yīng)的基⊙基變量中有人工變量→驅(qū)趕人工變量出基假設(shè)第i個(gè)基變量是人工變量，且當(dāng)前單純形表第i行的前n個(gè)數(shù)據(jù)是第i個(gè)約束冗余；刪除單純形表的第i

行數(shù)據(jù)以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸得輔助問(wèn)題的一個(gè)新最優(yōu)BFS，且基變量中少1個(gè)人工變量！得到原問(wèn)題的基本可行解◎z*>0，無(wú)可行解！◎z*=51例1.

給出下面系統(tǒng)的一個(gè)基本可行解，或者說(shuō)明其無(wú)解引入人工變量目標(biāo)：輔助問(wèn)題的初始表格！BFS例1.給出下面系統(tǒng)的一個(gè)基本可行解，或者說(shuō)明其無(wú)解引入人工52第一張單純形表第二張單純形表第一張第二張53輔助問(wèn)題的最優(yōu)值是0.原問(wèn)題的BFS：輔助問(wèn)題的最優(yōu)值是0.原問(wèn)題的BFS：54例2.

利用兩階段法求解下面的問(wèn)題輔助問(wèn)題第I階段：例2.利用兩階段法求解下面的問(wèn)題輔助問(wèn)題第I階段：55輔助問(wèn)題的最后一張單純形表原問(wèn)題的初始表格：輔助問(wèn)題的最后一張單純形表原問(wèn)題的初始表格：56原問(wèn)題的最優(yōu)解：原問(wèn)題的最優(yōu)解：57兩階段法－可求任一線性規(guī)劃問(wèn)題◎第I階段：?jiǎn)?dòng)單純形法

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

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

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

→原問(wèn)題無(wú)界或者有解兩階段法－可求任一線性規(guī)劃問(wèn)題◎第I階段：?jiǎn)?dòng)單純形法58退化(degenerate)與循環(huán)(cycling)◎退化問(wèn)題⊙單純形法可能出現(xiàn)循環(huán)！⊙實(shí)際中經(jīng)常碰到退化問(wèn)題，但很少出現(xiàn)循環(huán)⊙避免出現(xiàn)循環(huán)的措施：攝動(dòng)法、Bland法則、字典序法

基本可行解是退化的當(dāng)且僅當(dāng)單純形表最后一列有一個(gè)或者多個(gè)零！一次轉(zhuǎn)軸是退化的當(dāng)且僅當(dāng)目標(biāo)函數(shù)沒(méi)有發(fā)生變化！退化(degenerate)與循環(huán)(cycling)◎退化問(wèn)59最小系數(shù)規(guī)則：◎進(jìn)基變量：最小系數(shù)規(guī)則◎出基變量：最小指標(biāo)規(guī)則循環(huán)的例子Beale循環(huán)定義：從某張單純形表開(kāi)始返回到該單純形表的一串轉(zhuǎn)軸轉(zhuǎn)軸規(guī)則：選取進(jìn)基變量和離基變量的明確規(guī)則(可以選時(shí)！)最小系數(shù)規(guī)則：◎進(jìn)基變量：最小系數(shù)規(guī)則循環(huán)的例子Beale60線性規(guī)劃單純形法-課件61線性規(guī)劃單純形法-課件62

循環(huán)！注：循環(huán)轉(zhuǎn)軸序列中所有BFS都是退化的！是同一個(gè)BFS！第七張單純形表循環(huán)！注：循環(huán)轉(zhuǎn)軸序列中所有BFS都是退化的！是同一個(gè)BF63避免循環(huán)的方法⊙能進(jìn)基的變量(使目標(biāo)值減小)中選指標(biāo)最小者進(jìn)基◎攝動(dòng)法(Dantzig，1954年)◎

Bland法則(Bland,1977)－最小指標(biāo)法則◎字典序法(Orden和Wolfe，1954年)⊙能出基的變量(保持可行)中選指標(biāo)最小者出基美好愿望：構(gòu)造某種永遠(yuǎn)不會(huì)產(chǎn)生循環(huán)的轉(zhuǎn)軸規(guī)則！避免循環(huán)的方法⊙能進(jìn)基的變量(使目標(biāo)值減小)中選指標(biāo)最小者進(jìn)64前四張單純形表相同！利用Bland法則作為轉(zhuǎn)軸規(guī)則求解Beale的例子！前四張單純形表相同！利用Bland法則作為轉(zhuǎn)軸規(guī)則求解Bea65最后一張單純形表/最優(yōu)單純形表最后一張單純形表/最優(yōu)單純形表66退化的線性規(guī)劃－退化的基本可行解(幾何解釋)對(duì)于標(biāo)準(zhǔn)形而言，當(dāng)極點(diǎn)僅對(duì)應(yīng)一個(gè)基時(shí)，是非退化的；當(dāng)極點(diǎn)對(duì)應(yīng)多個(gè)基時(shí)，是退化的。退化的線性規(guī)劃－退化的基本可行解(幾何解釋)676.單純形法的矩陣形式給定基B

及對(duì)應(yīng)BFS(xB,0),其中xB=B-1b用非基變量表示目標(biāo)函數(shù)：用非基變量表示基變量：相對(duì)費(fèi)用向量6.單純形法的矩陣形式給定基B及對(duì)應(yīng)BFS(xB,68初始表格－單純形表初始表格通常不是單純形表！與基矩陣B

對(duì)應(yīng)的單純形表初始表格－單純形表初始表格與基矩陣B對(duì)應(yīng)的單純形表697.修正單純形法(Revisedsimplexmethod)◎重要事實(shí)：⊙通常僅有少數(shù)列發(fā)生轉(zhuǎn)軸(2m-3m)◎

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

的逆矩陣7.修正單純形法(Revisedsimplexmeth70修正單純形法的計(jì)算步驟步2選取q滿足步3計(jì)算yq=B-1aq；若步1計(jì)算。如果停；得最優(yōu)解.步0給定BFS及對(duì)應(yīng)的B-1。計(jì)算核心計(jì)算：B-1涉及到的計(jì)算：，停，問(wèn)題無(wú)界；否則，選p滿足步4更新B-1,B-1b和，返步1.修正單純形法的計(jì)算步驟步2選取q滿足步3計(jì)算71基的轉(zhuǎn)換定理左乘該矩陣等價(jià)于對(duì)矩陣進(jìn)行初等行變換！定理不妨設(shè)B=.則aq進(jìn)基，ap出基后所得新基的逆這里ei

表示n

維單位向量，向量v定義為基的轉(zhuǎn)換定理左乘該矩陣等價(jià)于對(duì)矩陣進(jìn)行初等行變換！定理不72相關(guān)數(shù)據(jù)的更新－初等行變換設(shè)轉(zhuǎn)軸元是，即aq出基，ap進(jìn)基以為轉(zhuǎn)軸元，轉(zhuǎn)軸后即得新基對(duì)應(yīng)的數(shù)據(jù)！相關(guān)數(shù)據(jù)的更新－初等行變換設(shè)轉(zhuǎn)軸元是，即aq出基，73例1求解例2.3.4例1求解例2.3.474a2進(jìn)基，計(jì)算y2.計(jì)算表格如下：計(jì)算a2進(jìn)基，計(jì)算y2.計(jì)算表格如下：計(jì)算75a1進(jìn)基，計(jì)算y1.得如下表格：a1進(jìn)基，計(jì)算y1.得如下表格：76最優(yōu)值：最優(yōu)解：最優(yōu)值：最優(yōu)解：77問(wèn)題.設(shè)用單純形法求解標(biāo)準(zhǔn)形式的LP時(shí)得到如下單純形表.還假設(shè)矩陣A的后三列形成單位矩陣1.給出由該表描述的當(dāng)前基是最優(yōu)的充分必要條件(依照表中的系數(shù)).2.假設(shè)該基是最優(yōu)的且.找出另外一個(gè)最優(yōu)基本可行解，其與該表所描述的不同.問(wèn)題.設(shè)用單純形法求解標(biāo)準(zhǔn)形式的LP時(shí)得到如下1.給出由該78假定與當(dāng)前表所聯(lián)系的基是最優(yōu)的假設(shè)將原問(wèn)題中的，給出使基保持最優(yōu)的的范圍.假設(shè)將原問(wèn)題中的，給出使基保持最優(yōu)的的范圍問(wèn)題.設(shè)用單純形法求解標(biāo)準(zhǔn)形式的LP時(shí)得到如下單純形表.還假設(shè)矩陣A的后三列形成單位矩陣假定與當(dāng)前表所聯(lián)系的基是最優(yōu)的問(wèn)題.設(shè)用單純形法求解標(biāo)準(zhǔn)形79實(shí)用優(yōu)化方法

第2章線性規(guī)劃：?jiǎn)渭冃畏?/p>

劉紅英理學(xué)院數(shù)學(xué)系實(shí)用優(yōu)化方法

第2章線性規(guī)劃：?jiǎn)渭冃畏?/p>

劉紅英80線性規(guī)劃：目標(biāo)函數(shù)是線性的，約束條件是線性等式或不等式線性規(guī)劃線性規(guī)劃：目標(biāo)函數(shù)是線性的，約束條件是線性規(guī)劃81線性規(guī)劃的歷史淵源要追溯到Euler、Liebnitz、Lagrange等GeorgeDantzig,NonNeumann(Princeton)和LeonidKantorovich在1940’s創(chuàng)建了線性規(guī)劃1947年,GeorgeDantzig于發(fā)明了單純形法1979年，L.Khachain找到了求解線性規(guī)劃的一種有效方法(第一個(gè)多項(xiàng)式時(shí)間算法－橢球內(nèi)點(diǎn)法)1984年，NarendraKarmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強(qiáng)有力的競(jìng)爭(zhēng)者(投影內(nèi)點(diǎn)法)現(xiàn)在求解大規(guī)模、退化問(wèn)題最有效的是原－對(duì)偶內(nèi)點(diǎn)法線性規(guī)劃的歷史淵源要追溯到Euler、Liebnitz、La82線性規(guī)劃單純形法-課件83線性規(guī)劃單純形法-課件84線性規(guī)劃單純形法-課件85◎問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最小？◎變量：n種食品，m種營(yíng)養(yǎng)成份；－第j種食品的單價(jià)－每單位第j種食品所含第i種營(yíng)養(yǎng)的數(shù)量

－食用第j種食品的數(shù)量－為了健康，每天必須食用第i種營(yíng)養(yǎng)的數(shù)量◎模型：例1.食譜問(wèn)題◎問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最小？◎變量：n86例2.運(yùn)輸問(wèn)題產(chǎn)銷平衡/不平衡的運(yùn)輸問(wèn)題例2.運(yùn)輸問(wèn)題產(chǎn)銷平衡/不平衡的運(yùn)輸問(wèn)題87

例3.目標(biāo)值帶絕對(duì)值的問(wèn)題

假設(shè)：事實(shí)：轉(zhuǎn)化為：

例3.目標(biāo)值帶絕對(duì)值的問(wèn)題

假設(shè)：事實(shí)：轉(zhuǎn)化為：88

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

數(shù)據(jù)包絡(luò)分析(dataenvelopeanalysis,DEA)網(wǎng)絡(luò)流問(wèn)題(Networkflow)博弈論(gametheory)等

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

數(shù)據(jù)包絡(luò)分析(dataenvelope89線性規(guī)劃的一般形式線性規(guī)劃的一般形式90線性規(guī)劃的標(biāo)準(zhǔn)形(分析、算法)*****標(biāo)準(zhǔn)形的特征：極小化、等式約束、變量非負(fù)向量表示：線性規(guī)劃的標(biāo)準(zhǔn)形(分析、算法)*****標(biāo)準(zhǔn)形的特征：極小化91一般形式標(biāo)準(zhǔn)形轉(zhuǎn)化稱

松弛(slack)/盈余(surplus)變量一般形式標(biāo)準(zhǔn)形轉(zhuǎn)化稱松弛(slack)/盈余(92例5.化成標(biāo)準(zhǔn)形等價(jià)表示為例5.化成標(biāo)準(zhǔn)形等價(jià)表示為93定義設(shè)B是A的m個(gè)線性無(wú)關(guān)列組成的矩陣.置所有與B無(wú)關(guān)列對(duì)應(yīng)的變量為零，稱所得方程組的解是Ax=b的基本解(basicsolution)稱B是基(basis)；稱與B對(duì)應(yīng)的變量為基變量(basicvariables)基本解與基變量(*****)其中滿秩假定：m<n，且A的行向量線性無(wú)關(guān)定義設(shè)B是A的m個(gè)線性無(wú)關(guān)列組成的矩陣.置所有與B無(wú)94基本可行解定義稱的非負(fù)基本解是標(biāo)準(zhǔn)形的基本可行解(basicfeasiblesolution)；例6.基本可行解及幾何意義基本可行解的個(gè)數(shù)不超過(guò)基本可行解定義稱的非負(fù)基本解是標(biāo)準(zhǔn)形的基本可行解95線性規(guī)劃的基本定理(*****)i)若有可行解，則必存在基本可行解；ii)若有解，則必有某個(gè)基本可行解是最優(yōu)解.考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中A是秩為m的m×n階矩陣，則以下結(jié)論成立：線性規(guī)劃的基本定理(*****)i)若有可行解，則必存在基96與凸性的關(guān)系線性規(guī)劃的基本定理(標(biāo)準(zhǔn)形)基本可行解線性方程組的基本性質(zhì)代數(shù)理論(與表述形式有關(guān))設(shè)計(jì)算法極點(diǎn)凸集理論幾何理論(與表述形式無(wú)關(guān))直觀理解與凸性的關(guān)系線性規(guī)劃的基本定理(標(biāo)準(zhǔn)形)基本可行解線性方程組97凸性(凸集及性質(zhì))幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集合中性質(zhì)定義是凸集(convexset)，如果對(duì)S中任意兩點(diǎn)x,y和(0,1)中的任一數(shù)滿足凸性(凸集及性質(zhì))幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集98一些重要的凸集有限個(gè)閉半空間的交集多面集(polyhedralconvexset):推廣平面上：多邊形注：任一線性規(guī)劃的可行集是多面集！超平面(hyperplane):正/負(fù)閉半空間：一些重要的凸集有限個(gè)閉半空間的交集多面集(polyhedra99極點(diǎn)幾何上：極點(diǎn)即不能位于連接該集合中其它兩點(diǎn)的開(kāi)線段上的點(diǎn)定義稱凸集C中的點(diǎn)x是C的極點(diǎn)，如果存在C中的點(diǎn)y,z和某，有則必有y=z.極點(diǎn)幾何上：極點(diǎn)即不能位于連接該集合中其它兩點(diǎn)的開(kāi)線段上的點(diǎn)100極點(diǎn)與基本可行解的等價(jià)性定理推論：線性規(guī)劃基本定理的幾何形式i)若K非空，則至少有一個(gè)極點(diǎn).ii)若線性規(guī)劃有解，則必有一個(gè)極點(diǎn)是最優(yōu)解.iii)K的極點(diǎn)是有限集.

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

的極點(diǎn)當(dāng)且僅當(dāng)x是線性規(guī)劃的基本可行解.極點(diǎn)與基本可行解的等價(jià)性定理推論：線性規(guī)劃基本定理的i)若101例2.

K有2個(gè)極點(diǎn)有3個(gè)基本解，2個(gè)可行K有3個(gè)極點(diǎn)有3個(gè)基本解，均可行例1.例2.K有2個(gè)極點(diǎn)有3個(gè)基本解，2個(gè)可行K有3個(gè)極點(diǎn)有102例3.Subjectto5個(gè)極點(diǎn)－極點(diǎn)問(wèn)題/作業(yè)考慮集合證明這兩個(gè)集合的極點(diǎn)是一一對(duì)應(yīng)的！例3.Subjectto5個(gè)極點(diǎn)－極點(diǎn)問(wèn)題/作業(yè)考慮集合103線性規(guī)劃問(wèn)題解的幾種情況線性規(guī)劃問(wèn)題解的幾種情況104線性規(guī)劃解的幾何特征唯一解(頂點(diǎn))！線性規(guī)劃解的唯一解(頂點(diǎn))！105頂點(diǎn)一條邊無(wú)(下)界頂點(diǎn)一條邊無(wú)(下)界106線性規(guī)劃解的幾何特征無(wú)界：沒(méi)有有限最優(yōu)解不可行：沒(méi)有可行解無(wú)解可行集：多邊形(二維)→多邊集(高維空間)給出有效的代數(shù)刻畫和嚴(yán)謹(jǐn)?shù)膸缀蚊枋觯瑥睦碚撋献C實(shí)上述幾何特征，并尋求有效算法有解：唯一解/多個(gè)解(整條邊、面、甚至整個(gè)可行集)有頂點(diǎn)解線性規(guī)劃解的幾何特征無(wú)界：沒(méi)有有限最優(yōu)解無(wú)解可行集：多邊形(107單純形法簡(jiǎn)介適用形式：標(biāo)準(zhǔn)形(基本可行解=極點(diǎn))理論基礎(chǔ)：線性規(guī)劃的基本定理！基本思想：從約束集的某個(gè)極點(diǎn)/BFS開(kāi)始，依次移動(dòng)到相鄰極點(diǎn)/BFS，直到找出最優(yōu)解，或判斷問(wèn)題無(wú)界.初試化：如何找到一個(gè)BFS？判斷準(zhǔn)則：何時(shí)最優(yōu)？何時(shí)無(wú)界？迭代規(guī)則：如何從一個(gè)極點(diǎn)/BFS迭代到相鄰極點(diǎn)/BFS？單純形法簡(jiǎn)介適用形式：標(biāo)準(zhǔn)形(基本可行解=極點(diǎn))初試化：如何1081.轉(zhuǎn)軸(基本解→相鄰基本解)滿秩假定：A是行滿秩的1.轉(zhuǎn)軸(基本解→相鄰基本解)滿秩假定：109規(guī)范形(canonicalform)基本解基變量非基變量等價(jià)變形不妨設(shè)線性無(wú)關(guān)一般地：次序可以打亂！只要有m個(gè)單位列規(guī)范形(canonicalform)基本解基變量非基變量等110規(guī)范形的轉(zhuǎn)換問(wèn)題⊙什么時(shí)候可以替換？⊙替換后新規(guī)范形是什么？◎替換問(wèn)題假設(shè)在上述規(guī)范形中，想用規(guī)范形的轉(zhuǎn)換問(wèn)題⊙什么時(shí)候可以替換？⊙替換后新規(guī)范形是什111轉(zhuǎn)軸(pivot)◎當(dāng)且僅當(dāng)，可以替換◎替換后，新規(guī)范形的系數(shù)轉(zhuǎn)軸公式－轉(zhuǎn)軸元(pivotelement)第二種解釋：表格中第i列的數(shù)據(jù)－用當(dāng)前基表示ai時(shí)的系數(shù)轉(zhuǎn)軸(pivot)◎當(dāng)且僅當(dāng)，可以替換◎替換后112轉(zhuǎn)軸例1.求下列方程組以為基變量的基本解轉(zhuǎn)軸例1.求下列方程組以為基變量的基本解113轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸x=(0,0,0,4,2,1)轉(zhuǎn)軸轉(zhuǎn)軸轉(zhuǎn)軸x=(0,0,0,4,2,1)114如何得到第一個(gè)規(guī)范形處理：給表格附加m個(gè)單位列向量開(kāi)始迭代，用A中的列依次替換這些單位列向量以下運(yùn)算同例1!例2.

利用轉(zhuǎn)軸解方程組為了得到第一個(gè)規(guī)范形，形成增廣表格如何得到第一個(gè)規(guī)范形處理：給表格附加m個(gè)單位列向量開(kāi)始迭代，1152.BFS→相鄰BFS(極點(diǎn)→相鄰極點(diǎn))◎問(wèn)題：確定出基變量，使轉(zhuǎn)軸后新規(guī)范形對(duì)應(yīng)BFS？設(shè)x是BFS,且規(guī)范形如前，且假設(shè)

aq進(jìn)基因?yàn)榱羁煞襁x取合適的使得是BFS？所以2.BFS→相鄰BFS(極點(diǎn)→相鄰極點(diǎn))◎問(wèn)題：確定出基變116確定離基變量至少有一個(gè)正元確定離基變量至少有一個(gè)正元117例3.

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

的任一解x用非基變量表示為相對(duì)/既約費(fèi)用系數(shù)(relative/reducedcos120確定進(jìn)基變量◎最優(yōu)性定理◎定理(BFS的提高)◎相對(duì)費(fèi)用系數(shù)的經(jīng)濟(jì)解釋！(合成價(jià)格、相對(duì)價(jià)格)給定目標(biāo)值為z0的非退化基本可行解，且假定存在j使得rj<0，則

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

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

◆退化基本可行解：某個(gè)或某些基變量取零的基本可行解！問(wèn)題：基本可行解與基的對(duì)應(yīng)關(guān)系？確定進(jìn)基變量◎最優(yōu)性定理◎定理(BFS的提高)◎相對(duì)費(fèi)用系數(shù)1214.計(jì)算過(guò)程－單純形法單純形表：BFS對(duì)應(yīng)規(guī)范形的表格＋既約費(fèi)用系數(shù)和BFS目標(biāo)值的相反數(shù)單純形表可以提供計(jì)算所需的所有信息！4.計(jì)算過(guò)程－單純形法單純形表：BFS對(duì)應(yīng)規(guī)范形的表格＋單122如何得到第一張單純形表◎用轉(zhuǎn)軸運(yùn)算(初等行變換)將最后一行與基變量對(duì)應(yīng)的元素化為零，即得第一張單純形表！◎初始表格：BFS對(duì)應(yīng)規(guī)范形的表格＋[c0]如何得到第一張單純形表◎用轉(zhuǎn)軸運(yùn)算(初等行變換)將◎初始123例1.

化標(biāo)準(zhǔn)形轉(zhuǎn)軸得標(biāo)準(zhǔn)形的初始表格/第一張單純形表例1.化標(biāo)準(zhǔn)形轉(zhuǎn)軸得標(biāo)準(zhǔn)形的初始表格/第一張單純形表124轉(zhuǎn)軸0↓-2↓-4↓-27/5轉(zhuǎn)軸轉(zhuǎn)軸0轉(zhuǎn)軸125最優(yōu)解：最優(yōu)值：原問(wèn)題的極大值：最優(yōu)解：最優(yōu)值：原問(wèn)題的極大值：126單純形法的步驟步0形成與初始BFS對(duì)應(yīng)的初始表格.通過(guò)行變換求出第一張單純形表.步1若對(duì)每個(gè)j都有，停；當(dāng)前BFS是最優(yōu)的.步2選取q滿足步4以為轉(zhuǎn)軸元進(jìn)行轉(zhuǎn)軸，更新單純形表，返步1.步3若，停，問(wèn)題無(wú)界；否則，選p滿足轉(zhuǎn)軸規(guī)則：進(jìn)基變量：最小相對(duì)費(fèi)用系數(shù)規(guī)則；出基變量：最小指標(biāo)規(guī)則！單純形法的步驟步0形成與初始BFS對(duì)應(yīng)的初始表格.步1127單純形法的收斂性◎非退化線性規(guī)劃：任一基本可行解非退化

對(duì)非退化線性規(guī)劃，從任一基本可行解出發(fā)，利用單純形法可在有限步內(nèi)得到最優(yōu)解或判斷問(wèn)題無(wú)界.◎收斂性定理：?jiǎn)渭冃畏ǖ氖諗啃浴蚍峭嘶€性規(guī)劃：任一基本可行解非退化1285.如何啟動(dòng)單純形法－人工變量◎目標(biāo)判斷Ax=b,x≥0是否有界；有解時(shí)找一個(gè)基本可行解；⊙給有需要的行乘以-1，使得b≥0◎方法(x,y)=(0,b)是基本可行解！故可以(0,b)為初始BFS，利用單純形法求解輔助問(wèn)題假設(shè)最后得最優(yōu)解(x,y)、最優(yōu)值z(mì)*和最優(yōu)基B⊙構(gòu)造輔助問(wèn)題人工變量5.如何啟動(dòng)單純形法－人工變量◎目標(biāo)判斷Ax=b129得到原問(wèn)題的基本可行解◎z*>0，無(wú)可行解！◎z*=0，有可行解！⊙基變量中無(wú)人工變量→x

是BFS，B是對(duì)應(yīng)的基⊙基變量中有人工變量→驅(qū)趕人工變量出基假設(shè)第i個(gè)基變量是人工變量，且當(dāng)前單純形表第i行的前n個(gè)數(shù)據(jù)是第i個(gè)約束冗余；刪除單純形表的第i

行數(shù)據(jù)以任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸得輔助問(wèn)題的一個(gè)新最優(yōu)BFS，且基變量中少1個(gè)人工變量！得到原問(wèn)題的基本可行解◎z*>0，無(wú)可行解！◎z*=130例1.

給出下面系統(tǒng)的一個(gè)基本可行解，或者說(shuō)明其無(wú)解引入人工變量目標(biāo)：輔助問(wèn)題的初始表格！BFS例1.給出下面系統(tǒng)的一個(gè)基本可行解，或者說(shuō)明其無(wú)解引入人工131第一張單純形表第二張單純形表第一張第二張132輔助問(wèn)題的最優(yōu)值是0.原問(wèn)題的BFS：輔助問(wèn)題的最優(yōu)值是0.原問(wèn)題的BFS：133例2.

利用兩階段法求解下面的問(wèn)題輔助問(wèn)題第I階段：例2.利用兩階段法求解下面的問(wèn)題輔助問(wèn)題第I階段：134輔助問(wèn)題的最后一張單純形表原問(wèn)題的初始表格：輔助問(wèn)題的最后一張單純形表原問(wèn)題的初始表格：135原問(wèn)題的最優(yōu)解：原問(wèn)題的最優(yōu)解：136兩階段法－可求任一線性規(guī)劃問(wèn)題◎第I階段：?jiǎn)?dòng)單純形法

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

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

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

→原問(wèn)題無(wú)界或者有解兩階段法－可求任一線性規(guī)劃問(wèn)題◎第I階段：?jiǎn)?dòng)單純形法137退化(degenerate)與循環(huán)(cycling)◎退化問(wèn)題⊙單純形法可能出現(xiàn)循環(huán)！⊙實(shí)際中經(jīng)常碰到退化問(wèn)題，但很少出現(xiàn)循環(huán)⊙避免出現(xiàn)循環(huán)的措施：攝動(dòng)法、Bland法則、字典序法

基本可行解是退化的當(dāng)且僅當(dāng)單純形表最后一列有一個(gè)或者多個(gè)零！一次轉(zhuǎn)軸是退化的當(dāng)且僅當(dāng)目標(biāo)函數(shù)沒(méi)有發(fā)生變化！退化(degenerate)與循環(huán)(cycling)◎退化問(wèn)138最小系數(shù)規(guī)則：◎進(jìn)基變量：最小系數(shù)規(guī)則◎出基變量：最小指標(biāo)規(guī)則循環(huán)的例子Beale循環(huán)定義：從某張單純形表開(kāi)始返回到該單純形表的一串轉(zhuǎn)軸轉(zhuǎn)軸規(guī)則：選取進(jìn)基變量和離基變量的明確規(guī)則(可以選時(shí)！)最小系數(shù)規(guī)則：◎進(jìn)基變量：最小系數(shù)規(guī)則循環(huán)的例子Beale139線性規(guī)劃單純形法-課件140線性規(guī)劃單純形法-課件141

循環(huán)！注：循環(huán)轉(zhuǎn)軸序列中所有BFS都是退化的！是同一個(gè)BFS！第七張單純形表循環(huán)！注：循環(huán)轉(zhuǎn)軸序列中所有BFS都是退化的！是同一個(gè)BF142避免循環(huán)的方法⊙能進(jìn)基的變量(使目標(biāo)值減小)中選指標(biāo)最小者進(jìn)基◎攝動(dòng)法(Dantzig，1954年)◎

Bland法則(Bland,1977)－最小指標(biāo)法則◎字典序法(Orden和Wolfe，1954年)⊙能出基的變量(保持可行)中選指標(biāo)最小者出基美好愿望：構(gòu)造某種永遠(yuǎn)不會(huì)產(chǎn)生循環(huán)的轉(zhuǎn)軸規(guī)則！避免循環(huán)的方法⊙能進(jìn)基的變量(使目標(biāo)值減小)中選指標(biāo)最小者進(jìn)143前四張