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ǔ) 問(wèn)題問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最小？

2、：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最小？ 變量：變量：n 種食品，種食品，m 種營(yíng)養(yǎng)成份；第種營(yíng)養(yǎng)成份；第 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ù)量 模型：模型：2.1.1 問(wèn)題舉例問(wèn)題舉例例例1. 1. 配餐問(wèn)題配餐問(wèn)題第第 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èn)題網(wǎng)絡(luò)流問(wèn)題(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ù)中含絕對(duì)值的問(wèn)題目標(biāo)函數(shù)中含絕對(duì)值的問(wèn)題例例3. 逐段線性凸函數(shù)逐段線性凸函數(shù)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃線性規(guī)劃解的解的幾何特征幾何特征惟一惟一 解解(頂點(diǎn)頂點(diǎn))！第第 2 章章 線性規(guī)劃線性規(guī)劃:

4、基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)無(wú)無(wú)(下下)界界沒有沒有 有限有限 解解(-1, -1)一條邊一條邊( 1, 0)一條邊一條邊( 0, 1)惟一的頂點(diǎn)惟一的頂點(diǎn)( 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ǔ) 無(wú)界無(wú)界：沒有有限最優(yōu)解：沒有有限最優(yōu)解(極小化時(shí)表示無(wú)下界，極大化時(shí)無(wú)上界) 不可行不可行：沒有可行解：沒有可行解無(wú)解無(wú)解 有解有解：惟一解或多個(gè)解惟一解或

5、多個(gè)解( (整條邊、面、甚至整個(gè)可行集整條邊、面、甚至整個(gè)可行集) ) 有頂點(diǎn)解有頂點(diǎn)解線性規(guī)劃解的線性規(guī)劃解的幾何特征幾何特征可行集：可行集：多邊形多邊形( (二維二維) )多面集多面集( (高維空間高維空間) )給出給出有效的代數(shù)刻畫有效的代數(shù)刻畫和和嚴(yán)謹(jǐn)?shù)膸缀蚊枋鰢?yán)謹(jǐn)?shù)膸缀蚊枋?，從理論上證，從理論上證實(shí)上述幾何特征，并實(shí)上述幾何特征，并尋求有效算法尋求有效算法第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃的一般形式線性規(guī)劃的一般形式其中其中 c 是是 n 維向量，維向量， 是是 m 維行向量，維行向量， 是實(shí)數(shù)，

6、這些是實(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è)計(jì)算法便于分析分析和設(shè)計(jì)算法)*標(biāo)準(zhǔn)形的標(biāo)準(zhǔn)形的特征特征：極小化極小化、等式約束等式約束、變量非負(fù)變量非負(fù)其中其中 給定，變量是給定，變量是向量表示：向量表示：其中其中 給定，變量給定，變量是是第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例4. 4. 化成標(biāo)準(zhǔn)形化成標(biāo)準(zhǔn)形等價(jià)表示為等價(jià)表示為第第 2 章章

7、 線性規(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個(gè)線性無(wú)關(guān)列組成的矩陣，個(gè)線性無(wú)關(guān)列組成的矩陣， 置其余置其余列所對(duì)應(yīng)的變量為零，稱所得方程組的解是列所對(duì)應(yīng)的變量為零，稱所得方程組的解是 Ax = b 的的基基本解本解(basic solution) ;非負(fù)基本解是非負(fù)基本解是標(biāo)準(zhǔn)形問(wèn)題標(biāo)準(zhǔn)形問(wèn)

8、題的的基本可基本可行解行解( (basic feasible solution)；稱稱 B 是是基基(basis)；稱與稱與 B 對(duì)應(yīng)的變量為對(duì)應(yīng)的變量為基變量基變量(basic variables)2.1.3 基本可行解基本可行解(*)其中其中滿秩假定：滿秩假定：m n，且，且 A 的行向量線性無(wú)關(guān)的行向量線性無(wú)關(guān)例第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)基本可行解的個(gè)數(shù)基本可行解的個(gè)數(shù)不超過(guò)不超過(guò) 退化退化基本可行解：某個(gè)或某些基變量取零的基本可行解！基本可行解：某個(gè)或某些基變量取零的基本可行解！問(wèn)題：?jiǎn)栴}：基本可行

9、解與基的對(duì)應(yīng)關(guān)系？基本可行解與基的對(duì)應(yīng)關(guān)系？(見習(xí)題見習(xí)題2.5)事實(shí)：事實(shí)： x 是基本可行解是基本可行解當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)它的正分量對(duì)應(yīng)的列線它的正分量對(duì)應(yīng)的列線性無(wú)關(guān)性無(wú)關(guān).例例. . 基本可行解及幾何意義基本可行解及幾何意義第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)基本可行解的存在性與基本定理基本可行解的存在性與基本定理(*)定理定理(線性規(guī)劃基本定理線性規(guī)劃基本定理) 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中中 A 是秩為是秩為 m 的的mn 矩陣矩陣. 若問(wèn)題有解，則若問(wèn)題有解，則必有必有某某個(gè)基本可行解是

10、最優(yōu)解個(gè)基本可行解是最優(yōu)解.定理定理 (BFS的存在性的存在性) 考慮考慮LP 標(biāo)準(zhǔn)形，其中標(biāo)準(zhǔn)形，其中A 是秩為是秩為 m 的的mn 矩陣矩陣. 若問(wèn)題有可行解，則若問(wèn)題有可行解，則必存在必存在基本可行解基本可行解.第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)“You dont understand anything until you learn it more than one way.” Marvin Minsky (人工智能領(lǐng)域的專家人工智能領(lǐng)域的專家)2.1.5 幾何直觀幾何直觀線性規(guī)劃的基本定理線性規(guī)劃的基本定

11、理( (標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) )基本可行解基本可行解線性方程組線性方程組的基本性質(zhì)的基本性質(zhì)代數(shù)理論代數(shù)理論(與與表述形式有關(guān)表述形式有關(guān))設(shè)計(jì)算法設(shè)計(jì)算法極點(diǎn)極點(diǎn)凸 集 理 論凸 集 理 論幾何理論幾何理論( (與表述形式與表述形式無(wú)關(guān)無(wú)關(guān)) )直觀理解直觀理解第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)凸集的定義及性質(zhì)凸集的定義及性質(zhì)幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集合中幾何解釋：連接集合中任兩點(diǎn)的線段仍含在該集合中性質(zhì)性質(zhì)稱集合稱集合 C 是錐是錐(cone)，如果，如果 蘊(yùn)含著對(duì)所有蘊(yùn)含著對(duì)所有 有有 . 若錐若錐

12、 C 還是凸的，稱為凸錐還是凸的，稱為凸錐(convex cone).稱稱 中的集合中的集合 C 是凸的是凸的(convex)，如果任給，如果任給 個(gè)個(gè) x, y 及每個(gè)及每個(gè) ，點(diǎn)，點(diǎn) . 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)一些重要的凸集一些重要的凸集有限個(gè)閉半空間的交集有限個(gè)閉半空間的交集多面集多面集(polyhedral set):推推廣廣平面上：多邊形平面上：多邊形注：任一線性規(guī)劃的可行集是注：任一線性規(guī)劃的可行集是多面集多面集！超平面超平面(hyperplane):(hyperplane):正正/ /負(fù)閉

13、半空間：負(fù)閉半空間：給定第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)極點(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.(1)xyz ( 0 , 1 ) 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)定理定理( (極點(diǎn)與基本可行解的

14、等價(jià)性極點(diǎn)與基本可行解的等價(jià)性) )推論：推論：(i) 若若 C 非空，則至少有一個(gè)極點(diǎn)非空，則至少有一個(gè)極點(diǎn).(ii) 若線性規(guī)劃有解，則必有一個(gè)極點(diǎn)是最優(yōu)解若線性規(guī)劃有解，則必有一個(gè)極點(diǎn)是最優(yōu)解.(iii) C 的極點(diǎn)集是有限集的極點(diǎn)集是有限集. 考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中考慮線性規(guī)劃標(biāo)準(zhǔn)形，其中 A 是秩為是秩為 m 的的 mn矩陣，令矩陣，令 , 則則 x 是是 C 的極點(diǎn)當(dāng)且僅當(dāng)?shù)臉O點(diǎn)當(dāng)且僅當(dāng) x 是系統(tǒng)是系統(tǒng) ， 的基本可行解的基本可行解(非負(fù)基本解非負(fù)基本解).(iv) C 中的點(diǎn)中的點(diǎn) x 是極點(diǎn)是極點(diǎn)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)它的正分量對(duì)應(yīng)的列線性無(wú)它的正分量對(duì)應(yīng)的列線性無(wú)關(guān)關(guān).:,R

15、0nCxA xbx第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)C有有2個(gè)極點(diǎn)個(gè)極點(diǎn)有有3個(gè)基本解，個(gè)基本解，2個(gè)個(gè)可行可行C 有有3個(gè)極點(diǎn)個(gè)極點(diǎn)有有3個(gè)基本解，個(gè)基本解，均可行均可行例例2.2. C例例1. 1. C第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例3. 3. subject to5個(gè)極點(diǎn)個(gè)極點(diǎn)x*=(3/2, 1/2)T 極點(diǎn)極點(diǎn)問(wèn)題問(wèn)題/ /作業(yè)作業(yè)( (習(xí)題習(xí)題2.6)2.6)證明這兩個(gè)集合的極點(diǎn)是證明這兩個(gè)集合的極點(diǎn)是一一對(duì)應(yīng)一一對(duì)應(yīng)

16、的！的！考慮集合考慮集合第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)線性規(guī)劃問(wèn)題解的幾種情況線性規(guī)劃問(wèn)題解的幾種情況第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.2 單純形法單純形法 適用形式：適用形式：標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形(基本可行解等價(jià)于極點(diǎn)基本可行解等價(jià)于極點(diǎn)) 理論基礎(chǔ)：理論基礎(chǔ)：線性規(guī)劃的線性規(guī)劃的基本定理基本定理！ 基本思想：基本思想：從約束集的從約束集的某個(gè)極點(diǎn)某個(gè)極點(diǎn)/BFS開始，依次開始，依次移動(dòng)到移動(dòng)到相鄰極點(diǎn)相鄰極點(diǎn)/BFS，直到找出最優(yōu)解

17、，或判斷，直到找出最優(yōu)解，或判斷問(wèn)題無(wú)界問(wèn)題無(wú)界. 初始化：初始化：如何找到一個(gè)如何找到一個(gè)BFS？ 判斷準(zhǔn)則：判斷準(zhǔn)則：何時(shí)最優(yōu)？何時(shí)無(wú)界？何時(shí)最優(yōu)？何時(shí)無(wú)界？ 迭代規(guī)則：迭代規(guī)則：如何從一個(gè)極點(diǎn)如何從一個(gè)極點(diǎn)/BFS迭代到相鄰極點(diǎn)迭代到相鄰極點(diǎn)/BFS？第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)基本解基本解基變量基變量非基變量非基變量即可，次序可以打亂！即可，次序可以打亂！只要有只要有 m 個(gè)單位列個(gè)單位列 e1 , e2 , , em2.1.1 既約既約/相對(duì)費(fèi)用系數(shù)相對(duì)費(fèi)用系數(shù)不妨設(shè)我們已經(jīng)得到了基變量為不妨設(shè)我們

18、已經(jīng)得到了基變量為 的基本可行解的基本可行解1mx ,x 規(guī)范形系數(shù)的一種解釋 表格中第 j 列的數(shù)據(jù)用當(dāng)前基表示 aj 時(shí)的系數(shù)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)將將 Ax = b 的任一解的任一解 x 用非基變量用非基變量表示為表示為既約費(fèi)用系數(shù)既約費(fèi)用系數(shù)/相對(duì)費(fèi)用系數(shù)相對(duì)費(fèi)用系數(shù)(*)相對(duì)費(fèi)用系數(shù)的經(jīng)濟(jì)解釋！(合成費(fèi)用、相對(duì)費(fèi)用)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)定理定理(最優(yōu)性判別最優(yōu)性判別)在某基本可行解處，如果對(duì)所有在某基

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

20、BFS，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)題的一個(gè)新的最優(yōu)得輔助問(wèn)題的一個(gè)新的最優(yōu)BFS，且基變量中少，且基變量中少1個(gè)人工變量！個(gè)人工變量！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例1. 給出

21、下面系統(tǒng)的一個(gè)基本可行解，或者說(shuō)明其無(wú)解給出下面系統(tǒng)的一個(gè)基本可行解，或者說(shuō)明其無(wú)解引入引入人工人工變量變量目標(biāo)目標(biāo)：輔助問(wèn)題的輔助問(wèn)題的初始表格初始表格！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ǔ)輔助問(wèn)題的輔助問(wèn)題的最優(yōu)值是最優(yōu)值是0 0. . 原問(wèn)題的原問(wèn)題的BFS：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本

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

23、UAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)兩階段法兩階段法可求解任意的可求解任意的線性規(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èn)題無(wú)界無(wú)界或者或者有解有解第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)兩階段法的例子兩階段法的例子第

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

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

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

27、量 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 進(jìn)基進(jìn)基以為轉(zhuǎn)軸元，以為轉(zhuǎn)軸元，轉(zhuǎn)軸后轉(zhuǎn)軸后即得新基對(duì)應(yīng)的數(shù)據(jù)！即得新基對(duì)應(yīng)的數(shù)據(jù)！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)例例1 求解例求解例2.2.2q = 1a1進(jìn)基進(jìn)基，計(jì)算，計(jì)算 y1.得得第第 2 章章 線性規(guī)劃

28、線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)轉(zhuǎn)軸：轉(zhuǎn)軸：計(jì)算計(jì)算 , q = 3計(jì)算計(jì)算第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)計(jì)算計(jì)算最優(yōu)值：最優(yōu)值：最優(yōu)解：最優(yōu)解：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)問(wèn)題問(wèn)題. . 設(shè)用單純形法求解標(biāo)準(zhǔn)形式的設(shè)用單純形法求解標(biāo)準(zhǔn)形式的LPLP時(shí)得到如下時(shí)得到如下 單純形表單純形表. .還假設(shè)矩陣還假設(shè)矩陣A的的后三列形成單位矩陣后三列形成單位矩陣1.1.給出由該

29、表描述的當(dāng)前基是最優(yōu)的充分必要條件給出由該表描述的當(dāng)前基是最優(yōu)的充分必要條件( (依照表中的系數(shù)依照表中的系數(shù)).).2.2.假設(shè)該基是最優(yōu)的且假設(shè)該基是最優(yōu)的且 . .找出另外一個(gè)最找出另外一個(gè)最優(yōu)基本可行解，其與該表所描述的不同優(yōu)基本可行解，其與該表所描述的不同. .第第 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)的的 假設(shè)將原問(wèn)題中的假設(shè)將原問(wèn)題中的 ，給出使基保，給出使基保持最優(yōu)的持最優(yōu)的 的范圍的范圍. .1.1.假設(shè)將原問(wèn)題中的假設(shè)將原問(wèn)題中的 ，給出使基保，給

30、出使基保持最優(yōu)的持最優(yōu)的 的范圍的范圍問(wèn)題問(wèn)題 設(shè)用單純形法求解標(biāo)準(zhǔn)形式的設(shè)用單純形法求解標(biāo)準(zhǔn)形式的LPLP時(shí)得到如下單純時(shí)得到如下單純 形表形表. .還假設(shè)矩陣還假設(shè)矩陣 A 的的后三列形成單位矩陣后三列形成單位矩陣第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.2.7 單純形法的效率單純形法的效率有效性問(wèn)題有效性問(wèn)題: : 給定一個(gè)問(wèn)題，求解它需要多長(zhǎng)時(shí)間給定一個(gè)問(wèn)題，求解它需要多長(zhǎng)時(shí)間( (時(shí)時(shí)間復(fù)雜度間復(fù)雜度) )？求解它需要多少存儲(chǔ)空間？求解它需要多少存儲(chǔ)空間( (空間復(fù)雜度空間復(fù)雜度) )？ 平均情況平均情況(a

31、verage case): 典型問(wèn)題需要多少時(shí)間典型問(wèn)題需要多少時(shí)間 從數(shù)學(xué)上研究很困難從數(shù)學(xué)上研究很困難 經(jīng)驗(yàn)研究經(jīng)驗(yàn)研究?jī)煞N解答兩種解答最壞情況最壞情況(worst case): 最難的問(wèn)題需要多少時(shí)間最難的問(wèn)題需要多少時(shí)間 數(shù)學(xué)上是可處理的數(shù)學(xué)上是可處理的 有限值有限值 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)度量度量(measures)大小的度量大小的度量(measures of size)問(wèn)題的度量問(wèn)題的度量 約束的個(gè)數(shù)約束的個(gè)數(shù) m 和和/或者變量的個(gè)數(shù)或者變量的個(gè)數(shù) n 數(shù)據(jù)個(gè)數(shù)數(shù)據(jù)個(gè)數(shù)mn 非零數(shù)據(jù)的個(gè)數(shù)

32、非零數(shù)據(jù)的個(gè)數(shù) 尺寸，比如以尺寸，比如以bytes為單位為單位度量時(shí)間度量時(shí)間(measuring time) 算法的度量算法的度量 迭代次數(shù)迭代次數(shù) 每次迭代的算術(shù)運(yùn)算次數(shù)每次迭代的算術(shù)運(yùn)算次數(shù) 每次算術(shù)運(yùn)算的時(shí)間每次算術(shù)運(yùn)算的時(shí)間(依賴于硬件依賴于硬件)第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)Klee-Minty問(wèn)題問(wèn)題(1972)n = 3 時(shí)：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)扭曲的立方體扭曲的立方體(A distorted Cube

33、)約束集是如下立方體的約束集是如下立方體的稍微稍微(minor)扭曲：扭曲：n=3時(shí)：時(shí)：9608第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)指數(shù)指數(shù) (Exponential)Klee-Minty的問(wèn)題說(shuō)明：的問(wèn)題說(shuō)明： 當(dāng)求解具有當(dāng)求解具有 n 個(gè)變量和約束的問(wèn)題時(shí)，個(gè)變量和約束的問(wèn)題時(shí)，最小系數(shù)最小系數(shù)規(guī)則規(guī)則有可能需要有可能需要 2n-1 次轉(zhuǎn)軸次轉(zhuǎn)軸(因此因此遍歷遍歷了扭曲立方體的了扭曲立方體的 2n 個(gè)頂個(gè)頂點(diǎn)點(diǎn))當(dāng)當(dāng) n = 70 時(shí)，時(shí)，假設(shè)假設(shè) 1 秒鐘迭代秒鐘迭代 1000 次，求解這個(gè)問(wèn)題需要次，求解這

34、個(gè)問(wèn)題需要 400 億年；億年；宇宙的估計(jì)年齡是宇宙的估計(jì)年齡是 137 億年億年.然而每天求解的問(wèn)題中，變量在然而每天求解的問(wèn)題中，變量在10,000到到100,000之間的很普遍之間的很普遍.Worst case 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)單純形法：?jiǎn)渭冃畏ǎ?

35、最壞情況：最壞情況：O(n22n) 平均情況：平均情況：O(n3) 問(wèn)題：?jiǎn)栴}： 是否存在求解線性規(guī)劃的方法，是否存在求解線性規(guī)劃的方法，它的最壞性能分析是多項(xiàng)式的它的最壞性能分析是多項(xiàng)式的?第第 2 章章 線性規(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ā)

36、明了發(fā)明了單純形法單純形法 1979年年，L. Khachain找到了求解線性規(guī)劃的一種有效方法找到了求解線性規(guī)劃的一種有效方法(第一個(gè)多項(xiàng)式時(shí)間算法第一個(gè)多項(xiàng)式時(shí)間算法橢球法橢球法) 1984年年，N. Karmarkan發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效發(fā)現(xiàn)了另一種求解線性規(guī)劃的有效方法，已證明是單純形法的強(qiáng)有力的競(jìng)爭(zhēng)者方法，已證明是單純形法的強(qiáng)有力的競(jìng)爭(zhēng)者(投影內(nèi)點(diǎn)法投影內(nèi)點(diǎn)法) 現(xiàn)在求解大規(guī)模和退化問(wèn)題最有效的是現(xiàn)在求解大規(guī)模和退化問(wèn)題最有效的是原始對(duì)偶路徑跟原始對(duì)偶路徑跟蹤內(nèi)點(diǎn)法蹤內(nèi)點(diǎn)法(9.5節(jié)節(jié))第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUA

37、A數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)紐約時(shí)報(bào)紐約時(shí)報(bào)時(shí)代周刊時(shí)代周刊第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)華爾街日?qǐng)?bào)華爾街日?qǐng)?bào)商業(yè)周刊商業(yè)周刊第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)紐約時(shí)報(bào)紐約時(shí)報(bào)華爾街日?qǐng)?bào)華爾街日?qǐng)?bào)第第 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ī)

38、劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)l對(duì)偶問(wèn)題對(duì)偶問(wèn)題l對(duì)偶定理對(duì)偶定理l與單純形法的關(guān)系與單純形法的關(guān)系l互補(bǔ)定理互補(bǔ)定理l對(duì)偶單純形法對(duì)偶單純形法2.3 對(duì)偶對(duì)偶第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ) 原始問(wèn)題原始問(wèn)題(primal)：給定數(shù)據(jù)給定數(shù)據(jù)2.3.1 對(duì)偶問(wèn)題對(duì)偶問(wèn)題原始變量原始變量 對(duì)偶問(wèn)題對(duì)偶問(wèn)題(dual)：對(duì)偶變量對(duì)偶變量第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對(duì)偶問(wèn)

39、題：對(duì)稱形式的對(duì)偶對(duì)對(duì)偶問(wèn)題：對(duì)稱形式的對(duì)偶對(duì)注注1 對(duì)于線性規(guī)劃，對(duì)偶是相互的，即對(duì)于線性規(guī)劃，對(duì)偶是相互的，即對(duì)偶問(wèn)題的對(duì)偶對(duì)偶問(wèn)題的對(duì)偶 是原始問(wèn)題是原始問(wèn)題 原始問(wèn)題原始問(wèn)題(primal)：給定數(shù)據(jù)給定數(shù)據(jù)注注2 2 為了確定任一線性規(guī)劃問(wèn)題的對(duì)偶，可以利用為了確定任一線性規(guī)劃問(wèn)題的對(duì)偶，可以利用 對(duì)稱形式或非對(duì)稱形式的對(duì)偶對(duì)！對(duì)稱形式或非對(duì)稱形式的對(duì)偶對(duì)！原始變量原始變量 對(duì)偶問(wèn)題對(duì)偶問(wèn)題(dual)：對(duì)偶變量對(duì)偶變量第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ) 配餐問(wèn)題配餐問(wèn)題：確定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)

40、最?。浚捍_定食品數(shù)量，滿足營(yíng)養(yǎng)需求，花費(fèi)最?。縩種食品，種食品，m種營(yíng)養(yǎng)成份；第種營(yíng)養(yǎng)成份；第 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ù)量 模型：模型：對(duì)偶問(wèn)題：經(jīng)濟(jì)解釋對(duì)偶問(wèn)題：經(jīng)濟(jì)解釋對(duì)偶問(wèn)題保健品公司藥劑師、營(yíng)養(yǎng)丸、對(duì)偶問(wèn)題保健品公司藥劑師、營(yíng)養(yǎng)丸、定價(jià)問(wèn)題定價(jià)問(wèn)題第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對(duì)偶問(wèn)題：一般問(wèn)題

41、的對(duì)偶對(duì)偶問(wèn)題：一般問(wèn)題的對(duì)偶給定數(shù)據(jù)給定數(shù)據(jù) A, b, c；記；記 A 的第的第 i 行為行為 ai，A 的第的第 j 列為列為 aj 原始問(wèn)題原始問(wèn)題(primal)： 對(duì)偶問(wèn)題對(duì)偶問(wèn)題(dual)：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對(duì)偶問(wèn)題：例子對(duì)偶問(wèn)題：例子第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.3.2 對(duì)偶定理對(duì)偶定理弱對(duì)偶定理弱對(duì)偶定理. . 設(shè)設(shè) 和和 分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解，則解，

42、則 . . 推論推論2. 如果原始問(wèn)題與對(duì)偶問(wèn)題之一無(wú)界，則另一個(gè)問(wèn)題如果原始問(wèn)題與對(duì)偶問(wèn)題之一無(wú)界，則另一個(gè)問(wèn)題 沒有可行解沒有可行解.推論推論1. 設(shè)設(shè) 和和 分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解,若若 則則 和和 分別是原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解分別是原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解. .考慮對(duì)偶問(wèn)題的初衷！考慮對(duì)偶問(wèn)題的初衷！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對(duì)偶定理：強(qiáng)對(duì)偶定理對(duì)偶定理：強(qiáng)對(duì)偶定理對(duì)于一般形式的線性規(guī)劃利用對(duì)于一般形式的線性規(guī)劃利用凸集分離凸集分離定理定理證明！證明！強(qiáng)對(duì)

43、偶定理強(qiáng)對(duì)偶定理. . 如果原始問(wèn)題和對(duì)偶問(wèn)題之一有解，則另如果原始問(wèn)題和對(duì)偶問(wèn)題之一有解，則另一個(gè)問(wèn)題也有解，且最優(yōu)值相等一個(gè)問(wèn)題也有解，且最優(yōu)值相等. .有解有解無(wú)無(wú)(下下)界界不可行不可行有解有解無(wú)無(wú)(上上)界界不可行不可行 對(duì)偶問(wèn)題對(duì)偶問(wèn)題原始問(wèn)題原始問(wèn)題第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.3.3 與單純形法的關(guān)系與單純形法的關(guān)系如何由原始問(wèn)題的解得到對(duì)偶問(wèn)題的解？定理2.3.3. 設(shè)標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題有最優(yōu)解，B是最優(yōu)基本可行解對(duì)應(yīng)的基，則是其對(duì)偶問(wèn)題的最優(yōu)解.特例：當(dāng)系數(shù)矩陣A中有單位矩陣時(shí)，如何從單

44、純形表讀出當(dāng)前基的逆矩陣？第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)考慮問(wèn)題引入松弛變量標(biāo)準(zhǔn)形利用單純形法求解與單純形法的關(guān)系與單純形法的關(guān)系：例子：例子對(duì)偶問(wèn)題第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)與單純形法的關(guān)系：例子與單純形法的關(guān)系：例子( (續(xù)續(xù)) )原原問(wèn)題問(wèn)題最優(yōu)解最優(yōu)解對(duì)偶對(duì)偶問(wèn)題問(wèn)題最優(yōu)解最優(yōu)解第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)2.3.4 靈敏度靈敏度與

45、與互補(bǔ)性互補(bǔ)性 與基與基 B 對(duì)應(yīng)的單純形乘子對(duì)應(yīng)的單純形乘子(simplex multiplier) 經(jīng)濟(jì)解釋經(jīng)濟(jì)解釋 記記 A 的列向量為的列向量為 aj，對(duì)應(yīng)費(fèi)用為，對(duì)應(yīng)費(fèi)用為 cj，j =1 , , n解釋為單位向量解釋為單位向量 ei 的的合成價(jià)格合成價(jià)格！解釋為解釋為 aj 的的相對(duì)相對(duì)/既約既約費(fèi)用系數(shù)費(fèi)用系數(shù) 最優(yōu)性：最優(yōu)性：對(duì)所有的對(duì)所有的 j 有有 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)靈敏度靈敏度(sensitivity)與與影子價(jià)格影子價(jià)格(shadow price)問(wèn)題：當(dāng)向量問(wèn)題：當(dāng)向量 b

46、 發(fā)生微小變化時(shí)，問(wèn)題的最優(yōu)值如何變化？發(fā)生微小變化時(shí)，問(wèn)題的最優(yōu)值如何變化？假設(shè)該問(wèn)題的最優(yōu)基是假設(shè)該問(wèn)題的最優(yōu)基是 B且且 B-1b 0 (非退化！非退化！)令令第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)因?yàn)?所以稱稱 為分量為分量 所對(duì)應(yīng)資源的所對(duì)應(yīng)資源的邊際邊際價(jià)格價(jià)格(marginal price) 或者或者影子影子價(jià)格價(jià)格(shadow price)從而z*z* 第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)互補(bǔ)定理互補(bǔ)定理(線性規(guī)劃的最優(yōu)性條

47、件線性規(guī)劃的最優(yōu)性條件)用用 aj 表示表示 A 的第的第 j 列，列，ai 表示表示 A 的第的第 i 行行 定理定理. . 設(shè)設(shè) 和和 分別是分別是非對(duì)非對(duì)稱稱形式原始問(wèn)題和對(duì)偶問(wèn)題形式原始問(wèn)題和對(duì)偶問(wèn)題的的可行解可行解. 則它們是各自最則它們是各自最優(yōu)解的優(yōu)解的充要充要條件是：對(duì)所有條件是：對(duì)所有 i 有有定理定理. 設(shè)設(shè) 和和 分別是分別是對(duì)稱對(duì)稱形式原始問(wèn)題和對(duì)偶問(wèn)題的形式原始問(wèn)題和對(duì)偶問(wèn)題的可行解可行解. 則它們是各自最優(yōu)則它們是各自最優(yōu)解的解的充要充要條件是：對(duì)所有的條件是：對(duì)所有的 i 和和 j 有有課本上定理3.2.1(p.63)的證明要用到互補(bǔ)定理！第第 2 章章 線性規(guī)劃

48、線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)互補(bǔ)定理互補(bǔ)定理(線性規(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ǔ)2.3.5 對(duì)偶單純形法對(duì)偶單純形法 適用問(wèn)題：標(biāo)準(zhǔn)形問(wèn)題有一個(gè)適用問(wèn)題：標(biāo)準(zhǔn)形問(wèn)題有一個(gè)不可行不可行的基本解，的基本解，但但 對(duì)應(yīng)單純形乘子是對(duì)偶問(wèn)題的可行解對(duì)應(yīng)單純形乘子是對(duì)偶問(wèn)題的可行解 單純形表中的表現(xiàn)：?jiǎn)渭冃伪碇械谋憩F(xiàn)： 第一張單純形表第一張單純形表: : 相對(duì)費(fèi)用系數(shù)非負(fù)，但有基變量取負(fù)值！相對(duì)

49、費(fèi)用系數(shù)非負(fù)，但有基變量取負(fù)值！ 轉(zhuǎn)軸過(guò)程中：保持相對(duì)費(fèi)用系數(shù)非負(fù)，直到轉(zhuǎn)軸過(guò)程中：保持相對(duì)費(fèi)用系數(shù)非負(fù)，直到全部全部基變量基變量 取非負(fù)值！取非負(fù)值！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)則稱則稱 x 是標(biāo)準(zhǔn)形問(wèn)題的是標(biāo)準(zhǔn)形問(wèn)題的對(duì)偶可行對(duì)偶可行基本解基本解.定義定義 假設(shè)是假設(shè)是 Ax = b 的基本解的基本解. 如果如果基本解基本解(互補(bǔ)性互補(bǔ)性)可行對(duì)偶可行最優(yōu)解可行對(duì)偶可行最優(yōu)解初始對(duì)偶可行基本解初始對(duì)偶可行基本解新的對(duì)偶可行基本解新的對(duì)偶可行基本解“原始可行對(duì)偶可行原始可行對(duì)偶可行”的基本解！的基本解！迭代

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

51、函數(shù)的值目標(biāo)函數(shù)的值增大增大！修正單純形法第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對(duì)偶單純形法：推導(dǎo)對(duì)偶單純形法：推導(dǎo)IIII出基變量：取出基變量：取負(fù)值負(fù)值的基變量的基變量( (* * * * * *) )進(jìn)基變量：其進(jìn)基變量：其 p 行的負(fù)元素，且取到行的負(fù)元素，且取到最小正比值最小正比值 ( (* * * * * *) )第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)步步0 給定對(duì)偶可行基本解對(duì)應(yīng)的單純形表給定對(duì)偶可行基本解對(duì)應(yīng)的單純形表.步步1

52、若對(duì)若對(duì)每個(gè)每個(gè) i 都有都有 ，停；當(dāng)前，停；當(dāng)前DFBS是最優(yōu)的是最優(yōu)的.步步2 選取選取 p 滿足滿足 yp0 0 ，這時(shí)，第，這時(shí)，第 p 個(gè)基變量出基個(gè)基變量出基.步步4 以以 ypq 為轉(zhuǎn)軸元進(jìn)行為轉(zhuǎn)軸元進(jìn)行轉(zhuǎn)軸轉(zhuǎn)軸，更新單純形表，返步，更新單純形表，返步1.對(duì)偶單純形法：計(jì)算步驟對(duì)偶單純形法：計(jì)算步驟步步3 若若 ，問(wèn)題，問(wèn)題無(wú)可行解無(wú)可行解；否則，；否則， 選選 q 滿足滿足第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)引入盈余變量；并給等式兩邊同乘引入盈余變量；并給等式兩邊同乘 -1；得初始表格；得初始表格/

53、第一張第一張單純形表單純形表對(duì)偶單純形法：例子對(duì)偶單純形法：例子第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對(duì)偶單純形法：例子對(duì)偶單純形法：例子( (續(xù)續(xù)) )最優(yōu)解：最優(yōu)解：第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ)對(duì)偶單純形法：收斂性對(duì)偶單純形法：收斂性定理定理. . 如果標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題的任一對(duì)偶可行基本如果標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題的任一對(duì)偶可行基本解所對(duì)應(yīng)的非基變量的相對(duì)費(fèi)用系數(shù)解所對(duì)應(yīng)的非基變量的相對(duì)費(fèi)用系數(shù)大于零大于零，則對(duì)偶，則對(duì)偶單純形法在單

54、純形法在有限步有限步內(nèi)終止內(nèi)終止. . 如果線性規(guī)劃問(wèn)題可以用對(duì)偶單純形法求解，則必有界！如果線性規(guī)劃問(wèn)題可以用對(duì)偶單純形法求解，則必有界！ 其計(jì)算結(jié)果只能是其計(jì)算結(jié)果只能是不可行不可行或者或者有解有解！ 如果線性規(guī)劃問(wèn)題可以用單純形法求解，則其如果線性規(guī)劃問(wèn)題可以用單純形法求解，則其無(wú)界無(wú)界或或有解有解 兩階段法可以求解任一線性規(guī)劃問(wèn)題；兩階段法可以求解任一線性規(guī)劃問(wèn)題； 第第I階段的結(jié)果為階段的結(jié)果為可行可行或者或者不可行不可行兩種；兩種； 對(duì)于可行的，在第對(duì)于可行的，在第II階段可得問(wèn)題階段可得問(wèn)題無(wú)界無(wú)界或或有解有解！第第 2 章章 線性規(guī)劃線性規(guī)劃: 基本理論與方法基本理論與方法LHY-SMSS-BUAA數(shù)學(xué)規(guī)劃基礎(chǔ)數(shù)學(xué)規(guī)劃基礎(chǔ) 典型典型情況情況( (有顯然的對(duì)偶可行基本解有顯然的對(duì)偶可行基本解) ) 一般一般情況情況 已有一個(gè)標(biāo)準(zhǔn)形問(wèn)題的最優(yōu)解和最優(yōu)基已有一個(gè)標(biāo)準(zhǔn)形問(wèn)題的最優(yōu)解和最優(yōu)基 添加一個(gè)添加一個(gè)“不等式約束不等式約束”后的新問(wèn)題后的新問(wèn)題( (習(xí)題習(xí)題3.9) )靈敏度分析靈敏度分析對(duì)偶單純形法：?jiǎn)?dòng)對(duì)偶單純