線性規(guī)劃范文
時間：2023-03-26 13:14:02
導(dǎo)語：如何才能寫好一篇線性規(guī)劃，這就需要搜集整理更多的資料和文獻，歡迎閱讀由公務(wù)員之家整理的十篇范文，供你借鑒。
篇1
關(guān)鍵詞：基本問題；平面區(qū)域；約束條件；目標(biāo)函數(shù)；雙變量；轉(zhuǎn)化化歸
線性規(guī)劃的研究內(nèi)容可歸納為兩個方面：一是系統(tǒng)的任務(wù)已定，如何合理籌劃，精細(xì)安排，用最少的資源（人力、物力和財力）去實現(xiàn)這個任務(wù)；二是資源的數(shù)量已定，如何合理利用、調(diào)配，使任務(wù)的完成數(shù)最多.
“線性規(guī)劃”在知識的整合、解題思路的拓展、方法的遷移等方面都有其鮮明的特點，有著豐富的思想內(nèi)涵. 挖掘題中條件，不失時機地運用“線性規(guī)劃”的思想方法解題，將使我們觀察思考問題的立意更高，視野更加開闊.
“線性規(guī)劃”問題的教學(xué)現(xiàn)狀
在中學(xué)教材中，稱求目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題為線性規(guī)劃問題. “線性規(guī)劃”的教學(xué)分為三個層次：
（1）二元一次不等式表示的平面區(qū)域；
（2）二元一次不等式組表示的平面區(qū)域；
（3）線性目標(biāo)函數(shù)在約束條件下的最值.
只含有兩個變量的簡單線性規(guī)劃問題可用圖解法來解決.
例如：設(shè)實數(shù)x，y滿足0≤x≤1，0≤y≤2，2y-x≥1，則z=2y-x+4的最大值是__________.
上述問題可轉(zhuǎn)化為一個平面區(qū)域與一條直線在有公共點的前提下，結(jié)合z的幾何意義來求解.
具體教學(xué)過程中，學(xué)生感覺有困難的部分是作圖環(huán)節(jié)，體現(xiàn)在速度慢，不夠準(zhǔn)確. 如何準(zhǔn)確有效地作出所需圖形，應(yīng)給予學(xué)生充分的指導(dǎo)、訓(xùn)練和體驗. 學(xué)生作圖時會出現(xiàn)過于細(xì)致的問題，如逐步描繪坐標(biāo)系刻度；又或出現(xiàn)過于輕率的問題，連圖形的形狀和基本特征都無法抓住.這兩個問題都使解題的速度和準(zhǔn)確性大打折扣.
當(dāng)然，線性規(guī)劃是一個比較深入的課題，教材中也介紹了更多變量的線性規(guī)劃問題，可引導(dǎo)學(xué)生進一步學(xué)習(xí).
線性規(guī)劃問題的考查特點與趨勢
1. 轉(zhuǎn)化成基本線性規(guī)劃問題
常規(guī)考題考查知識與技能，但還需要學(xué)生有一定的轉(zhuǎn)化和化歸意識，命題者會在行文敘述、符號變化、算式特征等方面設(shè)置一定障礙，需要解題者對得到的信息加工出熟悉的數(shù)學(xué)模型.
例1 （江蘇2013年9題）拋物線y=x2在x=1處的切線與兩坐標(biāo)軸圍成三角形區(qū)域為D（包含三角形內(nèi)部和邊界）. 若點P（x，y）是區(qū)域D內(nèi)的任意一點，則x+2y的取值范圍是__________.
分析：本題以拋物線的切線為背景，以文字?jǐn)⑹龅姆绞教峁┝丝尚袇^(qū)域，題中曲線切線利用導(dǎo)數(shù)可得.
解決：求導(dǎo)得y′=2x，切線方程為y=2x-1 ，轉(zhuǎn)化為等價的基本問題：約束條件為x≥0，y≤0，y≥2x-1，目標(biāo)函數(shù)z=x+2y. 作出圖形，易知z的取值范圍為-2，.
例2 設(shè)實數(shù)x，y滿足3≤xy2≤8，4≤≤9，則的最大值是__________.
分析：如何將其化歸成基礎(chǔ)問題，找到未知問題和基本題之間的橋梁是破解的關(guān)鍵.
解法一：整體代換，令xy2=m，=n，
那么==，轉(zhuǎn)化為等價問題：約束條件為3≤m≤8，16≤N≤81.目標(biāo)函數(shù)為z=，z幾何意義為對應(yīng)區(qū)域內(nèi)動點與坐標(biāo)原點連線的斜率，易得最大值為27.
解法二：將除法轉(zhuǎn)變?yōu)楹突虿睿}中代數(shù)式兩邊都取以2為底的對數(shù)，令log2x=A，log2B=y. 轉(zhuǎn)化為等價問題：約束條件為log23≤A+2B≤3，2≤2A-B≤2log23，目標(biāo)函數(shù)為z=3A-4B，可行區(qū)域如圖，容易求得z的最大值為3log23，那么=2z的最大值是27.
圖2
點評：解法一采用了整體換元，解法二采用了取對數(shù)化積為和、化除為差，通過轉(zhuǎn)化和化歸轉(zhuǎn)化成已經(jīng)解決過的基本問題.
2. 線性規(guī)劃問題的拓展延伸
（1）線性規(guī)劃問題中目標(biāo)函數(shù)的拓展
熟悉線性規(guī)劃基本題還遠(yuǎn)遠(yuǎn)不夠，深刻把握它的數(shù)學(xué)特點和數(shù)學(xué)思想，在實際處理問題中將未知問題轉(zhuǎn)化為基本題才更重要. 那么該類問題的基本特點是什么，常見問題是什么？只有清楚這些，我們才能在實際處理過程中及時、敏銳地轉(zhuǎn)化問題，達到解決問題的目的.
以下提供最常見的基本類型；
約束條件：實數(shù)x，y滿足y≤x，y≥0，2x-y≤2，可行區(qū)域如圖3.
圖3
目標(biāo)函數(shù)（1）：z=3x+y的最大值是__________，z的幾何意義即直線y=-3x+z的縱截距；
目標(biāo)函數(shù)（2）：z=的最大值是__________，z的幾何意義即可行區(qū)域內(nèi)動點P（x，y）與點（-1，0）所連直線的斜率；
目標(biāo)函數(shù)（3）：z=的最大值是__________，z的幾何意義即可行區(qū)域內(nèi)動點P（x，y）與點（0，1）之間的距離.
與線性規(guī)劃相關(guān)的問題普遍具有一些基本特征，主要表現(xiàn)為已知條件是含“雙變量”的不等關(guān)系，目標(biāo)任務(wù)為代數(shù)式的最值或取值范圍問題. 可解決的目標(biāo)函數(shù)也不一定是線性代數(shù)式，可以為其他類型.常見的可以為乘積或比值形式、二次或根式形式，甚至可以用向量等給出的代數(shù)式. 也不一定拘泥于目標(biāo)函數(shù)的最值問題，也可成為以可行區(qū)域為背景的面積、向量、概率等問題.
（2）線性規(guī)劃問題中約束條件的拓展
我們可以將它的數(shù)學(xué)思想拓展得更寬. 約束條件不一定要是線性約束條件，相應(yīng)的平面區(qū)域也可以為直線、圓、曲線等構(gòu)成的復(fù)合形態(tài).
例如：實數(shù)x，y滿足x2+y2=1，則x+y的最大值是__________.
此題可行區(qū)域可認(rèn)為是圓，可視為曲線圓與直線x+y=m有公共點. 由此看來，約束條件的給出有了更大的空間，線性規(guī)劃這個知識點也更容易滲透到其他數(shù)學(xué)知識點中.
例3 若a>0，b>0且+=1，則a+2b的最小值為__________.
分析：題目涉及兩個變量的等量關(guān)系，可以考慮減元處理，已由代數(shù)式整理得a=-b++1，結(jié)合基本不等式解決a+2b的最小值；也可以考慮其幾何意義，視作以b為自變量的函數(shù)，那么P（b，a）為函數(shù)圖象上的每一個點.
圖4
解決：a=-b++1，令z=a+2b，z表示此直線的縱截距.當(dāng)直線與曲線相切時z最小，此時a′=-2.求導(dǎo)a′=-1-，所以b=，a=-++1=+，所以a+2b=+.
例4 （江蘇2012年14題）已知正數(shù)a，b，c滿足：5c-3a≤b≤4c-a，clnb≥a+clnc，則的取值范圍是__________.
分析：此題和基本問題的相似度極高，已知條件含有3個變量，而且目標(biāo)函數(shù)為比值形式，有明確的幾何意義. 由代數(shù)式clnb≥a+clnc的邏輯計算知ln≥，由此得到轉(zhuǎn)化的突破口，可轉(zhuǎn)化為兩個變元.
圖5
解決：已知兩個不等式同除c得到5-3≤≤4-，ln≥.記=x，=y，
轉(zhuǎn)化為等價問題：
約束條件為x，y>0，5-3x≤y≤4-x，lny≥x？圳y≥ex，目標(biāo)函數(shù)k==.
作出圖形，利用導(dǎo)數(shù)求出曲線y=ex過坐標(biāo)原點的切線為y=ex，發(fā)現(xiàn)切點T（1，e）在可行區(qū)域內(nèi). 綜上，直線y=kx過C點時k最大，與曲線y=ex相切于點T時k最小. 所求取值范圍為[e，7].
圖6
點評：三變量的問題轉(zhuǎn)化為兩變量問題，該問題的解決具有一定的代表性.由已知代數(shù)式還可以考慮同除a或b進行轉(zhuǎn)化，不是每一個轉(zhuǎn)化都適合，但有些轉(zhuǎn)化又是相通和可行的，因此求解時需要一定的嘗試和觀察.
3. 線性規(guī)劃問題的知識遷移
有些數(shù)學(xué)問題并無明顯的線性規(guī)劃痕跡，卻也可以轉(zhuǎn)化成線性規(guī)劃的基本問題，比如解析幾何、函數(shù)、數(shù)列等含有多個變量的數(shù)學(xué)問題可采用線性規(guī)劃的方法來求解. 以下試題立足于課本，但高于課本，題目充分體現(xiàn)了命題教師的高瞻遠(yuǎn)矚，而反過來又對高中的教學(xué)提出更高要求.
例5 （江蘇2011年14題）設(shè)集合A=（x，y）≤（x-2）2+y2≤m2，x，y∈R，B={（x，y）2m≤x+y≤2m+1，x，y∈R}，若A∩B≠，則實數(shù)m的取值范圍是__________.
分析：兩集合為點集，交集非空.思考難度超越課本，類比線性規(guī)劃，將其轉(zhuǎn)化為兩個平面區(qū)域有公共點，同時本題的計算量大.
解決：集合A對應(yīng)區(qū)域為D1，集合B對應(yīng)區(qū)域為D2，D2容易認(rèn)識為兩平行直線確定的帶狀區(qū)域. 由區(qū)域D1非空可知m2≥，求得m≤0或m≥.
（1）m=0區(qū)域D1收縮為一點，容易判斷不滿足要求；
（2）m≠0區(qū)域D1又分為兩種情況，當(dāng)m0時表示兩個同心圓確定的環(huán)形區(qū)域.不論哪種情況，要滿足題意，只需要保證圓（x-2）2+y2=m2和直線x+y=2m或直線x+y=2m+1其中之一有公共點. 圓心到兩直線距離分別為d1和d2，且d1=，d2=. 所以d1≤r=m或d2≤r=m，容易解得m∈1-，2+，綜合以上分析，實數(shù)m的取值范圍是，2+.
點評：問題描述采用了幾何語言，解決思路和線性規(guī)劃有類似之處，同時解析幾何背景很強，充分考查了直線和圓的位置關(guān)系，而且分析時利用分類討論細(xì)化，處理時又不討論集中解決，思維跳躍度很大.
例6 已知a，b為常數(shù)，a≠0，函數(shù)f（x）=a+ex. 若f（2）
分析：此題僅僅從表象上看到已知條件對變量a，b作了限制，與線性規(guī)劃知識點的相關(guān)性相當(dāng)隱蔽. 該題目變量的關(guān)系相互依賴性較強，關(guān)鍵從已知條件合理的抽離出最有效約束條件.
圖7
解決：由f（2）
點評：g（x）=ax2+bx-b≥0恒成立分析較難，考慮不等式成立的必要條件攻克了這個難點，根據(jù)代數(shù)式的依存關(guān)系得到約束條件，畫出圖形，所求面積視為兩個三角形面積差.
以上可以看出這些問題和教材中很多知識點綜合，都需要學(xué)生具備良好的知識遷移能力. 包括高考在內(nèi)的眾多考題都或多或少地含有線性規(guī)劃知識或思想的若干部分，這樣的考題都具備一定的難度，成為命題的熱點題型，在考試中層出不窮.
教學(xué)感悟與思考
篇2
新教材增加的簡單線性規(guī)劃內(nèi)容,不僅給傳統(tǒng)的高中數(shù)學(xué)注入了新鮮的“血液”,而且給學(xué)生提供了學(xué)數(shù)學(xué),用數(shù)學(xué)的實踐機會。線性規(guī)劃問題是教材中重點內(nèi)容,也是高考中熱點。線性規(guī)劃問題主要考查在線性約束條件下,求可行域的面積或確定形狀;求線性目標(biāo)函數(shù)的取值范圍、最值(如直線斜率,兩點間的距離,點到直線的距離、范圍等)或取最值時點的坐標(biāo)。線性約束條件是由不等式(組)或方程(組)來表示的,因此線性規(guī)劃必然與不等式、方程、函數(shù)等知識聯(lián)系密切,而“在知識網(wǎng)絡(luò)交匯點設(shè)計問題,促進學(xué)科內(nèi)知識的交融和滲透”正好是新課程高考命題的求新點和切入點。高中階段學(xué)習(xí)的線性規(guī)劃具有工具性、應(yīng)用性,同時也滲透了化歸、數(shù)形結(jié)合的數(shù)學(xué)思想,為學(xué)生今后解決實際問題提供了一種重要的解題方法――數(shù)學(xué)建模法。
一、面積問題
1、(全國卷)在坐標(biāo)平面上,不等式組y≥x-1y≤-3x+1所表示的平面區(qū)域的面積為_________。
解析:原不等式組去掉絕對值后轉(zhuǎn)化為兩個不等式組,畫出平面區(qū)域,根據(jù)三角形面積公式求得答案。
二、最值問題
2、(全國卷)若x,y滿足約束條件x+y≥0x-y+3≥00≤x≤3則z=2x-y的最大值為____________。
解析:z=2x-y的幾何意義是斜率為2的直線的縱截距的相反數(shù),在坐標(biāo)平面上畫出可行域,可得結(jié)果。
x,y滿足x-y-2≤0x+2y-4>02y-3≤0則的最大值是________。
3、(江西)設(shè)實數(shù)
解析:在坐標(biāo)平面上畫出可行域z==的幾何意義是兩點O(0,0)A(x,y)連線的斜率,畫圖可知,在點(1, )時z最大,故所求最大值為。
4、教材第二冊(上)第99頁 第5題
解析:由問題的形式聯(lián)想到兩點間距離公式,從而利用線性規(guī)劃的思想去解決。上述幾題中的約束條件是以不等式的形式出現(xiàn),有時以方程形式給出,如教材第二冊(上)第99頁 第6題
方法提煉:
①解決線性規(guī)劃問題,首先找到線性約束條件,畫出可行域;線性約束條件可能是關(guān)于x、y的不等式(組)或方程(組)。
②其次要確定目標(biāo)函數(shù)(多是二元函數(shù))理解它的幾何意義;如:截距問題,斜率 ,兩點間距離,點到直線距離。
篇3
毋庸置疑，數(shù)學(xué)規(guī)劃領(lǐng)域的重大突破總是始于線形規(guī)劃。提到線性規(guī)劃算法，人們最先想到的是單純形法和內(nèi)點法。單純形法是實際應(yīng)用中使用最普遍的一種線性規(guī)劃算法，而研究者們已證明在最壞的情況下單純形法的計算復(fù)雜度是指數(shù)級的，內(nèi)點算法的計算復(fù)雜度是多項式時間的。把兩種算法相提并論，要么是這兩種算法都已經(jīng)非常完備，要么都有需改進之處。顯然不屬于前者，即兩者都有需要改進之處。幾十年來，研究者通過不斷努力，在兩種算法的計算上都取得相當(dāng)?shù)倪M展。
1數(shù)學(xué)模型
線性規(guī)劃問題通常表示成如下兩種形式:標(biāo)準(zhǔn)型、規(guī)范型。
設(shè)jj(2…，n)是待確定的非負(fù)的決策變量；認(rèn)2…，n)是與決策變量相對應(yīng)的價格系數(shù)；K2…mj=l2…n)是技術(shù)系數(shù)；b(i12…，m)是右端項系數(shù)；
線性規(guī)劃是運籌學(xué)最基本、運用最廣泛的分支，是其他運籌學(xué)問題研究的基礎(chǔ)。在20世紀(jì)50年代
到60年代期間，運籌學(xué)領(lǐng)域出現(xiàn)許多新的分支：非線性規(guī)劃（nonlinearprogranming、商業(yè)應(yīng)用（crnxmereialpplieation、大尺度方法(laresealemeh-Qd)隨機規(guī)劃（stochasticPKgiamniig)、整數(shù)規(guī)劃(ntegerprogramming)、互補轉(zhuǎn)軸理論（amplmentaiyPivotheor)多項式時間算法（polynomialtjneagatm)等。20世紀(jì)70年代末，上述分支領(lǐng)域都得到了極大發(fā)展，但是卻都不完善。而且數(shù)學(xué)規(guī)劃領(lǐng)域中存在許多Nfkhard問題，如TP問題，整數(shù)規(guī)劃問題等。這些問題的基本模型都可以寫成線性規(guī)劃形式，因此通過對線性規(guī)劃算法的進一步研究，可以進一步啟發(fā)及推動數(shù)學(xué)規(guī)劃領(lǐng)域內(nèi)其他分支的發(fā)展。
2邊界點算法
由于單純形法與基線算法都是在可行集的邊界上取得最優(yōu)值，故合稱單純形法與基線法為邊界點算法。單純形法是線性規(guī)劃使用最早也是目前實際應(yīng)用中最流行和求解新型規(guī)劃問題最有效的算法之一。它實施起來相當(dāng)簡單特別對中小規(guī)模問題效果顯著。單純形法最早是由Damzg于1947年夏季首先提出來的。1953年Dantzig為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法12。1954年美國數(shù)學(xué)家CELmH3針對對偶問題提出一種在數(shù)學(xué)上等價于用改進單純形法求解的對偶線形規(guī)劃。1974年CuretN41提出了求解一般線性規(guī)劃問題的原對偶單純形法，該算法與對偶單純形法類似，但是原對偶單純形法允許我們從一個非基礎(chǔ)對偶可行解開始算法求解。
1972年Klee等舉例證明了單純形算法的時間復(fù)雜性有可能是指數(shù)型。1973年，Jeoslowoi和Zdeh7又分別進一步指出常用的對偶單純形法、原一對偶單純形法等都是指數(shù)級的。
這就讓人們產(chǎn)生兩個疑問:①是否存在單純形法的某種改型，用它求解線性規(guī)劃問題是多項式時算法。
對于問題①，研究者們對單純形法采用了一系列改進技術(shù)如數(shù)據(jù)的預(yù)處理方法、更好的退化性處理、更好的局部價格向量計算、原一對偶最速下降邊算法的應(yīng)用、更快和更穩(wěn)定的矩陣分解、更好的Cach存貯的應(yīng)用、以及階段1和階段2的組合算法等。但是仍未能從理論上證明線形規(guī)劃算法是多項式時間的。
近年來國內(nèi)也出現(xiàn)了一批致力于線形規(guī)劃算法研究的學(xué)者，但是國內(nèi)學(xué)者的研究主要集中在對單純形法的突破研究上，如基線法|8_'最鈍角原理1111等。
最鈍角及投影主元標(biāo)算法都是針對單純形算法存在退化現(xiàn)象就如何選擇最優(yōu)入基、離基做出的一系列研究及改進。退化現(xiàn)象是單純形法一直以來需解決的難題，為了克服退化問題許多學(xué)者提出了有限主元規(guī)則：擾動法、字典序規(guī)則、Blad規(guī)則1171等，其中Bind規(guī)則由于其簡單而備受關(guān)注，但是這些有限主元規(guī)則的實際應(yīng)用方面并不令人滿意，甚至都不能和Dantzg規(guī)則相比。1990年，潘平奇教授在文獻[11]給出了線性規(guī)劃問題最優(yōu)基的一個啟發(fā)式刻畫特征:最鈍角原理。最鈍角原理是引人反映目標(biāo)梯度與約束梯度夾角大小的“主元標(biāo)”乍為確定變量進基優(yōu)先性的依據(jù)，潘教授的數(shù)值試驗11819表明此規(guī)則明顯優(yōu)于Bland規(guī)則。然而潘的方法僅適用于只含不等式約束的線性規(guī)劃問題。為便于求解標(biāo)準(zhǔn)線性規(guī)劃問題，許多學(xué)者在其基礎(chǔ)上又提出了對偶主元標(biāo)法。由于對偶主元標(biāo)法是利用嚴(yán)格互補松弛來推導(dǎo)過度的，針對這一問題，又有學(xué)者提出了投影主元標(biāo)法。
除此之外還有一系列最鈍角原理在非人工變量兩階段算法1M21及虧基情況下的應(yīng)用研究。這些研究表明，最鈍角原理是克服單純形法退化的一種有效方法。
基線算法的概念是1996年阮國楨教授提出來的1891，這種算法是單純形法的發(fā)展，名字由來一方面是相對單純形法（基點法）提出，另一方面是使用
基線算法的主要思想是：
其中疋FTX1;eRbERm為一個m階單位矩陣。n是問題的維數(shù)，m是約束個數(shù)。把目標(biāo)函數(shù)v=ff作為一個約束，看作參數(shù)。
Stef!以任意：>0所對應(yīng)的變量作為進基變量，則x所在的列與單位矩陣一起構(gòu)成了一個可行基B改寫八=[N馬，相應(yīng)地改寫X為[xrxo’，x為非基變量，x為基變量。于是方程組AX=[vb’可以寫成Nx+Bx^Evl]’=a0+^0VStep求B1，以B1左乘，得B^1N^N+3B=B1[v]’=礦a0+B1⑷v
(2.1)
令a=B1a。，p=B-1仏則式（21河寫作
Sep對任意巨{01，…，m}，令aA^vs0
計算出當(dāng)前基線表對應(yīng)的可行值區(qū)間[J-”。若h
…，n-L貝IJv為最優(yōu)值，或者轉(zhuǎn)SteP4
Sep旋轉(zhuǎn)基表，更新BaP旋轉(zhuǎn)基表時通常只使用有限軟上界行的負(fù)可旋主元。對于負(fù)可旋主元的選擇主要實現(xiàn)方法有：最大負(fù)主元算法[221，行列最好主元算法[231,保硬主元算法[24251等。
基線算法操作簡單迭代次數(shù)少，求解速度快。相對單純形法來說，單純形法最多能搜索與當(dāng)前極點相鄰的n個極點，而基線算法能搜索11個二維面，這是基線算法能夠快速求解LP問題的關(guān)鍵所在。
發(fā)展至今，基線算法已有其對偶算法[271，群部分算法['目標(biāo)規(guī)劃[29301,錐上算法[311等一整套的理論基礎(chǔ)和一系列具體的快速實現(xiàn)算法12632,圍繞著是否存在著多項式的基線算法，在計算復(fù)雜度方面作深入的研究將對線性規(guī)劃的發(fā)展具有十分深遠(yuǎn)的意義。
3割平面法
線性規(guī)劃算法中割平面思想的應(yīng)用主要是指橢球法。1979年Khanchiaii33!改進Yudin和Nan-
ovski等[34]為凸規(guī)劃開發(fā)的橢球法，獲得了一個求解線形規(guī)劃的多項式時間算法:橢球法。對問題②做出了明確回答。不同于單純形法從一個基礎(chǔ)可行解開始迭代，橢球法的特點是求解過程的每一階段都有一個以某一點為中心的橢球，迭代是從一個包含最優(yōu)解的較大的橢球迭代到包含最優(yōu)解的較小的橢球直至逼近最優(yōu)解。
為線性規(guī)劃問題式（1.2)的規(guī)模。其中，lg]是以2為底的對數(shù)，「?]表示剛剛大于括號值的整數(shù)。則橢球法的時間復(fù)雜度為OML)
Khachiar橢!球法的主要思想是：
根據(jù)線性規(guī)劃的強對偶定理，線性規(guī)劃問題式(1.2)可以轉(zhuǎn)為下列求可行域問題：
2)從球開始，這個球大到包括式（3l1)的所有可行集X不斷構(gòu)造一系列橢球，第k次迭代的橢球為Ek檢驗橢球中心&是否滿足約束條件；若滿
足則停止，否則利用割平面球的半橢球$Ek=EH
{aTA構(gòu)造新的橢球更新橢球Ek+1為包含半橢球的最小體積橢球。按照這種算法下去直到橢球中心位于目標(biāo)集內(nèi)，橢球中心即為問題式（31)的解;否則橢球體積太小以至不含問題式（31)的可行解。
由于Khachiarn橢球法從構(gòu)造包含可行域的大
的橢球出發(fā)，初始橢球體積有可能是天文數(shù)字，而且KhanCir橢球法利用K-K-T條件將原規(guī)劃問題轉(zhuǎn)
化為可行域求解問題，擴大了求解規(guī)模的同時加入了等式約束，使得可行集體積為零。雖然求解時，對等式進行攝動，可行集體積仍然很小。初始橢球體積太大，最終橢球（包含可行集的最小橢球）體積又幾乎為零，算法可能需要經(jīng)過非常大的迭代步數(shù)才能收斂。而且如果對偶問題無界則原問題不可行，因此當(dāng)計算結(jié)果無解時不能判斷是原問題無界呢還是原問題不可行。
不少研究者從加大每次迭代后橢球縮小比出發(fā)，提出了許多KhanCirn橢球法的改進算法:深切害J(deepeus)35-37、替代切割（surrogatecuts)381、
平行切割（paUMeus)|39-411等。最新成果是楊德莊等人提出的新的橢球法142,其優(yōu)點在于引入目標(biāo)束不等式及目標(biāo)不等式組成，與原橢球法相比一方面大大縮小了算法求解規(guī)模，另一方面擴大了可行集的體積。而且新算法中可行集切割及目標(biāo)切割交替進行，加速了橢球體積的縮小。不過令人失望的是即使最好的橢球法實施在計算上都難以與已有的單純形法相比。因此，實際中很少作為一般方法使用1431。
然而線性規(guī)劃的其他解法如單純形法、內(nèi)點法都需要從一個基礎(chǔ)解出發(fā)，然后確定迭代方向、迭代步長，因此每次迭代都需要計算目標(biāo)函數(shù)和所有約束函數(shù)。而橢球法的計算則簡單得多，理論上來說橢球法對于約束條件多的問題更有效。
4內(nèi)點法
1984年KamarH441提出了一個比Khanchian法好的多項式時間算法的內(nèi)點法，稱為Kamaikar法。由于該法引用了非線性規(guī)劃中的牛頓投影，因此又稱K_aka牧影法。
K_aka袪的提出在線性規(guī)劃領(lǐng)域具有極大的理論意義。與橢球法不同，這個新算法不僅在最壞情況下在時間復(fù)雜度上優(yōu)于單純形法，在大型實際問題中也有潛力與單純形法競爭。
這一方法的提出掀起了一股內(nèi)點法的研究熱潮。鑒于Kamaka?法的難讀性，一些研究學(xué)者?對Kamaika袪進行了適度的修改，使其簡便易讀。然而直接用該方法編程解題的測試表明，與目前基于單純形法的商用軟件相比，并沒有明顯的優(yōu)勢1491。因此很多研究者在Kamarka法的基礎(chǔ)上深入研究并提出了各種修正內(nèi)點法方法：仿射尺度法，對數(shù)障礙函數(shù)法，路徑跟蹤法算法等。
仿射比例調(diào)節(jié)法又分為原（Ptme)仿射比例調(diào)節(jié)法和對偶（Dua)方射比例調(diào)節(jié)法。原仿射比例調(diào)節(jié)法是從原問題出發(fā)，用一個仿射變換代替投影變換，把坐標(biāo)系從一個非負(fù)象限不是單純形）映射到其本身。該法1967年由前蘇聯(lián)學(xué)者Dkii5(0提出，但他的工作直到Bame1]等人再次研究該法后才被 法，另一方面作了完全的收斂性的證明。此外，1989年AdleP等發(fā)表了從原問題的對偶問題出發(fā)的對偶仿射比例調(diào)節(jié)法。
1986年G1531等人第一次把用于非線性規(guī)劃的對數(shù)障礙函數(shù)法用于線性規(guī)劃，并證明了對數(shù)障礙函數(shù)法和Kamarka投影法是等價的。以后的研究表明kamaikaf法實際上是廣義對數(shù)障礙函數(shù)法的一個特殊情形。由于其計算方面的優(yōu)越性，因此該法得到更多的研究和發(fā)展，該法也分為原對數(shù)障礙函數(shù)法和對偶對數(shù)障礙函數(shù)法。
原對偶（PrimaDua)各徑跟蹤法，實際上是原對偶障礙函數(shù)法，是MeidG19M541年提出的。他將包含對數(shù)障礙函數(shù)問題的障礙參數(shù)的唯一的最優(yōu)解所構(gòu)成的曲線稱為一條路徑或中心軌跡，當(dāng)障礙參數(shù)趨近零時，中心軌跡的極限即為原問題的最優(yōu)解。Kojma55'等最早（1987)提出收斂的算法，之后其他研究者對算法作了進一步的改進。為了找到起始可行解算法都要引進人工變量和附加約束條件，分別以適當(dāng)?shù)拇髷?shù)作系數(shù)和右端值，但算法對這些大數(shù)的選擇很敏感易導(dǎo)致算法中數(shù)值的不穩(wěn)定性。因此LustiTi等考慮使這些大數(shù)同時變?yōu)闊o窮大時坐標(biāo)增量的“極限可行方向”該方向只改變了求最優(yōu)解的方向，并不改變確定軌跡中心的方向，因而問題解法成為不可行問題原對偶牛頓法，其優(yōu)點是對初始解不必引入人工變量。該法也可用類似形式應(yīng)用于不可行原問題或?qū)ε紗栴}的方法中[57581。該法還便于處理有界變量問題。然而這個方法的計算復(fù)雜性尚未確知，沒有一般收斂的算法的證明。此外，在方法的改進方面，出現(xiàn)了全面收斂不可行內(nèi)點算法和預(yù)計改正法。
勢函數(shù)下降法有基于Gezaga等人提出的原勢函數(shù)下降法和Ye等人提出的原對偶勢函數(shù)下降法,計算復(fù)雜性都達到較好指標(biāo)。前者算法包含了兩個搜索方向，且所有仿射變換方法都采用了最速下降方向。這方面的改進還有Kajmm等的原對偶勢函數(shù)下降法等。由于上述勢函數(shù)下降法的各種算法是基于一系列嚴(yán)格的可行解上，方法都要求說是難以做到的。顯然直接采用不可行內(nèi)點算法是最好的解決辦法，因而Y，eTOdd和Misunol994年提
出了構(gòu)建“齊次自對偶問題”的方法，該齊次自對偶問題的解則可以用Kajjna等的原對偶勢函數(shù)下降法來解出。
在20世紀(jì)90年代內(nèi)點法理論發(fā)展成一個相當(dāng)成熟的原理。這一時期，對內(nèi)點法理論的一個主要貢獻來自YENesterov和八SNmirovski兩位數(shù)學(xué)家[69。他們創(chuàng)建的Self-Cocrdant函數(shù)理論，使基于對數(shù)障礙函數(shù)的線性規(guī)劃內(nèi)點法很容易推廣到更為復(fù)雜的優(yōu)化問題上，如非線性凸規(guī)劃、非線性互補、變分不等式、半定優(yōu)化以及二階錐優(yōu)化等。目前自協(xié)調(diào)函數(shù)形式主要有：對數(shù)函數(shù)和商函數(shù)形式。
今天，內(nèi)點法的研究熱點主要轉(zhuǎn)向于半定優(yōu)化、半定互補、非凸優(yōu)化及組合優(yōu)化問題上。
5自協(xié)調(diào)函數(shù)理論
自協(xié)調(diào)函數(shù)可謂是線性規(guī)劃算法研究的一個重大突破，也是我們后續(xù)研究的重點。自協(xié)調(diào)函數(shù)理論又名自協(xié)調(diào)障礙函數(shù)理論，為解線性和凸優(yōu)化問題提供了多項式時間內(nèi)點算法。根據(jù)自協(xié)調(diào)障礙函數(shù)的參數(shù)就可以分析內(nèi)點算法的復(fù)雜性。
自協(xié)調(diào)函數(shù)定義：
一個凸函數(shù)fR-R對定義域內(nèi)的任意x滿足Lf"(x)<2f(x3/2,我們就稱它為自協(xié)調(diào)函數(shù)。如果函數(shù)(Rn-R對于任意直線滿足自協(xié)調(diào)條件，我們稱函數(shù)§(9是自協(xié)調(diào)函數(shù)。
自協(xié)調(diào)函數(shù)理論的關(guān)鍵是算法的復(fù)雜性由自協(xié)調(diào)函數(shù)的兩個參數(shù)決定，只要這兩個參數(shù)可以推導(dǎo)出，則可求得算法的復(fù)雜性。
然而目前常用的自協(xié)調(diào)函數(shù)形式只有對數(shù)障礙函數(shù)形式:負(fù)對數(shù)函數(shù)：f=一Igx及負(fù)商函數(shù)加上負(fù)對數(shù)函數(shù)：f=xgx^lgP]。
最近CReas等m指出有些內(nèi)核函數(shù)盡管沒有全局自協(xié)調(diào)性，卻能在局部自協(xié)調(diào)。而且，CR?s
部值 也可以較好的求得算法的復(fù)雜性。基于CRQ0S的思想，金正靜等1711提出了一個局部自協(xié)調(diào)函數(shù)，其形式如下
自協(xié)調(diào)函數(shù)理論的提出，為我們分析算法復(fù)雜性帶來了極大的便利。然而以上的自協(xié)調(diào)函數(shù)形式都要求核函數(shù)為正，這為我們的研究帶來了極大的限制。那么自協(xié)調(diào)函數(shù)是否存在不要求核函數(shù)為正的形式為我們研究自協(xié)調(diào)函數(shù)提供了方向。
6結(jié)束語
除了邊界點算法，橢球法，內(nèi)點法，線性規(guī)劃還有有效集法等經(jīng)典算法、楊德莊教授的新算法及遺傳算法，神經(jīng)網(wǎng)絡(luò)等求解線性規(guī)劃的智能計算方法，有興趣者可參看有關(guān)文獻。
篇4
2.了解線性規(guī)劃問題的圖象法，并能用線性規(guī)劃的方法解決一些簡單的實際問題。
教學(xué)重點
1.二元一次不等式(組)表示的平面區(qū)域;
2.應(yīng)用線性規(guī)劃的方法解決一些簡單的實際問題。
教學(xué)難點
線性規(guī)劃在實際問題的應(yīng)用
高考展望
1.線性規(guī)劃是教材的新增內(nèi)容，高考中對這方面的知識涉及的還比較少，但今后將會成為新高考的熱點之一;
2.在高考中一般不會單獨出現(xiàn)，往往都是隱含在其他數(shù)學(xué)內(nèi)容的問題之中，就是說常結(jié)合其他數(shù)學(xué)內(nèi)容考查，往往都是容易題
知識整合
1.二元一次不等式(組)表示平面區(qū)域：一般地，二元一次不等式在平面直角坐標(biāo)系中表示直線某一側(cè)所有點組成的__________。我們把直線畫成虛線以表示區(qū)域_________邊界直線。當(dāng)我們在坐標(biāo)系中畫不等式所表示的平面區(qū)域時,此區(qū)域應(yīng)___________邊界直線，則把邊界直線畫成____________.
2.由于對在直線同一側(cè)的所有點，把它的坐標(biāo)代入，所得到實數(shù)的符號都__________，所以只需在此直線的某一側(cè)取一個特殊點，從的_________即可判斷>0表示直線哪一側(cè)的平面區(qū)域
3.二元一次不等式組是一組對變量x,y的__________，這組約束條件都是關(guān)于x,y的一次不等式，所以又稱為_____________;
4.(a,b是實常數(shù))是欲達到最大值或_________所涉及的變量x,y的解析式，叫做______________。由于又是x,y的一次解析式，所以又叫做_________;
5.求線性目標(biāo)函數(shù)在_______下的最大值或____________的問題，統(tǒng)稱為_________問題。滿足線性約束條件的解叫做_________，由所有可行解組成的集合叫做_________。分別使目標(biāo)函數(shù)取得____________和最小值的可行解叫做這個問題的___________.
典型例題
例1.(課本題)畫出下列不等式(組)表示的平面區(qū)域，
1)2)3)
4)5)6)
例2.
1)畫出表示的區(qū)域，并求所有的正整數(shù)解
2)畫出以A(3，-1)、B(-1，1)、C(1，3)為頂點的的區(qū)域(包括各邊)，寫出該區(qū)域所表示的二元一次不等式組，并求以該區(qū)域為可行域的目標(biāo)函數(shù)的最大值和最小值。
例3.1)已知，求的取值范圍
2)已知函數(shù)，滿足求的取值范圍
例4(04蘇19)制定投資計劃時，不僅要考慮可能獲得的盈利，而且要考慮可能出現(xiàn)的虧損。某投資人打算投資甲、乙兩個項目，根據(jù)預(yù)測，甲、乙項目可能的最大盈利率分別為100%和50%，可能的最大虧損率為30%和10%，投資人計劃投資金額不超過10萬元，要求確保可能的資金虧損不超過1.8萬元，問投資人對甲、乙兩個項目各投資打算多少萬元，才能使可能的盈利最大?
例5.某人承攬一項業(yè)務(wù)，需做文字標(biāo)牌4個，繪畫標(biāo)牌6個，現(xiàn)有兩種規(guī)格原料，甲種規(guī)格每張3m，可做文字標(biāo)牌1個，繪畫標(biāo)牌2個;乙種規(guī)格每張2m，可做文字標(biāo)牌2個，繪畫標(biāo)牌1個,求兩種規(guī)格的原料各用多少張，才能使總的用料面積最小?
例6.某人上午時乘摩托艇以勻速V海里/小時從A港出發(fā)到相距50海里的B港駛?cè)ィ缓蟪似囈詣蛩賅千米/小時自B港向相距300km的C市駛?cè)ィ瑧?yīng)該在同一天下午4點到9點到達C市。設(shè)汽車、摩托艇所需時間分別為小時，如果已知所要經(jīng)費P=(元)，那么V、W分別是多少時走得最經(jīng)濟?此時需花費多少元?
鞏固練習(xí)
1.將目標(biāo)函數(shù)看作直線方程,z為參數(shù)時，z的意義是()
A.該直線的縱截距B。該直線縱截距的3倍
C.該直線的橫截距的相反數(shù)D。該直線縱截距的
2。變量滿足條件則使的值最小的是()
A.(B。(3，6)C。(9，2)D。(6，4)
3。設(shè)式中變量和滿足條件則的最小值為()
A.1B。-1C。3D。-3
4。(05浙7)設(shè)集合A={是三角形的三邊長}，則A所表示的平面區(qū)域(不含邊界的陰影部分)是()
5。在坐標(biāo)平面上，不等式組所表示的平面區(qū)域的面積為()
A。B。C。D。2
6.(06全國ⅰ14)設(shè)，式中變量和滿足下列條件則的最大值為__________________;
篇5
1.常規(guī)問題
例1 （2012?山東）設(shè)變量x，y滿足約束條件x+2y≥2，
2x+y≤4，
4x-y≥-1，則目標(biāo)函數(shù)z=3x-y的取值范圍是（ ）
A.[-32，6] B.[-32，-1]
C.[-1，6] D.[-6，32]
解析 作出不等式組表示的可行域，如圖1陰影部分所示，作直線3x-y=0，并向上、下平移，由圖可得，當(dāng)直線過點A時，z=3x-y取最大值；當(dāng)直線過點B時，z=3x-y取最小值.由x+2y=2，
2x+y=4，解得A（2，0）；由2x+y=4，
4x-y=-1，解得B（12，3）.
所以zmax=3×2-0=6，zmin=3×12-3=-32.所以z=3x-y的取值范圍是[-32，6].
2.非線性目標(biāo)函數(shù)問題
例2 （2011?廣東）已知平面直角坐標(biāo)系xOy上的區(qū)域D由不等式組0≤x≤2，
y≤2，
x≤2y給定.若M（x，y）為D上的動點，點A的坐標(biāo)為（2，1）則z=OM?OA的最大值為（ ）.
A.42 B.32 C.4 D.3
解析 如圖2作出區(qū)域D，目標(biāo)函數(shù)z=2x+y過點B（2，2）時取最大值，故z的最大值為2×2+2=4，
故選C.
例3 （2012?北京）設(shè)不等式組0≤x≤2，
0≤y≤2表示的平面區(qū)域為D，在區(qū)域D內(nèi)隨機取一個點，則此點到坐標(biāo)原點的距離大于2的概率是（ ）.
A.π4 B.π-22 C.π6 D. 4-π4
解析 如圖3所示，正方形OABC及其內(nèi)部是不等式組所表示的區(qū)域D，且區(qū)域D的面積為4，而陰影部分表示的是區(qū)域D內(nèi)到坐標(biāo)原點的距離大于2的區(qū)域.因此滿足條件的概率是4-π4.
3.含參的線性規(guī)劃問題
例4 （2011?湖南）設(shè)m>1，在約束條件y≥x，
y≤mx，
x+y≤1下，目標(biāo)函數(shù)z=x+my的最大值小于2，則m的取值范圍為.
解析 目標(biāo)函數(shù)z=x+my可變?yōu)閥=-
1mx+zm.
因為m>1，所以-1
如圖4，當(dāng)目標(biāo)函數(shù)經(jīng)過點P（1m+1，mm+1）時取最大值，
所以1m+1+mm+11，得1
4.平面區(qū)域問題
例5 （2013安徽）在平面直角坐標(biāo)系中，O是坐標(biāo)原點，兩定點A，B滿足
|OA|=|OB|=OA?OB=2，則點集{P|OP=λOA+μOB，|λ|+|μ|≤1，λ，μ∈R}所表示的區(qū)域的面積是（ ）.
A.22 B.23 C.42 D.43
解析 若A，B，C三點共線，P是線外一點，則PA=λPB+μPC，其中λ+μ=1.
在本題中，OA?OB=|OA||OB|cosθ=4cosθ=2θ=π3.
建立直角坐標(biāo)系，設(shè)A（2，0），B（1，3）.則當(dāng)λ≥0，μ≥0，λ+μ≤1時，P在三角形OAB內(nèi)（含邊界）.
根據(jù)對稱性，所求區(qū)域的面積S=4×三角形OAB的面積=43.
A.2a B.12a C.4a D.4a
解析 如果用常規(guī)方法，顯然比較麻煩，有點“小題大做”了.由于直線的位置沒有特殊要求，因此可選取一個特殊位置，在此位置處求1p+1q的值即可.
篇6
關(guān)鍵詞：線性規(guī)劃思想；解題；應(yīng)用
中圖分類號：G427 文獻標(biāo)識碼：A文章編號：1992-7711（2012）03-076-2
線性規(guī)劃問題以二元一次不等式所表示的平面區(qū)域內(nèi)容為基礎(chǔ)，它將代數(shù)與幾何，數(shù)學(xué)與實際巧妙地聯(lián)系起來，線性規(guī)劃實際上就是以數(shù)學(xué)知識為工具，來研究在一定的人、財、物、時、空等資源條件下，如何精打細(xì)算巧妙安排以最少的資源來取得最大的經(jīng)濟效益。然而中學(xué)所學(xué)的線性規(guī)劃只是規(guī)劃論中極小的一部分，但這部分內(nèi)容體現(xiàn)了數(shù)學(xué)的工具性、應(yīng)用性，同時滲透了化歸、數(shù)形結(jié)合的思想，并且為學(xué)生今后解決實際問題提供了一種重要的解題方法――數(shù)學(xué)模型法，所以掌握好這部分內(nèi)容非常重要。
一、線性規(guī)劃的內(nèi)涵
線性規(guī)劃是數(shù)學(xué)規(guī)劃的一部分，它研究目標(biāo)函數(shù)在約束條件下的最大值和最小值問題，即要尋找既滿足約束條件又使得目標(biāo)函數(shù)達到最優(yōu)的解，要一下子處理可能比較困難，于是提出“可行解”這一概念，將求解線性規(guī)劃的問題分解為兩步，第一步先求“可行解”，第二步再求“最優(yōu)解”。從而分散了難點，找到了解決問題的方法。雖然中學(xué)所學(xué)的線性規(guī)劃只是規(guī)劃論中極小一部分，但這部分內(nèi)容體現(xiàn)了數(shù)學(xué)的工具性、應(yīng)用性，同時滲透了化歸、數(shù)形結(jié)合的思想，能夠?qū)嶋H問題轉(zhuǎn)化為數(shù)學(xué)問題，抽象解決一些簡單的線性規(guī)劃應(yīng)用問題的基本思路和主要方法。
二、線性規(guī)劃思想解題
利用線性規(guī)劃的思想解題主要是依據(jù)給定的條件，把整個題目的有關(guān)約束條件和所求目標(biāo)函數(shù)用數(shù)學(xué)關(guān)系和邏輯關(guān)系表示出來，運用化規(guī)，數(shù)形結(jié)合等思想，主要通過圖解法的方法求解，得出最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值。下面舉例說明幾種用的線性規(guī)劃的方法在實際解題中的應(yīng)用。
(一)向量問題轉(zhuǎn)化為線性規(guī)劃問題
向量是平面幾何的基礎(chǔ)，線性規(guī)劃作為連接點巧妙地將幾何問題與代數(shù)問題聯(lián)結(jié)起來。
例1 已知在平面直角坐標(biāo)系中，O(0,0)，M(1,12)，N(0,1)，Q(2,3)，動點P(x,y)滿足不等式0≤OP•OM≤1，0≤OP•ON≤1，則W=OP•OQ的最大值是多少？
分析 因為O(0,0)，M(1,12)，N(0,1)，Q(2,3)，所以 0≤OP•OM≤1,0≤OP•ON≤1，0≤x+12y 圖1
≤1,0≤y≤1，W=OP•OQ=2x+3y。
本例轉(zhuǎn)化為在線性的約束條件
x+12y≤1,0≤y≤1,x+12y≥0
下，求線性目標(biāo)函數(shù)W=OP•OQ=2x+3y的最大值題。可作出如圖的可行域，顯然在點T的坐標(biāo)是最優(yōu)解。
由
x+12y=1,y=1
得
T(12,1),
所以
Wmax=2×12+3×1=4。
注 本題將平面向量與線性規(guī)劃巧妙地結(jié)合起來，真正體現(xiàn)了在知識交匯點處命題的高考指導(dǎo)思想。解決這類問題的關(guān)鍵是將已知的不等式組準(zhǔn)確地轉(zhuǎn)化為二元一次不等式組并準(zhǔn)確畫圖，然后求最值。
(二)三角問題轉(zhuǎn)化為線性規(guī)劃問題
求解三角形個數(shù)問題，常規(guī)解法是根據(jù)三角形三邊關(guān)系，利用分類計數(shù)原理求解，而用線性規(guī)劃方法求解，則別具一格［2］。
例2 三邊長均為整數(shù)，且最大邊長為11的三角形個數(shù)為多少？ 圖2
解 設(shè)三角形另兩邊長分別x,y(x,y∈N*),
根據(jù)題意得
x+y>11,x≤11,y≤11,x≥y,x,y∈N*
轉(zhuǎn)化為在此約束條件下求整數(shù)點的問題，
如圖所示可得 1+3+5+7+9+11=36，
故三角形的個數(shù)為36個。
注 本題巧妙地將線性規(guī)劃問題運用到三角形的問題中，體現(xiàn)了線性規(guī)劃廣泛運用的特點。求解這類題目關(guān)鍵是利用三角形兩邊之和大于第三邊的關(guān)系，轉(zhuǎn)換為標(biāo)準(zhǔn)的線性規(guī)劃問題，其中，在求整數(shù)可行解時，也就是可行域中橫坐標(biāo)和縱坐標(biāo)都是整數(shù)的點，可先畫出滿足線性規(guī)劃約束條件的平面區(qū)域，然后再找整數(shù)點。
(三)與函數(shù)或不等式結(jié)合,求取值范圍問題
函數(shù)與不等式是高中數(shù)學(xué)的基本知識點，求取值范圍也是常見地類型，結(jié)合函數(shù)或不等式的性質(zhì)，運用數(shù)形結(jié)合的思想把問題轉(zhuǎn)化為線性規(guī)劃的問題解決，即形象又直觀［3］。
例3 已知f(x)=ax2+bx，且1≤f(－1)≤2，2≤f(1)≤4，求f(－2)的取值范圍。
分析 對這個問題，可以用f(－1)，f(1)表示f(－2)，再由f(－1)，f(1)的范圍，結(jié)合不等式的性質(zhì)求出f(－2)的取值范圍。我們可以轉(zhuǎn)化為線性規(guī)劃問題求解。 圖3
解 1≤f(－1)≤2,2≤f(1)≤4,得1≤a－b≤2,2≤a+b≤4。(1)
目標(biāo)是求f(-2)=4a－2b的取值范圍。
作出線性約束條件（1）下的可行域四邊形ABCD，
如圖3A(2,0),B(3,1),C(52,32),D(32,12)不難得到，
當(dāng)直線4a－2b= f(-2)經(jīng)過點B和D 時，
f(－2)分別取得最大值最小值10和5。
所以 f(-2)∈［5,10］。
注 對于這個問題，很多學(xué)生常犯如下錯誤:由題設(shè)
1≤a－b≤2,2≤a+b≤4,
得
32≤a≤3,0≤b≤32。 (2)
又因f(-2)=4a－2b，所以3≤f(－2)≤12。
線性規(guī)劃中的可行域可以直觀形象地幫助我們可看到此種解法的錯誤之處。作出（2）式表示的可行域如圖4，可清楚地看到圖3中的可行域是圖4的一部分，即由（1）到（2）后范圍擴大了。
(四)線性規(guī)劃在函數(shù)問題中的應(yīng)用
對于某些與函數(shù)有關(guān)的問題，若善于利用已知條件構(gòu)造線性約束條件，將問題換為線性規(guī)劃問題求解，有時能起到事半功倍的效果。
例4 已知函數(shù)f(x)=x3+ax2+bx+c在區(qū)間［－1,2］上是減函數(shù)，求a+b的最大值。
分析 根據(jù)線性規(guī)劃思想，可視t=a+b為目標(biāo)函數(shù)，再由已知條件可知a,b的約束條件，即由f(x)=x3+ax2+bx+c在區(qū)間［－1,2］上是減函數(shù)，得出目標(biāo)函數(shù)的可行域。這樣，求a+b的最大值就轉(zhuǎn)化為在可行域中求目標(biāo)函數(shù)的最大值。
圖4
解 由題意知f′(x)=3x2+2ax+b,在［－1,2］恒有f′(x)≤0，
則
f′(－1)≤0,f′(2)≤0
即
3－2a+b≤0,12+4a+b≤0。
令t=a+b，其中a,b滿足上述約束條件，作出這個約束條件下的可行域,如圖5所示，當(dāng)直線t=a+b 過點 A(－32,－6)時，tmax=－152。
容易驗證:a=－32,b=－6 時，f(x)在區(qū)間［－1,2］上是減函數(shù)，所以a+b的最大值為－152。
注 本例題由函數(shù)的單調(diào)性，運用導(dǎo)數(shù)列出不等式即得出目標(biāo)函數(shù)的可行域，將本例轉(zhuǎn)化為求解目標(biāo)函數(shù)的最大值，若直接運用函數(shù)的性質(zhì)求解，顯得繁瑣且容易將范圍擴大,因此，運用線性規(guī)劃思想求解此類最值問題時既簡捷又方便。
(五)與解析幾何結(jié)合，求參數(shù)的范圍問題
線性規(guī)劃體現(xiàn)的是數(shù)形結(jié)合的思想，理解了這一點，則賦予了線性規(guī)劃知識更廣泛、更深刻的意義。在線性約束條件下，凡結(jié)論具有一定的幾何意義的問題均可類比解決。
例5 已知線段AB的端點為A(1,3)、B(5,2)，若動直線l:x+ty=－1t與線段AB相交，求參數(shù)t的取值范圍。
圖5
分析 直線l可化為x+ty+1t=0。因線段AB與直線l有公共點。
由線性規(guī)劃知識得
(1+3t+1t)(5+2t+1t)≤0,
而 t2>0，所以化為
(3t2+t+1)(2t2+5t+1)≤0。
又3t2+t+1=3(t+16)2+1112>0,
所以再化為
2t2+5t+1≤0,
解得
－5－174≤t≤－5+174。
注1 直角坐標(biāo)系內(nèi)有兩點P1(x1,y1),P2(x2,y2)直線l:Ax+By+C=0，直線l和線段P1P2有公共點的充要條件是(Ax1+By1+C)(Ax2+By2+C)≤0。
注2 按傳統(tǒng)解法是從直線斜率出發(fā)，由動直線引出定點，通過對直線系探討等決與線段有公共點的問題。而本題難以確定動直線所過定點，傳統(tǒng)方法無法用上。現(xiàn)在利用線性規(guī)劃知識構(gòu)建不等式，就可以使問題得到圓滿解決。
(六)概率問題轉(zhuǎn)化為線性規(guī)劃問題
概率是中學(xué)數(shù)學(xué)教材中新增內(nèi)容，它在理論與實際生活中都有重要意義，在求解某些概率問題的過程中，若思路受阻，或很難找到突破口，可以借助坐標(biāo)和一系列的等價變換，將一次試驗可能結(jié)果的全體用某一圖形的面積G來代替，然后將所求事件包含的結(jié)果數(shù)以線性約束條件的形式展現(xiàn)出來，若其相應(yīng)的可行域的面積為g，則所求事件的概率為gG。
例6 兩人相約9點到10點在同一地點會面，早到的人要等另一個人20分鐘才能離開，試求兩人會面的概率。
分析 以x,y分別代表兩人到會面地點的時刻，則兩人會面的充要條件為
|x－y|≤20,x,y∈［0,60］,即x－y≤20,y－x≤20,0≤x≤60,0≤y≤60
在直角坐標(biāo)系中畫出x,y的可行域（如圖6的陰影部分）。顯然兩人可能到達的時間為圖中正方形內(nèi)（含邊界）的點，陰影部分表示能會面的點，從而可利用其面積之比得概率為:P=602－12×40×40×2602=59。
注 這是一道幾何概率問題，用線性規(guī)劃的思想可直觀簡捷的求解這類問題。本例題中有明確的不等式關(guān)系，可將其概括成不等式組，畫可行域，用線性規(guī)劃的思想解題。
線性規(guī)劃是數(shù)學(xué)規(guī)劃中理論較完整，方法較成熟，應(yīng)用廣泛的一個分支，它能解決許多方面的實際問題。它是直線方程的一個簡單應(yīng)用，也是數(shù)形結(jié)合數(shù)學(xué)思想的很好體現(xiàn)。文章是在了解線性規(guī)劃的意義，以及線性約束、線性目標(biāo)函數(shù)、可行解、可行域、最優(yōu)解等概念，并且熟練掌握線性規(guī)劃的圖解法的基礎(chǔ)上，運用數(shù)形結(jié)合的思想解決有關(guān)向量、函數(shù)、不等式、解析幾何等方面的問題，使解決這些問題變得更加簡便，同時也有助于數(shù)學(xué)思維能力的提高。
［參考文獻］
［1］教育部.普通高中數(shù)學(xué)課程標(biāo)準(zhǔn)(實驗).人民教育出版社,2003.
［2］吳成強.線性目標(biāo)函數(shù)最優(yōu)解的探求.中學(xué)生理科月刊,2003（5）.
篇7
[關(guān)鍵詞]非線性規(guī)劃 懲罰函數(shù)法 磨光法
一、引言
懲罰函數(shù)法是求解約束型非線性規(guī)劃的有效算法之一。但對具有不等式約束的非線性規(guī)劃問題,常用的簡單罰函數(shù)法存在缺陷。由于一般的簡單罰函數(shù)在可行域邊界點上不可微,因此給求解無約束優(yōu)化問題的編程計算帶來不方便。近年來,關(guān)于處理不可微優(yōu)化問題的算法很多,但大多數(shù)算法是引入次梯度的迭代算法,理論推導(dǎo)復(fù)雜,局限性比較大,編程計算仍然不便。受文獻[1-2]利用磨光參數(shù)處理不可微點技術(shù)的啟發(fā),提出求解約束型非線性規(guī)劃的磨光懲罰函數(shù)法。文獻[1]利用磨光參數(shù)獲得了非光滑最優(yōu)控制的差分解,文獻求解了具有互補約束條件的優(yōu)化問題,同樣引進了磨光參數(shù)將不可微點近似處理為可微函數(shù),逐步逼近真解。磨光懲罰函數(shù)法的基本思想是,在簡單罰函數(shù)法的基礎(chǔ)上利用磨光參數(shù)將非光滑罰函數(shù)近似為光滑函數(shù),進一步采用可微函數(shù)的常規(guī)算法獲得包含磨光參數(shù)的近似解,通過逐步細(xì)磨獲得最優(yōu)解。該方法避開了罰函數(shù)的不可微性,使編程求解更加初等化,簡單化。
二、簡單罰函數(shù)法和磨光參數(shù)
考慮具有不等式約束的非線性規(guī)劃問題:
Min f(x) (1)
(2)
其中f(x),gi(x)是Rn上的連續(xù)的可微函數(shù)。實現(xiàn)這類約束問題求解的途徑是由目標(biāo)函數(shù)和約束函數(shù)組成輔助函數(shù),把原來的約束問題轉(zhuǎn)換成為極小化輔助函數(shù)的無約束問題。
定義輔助函數(shù)為下列形式:
是滿足下列條件的連續(xù)函數(shù)
其中,的典型取法為,其中β≥1均為給定的常數(shù),通常取為2。構(gòu)造增廣目標(biāo)函數(shù),得到外點罰函數(shù)算法[4-5](SUMT)。
算法1:(SUMT)
三、磨光罰函數(shù)法及其收斂性
值得說明的是,算法2:(S- SUMT)得到的解對應(yīng)的目標(biāo)值與算法1(SUMT)得到的解對應(yīng)的目標(biāo)值相同,但最優(yōu)解不一定相同。然而,如果問題(1)(2)的解唯一,則兩算法得到的最優(yōu)解相同。
四、數(shù)值例子
考慮約束型非線性規(guī)劃問題
五、結(jié)束語
由算例可以看出隨著磨光參數(shù)的減小,在同樣的懲罰因子下,其解逐步趨近于精確解。因此本文提出的磨光罰函數(shù)法(S- SUMT)是可執(zhí)行的,有效的。更重要的是該算法避開了簡單罰函數(shù)不可微的缺陷,使得原問題連續(xù)可微,有利于編程實現(xiàn)。
參考文獻:
[1]Xiaojun Chen. Finite difference smoothing solutions of nonsmooth constrained optimal control problem[J].Numerical Functional Analysis and Optimization, 2005,26(1):49-68.
[2]Xinmin Hu, Daniel Ralph. Convergence of a penalty method for mathematical programming with complementarity constraints[J].Journal of Optimization and application,2004,123(2):365-390.
[3]Scholtes,S. Convergence Properties of a Regularization scheme for Mathematical Programs with Complementarity Constraints[J].SIAM Journal on Optimization,2001,11(4):918-936.
篇8
關(guān)鍵詞：線性規(guī)劃 ；移動Agent
中圖分類號：TP18文獻標(biāo)識碼：A文章編號：1009-3044(2011)28-6967-02
Based on Mobile Agent of Linear Programming model
HE Bin
(Computer Science Dept. of Ningxia University, Yinchuan 750021, China)
Abstract: This article discusses a mobile agent based on linear programming solving solutions to improve the calculation efficiency, has the nice practical significance.
Key words: linear programming; mobile agent
1 緒論
整數(shù)線性規(guī)劃問題的求解已廣泛的應(yīng)用到工程實踐中。傳統(tǒng)的求解整數(shù)線性規(guī)劃方法有：枚舉法、割平面法以及分枝定界法。其中分枝定界法是最為常用的方法[1]。
分枝定界法是20世紀(jì)60年代初期由Land Doid 和Dakin等人提出的，是一種系統(tǒng)化的解法，以一般線性規(guī)劃的單純形法解得最佳解，然后將非整數(shù)值的解分割成最接近的兩個整數(shù)，分列條件，加入原問題中，如此分枝成兩個子問題分別求解，這樣便可求得目標(biāo)函數(shù)值的上界或下界，從其中尋得可行解。 可見本算法能較快的求得最佳解，且平均速度快，但要存儲很多葉子結(jié)點的限界和對應(yīng)的耗費矩陣，花費很多內(nèi)存空間，計算效率較低。本文探討一種基于演化agent的解決方案。
2 基于移動Agent的整數(shù)線性規(guī)劃
移動agent是具有移動性的智能agent，能夠自行決定在網(wǎng)絡(luò)的各個節(jié)點之間移動，代表其他實體（人或其他agent）進行工作的一種軟件實體。移動Agent技術(shù)是分布式技術(shù)與Agent技術(shù)相結(jié)合的產(chǎn)物，它除了具有agent最基本的特性：自主性、反應(yīng)性、能動性、通信性以外，還具有移動性[2]。這些特有的屬性和技術(shù)優(yōu)勢使其在諸多領(lǐng)域得到了科學(xué)的應(yīng)用，特別適合于解決傳統(tǒng)方法中代價過于昂貴，或者解決不了的問題。
2.1 agent模型
定義一個agent，它是具有目標(biāo)、動作、通信等行為功能的復(fù)合體，用符合T表示。agent的行為描述如下：
1）復(fù)制
一個agent T可以復(fù)制成兩個子agent T1、T2，我們稱T為父agent。它的兩個子agent與其具有同樣的目標(biāo)，但所處的問題環(huán)境有所改變。
2）動作
Agent會根據(jù)其所處的問題環(huán)境不停地計算其目標(biāo)，直到成功或者到達中止條件。
3）通信
設(shè)環(huán)境E中是agent T的計算環(huán)境，那么agent T會在這個環(huán)境中進行計算，直到達到其目標(biāo)，如果目標(biāo)不能達到，agent T會復(fù)制成agent T1、T2來繼續(xù)計算其目標(biāo)，此時環(huán)境E也會被分成E1 、E2（E的兩個子環(huán)境），它們就分別是T1、T2的計算環(huán)境。
T1、T2分別在E1、E2中計算其目標(biāo)，如果它們的計算達到目標(biāo)，則將計算結(jié)果發(fā)送給agent T，否則將會繼續(xù)復(fù)制，繼續(xù)計算下去。
2.2 求解算法
這個算法的基本思想是：將松弛問題Q作為agent T的目標(biāo)和計算環(huán)境，T首先按單純形法來求解，如果計算的結(jié)果有最佳整數(shù)值，則問題得到求解。否則，T將復(fù)制成兩個子agent T1、T2分別對應(yīng)與兩個子問題B1、B2繼續(xù)求解，如此下去，以獲得問題的最優(yōu)整數(shù)解。算法可描述如下：
1）首先把整數(shù)線性規(guī)劃問題中得目標(biāo)函數(shù)以及約束條件作為agent T的目標(biāo)和環(huán)境賦給它，并且定義變量p（p首先不賦予值）；
2）agent T首先求解松弛問題，如果松弛問題的最優(yōu)解全為整數(shù)，那么把這些最優(yōu)解賦值給p，轉(zhuǎn)去執(zhí)行（6），如果松弛問題沒有可行解，就直接轉(zhuǎn)去執(zhí)行6），否則將執(zhí)行下一步；
3）若在求解過程中某個變量xi的解為分?jǐn)?shù)值kj，那么就分別求得小于 kj下的最大整數(shù)[kj]和大于的最小整數(shù)[kj]+1，agent T 將復(fù)制成兩個子agent T1、T2。這兩個子agent的計算目標(biāo)與agent T相同，但其環(huán)境分別為原來T的計算環(huán)境加上約束條件xi=[kj]+1。
4）agent T1、T2 分別在其所處的環(huán)境里計算它們的目標(biāo)，如果最優(yōu)整數(shù)解已求出，則若p沒有值，那么將最優(yōu)整數(shù)解賦值給p，否則，p min（p，最優(yōu)值）；
5）當(dāng)T1、T2 中有非整數(shù)可行解者Tj 時，如果p沒有值或所得的非整數(shù)可行解小于p，那么將Tj 的解賦值給T，轉(zhuǎn)到（3）繼續(xù)執(zhí)行；
6）如果p已有值，則輸出p，否則就輸出此整數(shù)線性規(guī)劃問題沒有可行解。
2.3 模型的實現(xiàn)
可選用日本IBM公司開發(fā)的Aglet平臺，該平臺是目前最為成功和全面的移動平臺[3]。Aglet系統(tǒng)可以根據(jù)需要創(chuàng)建agent T ；復(fù)制agent T1、T2，將它們分派到各自的環(huán)境中執(zhí)行；也能執(zhí)行暫停、清除。
2.4 算法的時間復(fù)雜度
在微機上，采用一般的單純形法來求解整數(shù)線性規(guī)劃問題，其時間復(fù)雜度為O (n)；而用本文的模型進行求解，它的時間復(fù)雜度為O (log n)，可見實現(xiàn)的時間復(fù)雜度較低。
3 結(jié)束語
通過編程實現(xiàn)，本文探討的模型取得了很好的效果。Agent可以同時復(fù)制，故求解過程具有并行性；并且程序?qū)崿F(xiàn)的時間復(fù)雜度較低，求解過程基于目標(biāo)驅(qū)動，提高了計算效率。
參考文獻：
[1] 張干宗.線性規(guī)劃[M].武漢:武漢大學(xué)出版社,2007.
篇9
關(guān)鍵詞：非線性規(guī)劃；企業(yè)營銷；Lingo
中圖分類號：F274 文獻標(biāo)志碼：A 文章編號：1673-291X（2016）04-0059-02
一、非線性規(guī)劃數(shù)學(xué)模型
對實際非線性規(guī)劃問題做定量分析，首先要選定適當(dāng)?shù)哪繕?biāo)變量和決策變量，并建立起目標(biāo)變量與決策變量之間的函數(shù)關(guān)系，即目標(biāo)函數(shù)，并建立約束條件。非線性規(guī)劃問題的一般數(shù)學(xué)模型可表述為求未知量x1，x2...，xn，使?jié)M足約束條件：
gi（x1，...，xn）≥0，i=1，...，m
hj（x1，...，xn）=0，j=1，...，p
并使目標(biāo)函數(shù)f（x1，...，xn）達到最小值（或最大值）。其中g(shù)i（x1，...，xn）和hj（x1，...，xn）均是定義在n維向量空間Rn上的某子集D（定義域）上的實值函數(shù)，且f（x1，...，xn）、gi（x1，...，xn）、hj（x1，...，xn）中至少有一個是非線性函數(shù)。記x=（x1，...，xn），則上述模型可以簡記為：
minf（x）或maxf（x）
s.t.gi（x）≥0，i=1，...，mhj（x）=0，j=1，...，p
定義域D中滿足約束條件的點稱為問題的可行解，全體可行解所組成的集合稱為問題的可行集。對于一個可行解x*，如果存在x*的一個領(lǐng)域，使目標(biāo)函數(shù)在x*處的函數(shù)值f（x*）不大于（或不小于）該領(lǐng)域中任何其他可行解處的函數(shù)值，則稱x*為問題的局部最優(yōu)解，如果f（x*）不大于（或不小于）一切可行解處的目標(biāo)函數(shù)值，則稱x*為該模型的整體最優(yōu)解。
二、應(yīng)用舉例
（一）案例介紹
宏宇電器公司計劃生產(chǎn)三類10種小家電，其中包括：熱水壺（1.5升、1.8升、2升）、豆?jié){機（0.9升、1.1升、1.3升）、電飯煲（2升、2.5升、3升、3.5升）。三類小家電的年最大生產(chǎn)能力分別為：熱水壺5萬個、豆?jié){機6.5萬個、電飯煲6.2萬個。制定使公司利潤最大的的生產(chǎn)、銷售方案（數(shù)據(jù)來源：2010年東北三省數(shù)學(xué)建模聯(lián)賽A題）。
（二）案例求解
公司的收入和支出來自計劃內(nèi)銷售和計劃外銷售兩部分，公司所承擔(dān)的計劃內(nèi)成本應(yīng)該根據(jù)計劃內(nèi)的產(chǎn)品數(shù)量占總產(chǎn)品數(shù)量的比值確定，即：
公司承擔(dān)的生產(chǎn)成本=總成本×
公司利潤的表達式：
公司總利潤=已簽約合同的銷售額+意向簽約合同的銷售額+計劃外營銷部上繳利潤-計劃內(nèi)成本-經(jīng)費
第1種小家電的銷售額與訂購量的函數(shù)關(guān)系為：
f1（x）=-0.26713x2+11.418x+1.3873
同理可以得到，第2至10種家電銷售額與其訂購量的函數(shù)關(guān)系。記fi（x）為第i種小家電的銷售額，i=1，2，...，10，x代表訂購量。
同理，記gi（y）為計劃外銷售第i種小家電營銷部向企業(yè)繳納的利潤，i=1，2，...，10，y代表銷售量；記mi（z）為第種小家電的經(jīng)費，i=1，2，...，10，z代表產(chǎn)量；記ni（y）為第種小家電的經(jīng)費，i=1，2，...，10，y代表銷售量；記ni（y）為第i種小家電的經(jīng)費，i=1，2，...，10，y代表產(chǎn)量。
1.每個產(chǎn)品的訂購量不能超過客戶的最大意向簽約量。xij≤Mij，其中xij代表第j個顧客對第i種小家電的訂購量，i=1，2，...，10，j=1，2，3，4，5，Mij代表第j個客戶對第i種產(chǎn)品的最大簽約量。
2.計劃外產(chǎn)品的訂購量不能超過其最大可能訂購量。xi6≤Ni6，其中xi6代表計劃外的第i種小家電的訂購量，i=1，2，...，10，Ni6代表計劃外第i種產(chǎn)品的最大可能訂購量。
3.所有產(chǎn)品的訂購量均不能為負(fù)數(shù)。xij≥0，i=1，2，...，10，j=1，2，3，4，5，6。
4.各類產(chǎn)品的訂購量不能與超過其最大生產(chǎn)能力。∑3 i=1∑6 j=1xij≤12，∑6 i=4∑6 j=1xij≤20，∑3 i=7∑6 j=1xij≤19。
運用Lingo軟件得到最大值t=697.33萬元，目標(biāo)函數(shù)取得最大值時的各變量取值。為使公司利潤達到最大時的生產(chǎn)方案為：1至10種小家電分別對應(yīng)的生產(chǎn)數(shù)量（千件）為：11.59、24.54、13.87、14、29、20、12、24.3、14.3、8.4。
篇10
回答 含參線性規(guī)劃問題一般可分為兩類，一類是約束條件含參，另一類是目標(biāo)函數(shù)含參. 這兩類問題的解題原理是相同的，關(guān)鍵是理解參數(shù)的本質(zhì)，并認(rèn)清參數(shù)變化對直線位置產(chǎn)生的影響.下面，我們就以提問中的問題為例進行分析.
我們首先想到作出直線x+3y-3=0，2x-y-3=0與x-my+1=0，確定可行域.但怎么確定含參直線x-my+1=0的具置呢？令y=0，解得x=-1，可知直線x-my+1=0必過定點（-1，0）.當(dāng)m≠0時，直線x-my+1=0的斜率k=≠0；當(dāng)m=0時，直線x-my+1=0的斜率不存在，故直線x-my+1=0可看作繞定點（-1，0）旋轉(zhuǎn)且不與x軸重合的動直線，參數(shù)m就是控制直線x-my+1=0的位置的關(guān)鍵要素.當(dāng)參數(shù)m變化時，不等式組x+3y-3≥0，2x-y-3≤0，x-my+1≥0表示的可行域也會隨之變化.
在解題時，我們不妨以靜制動，先設(shè)m為一個任意的常數(shù)，作出一個確定的可行域，然后以動馭靜，讓含參直線旋轉(zhuǎn)起來，在旋轉(zhuǎn)中尋找滿足“x+y的最大值為9”的參數(shù)m.
如圖1所示，在直角坐標(biāo)系中作出直線l1：x+3y-3=0，l2：2x-y-3=0，l3：x-my+1=0的圖象.
注意：過點（-1，0）作直線l3：x-my+1=0的圖象（以虛線表示）時，可以對參數(shù)m取任一常數(shù).
記不等式組x+3y-3≥0，2x-y-3≤0，x-my+1≥0所表示的平面區(qū)域為Ⅰ（如圖1所示）. 把條件“x+y的最大值為9”等價轉(zhuǎn)化為不等式x+y≤9，作直線l4：x+y=9的圖象，記不等式x+y≤9所表示的平面區(qū)域為Ⅱ.判斷平面區(qū)域Ⅰ與平面區(qū)域Ⅱ的位置關(guān)系.由題意可知x+y的最大值為9，所以平面區(qū)域Ⅰ應(yīng)恒在平面區(qū)域Ⅱ的下方.
在圖1中，平面區(qū)域Ⅰ不恒在平面區(qū)域Ⅱ的下方. 將直線l3：x-my+1=0繞定點（-1，0）沿逆時針方向旋轉(zhuǎn)，平面區(qū)域Ⅰ不恒在平面區(qū)域Ⅱ的下方，不滿足題意.如圖2所示，將直線l3繞定點（-1，0）沿順時針方向旋轉(zhuǎn)，使平面區(qū)域Ⅰ恒在平面區(qū)域Ⅱ的下方，但此時x+y的最大值小于9，所以直線l3的位置也不滿足題意.
由此可見，要使x+y=9成立，區(qū)域Ⅰ和區(qū)域Ⅱ的交點必須在直線x+y=9上.
繼續(xù)旋轉(zhuǎn)直線l3：x-my+1=0.如圖3所示，當(dāng)它經(jīng)過直線l1：x+3y-3=0與l4：x+y=9的交點A（12，-3）時，平面區(qū)域Ⅰ不恒在平面區(qū)域Ⅱ的下方，所以也不符合題意.
綜上所述，如圖4所示，當(dāng)直線l3：x-my+1=0過直線l2：2x-y-3=0與l4：x+y=9的交點B（4，5）時，平面區(qū)域Ⅰ恒在平面區(qū)域Ⅱ的下方，且x+y取到最大值9，滿足題意.
由l3：x-my+1=0過點（4，5），可解得m=1.
在約束條件含參的線性規(guī)劃問題中，參數(shù)的本質(zhì)就是控制含參直線位置的關(guān)鍵要素.我們可以先給參數(shù)取任意一個常數(shù)，即先把含參問題看成一個不含參問題，這樣就能大致作出約束條件所表示的平面區(qū)域.再把已知最值的線性目標(biāo)函數(shù)轉(zhuǎn)化為一個不等式，作出該不等式表示的平面區(qū)域.根據(jù)題意平移或旋轉(zhuǎn)含參直線的位置，并判斷這兩個平面區(qū)域的位置關(guān)系，求出參數(shù)值.
