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

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

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

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

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

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

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

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

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

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

10、un f)的描述方法.（1）自然語(yǔ)言（2）流程圖（3）程序設(shè)計(jì)(chn x sh j)語(yǔ)言第29頁(yè)/共72頁(yè)第三十頁(yè)，共72頁(yè)。例. 求正整數(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頁(yè)/共72頁(yè)第三十一頁(yè)，共72頁(yè)。解二. 開(kāi) 始輸入(shr)m、nr=m%nr=0?mn，nr輸出(shch)n是否第31頁(yè)/共72頁(yè)第三十二頁(yè)，共72頁(yè)。解三. Euclid(int m, int n) int r;

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

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

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

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

15、頁(yè)，共72頁(yè)。47第46頁(yè)/共72頁(yè)第四十七頁(yè)，共72頁(yè)。48第47頁(yè)/共72頁(yè)第四十八頁(yè)，共72頁(yè)。例例一一兩兩個(gè)個(gè)矩矩陣陣相相乘乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲(chǔ)矩陣以二維數(shù)組存儲(chǔ)矩陣(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)操作時(shí)間(shjin)復(fù)雜度: O(n3)第48頁(yè)/共72頁(yè)第四十

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

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

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

19、題問(wèn)題(wnt)(wnt)，當(dāng)，當(dāng)S=(1,2,3,4)S=(1,2,3,4)時(shí)，時(shí)，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). 類(lèi)似可定義類(lèi)似可定義k-opt(kk-opt(k2)2)第55頁(yè)/共72頁(yè)第五十六頁(yè)，共72頁(yè)。局部局部(jb)(jb)最優(yōu)與全局最優(yōu)最優(yōu)與全局最優(yōu) 若若s s* *滿(mǎn)足滿(mǎn)足(mnz)(mnz) f(s f(s* *) )( ()f(s),)f(s),

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

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