國(guó)家集訓(xùn)隊(duì)2004論文集 金愷

《國(guó)家集訓(xùn)隊(duì)2004論文集 金愷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、極限法——解決幾何最優(yōu)化問(wèn)題的捷徑長(zhǎng)郡中學(xué)金愷概述在平面幾何問(wèn)題中我們經(jīng)常會(huì)遇到一些求極值的問(wèn)題。在這些問(wèn)題中，自變量和目標(biāo)函數(shù)可能涉及到坐標(biāo)、斜率、角度、周長(zhǎng)、面積等等一些復(fù)雜的量，而且自變量往往還有復(fù)雜的約束條件，所以直接用求函數(shù)最值的方法無(wú)從下手或者極其復(fù)雜?；療o(wú)限為有限在這些問(wèn)題中，自變量往往有無(wú)窮多種取值方案（比如點(diǎn)在平面上)，無(wú)法枚舉每種取值方案來(lái)求最值。怎么辦？通過(guò)極限法，可以證明：自變量取非特殊情況時(shí)函數(shù)不可能得到最優(yōu)解，因?yàn)榘炎宰兞课⒄{(diào)一個(gè)無(wú)窮小量能夠使得目標(biāo)函數(shù)變得更優(yōu)。從而只剩下有限個(gè)特殊情況需要考慮。枚舉所有的特殊情

2、況，就可找到最優(yōu)解了?；邢逓樯倭吭诹硪恍﹩?wèn)題中，本就可以通過(guò)枚舉有限個(gè)特殊情況求出最優(yōu)解，但是枚舉的量很大，時(shí)間復(fù)雜度較高；嘗試通過(guò)極限法減少需要枚舉的情況數(shù)，降低時(shí)間復(fù)雜度。極限法的本質(zhì)就是對(duì)目標(biāo)函數(shù)求導(dǎo)：如果自變量不取定義域的邊界（取邊界時(shí)對(duì)應(yīng)某些特殊情況）并且這一點(diǎn)的導(dǎo)數(shù)不為0（導(dǎo)數(shù)為0時(shí)對(duì)應(yīng)另一些特殊情況），則目標(biāo)函數(shù)不可能為最優(yōu)值。例題一、巧克力問(wèn)題描述：兩個(gè)小孩一起買(mǎi)了一塊凸N邊形巧克力，想一刀把它割成兩半,兩半的面積必須相等。找出用以分割巧克力的分割線的最短長(zhǎng)度。數(shù)學(xué)模型：已知量：N個(gè)點(diǎn)(Xi,Yi),1≤i≤N，構(gòu)成一個(gè)凸

3、包P；求：一條分割線L；約束條件：P在L兩側(cè)的面積相等；目標(biāo)函數(shù)：L的長(zhǎng)度；要求使目標(biāo)函數(shù)值最小的一條L。問(wèn)題分析設(shè)L的兩個(gè)端點(diǎn)為A、B；L可能過(guò)P的頂點(diǎn)也可能不過(guò)，分開(kāi)解決這兩種情況：1、A在P的頂點(diǎn)上（B在P的頂點(diǎn)上類(lèi)似）1)枚舉P中的一個(gè)頂點(diǎn)作為A；2)由分割線兩側(cè)面積相等確定B所在的邊；3)算出B的具體位置。ASLSRBL2、A、B都在P的邊{不含端點(diǎn)}上：枚舉A、B所在的兩條邊a、b設(shè)這兩條邊相交于C，∠C=γBCγβαLA設(shè)∠CAB=α，∠CBA=β。下面將證明α≠β時(shí)（即非特殊情況下），L不是最優(yōu)的分割線。不妨設(shè)β>αab

4、先把L繞B點(diǎn)往交點(diǎn)C方向旋轉(zhuǎn)一個(gè)微量θ；再平移一個(gè)微量到L'使P在L'兩邊的面積相等；L'仍與a、b相交，交點(diǎn)為A'、B'；則∠CA'B'=α+θ，∠CB'A'=β-θ；A'BCα+θγβαθθβ-θLAB'L'θL和L'都是分割線，所以ab∴L2>L'2，L'1由正弦定理：AC·BC=A'C·B'C結(jié)論如果a、b平行即C在無(wú)窮遠(yuǎn)處，也有相同結(jié)論若L是最短的分割線但不經(jīng)過(guò)P的頂點(diǎn)，那么L與P的兩個(gè)夾角必然相等。枚舉a、b后，確定L的斜率，根據(jù)P在L兩邊面積相等，可算出L的位置。需要枚舉的a、b只有N對(duì)，可以

5、用滑動(dòng)指針的算法找到所有這樣的邊對(duì)，總復(fù)雜度為O(N)通過(guò)此題，我們已經(jīng)初次接觸到了極限法，并利用它得到了一個(gè)極其簡(jiǎn)單的結(jié)論。本題中極限法的作用是：把自變量的取值范圍從無(wú)窮多條直線減少到了N條直線。例題二、太空站問(wèn)題描述：平面上有n(3≤n≤10000)個(gè)互不重合的已知點(diǎn)，求一條直線，使得所有已知點(diǎn)到這條直線的距離和最小。數(shù)學(xué)模型已知n點(diǎn)的坐標(biāo)分別為：V1(x1,y1),V2(x2,y2),…,Vn(xn,yn)。直線l(ax+by+c=0(ab≠0))的費(fèi)用定義為求min{f(l)}想法：枚舉所有的直線，得到最優(yōu)值平面中的直線有無(wú)窮多條怎

6、樣的直線才有可能是我們要找的那一條呢？若l不經(jīng)過(guò)任何已知點(diǎn)。設(shè)l兩側(cè)的點(diǎn)數(shù)分別有a、b個(gè)，a≥b將l往點(diǎn)多的一側(cè)平移一個(gè)無(wú)窮小量△到l'則f(l')-f(l)=b△-a△=(b-a)△≤0∴f(l')≤f(l)所以已知點(diǎn)相對(duì)于l的位置未發(fā)生改變，即a、b值未變?？刹粩嗤粋€(gè)方向平移l'直至碰到一個(gè)已知點(diǎn)，到l''處，同樣有f(l'')≤f(l)。l''經(jīng)過(guò)某一個(gè)已知點(diǎn)，且費(fèi)用不比l高。l'l''①規(guī)定直線l經(jīng)過(guò)某一個(gè)已知點(diǎn)。la個(gè)點(diǎn)b個(gè)點(diǎn)△△△②直線l必經(jīng)過(guò)兩個(gè)已知點(diǎn)。根據(jù)結(jié)論①，設(shè)l過(guò)V1，而不過(guò)其它已知點(diǎn)。定義：Li—Vi到V

7、1的距離αi—Vi到l的垂線與ViV1的夾角lα2α4α3α7α5α6L2L4L3L7L5L6V1V4V3V5V6V7V2證明②將l繞V1逆時(shí)針旋轉(zhuǎn)一個(gè)無(wú)窮小的角度θ到l'；將l順時(shí)針旋轉(zhuǎn)相同的角度θ到l''；θ足夠小，使旋轉(zhuǎn)過(guò)程中不碰到其它的已知點(diǎn)。ll'l''θθ單獨(dú)的考慮一個(gè)已知點(diǎn)i(i>1)到l的距離的改變當(dāng)αi=0時(shí)∵直角三角形中直角邊<斜邊∴不論直線旋轉(zhuǎn)到l'還是l''，Vi到直線的距離都嚴(yán)格減小了ViV1ll'l''當(dāng)αi>0時(shí)θθV1Viαiθθθθ對(duì)稱(chēng)的情況：∴l(xiāng)不可能為最優(yōu)的ll'l''或∴算法一待枚舉的直線變?yōu)榱擞邢迼l

8、(N2條)，得到一個(gè)有效的算法：min?∞枚舉兩個(gè)已知點(diǎn)根據(jù)這兩個(gè)點(diǎn)確定直線h計(jì)算f(h)若f(h)