emp_lp_fundenmental_2016_spring

1、第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃：基本理論與方法線性規(guī)劃：基本理論與方法劉紅英劉紅英北航數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院北航數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)目標(biāo)函數(shù)是線性的，約束條件是線性等式或不等式目標(biāo)函數(shù)是線性的，約束條件是線性等式或不等式線性規(guī)劃線性規(guī)劃第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ) 問題問題：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？

2、：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？ 變量：變量：n 種食品，種食品，m 種營養(yǎng)成份；第種營養(yǎng)成份；第 j 種食品的單價種食品的單價每單位第每單位第 j 種食品所含第種食品所含第 i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量第第 j 種食品的數(shù)量種食品的數(shù)量為了健康，每天必須食用第為了健康，每天必須食用第i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量 模型：模型：2.1.1 問題舉例問題舉例例例1. 1. 配餐問題配餐問題第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例4. 其它應(yīng)用其它應(yīng)用 博弈論博弈論(game theory)等等( (習(xí)題習(xí)題2.2

3、6, 2.27) ) 網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題(network flow, 3.1-3.2節(jié)節(jié)) 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃( (3.3-3.4節(jié)節(jié)) ) 數(shù)據(jù)包絡(luò)分析數(shù)據(jù)包絡(luò)分析(data envelope analysis, DEA, Charnes & Copper，1986)例例2. 目標(biāo)函數(shù)中含絕對值的問題目標(biāo)函數(shù)中含絕對值的問題(習(xí)題習(xí)題2.2)例例3. 逐段線性凸函數(shù)逐段線性凸函數(shù)(習(xí)題習(xí)題2.3)是一種對多投入/多產(chǎn)出的多個決策單元的效率進行評價的方法，廣泛應(yīng)用于業(yè)績評價，如快餐分銷店、銀行支行、診所、小學(xué)或者圖書館等第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論

4、與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃線性規(guī)劃解的解的幾何特征幾何特征惟一惟一 解解(頂點頂點)！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)無無(下下)界界沒有沒有 有限有限 解解(-1, -1)一條邊一條邊( 1, 0)一條邊一條邊( 0, 1)惟一的頂點惟一的頂點( 1, 1)解的幾何特征解的幾何特征( 0, 0)(x1, 0), x1 0(0, x2), x20,1Tc*()Tx第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)

5、 無界無界：沒有有限最優(yōu)解：沒有有限最優(yōu)解(極小化時表示無下界，極大化時無上界) 不可行不可行：沒有可行解：沒有可行解無解無解 有解有解：惟一解或多個解惟一解或多個解( (整條邊、面、甚至整個可行集整條邊、面、甚至整個可行集) ) 有頂點解有頂點解線性規(guī)劃解的線性規(guī)劃解的幾何特征幾何特征可行集：可行集：多邊形多邊形( (二維二維) )多面集多面集( (高維空間高維空間) )給出給出頂點頂點有效的有效的代數(shù)刻畫代數(shù)刻畫和和嚴謹?shù)膰乐數(shù)膸缀蚊枋鰩缀蚊枋?，從，從理論理論上上證實上述幾何特征，并證實上述幾何特征，并尋求有效算法尋求有效算法第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法

6、LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃的一般形式線性規(guī)劃的一般形式其中其中 c 是是 n 維向量，維向量， 是是 m 維行向量，維行向量， 是實數(shù)，這些是實數(shù)，這些均是給定的數(shù)據(jù)；均是給定的數(shù)據(jù)； 是變量是變量 .第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.1.2 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形(便于分析分析和設(shè)計算法便于分析分析和設(shè)計算法)*標(biāo)準(zhǔn)形的標(biāo)準(zhǔn)形的特征特征：極小化極小化、等式約束等式約束、變量非負變量非負其中其中 給定，變量是給定，變量是向量表示：向量表示：其中其中 給定，變量給定，變量是是第第 2 章章

7、線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例4. 4. 化成標(biāo)準(zhǔn)形化成標(biāo)準(zhǔn)形等價表示為等價表示為第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)一般形式一般形式 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形轉(zhuǎn)化轉(zhuǎn)化稱稱 松弛松弛(slack)/盈余盈余(surplus)變量變量第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)定義定義 設(shè)設(shè) B 是是 A 的的m個線性無關(guān)列組成的矩陣，個線性無關(guān)列組成的矩陣， 置其余置其余列所對應(yīng)的變量為零

8、，稱所得方程組的解是列所對應(yīng)的變量為零，稱所得方程組的解是 Ax = b 的的基基本解本解(basic solution) ;非負基本解是非負基本解是標(biāo)準(zhǔn)形問題標(biāo)準(zhǔn)形問題的的基本可基本可行解行解( (basic feasible solution)；稱稱 B 是是基基(basis)；稱與稱與 B 的列對應(yīng)的變量為的列對應(yīng)的變量為基變量基變量(basic variables)2.1.3 基本可行解基本可行解(*)其中其中滿秩假定：滿秩假定：m n，且，且 A 的行向量線性無關(guān)的行向量線性無關(guān)例第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)

9、學(xué)規(guī)劃基礎(chǔ)u基本可行解的個數(shù)基本可行解的個數(shù)不超過不超過 退化退化基本可行解：某個或某些基變量取零的基本可行解！基本可行解：某個或某些基變量取零的基本可行解！問題：問題：基本可行解與基的對應(yīng)關(guān)系？基本可行解與基的對應(yīng)關(guān)系？(見習(xí)題見習(xí)題2.5)事實事實：設(shè)：設(shè) x 是線性規(guī)劃的可行解，則是線性規(guī)劃的可行解，則x 是線性規(guī)劃的基是線性規(guī)劃的基本可行解本可行解當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)它的正分量對應(yīng)的列線性無關(guān)它的正分量對應(yīng)的列線性無關(guān).例例. . 基本可行解及幾何意義基本可行解及幾何意義第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)基本可

10、行解的存在性與基本定理基本可行解的存在性與基本定理(*)定理定理(線性規(guī)劃基本定理線性規(guī)劃基本定理) 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中中 A 是秩為是秩為 m 的的mn 矩陣矩陣. 若問題有解，則若問題有解，則必有必有某某個基本可行解是最優(yōu)解個基本可行解是最優(yōu)解.定理定理 (BFS的存在性的存在性) 考慮考慮LP 標(biāo)準(zhǔn)形，其中標(biāo)準(zhǔn)形，其中A 是秩為是秩為 m 的的mn 矩陣矩陣. 若問題有可行解，則若問題有可行解，則必存在必存在基本可行解基本可行解.第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)“You dont

11、 understand anything until you learn it more than one way.” Marvin Minsky (人工智能領(lǐng)域的專家人工智能領(lǐng)域的專家)2.1.5 幾何直觀幾何直觀線性規(guī)劃的基本定理線性規(guī)劃的基本定理( (標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) )基本可行解基本可行解線性方程組線性方程組的基本性質(zhì)的基本性質(zhì)代數(shù)理論代數(shù)理論(與與表述形式有關(guān)表述形式有關(guān))設(shè)計算法設(shè)計算法極點極點凸 集 理 論凸 集 理 論幾何理論幾何理論( (與表述形式與表述形式無關(guān)無關(guān)) )直觀理解直觀理解第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)

12、學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)凸集的定義及性質(zhì)凸集的定義及性質(zhì)幾何解釋：連接集合中任兩點的線段仍含在該集合中幾何解釋：連接集合中任兩點的線段仍含在該集合中性質(zhì)性質(zhì)稱集合稱集合 C 是錐是錐(cone)，如果，如果 蘊含著對所有蘊含著對所有 有有 . 若錐若錐 C 還是凸的，稱為凸錐還是凸的，稱為凸錐(convex cone).稱稱 中的集合中的集合 C 是凸的是凸的(convex)，如果任給，如果任給 個個 x, y 及每個及每個 ，點，點 . 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)一些重要的凸集一些重要的凸集有限個閉半空間的

13、交集有限個閉半空間的交集多面集多面集(polyhedral set):推推廣廣平面上：多邊形平面上：多邊形注：任一線性規(guī)劃的可行集是注：任一線性規(guī)劃的可行集是多面集多面集！超平面超平面(hyperplane):(hyperplane):正正/ /負閉半空間：負閉半空間：給定第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)極點極點幾何上：極點即不能位于連接該集合中其它兩點的開線段幾何上：極點即不能位于連接該集合中其它兩點的開線段上的點上的點定義定義 稱凸集稱凸集 C 中的點中的點 x 是是 C 的極點，如果存在的極點，如果存在 C

14、 中的點中的點 y, z 和某和某 ，有，有則必有則必有 y = z.(1)xyz ( 0 , 1 ) 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)定理定理( (極點與基本可行解的等價性極點與基本可行解的等價性) )推論：推論：(i) 若若 C 非空，則至少有一個極點非空，則至少有一個極點.(ii) 若線性規(guī)劃有解，則必有一個極點是最優(yōu)解若線性規(guī)劃有解，則必有一個極點是最優(yōu)解.(iii) C 的極點集是有限集的極點集是有限集. 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中 A 是秩為是秩為 m 的的 mn矩陣，令矩陣，令

15、 , 則則 x 是是 C 的極點當(dāng)且僅當(dāng)?shù)臉O點當(dāng)且僅當(dāng) x 是系統(tǒng)是系統(tǒng) ， 的基本可行解的基本可行解(非負基本解非負基本解).(iv) C 中的點中的點 x 是極點是極點當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)它的正分量對應(yīng)的列線性無它的正分量對應(yīng)的列線性無關(guān)關(guān).:,R 0nCxA xbx第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)C有有2個極點個極點有有3個基本解，個基本解，2個個可行可行C 有有3個極點個極點有有3個基本解，個基本解，均可行均可行例例2.2. C例例1. 1. C第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法

16、LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例3. 3. subject to5個極點個極點x*=(3/2, 1/2)T 極點極點問題問題/ /作業(yè)作業(yè)( (習(xí)題習(xí)題2.62.6) )證明這兩個集合的極點是證明這兩個集合的極點是一一對應(yīng)一一對應(yīng)的！的！考慮集合考慮集合第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃問題解的幾種情況線性規(guī)劃問題解的幾種情況第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.2 單純形法單純形法 適用形式：適用形式：標(biāo)

17、準(zhǔn)形標(biāo)準(zhǔn)形(基本可行解等價于極點基本可行解等價于極點) 理論基礎(chǔ)：理論基礎(chǔ)：線性規(guī)劃的線性規(guī)劃的基本定理基本定理！ 基本思想：基本思想：從約束集的從約束集的某個極點某個極點/BFS開始，依次開始，依次移動到移動到相鄰極點相鄰極點/BFS，直到找出最優(yōu)解，或判斷，直到找出最優(yōu)解，或判斷問題無界問題無界. 初始化：初始化：如何找到一個如何找到一個BFS？ 判斷準(zhǔn)則：判斷準(zhǔn)則：何時最優(yōu)？何時無界？何時最優(yōu)？何時無界？ 迭代規(guī)則：迭代規(guī)則：如何從一個極點如何從一個極點/BFS迭代到相鄰極點迭代到相鄰極點/BFS？第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA

18、數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)基本解基本解基變量基變量非基變量非基變量即可，次序可以打亂！即可，次序可以打亂！只要有只要有 m 個單位列個單位列 e1 , e2 , , em2.1.1 既約既約/相對費用系數(shù)規(guī)范形相對費用系數(shù)規(guī)范形不妨設(shè)得到了基變量為 的BFS，對應(yīng)基為B ，則有1mx ,x不妨設(shè) ，則有 1mBa ,a第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)即可，次序可以打亂！即可，次序可以打亂！只要有只要有 m 個單位列個單位列 e1 , e2 , , em 規(guī)范形的系數(shù)的一種解釋規(guī)范形第 j 列的系數(shù)是用當(dāng)前基表示 a

19、j 時的系數(shù)！不妨設(shè) ，則有 1mBa ,a11122jjjjjmjmyB aay ay ay a第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)將將 Ax = b 的任一解的任一解 x 用非基變量用非基變量表示為表示為既約費用系數(shù)既約費用系數(shù)/相對費用系數(shù)相對費用系數(shù)(*)相對費用系數(shù)的經(jīng)濟解釋！(合成費用、相對費用)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)定理定理(最優(yōu)性判別最優(yōu)性判別)在某基本可行解處，如果對所有在某基本可行解處，如果對所有 j 有有

20、 ,0jjjcrz則這個基本可行解是最優(yōu)的則這個基本可行解是最優(yōu)的.既約線性規(guī)劃既約線性規(guī)劃 假設(shè)假設(shè)令令第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.2.2 基本可行解的改進基本可行解的改進定理定理( BFS的提高的提高) 給定目標(biāo)值為給定目標(biāo)值為 z0 的的非退化非退化基本可行解，且假定存基本可行解，且假定存在在 q 使得使得 rq 0，無無可行解！可行解！ z = 0，有有可行解，且可行解，且 x 是潛在的基本可行解！是潛在的基本可行解！ 基變量中基變量中無無人工變量人工變量 x 是是BFS，B 是對應(yīng)的基是對應(yīng)的基

21、 基變量中基變量中有有人工變量人工變量驅(qū)趕人工變量出基驅(qū)趕人工變量出基假設(shè)第假設(shè)第 i 個基變量是人工變量，且當(dāng)前單純形表個基變量是人工變量，且當(dāng)前單純形表第第 i 行的前行的前 n 個數(shù)據(jù)是個數(shù)據(jù)是第第 i 個約束冗余；個約束冗余；刪除單純形表的第刪除單純形表的第 i 行數(shù)據(jù)行數(shù)據(jù)以以任一非零元任一非零元為轉(zhuǎn)軸元轉(zhuǎn)軸為轉(zhuǎn)軸元轉(zhuǎn)軸得輔助問題的一個新的最優(yōu)得輔助問題的一個新的最優(yōu)BFS，且基變量中少，且基變量中少1個人工變量！個人工變量！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例1. 給出下面系統(tǒng)的一個基本可行解，或者說

22、明其無解給出下面系統(tǒng)的一個基本可行解，或者說明其無解引入引入人工人工變量變量目標(biāo)目標(biāo)：輔助問題的輔助問題的初始表格初始表格！BFSx = (0, 0, 0, 4, 3)T第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)第一張第一張單純形表單純形表第二張第二張單純形表單純形表第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)輔助問題的輔助問題的最優(yōu)值是最優(yōu)值是0 0. . 原問題的原問題的BFS：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-

23、SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例2. 利用兩階段法求解下面的問題利用兩階段法求解下面的問題輔助問題輔助問題第第 I 階段：階段：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)輔助問題的輔助問題的最后一張單純形表最后一張單純形表原問題的原問題的初始初始表格：表格：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)原問題的原問題的最優(yōu)解最優(yōu)解：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基

24、礎(chǔ)兩階段法兩階段法可求解任意的可求解任意的線性規(guī)劃問題線性規(guī)劃問題 第第 I 階段：啟動單純形法階段：啟動單純形法 構(gòu)造、求解輔助問題構(gòu)造、求解輔助問題 判斷原問題判斷原問題不可行、或可行不可行、或可行 可行時找到基本可行解及對應(yīng)規(guī)范形可行時找到基本可行解及對應(yīng)規(guī)范形 第第 II 階段：利用單純形法求原問題階段：利用單純形法求原問題 從上述從上述BFS出發(fā)，求解所給問題出發(fā)，求解所給問題 原問題原問題無界無界或者或者有解有解第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)兩階段法的例子兩階段法的例子p.27第第 2 章章 線性規(guī)

25、劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.2.6 修正單純形法修正單純形法給定基給定基 B 及對應(yīng)及對應(yīng)BFS，即，即 B-1b用用非基非基變量表示變量表示基基變量：變量：用用非基非基變量表示變量表示目標(biāo)函數(shù)目標(biāo)函數(shù)：既約既約/ /相對相對費用向量費用向量(單純形法的一種實現(xiàn)方式，*)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)與基矩陣與基矩陣 B 對應(yīng)的單純形表對應(yīng)的單純形表 每次迭代需要的數(shù)據(jù)每次迭代需要的數(shù)據(jù)核心核心計算：計算：B-1單純形表的最后一行、某列和最后一

26、列單純形表的最后一行、某列和最后一列 僅需原始數(shù)據(jù)僅需原始數(shù)據(jù)(c, A, b)和基和基 B 的逆矩陣的逆矩陣 重要事實：重要事實： 單純形法的迭代次數(shù)典型地為單純形法的迭代次數(shù)典型地為 2m-3m第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)修正單純形法的計算步驟修正單純形法的計算步驟步步2 選取選取 q 滿足滿足步步0 給定給定BFS及對應(yīng)的及對應(yīng)的B-1.計算計算 , 步步4 更新更新 B-1, B-1b 和和 ，返步，返步1.步步1 計算計算 .如果如果 停；得最優(yōu)解停；得最優(yōu)解.問題問題無界無界；否則，選；否則，選

27、p 滿足滿足步步3 計算計算 yq=B-1 aq；若；若 ， 核心問題：核心問題：理論上的表現(xiàn)理論上的表現(xiàn)當(dāng)前基的逆當(dāng)前基的逆 新基的逆新基的逆如何更新如何更新如何用初等行變換實現(xiàn)如何用初等行變換實現(xiàn)單純形乘子單純形乘子第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)定理 設(shè) ，則 aq 進基 ap 出基后所得新基 滿足利用利用初等行變換初等行變換可以實現(xiàn)上述基的逆和單純形乘子的轉(zhuǎn)換！可以實現(xiàn)上述基的逆和單純形乘子的轉(zhuǎn)換！(2) 轉(zhuǎn)軸后的單純形乘子 ，其中 up 表示 B-1 的第 p 行.這里 ei 表示第 i 個 m 維單位

28、向量，向量 v 定義為(1) ，其中基的逆和單純形乘子的轉(zhuǎn)換基的逆和單純形乘子的轉(zhuǎn)換(*)對偶單純形中要用到這個事實！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)相關(guān)數(shù)據(jù)的更新相關(guān)數(shù)據(jù)的更新初等行變換初等行變換設(shè)設(shè)轉(zhuǎn)軸元轉(zhuǎn)軸元是是 ，即，即 ap 出基，出基， aq 進基進基以為轉(zhuǎn)軸元，以為轉(zhuǎn)軸元，轉(zhuǎn)軸后轉(zhuǎn)軸后即得新基對應(yīng)的數(shù)據(jù)！即得新基對應(yīng)的數(shù)據(jù)！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例1 求解例求解例2.2.2q = 1a1進基進基，計算，計算

29、 y1.得得第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)轉(zhuǎn)軸：轉(zhuǎn)軸：計算計算 , q = 3計算計算第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)計算計算最優(yōu)值：最優(yōu)值：最優(yōu)解：最優(yōu)解：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)l 對偶理論和最小費用流問題中都要用到“單純形乘子”！l 重要事實：若標(biāo)準(zhǔn)形的系數(shù)矩陣A中有一個單位矩陣，則每張單純形表對應(yīng)位置為當(dāng)前基的逆！提示第第 2 章章

30、線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)問題問題. . 設(shè)用單純形法求解標(biāo)準(zhǔn)形式的設(shè)用單純形法求解標(biāo)準(zhǔn)形式的LPLP時得到如下時得到如下 單純形表單純形表. .還假設(shè)矩陣還假設(shè)矩陣A的的后三列形成單位矩陣后三列形成單位矩陣1.1.給出由該表描述的當(dāng)前基是最優(yōu)的充分必要條件給出由該表描述的當(dāng)前基是最優(yōu)的充分必要條件( (依照表中的系數(shù)依照表中的系數(shù)).).2.2.假設(shè)該基是最優(yōu)的且假設(shè)該基是最優(yōu)的且 . .找出另外一個最找出另外一個最優(yōu)基本可行解，其與該表所描述的不同優(yōu)基本可行解，其與該表所描述的不同. .(習(xí)題習(xí)題2.12(b) )第第

31、 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)假定與假定與當(dāng)前表所聯(lián)系的基是最優(yōu)當(dāng)前表所聯(lián)系的基是最優(yōu)的的1.1.假設(shè)將原問題中的假設(shè)將原問題中的 ，給出使基保，給出使基保持最優(yōu)的持最優(yōu)的 的范圍的范圍. . (習(xí)題習(xí)題2.11(a)2.2.假設(shè)將原問題中的假設(shè)將原問題中的 ，給出使基保，給出使基保持最優(yōu)的持最優(yōu)的 的范圍的范圍. . (習(xí)題習(xí)題2.11(b)問題問題 設(shè)用單純形法求解標(biāo)準(zhǔn)形式的設(shè)用單純形法求解標(biāo)準(zhǔn)形式的LPLP時得到如下單純時得到如下單純 形表形表. .還假設(shè)矩陣還假設(shè)矩陣 A 的的后三列形成單位矩陣后三列形成單

32、位矩陣第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.2.7 單純形法的效率單純形法的效率有效性問題有效性問題: : 給定一個問題，求解它需要多長時間給定一個問題，求解它需要多長時間( (時時間復(fù)雜度間復(fù)雜度) )？求解它需要多少存儲空間？求解它需要多少存儲空間( (空間復(fù)雜度空間復(fù)雜度) )？ 平均情況平均情況(average case): 典型問題需要多少時間典型問題需要多少時間 從數(shù)學(xué)上研究很困難從數(shù)學(xué)上研究很困難 經(jīng)驗研究經(jīng)驗研究兩種解答兩種解答最壞情況最壞情況(worst case): 最難的問題需要多少時間最難的

33、問題需要多少時間 數(shù)學(xué)上是可處理的數(shù)學(xué)上是可處理的 有限值有限值 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)度量度量(measures)大小的度量大小的度量(measures of size)問題的度量問題的度量 約束的個數(shù)約束的個數(shù) m 和和/或者變量的個數(shù)或者變量的個數(shù) n 數(shù)據(jù)個數(shù)數(shù)據(jù)個數(shù)mn 非零數(shù)據(jù)的個數(shù)非零數(shù)據(jù)的個數(shù) 尺寸，比如以尺寸，比如以bytes為單位為單位度量時間度量時間(measuring time) 算法的度量算法的度量 迭代次數(shù)迭代次數(shù) 每次迭代的算術(shù)運算次數(shù)每次迭代的算術(shù)運算次數(shù) 每次算術(shù)運算的

34、時間每次算術(shù)運算的時間(依賴于硬件依賴于硬件)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)Klee-Minty問題問題(1972)n = 3 時：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)扭曲的立方體扭曲的立方體(A distorted Cube)約束集是如下立方體的約束集是如下立方體的稍微稍微(minor)扭曲：扭曲：n=3時：時：9608第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)

35、指數(shù)指數(shù) (Exponential)Klee-Minty的問題說明：的問題說明： 當(dāng)求解具有當(dāng)求解具有 n 個變量和約束的問題時，個變量和約束的問題時，最小系數(shù)最小系數(shù)規(guī)則規(guī)則有可能需要有可能需要 2n-1 次轉(zhuǎn)軸次轉(zhuǎn)軸(因此因此遍歷遍歷了扭曲立方體的了扭曲立方體的 2n 個頂個頂點點)當(dāng)當(dāng) n = 70 時，時，假設(shè)假設(shè) 1 秒鐘迭代秒鐘迭代 1000 次，求解這個問題需要次，求解這個問題需要 400 億年；億年；宇宙的估計年齡是宇宙的估計年齡是 137 億年億年.然而每天求解的問題中，變量在然而每天求解的問題中，變量在10,000到到100,000之間的很普遍之間的很普遍.Worst ca

36、se analysis is just that: worst case.第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)復(fù)雜度復(fù)雜度(Complexity)排序：排序：O(nlogn)矩陣乘以向量：矩陣乘以向量：O(n2)矩陣乘以矩陣：矩陣乘以矩陣：O(n3)解線性方程組：解線性方程組：O(n3)單純形法：單純形法： 最壞情況：最壞情況：O(n22n) 平均情況：平均情況：O(n3) 問題：問題： 是否存在求解線性規(guī)劃的方法，是否存在求解線性規(guī)劃的方法，它的最壞性能分析是多項式的它的最壞性能分析是多項式的?第第 2 章章 線性

37、規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃的歷史線性規(guī)劃的歷史 淵源要追溯到淵源要追溯到Euler、Leibniz、Lagrange等等 G. Dantzig, Von Neumann(Princeton) 和和 L. Kantorovich在在1940s創(chuàng)建了線性規(guī)劃創(chuàng)建了線性規(guī)劃 1947年年, G. Dantzig于于發(fā)明了發(fā)明了單純形法單純形法 1979年年，L. Khachain找到了求解線性規(guī)劃的一種有效方法找到了求解線性規(guī)劃的一種有效方法(第一個多項式時間算法第一個多項式時間算法橢球法橢球法) 1984年年，N. Kar

38、markan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強有力的競爭者方法，已證明是單純形法的強有力的競爭者(投影內(nèi)點法投影內(nèi)點法) 現(xiàn)在求解大規(guī)模和退化問題最有效的是現(xiàn)在求解大規(guī)模和退化問題最有效的是原始對偶路徑跟原始對偶路徑跟蹤內(nèi)點法蹤內(nèi)點法(9.5節(jié)節(jié))第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)紐約時報紐約時報時代周刊時代周刊第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)華爾街日報華爾街日報商業(yè)周刊商業(yè)周刊第第

39、 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)紐約時報紐約時報華爾街日報華爾街日報第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)1 24225345123123:,0,1 xxx 142512x232423x134514x作業(yè)2.30第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)l對偶問題對偶問題l對偶定理對偶定理l與單純形法的關(guān)系與單純形法的關(guān)系l互補定理互補定理l對偶單純形法對偶單純形法2.3

40、 對偶對偶第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ) 原始問題原始問題(primal)：給定數(shù)據(jù)給定數(shù)據(jù)2.3.1 對偶問題對偶問題原始變量原始變量 對偶問題對偶問題(dual)：對偶變量對偶變量第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶問題：對稱形式的對偶對對偶問題：對稱形式的對偶對注注1 對于線性規(guī)劃，對偶是相互的，即對于線性規(guī)劃，對偶是相互的，即對偶問題的對偶對偶問題的對偶 是原始問題是原始問題 原始問題原始問題(primal)：給定數(shù)據(jù)給定

41、數(shù)據(jù)注注2 2 為了確定任一線性規(guī)劃問題的對偶，可以利用為了確定任一線性規(guī)劃問題的對偶，可以利用 對稱形式的對偶對或者標(biāo)準(zhǔn)形的對偶對！對稱形式的對偶對或者標(biāo)準(zhǔn)形的對偶對！原始變量原始變量 對偶問題對偶問題(dual)：對偶變量對偶變量第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ) 配餐問題配餐問題：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？：確定食品數(shù)量，滿足營養(yǎng)需求，花費最??？n種食品，種食品，m種營養(yǎng)成份；第種營養(yǎng)成份；第 j 種食品的單價種食品的單價每單位第每單位第 j 種食品含第種食品含第 i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量 變

42、量變量： 食用第食用第 j 種食品的數(shù)量種食品的數(shù)量為了健康，每天最少要食用第為了健康，每天最少要食用第 i 種營養(yǎng)的數(shù)量種營養(yǎng)的數(shù)量 模型：模型：對偶問題：經(jīng)濟解釋對偶問題：經(jīng)濟解釋對偶問題保健品公司藥劑師、營養(yǎng)丸、對偶問題保健品公司藥劑師、營養(yǎng)丸、定價問題定價問題第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶問題：一般問題的對偶對偶問題：一般問題的對偶給定數(shù)據(jù)給定數(shù)據(jù) A, b, c；記；記 A 的第的第 i 行為行為 ai，A 的第的第 j 列為列為 aj 原始問題原始問題(primal)： 對偶問題對偶問題(dua

43、l)：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶問題：例子對偶問題：例子第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.3.2 對偶定理對偶定理弱對偶定理弱對偶定理. . 設(shè)設(shè) 和和 分別是原始問題和對偶問題的可行分別是原始問題和對偶問題的可行解，則解，則 . . 推論推論2. 如果原始問題與對偶問題之一無界，則另一個問題如果原始問題與對偶問題之一無界，則另一個問題 沒有可行解沒有可行解.推論推論1. 設(shè)設(shè) 和和 分別是原始問題和對偶問題的可行解分別

44、是原始問題和對偶問題的可行解,若若 則則 和和 分別是原始問題和對偶問題最優(yōu)解分別是原始問題和對偶問題最優(yōu)解. .考慮對偶問題的初衷！考慮對偶問題的初衷！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶定理：強對偶定理對偶定理：強對偶定理對于一般形式的線性規(guī)劃利用對于一般形式的線性規(guī)劃利用凸集分離凸集分離定理定理證明！證明！強對偶定理強對偶定理. . 如果原始問題和對偶問題之一有解，則另如果原始問題和對偶問題之一有解，則另一個問題也有解，且最優(yōu)值相等一個問題也有解，且最優(yōu)值相等. .有解有解無無(下下)界界不可行不可行有解有

45、解無無(上上)界界不可行不可行 對偶問題對偶問題原始問題原始問題思考題：寫出兩階段法中第一階段的輔助問題的對偶問題？這個對偶問題有最優(yōu)解嗎？為什么？第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.3.3 與單純形法的關(guān)系與單純形法的關(guān)系如何由原始問題的解得到對偶問題的解？定理2.3.3. 設(shè)標(biāo)準(zhǔn)形線性規(guī)劃問題有最優(yōu)解，B是最優(yōu)基本可行解對應(yīng)的基，則是其對偶問題的最優(yōu)解.特例：當(dāng)系數(shù)矩陣A中有單位矩陣時，如何從單純形表讀出當(dāng)前基的逆矩陣？(見p.38，定理2.33下面)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論

46、與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)考慮問題引入松弛變量標(biāo)準(zhǔn)形利用單純形法求解與單純形法的關(guān)系與單純形法的關(guān)系：例子：例子對偶問題第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)與單純形法的關(guān)系：例子與單純形法的關(guān)系：例子( (續(xù)續(xù)) )原原問題問題最優(yōu)解最優(yōu)解對偶對偶問題問題最優(yōu)解最優(yōu)解第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.3.4 靈敏度靈敏度與與互補性互補性 與基與基 B 對應(yīng)的單純形乘子對應(yīng)的單純形乘子(simplex mu

47、ltiplier) 經(jīng)濟解釋經(jīng)濟解釋 記記 A 的列向量為的列向量為 aj，對應(yīng)費用為，對應(yīng)費用為 cj，j =1 , , n解釋為單位向量解釋為單位向量 ei 的的合成價格合成價格！解釋為解釋為 aj 的的相對相對/既約既約費用系數(shù)費用系數(shù) 最優(yōu)性：最優(yōu)性：對所有的對所有的 j 有有 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)靈敏度靈敏度(sensitivity)與與影子價格影子價格(shadow price)問題：當(dāng)向量問題：當(dāng)向量 b 發(fā)生微小變化時，問題的最優(yōu)值如何變化？發(fā)生微小變化時，問題的最優(yōu)值如何變化？假設(shè)該

48、問題的最優(yōu)基是假設(shè)該問題的最優(yōu)基是 B且且 B-1b 0 (非退化！非退化！)令令第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)因為 所以稱稱 為分量為分量 所對應(yīng)資源的所對應(yīng)資源的邊際邊際價格價格(marginal price) 或者或者影子影子價格價格(shadow price)從而z*z*第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)互補定理互補定理(線性規(guī)劃的最優(yōu)性條件線性規(guī)劃的最優(yōu)性條件)用用 aj 表示表示 A 的第的第 j 列，列，ai 表示表示

49、 A 的第的第 i 行行 定理定理. . 設(shè)設(shè) 和和 分別是分別是非對非對稱稱形式原始問題和對偶問題形式原始問題和對偶問題的的可行解可行解. 則它們是各自最則它們是各自最優(yōu)解的優(yōu)解的充要充要條件是：對所有條件是：對所有 i 有有定理定理. 設(shè)設(shè) 和和 分別是分別是對稱對稱形式原始問題和對偶問題的形式原始問題和對偶問題的可行解可行解. 則它們是各自最優(yōu)則它們是各自最優(yōu)解的解的充要充要條件是：對所有的條件是：對所有的 i 和和 j 有有l(wèi) 課本上定理3.2.1(p.63)的證明要用到互補定理！l 最優(yōu)性原始可行性對偶可行性互補性第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY

50、-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)互補定理互補定理(線性規(guī)劃的最優(yōu)性條件線性規(guī)劃的最優(yōu)性條件)的應(yīng)用的應(yīng)用例例 2.3.5第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)單純形法單純形法對偶單純形法對偶單純形法原始可行對偶可行互補性原始可行對偶可行互補性初始迭代中最優(yōu)終止時2.3.5 對偶單純形法對偶單純形法 適用問題：標(biāo)準(zhǔn)形問題有一個適用問題：標(biāo)準(zhǔn)形問題有一個不可行不可行的基本解，的基本解，但但 對應(yīng)單純形乘子是對偶問題的可行解對應(yīng)單純形乘子是對偶問題的可行解 單純形表中的表現(xiàn)：單純形表中的表現(xiàn)： 第一張單純形表中的

51、既約費用系數(shù)非負，但有基變量取第一張單純形表中的既約費用系數(shù)非負，但有基變量取負值負值！ 迭代時保持既約費用系數(shù)非負，直到迭代時保持既約費用系數(shù)非負，直到全部全部基變量取非負值?；兞咳》秦撝?。階段 性質(zhì) 方法第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)則稱則稱 x 是標(biāo)準(zhǔn)形問題的是標(biāo)準(zhǔn)形問題的對偶可行對偶可行基本解基本解.定義定義 假設(shè)是假設(shè)是 Ax = b 的基本解的基本解. 如果如果基本解基本解(互補性互補性)可行對偶可行最優(yōu)解可行對偶可行最優(yōu)解初始對偶可行基本解初始對偶可行基本解新的對偶可行基本解新的對偶可行基本解“

52、原始可行對偶可行原始可行對偶可行”的基本解！的基本解！迭代迭代對偶單純形法：對偶可行基本解對偶單純形法：對偶可行基本解 是是對偶問題的可行解對偶問題的可行解，即，即 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)設(shè)對偶可行基本解設(shè)對偶可行基本解 x 對應(yīng)的基對應(yīng)的基 對偶單純形法：推導(dǎo)對偶單純形法：推導(dǎo)I I不妨設(shè)不妨設(shè) yp0 0； 此外還假設(shè)此外還假設(shè) 非退化非退化，即，即令令 ，其中，其中 是是 的第的第 p 行，則行，則目的：目的：找新的找新的 使前使前 m 個等式中的某個與后個等式中的某個與后n-m個不等式個不等式中

53、的某個角色互換，同時使中的某個角色互換，同時使對偶對偶目標(biāo)函數(shù)的值目標(biāo)函數(shù)的值增大增大！修正單純形法對偶問題的非退化極點是Rm中恰好m個超平面的交點！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶單純形法：推導(dǎo)對偶單純形法：推導(dǎo)IIII出基變量：取出基變量：取負值負值的基變量的基變量( (* * * * * *) )進基變量：其進基變量：其 p 行的負元素，且取到行的負元素，且取到最小正比值最小正比值 ( (* * * * * *) )第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUA

54、A數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)步步0 給定對偶可行基本解對應(yīng)的單純形表給定對偶可行基本解對應(yīng)的單純形表.步步1 若對若對每個每個 i 都有都有 ，停；當(dāng)前，停；當(dāng)前DFBS是最優(yōu)的是最優(yōu)的.步步2 選取選取 p 滿足滿足 yp0 0 ，這時，第，這時，第 p 個基變量出基個基變量出基.步步4 以以 ypq 為轉(zhuǎn)軸元進行為轉(zhuǎn)軸元進行轉(zhuǎn)軸轉(zhuǎn)軸，更新單純形表，返步，更新單純形表，返步1.對偶單純形法：計算步驟對偶單純形法：計算步驟步步3 若若 ，問題，問題無可行解無可行解；否則，；否則， 選選 q 滿足滿足第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃

55、基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶單純形法：例子對偶單純形法：例子1) 寫出對偶問題并用圖解法求解。2) 用對偶單純形法求解所給問題。解. 對偶問題為第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)引入盈余變量；并給等式兩邊同乘引入盈余變量；并給等式兩邊同乘 -1；得初始表格；得初始表格/第一張第一張單純形表單純形表對偶單純形法：例子對偶單純形法：例子( (續(xù)續(xù)) )第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶單純形法：例子對偶單純形法：例子( (續(xù)續(xù)) )最優(yōu)解：最優(yōu)

56、解：單純形乘子的迭代為若第一步讓x4出基，單純形乘子的迭代為第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對偶單純形法：收斂性對偶單純形法：收斂性定理定理. . 如果標(biāo)準(zhǔn)形線性規(guī)劃問題的任一對偶可行基本如果標(biāo)準(zhǔn)形線性規(guī)劃問題的任一對偶可行基本解所對應(yīng)的非基變量的相對費用系數(shù)解所對應(yīng)的非基變量的相對費用系數(shù)大于零大于零，則對偶，則對偶單純形法在單純形法在有限步有限步內(nèi)終止內(nèi)終止. . 如果線性規(guī)劃問題可以用對偶單純形法求解，則必有界！如果線性規(guī)劃問題可以用對偶單純形法求解，則必有界！ 其計算結(jié)果只能是其計算結(jié)果只能是不可行不可行

57、或者或者有解有解！ 如果線性規(guī)劃問題可以用單純形法求解，則其如果線性規(guī)劃問題可以用單純形法求解，則其無界無界或或有解有解 兩階段法可以求解任一線性規(guī)劃問題；兩階段法可以求解任一線性規(guī)劃問題； 第第I階段的結(jié)果為階段的結(jié)果為可行可行或者或者不可行不可行兩種；兩種； 對于可行的，在第對于可行的，在第II階段可得問題階段可得問題無界無界或或有解有解！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ) 典型典型情況情況( (有顯然的對偶可行基本解有顯然的對偶可行基本解) ) 一般一般情況情況 已有一個標(biāo)準(zhǔn)形問題的最優(yōu)解和最優(yōu)基已有一個標(biāo)準(zhǔn)形