運籌學(xué)搜索論課件1

1、教案要點文 件 名：051OR02.PPT；搜索論.XLS上節(jié)習(xí)題：051ORL01.PPT授課時間：第二講授課內(nèi)容：搜索論（一）預(yù)備知識：解析幾何、微積分難 點：迭代公式、使用條件、比較重 點：幾種找零點的方法：秦九韶法、對分法、切線法、弦線法、聯(lián)合法、其它方法，算法及Excel 實現(xiàn)。下節(jié)預(yù)習(xí)：找極值點的方法網(wǎng)站、參考書）。復(fù)習(xí)可行解、基可行解，基及非基變量。搜索論(Search Theory)紹興文理學(xué)院工學(xué)院計算機(jī)系搜索論何謂搜索論搜索論的應(yīng)用搜索策略找零點找極值點0.618法瞎子爬山法后記何謂“搜索論”搜索論是順應(yīng)第二次世界大戰(zhàn)中戰(zhàn)爭的需要而出現(xiàn)的運籌學(xué)分支。主要研究在資源和探測手段

2、受到限制的情況下，設(shè)計尋找某種目標(biāo)的最優(yōu)方案，及有關(guān)的理論和方法。在第二次世界大戰(zhàn)中，同盟國的空軍和海軍針對軸心國的潛艇活動，研究如何甄別、艦隊運輸和兵力如何部署等的過程中產(chǎn)生的。戰(zhàn)后搜索論在實際應(yīng)用中也取得了不少成效，例如二十世紀(jì)六十年代，美國尋找在大西洋失蹤的核潛艇“打谷者號”和“蝎子號”，以及在地中海尋找丟失的氫彈，都是成功應(yīng)用搜索論的范例。搜索論的應(yīng)用美軍尋找在大西洋失蹤的兩艘核潛艇美軍尋找丟失的氫彈找油田找故障點找零點找極值點找油田的應(yīng)用地質(zhì)結(jié)構(gòu)（李四光）打探井人造地震法無功而返油水有油是水搜索故障點找漏氣點、斷路點編程中DEBUG找暗堡、防空陣地雷達(dá)、聲納醫(yī)生對病人診斷文字校對讓計

3、算機(jī)來算找函數(shù)的零點預(yù)備知識秦九韶法對分法切線法弦線法聯(lián)合法其它方法實際例子預(yù)備知識y=f(x)是閉區(qū)間a,b上的連續(xù)函數(shù),在區(qū)間兩端異號即：f(a)f(b)0, 則 有零點。在開區(qū)間內(nèi)必a(a,f(a)b(b,f(b)會在端點嗎？不會！零點唯一嗎？未必！零點有奇數(shù)個嗎？未必！函數(shù)與導(dǎo)數(shù)連續(xù)函數(shù)在閉區(qū)間兩端異號則 必有零點。一個函數(shù)在它的導(dǎo)數(shù)不變號的區(qū)間內(nèi) 。在開區(qū)間內(nèi)函數(shù)y=f(x)在(x0,f(x0)處的切線斜率是：嚴(yán)格單調(diào)函數(shù)y=f(x)在(x0,f(x0)處的切線方程是：f(x0)y=f(x0)+ ? (x-x0)f(x0)函數(shù)與導(dǎo)數(shù)連續(xù)函數(shù)在閉區(qū)間兩端異號則 必有零點。一個函數(shù)在它的

4、導(dǎo)數(shù)不變號的區(qū)間內(nèi) 。在開區(qū)間內(nèi)嚴(yán)格單調(diào)兩點(x1,y1),(x2,y2)連線方程是：函數(shù)y=f(x)在(x0,f(x0)處的切線方程是：找函數(shù)的零點算法一:秦九韶-霍納法：區(qū)間a,b上連續(xù)函數(shù)f(x)若兩端函數(shù)值f(a)f(b)0 (異號),則其內(nèi)至少有一個零點。區(qū)間十等分。如3,4中有根，查3.1,3.2,3.9處的函數(shù)值，若有一點為0或絕對值足夠小則找到，否則這十個小區(qū)間中必有一個兩端的函數(shù)值是異號的。在此小區(qū)間中繼續(xù)，即把它再十等分。直到有一個分點的函數(shù)值為0或絕對值足夠小，或小區(qū)間的長度已足夠短的時取中點，結(jié)束。找函數(shù)的零點算法二:對分法:若連續(xù)函數(shù)f(x)在區(qū)間a,b兩端函數(shù)值f(

5、a)f(b)0(異號),則其內(nèi)至少有一個零點。區(qū)間對分S1:令x(a+b)/2,若b-a,轉(zhuǎn)S4,否則轉(zhuǎn)S2;S2:若f(x)=0,轉(zhuǎn)S4 ,否則轉(zhuǎn)S3;S3:若f(x)f(a)0,令bx,否則令ax,轉(zhuǎn)S1; S4:輸出x,結(jié)束。算法三：切線法函數(shù)y=f(x)在x=a處的切線斜率：a(a,f(a)c=a-f(a)/f(a)f (a)切線過點(a,f(a),其方程是：函數(shù)y=f(x)在x=a處的切線與x軸的交點的縱坐標(biāo):y-f(a)=f (a)(x-a),橫坐標(biāo):0y=f(x)這個c往往比a更靠近零點.算法三：切線法選一端引切線，與x軸的交點會更“好”些！算法三：切線法選一端a引切線，與x軸的

6、交點的橫坐標(biāo)c:a(a,f(a)c=a-f(a)/f(a)以c為新的a繼續(xù)做，直到f(a)足夠靠近0了為止。算法三：切線法S1:若f(a)f”(a)0,則ab,轉(zhuǎn)S2;S2:若|f(a)|0,f(1.8)=0.088,應(yīng)從b起,但f(a)很接近0,從a起。算法四：弦線法函數(shù)y=f(x)在區(qū)間a,b的兩端異號，連接點(a,f(a),(b,f(b)的線段(弦)：abc弦與x軸交于點(c,0)：c點為新的b繼續(xù)。算法四：弦線法畫連接點(a,f(a),(b,f(b)的線段(弦),與x軸交于點(c,0);ab若f(c)與f(a)異號,以a,c為新的區(qū)間繼續(xù)做,。c算法四：弦線法選一端引弦線,與x軸的交點

7、替換另一端！算法四：弦線法缺點：有一頭停滯不進(jìn)。abcf(b)f”(b)0,選b點：算法五：聯(lián)合法如圖同時用弦線法從左邊，用切線法從右邊，聯(lián)合“夾攻”。aba1b1算法五：聯(lián)合法如f(a)f(b)0,從b出發(fā)。具體算法：S1:若b-a,令x(a+b)/2,轉(zhuǎn)S3,否則轉(zhuǎn)S2;S2:令ab-f(b)(b-a)/(f(b)-f(a), bb-f(b)/f(b),轉(zhuǎn)S1;S3:輸出x,結(jié)束。找函數(shù)的零點找函數(shù)的零點前面我們介紹了五種算法：秦九韶-霍納法、對分法、切線法、弦線法和聯(lián)合法。其它還有拋物線法、林士諤-趙訪熊法(劈因子法)、下降法等。進(jìn)一步的研究可以參看計算方法方面的書。在Excel中怎么做

8、呢？用上述五種算法、用單變量求解、規(guī)劃求解等。思考討論一下有多少種方法求用計算器、查表、手算用計算機(jī)：附件計算器OfficeExcel用計算機(jī)語言編程求y=x2-7在2,3中的零點。求7的平方根計算器求用計算機(jī)：附件計算器用Excel的解法利用函數(shù)MAX和MIN可以找到一批單元格中最大(小)者。利用“規(guī)劃求解”也可解決大量求極值的問題。求7的平方根用計算機(jī)：OfficeExcel用公式：=SQRT(7)求7的平方根用計算機(jī)：OfficeExcel用單變量求解、規(guī)劃求解求7的平方根用計算機(jī)：OfficeExcel秦九韶法對分法作圖法逼近求7的平方根用切線法求y=x2-7在2,3中的零點即 。3268/38/31/916/3127/48127/481