資源描述：
《論文國(guó)家隊(duì)金愷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、極限法——解決幾何最優(yōu)化問(wèn)題的捷徑長(zhǎng)郡中學(xué)金愷【關(guān)鍵字】最優(yōu)值極限無(wú)窮小微調(diào)在平血幾何問(wèn)題中我們經(jīng)常會(huì)遇到一些求極值的問(wèn)題。在這些問(wèn)題中，口變量和目標(biāo)函數(shù)町能涉及到坐標(biāo)、斜率、長(zhǎng)度、角度、周長(zhǎng)、面積等等一些復(fù)雜的量，而且往往口變量還有一些復(fù)朵的約束條件，因此直接用函數(shù)求極值的方法是行不通或極其復(fù)雜的。這些問(wèn)題中，變量往往有無(wú)窮多種取值方案（比如說(shuō)點(diǎn)的取值范圍可能是整個(gè)平而或在某條直線上），所以無(wú)法枚舉毎-?種取值方案來(lái)找最值，這時(shí)往往能夠通過(guò)極限法證明：口變量取某些非特殊情況值時(shí)H標(biāo)函數(shù)不可能是最
2、優(yōu)的——因?yàn)檫@時(shí)經(jīng)過(guò)微調(diào)一個(gè)無(wú)窮小量I能夠使得H標(biāo)函數(shù)的值變得更優(yōu)，從而剩下有限種特殊的取值情況可能成為最優(yōu)解，通過(guò)枚舉所冇特殊情況就能找到目標(biāo)函數(shù)的最優(yōu)解了。2在另一些同類(lèi)問(wèn)題中，本來(lái)就可以通過(guò)枚舉有限個(gè)取值情況求出最優(yōu)解，但是枚舉的量很人，時(shí)間復(fù)雜度較高，我們也可嘗試通過(guò)極限法來(lái)大大減少需要枚舉的情況，從而降低時(shí)間復(fù)雜度。以上就是極限法的大致思想，它的作用簡(jiǎn)而言之就是化無(wú)限為有限，變有限為少量。正文極限法的應(yīng)用實(shí)例菲常的多，比如經(jīng)典的最小矩形覆蓋3問(wèn)題，就是通過(guò)極限法證明了：最小矩形的某條邊必
3、須過(guò)兩個(gè)已知點(diǎn)，從而大大減少了需要枚舉的矩形數(shù)目。然而極限法用起來(lái)的確有較人的困難，有時(shí)候證明起來(lái)非常困難，可能情況比較復(fù)雜，也可能不知道如何調(diào)整，需要用到三角兩數(shù)Z類(lèi)的比較復(fù)雜的數(shù)學(xué)知識(shí)，因此其正掌握它需要扎實(shí)的數(shù)學(xué)功底，極強(qiáng)的觀察力以及必要的經(jīng)驗(yàn)是必不可少的。下面就來(lái)用極限法解決一些典型問(wèn)題，從實(shí)例的分析中一步一步深入地認(rèn)識(shí)極限法的用途和用法。例題一、巧克力'比如旋轉(zhuǎn)一個(gè)無(wú)窮小的角度、微移-?段無(wú)窮小的距離。在本文中，微量這一名詞就是指無(wú)窮小量：只要改變得足夠小（無(wú)窮?。湍苁裹c(diǎn)的相對(duì)位置、
4、線段的相交情況等不發(fā)生改變。2極限法的本質(zhì)也就是對(duì)目標(biāo)函數(shù)求導(dǎo)，如果導(dǎo)數(shù)不為0并口白變量不在定義域的邊界則不可能為最優(yōu)值。這正是采用“極限法”來(lái)命名的原因。3平浙上有〃個(gè)已知點(diǎn)，求一個(gè)面積最小的矩形，使得所冇已知點(diǎn)都在矩形的內(nèi)部。頁(yè)共12頁(yè)問(wèn)題描述：糖果廠有一種凸起的N(4WNW50)邊形巧克力，Kiddy和Carlson湊錢(qián)買(mǎi)了一塊，想把它用一?刀割成兩半。兩半的大小必須相等，找出用以分割巧克力的分割線的最短長(zhǎng)度。數(shù)學(xué)模型：已知N個(gè)點(diǎn)(XJi)lWiWN構(gòu)成一凸包P｛已知量｝,求一條劃分線L,使
5、得分割線兩側(cè)的而積相等｛約束條件｝,并且使L的長(zhǎng)度｛目標(biāo)函數(shù)｝最小。問(wèn)題分析：設(shè)分割線的兩個(gè)端點(diǎn)分別為A、B,A、B可能在P的頂點(diǎn)上也有可能只在P的邊上｛不含端點(diǎn)｝。我們分開(kāi)解決這兩種情況：A1、4在P的頂點(diǎn)上(或3在P的頂點(diǎn)上，此時(shí)交換Si=SrAB):顯然可以枚舉P中的一個(gè)頂點(diǎn)作為A，由分割SLLQ線兩側(cè)而積相等這一約束條件直接確定B的位置，如圖1。2、A、B都在P的邊上：枚舉A、B所在的兩條邊，B設(shè)這兩條邊相交于C,如圖2：圖1AAfaa+00UL陰卩B，B設(shè)ZC=y,ZCAB=a,ZCBA
6、邙。當(dāng)a^p時(shí)，可以證明：把分割線L稍微旋轉(zhuǎn)一個(gè)無(wú)窮小量0到L'并保持厶'兩邊的面積相等，能夠使乙‘的長(zhǎng)度小于L.證明如下：不妨設(shè)旋轉(zhuǎn)后U仍與原來(lái)的兩邊相交(因?yàn)閮H旋轉(zhuǎn)了一個(gè)無(wú)窮小量)，交點(diǎn)為B',ZCq'B'w+O,ZCBA=/?-Oo在三角形ABC中，有正弦定理:ACBCsin?sin〈sin?在三角形ABC中，有正弦定理:A2CB2CL2sin(?()sin(〈+()sin?第2頁(yè)共12頁(yè)由于L和Z/都是分割線,所以Sabc=Sabg即1122?AC十BC=A2C十B2CLsin?Lsin
7、(L2sin(?()￡2sin(〈+()TM*卜sin?sin?sin?sin?w、二pi>?>(>04pi>?(>04cos(?(2()>cos(?〈)4>所以LoLS,即L'a時(shí)，厶不可能為最短的分割線。同理，當(dāng)卩勺時(shí)，厶也不可能是最短的。若L是不過(guò)P的頂點(diǎn)的最短的分割線，那么J與P的兩個(gè)夾角必然相等。這就是我們希望得到的，因?yàn)槊杜eL兩個(gè)端點(diǎn)所在的邊后，L的斜率就確定了，再根據(jù)L的兩邊而積相等，就可以直接算出
8、L的位置。得到了這些結(jié)論后，已能夠圖3設(shè)計(jì)出0(N2)的算法。小結(jié)：通過(guò)此題，我們已經(jīng)初次接觸到了極限法，并利用它得到了一個(gè)極其簡(jiǎn)單的結(jié)論。使得自變量的取值范I韋I從無(wú)窮多條玄線減少到了有限條，從而通過(guò)簡(jiǎn)單的窮舉法解決。例題二、太空站SPACE(2003集訓(xùn)討論試題之0039)問(wèn)題描述：平面上有0000)個(gè)互不重合的點(diǎn)，要求一條玄線，使得所有點(diǎn)到這條肓線的距離和最小。數(shù)學(xué)模型：已知n點(diǎn)的坐標(biāo)分別為：V心1ji),必(尤2,尹),???必仏片)。肓線l(ax+by+c=0(ab^()
