最優(yōu)化理論與方法實用教案VIP

1、會計學(xué)1最優(yōu)化理論最優(yōu)化理論(lln)與方法與方法第一頁，共72頁。2第1頁/共72頁第二頁，共72頁。3第2頁/共72頁第三頁，共72頁。4第3頁/共72頁第四頁，共72頁。5第4頁/共72頁第五頁，共72頁。6第5頁/共72頁第六頁，共72頁。7決策變量有限點集約束函數(shù)目標(biāo)函數(shù), . , 0)(. . )( minDxxgtsxf第6頁/共72頁第七頁，共72頁。8.| )(min)(,:,0)(,|:),(FxxfxfFxxFxfxgDxxFDfFD最優(yōu)解，如果可行解（點）目標(biāo)函數(shù)有限點集可行域決策變量定義域第7頁/共72頁第八頁，共72頁。9裝包？問題：如何以最大價值件物品單位價值，第

2、件物品單位體積，第背包容積., 1:., 1:niicniiabii第8頁/共72頁第九頁，共72頁。10.1 ,0i0i 1(1.3) ., 1,1 ,0 (1.2) ,as.t.(1.1) maxn1ii1iniiiniiDxnixbxxc物品，不裝第物品裝第，其中決策變量包容量限制總價值數(shù)學(xué)模型：第9頁/共72頁第十頁，共72頁。11第10頁/共72頁第十一頁，共72頁。12ij1ij1min (1.4) s.t.1.1,2, , (1.5) i 1.1,2, , ijijijnjnid xxinxjn數(shù)學(xué)模型：總路長只從城市 出來一次, (1.6) 1,21,1,2, (1.7) 0,

3、1 , ,1,2, ,. (1.8) :ij , s :s 1, iji jsijijijjxssnsnxi jn ijdijx只走入城市 一次在任意城市子集中不形成回路決策變量其中城市 與城市 之間的距離集合 中元素的個數(shù)，走城市 和城市0.:,:,ijjiijjiijTSPddi jTSPddi j之間的路徑，不走城市 和城市 之間的路徑對稱距離非對稱距離第11頁/共72頁第十二頁，共72頁。1312 ,.na aa第12頁/共72頁第十三頁，共72頁。1411min. .1,1, 2, 1,1, 2, 0,1 ,1, 2,;1, 2, B :1, 0 .BibbniibiibibBs t

4、xina xbBxin bBibxib數(shù) 學(xué) 模 型 ：其 中裝 下 全 部 物 品 需 要 的 箱 子 ，第 物 品 裝 在 第個 箱 子 ， 第 物 品 不 裝 在 第個 箱 子第13頁/共72頁第十四頁，共72頁。15第14頁/共72頁第十五頁，共72頁。16第15頁/共72頁第十六頁，共72頁。17第16頁/共72頁第十七頁，共72頁。一個有窮規(guī)則的有序集合(jh)稱為一個算法。1.定義(dngy). 2.算法(sun f)的特征.n可行性：執(zhí)行每條指令的時間也有限。第17頁/共72頁第十八頁，共72頁。1 1有窮性有窮性 對于任意一組合法輸入值，對于任意一組合法輸入值，在執(zhí)行有窮步驟

5、之后在執(zhí)行有窮步驟之后(zhhu)(zhhu)一定能結(jié)束一定能結(jié)束，即：，即：算法中的每個步驟都能在有限時間內(nèi)完成算法中的每個步驟都能在有限時間內(nèi)完成；第18頁/共72頁第十九頁，共72頁。 2 2確定性確定性 對于對于(duy)(duy)每種情況下所每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；都只有一條執(zhí)行路徑；第19頁/共72頁第二十頁，共72頁。3 3可行性可行性 算法中的所有算法中的所

6、有(suyu)(suyu)操作都操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之；操作運算有限次實現(xiàn)之；第20頁/共72頁第二十一頁，共72頁。4 4有輸入有輸入 作為算法加工對象的量值，通常作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要體現(xiàn)為算法中的一組變量。有些輸入量需要(xyo)(xyo)在算法執(zhí)行過程中輸入，而有的算法在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之表面上可以沒有輸入，實際上已被嵌入算法之中；中；第21頁/共72頁第二十二頁，共72頁。 5有輸出 它是一組與“輸入”與確定關(guān)

7、系的量值，是算法進行信息加工后得到的結(jié)果(ji gu)，這種確定關(guān)系即為算法的功能。第22頁/共72頁第二十三頁，共72頁。二、算法二、算法(sun f)(sun f)設(shè)計的原則設(shè)計的原則設(shè)計算法時，通常應(yīng)考慮達到以下(yxi)目標(biāo)：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲量需求高效率與低存儲量需求(xqi)第23頁/共72頁第二十四頁，共72頁。1 1正確性正確性首先，算法首先，算法(sun f)(sun f)應(yīng)當(dāng)滿足以特定的應(yīng)當(dāng)滿足以特定的“規(guī)規(guī)格說明格說明”方式給出的需求。方式給出的需求。 其次(qc)，對算法是否“正確”的理解有四個層次：a a程序程序(chn

8、gx)(chngx)中不含語法錯誤；中不含語法錯誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；第24頁/共72頁第二十五頁，共72頁。 c c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)С绦驅(qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y有刁難(dionn)(dionn)性的幾組輸入數(shù)據(jù)能夠得性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；出滿足要求的結(jié)果；通常以第 c 層意義的正確性作為衡量一個(y )算法是否合格的標(biāo)準(zhǔn)。 d程序?qū)τ?duy)一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果；第25頁/共72頁第二十六頁，共72頁。2. . 可讀性可讀性 算法主要是為了人的閱讀與交流，其次才是為計算機執(zhí)行。因此算法應(yīng)該易

9、于人的理解；另一方面，晦澀(hus)難讀的程序易于隱藏較多錯誤而難以調(diào)試；第26頁/共72頁第二十七頁，共72頁。3健壯性健壯性 當(dāng)輸入的數(shù)據(jù)非法時，算法(sun f)應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理。第27頁/共72頁第二十八頁，共72頁。4高效率與低存儲量需求高效率與低存儲量需求(xqi) 通常，效率(xio l)指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關(guān)。第28頁/共72頁第二十九頁，共72頁。算法(s

10、un f)的描述方法.（1）自然語言（2）流程圖（3）程序設(shè)計(chn x sh j)語言第29頁/共72頁第三十頁，共72頁。例. 求正整數(shù)m、n的最大公因數(shù)。解一. （1）求余數(shù)(ysh)：用m除以n，得余數(shù)(ysh)r(0rn)。（2） 判斷余數(shù)：若余數(shù)r=0，輸出n，結(jié)束(jish)。 否則，轉(zhuǎn)（3）。（3）更新(gngxn)被除數(shù)和除數(shù)：mn，nr，轉(zhuǎn)(1)。第30頁/共72頁第三十一頁，共72頁。解二. 開 始輸入(shr)m、nr=m%nr=0?mn，nr輸出(shch)n是否第31頁/共72頁第三十二頁，共72頁。解三. Euclid(int m, int n) int r;

11、while(n!=0) r=m%n; m=n; n=r; printf(“%d”, m) 第32頁/共72頁第三十三頁，共72頁。34第33頁/共72頁第三十四頁，共72頁。35城市數(shù)2425262728293031計算時間1sec24sec10min4.3hour4.9day136.5day10.8year325year隨城市(chngsh)增多，計算時間增加很快。到31個城市(chngsh)時，要計算325年。第34頁/共72頁第三十五頁，共72頁。36描述算法的好壞計算復(fù)雜性討論計算時間與問題規(guī)模之間的關(guān)系以目前二進制計算機中的存儲和計算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評估(pn )算法

12、性能的基礎(chǔ)。第35頁/共72頁第三十六頁，共72頁。37第36頁/共72頁第三十七頁，共72頁。38第37頁/共72頁第三十八頁，共72頁。392( )( )log (| 1)2xl xl xx記 的輸入規(guī)模（編碼長度）為，則其中2是考慮了1個符號位和1個數(shù)據(jù)分隔位。第38頁/共72頁第三十九頁，共72頁。如何估算如何估算( sun)( sun) 算法的時間復(fù)雜度？算法的時間復(fù)雜度？第39頁/共72頁第四十頁，共72頁。算法算法(sun f) = (sun f) = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 算法的執(zhí)行時間算法的執(zhí)行時間 =元操作元操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)元操作元操作

13、(i)(i)的執(zhí)行時間的執(zhí)行時間第40頁/共72頁第四十一頁，共72頁。 從算法中選取一種對于所研究(ynji)的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運行時間的衡量準(zhǔn)則。第41頁/共72頁第四十二頁，共72頁。4321, , (1)!(1)!;(1)! (1)!nniinnnnnnnn城市數(shù)第一城市為始終點，計算一條路徑（,1） 長度的基本運算為兩兩城市間距離的 個數(shù)求和,共有條路徑,求和運算次數(shù)為：枚舉所有路徑進行次比較可得最優(yōu)路徑,基本計算總次數(shù)為總計算量:計算計算(j sun)量的統(tǒng)量的統(tǒng)計：計：第42頁/共72頁第四十三頁，共72頁。4422,

14、(1)( log12)log12ijijdKLn nKn設(shè) 對有則（）（）n實例的輸入長度是n的多項式函數(shù)(hnsh)n枚舉法的基本計算量是n的階乘函數(shù)(hnsh)，n 隨n的增加，比指數(shù)函數(shù)(hnsh)增加得還快.第43頁/共72頁第四十四頁，共72頁。45AAA, ( )AC (I)( ) ( ( ) ( )( ( ( )( )Il Ig xC (I)g l ICIO g l Ig x 實例實例規(guī)模：，算法基本計算總次數(shù)：存在函數(shù)和一個常數(shù) ，使得對于該問題的任意實例都滿足 （）則二者關(guān)系表示為：的性質(zhì)決定了算法的性能。第44頁/共72頁第四十五頁，共72頁。46第45頁/共72頁第四十六

15、頁，共72頁。47第46頁/共72頁第四十七頁，共72頁。48第47頁/共72頁第四十八頁，共72頁。例例一一兩兩個個矩矩陣陣相相乘乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲矩陣以二維數(shù)組存儲矩陣(j zhn)元素，元素，c 為為 a 和和 b 的乘積的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法(chngf)操作時間(shjin)復(fù)雜度: O(n3)第48頁/共72頁第四十

16、九頁，共72頁。 常用的時間(shjin)復(fù)雜度有如下的關(guān)系：O(1)=O(log2n)=O(n)=O(nlog2n)=O(n2)=O(2n) =O(n!)第49頁/共72頁第五十頁，共72頁。四、算法四、算法(sun f)(sun f)的存儲空間需求的存儲空間需求算法的空間(kngjin)復(fù)雜度定義為: 表示隨著問題規(guī)模 n 的增大，算法運行(ynxng)所需存儲量的增長率與 g(n) 的增長率相同。S(n) = O(g(n)第50頁/共72頁第五十一頁，共72頁。算法算法(sun f)的存儲量包括的存儲量包括:1輸入數(shù)據(jù)(shj)所占空間2程序本身(bnshn)所占空間；3輔助變量輔助變量

17、所占空間。第51頁/共72頁第五十二頁，共72頁。53第52頁/共72頁第五十三頁，共72頁。鄰域鄰域(ln y)(ln y)概念概念 對于組合優(yōu)化問題對于組合優(yōu)化問題(D,F,f),D(D,F,f),D上的一個上的一個映射：映射： N:S N:SD D N(S) N(S)2D2D稱為一個鄰域稱為一個鄰域(ln y)(ln y)映射，其中映射，其中2D2D表示表示D D的所有子集構(gòu)成的集合，的所有子集構(gòu)成的集合，N(S)N(S)稱為稱為S S的鄰的鄰域域(ln y)(ln y)。 鄰域鄰域(ln y)(ln y)的構(gòu)造依賴于問題決策的構(gòu)造依賴于問題決策變量的表示，鄰域變量的表示，鄰域(ln y

18、)(ln y)的結(jié)構(gòu)在現(xiàn)代的結(jié)構(gòu)在現(xiàn)代化優(yōu)化算法中起重要作用?；瘍?yōu)化算法中起重要作用。第53頁/共72頁第五十四頁，共72頁。鄰域概念鄰域概念(ginin)(ginin)例如例如TSPTSP問題解的另一種問題解的另一種(y zhn)(y zhn)表示法為表示法為D=S=(i1,i2,in)D=S=(i1,i2,in)是是1,2,n1,2,n的一個排列的一個排列 可以定義它的鄰域映射為可以定義它的鄰域映射為2-opt2-opt，即，即S S中的兩個元中的兩個元素對換。素對換。第54頁/共72頁第五十五頁，共72頁。鄰域鄰域(ln y)(ln y)概念概念 如如4 4個城市的個城市的TSPTSP問

19、題問題(wnt)(wnt)，當(dāng)，當(dāng)S=(1,2,3,4)S=(1,2,3,4)時，時，N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3).,2,4),(1,4,3,2),(1,2,4,3). 類似可定義類似可定義k-opt(kk-opt(k2)2)第55頁/共72頁第五十六頁，共72頁。局部局部(jb)(jb)最優(yōu)與全局最優(yōu)最優(yōu)與全局最優(yōu) 若若s s* *滿足滿足(mnz)(mnz) f(s f(s* *) )( ()f(s),)f(s),

20、其中其中s sN(sN(s* *) )F,F,則稱則稱s s* *為為f f在在F F上的局部上的局部(local)(local)最?。ㄗ畲螅┙狻Ｗ钚。ㄗ畲螅┙?。 若若s s* *滿足滿足(mnz)(mnz) f(s f(s* *) )( ()f(s),)f(s),其中其中s sF,F,則稱則稱s s* *為為f f在在F F上的全局上的全局(global)(global)最小（最大）解。最?。ㄗ畲螅┙?。第56頁/共72頁第五十七頁，共72頁。58第57頁/共72頁第五十八頁，共72頁。近似算法定義近似算法定義 記問題記問題A A的任何一個實例的任何一個實例I I的最優(yōu)解和啟發(fā)式的最優(yōu)解和啟發(fā)

21、式算法算法H H解的目標(biāo)值分別為解的目標(biāo)值分別為z zoptopt(I)(I)和和z zH H(I),(I),若對某若對某個正數(shù)個正數(shù)0 0，有，有 | |z zH H(I)-z(I)-zoptopt(I)|(I)| | |z zoptopt(I)|(I)|， I I A A則稱則稱H H是是A A的的 近似算法。近似算法。1.4 啟發(fā)式算法(sun f)第58頁/共72頁第五十九頁，共72頁。60第59頁/共72頁第六十頁，共72頁。61第60頁/共72頁第六十一頁，共72頁。 背包問題的貪婪算法背包問題的貪婪算法1 1）將物品以）將物品以ci/aici/ai（單位體積的價值）由大到小的順（單位體積的價值）由大到小的順序排列序排列(pili)(pili)，不妨把排列，不妨把排列(pili)(pili)記為記為1,2,n,k:=1;1,2,n,k:=1;2 2）若）若