導(dǎo)言：作為寫(xiě)作愛(ài)好者，不可錯(cuò)過(guò)為您精心挑選的10篇線性規(guī)劃，它們將為您的寫(xiě)作提供全新的視角，我們衷心期待您的閱讀，并希望這些內(nèi)容能為您提供靈感和參考。

篇1

線性規(guī)劃的研究?jī)?nèi)容可歸納為兩個(gè)方面：一是系統(tǒng)的任務(wù)已定，如何合理籌劃，精細(xì)安排，用最少的資源（人力、物力和財(cái)力）去實(shí)現(xiàn)這個(gè)任務(wù)；二是資源的數(shù)量已定，如何合理利用、調(diào)配，使任務(wù)的完成數(shù)最多.

“線性規(guī)劃”在知識(shí)的整合、解題思路的拓展、方法的遷移等方面都有其鮮明的特點(diǎn)，有著豐富的思想內(nèi)涵. 挖掘題中條件，不失時(shí)機(jī)地運(yùn)用“線性規(guī)劃”的思想方法解題，將使我們觀察思考問(wèn)題的立意更高，視野更加開(kāi)闊.

“線性規(guī)劃”問(wèn)題的教學(xué)現(xiàn)狀

在中學(xué)教材中，稱求目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問(wèn)題為線性規(guī)劃問(wèn)題. “線性規(guī)劃”的教學(xué)分為三個(gè)層次：

（1）二元一次不等式表示的平面區(qū)域；

（2）二元一次不等式組表示的平面區(qū)域；

（3）線性目標(biāo)函數(shù)在約束條件下的最值.

只含有兩個(gè)變量的簡(jiǎn)單線性規(guī)劃問(wèn)題可用圖解法來(lái)解決.

例如：設(shè)實(shí)數(shù)x，y滿足0≤x≤1，0≤y≤2，2y-x≥1，則z=2y-x+4的最大值是__________.

上述問(wèn)題可轉(zhuǎn)化為一個(gè)平面區(qū)域與一條直線在有公共點(diǎn)的前提下，結(jié)合z的幾何意義來(lái)求解.

具體教學(xué)過(guò)程中，學(xué)生感覺(jué)有困難的部分是作圖環(huán)節(jié)，體現(xiàn)在速度慢，不夠準(zhǔn)確. 如何準(zhǔn)確有效地作出所需圖形，應(yīng)給予學(xué)生充分的指導(dǎo)、訓(xùn)練和體驗(yàn). 學(xué)生作圖時(shí)會(huì)出現(xiàn)過(guò)于細(xì)致的問(wèn)題，如逐步描繪坐標(biāo)系刻度；又或出現(xiàn)過(guò)于輕率的問(wèn)題，連圖形的形狀和基本特征都無(wú)法抓住.這兩個(gè)問(wèn)題都使解題的速度和準(zhǔn)確性大打折扣.

當(dāng)然，線性規(guī)劃是一個(gè)比較深入的課題，教材中也介紹了更多變量的線性規(guī)劃問(wèn)題，可引導(dǎo)學(xué)生進(jìn)一步學(xué)習(xí).

線性規(guī)劃問(wèn)題的考查特點(diǎn)與趨勢(shì)

1. 轉(zhuǎn)化成基本線性規(guī)劃問(wèn)題

常規(guī)考題考查知識(shí)與技能，但還需要學(xué)生有一定的轉(zhuǎn)化和化歸意識(shí)，命題者會(huì)在行文敘述、符號(hào)變化、算式特征等方面設(shè)置一定障礙，需要解題者對(duì)得到的信息加工出熟悉的數(shù)學(xué)模型.

例1 （江蘇2013年9題）拋物線y=x2在x=1處的切線與兩坐標(biāo)軸圍成三角形區(qū)域?yàn)镈（包含三角形內(nèi)部和邊界）. 若點(diǎn)P（x，y）是區(qū)域D內(nèi)的任意一點(diǎn)，則x+2y的取值范圍是__________.

分析：本題以拋物線的切線為背景，以文字?jǐn)⑹龅姆绞教峁┝丝尚袇^(qū)域，題中曲線切線利用導(dǎo)數(shù)可得.

解決：求導(dǎo)得y′=2x，切線方程為y=2x-1 ，轉(zhuǎn)化為等價(jià)的基本問(wèn)題：約束條件為x≥0，y≤0，y≥2x-1，目標(biāo)函數(shù)z=x+2y. 作出圖形，易知z的取值范圍為-2，.

例2 設(shè)實(shí)數(shù)x，y滿足3≤xy2≤8，4≤≤9，則的最大值是__________.

分析：如何將其化歸成基礎(chǔ)問(wèn)題，找到未知問(wèn)題和基本題之間的橋梁是破解的關(guān)鍵.

解法一：整體代換，令xy2=m，=n，

那么==，轉(zhuǎn)化為等價(jià)問(wèn)題：約束條件為3≤m≤8，16≤N≤81.目標(biāo)函數(shù)為z=，z幾何意義為對(duì)應(yīng)區(qū)域內(nèi)動(dòng)點(diǎn)與坐標(biāo)原點(diǎn)連線的斜率，易得最大值為27.

解法二：將除法轉(zhuǎn)變?yōu)楹突虿睿}中代數(shù)式兩邊都取以2為底的對(duì)數(shù)，令log2x=A，log2B=y. 轉(zhuǎn)化為等價(jià)問(wèn)題：約束條件為log23≤A+2B≤3，2≤2A-B≤2log23，目標(biāo)函數(shù)為z=3A-4B，可行區(qū)域如圖，容易求得z的最大值為3log23，那么=2z的最大值是27.

圖2

點(diǎn)評(píng)：解法一采用了整體換元，解法二采用了取對(duì)數(shù)化積為和、化除為差，通過(guò)轉(zhuǎn)化和化歸轉(zhuǎn)化成已經(jīng)解決過(guò)的基本問(wèn)題.

2. 線性規(guī)劃問(wèn)題的拓展延伸

（1）線性規(guī)劃問(wèn)題中目標(biāo)函數(shù)的拓展

熟悉線性規(guī)劃基本題還遠(yuǎn)遠(yuǎn)不夠，深刻把握它的數(shù)學(xué)特點(diǎn)和數(shù)學(xué)思想，在實(shí)際處理問(wèn)題中將未知問(wèn)題轉(zhuǎn)化為基本題才更重要. 那么該類問(wèn)題的基本特點(diǎn)是什么，常見(jiàn)問(wèn)題是什么？只有清楚這些，我們才能在實(shí)際處理過(guò)程中及時(shí)、敏銳地轉(zhuǎn)化問(wèn)題，達(dá)到解決問(wèn)題的目的.

以下提供最常見(jiàn)的基本類型；

約束條件：實(shí)數(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)動(dòng)點(diǎn)P（x，y）與點(diǎn)（-1，0）所連直線的斜率；

目標(biāo)函數(shù)（3）：z=的最大值是__________，z的幾何意義即可行區(qū)域內(nèi)動(dòng)點(diǎn)P（x，y）與點(diǎn)（0，1）之間的距離.

與線性規(guī)劃相關(guān)的問(wèn)題普遍具有一些基本特征，主要表現(xiàn)為已知條件是含“雙變量”的不等關(guān)系，目標(biāo)任務(wù)為代數(shù)式的最值或取值范圍問(wèn)題. 可解決的目標(biāo)函數(shù)也不一定是線性代數(shù)式，可以為其他類型.常見(jiàn)的可以為乘積或比值形式、二次或根式形式，甚至可以用向量等給出的代數(shù)式. 也不一定拘泥于目標(biāo)函數(shù)的最值問(wèn)題，也可成為以可行區(qū)域?yàn)楸尘暗拿娣e、向量、概率等問(wèn)題.

（2）線性規(guī)劃問(wèn)題中約束條件的拓展

我們可以將它的數(shù)學(xué)思想拓展得更寬. 約束條件不一定要是線性約束條件，相應(yīng)的平面區(qū)域也可以為直線、圓、曲線等構(gòu)成的復(fù)合形態(tài).

例如：實(shí)數(shù)x，y滿足x2+y2=1，則x+y的最大值是__________.

此題可行區(qū)域可認(rèn)為是圓，可視為曲線圓與直線x+y=m有公共點(diǎn). 由此看來(lái)，約束條件的給出有了更大的空間，線性規(guī)劃這個(gè)知識(shí)點(diǎn)也更容易滲透到其他數(shù)學(xué)知識(shí)點(diǎn)中.

例3 若a>0，b>0且+=1，則a+2b的最小值為_(kāi)_________.

分析：題目涉及兩個(gè)變量的等量關(guān)系，可以考慮減元處理，已由代數(shù)式整理得a=-b++1，結(jié)合基本不等式解決a+2b的最小值；也可以考慮其幾何意義，視作以b為自變量的函數(shù)，那么P（b，a）為函數(shù)圖象上的每一個(gè)點(diǎn).

圖4

解決：a=-b++1，令z=a+2b，z表示此直線的縱截距.當(dāng)直線與曲線相切時(shí)z最小，此時(shí)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，則的取值范圍是__________.

分析：此題和基本問(wèn)題的相似度極高，已知條件含有3個(gè)變量，而且目標(biāo)函數(shù)為比值形式，有明確的幾何意義. 由代數(shù)式clnb≥a+clnc的邏輯計(jì)算知ln≥，由此得到轉(zhuǎn)化的突破口，可轉(zhuǎn)化為兩個(gè)變?cè)?

圖5

解決：已知兩個(gè)不等式同除c得到5-3≤≤4-，ln≥.記=x，=y，

轉(zhuǎn)化為等價(jià)問(wèn)題：

約束條件為x，y>0，5-3x≤y≤4-x，lny≥x？圳y≥ex，目標(biāo)函數(shù)k==.

作出圖形，利用導(dǎo)數(shù)求出曲線y=ex過(guò)坐標(biāo)原點(diǎn)的切線為y=ex，發(fā)現(xiàn)切點(diǎn)T（1，e）在可行區(qū)域內(nèi). 綜上，直線y=kx過(guò)C點(diǎn)時(shí)k最大，與曲線y=ex相切于點(diǎn)T時(shí)k最小. 所求取值范圍為[e，7].

圖6

點(diǎn)評(píng)：三變量的問(wèn)題轉(zhuǎn)化為兩變量問(wèn)題，該問(wèn)題的解決具有一定的代表性.由已知代數(shù)式還可以考慮同除a或b進(jìn)行轉(zhuǎn)化，不是每一個(gè)轉(zhuǎn)化都適合，但有些轉(zhuǎn)化又是相通和可行的，因此求解時(shí)需要一定的嘗試和觀察.

3. 線性規(guī)劃問(wèn)題的知識(shí)遷移

有些數(shù)學(xué)問(wèn)題并無(wú)明顯的線性規(guī)劃痕跡，卻也可以轉(zhuǎn)化成線性規(guī)劃的基本問(wèn)題，比如解析幾何、函數(shù)、數(shù)列等含有多個(gè)變量的數(shù)學(xué)問(wèn)題可采用線性規(guī)劃的方法來(lái)求解. 以下試題立足于課本，但高于課本，題目充分體現(xiàn)了命題教師的高瞻遠(yuǎn)矚，而反過(guò)來(lái)又對(duì)高中的教學(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í)數(shù)m的取值范圍是__________.

分析：兩集合為點(diǎn)集，交集非空.思考難度超越課本，類比線性規(guī)劃，將其轉(zhuǎn)化為兩個(gè)平面區(qū)域有公共點(diǎn)，同時(shí)本題的計(jì)算量大.

解決：集合A對(duì)應(yīng)區(qū)域?yàn)镈1，集合B對(duì)應(yīng)區(qū)域?yàn)镈2，D2容易認(rèn)識(shí)為兩平行直線確定的帶狀區(qū)域. 由區(qū)域D1非空可知m2≥，求得m≤0或m≥.

（1）m=0區(qū)域D1收縮為一點(diǎn)，容易判斷不滿足要求；

（2）m≠0區(qū)域D1又分為兩種情況，當(dāng)m0時(shí)表示兩個(gè)同心圓確定的環(huán)形區(qū)域.不論哪種情況，要滿足題意，只需要保證圓（x-2）2+y2=m2和直線x+y=2m或直線x+y=2m+1其中之一有公共點(diǎn). 圓心到兩直線距離分別為d1和d2，且d1=，d2=. 所以d1≤r=m或d2≤r=m，容易解得m∈1-，2+，綜合以上分析，實(shí)數(shù)m的取值范圍是，2+.

點(diǎn)評(píng)：?jiǎn)栴}描述采用了幾何語(yǔ)言，解決思路和線性規(guī)劃有類似之處，同時(shí)解析幾何背景很強(qiáng)，充分考查了直線和圓的位置關(guān)系，而且分析時(shí)利用分類討論細(xì)化，處理時(shí)又不討論集中解決，思維跳躍度很大.

例6 已知a，b為常數(shù)，a≠0，函數(shù)f（x）=a+ex. 若f（2）

分析：此題僅僅從表象上看到已知條件對(duì)變量a，b作了限制，與線性規(guī)劃知識(shí)點(diǎn)的相關(guān)性相當(dāng)隱蔽. 該題目變量的關(guān)系相互依賴性較強(qiáng)，關(guān)鍵從已知條件合理的抽離出最有效約束條件.

圖7

解決：由f（2）

點(diǎn)評(píng)：g（x）=ax2+bx-b≥0恒成立分析較難，考慮不等式成立的必要條件攻克了這個(gè)難點(diǎn)，根據(jù)代數(shù)式的依存關(guān)系得到約束條件，畫(huà)出圖形，所求面積視為兩個(gè)三角形面積差.

以上可以看出這些問(wèn)題和教材中很多知識(shí)點(diǎn)綜合，都需要學(xué)生具備良好的知識(shí)遷移能力. 包括高考在內(nèi)的眾多考題都或多或少地含有線性規(guī)劃知識(shí)或思想的若干部分，這樣的考題都具備一定的難度，成為命題的熱點(diǎn)題型，在考試中層出不窮.

篇2

線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支,它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法.在經(jīng)濟(jì)管理、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中,提高經(jīng)濟(jì)效果是人們不可缺少的要求,而提高經(jīng)濟(jì)效果一般通過(guò)兩種途徑:一是技術(shù)方面的改進(jìn),例如改善生產(chǎn)工藝,使用新設(shè)備和新型原材料.二是生產(chǎn)組織與計(jì)劃的改進(jìn),即合理安排人力物力資源.線性規(guī)劃所研究的是:在一定條件下,合理安排人力物力等資源,使經(jīng)濟(jì)效果達(dá)到最好.一般地,求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問(wèn)題,統(tǒng)稱為線性規(guī)劃問(wèn)題.滿足線性約束條件的解叫做可行解,由所有可行解組成的集合叫做可行域.決

策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素.而此類問(wèn)題在課本中已經(jīng)有了很多體現(xiàn),在此筆者不再贅述.本文中,筆者想敘述線性規(guī)劃應(yīng)用的一種情況,就是用線性規(guī)劃的方法解決一類概率問(wèn)題.此類概率問(wèn)題一般是幾何概率的問(wèn)題.

請(qǐng)看下面兩例:

例1.甲、乙兩人約定在6時(shí)到7時(shí)之間在某處會(huì)面,并約定先到者應(yīng)等候另一人一刻鐘,過(guò)時(shí)即可離去.求兩人能會(huì)面的概率.

稍加分析我們不難發(fā)現(xiàn),本題中顯然不是一個(gè)變量,而是兩個(gè)變量,即甲、乙各自到達(dá)約會(huì)地點(diǎn)的時(shí)間,所以可以假設(shè)兩個(gè)變量.那么可以在平面直角坐標(biāo)系內(nèi)用x軸表示甲到達(dá)約會(huì)地點(diǎn)的時(shí)間,y軸表示乙到達(dá)約會(huì)地點(diǎn)的時(shí)間,用0分到60分表示6時(shí)到7時(shí)的時(shí)間段,則橫軸0到60與縱軸0到60的正方形中任一點(diǎn)的坐標(biāo)(x,y)就表示甲、乙兩人分別在6時(shí)到7時(shí)時(shí)間段內(nèi)到達(dá)的時(shí)間.而能會(huì)面的時(shí)間由x-y≤15

所對(duì)應(yīng)的圖中陰影部分表示.

反思說(shuō)明:

(1)三角形三邊長(zhǎng)度都是在0到l之間,故每一對(duì)結(jié)果對(duì)應(yīng)三條邊長(zhǎng),分別用x,y軸上的數(shù)表示,則每一個(gè)結(jié)果(x,y)就對(duì)應(yīng)于圖中三角形內(nèi)的任一點(diǎn);

(2)找出事件A發(fā)生的條件,并把它在圖中的區(qū)域找出來(lái)分別計(jì)算面積即可;

(3)本題的難點(diǎn)是把三條邊長(zhǎng)分別用x,y兩個(gè)坐標(biāo)分別表示,構(gòu)成平面內(nèi)的點(diǎn)(x,y),從而把邊長(zhǎng)是一段長(zhǎng)度問(wèn)題轉(zhuǎn)化為平面圖形中的線性規(guī)劃問(wèn)題,轉(zhuǎn)化成面積為測(cè)度的幾何概型的問(wèn)題.

但是對(duì)于類似問(wèn)題我們一定要注意是否是以面積為測(cè)度的概率問(wèn)題,有些仍然是古典概率,如下例:

例3.如下圖,從某學(xué)校高三年級(jí)共800名男生中隨機(jī)抽取50名測(cè)量身高,測(cè)量發(fā)現(xiàn)被測(cè)學(xué)生身高全部介于155cm和195cm之間,將測(cè)量結(jié)果按如下方式分成八組:第一組[155,160)、第二組[160,165)、……第八組[190,195),下圖是按上述分組方法得到的頻率分布直方圖的一部分,已知第一組與第八組人數(shù)相同,第六組、第七組、第八組人數(shù)依次構(gòu)成等差數(shù)列.若從身高屬于第六組和第八組的所有男生中隨機(jī)抽取兩名男生,記他們的身高分別為x、y,求滿足x-y≤5的事件概率.

篇3

常規(guī)的線性規(guī)劃問(wèn)題求最優(yōu)解，要明確線性規(guī)劃問(wèn)題求解的基本步驟，即在作出可行域，理解目標(biāo)函數(shù)z的意義的基礎(chǔ)上，通過(guò)平移目標(biāo)函數(shù)所在直線，最終尋求最優(yōu)解.

例1 （2015年陜西）某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品均需用A，B兩種原料.已知生產(chǎn)1噸每種產(chǎn)品需原料及每天原料的可用限額如表所示，如果生產(chǎn)1噸甲、乙產(chǎn)品可獲利潤(rùn)分別為3萬(wàn)元、4萬(wàn)元，則該企業(yè)每天可獲得最大利潤(rùn)為（ ）.

A.12萬(wàn)元 B.16萬(wàn)元 C.17萬(wàn)元 D.18萬(wàn)元

甲乙原料限額A（噸）3212B（噸）128

解析 設(shè)該企業(yè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為x、y噸，則利潤(rùn)z=3x+4y，

由題意可列3x+2y≤12，

x+2y≤8，

x≥0，

y≥0，該不等式組表示的平面區(qū)域如圖1所示陰影部分：

圖1

易知目標(biāo)函數(shù)z=3x+4y所在直線y=-34x+z4過(guò)點(diǎn)A（2，3），即x=2，y=3時(shí)，z取得最大值，zmax=3×2+4×3=18，故選D.

實(shí)際問(wèn)題涉及的線性規(guī)劃問(wèn)題求解，不同于純數(shù)學(xué)形式的線性規(guī)劃問(wèn)題，尤其最優(yōu)解，要遵循實(shí)際問(wèn)題所在的意義.類似教材中鋼板張數(shù)，人力資源分配，車(chē)輛配備等問(wèn)題要尋求最優(yōu)整數(shù)解等，都不同于一般的數(shù)學(xué)求實(shí)數(shù)解問(wèn)題，這在求解過(guò)程中尤其注意.

練習(xí) （2015年天津）設(shè)變量x，y滿足約束條件x+2≥0，

x-y+3≥0，

2x+y-3≤0，則目標(biāo)函數(shù)z=x+6y的最大值為（ ）.

A.3 B.4 C.18 D.40

（答案C.）

2 線性規(guī)劃問(wèn)題中的參數(shù)求解

在線性規(guī)劃問(wèn)題中，常常遇到借助于不等式組，或者目標(biāo)函數(shù)設(shè)置一些參數(shù)，利用已知的目標(biāo)函數(shù)z的最值，來(lái)求出參數(shù)值的題目.這類線性規(guī)劃問(wèn)題的求解，方法上仍要遵循線性規(guī)劃問(wèn)題的求解步驟，但在求解中涉及到分類討論，數(shù)形結(jié)合等數(shù)學(xué)思想.

例2 （2015年山東）已知x，y滿足約束條件x-y≥0，

x+y≤2，

y≥0. 若z=ax+y的最大值為4，則a=（ ）.

A.3 B.2 C.-2 D.-3

圖2

解析 由z=ax+y得y=-ax+z，借助圖形2可知：

當(dāng)-a≥1，即a≤-1時(shí)，在x=y=0時(shí)有最大值0，不符合題意;

當(dāng)0≤-a<1，即-1<a≤0時(shí)，在x=y=1時(shí)有最大值a+1=4，a=3，不滿足-1<a≤0;

當(dāng)-1<-a≤0，即0<a≤1時(shí)，在x=y=1時(shí)有最大值a+1=4，a=3，不滿足0<a≤1;當(dāng)-a<-1，即a>1時(shí)在x=2，y=0時(shí)有最大值2a=4，a=2，滿足a>1;故選B.

本例中參數(shù)a在目標(biāo)函數(shù)所在直線方程中的意義與斜率有關(guān)，即直線的斜率k=-a，故如何利用條件中的函數(shù)最大值4求參數(shù)a成為解題關(guān)鍵，或者說(shuō)目標(biāo)函數(shù)所在直線經(jīng)過(guò)不等式組所示區(qū)域的哪一點(diǎn)取到最大值成為參數(shù)a分類討論的依據(jù).

3 非線性目標(biāo)函數(shù)的最值求解

在線性規(guī)劃問(wèn)題中，我們常常會(huì)遇到一些非線性目標(biāo)函數(shù)的求解問(wèn)題.

例3 （2015年四川）設(shè)實(shí)數(shù)x，y滿足

2x+y≤10，

2+2y≤14，

x+y≥6，

則xy的最大值為（ ）.

A.252 B.492

C.12 D.14 圖3

解析 不等式所示平面區(qū)域如圖3，

當(dāng)動(dòng)點(diǎn)（x，y）在線段AC上時(shí)，此時(shí)2x+y=10，據(jù)基本不等式知道，非線性目標(biāo)函數(shù)z=xy=12（2x?y）≤12（2x+y2）2=252，當(dāng)且僅當(dāng)x=52，y=5時(shí)取等號(hào)，對(duì)應(yīng)點(diǎn)落在線段AC上，故最大值為252，選A.

本例中，目標(biāo)函數(shù)z=xy，借助于直線方程2x+y=10，通過(guò)變形xy=12（2x?y）聯(lián)想到不等式2x?y≤（2x+y2）2，從而找到目標(biāo)函數(shù)xy的最優(yōu)解.類似非線性目標(biāo)函數(shù)x2+y2，y-bx-a等形式都要在理解函數(shù)意義的基礎(chǔ)上尋求最優(yōu)解.

練習(xí) （2015年新課標(biāo)卷）若x，y滿足約束條件x-1≥0，

x-y≤0，

x+y-4≤0， 則yx的最大值為 .

（答案3.）

4 線性規(guī)劃問(wèn)題的綜合運(yùn)用

有些數(shù)學(xué)問(wèn)題如果轉(zhuǎn)化為線性規(guī)劃問(wèn)題會(huì)得到簡(jiǎn)捷的解法，當(dāng)然這要求對(duì)問(wèn)題有著較深刻的理解，要善于利用轉(zhuǎn)化和劃歸思想轉(zhuǎn)化為線性規(guī)劃問(wèn)題.

例4 （2015年浙江理科）若實(shí)數(shù)滿足x2+y2≤1，則|2x+y-2|+|6-x-3y|的最小值是 .

解析 條件x2+y2≤1表示圓x2+y2=1及其內(nèi)部，易得直線6-x-3y=0與該圓相離，故|6-x-3y|=6-x-3y，設(shè)函數(shù)z=|2x+y-2|+|6-x-3y|，

當(dāng)2x+y-2≥0時(shí)，則x2+y2≤1，

2x+y-2≥0，所示平面區(qū)域如圖4所示，可行域?yàn)樾〉墓蝺?nèi)部，易知目標(biāo)函數(shù)z=|2x+y-2|+|6-x-3y|=x-2y+4，

故目標(biāo)函數(shù)z=x-2y+4所在直線y=12x-z2+2過(guò)點(diǎn)A（35，45）時(shí)z最小，即x=35，y=45時(shí)，zmin=4;

圖4

當(dāng)x-2y+4<0時(shí)，z=|2x+y-2|+|6-x-3y|=8-3x-4y，可行域?yàn)榇蟮墓?/p>

內(nèi)部，同理可知目標(biāo)函數(shù)z=8-3x-4y所在直線y=-34x-z4+2過(guò)點(diǎn)A（35，45）時(shí)z最小，當(dāng)x=35，y=45時(shí)，zmin=4.

篇4

一、面積問(wèn)題

1、(全國(guó)卷)在坐標(biāo)平面上,不等式組y≥x-1y≤-3x+1所表示的平面區(qū)域的面積為_(kāi)________。

解析:原不等式組去掉絕對(duì)值后轉(zhuǎn)化為兩個(gè)不等式組,畫(huà)出平面區(qū)域,根據(jù)三角形面積公式求得答案。

二、最值問(wèn)題

2、(全國(guó)卷)若x,y滿足約束條件x+y≥0x-y+3≥00≤x≤3則z=2x-y的最大值為_(kāi)___________。

解析:z=2x-y的幾何意義是斜率為2的直線的縱截距的相反數(shù),在坐標(biāo)平面上畫(huà)出可行域,可得結(jié)果。

x,y滿足x-y-2≤0x+2y-4>02y-3≤0則的最大值是________。

3、(江西)設(shè)實(shí)數(shù)

解析:在坐標(biāo)平面上畫(huà)出可行域z==的幾何意義是兩點(diǎn)O(0,0)A(x,y)連線的斜率,畫(huà)圖可知,在點(diǎn)(1, )時(shí)z最大,故所求最大值為。

4、教材第二冊(cè)(上)第99頁(yè) 第5題

解析:由問(wèn)題的形式聯(lián)想到兩點(diǎn)間距離公式,從而利用線性規(guī)劃的思想去解決。上述幾題中的約束條件是以不等式的形式出現(xiàn),有時(shí)以方程形式給出,如教材第二冊(cè)(上)第99頁(yè) 第6題

方法提煉:

①解決線性規(guī)劃問(wèn)題,首先找到線性約束條件,畫(huà)出可行域;線性約束條件可能是關(guān)于x、y的不等式(組)或方程(組)。

篇5

這個(gè)參數(shù)往往與直線的斜率有關(guān)系，并且已知最優(yōu)解，因此解題時(shí)可充分利用斜率的特征加以轉(zhuǎn)化。

1.目標(biāo)函數(shù)中的系數(shù)為參數(shù)

例1、(2009年陜西理11)若x，y滿足約束條件x+y?叟1x-y?叟-12x-y?燮2，目標(biāo)函數(shù)z=ax+2y僅在點(diǎn)（1，0）處取得最小值，則a的取值范圍是（ ）

A. (-1,2) B. (-4,2) C. (-4,0) D.(-2,4)

分析：明確a的幾何意義，與直線的斜率有關(guān)，根據(jù)圖形特征確定怎樣才能保證僅在點(diǎn)（1，0）處取得最小值。

解：作出約束條件所形成的區(qū)域圖形，目標(biāo)函數(shù)化成y=-■x+■，則斜率k=-■，截距為■，要使截距最小，則-1

2.目標(biāo)函數(shù)中的系數(shù)為參數(shù)

例2 (2006湖北理) 已知平面區(qū)域D由以A(1，3)，B(5，2)，C(3，1)為頂點(diǎn)的三角形內(nèi)部和邊界組成，若在區(qū)域D上有無(wú)窮多個(gè)點(diǎn)(x，y)可使目標(biāo)函數(shù)z=x+my取得最小值,則m=（ ）。

A.-2 B.-1 C.1 D.4

分析：最優(yōu)解有無(wú)窮多個(gè)，往往是指目標(biāo)函數(shù)與其中一條直線重合，此外要注意到參數(shù)為或的系數(shù)上的不一致。

解：要使目標(biāo)函數(shù)z=x+my的最優(yōu)解有無(wú)窮多個(gè)，則直線z=x+my應(yīng)與直線AC或AB，BC重合，但要使目標(biāo)函數(shù)Z=X+my取得最小值，必須使得函數(shù)斜率為負(fù)值，且斜率的絕對(duì)值要大，從而只能與直線AC重合，則-■=kAC=-1，所以m=1，選C。

3.目標(biāo)函數(shù)中x,y的系數(shù)均為參數(shù)

例3 (2009年山東理12) 設(shè)x，y滿足約束條件3x-y-6?燮0x-y+2?叟0x?叟0,y?叟0，若目標(biāo)函數(shù)z=ax+by，(a>0,b>0)的值是最大值為12，則■+■的最小值為( )。

A.■ B.■ C.■ D. 4

分析：本題綜合地考查了線性規(guī)劃問(wèn)題和由基本不等式求函數(shù)的最值問(wèn)題.要求能準(zhǔn)確地畫(huà)出不等式表示的平面區(qū)域,并且能夠求得目標(biāo)函數(shù)的最值,對(duì)于形如已知2a+3b=6,求■+■的最小值常用乘積進(jìn)而用均值不等式解答。

解：不等式表示的平面區(qū)域如圖所示陰影部分,當(dāng)直線z=ax+by(a>b,b>0)過(guò)直線x-y+2=0與直線3x-y-6=0的交點(diǎn)A(4,6)時(shí),目標(biāo)函數(shù)z=ax+by(a>0,b>0)取得最大12,4a+6b=12,即2a+3b=6,而■+■=(■+■)■=■+(■+■)?叟■+2=■,故選A。

二、約束條件中含有參數(shù)

約束條件中某一個(gè)約束條件含有參數(shù)，意味著約束條件是變動(dòng)的，這種變動(dòng)導(dǎo)致了目標(biāo)函數(shù)最值的變動(dòng)。

1.已知目標(biāo)函數(shù)最值，求參數(shù)的值

例4 （2010年浙江理7）若實(shí)數(shù)，滿足不等式組x+3y-3?叟0，2x-y-3?燮0，x-my+1?叟0，且z=x+y的最大值為9，則實(shí)數(shù)m=（ ）。

A.-2 B.-1

C.1 D.2

分析：已知目標(biāo)函數(shù)的最值求參數(shù)的值，關(guān)鍵是找到最優(yōu)解，代入到目標(biāo)函數(shù)中，求出參數(shù)的值。

解：不等式組表示的平面區(qū)域如圖中陰影所示，把目標(biāo)函數(shù)化為y=-x+z，則當(dāng)直線y=-x+z過(guò)A點(diǎn)時(shí)z最大，由2x-y-3=0，x-my+1=0，得到A(■，■)，代入目標(biāo)函數(shù)得■+■=9，所以m=1。

2.已知目標(biāo)函數(shù)最值范圍，求參數(shù)的范圍

例5 (2011年高考湖南卷理科7)設(shè)m>1，在約束條件y?叟xy?燮mxx+y?燮1下，目標(biāo)函數(shù)Z=x+my的最大值小于2，則m的取值范圍為

。

分析：本題關(guān)鍵是理解參數(shù)的幾何意義是直線的斜率，找到關(guān)于m的一個(gè)不等式。

篇6

1． 當(dāng)變量x，y滿足約束條件x≥0，y≤x，2x+y+k≤0時(shí)（k為常數(shù)），能使z=x+3y的最大值為12的k為（）

3． 如果實(shí)數(shù)x，y滿足條件x－y+1≥0，y+1≥0，x+y+1≤0，那么2x－y的最大值為（）

A． 2?搖?搖?搖?搖?搖?搖 B． 1 ?搖?搖 C． －2?搖 ?搖?搖?搖?搖?搖D． －3

4． 已知2x+y－2≥0，x－2y+4≥0，3x－y－3≤0，則x2+y2的最大值與最小值分別是（）

A． 13，1 B． 13，2

5. 已知三點(diǎn)A（x0，y0），B（1，1），C（5，2）.如果一個(gè)線性規(guī)劃問(wèn)題的可行域是ABC的邊界及其內(nèi)部，線性目標(biāo)函數(shù)z=ax+by在點(diǎn)B處取得最小值3，在點(diǎn)C處取得最大值12，則下列關(guān)系成立的是（）

A. 3≤x0+2y0≤12

B． x0+2y0≤3或x0+2y0≥12

C． 3≤2x0+y0≤12

D． 2x0+y0≤3或2x0+y0≥12

7． 在約束條件x≥0，y≥0，y+x≤s，y+2x≤4下，當(dāng)3≤s≤5時(shí)，目標(biāo)函數(shù)z=3x+2y的最大值的變化范圍是_______．

以上題目從多角度考查了線性規(guī)劃的相關(guān)知識(shí)，同學(xué)們只要抓住解線性規(guī)劃題的本質(zhì)就不難解決．

1. 首先要能正確畫(huà)出可行域（可借助特殊點(diǎn)法來(lái)確定二元一次不等式表示的區(qū)域）；

2. 然后利用平移法找到所要求的最值（可借助直線的斜率來(lái)幫助判斷最值點(diǎn)），此外還要注意目標(biāo)函數(shù)的幾何意義（除了通常的截距外還可能轉(zhuǎn)化為兩點(diǎn)間距離，斜率等）；

3. 最后在解實(shí)際問(wèn)題時(shí)一定要仔細(xì)讀題，然后根據(jù)條件列出線性約束條件和目標(biāo)函數(shù)，這以后的步驟就用1、2兩點(diǎn)的方法來(lái)解決．

同學(xué)們?cè)诮獯祟愵}目時(shí)，不管題目如何變化，只要按照所講的步驟一步步進(jìn)行下去，這些問(wèn)題都會(huì)迎刃而1． B

2． A

3． B

篇7

1數(shù)學(xué)模型

線性規(guī)劃問(wèn)題通常表示成如下兩種形式:標(biāo)準(zhǔn)型、規(guī)范型。

設(shè)jj(2…，n)是待確定的非負(fù)的決策變量；認(rèn)2…，n)是與決策變量相對(duì)應(yīng)的價(jià)格系數(shù)；K2…mj=l2…n)是技術(shù)系數(shù)；b(i12…，m)是右端項(xiàng)系數(shù)；

線性規(guī)劃是運(yùn)籌學(xué)最基本、運(yùn)用最廣泛的分支，是其他運(yùn)籌學(xué)問(wèn)題研究的基礎(chǔ)。在20世紀(jì)50年代

到60年代期間，運(yùn)籌學(xué)領(lǐng)域出現(xiàn)許多新的分支：非線性規(guī)劃（nonlinearprogranming、商業(yè)應(yīng)用（crnxmereialpplieation、大尺度方法(laresealemeh-Qd)隨機(jī)規(guī)劃（stochasticPKgiamniig)、整數(shù)規(guī)劃(ntegerprogramming)、互補(bǔ)轉(zhuǎn)軸理論（amplmentaiyPivotheor)多項(xiàng)式時(shí)間算法（polynomialtjneagatm)等。20世紀(jì)70年代末，上述分支領(lǐng)域都得到了極大發(fā)展，但是卻都不完善。而且數(shù)學(xué)規(guī)劃領(lǐng)域中存在許多Nfkhard問(wèn)題，如TP問(wèn)題，整數(shù)規(guī)劃問(wèn)題等。這些問(wèn)題的基本模型都可以寫(xiě)成線性規(guī)劃形式，因此通過(guò)對(duì)線性規(guī)劃算法的進(jìn)一步研究，可以進(jìn)一步啟發(fā)及推動(dòng)數(shù)學(xué)規(guī)劃領(lǐng)域內(nèi)其他分支的發(fā)展。

2邊界點(diǎn)算法

由于單純形法與基線算法都是在可行集的邊界上取得最優(yōu)值，故合稱單純形法與基線法為邊界點(diǎn)算法。單純形法是線性規(guī)劃使用最早也是目前實(shí)際應(yīng)用中最流行和求解新型規(guī)劃問(wèn)題最有效的算法之一。它實(shí)施起來(lái)相當(dāng)簡(jiǎn)單特別對(duì)中小規(guī)模問(wèn)題效果顯著。單純形法最早是由Damzg于1947年夏季首先提出來(lái)的。1953年Dantzig為了改進(jìn)單純形法每次迭代中積累起來(lái)的進(jìn)位誤差，提出改進(jìn)單純形法12。1954年美國(guó)數(shù)學(xué)家CELmH3針對(duì)對(duì)偶問(wèn)題提出一種在數(shù)學(xué)上等價(jià)于用改進(jìn)單純形法求解的對(duì)偶線形規(guī)劃。1974年CuretN41提出了求解一般線性規(guī)劃問(wèn)題的原對(duì)偶單純形法，該算法與對(duì)偶單純形法類似，但是原對(duì)偶單純形法允許我們從一個(gè)非基礎(chǔ)對(duì)偶可行解開(kāi)始算法求解。

1972年Klee等舉例證明了單純形算法的時(shí)間復(fù)雜性有可能是指數(shù)型。1973年，Jeoslowoi和Zdeh7又分別進(jìn)一步指出常用的對(duì)偶單純形法、原一對(duì)偶單純形法等都是指數(shù)級(jí)的。

這就讓人們產(chǎn)生兩個(gè)疑問(wèn):①是否存在單純形法的某種改型，用它求解線性規(guī)劃問(wèn)題是多項(xiàng)式時(shí)算法。

對(duì)于問(wèn)題①，研究者們對(duì)單純形法采用了一系列改進(jìn)技術(shù)如數(shù)據(jù)的預(yù)處理方法、更好的退化性處理、更好的局部?jī)r(jià)格向量計(jì)算、原一對(duì)偶最速下降邊算法的應(yīng)用、更快和更穩(wěn)定的矩陣分解、更好的Cach存貯的應(yīng)用、以及階段1和階段2的組合算法等。但是仍未能從理論上證明線形規(guī)劃算法是多項(xiàng)式時(shí)間的。

近年來(lái)國(guó)內(nèi)也出現(xiàn)了一批致力于線形規(guī)劃算法研究的學(xué)者，但是國(guó)內(nèi)學(xué)者的研究主要集中在對(duì)單純形法的突破研究上，如基線法|8_'最鈍角原理1111等。

最鈍角及投影主元標(biāo)算法都是針對(duì)單純形算法存在退化現(xiàn)象就如何選擇最優(yōu)入基、離基做出的一系列研究及改進(jìn)。退化現(xiàn)象是單純形法一直以來(lái)需解決的難題，為了克服退化問(wèn)題許多學(xué)者提出了有限主元規(guī)則：擾動(dòng)法、字典序規(guī)則、Blad規(guī)則1171等，其中Bind規(guī)則由于其簡(jiǎn)單而備受關(guān)注，但是這些有限主元規(guī)則的實(shí)際應(yīng)用方面并不令人滿意，甚至都不能和Dantzg規(guī)則相比。1990年，潘平奇教授在文獻(xiàn)[11]給出了線性規(guī)劃問(wèn)題最優(yōu)基的一個(gè)啟發(fā)式刻畫(huà)特征:最鈍角原理。最鈍角原理是引人反映目標(biāo)梯度與約束梯度夾角大小的“主元標(biāo)”乍為確定變量進(jìn)基優(yōu)先性的依據(jù)，潘教授的數(shù)值試驗(yàn)11819表明此規(guī)則明顯優(yōu)于Bland規(guī)則。然而潘的方法僅適用于只含不等式約束的線性規(guī)劃問(wèn)題。為便于求解標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題，許多學(xué)者在其基礎(chǔ)上又提出了對(duì)偶主元標(biāo)法。由于對(duì)偶主元標(biāo)法是利用嚴(yán)格互補(bǔ)松弛來(lái)推導(dǎo)過(guò)度的，針對(duì)這一問(wèn)題，又有學(xué)者提出了投影主元標(biāo)法。

除此之外還有一系列最鈍角原理在非人工變量?jī)呻A段算法1M21及虧基情況下的應(yīng)用研究。這些研究表明，最鈍角原理是克服單純形法退化的一種有效方法。

基線算法的概念是1996年阮國(guó)楨教授提出來(lái)的1891，這種算法是單純形法的發(fā)展，名字由來(lái)一方面是相對(duì)單純形法（基點(diǎn)法）提出，另一方面是使用

基線算法的主要思想是：

其中疋FTX1;eRbERm為一個(gè)m階單位矩陣。n是問(wèn)題的維數(shù)，m是約束個(gè)數(shù)。把目標(biāo)函數(shù)v=ff作為一個(gè)約束，看作參數(shù)。

Stef!以任意：>0所對(duì)應(yīng)的變量作為進(jìn)基變量，則x所在的列與單位矩陣一起構(gòu)成了一個(gè)可行基B改寫(xiě)八=[N馬，相應(yīng)地改寫(xiě)X為[xrxo’，x為非基變量，x為基變量。于是方程組AX=[vb’可以寫(xiě)成Nx+Bx^Evl]’=a0+^0VStep求B1，以B1左乘，得B^1N^N+3B=B1[v]’=礦a0+B1⑷v

(2.1)

令a=B1a。，p=B-1仏則式（21河寫(xiě)作

Sep對(duì)任意巨{01，…，m}，令aA^vs0

計(jì)算出當(dāng)前基線表對(duì)應(yīng)的可行值區(qū)間[J-”。若h

…，n-L貝IJv為最優(yōu)值，或者轉(zhuǎn)SteP4

Sep旋轉(zhuǎn)基表，更新BaP旋轉(zhuǎn)基表時(shí)通常只使用有限軟上界行的負(fù)可旋主元。對(duì)于負(fù)可旋主元的選擇主要實(shí)現(xiàn)方法有：最大負(fù)主元算法[221，行列最好主元算法[231,保硬主元算法[24251等。

基線算法操作簡(jiǎn)單迭代次數(shù)少，求解速度快。相對(duì)單純形法來(lái)說(shuō)，單純形法最多能搜索與當(dāng)前極點(diǎn)相鄰的n個(gè)極點(diǎn)，而基線算法能搜索11個(gè)二維面，這是基線算法能夠快速求解LP問(wèn)題的關(guān)鍵所在。

發(fā)展至今，基線算法已有其對(duì)偶算法[271，群部分算法['目標(biāo)規(guī)劃[29301,錐上算法[311等一整套的理論基礎(chǔ)和一系列具體的快速實(shí)現(xiàn)算法12632,圍繞著是否存在著多項(xiàng)式的基線算法，在計(jì)算復(fù)雜度方面作深入的研究將對(duì)線性規(guī)劃的發(fā)展具有十分深遠(yuǎn)的意義。

3割平面法

線性規(guī)劃算法中割平面思想的應(yīng)用主要是指橢球法。1979年Khanchiaii33!改進(jìn)Yudin和Nan-

ovski等[34]為凸規(guī)劃開(kāi)發(fā)的橢球法，獲得了一個(gè)求解線形規(guī)劃的多項(xiàng)式時(shí)間算法:橢球法。對(duì)問(wèn)題②做出了明確回答。不同于單純形法從一個(gè)基礎(chǔ)可行解開(kāi)始迭代，橢球法的特點(diǎn)是求解過(guò)程的每一階段都有一個(gè)以某一點(diǎn)為中心的橢球，迭代是從一個(gè)包含最優(yōu)解的較大的橢球迭代到包含最優(yōu)解的較小的橢球直至逼近最優(yōu)解。

為線性規(guī)劃問(wèn)題式（1.2)的規(guī)模。其中，lg]是以2為底的對(duì)數(shù)，「?]表示剛剛大于括號(hào)值的整數(shù)。則橢球法的時(shí)間復(fù)雜度為OML)

Khachiar橢!球法的主要思想是：

根據(jù)線性規(guī)劃的強(qiáng)對(duì)偶定理，線性規(guī)劃問(wèn)題式(1.2)可以轉(zhuǎn)為下列求可行域問(wèn)題：

2)從球開(kāi)始，這個(gè)球大到包括式（3l1)的所有可行集X不斷構(gòu)造一系列橢球，第k次迭代的橢球?yàn)镋k檢驗(yàn)橢球中心&是否滿足約束條件；若滿

足則停止，否則利用割平面球的半橢球$Ek=EH

{aTA構(gòu)造新的橢球更新橢球Ek+1為包含半橢球的最小體積橢球。按照這種算法下去直到橢球中心位于目標(biāo)集內(nèi)，橢球中心即為問(wèn)題式（31)的解;否則橢球體積太小以至不含問(wèn)題式（31)的可行解。

由于Khachiarn橢球法從構(gòu)造包含可行域的大

的橢球出發(fā)，初始橢球體積有可能是天文數(shù)字，而且KhanCir橢球法利用K-K-T條件將原規(guī)劃問(wèn)題轉(zhuǎn)

化為可行域求解問(wèn)題，擴(kuò)大了求解規(guī)模的同時(shí)加入了等式約束，使得可行集體積為零。雖然求解時(shí)，對(duì)等式進(jìn)行攝動(dòng)，可行集體積仍然很小。初始橢球體積太大，最終橢球（包含可行集的最小橢球）體積又幾乎為零，算法可能需要經(jīng)過(guò)非常大的迭代步數(shù)才能收斂。而且如果對(duì)偶問(wèn)題無(wú)界則原問(wèn)題不可行，因此當(dāng)計(jì)算結(jié)果無(wú)解時(shí)不能判斷是原問(wèn)題無(wú)界呢還是原問(wèn)題不可行。

不少研究者從加大每次迭代后橢球縮小比出發(fā)，提出了許多KhanCirn橢球法的改進(jìn)算法:深切害J(deepeus)35-37、替代切割（surrogatecuts)381、

平行切割（paUMeus)|39-411等。最新成果是楊德莊等人提出的新的橢球法142,其優(yōu)點(diǎn)在于引入目標(biāo)束不等式及目標(biāo)不等式組成，與原橢球法相比一方面大大縮小了算法求解規(guī)模，另一方面擴(kuò)大了可行集的體積。而且新算法中可行集切割及目標(biāo)切割交替進(jìn)行，加速了橢球體積的縮小。不過(guò)令人失望的是即使最好的橢球法實(shí)施在計(jì)算上都難以與已有的單純形法相比。因此，實(shí)際中很少作為一般方法使用1431。

然而線性規(guī)劃的其他解法如單純形法、內(nèi)點(diǎn)法都需要從一個(gè)基礎(chǔ)解出發(fā)，然后確定迭代方向、迭代步長(zhǎng)，因此每次迭代都需要計(jì)算目標(biāo)函數(shù)和所有約束函數(shù)。而橢球法的計(jì)算則簡(jiǎn)單得多，理論上來(lái)說(shuō)橢球法對(duì)于約束條件多的問(wèn)題更有效。

4內(nèi)點(diǎn)法

1984年KamarH441提出了一個(gè)比Khanchian法好的多項(xiàng)式時(shí)間算法的內(nèi)點(diǎn)法，稱為Kamaikar法。由于該法引用了非線性規(guī)劃中的牛頓投影，因此又稱K_aka牧影法。

K_aka袪的提出在線性規(guī)劃領(lǐng)域具有極大的理論意義。與橢球法不同，這個(gè)新算法不僅在最壞情況下在時(shí)間復(fù)雜度上優(yōu)于單純形法，在大型實(shí)際問(wèn)題中也有潛力與單純形法競(jìng)爭(zhēng)。

這一方法的提出掀起了一股內(nèi)點(diǎn)法的研究熱潮。鑒于Kamaka?法的難讀性，一些研究學(xué)者?對(duì)Kamaika袪進(jìn)行了適度的修改，使其簡(jiǎn)便易讀。然而直接用該方法編程解題的測(cè)試表明，與目前基于單純形法的商用軟件相比，并沒(méi)有明顯的優(yōu)勢(shì)1491。因此很多研究者在Kamarka法的基礎(chǔ)上深入研究并提出了各種修正內(nèi)點(diǎn)法方法：仿射尺度法，對(duì)數(shù)障礙函數(shù)法，路徑跟蹤法算法等。

仿射比例調(diào)節(jié)法又分為原（Ptme)仿射比例調(diào)節(jié)法和對(duì)偶（Dua)方射比例調(diào)節(jié)法。原仿射比例調(diào)節(jié)法是從原問(wèn)題出發(fā)，用一個(gè)仿射變換代替投影變換，把坐標(biāo)系從一個(gè)非負(fù)象限不是單純形）映射到其本身。該法1967年由前蘇聯(lián)學(xué)者Dkii5(0提出，但他的工作直到Bame1]等人再次研究該法后才被 法，另一方面作了完全的收斂性的證明。此外，1989年AdleP等發(fā)表了從原問(wèn)題的對(duì)偶問(wèn)題出發(fā)的對(duì)偶仿射比例調(diào)節(jié)法。

1986年G1531等人第一次把用于非線性規(guī)劃的對(duì)數(shù)障礙函數(shù)法用于線性規(guī)劃，并證明了對(duì)數(shù)障礙函數(shù)法和Kamarka投影法是等價(jià)的。以后的研究表明kamaikaf法實(shí)際上是廣義對(duì)數(shù)障礙函數(shù)法的一個(gè)特殊情形。由于其計(jì)算方面的優(yōu)越性，因此該法得到更多的研究和發(fā)展，該法也分為原對(duì)數(shù)障礙函數(shù)法和對(duì)偶對(duì)數(shù)障礙函數(shù)法。

原對(duì)偶（PrimaDua)各徑跟蹤法，實(shí)際上是原對(duì)偶障礙函數(shù)法，是MeidG19M541年提出的。他將包含對(duì)數(shù)障礙函數(shù)問(wèn)題的障礙參數(shù)的唯一的最優(yōu)解所構(gòu)成的曲線稱為一條路徑或中心軌跡，當(dāng)障礙參數(shù)趨近零時(shí)，中心軌跡的極限即為原問(wèn)題的最優(yōu)解。Kojma55'等最早（1987)提出收斂的算法，之后其他研究者對(duì)算法作了進(jìn)一步的改進(jìn)。為了找到起始可行解算法都要引進(jìn)人工變量和附加約束條件，分別以適當(dāng)?shù)拇髷?shù)作系數(shù)和右端值，但算法對(duì)這些大數(shù)的選擇很敏感易導(dǎo)致算法中數(shù)值的不穩(wěn)定性。因此LustiTi等考慮使這些大數(shù)同時(shí)變?yōu)闊o(wú)窮大時(shí)坐標(biāo)增量的“極限可行方向”該方向只改變了求最優(yōu)解的方向，并不改變確定軌跡中心的方向，因而問(wèn)題解法成為不可行問(wèn)題原對(duì)偶牛頓法，其優(yōu)點(diǎn)是對(duì)初始解不必引入人工變量。該法也可用類似形式應(yīng)用于不可行原問(wèn)題或?qū)ε紗?wèn)題的方法中[57581。該法還便于處理有界變量問(wèn)題。然而這個(gè)方法的計(jì)算復(fù)雜性尚未確知，沒(méi)有一般收斂的算法的證明。此外，在方法的改進(jìn)方面，出現(xiàn)了全面收斂不可行內(nèi)點(diǎn)算法和預(yù)計(jì)改正法。

勢(shì)函數(shù)下降法有基于Gezaga等人提出的原勢(shì)函數(shù)下降法和Ye等人提出的原對(duì)偶勢(shì)函數(shù)下降法,計(jì)算復(fù)雜性都達(dá)到較好指標(biāo)。前者算法包含了兩個(gè)搜索方向，且所有仿射變換方法都采用了最速下降方向。這方面的改進(jìn)還有Kajmm等的原對(duì)偶勢(shì)函數(shù)下降法等。由于上述勢(shì)函數(shù)下降法的各種算法是基于一系列嚴(yán)格的可行解上，方法都要求說(shuō)是難以做到的。顯然直接采用不可行內(nèi)點(diǎn)算法是最好的解決辦法，因而Y，eTOdd和Misunol994年提

出了構(gòu)建“齊次自對(duì)偶問(wèn)題”的方法，該齊次自對(duì)偶問(wèn)題的解則可以用Kajjna等的原對(duì)偶勢(shì)函數(shù)下降法來(lái)解出。

在20世紀(jì)90年代內(nèi)點(diǎn)法理論發(fā)展成一個(gè)相當(dāng)成熟的原理。這一時(shí)期，對(duì)內(nèi)點(diǎn)法理論的一個(gè)主要貢獻(xiàn)來(lái)自YENesterov和八SNmirovski兩位數(shù)學(xué)家[69。他們創(chuàng)建的Self-Cocrdant函數(shù)理論，使基于對(duì)數(shù)障礙函數(shù)的線性規(guī)劃內(nèi)點(diǎn)法很容易推廣到更為復(fù)雜的優(yōu)化問(wèn)題上，如非線性凸規(guī)劃、非線性互補(bǔ)、變分不等式、半定優(yōu)化以及二階錐優(yōu)化等。目前自協(xié)調(diào)函數(shù)形式主要有：對(duì)數(shù)函數(shù)和商函數(shù)形式。

今天，內(nèi)點(diǎn)法的研究熱點(diǎn)主要轉(zhuǎn)向于半定優(yōu)化、半定互補(bǔ)、非凸優(yōu)化及組合優(yōu)化問(wèn)題上。

5自協(xié)調(diào)函數(shù)理論

自協(xié)調(diào)函數(shù)可謂是線性規(guī)劃算法研究的一個(gè)重大突破，也是我們后續(xù)研究的重點(diǎn)。自協(xié)調(diào)函數(shù)理論又名自協(xié)調(diào)障礙函數(shù)理論，為解線性和凸優(yōu)化問(wèn)題提供了多項(xiàng)式時(shí)間內(nèi)點(diǎn)算法。根據(jù)自協(xié)調(diào)障礙函數(shù)的參數(shù)就可以分析內(nèi)點(diǎn)算法的復(fù)雜性。

自協(xié)調(diào)函數(shù)定義：

一個(gè)凸函數(shù)fR-R對(duì)定義域內(nèi)的任意x滿足Lf"(x)<2f(x3/2,我們就稱它為自協(xié)調(diào)函數(shù)。如果函數(shù)(Rn-R對(duì)于任意直線滿足自協(xié)調(diào)條件，我們稱函數(shù)§(9是自協(xié)調(diào)函數(shù)。

自協(xié)調(diào)函數(shù)理論的關(guān)鍵是算法的復(fù)雜性由自協(xié)調(diào)函數(shù)的兩個(gè)參數(shù)決定，只要這兩個(gè)參數(shù)可以推導(dǎo)出，則可求得算法的復(fù)雜性。

然而目前常用的自協(xié)調(diào)函數(shù)形式只有對(duì)數(shù)障礙函數(shù)形式:負(fù)對(duì)數(shù)函數(shù)：f=一Igx及負(fù)商函數(shù)加上負(fù)對(duì)數(shù)函數(shù)：f=xgx^lgP]。

最近CReas等m指出有些內(nèi)核函數(shù)盡管沒(méi)有全局自協(xié)調(diào)性，卻能在局部自協(xié)調(diào)。而且，CR?s

部值 也可以較好的求得算法的復(fù)雜性。基于CRQ0S的思想，金正靜等1711提出了一個(gè)局部自協(xié)調(diào)函數(shù)，其形式如下

自協(xié)調(diào)函數(shù)理論的提出，為我們分析算法復(fù)雜性帶來(lái)了極大的便利。然而以上的自協(xié)調(diào)函數(shù)形式都要求核函數(shù)為正，這為我們的研究帶來(lái)了極大的限制。那么自協(xié)調(diào)函數(shù)是否存在不要求核函數(shù)為正的形式為我們研究自協(xié)調(diào)函數(shù)提供了方向。

6結(jié)束語(yǔ)

篇8

A. 1 B. [32]

C. 2 D. 3

2. 若實(shí)數(shù)[x]，[y]滿足不等式組[x+3y-3≥0，2x-y-3≤0，x-my+1≥0，]且[x+y]的最大值為9，則實(shí)數(shù)[m=]（ ）

A. [-2] B. [-1]

C. 1 D. 2

3. 設(shè)不等式組[x+y-11≥0，3x-y+3≥0，5x-3y+9≤0，]表示的平面區(qū)域?yàn)閇D]，若指數(shù)函數(shù)[y=ax]的圖象上存在區(qū)域D上的點(diǎn)，則[a]的取值范圍是（ ）

A. [（1，3]] B. [[2，3]]

C. [（1，2]] D. [[3，+∞）]

4. 某公司生產(chǎn)甲、乙兩種桶裝產(chǎn)品.已知生產(chǎn)甲產(chǎn)品1桶需耗[A]原料1千克、[B]原料2千克；生產(chǎn)乙產(chǎn)品1桶需耗[A]原料2千克，[B]原料1千克.每桶甲產(chǎn)品的利潤(rùn)是300元，每桶乙產(chǎn)品的利潤(rùn)是400元.公司在生產(chǎn)這兩種產(chǎn)品的計(jì)劃中，要求每天消耗[A]，[B]原料都不超過(guò)12千克. 通過(guò)合理安排生產(chǎn)計(jì)劃，從每天生產(chǎn)的甲、乙兩種產(chǎn)品中，公司共可獲得的最大利潤(rùn)是（ ）

A. 1800元 B. 2400元

C. 2800元 D. 3100元

5. 在平面直角坐標(biāo)系[xOy]中，[M]為不等式組[2x-y-2≥0，x+2y-1≥0，3x+y-8≤0]所表示的平面區(qū)域上一動(dòng)點(diǎn)，則[OM]斜率的最小值為（ ）

A. [2] B. [1]

C. [-13] D. [-12]

6. 已知[a>0]，[x，y]滿足約束條件[x≥1，x+y≤3，y≥a（x-3），]若[z=2x+y]的最小值為[1]，則[a=]（ ）

A. [14] B. [12]

C. [1] D. [2]

7. 某旅行社租用[A]，[B]兩種型號(hào)的客車(chē)安排900名客人旅行，[A]，[B]兩種車(chē)輛的載客量分別為36人和60人，租金分別為1600元/輛和2400元/輛，旅行社要求租車(chē)總數(shù)不超過(guò)21輛，且[B]型車(chē)不多于[A]型車(chē)7輛. 則租金最少為（ ）

A. 31200元 B. 36000元

C. 36800元 D. 38400元

8. 設(shè)變量[x，y]滿足[x+y≤1，]則[x+2y]的最大值和最小值分別為（ ）

A. 1，-1 B. 2，-2

C. 1，-2 D. 2，-1

9. 已知變量[x，y]滿足[2x-y≤0，x-2y+3≥0，x≥0，]則[z=log12（x+y+5）]的最小值為（ ）

A. -8 B. -4

C. -3 D. -2

10. 已知實(shí)數(shù)[x，y]滿足[y≥0y≤2x-1x+y≤m]，如果目標(biāo)函數(shù)[z=x-y]的最小值的取值范圍是[-2，-1]，則目標(biāo)函數(shù)的最大值的取值范圍是（ ）

A. [1，2] B. [3，6]

C. [5，8] D. [7，10]

二、填空題（每小題4分，共16分）

11. 已知[z=2x-y]，式中變量[x]，[y]滿足約束條件[y≤x，x+y≥1，x≤2，]，則[z]的最大值為 .

12. 拋物線[y=x2]在[x=1]處的切線與兩坐標(biāo)軸圍成三角形區(qū)域?yàn)閇D]（包含三角形內(nèi)部和邊界） . 若點(diǎn)[P（x，y）]是區(qū)域[D]內(nèi)的任意一點(diǎn)，則[x+2y]的取值范圍是 .

13. 設(shè)[P]是不等式組[x，y≥0，x-y≥-1，x+y≤3]表示的平面區(qū)域內(nèi)的任意一點(diǎn)，向量[m=（1，1）]，[n=（2，1）]，若[OP=λm][+μn]（[λ，μ]為實(shí)數(shù)），則[2λ+μ]的最大值為 .

14. 記不等式組[x≥0x+3y≥43x+y≤4]，所表示的平面區(qū)域?yàn)閇D]，若直線[y=a（x+1）]與[D]有公共點(diǎn)，則[a]的取值范圍是 .

三、解答題（共4小題，44分）

15. （10分）若變量[x，y]滿足約束條件[3≤2x+y≤9，6≤x-y≤9，]求[z=x+2y]的最小值.

篇9

1.靜態(tài)可行域下形如z=ax+by+c截距型線性目標(biāo)函數(shù)的最值

例1（2015年湖南卷）若變量x，y滿足約束條件則z=3x-y 的最小值為（ ）

解析：作出可行域（圖略），作直線l：3x-y=0，平移直線l利用數(shù)形結(jié)合法求最值。答案：選A

命題點(diǎn)睛 要求考生理解目標(biāo)函數(shù)的意義：把z=3x-y看作一條“動(dòng)直線”l，觀察其位置，從而確定目標(biāo)函數(shù)取得最值時(shí)所經(jīng)過(guò)的點(diǎn)。動(dòng)中有靜，動(dòng)直線l牽引出最優(yōu)解（定點(diǎn)），從而得到z的最小值。

2.動(dòng)態(tài)可行域下形如z=ax+by+c 截距型線性目標(biāo)函數(shù)最值的逆向問(wèn)題

例2 （2015年福建卷）變量x，y滿足約束條件若z=2x-y的最大值為2，則實(shí)數(shù)m 等于（ ）

A、-2 B、-1

C、1 D、2

圖1

解析 將目標(biāo)函數(shù)看作動(dòng)直線l：2x-z=0，當(dāng)z取最大值時(shí)，動(dòng)直線l縱截距最小。故當(dāng)m≤0時(shí)，不滿足題意;當(dāng)m>0時(shí)，由可行域如圖1所示，其中 是最優(yōu)解，代入目標(biāo)函數(shù)得：，得m=1。故選C。

命題點(diǎn)睛 以動(dòng)制靜，動(dòng)直線l的位置與參數(shù)m的符號(hào)相互制約，由兩條動(dòng)直線l：y=2x-z與l1：y=mx牽引出定點(diǎn)B最優(yōu)解。解含參數(shù)的線性規(guī)劃問(wèn)題，要善于從已知的可行域（動(dòng)態(tài)區(qū)域）中找出不變的（靜態(tài)）區(qū)域。困難在于對(duì)參數(shù)m的符號(hào)討論，以確定可行域，往往還要將動(dòng)直線l的斜率和可行域邊界的斜率比較，否則找出最優(yōu)解很容易出錯(cuò)。思維從靜態(tài)到動(dòng)態(tài)模式跳躍式開(kāi)放性發(fā)展，更能考查學(xué)生的創(chuàng)新應(yīng)用能力。

二、一線牽引出非線性目標(biāo)函數(shù)的最值

1.斜率型

例3 （2015年全國(guó)卷） 若x，y 滿足約束條件 則的最大值為 。

解析 作出可行域（圖略），由斜率的意義知是可行域內(nèi)的動(dòng)點(diǎn)P（x，y）與原點(diǎn)連線的斜率。答案：3

命題點(diǎn)睛 形如型的目標(biāo)函數(shù)，其表示可行域內(nèi)的動(dòng)點(diǎn)P（x，y）與定點(diǎn)M（a，b）連線的斜率。將直線PM繞點(diǎn)M旋轉(zhuǎn)，且確保動(dòng)點(diǎn)P在可行域內(nèi)，這樣由動(dòng)點(diǎn)與定點(diǎn)的連線牽引出斜率的取值范圍。

2.距離型：點(diǎn)點(diǎn)距、點(diǎn)線距

例4 （2016年山東卷） 若變量x，y滿足 則x2+y2的最大值是（ ）

A、4 B、9

C、10 D、12

解析x2+y2表示可行域內(nèi)的動(dòng)點(diǎn)（x，y）到原點(diǎn)O（0，0）距離的平方，可得x2+y2的最大值為10。故選C。

命題點(diǎn)睛 點(diǎn)點(diǎn)距離型實(shí)質(zhì)就是動(dòng)點(diǎn)與定點(diǎn)連線的長(zhǎng)度。

變式探究1（點(diǎn)線距）：（2016年浙江卷文?4改編）

若平面區(qū)域

（1） 的最大值是 。

（2）的最大值是 。

答案：（1）（2）

3.向量數(shù)量積型（夾角型、投影型）

例5 （2016年浙江卷） 在平面上，過(guò)點(diǎn)P作直線l的垂線所得的垂足稱為點(diǎn)P在直線l上的投影。由區(qū)域中的點(diǎn)在直線x+y-2=0上的投影構(gòu)成的線段記為AB，則|AB|（ ）。

A、 B、4

C、 D、6

答案：C

變式拓展2：（夾角型、投影型） 已知點(diǎn)A（3，1），O為坐標(biāo)原點(diǎn)，點(diǎn)P（x，y）滿足則

（1） 的最小值是 。

（2） 的最大值是 。

（3） 的取值范圍是 。

解析 如圖2所示，（1）

當(dāng)且僅當(dāng)與 反向時(shí)，取等號(hào);

（2）的最大值即在方向上的投影，為

（3）的最小值即在方向上的投影，為

其最大值即與共線時(shí)在方向上的投影，為，所以其取值范圍是

命題點(diǎn)睛 （1）中抓住定向量與動(dòng)向量的夾角;（2）中抓住動(dòng)線段OP在一條定直線OA上的投影;（3）與（2）正好反之。

圖2

4.直線與圓錐曲線相關(guān)位置型

圖3

例6 （2016年山東卷文?4改編） 設(shè)x，y滿足約束條件若Z=x2+4y2，則Z的取值范圍是 。

解析Z=x2+4y2表示中心在坐標(biāo)

原點(diǎn)，焦點(diǎn)在x 軸上的橢圓，當(dāng)此橢圓與直線x+y=1相切時(shí)，Z=x2+4y2最小，

由 得5y2-2y+1=0 ，由Δ=0

得 為最小值;當(dāng)此橢圓過(guò)點(diǎn) 時(shí)，為最大值，故所求范圍是

圖4

命題點(diǎn)睛 圓錐曲線（動(dòng)曲線）與一條定直線（或定點(diǎn)）的位置關(guān)系牽引出z的取值范圍，此題型新穎別致，賞心悅目，耐人尋味。

變式拓展3 設(shè)變量x，y滿足約束條件

其中k∈R，k>0.

篇10

教學(xué)重點(diǎn)

1.二元一次不等式(組)表示的平面區(qū)域;

2.應(yīng)用線性規(guī)劃的方法解決一些簡(jiǎn)單的實(shí)際問(wèn)題。

教學(xué)難點(diǎn)

線性規(guī)劃在實(shí)際問(wèn)題的應(yīng)用

高考展望

1.線性規(guī)劃是教材的新增內(nèi)容，高考中對(duì)這方面的知識(shí)涉及的還比較少，但今后將會(huì)成為新高考的熱點(diǎn)之一;

2.在高考中一般不會(huì)單獨(dú)出現(xiàn)，往往都是隱含在其他數(shù)學(xué)內(nèi)容的問(wèn)題之中，就是說(shuō)常結(jié)合其他數(shù)學(xué)內(nèi)容考查，往往都是容易題

知識(shí)整合

1.二元一次不等式(組)表示平面區(qū)域：一般地，二元一次不等式在平面直角坐標(biāo)系中表示直線某一側(cè)所有點(diǎn)組成的__________。我們把直線畫(huà)成虛線以表示區(qū)域_________邊界直線。當(dāng)我們?cè)谧鴺?biāo)系中畫(huà)不等式所表示的平面區(qū)域時(shí),此區(qū)域應(yīng)___________邊界直線，則把邊界直線畫(huà)成____________.

2.由于對(duì)在直線同一側(cè)的所有點(diǎn)，把它的坐標(biāo)代入，所得到實(shí)數(shù)的符號(hào)都__________，所以只需在此直線的某一側(cè)取一個(gè)特殊點(diǎn)，從的_________即可判斷>0表示直線哪一側(cè)的平面區(qū)域

3.二元一次不等式組是一組對(duì)變量x,y的__________，這組約束條件都是關(guān)于x,y的一次不等式，所以又稱為_(kāi)____________;

4.(a,b是實(shí)常數(shù))是欲達(dá)到最大值或_________所涉及的變量x,y的解析式，叫做______________。由于又是x,y的一次解析式，所以又叫做_________;

5.求線性目標(biāo)函數(shù)在_______下的最大值或____________的問(wèn)題，統(tǒng)稱為_(kāi)________問(wèn)題。滿足線性約束條件的解叫做_________，由所有可行解組成的集合叫做_________。分別使目標(biāo)函數(shù)取得____________和最小值的可行解叫做這個(gè)問(wèn)題的___________.

典型例題

例1.(課本題)畫(huà)出下列不等式(組)表示的平面區(qū)域，

1)2)3)

4)5)6)

例2.

1)畫(huà)出表示的區(qū)域，并求所有的正整數(shù)解

2)畫(huà)出以A(3，-1)、B(-1，1)、C(1，3)為頂點(diǎn)的的區(qū)域(包括各邊)，寫(xiě)出該區(qū)域所表示的二元一次不等式組，并求以該區(qū)域?yàn)榭尚杏虻哪繕?biāo)函數(shù)的最大值和最小值。

例3.1)已知，求的取值范圍

2)已知函數(shù)，滿足求的取值范圍

例4(04蘇19)制定投資計(jì)劃時(shí)，不僅要考慮可能獲得的盈利，而且要考慮可能出現(xiàn)的虧損。某投資人打算投資甲、乙兩個(gè)項(xiàng)目，根據(jù)預(yù)測(cè)，甲、乙項(xiàng)目可能的最大盈利率分別為100%和50%，可能的最大虧損率為30%和10%，投資人計(jì)劃投資金額不超過(guò)10萬(wàn)元，要求確?？赡艿馁Y金虧損不超過(guò)1.8萬(wàn)元，問(wèn)投資人對(duì)甲、乙兩個(gè)項(xiàng)目各投資打算多少萬(wàn)元，才能使可能的盈利最大?

例5.某人承攬一項(xiàng)業(yè)務(wù)，需做文字標(biāo)牌4個(gè)，繪畫(huà)標(biāo)牌6個(gè)，現(xiàn)有兩種規(guī)格原料，甲種規(guī)格每張3m，可做文字標(biāo)牌1個(gè)，繪畫(huà)標(biāo)牌2個(gè);乙種規(guī)格每張2m，可做文字標(biāo)牌2個(gè)，繪畫(huà)標(biāo)牌1個(gè),求兩種規(guī)格的原料各用多少?gòu)垼拍苁箍偟挠昧厦娣e最小?

例6.某人上午時(shí)乘摩托艇以勻速V海里/小時(shí)從A港出發(fā)到相距50海里的B港駛?cè)?，然后乘汽?chē)以勻速W千米/小時(shí)自B港向相距300km的C市駛?cè)ィ瑧?yīng)該在同一天下午4點(diǎn)到9點(diǎn)到達(dá)C市。設(shè)汽車(chē)、摩托艇所需時(shí)間分別為小時(shí)，如果已知所要經(jīng)費(fèi)P=(元)，那么V、W分別是多少時(shí)走得最經(jīng)濟(jì)?此時(shí)需花費(fèi)多少元?

鞏固練習(xí)

1.將目標(biāo)函數(shù)看作直線方程,z為參數(shù)時(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={是三角形的三邊長(zhǎng)}，則A所表示的平面區(qū)域(不含邊界的陰影部分)是()

5。在坐標(biāo)平面上，不等式組所表示的平面區(qū)域的面積為()

A。B。C。D。2