論文-極限法-解決幾何最優(yōu)化問(wèn)題的捷徑

極限法——解決幾何最優(yōu)化問(wèn)題的捷徑【關(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è)平面或在某條直線(xiàn)上），所以無(wú)法枚舉每一種取值方案來(lái)找最值，這時(shí)往往能夠通過(guò)極限法證明：自變量取某些非特殊情況值時(shí)目標(biāo)函數(shù)不可能是最優(yōu)的——因?yàn)檫@時(shí)經(jīng)過(guò)微調(diào)一個(gè)無(wú)窮小量比如旋轉(zhuǎn)一個(gè)無(wú)窮小的角度、微移一段無(wú)窮小的距離。在本文中，微量這一名詞就是指無(wú)窮小量：只要改變得足夠?。o(wú)窮小），就能使點(diǎn)的相對(duì)位置、線(xiàn)段的相交情況等不發(fā)生改變。能夠使得目標(biāo)函數(shù)的值變得更優(yōu)，從而剩下有限種特殊的取值情況可能成為最優(yōu)解，通過(guò)枚舉所有特殊情況就能找到目標(biāo)函數(shù)的最優(yōu)解了。比如旋轉(zhuǎn)一個(gè)無(wú)窮小的角度、微移一段無(wú)窮小的距離。在本文中，微量這一名詞就是指無(wú)窮小量：只要改變得足夠?。o(wú)窮小），就能使點(diǎn)的相對(duì)位置、線(xiàn)段的相交情況等不發(fā)生改變。極限法的本質(zhì)也就是對(duì)目標(biāo)函數(shù)求導(dǎo)，如果導(dǎo)數(shù)不為0并且自變量不在定義域的邊界則不可能為最優(yōu)值。這正是采用“極限法”來(lái)命名的原因。在另一些同類(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)典的最小矩形覆蓋平面上有n個(gè)已知點(diǎn)，求一個(gè)面積最小的矩形，使得所有已知點(diǎn)都在矩形的內(nèi)部。問(wèn)題，就是通過(guò)極限法證明了：最小矩形的某條邊必須過(guò)兩個(gè)已知點(diǎn)，平面上有n個(gè)已知點(diǎn)，求一個(gè)面積最小的矩形，使得所有已知點(diǎn)都在矩形的內(nèi)部。然而極限法用起來(lái)的確有較大的困難，有時(shí)候證明起來(lái)非常困難，可能情況比較復(fù)雜，也可能不知道如何調(diào)整，需要用到三角函數(shù)之類(lèi)的比較復(fù)雜的數(shù)學(xué)知識(shí)，因此真正掌握它需要扎實(shí)的數(shù)學(xué)功底，極強(qiáng)的觀(guān)察力以及必要的經(jīng)驗(yàn)是必不可少的。下面就來(lái)用極限法解決一些典型問(wèn)題，從實(shí)例的分析中一步一步深入地認(rèn)識(shí)極限法的用途和用法。例題一、巧克力問(wèn)題描述：糖果廠(chǎng)有一種凸起的N（4≤N≤50）邊形巧克力，Kiddy和Carlson湊錢(qián)買(mǎi)了一塊，想把它用一刀割成兩半。兩半的大小必須相等，找出用以分割巧克力的分割線(xiàn)的最短長(zhǎng)度。數(shù)學(xué)模型：已知N個(gè)點(diǎn)(Xi,Yi)1≤i≤N構(gòu)成一凸包P{已知量}，求一條劃分線(xiàn)L，使得分割線(xiàn)兩側(cè)的面積相等{約束條件}，并且使L的長(zhǎng)度{目標(biāo)函數(shù)}最小。ASRBLSLSL=SR問(wèn)題分析：設(shè)分割線(xiàn)的兩個(gè)端點(diǎn)分別為A、B，A、BASRBLSLSL=SRA在P的頂點(diǎn)上（或B在P的頂點(diǎn)上，此時(shí)交換AB）：顯然可以枚舉P中的一個(gè)頂點(diǎn)作為A，由分割線(xiàn)兩側(cè)面積相等這一約束條件直接確定B的位置，如圖1。圖1A、B都在P的邊上：枚舉A、B所在的兩條邊，設(shè)這兩條邊相交于C，如圖2：圖1AA’BCα+θγβαθθβ-θLAB’L’圖2設(shè)∠C=γ，∠CAB=α，∠CBA=β。當(dāng)α≠β時(shí)，可以證明：把分割線(xiàn)L稍微旋轉(zhuǎn)一個(gè)無(wú)窮小量θ到L’并保持L’兩邊的面積相等，能夠使L’的長(zhǎng)度小于L。證明如下：不妨設(shè)α>β，旋轉(zhuǎn)后L’仍與原來(lái)的兩邊相交（因?yàn)閮H旋轉(zhuǎn)了一個(gè)無(wú)窮小量），交點(diǎn)為A’、B’，∠CA’B’=α+θ，∠CBA=β-θ。在三角形ABC中，有正弦定理：在三角形A’B’C中，有正弦定理：由于L和L’都是分割線(xiàn)，所以SABC=SA’B’C，即圖3所以L(fǎng)2>L’2，即L’<L。如果A、B所在的兩邊平行（即C在無(wú)窮遠(yuǎn)處），也有相同的結(jié)論（如圖3）圖3因此若β>α?xí)r，L不可能為最短的分割線(xiàn)。同理，當(dāng)β<α?xí)r，L也不可能是最短的。若L是不過(guò)P的頂點(diǎn)的最短的分割線(xiàn)，那么L與P的兩個(gè)夾角必然相等。這就是我們希望得到的，因?yàn)槊杜eL兩個(gè)端點(diǎn)所在的邊后，L的斜率就確定了，再根據(jù)L的兩邊面積相等，就可以直接算出L的位置。得到了這些結(jié)論后，已能夠設(shè)計(jì)出O(N2)的算法。小結(jié)：通過(guò)此題，我們已經(jīng)初次接觸到了極限法，并利用它得到了一個(gè)極其簡(jiǎn)單的結(jié)論。使得自變量的取值范圍從無(wú)窮多條直線(xiàn)減少到了有限條，從而通過(guò)簡(jiǎn)單的窮舉法解決。例題二、太空站SPACE(2003集訓(xùn)討論試題之0039)問(wèn)題描述：平面上有n(3≤n≤10000)個(gè)互不重合的點(diǎn)，要求一條直線(xiàn)，使得所有點(diǎn)到這條直線(xiàn)的距離和最小。數(shù)學(xué)模型：已知n點(diǎn)的坐標(biāo)分別為：V1(x1,y1),V2(x2,y2),…Vn(xn,yn)。直線(xiàn)l(ax+by+c=0(ab≠0))的f值定義為，求min{f(l)}。試題分析：最容易想到的做法是枚舉所有的直線(xiàn)，得到最優(yōu)值。但平面中的直線(xiàn)有無(wú)窮多條，怎樣的直線(xiàn)才有可能是我們要找的那一條呢？⑴可以規(guī)定直線(xiàn)l經(jīng)過(guò)某一個(gè)已知點(diǎn)。因?yàn)椋喝鬺不經(jīng)過(guò)任何一個(gè)已知點(diǎn)，則l兩側(cè)肯定有一側(cè)的點(diǎn)數(shù)不少于另一側(cè)，設(shè)多的一側(cè)有a個(gè)點(diǎn)，少的一側(cè)有b個(gè)點(diǎn)，將l往點(diǎn)多的那側(cè)平移一個(gè)微量△到l’，則f(l’)-f(l)=b△-a△=(b-a)△≤0，故f(l’)≤f(l)。（如圖4）ll’’圖4這樣不斷的往同一個(gè)方向平移，直到遇到第一個(gè)已知點(diǎn)，移動(dòng)到l’’?？芍猣(l’’)≤ll’’圖4lα2α4α3α7α5α6L2L4L3L7L5L6V1V4V3V5V6V7V2圖5⑵可以再規(guī)定直線(xiàn)l經(jīng)過(guò)兩個(gè)已知點(diǎn)。原因如下：根據(jù)⑴，設(shè)llα2α4α3α7α5α6L2L4L3L7L5L6V1V4V3V5V6V7V2圖5設(shè)直線(xiàn)繞V1逆時(shí)針旋轉(zhuǎn)一個(gè)很小的角度α(α0+)到l’，l順時(shí)針旋轉(zhuǎn)相同的角度α到l’’。（如圖6）只要α足夠小，就能使旋轉(zhuǎn)過(guò)程中不碰到其它已知點(diǎn)。如果αi=0，那么不論直線(xiàn)旋轉(zhuǎn)到l’還是l’’，Vi到直線(xiàn)的距離都嚴(yán)格減小了。(如圖7)αi≠0，則旋轉(zhuǎn)后的夾角分別變?yōu)棣羒+α，αi–α。由于lαlαl'l''α圖6所以

將每點(diǎn)所作的改變量相加可以得出：；而由直線(xiàn)l的最優(yōu)性可以知道：，，矛盾。αααVαααV1Vi圖7至此，待枚舉的直線(xiàn)就變?yōu)榱擞邢迼l，因此我們可以得到一個(gè)有效的算法了：min∞枚舉兩個(gè)點(diǎn)①根據(jù)兩個(gè)點(diǎn)確定直線(xiàn)h②計(jì)算直線(xiàn)nowf(h)③若now<min則lh,minnow通過(guò)極限法，我們已經(jīng)將需考慮的直線(xiàn)從無(wú)線(xiàn)條轉(zhuǎn)化為了有限的n2條，從而能夠設(shè)計(jì)出一個(gè)有效算法解決本題。此算法的時(shí)間復(fù)雜度為O(n3)，需要進(jìn)一步減少，也就是需要減少枚舉無(wú)用的直線(xiàn)。⑶定義a(l)為直線(xiàn)l上方（若直線(xiàn)豎直則為右方）的點(diǎn)數(shù)；b(l)為直線(xiàn)l上面的點(diǎn)數(shù)；c(l)為直線(xiàn)l下方（若直線(xiàn)豎直則為左方）的點(diǎn)數(shù)。ll’A圖8若l是最優(yōu)的，那么必有a(l)+b(l)>c(l)且c(l)+b(l)ll’A圖8證明：若a(l)+b(l)≤c(l)且c(l)+b(l)≤a(l)，先把它往點(diǎn)較多（可能相等）的一側(cè)平移一個(gè)微量到達(dá)l’（如圖8），顯然根據(jù)⑴的相同證法有f(l’)≤f(l)。由于移動(dòng)的是一個(gè)微量，所以l’上沒(méi)有其它已知點(diǎn)，在l’上任取一點(diǎn)A，把A看成結(jié)論⑵中的V1，繞A微調(diào)，用⑵的類(lèi)似的證明方法有結(jié)論：f(l’)不可能為最優(yōu)解，因此：f(l)也不可能為最優(yōu)解。滿(mǎn)足結(jié)論⑴⑵⑶的直線(xiàn)集合設(shè)為E?？勺C|E|為n級(jí)，用旋轉(zhuǎn)法方法可以使得從E中的一條直線(xiàn)找下一條直線(xiàn)花O(n)的時(shí)間復(fù)雜度（旋轉(zhuǎn)一周后便能把所有的E中的直線(xiàn)找到），計(jì)算一條直線(xiàn)的f值也只需O(n)的時(shí)間復(fù)雜度，所以總的時(shí)間復(fù)雜度只需O(n2)。詳細(xì)的證明和算法請(qǐng)參閱我2003年的集訓(xùn)作業(yè)詳細(xì)的證明和算法請(qǐng)參閱我2003年的集訓(xùn)作業(yè)—0039解題報(bào)告。小結(jié)：本題的幾個(gè)證明過(guò)程并不復(fù)雜，從本質(zhì)上說(shuō)，這三個(gè)結(jié)論的證明方法都是和極限法緊密相關(guān)的：⑴通過(guò)平移一個(gè)微量證明某一類(lèi)直線(xiàn)不可能為最優(yōu)解，將l的取值范圍從所有平面中的直線(xiàn)降為過(guò)一個(gè)已知點(diǎn)的直線(xiàn)；⑵通過(guò)旋轉(zhuǎn)一個(gè)微量證明剩下的直線(xiàn)中的某一類(lèi)不可能為最優(yōu)解，從而使自變量l的取值范圍進(jìn)一步減少到有限條。⑶通過(guò)先平移一個(gè)微量再旋轉(zhuǎn)一個(gè)微量將待考慮的直線(xiàn)條數(shù)從n2降到了n。從本題可以看到解決平面最優(yōu)化問(wèn)題的一般規(guī)律：遇到問(wèn)題后容易產(chǎn)生這樣的猜想：即最優(yōu)解是不是滿(mǎn)足某種性質(zhì)？如果滿(mǎn)足，是不是滿(mǎn)足更特殊的性質(zhì)？……這樣不斷地提出猜想并且嘗試證明，使得自變量的取值范圍不斷縮小，直至不能再小或者達(dá)到我們滿(mǎn)意的地步，剩下的工作就只需通過(guò)枚舉和計(jì)算解決了。提出的這些猜想有時(shí)是正確的、有的存在反例，有的是顯然的、有些證明卻很難。怎么形成猜想呢？最簡(jiǎn)單有效的方法就是通過(guò)一些簡(jiǎn)單的例子尋找一些規(guī)律，要靠認(rèn)真地觀(guān)察才能得到直覺(jué)和靈感。怎么證明猜想呢？最容易的方法是拿幾個(gè)例子進(jìn)行驗(yàn)證，如果有反例，那么猜想失敗，需要部分的修改猜想或者提出全新的猜想。如果找不到反例呢？這并不代表猜想就是正確的。需要進(jìn)行嚴(yán)密的分析來(lái)完整地證明，而極限法正是一個(gè)簡(jiǎn)單、實(shí)用的分析工具。前面兩道題比較簡(jiǎn)單，都直接提出了一種正確地猜想，并且證明的方法也很容易，但平時(shí)解決問(wèn)題常常不是那么一帆風(fēng)順，此時(shí)應(yīng)該怎么做呢？讓我們來(lái)完整的考慮一個(gè)較為復(fù)雜的實(shí)際問(wèn)題。例題三、導(dǎo)彈防御系統(tǒng)（自創(chuàng)試題）問(wèn)題描述：某國(guó)的國(guó)界是一個(gè)凸多邊形，為了防衛(wèi)，國(guó)王打算派工程部隊(duì)修建4座防御塔。戰(zhàn)爭(zhēng)爆發(fā)后敵人可能會(huì)偷襲其中的一座防御塔，而一旦遭偷襲、其余3座防御塔就會(huì)進(jìn)入臨戰(zhàn)狀態(tài)，并且把由它們兩兩相連構(gòu)成的三角形區(qū)域完全封鎖，狡猾的敵人會(huì)使封鎖的區(qū)域面積盡量小，而精明的國(guó)王則希望被敵人破壞后啟動(dòng)的這個(gè)區(qū)域面積盡量大。數(shù)學(xué)模型：函數(shù)f(A,B,C,D)=min{S△ABC、S△ABD、S△ACD、S△BCD}平面上有一個(gè)凸n邊形P，請(qǐng)你在P的內(nèi)部（可以在邊界）選擇4個(gè)點(diǎn)ABCD，使得f(A,B,C,D)最大。問(wèn)題分析：首先，f函數(shù)是求4個(gè)量中的最小值，這很不好處理，究竟4個(gè)三角形中哪個(gè)最小呢？考慮平面上任意四點(diǎn)A、B、C、D，它們有下列3種排列情況：1、某三個(gè)點(diǎn)成一直線(xiàn)，此時(shí)f(A,B,C,D)=0；2、任意三點(diǎn)都不在同一直線(xiàn)上，但是某個(gè)點(diǎn)在另三個(gè)點(diǎn)圍成的三角形內(nèi)，不妨設(shè)D在三角形ABC內(nèi)部，此時(shí)f(A,B,C,D)=min{S△ABD,S△ACD,S△BCD,S△ABD+S△ACD+S△BCD}=min{S△ABD,S△ACD,S△BCD}，由于S△ABD+S△ACD+S△BCD=S△ABC，所以f(A,B,C,D)≤S△ABC/3，又由于A(yíng)BCD任意選取，所以不妨選D為△ABC的重心，此時(shí)f(A,B,C,D)=S△ABC/3。因此某個(gè)點(diǎn)在另三個(gè)點(diǎn)構(gòu)成的三角形內(nèi)這類(lèi)情況最大的f值，等于P中面積最大的三角形ABC的面積的1/3{①}。3、A、B、C、D是某個(gè)凸四邊形的四個(gè)頂點(diǎn)：ABCDA’圖9不妨設(shè)f{A,B,C,D}=S△BCD,那么分別過(guò)D、B作BC、DC的平行線(xiàn)交于A(yíng)’ABCDA’圖9證明：如圖9，S△BCA’=S△BCD≤S△BCAA、B在A(yíng)’D異側(cè)；S△A’CD=S△BCD≤S△ACDA、D在A(yíng)’B異側(cè)，故結(jié)論成立)因此A’也在P內(nèi)部，由于平行四邊形4個(gè)端點(diǎn)的f值=這個(gè)平行四邊形面積的一半，而A’BCD是平行四邊形，因此f(A’,B,C,D)=SABCD/2=S△BCD=f(A,B,C,D)，也就是說(shuō)在可以把ABCD調(diào)整為P內(nèi)某個(gè)平行四邊形的頂點(diǎn)而不使f值改變。因此f值最大的凸四邊形的f值=面積最大的平行四邊形的面積的一半！因此四個(gè)點(diǎn)構(gòu)成凸四邊形這類(lèi)情況的最大f值，等于P中面積最大的平行四邊形面積的1/2{②}。經(jīng)過(guò)上面的轉(zhuǎn)化，我們把原來(lái)的最小值最大問(wèn)題轉(zhuǎn)化為了某個(gè)特定值最大的問(wèn)題，新的問(wèn)題明顯比原問(wèn)題更容易考慮。先來(lái)看①的求解，因?yàn)榭雌饋?lái)它似乎比②簡(jiǎn)單一些（實(shí)際上要簡(jiǎn)單得多），首先假設(shè)A、B、C已經(jīng)確定，看看它應(yīng)滿(mǎn)足什么樣的條件。ABCA’圖10A、B、C可以都取P的頂點(diǎn)，而不會(huì)使面積減少。（換言之，A、B、CABCA’圖10如圖10，過(guò)A做BC的平行線(xiàn)l，則在l上或l的遠(yuǎn)離BC的一側(cè)必然存在P一個(gè)的頂點(diǎn)A’。而A’到BC的距離≥A到BC的距離，所以S△A’BC≥S△ABC。故可以將A移至某個(gè)頂點(diǎn)而使得面積變大或不變?？梢杂肙(N3)的算法枚舉P的3個(gè)頂點(diǎn)A、B、C，并求它們構(gòu)成的三角形的面積的最大值S，S/3就是問(wèn)題①的解。三角形的情況的確容易，因?yàn)榭梢宰孉、B、C恰好為P的三個(gè)頂點(diǎn)，那么平行四邊形是否可以能用同樣的方法呢?這顯然是錯(cuò)誤的，因?yàn)橛锌赡躊的任意4個(gè)頂點(diǎn)都不構(gòu)成平行四邊形，如果真的A、B、C、D都是頂點(diǎn)那豈不是無(wú)解？如果不轉(zhuǎn)化為平行四邊形，而直接枚舉P的頂點(diǎn)做A、B、C、D如果不轉(zhuǎn)化為平行四邊形，而直接枚舉P的頂點(diǎn)做A、B、C、D計(jì)算f(A,B,C,D)也不會(huì)是最優(yōu)的。比如下面這個(gè)例子：n=6,p={(-9.60,0.95)(-7.123.15)(-0.744.72)(7.330.98)(4.26-2.41)(-6.37-.152)}。最優(yōu)解是26.35，而枚舉4個(gè)頂點(diǎn)算出來(lái)的f的最大值為19.40。首先還是要考慮縮小A、B、C、D的取值范圍。一、A、B、C、D都在P的邊界上（不一定是頂點(diǎn)?。?。AABCDA’D’A’’BA’D’D’’C圖11證明：若A、B、C、D中某點(diǎn)不在P的邊界上，不妨設(shè)為A點(diǎn)。將AD沿著DA方向平移一個(gè)微量小到使A’D’都在P內(nèi)部（不包括邊界）到A’D’（如圖11左），此時(shí)SA’BCD’=SABCD，并且A’、D’都不在邊界上。再把A’D’邊沿著B(niǎo)A’方向平移一個(gè)微量小到使A’’D’’都在P內(nèi)部（不包括邊界）到A’’D’’（如圖11右），有小到使A’D’都在P內(nèi)部（不包括邊界）小到使A’’D’’都在P內(nèi)部（不包括邊界）二、A、B、C、D之一可以取P的頂點(diǎn)，而不會(huì)使面積減少。（換言之，A、B、C、D之一是P的頂點(diǎn)的平行形的面積的最大值=P內(nèi)的平行四邊形面積的最大值）終于到了極限法該隆重登場(chǎng)的時(shí)候了！不過(guò)在證明這個(gè)命題之前先要介紹幾個(gè)新的概念：lgg'DBE圖12若直線(xiàn)l和g不平行，點(diǎn)E不在l和（或）g上，如果某個(gè)點(diǎn)B處在l上，另一個(gè)點(diǎn)D處在g上，并且BD關(guān)于點(diǎn)E中心對(duì)稱(chēng)，那么稱(chēng)線(xiàn)段lgg'DBE圖12引理一：(l,g,E)的平分線(xiàn)是唯一確定的。證明如下：如圖12，把g繞E旋轉(zhuǎn)180度到g’，g和g’關(guān)于E中心對(duì)稱(chēng)，設(shè)l和g’相交于B（由于l和g相交、g和g’平行，故l和g’相交），設(shè)D為B關(guān)于中心E的對(duì)稱(chēng)點(diǎn)。由于B在g’上所以D在g上，又因?yàn)锽在l上，所以BD是(l,g,E)的平分線(xiàn)。另一方面，直線(xiàn)l與g’的交點(diǎn)只有一個(gè)，很容易知道不存在其它的BD是（l,g,E）的平分線(xiàn)。D''D'DB(B')(B'')E''EE'gl圖13引理二：若E’,E’’關(guān)于E中心對(duì)稱(chēng)且EE’是微量，BD、B’D’、BD''D'DB(B')(B'')E''EE'gl圖13①EE’E’’平行于g（如圖13）。則B,B’,B’’重合，所以B’B’’關(guān)于B對(duì)稱(chēng)，同時(shí)由中位線(xiàn)知識(shí)容易看出：DD’=2EE’=2EE’’=DD’’,而DD’D’’都在g上，所以D’D’’關(guān)于D中心對(duì)稱(chēng)。②EE'E''平行于l。同理可證。③EE’E’’不平行于g和（或）l。由于E’E’’關(guān)于E中心對(duì)稱(chēng)，所以E’E’’=2EE’’。設(shè)x=H(E’’,g)H(V,l)表示點(diǎn)V到直線(xiàn)l的距離H(V,l)表示點(diǎn)V到直線(xiàn)l的距離glDBED'B'E'D''B''E''圖14H(B’’,g)=glDBED'B'E'D''B''E''圖14H(B’,g)=2(x+2y)，所以BB’’=BB’。而B(niǎo)、B’、B’’都在同一直線(xiàn)l上，故B’B’’關(guān)于B對(duì)稱(chēng)?？紤]垂直于l的方向的距離可證DD’’=DD’，所以D’D’’關(guān)于D對(duì)稱(chēng)?？偨Y(jié)①②③得引理二得證。BCADB’A’圖15下面分兩種情況BCADB’A’圖15<1>某兩個(gè)頂點(diǎn)在同一條邊上（不妨設(shè)A、B在同一條邊上），根據(jù)圖15容易看出，因?yàn)榇嬖谝粋€(gè)面積不變的平行四邊形A’B’CD，使得某個(gè)點(diǎn)在P的頂點(diǎn)上。ABCDabcdE圖16<2>任意兩個(gè)頂點(diǎn)都不在同一條邊上，即A、B、C、D在P的4條不同的邊上，如圖16：設(shè)A在a上，B在b上，C在c上，D在d上，并且都不是邊的端點(diǎn)。aABCDabcdE圖16<2>-I、a//c并且b//d。bdDB圖17B1D1B2D2F此時(shí)E的位置是確定的。SABCD=4SABE=2AE*H(B,AC)保持AC邊不變，調(diào)整BD：過(guò)B點(diǎn)做AC的平行線(xiàn)e，b的某個(gè)端點(diǎn)V一定在e的遠(yuǎn)離E的一側(cè)或在直線(xiàn)e上，此時(shí)把B往V方向移動(dòng)一個(gè)微量到B’，同時(shí)D往反方向移動(dòng)到D’。顯然有H(B’,AC)≥H(B,AC)，所以SAB’CD’不會(huì)比bdDB圖17B1D1B2D2FaabcdEACBabcdEACVDDV圖17<2>-II、若或者,情況就要復(fù)雜多了。不妨設(shè)，如圖17所示：設(shè)bd的延長(zhǎng)線(xiàn)交于F，b的兩個(gè)端點(diǎn)為B1,B2（B1在F和B2之間），d的兩個(gè)端點(diǎn)為D1,D2（D1在F和D2之間），定義紅色區(qū)域?yàn)樯渚€(xiàn)B2B1,D2D1與線(xiàn)段B1D1圍成的三角形區(qū)域，定義黃色區(qū)域?yàn)樯渚€(xiàn)B1B2,D1D2與線(xiàn)段B2D2圍成的無(wú)限區(qū)域。由于A(yíng)、B、C、D都在凸包P上，所以A和C有且僅有一個(gè)點(diǎn)（不妨設(shè)為C）在紅色區(qū)域中，另一個(gè)（不妨設(shè)為A）在圖中黃色區(qū)域中。接下來(lái)證明：固定A點(diǎn)、調(diào)整BCD使平行四邊形的面積增大若固定若固定C點(diǎn)，調(diào)整ABD將不能證明后面的結(jié)論!cclgbB''D''B'AD'E''E'C''BDECC'圖18設(shè)B所在邊b所在直線(xiàn)為l,D所在的邊所在的直線(xiàn)為g。在線(xiàn)段c上取兩個(gè)點(diǎn)C’C’’關(guān)于C對(duì)稱(chēng)，并且CC’的距離趨近于0，設(shè)E’,E’’分別為AC’、AC’’的中點(diǎn)，設(shè)B’D’和B’’D’’分別是(l,g,E’)、(l,g,E’’)的平分線(xiàn)。根據(jù)對(duì)角線(xiàn)互相平分的四邊形是平行四邊形得：AB’C’D’和AB’’C’’D’’都是平行四邊形，E’和E’’分別是它們的中心。只要我們能夠證明SAB’C’D’+SAB’’C’’D’’>2SABCD，那么AB’C’D’和AB’’C’’D’’中至少有一個(gè)面積比SABCD大，也就證明了結(jié)論。而SABCD=4SADE；SAB’C’D’=4SAD’E’；SAB’’C’’D’'=4SAD’’E’’；因此可以證明等價(jià)的結(jié)論：SAD’E’+SAD’’E’’>2SADE。因?yàn)镋’E’’關(guān)于E中心對(duì)稱(chēng)，由引理二可以知道：D’D’’關(guān)于D中心對(duì)稱(chēng)。另外，由于EE’平行于g，而g與c相交，因此EE’與DD'相交，不妨設(shè)它們交于X，如圖19：1、1、圖19所示的為ADX為逆時(shí)針順序時(shí)的情況；2、當(dāng)ADX為順時(shí)針?lè)较驎r(shí)，同理可證；3、當(dāng)D、X重合時(shí)亦可證明（如圖20），方法略。cgE'D'XAE''EDD''圖19D''D''E''DAEE'D'圖20SAD’E’+SAD’’E’’=(SAD’’XE’-SAD’D’’-SD’E’E’’-SXE’’D’)+(SAD’’XE’-SAE’E’’-SE’’D’D’’-SXE’’D’)=2SAD’’XE’-2SXE’’D’-SAD’D’’-SAE’E’’-SD’E’E’’-{SE’’D’D’’}2SADE =2(SAD’’XE’-SADD’’-SAEE’-SD’EE’’-SEDD’-SXE’’D’)=2SAD’’XE’-2SXE’’D’-SAD’D’’-SAE’E’’-SD’E’E’’-{SED’D’’}SAD’E’+SAD’’E’’-2SADE=SED’D’’-SE’’D’D’’>0故SAD’E’+SAD’’E’’>2SADE所以有SAD’E’>SADE或SAD’’E’’>SADE，因此有SAB’C’D’>SABCD或SAB’’C’’D’’>SABCD，也就是說(shuō)當(dāng)ABCD在P的邊界上但都不是P的頂點(diǎn)時(shí)，ABCD的面積肯定不是P中平行四邊形的面積的最大值。綜合上述證明得：A、B、C、D之一可以取P的頂點(diǎn)，而不會(huì)使面積減少。下面簡(jiǎn)單的說(shuō)明為什么不能固定C點(diǎn)調(diào)整ABD，因?yàn)榇藭r(shí)D''DD'的相對(duì)位置發(fā)生了改變，如圖21，此時(shí)SAE'D'+SAE''D''并不是恒大于2SAED的。小結(jié)：結(jié)論二比結(jié)論一的得到困難了許多，回顧證明的過(guò)程：首先我們不得不分了許多種情況來(lái)一一證明，好在大多數(shù)情況都是較為特殊的，證明較為容易。情況<2>-II是一般的，也是最難證的：證明過(guò)程中，先選擇固定A點(diǎn)，然后在C的兩側(cè)取兩個(gè)距離無(wú)限小的對(duì)稱(chēng)點(diǎn)，最后往兩個(gè)方向分別調(diào)整ABCD到AB’C’D’和AB’’C’’D’’。引理二告訴我們一個(gè)簡(jiǎn)單的性質(zhì)：B’B’’、D’D’’分別關(guān)于B和D對(duì)稱(chēng)，利用這一簡(jiǎn)單的性質(zhì)用就能得到SAB’C’D’+SAB’’C’’D’’>2SABCD。<2>-II的證明是個(gè)比較復(fù)雜的極限法，此次調(diào)整的量是距離而不是角度，因?yàn)楹苊黠@調(diào)整距離時(shí)各個(gè)量的改變都容易得到，而如果采用角度，恐怕就會(huì)有更為復(fù)雜的數(shù)學(xué)式子了！這說(shuō)明了觀(guān)察能力在極限法中的重要作用。另外，證明中和例題2一樣采用了是2次調(diào)整做和，為什么不能直接調(diào)整1次呢？有兩個(gè)主要原因：我們并不知道往哪一側(cè)調(diào)整后能使目標(biāo)函數(shù)更優(yōu)（并不是往任意方向調(diào)整都會(huì)變優(yōu)的）；（2次調(diào)整后的目標(biāo)函數(shù)的和）與（原函數(shù)的兩倍）的差很容易計(jì)算，把它們拆成一些三角形的和后大部分的項(xiàng)做差后都被抵消了。如果只調(diào)整1次，我們需要計(jì)算在什么時(shí)候往什么方向調(diào)整（而與調(diào)整2次相比，這是一項(xiàng)額外的工作），而且證明過(guò)程也將更為復(fù)雜。2次調(diào)整做和方法是極限法證明中經(jīng)常要用到的手段?？偨Y(jié)了這么多，是不是有些太早了？我們僅僅證明了結(jié)論二，但是滿(mǎn)足結(jié)論二的平行四邊形仍然有無(wú)窮多個(gè)！我們并沒(méi)有完整地解決原問(wèn)題。不過(guò)，你也許馬上就會(huì)猜想：規(guī)定A、B、C、D中有兩個(gè)點(diǎn)是P的頂點(diǎn)，是不是也不影響最優(yōu)值？看起來(lái)似乎的確能夠利用剛才類(lèi)似的方法進(jìn)行證明：首先由結(jié)論二可設(shè)A是P的頂點(diǎn)而B(niǎo)、C、D在P的邊上，由于固定B、C或D時(shí)，A可