最優(yōu)化理論與算法完整版課件

1、TP SHUAI,1,最優(yōu)化理論與算法,,TP SHUAI,2,提綱,1. 線性規(guī)劃 對偶定理2. 非線性規(guī)劃 K-K-T 定理3. 組合最優(yōu)化 算法設(shè)計技巧,使用教材：最優(yōu)化理論與算法 陳寶林參考書 ：數(shù)學(xué)規(guī)劃 黃紅選， 韓繼業(yè) 清華大學(xué)出版社,TP SHUAI,3,其他參考書目,,Nonlinear Programming - Theory and AlgorithmsMokhtar S. Bazaraa, C.

2、M. ShettyJohn Wiley & Sons, Inc. 1979 (2nd Edit, 1993，3nd Edit，2006),Linear and Nonlinear Programming David G. LuenbergerAddison-Wesley Publishing Company, 2nd Edition, 1984/2003..,TP SHUAI,4,Linear Programming an

3、d Network Flows M. S. Bazaraa, J. J. Jarvis, John Wiley & Sons, Inc., 1977.,運(yùn)籌學(xué)基礎(chǔ)手冊徐光輝、劉彥佩、程侃科學(xué)出版社，1999,組合最優(yōu)化算法和復(fù)雜性 Combinatorial Optimization 蔡茂誠、劉振宏 Algorithms and Complexity 清華大學(xué)出版社，1988

4、 Printice-Hall Inc.,1982/1998,其他參考書目,,TP SHUAI,5,1,緒論----學(xué)科概述,最優(yōu)化是從所有可能的方案中選擇最合理 的一種方案,以達(dá)到最佳目標(biāo) 的科學(xué).達(dá)到最佳目標(biāo)的方案是最優(yōu)方案,尋找最優(yōu) 方案的方法----最優(yōu)化方法(算法)這種方法的數(shù)學(xué)理論即為最優(yōu)化理論.是運(yùn)籌學(xué)的方法論之一.是其重要組成部分.,,運(yùn)籌學(xué)的“三個代表”模型理論算法,最優(yōu)化首先是一種理念,其次才

5、是一種方法.,TP SHUAI,6,緒論---運(yùn)籌學(xué)（Operations Research - OR）,運(yùn)籌學(xué)方法,TP SHUAI,7,優(yōu)化樹,TP SHUAI,8,最優(yōu)化的發(fā)展歷程,費(fèi)馬:1638;牛頓,1670,歐拉,1755,Min f(x1 x2 ··· xn ) ? f(x)=0,TP SHUAI,9,歐拉，拉格朗日：無窮維問題，變分學(xué)柯西：最早應(yīng)用最速下降法,拉格朗日，1797,

6、Min f(x1 x2 ··· xn)s.t. gk (x1 x2 ··· xn )=0, k=1,2,…,m,TP SHUAI,10,1930年代，康托諾維奇：線性規(guī)劃1940年代，Dantzig：單純形方法， 馮 諾依曼：對策論1950年代，Bellman：動態(tài)規(guī)劃，最優(yōu)性原理； KK

7、T條件；1960年代：Zoutendijk,Rosen,Carroll,etc.非線性規(guī)劃算法，Duffin，Zener等幾何規(guī)劃，Gomory，整數(shù)規(guī)劃,Dantzig等隨機(jī)規(guī)劃 6-70年代：Cook等復(fù)雜性理論，組合優(yōu)化迅速發(fā)展,電子計算機(jī)----------?最優(yōu)化,TP SHUAI,11,最優(yōu)化應(yīng)用舉例,具有廣泛的實(shí)用性運(yùn)輸問題，車輛調(diào)度，員工安排，空運(yùn)控制等工程設(shè)計，結(jié)構(gòu)設(shè)計等資源分配，生產(chǎn)計劃等通信：光網(wǎng)絡(luò)、無

8、線網(wǎng)絡(luò)，ad hoc 等.制造業(yè)：鋼鐵生產(chǎn)，車間調(diào)度等醫(yī)藥生產(chǎn)，化工處理等電子工程，集成電路VLSI etc.排版（TEX,Latex,etc.）,TP SHUAI,12,1. 食譜問題,,我每天要求一定量的兩種維生素，Vc和Vb。假設(shè)這些維生素可以分別從牛奶和雞蛋中得到。,需要確定每天喝奶和吃蛋的量，目標(biāo)以便以最低可能的花費(fèi)購買這些食物，而滿足最低限度的維生素需求量。,TP SHUAI,13,1. 食譜問題（續(xù)）,,令x

9、表示要買的奶的量，y為要買的蛋的量。食譜問題可以寫成如下的數(shù)學(xué)形式：,運(yùn)籌學(xué)工作者參與建立關(guān)于何時出現(xiàn)最小費(fèi)用（或者最大利潤）的排序，或者計劃，早期被標(biāo)示為programs。求最優(yōu)安排或計劃的問題，稱作programming問題。,Min 3x +2.5y s.t. 2x + 4y ? 40 3x + 2y ? 50 x, y ? 0.,極小化目標(biāo)函數(shù)可行區(qū)域（單純形）可行解,TP SH

10、UAI,14,2 運(yùn)輸問題,,設(shè)某種物資有m個產(chǎn)地A1,A2,…Am,各產(chǎn)地的產(chǎn)量是a1,a2,…,am;有 n個銷地B1,B2,…,Bn.各銷地的銷量是b1,b2,…,bn.假定從產(chǎn)地Ai(i=1,2,…,m)到銷地Bj(j=1,2,…,n)運(yùn)輸單位物品的運(yùn)價是cij問怎樣調(diào)運(yùn)這些物品才能使總運(yùn)費(fèi)最??？,如果運(yùn)輸問題的總產(chǎn)量等于總銷量，即有,則稱該運(yùn)輸問題為產(chǎn)銷平衡問題；反之，稱產(chǎn)銷不平衡問題。,TP SHUAI,15,令xij表示由

11、產(chǎn)地Ai運(yùn)往銷地Bj的物品數(shù)量，則產(chǎn)銷平衡問題的數(shù)學(xué)模型為：,2 運(yùn)輸問題（續(xù)）,,TP SHUAI,16,以價格qi 購買了si份股票i,i=1,2,…,n股票i的現(xiàn)價是pi你預(yù)期一年后股票的價格為ri 在出售股票時需要支付的稅金=資本收益×30%扣除稅金后，你的現(xiàn)金仍然比購買股票前增多支付1%的交易費(fèi)用例如：將原先以每股30元的價格買入1000股股票，以每股50元的價格出售，則凈現(xiàn)金為：50 ×10

12、00-0.3(50-30)1000-0.1×50 ×1000=39000,3 稅下投資問題,,TP SHUAI,17,我們的目標(biāo)是要使預(yù)期收益最大。Xi：當(dāng)前拋出股票i的數(shù)量。,3 稅下投資問題（續(xù)）,,TP SHUAI,18,4 選址問題（1）,,實(shí)例:一組潛在位置（地址）, 一組顧客集合及相應(yīng)的 利潤和費(fèi)用數(shù)據(jù)； 解: 設(shè)施開放(使用)的數(shù)目，他們的位置，以及顧客

13、被哪個設(shè)施服務(wù)的具體安排方案；目標(biāo)：總的利潤最大化。,數(shù)據(jù)與約束J={1,2,…,n}:放置設(shè)施的可能的潛在位置集合I={1,2,…,m}:顧客集合,其要求的服務(wù)需要某設(shè)施所提 供.,TP SHUAI,19,4 選址問題（2）,,TP SHUAI,20,4選址問題（3）,,TP SHUAI,21,5負(fù)載平衡(1),,實(shí)例: 網(wǎng)絡(luò)G(V,E) 及一組m 個數(shù)的集合{?s,d>0}，表示 連接源

14、點(diǎn) s與匯點(diǎn)d 之間的流量解: {?s,d>0}的一組路由, 即G(V,E) 中m 條s 與 d間的路, 表示連接s與d 的負(fù)載流量的路徑。目標(biāo):極小化網(wǎng)絡(luò)負(fù)載,TP SHUAI,22,5 負(fù)載平衡(2),,TP SHUAI,23,6.結(jié)構(gòu)設(shè)計問題,兩桿桁架的最優(yōu)設(shè)計問題。由兩根空心圓桿組成對稱的兩桿桁架，其頂點(diǎn)承受負(fù)載為2p，兩支座之間的水平距離為2L，圓桿的壁厚為B，桿的比重為ρ，彈性模量為E

15、，屈吸強(qiáng)度為δ。求在桁架不被破壞的情況下使桁架重量最輕的桁架高度h及圓桿平均直徑d。,,TP SHUAI,24,6.結(jié)構(gòu)設(shè)計問題,,TP SHUAI,25,6.結(jié)構(gòu)設(shè)計問題,,此應(yīng)力要求小于材料的屈吸極限，即,解：桁桿的截面積為 ：,桁桿的總重量為：,負(fù)載2p在每個桿上的分力為：,于是桿截面的應(yīng)力為：,圓桿中應(yīng)力小于等于壓桿穩(wěn)定的臨界應(yīng)力。由材料力學(xué)知：壓桿穩(wěn)定的臨界應(yīng)力為,由此得穩(wěn)定約束：,6.結(jié)構(gòu)設(shè)計問題,,,另外還要考慮到設(shè)計變

16、量d和h有界。 從而得到兩桿桁架最優(yōu)設(shè)計問題的數(shù)學(xué)模型：,6.結(jié)構(gòu)設(shè)計問題,,TP SHUAI,28,基本概念,在上述例子中,有的目標(biāo)函數(shù)和約束函數(shù)都是線性的,稱之為線性規(guī)劃問題,而有的模型中含有非線性函數(shù),稱之為非線性規(guī)劃.在線性與非線性規(guī)劃中,滿足約束條件的點(diǎn)稱為可行點(diǎn),全體可行點(diǎn)組成的集合稱為可行集或可行域.如果一個問題的可行域是整個空間,則稱此問題為無約束問題.,,TP SHUAI,29,基本概念,最優(yōu)化問題可寫成如下

17、形式:,,TP SHUAI,30,基本概念,Df 1. 1 設(shè)f(x)為目標(biāo)函數(shù)，S為可行域，x0?S,若對每一個x ?S,成立f(x)?f(x0),則稱x0為極小化問題min f(x), x ?S的最優(yōu)解（整體最優(yōu)解）,則稱x0為極小化問題min f(x),x ?S的局部最優(yōu)解,Df 1.2 設(shè)f(x)為目標(biāo)函數(shù)，S為可行域，,,TP SHUAI,31,Thank you very much for your attendance!

18、,優(yōu)化軟件 http://www-neos.mcs.anl.gov/ http://neos.mcs.anl.gov/neos/solvers/index.html,TP SHUAI,32,最優(yōu)化理論與算法,帥天平北京郵電大學(xué)數(shù)學(xué)系Email:tpshuai@gmail.com,Tel:62281308,Rm:主樓814§ 1 預(yù)備知識,TP SHUAI,33,1，

19、 預(yù)備知識,1.線性空間2.范數(shù)3.集合與序列4.矩陣的分解與校正,TP SHUAI,34,1.線性空間,Df 1.3:給定一非空集合G以及在G上的一種代數(shù)運(yùn)算+:G×G→G(稱為加法),若下述條件成立:,則稱為一個群.若還滿足對任意的a,b∈G,有a+b=b+a,則稱為一個阿貝爾群(&交換群),TP SHUAI,35,1.線性空間,Df 1.4:給定一非空集合V和一個域F,并定義兩種運(yùn)算加法+:V×

20、V→V以及數(shù)乘?: F×V→V.若構(gòu)成一交換群,且兩種運(yùn)算滿足下面性質(zhì):,則稱V在域F上關(guān)于加法和數(shù)乘 ? 運(yùn)算構(gòu)成一線性空間,簡稱V為F上的線性空間.記為V(F).若V的非空子集合S關(guān)于加法和數(shù)乘運(yùn)算在F上也構(gòu)成一線性空間,則S稱為F上的線性子空間.,TP SHUAI,36,1.線性空間,例子,TP SHUAI,37,1.線性空間,TP SHUAI,38,1.線性空間,Th1.1 線性空間V(F)的非空子集S的線性擴(kuò)張L

21、(S)是V中包含S的最小子空間.,TP SHUAI,39,1.線性空間,TP SHUAI,40,1.線性空間,TP SHUAI,41,2.范數(shù),TP SHUAI,42,2.范數(shù),TP SHUAI,43,2.范數(shù),TP SHUAI,44,3.集合與序列,TP SHUAI,45,3，集合與序列,TP SHUAI,46,3.集合與序列,TP SHUAI,47,3.集合與序列,TP SHUAI,48,4.矩陣的分解與校正,Th1.5 若n階矩

22、陣A可逆，則存在一個排列矩陣P,單位下三角矩陣L和上三角矩陣U，使得PA=LU,TP SHUAI,49,4.矩陣的分解與校正,Th1.6 設(shè)A為對稱正定矩陣，則（1）矩陣A可唯一的分解成A=LDLT, 其中L為單位下三角矩陣，D為對角矩陣（2）存在可逆的下三角矩陣L，使得A=LLT. 當(dāng)L的對角元素為正時，分解是唯一的。(Cholesky分解),TP SHUAI,50,4.矩陣的分解與校正,TP SHUAI,51,4.矩陣的分解與

23、校正,TP SHUAI,52,5.函數(shù)的可微性與展開,TP SHUAI,53,5.函數(shù)的可微性與展開,當(dāng)f(x)在x點(diǎn)存在二階偏導(dǎo)時,函數(shù)f在點(diǎn)x的Hesse矩陣定義為,TP SHUAI,54,5.函數(shù)的可微性與展開,TP SHUAI,55,5.函數(shù)的可微性與展開,TP SHUAI,56,5.函數(shù)的可微性與展開,TP SHUAI,57,最優(yōu)化理論與算法,帥天平北京郵電大學(xué)數(shù)學(xué)系Email:tpshuai@gmail.com,Tel

24、:62281308,Rm:主樓814§2，凸分析與凸函數(shù),,TP SHUAI,58,2. 凸集與凸函數(shù),,2.1 凸集與錐,TP SHUAI,59,2. 凸集與凸函數(shù),,TP SHUAI,60,2. 凸集與凸函數(shù),,TP SHUAI,61,2. 凸集與凸函數(shù),,TP SHUAI,62,運(yùn)用定義不難驗(yàn)證如下命題：,2. 凸集與凸函數(shù),,TP SHUAI,63,2. 凸集與凸函數(shù),,多面體(polyhedral set)是有限

25、閉半空間的交. (可表為 Ax?b ).,TP SHUAI,64,2. 凸集與凸函數(shù),,,TP SHUAI,65,多面集 {x|Ax?0}也是凸錐，稱為多面錐。,2. 凸集與凸函數(shù),,由定義可知,錐關(guān)于正的數(shù)乘運(yùn)算封閉,凸錐關(guān)于加法和正的數(shù)乘封閉,一般的,對于凸集S,集合,K(S)={λx|λ>0,x?S},是包含S的最小凸錐.,錐C稱為尖錐,若0?S.尖錐稱為突出的,若它不包含一維子空間.,約定: 非空集合S生成的凸錐,是指

26、可以表示成S中有限個元素的非負(fù)線性組合(稱為凸錐組合)的所有點(diǎn)所構(gòu)成的集合,記為coneS. 若S凸,則,coneS=K(S) ∪{0},TP SHUAI,66,2. 凸集與凸函數(shù),,Df 2.5 非空凸集中的點(diǎn) x 稱為極點(diǎn),若 x=?x1+(1-?)x2 , ??(0,1) , x1 ,x2 ?S, 則 x=x1=x2.換言之,x不能表示成S中兩個不同點(diǎn)的凸組合.,由上可知,任何有界凸集中任一點(diǎn)都可表成極點(diǎn)的凸組合.,TP SHU

27、AI,67,2. 凸集與凸函數(shù),,Def 2.6. 設(shè)非空凸集S?Rn, Rn中向量d?0 稱為S的一個回收方向(方向), 若對每一 x?S, R(x.d)={x+?d| ??0 }?S.S的所有方向構(gòu)成的尖錐稱為S的回收錐,記為0+S,方向d1和d2 稱為S的兩個不同的方向,若對任意?>0, 都有 d1??d2；方向d稱為S的極方向extreme direction ,若 d=?d1+(1-?)d2, ??(0,1),d1 ,

28、d2 是S的兩個方向,則有 d=d1=d2.換言之d不能表成它的兩個不同方向的凸錐組合,TP SHUAI,68,2. 凸集與凸函數(shù),,TP SHUAI,69,2. 凸集與凸函數(shù),表示定理,,Th2.4 若多面體P={x?Rn|Ax?b}?, r(A)=n則:,則,(3)指標(biāo)集J是空集當(dāng)且僅當(dāng)P是有界集合,即多胞形.,TP SHUAI,70,2. 凸集與凸函數(shù),,表示定理直觀描述:設(shè) X 為非空多面體. 則存在有限個極點(diǎn) x1, …,

29、xk , k>0. 進(jìn)一步,存在有限個極方向 d1, …, dl, l>0 當(dāng)且僅當(dāng) X 無界. 進(jìn)而, x?X 的充要條件是 x 可以表為 x1, …, xk 的凸組合和d1, …, dl的非負(fù)線性組合(凸錐組合).,推論2.1 若多面體S={x|Ax=b,x≥0}非空,則S必有極點(diǎn).,TP SHUAI,71,2. 2 凸集分離定理,2. 凸集與凸函數(shù),,TP SHUAI,72,2. 凸集與凸函數(shù),,TP SHUAI

30、,73,證明：令,2. 凸集與凸函數(shù),,TP SHUAI,74,所以為柯西列，必有極限,且由S為閉集知。此極限點(diǎn)必在S中。,2. 凸集與凸函數(shù),,下證明唯一性,TP SHUAI,75,2. 凸集與凸函數(shù),,TP SHUAI,76,2. 凸集與凸函數(shù),,TP SHUAI,77,2. 凸集與凸函數(shù),,證明提綱,TP SHUAI,78,由此可得,2. 凸集與凸函數(shù),,TP SHUAI,79,2. 凸集與凸函數(shù),Th2.7表明，S為閉凸集， y

31、?S，則y與S可分離。若令clS表示非空集合S的閉包，則當(dāng)y?clS時，定理結(jié)論也真。實(shí)際上我們有下述定理,,TP SHUAI,80,證明,2. 凸集與凸函數(shù),,TP SHUAI,81,推論2.2：設(shè)S為Rn 中的非空集合，y?S,則存在非零向量p，使對?x?clS, pT (x-y)?0,2. 凸集與凸函數(shù),,TP SHUAI,82,2. 凸集與凸函數(shù),,TP SHUAI,83,2. 凸集與凸函數(shù),,TP SHUAI,84,作為凸集分

32、離定理的應(yīng)用，下面介紹兩個擇一定理：Farkas定理和Gordan定理，它們在最優(yōu)化理論中是很有用的。,2. 凸集與凸函數(shù),,2.3 擇一定理,TP SHUAI,85,2. 凸集與凸函數(shù),,TP SHUAI,86,2. 凸集與凸函數(shù),,TP SHUAI,87,2. 凸集與凸函數(shù),,TP SHUAI,88,2. 凸集與凸函數(shù),,TP SHUAI,89,2. 凸集與凸函數(shù),,TP SHUAI,90,2. 凸集與凸函數(shù),,TP SHUAI,9

33、1,2. 凸集與凸函數(shù),,TP SHUAI,92,2. 凸集與凸函數(shù),,TP SHUAI,93,2. 凸集與凸函數(shù),2.4 凸函數(shù),,,Df2. 10 設(shè)S?Rn是非空凸集,函數(shù)f:S?R,若對任意x1, x2∈S,和每一λ∈(0, 1)都有 f(λx1+(1-λ)x2)≤λf(x1)+(1-λ)f(x2)則稱f是S上的凸函數(shù).若上面的不等式對于x?y嚴(yán)格成立,則稱f是S上的嚴(yán)格凸函數(shù). 若-f是S上的凸函數(shù),

34、則稱f是S上的凹函數(shù).若-f是S上的嚴(yán)格凸函數(shù),則稱f是S上的嚴(yán)格凹函數(shù).,2.4.1 基本性質(zhì),TP SHUAI,94,2. 凸集與凸函數(shù),,,TP SHUAI,95,Th2.13 設(shè) f 是一凸函數(shù)，則對任意的x?Rn 和d(?0 )?Rn，f在x處沿方向d的方向?qū)?shù)存在。,2. 凸集與凸函數(shù),,TP SHUAI,96,2. 凸集與凸函數(shù),,TP SHUAI,97,2.凸集與凸函數(shù),,,TP SHUAI,98,命題2.3 設(shè)f是定

35、義在凸集S上的凸函數(shù)，則(1)所有凸函數(shù)f的集合關(guān)于凸錐組合運(yùn)算是封閉的,即(a)實(shí)數(shù)??0，則?f也是定義在S上的凸函數(shù)(b)設(shè)f1和f2是定義在凸集S上的凸函數(shù)，則f1+f2也是定義在S上的凸函數(shù),2. 凸集與凸函數(shù),,(2)函數(shù)f在開集intS內(nèi)是連續(xù)的.(3)函數(shù)f的水平集L(f,?)={x|x?S,f(x) ≤?},??R 和上鏡圖epi(f)={(x,y)|x?S,y?R,y≥f(x)}都是凸集,TP SHUA

36、I,99,2. 凸集與凸函數(shù),,,設(shè)S 為Rn中的非空凸集,則 f(x) 是凸的當(dāng)且僅當(dāng)上鏡圖 epif={(x, y) | x∈S, y∈R, y≥f(x)}是凸集,對上鏡圖事實(shí)上我們有如下定理,TP SHUAI,100,2. 凸集與凸函數(shù),,TP SHUAI,101,定理2.14 設(shè)S?Rn為一非空凸集，f是定義在S上的凸函數(shù)，則f在S上的局部極小點(diǎn)是整體極小點(diǎn)，且極小點(diǎn)的集合為凸集。,2. 凸集與凸函數(shù),,TP SH

37、UAI,102,2. 凸集與凸函數(shù),,TP SHUAI,103,2. 凸集與凸函數(shù),,TP SHUAI,104,2. 凸集與凸函數(shù),2.5.2 凸函數(shù)的判別,,Th2.16. 設(shè)S 是Rn 中的非空開凸集, f(x):S?R 是可微的函數(shù) 則 f(x) 是凸函數(shù)當(dāng)且僅當(dāng)對任意的 x*?S, 我們有f(x) ? f(x*)+?f(x*) (x-x*), 任意 x?S. 類似的, f(x) 嚴(yán)格凸當(dāng)且僅當(dāng)對每一 x*?S,f(x)

38、> f(x*)+?f(x*) (x-x*), 任意 x?S.,2.4.2 凸函數(shù)的判別,TP SHUAI,105,2. 凸集與凸函數(shù),,TP SHUAI,106,2. 凸集與凸函數(shù),,Th 2.16*. 設(shè)S 是 Rn 上的非空開凸集, f(x) 為 S 到 R上的可微函數(shù). 則 f(x) 是凸函數(shù)當(dāng)且僅當(dāng)任意的 x1, x2 ?S, 有 (?f(x2)-?f(x1))(x2-x1)?0.類似

39、的, f 嚴(yán)格凸當(dāng)且僅當(dāng)對任意相異的 x1, x2 ?S, (?f(x2)-?f(x1))(x2-x1)>0.,TP SHUAI,107,,,2. 凸集與凸函數(shù),TP SHUAI,108,2. 凸集與凸函數(shù),Th 2.17 設(shè)S 是 Rn a上的非空開凸集, f(x) 為 S 到 R上的二次可微函數(shù). 則(1) f(x) 是凸函數(shù)當(dāng)且僅當(dāng)S上每一點(diǎn)的Hessian矩陣是半正定的.(2) f(x)

40、是嚴(yán)格凸函數(shù)當(dāng)且僅當(dāng)S上每一點(diǎn)的Hessian矩陣是正定的.,TP SHUAI,109,凸規(guī)劃,2. 凸集與凸函數(shù),,TP SHUAI,110,最優(yōu)化理論與算法,帥天平北京郵電大學(xué)數(shù)學(xué)系Email:tpshuai@gmail.com,Tel:62281308, Rm:主樓814§3， 線性規(guī)劃的基本性質(zhì),,TP SHUAI,111,第二章 線性規(guī)劃的基本性質(zhì),標(biāo)準(zhǔn)形式與圖解法基本性質(zhì),TP SHUAI,112,,我

41、每天要求一定量的兩種維生素，Vc和Vb。假設(shè)這些維生素可以分別從牛奶和雞蛋中得到。,需要確定每天喝奶和吃蛋的量，目標(biāo)以便以最低可能的花費(fèi)購買這些食物，而滿足最低限度的維生素需求量。,2.線性規(guī)劃- 例子-食譜問題,TP SHUAI,113,,令x表示要買的奶的量，y為要買的蛋的量。食譜問題可以寫成如下的數(shù)學(xué)形式：,Min 3x +2.5y s.t. 2x + 4y ? 40 3x + 2y ?

42、50 x, y ? 0.,極小化目標(biāo)函數(shù)可行區(qū)域（單純形）可行解,2.線性規(guī)劃- 例子-食譜問題,TP SHUAI,114,1標(biāo)準(zhǔn)形式,矩陣表示,其中A是m?n矩陣，c是n維行向量， b是m維列向量。,注：為計算需要，一般假設(shè)b?0.否則，可在方程兩端乘以(-1)即可化為非負(fù)。,2.線性規(guī)劃-形式,TP SHUAI,115,任意非標(biāo)準(zhǔn)形式均可化為標(biāo)準(zhǔn)形式，如,引入松弛變量xn+1， xn+2 ,… xn+m.,2.線性規(guī)劃-

43、形式,TP SHUAI,116,則有,2.線性規(guī)劃-形式,TP SHUAI,117,Min 3x +2.5y s.t. 2x + 4y ? 40 3x + 2y ? 50 x, y ? 0.,例如，考慮食譜問題,2. 圖解法 當(dāng)自變量個數(shù)少于3時,可以用較簡便的方法求解.,2.線性規(guī)劃-圖解法,TP SHUAI,118,可行區(qū)域的極點(diǎn)：(0, 25)(15, 2.5) 最優(yōu)解(2

44、0, 0),Min 3x +2.5y s.t. 2x + 4y ? 40 3x + 2y ? 50 x, y ? 0.,2.線性規(guī)劃-圖解法,TP SHUAI,119,3 基本性質(zhì)3.1 線性規(guī)劃的可行域,定理 2.2 線性規(guī)劃的可行域是凸集.,3.2 最優(yōu)極點(diǎn),觀察上例，最優(yōu)解在極點(diǎn)(15,2.5)達(dá)到，我們有如下事實(shí):線性規(guī)劃若存在最優(yōu)解,則最優(yōu)解一定可在某極點(diǎn)上達(dá)到.,2.線性規(guī)

45、劃-性質(zhì)1,TP SHUAI,120,考察線性規(guī)劃的標(biāo)準(zhǔn)形式(2. 2),根據(jù)表示定理，任意可行點(diǎn)x可表示為,2.線性規(guī)劃-性質(zhì)2,TP SHUAI,121,把x的表達(dá)式代入(2. 2),得等價的線性規(guī)劃:,2.線性規(guī)劃-性質(zhì)3,TP SHUAI,122,于是,問題簡化成,在(2.6)中令,顯然,當(dāng),時目標(biāo)函數(shù)取極小值.,2.線性規(guī)劃-性質(zhì)4,TP SHUAI,123,因此極點(diǎn)x(p)是問題(2.2)的最優(yōu)解.,即(2.5)和(2.8)

46、是(2.4)的最優(yōu)解,此時,2.線性規(guī)劃-性質(zhì)5,TP SHUAI,124,2,若(2. 2)存在有限最優(yōu)解,則目標(biāo)數(shù)的最優(yōu)值可在某極點(diǎn)達(dá)到.,定理2.3 設(shè)線性規(guī)劃(2.2)的可行域非空,則,2.線性規(guī)劃-性質(zhì)6,TP SHUAI,125,4最優(yōu)基本可行解,前面討論知道們最優(yōu)解可在極點(diǎn)達(dá)到，而極點(diǎn)是一幾何概念，下面從代數(shù)的角度來考慮。,不失一般性,設(shè)rank(A)=m,A=[B,N],B是m階可逆的.,2.線性規(guī)劃-性質(zhì)7,TP

47、SHUAI,126,于是,Ax=b可寫為,于是,2.線性規(guī)劃-性質(zhì)8,TP SHUAI,127,稱為方程組Ax=b的一個基本解.,定義2.6,為約束條件Ax=b,x?0的一個基本可行解. B稱為可行基矩陣,稱為一組可行基.,2.線性規(guī)劃-性質(zhì)9,TP SHUAI,128,且至少有一個分量為0,稱基本可行解是退化的.,2.線性規(guī)劃-性質(zhì)10,TP SHUAI,129,2.線性規(guī)劃-性質(zhì)11,TP SHUAI,130,2.線性規(guī)劃-性質(zhì)12

48、,TP SHUAI,131,2.線性規(guī)劃-性質(zhì)13,TP SHUAI,132,容易知道,基矩陣的個數(shù)是有限的,因此基本解從而基本可行解的個數(shù)也是有限的, 不超過,,2.線性規(guī)劃-性質(zhì)14,TP SHUAI,133,定理2. 4 令K={x| Ax=b,x?0},A是m×n矩陣,r(A)=m則K的極點(diǎn)集與Ax=b,x?0的基本可行解集合等價.,證明: (提綱)1)設(shè)x是K的極點(diǎn),則x是Ax=b,x?0的基本可行解.2)設(shè)x

49、是Ax=b,x?0的基本可行解,則x是K的極點(diǎn).,2.線性規(guī)劃-性質(zhì)15,TP SHUAI,134,1),先證極點(diǎn)x的正分量所對應(yīng)的A的列線性無關(guān).,2.線性規(guī)劃-性質(zhì)16,TP SHUAI,135,2.線性規(guī)劃-性質(zhì)17,TP SHUAI,136,2.線性規(guī)劃-性質(zhì)18,TP SHUAI,137,2)設(shè)x是Ax=b,x?0的基本可行解,記,2.線性規(guī)劃-性質(zhì)19,TP SHUAI,138,即,2.線性規(guī)劃-性質(zhì)20,TP SHUAI,

50、139,總結(jié),線性規(guī)劃存在最優(yōu)解,目標(biāo)函數(shù)的最優(yōu)值 一定能在某極點(diǎn)上達(dá)到.可行域K={x| Ax=b,x?0}的極點(diǎn)就是其基本可行解. 從而,求線性規(guī)劃的最優(yōu)解,只需要求出最優(yōu)基本可行解即可.,2.線性規(guī)劃-性質(zhì)21,TP SHUAI,140,5 基本可行解的存在問題,定理2. 5 若Ax=b,x?0有可行解,則一定存在基本可行解,其中A是秩為m的m?n矩陣.,2.線性規(guī)劃-性質(zhì)22,TP SHUAI,141,否則,我們通過如

51、下步驟構(gòu)造出一基本可行解,2.線性規(guī)劃-性質(zhì)23,TP SHUAI,142,2.線性規(guī)劃-性質(zhì)24,最優(yōu)化理論與算法,帥天平北京郵電大學(xué)數(shù)學(xué)系Email:tpshuai@gmail.com,Tel:62281308, Rm:主樓814§4， 線性規(guī)劃的單純形方法,,第三章 單純形方法,1，單純形方法原理2，兩階段法和大Mf法3，退化情形4，修正單純形方法,單純形法的基本思路 是有選擇地?。ǘ皇敲杜e所有的）基本

52、可行解，即是從可行域的一個頂點(diǎn)出發(fā)，沿著可行域的邊界移到另一個相鄰的頂點(diǎn)，要求新頂點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差，如此迭代，直至找到最優(yōu)解，或判定問題無界。,單純形法的基本過程,3.1線性規(guī)劃-單純形方法1,,,3.1線性規(guī)劃-單純形方法2,給定標(biāo)準(zhǔn)形式的LP,,,利用分塊矩陣,3.1線性規(guī)劃-單純形方法3,,于是目標(biāo)函數(shù),于是有,基本可行解x與基B關(guān)聯(lián);,3.線性規(guī)劃-單純形方法4,,于是我們有如下定理：,3.1.線性規(guī)劃-單純形方

53、法5,由上知,要減少費(fèi)用, 只有當(dāng) C?0時才可能，即,,,3.1線性規(guī)劃-單純形方法6,,令 y=x+?d, ?>0, 我們能降低費(fèi)用嗎？,3.1線性規(guī)劃-單純形方法7,,3.1線性規(guī)劃-單純形方法8,,3.1線性規(guī)劃-單純形方法9,,正確性如何？ 顯然按上述取法，是可以保證y≥0的。y還是基本可行解嗎？,3.1線性規(guī)劃-單純形方法10,,3.1線性規(guī)劃-單純形方法11,,單純形法,3.1線性規(guī)劃-單純形方法12,,Th

54、3.4(單純形法的收斂性）對于相容的非退化(每個基可行解都是非退的)LP問題， 那么經(jīng)過有限次迭代后，單純形法或者得到最優(yōu)的BFS(最優(yōu)可行基B）或有一個方向d:且最優(yōu)的費(fèi)用為-∞.,3.1線性規(guī)劃-單純形方法13,,例1,3.1線性規(guī)劃-單純形方法14,,3.1線性規(guī)劃-單純形方法15,,3.1線性規(guī)劃-單純形方法16,,3.1線性規(guī)劃-單純形方法17,,3.1線性規(guī)劃-單純形方法18,,3.1線性規(guī)劃-單純形方法19,新的基為

55、B=(A1, A3, A4, A7),,3.1線性規(guī)劃-單純形方法20,,3.1線性規(guī)劃-單純形方法21,新的基為B=(A3, A4, A5, A7),,3.1線性規(guī)劃-單純形方法22,,,利用分塊矩陣,表格形式的單純形方法,3.1線性規(guī)劃-單純形方法23,,,3.1線性規(guī)劃-單純形方法24,,3.1線性規(guī)劃-單純形方法25,進(jìn)基變量,離基變量,旋轉(zhuǎn)元,右端向量,返回,,,單純形表,例2： 求解線性規(guī)劃問題,化成標(biāo)準(zhǔn)化形式,3.1線性規(guī)

56、劃-單純形方法26,,,,,,,寫出單純形表,25/1,36/2,,0,-3,-2,0,-2,-72,0,1/2,0,1,-1/2,7/0.5,1,1/2,1,0,1/2,18/0.5,x2,7,18,1,1/2,1/2,x5,,x6離基，,x2進(jìn)基，,x5離基，,x1進(jìn)基，,,,3.1線性規(guī)劃-單純形方法27,0,-4,-2,-2,-1,-86,0,1,0,2,-1,1,0,1,-1,1,14,11,0,0,得到最優(yōu)解，最優(yōu)解為：,（

57、x1，x2，x3，x4，x5，x6）=（14,11,0,0,0,0）min z’=-86， max z=86,1,,3.1線性規(guī)劃-單純形方法28,,,例3： 求解線性規(guī)劃問題,3.1線性規(guī)劃-單純形方法29,,,3.1線性規(guī)劃-單純形方法30,,,x3進(jìn)基，x6離基,3.1單純形方法31,,,,初始單純型表,最優(yōu)單純型表,,,,,,,,3.2 兩階段法&大M法1,單純形法三要素： 初始基本可行解，解的迭代，最

58、優(yōu)性檢驗(yàn)后兩個已解決,現(xiàn)考慮如何獲得一個初始基可行解.,（一）兩階段法,設(shè)標(biāo)準(zhǔn)LP為,3.2 兩階段法&大M法2,若系數(shù)矩陣中有一個單位矩陣，則容易得到初始基可行解.所以我們希望幸運(yùn)的碰到這種矩陣.沒有的話，硬性加一個？,3.2 兩階段法&大M法3,問題是如何由(3.2.3)的初始可行解獲得原來LP的一個初始可行解？為此，考慮如下輔助LP(第一階段),如果原問題有可行解，則輔助問題的最優(yōu)值為0，反之亦然。,3.2

59、兩階段法&大M法4,3.2 兩階段法&大M法5,利用單純形法求得一個最優(yōu)可行解.這個解將會給我們帶來什么？,3.2 兩階段法&大M法6,于是我們獲得一個初始基可行解,從而可以以此基可行解出發(fā)利用單純形法求出最優(yōu)解.,第一階段：不考慮原LP問題是否有基可行解，添加人工變量，構(gòu)造僅含人工變量的目標(biāo)函數(shù)，得輔助規(guī)劃(3.2.4),單純型法求解上述模型，若有目標(biāo)函數(shù)=0，說明原問題存在初始基本可行解，轉(zhuǎn)入第二階段。否則，

60、原問題無可行解，計算停止。,第二階段：將第一階段計算得到的最終表，除去人工變量，從該初始基本可行解開始，用單純形法求原問題的最優(yōu)解或判定原問題無界。,3.2 兩階段法&大M法7,寫成標(biāo)準(zhǔn)化形式,例1 求解,3.2 兩階段法&大M法8,第1 階段,首先引入人工變量，構(gòu)造輔助規(guī)劃問題,, 其對應(yīng)的單純形表為,3.2 兩階段法&大M法9,,,RHS,3.2 兩階段法&大M法10,,,RHS,RHS,,RHS

61、,第一階段結(jié)束，得到輔助問題的一個最優(yōu)解,同時得到原問題的一個初始基本可行解,3.2 兩階段法&大M法11,,去掉人工變量對應(yīng)的行、列，得到原問題的初始典式，,直接開始第二階段運(yùn)算,第 2 階 段,RHS,,,RHS,z,原問題的最優(yōu)解,其最優(yōu)值為,3.2 兩階段法&大M法12,例2求解,3.2 兩階段法&大M法13,解：引進(jìn)人工變量進(jìn)行第一階段,,,3.2 兩階段法&大M法14,單純形法求解：,3

62、.2 兩階段法&大M法15,0 1 1 -1 0 1 0 4,0 0 2 -3 0 0 1 4,0 -1 1 -2 1 0 0 0,0 0 4 -6 0 0 0 8,,

63、3.2 兩階段法&大M法16,0 2 0 1 -2 0 1 4,0 2 0 1 -1 1 0 4,0 4 0 2 -4 0 0 8,,3,3.2 兩階段法&大M法17,0 1 0 ½

64、 - ½ ½ 0 2,0 0 0 0 -1 -1 1 0,0 0 1 -3/2 ½ ½ 0 2,0 0 0 0 -2 -2 0 8,2,3.2 兩階段法&大M法18,第二階段：,,,3.2

65、兩階段法&大M法19,第二階段初始單純形表：,3.2 兩階段法&大M法20,前面所說的兩階段法分成兩步走。能不能把這兩步合并？如何合并？,（二）大M法,設(shè)原問題為,引入m個人工變量,3.2 兩階段法&大M法21,現(xiàn)在關(guān)鍵是如何選取目標(biāo)函數(shù)，因要包含原問題,所以必須包含原目標(biāo)。聯(lián)系到兩階段法，我們要強(qiáng)迫人工變量取值為0，于是加上一個懲罰因子，因?yàn)槭菢O小化，所以希望這個懲罰因子越大越好??！,在目標(biāo)函數(shù)中增加,3

66、.2 兩階段法&大M法22,可行嗎？,直觀上，因M為足夠大的正數(shù)，新問題最優(yōu)解對應(yīng)的人工變量取值應(yīng)滿足 ，（除非原問題不可行）,從而新LP問題的最優(yōu)解對應(yīng)于原問題的（基本）可行解，,容易知道此時兩個問題的目標(biāo)函數(shù)值滿足,3.2 兩階段法&大M法23,因此只需求解輔助問題就可求得原問題的最優(yōu)解。,且兩個規(guī)劃目標(biāo)值相等，故原問題的最優(yōu)解,綜合,,3.2 兩階段法&大M法24,例3 求解

67、如下LP,解：,,,,,,得到最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：max=112/3,,,,,3.2 兩階段法&大M法25,,3.2.3 單個人工變量技巧1,前述方法引入多個人工變量，能否只引入一個變量而達(dá)到目標(biāo)？,考慮LP,3.2.3 單個人工變量技巧2,3.2.3 單個人工變量技巧3,例子：,3.2.3 單個人工變量技巧4,利用表格形式求解一個(3.2.17)的BFS：,3.2.3 單個人工變量

68、技巧5,于是得到(3.2.17)的一個BFS，下面再用兩階段(或大M)法求解之.,3.2.3 單個人工變量技巧6,,,,3.2.3 單個人工變量技巧7,于是得到進(jìn)行第二階段時的初始表。,由上知道這是最優(yōu)單純形表。,3.3 退化情形1,單純形法收斂定理要求BFS非退化，這個限制可以去掉嗎？試看下例。,例(3.3.1)：用單純形法求解下面的LP,注意到該LP有一個明顯的BFS x=(0，0，1，0，0，0，

69、0),3.3 退化情形2,其單純形法迭代過程如下：,,,3.3 退化情形3,,,3.3 退化情形4,,,3.3 退化情形5,,3.3 退化情形6,前例表明算法會無限循環(huán)下去，能否找到一種辦法避免出現(xiàn)這種情況？,(a)攝動法,3.3 退化情形7,下面討論這種辦法的可行性。,對右端向量b 作如下攝動。令,于是得（3.3.1）的攝動問題：,3.3 退化情形8,下面我們將證明當(dāng)適當(dāng)對取值時，LP(3.3.3)非退化，且可以通過求解LP(3.3.