《簡單的線性規(guī)劃》課件 全省一等獎(jiǎng)

簡單線性規(guī)劃一、線性規(guī)劃問題及可行解、可行域、最優(yōu)解的概念1．如果兩個(gè)變量x、y滿足一元一次不等式組，求這兩個(gè)變量的一個(gè)線性函數(shù)的最大值或最小值，那么我們就稱這個(gè)線性函數(shù)為①________，稱一次不等式組為②________，像這樣的問題叫做③________.知識(shí)梳理2．在線性規(guī)劃問題中，滿足約束條件的解(x，y)稱為④________，由所有可行解組成的集合稱為⑤________.分別使目標(biāo)函數(shù)取得最小值或最大值的可行解稱為⑥________，最優(yōu)解一般在⑦_(dá)_______上，而且通常在可行域的頂點(diǎn)處取得．友情提示：(1)求最優(yōu)解前，令⑧________的目的是確定目標(biāo)函數(shù)在可行域內(nèi)的什么位置有可行解；(2)一般來說，最優(yōu)解為多邊形區(qū)域的⑨________，但不是絕對的，有時(shí)也可能是多邊形區(qū)域⑩________；(3)對于目標(biāo)函數(shù)所在直線與可行域內(nèi)的某一條邊的斜率較為接近時(shí)，如果直接在圖形上判斷不太方便，可以考慮比較它們?________，從而確定最優(yōu)解；(4)在求目標(biāo)函數(shù)的最優(yōu)解的步驟中有一個(gè)關(guān)鍵的地方，就是要判斷在某個(gè)點(diǎn)處，目標(biāo)函數(shù)取得?________，這個(gè)判斷可以將點(diǎn)的坐標(biāo)代入完成，也可以利用目標(biāo)函數(shù)中z的幾何意義完成．如函數(shù)z＝3x＋y，z是其對應(yīng)直線在y軸上的?________，則只要看過某點(diǎn)時(shí)直線的截距是?________進(jìn)行判斷．二、線性規(guī)劃問題的求解程序在約束條件下，當(dāng)b>0時(shí)，求目標(biāo)函數(shù)z＝ax＋by＋c的最小值或最大值的求解程序?yàn)椋?1)作出?________；(2)作出直線l0：?________；(3)確定l0的?________，依可行域判斷取得最優(yōu)解的點(diǎn)；(4)解相關(guān)方程組，求出?________，從而得出目標(biāo)函數(shù)的最小值或最大值．答案：①目標(biāo)函數(shù)②約束條件③二元線性規(guī)劃問題④可行解⑤可行域⑥最優(yōu)解⑦可行域的邊界⑧z＝0⑨頂點(diǎn)⑩一條邊上的點(diǎn)?斜率的大小?最大值還是最小值?截距?最大還是最小?可行域?ax＋by＝0?平移方向?最優(yōu)解1.簡單線性規(guī)劃應(yīng)用問題的求解步驟(1)設(shè)：設(shè)出變量x，y，寫出約束條件及目標(biāo)函數(shù)．(2)作：作出可行域．(3)移：作一組平行直線l，平移l，找最優(yōu)解．(4)解：聯(lián)立方程組求最優(yōu)解，并代入目標(biāo)函數(shù)，求出最值．(5)答：寫出答案．總之：求解線性規(guī)劃問題的基本程序是作可行域，畫平行線，解方程組，求最值．名師解疑線性規(guī)劃方法又稱為圖解法．解決線性規(guī)劃問題時(shí)，首先畫出不等式組的平面區(qū)域，然后作出直線，求出可行域中的最優(yōu)解．學(xué)習(xí)探究題型一簡單線性規(guī)劃中的最值問題解析：作出可行域如下圖所示，并求出頂點(diǎn)的坐標(biāo)A(1,3)、B(3,1)、C(7,9)．(1)易知可行域內(nèi)各點(diǎn)均在直線x＋2y－4＝0的上方，故x＋2y－4>0，將C(7,9)代入z得最大值為21.(2)z＝x2＋(y－5)2表示可行域內(nèi)任一點(diǎn)(x，y)到定點(diǎn)M(0,5)的距離的平方，過M作直線AC的垂線，易知垂足N在線段AC上，故z的最小值是|MN|2＝.(2)設(shè)u＝x2＋y2，則為點(diǎn)(x，y)到原點(diǎn)(0,0)的距離．結(jié)合不等式組所表示的區(qū)域，不難知道：點(diǎn)B到原點(diǎn)距離最大；而當(dāng)(x，y)在原點(diǎn)時(shí)，距離為0，∴umax＝(－1)2＋(－6)2＝37，umin＝0，故4x－3y的最大值為14，最小值為－18；x2＋y2的最大值為37，最小值為0.如何求線性規(guī)劃問題的最優(yōu)整數(shù)解是整個(gè)線性規(guī)劃中最復(fù)雜也是最困難的問題．為了解決這類問題，可以采用如下兩種方法：題型二線性規(guī)劃問題中取得最值得整點(diǎn)坐標(biāo)問題(1)“局部微調(diào)法”所謂“局部微調(diào)法”是指：在求線性目標(biāo)函數(shù)z＝ax＋by＋c的最優(yōu)整數(shù)解時(shí)，先根據(jù)基本方法求出目標(biāo)函數(shù)的最值，但若此時(shí)最優(yōu)解不是整數(shù)，即此時(shí)直線經(jīng)過的點(diǎn)A(x0，y0)不是整點(diǎn)，可先根據(jù)A(x0，y0)求出此時(shí)的z0＝ax0＋by0＋c，然后根據(jù)條件把z0的值微調(diào)為大于(或小于)z0且與z0最接近的整數(shù)z1，再求出直線z1＝ax＋by＋c與可行域各直線的交點(diǎn)坐標(biāo)，然后在這些交點(diǎn)之間尋找整點(diǎn)．(2)“小范圍搜索法”“小范圍搜索法”的步驟為：①在邊界折線頂點(diǎn)附近的小范圍內(nèi)搜索一個(gè)可行域內(nèi)的整點(diǎn)；②在該點(diǎn)作一條斜率為 (其中A、B分別為目標(biāo)函數(shù)中變量x、y的系數(shù))的直線，與可行域邊界折線相交得到一個(gè)小范圍的區(qū)域；③在這個(gè)小范圍區(qū)域內(nèi)繼續(xù)搜索全部最優(yōu)整數(shù)解．解析：(1)由x>0，－nx＋3n≥y>0，得0<x<3，∴x＝1或x＝2，∴Dn內(nèi)的整點(diǎn)在直線x＝1或x＝2上．記直線y＝－nx＋3n為l，l與直線x＝1、x＝2的交點(diǎn)的縱坐標(biāo)分別為y1、y2，則y1＝－n＋3n＝2n，y2＝－2n＋3n＝n，∴an＝3n(n∈N*)．[例3]設(shè)實(shí)數(shù)x，y滿足不等式組(1)畫出點(diǎn)(x，y)所在平面區(qū)域；(2)設(shè)a>－1，在(1)所求的區(qū)域內(nèi)，求函數(shù)f(x，y)＝y(tǒng)－ax的最大值和最小值．題型三目標(biāo)函數(shù)中的參數(shù)問題其中AB：y＝2x－5；BC：x＋y＝4；CD：y＝－2x＋1；DA：x＋y＝1.(2)f(x，y)表示直線l：y－ax＝k在y軸上截距，且直線l與(1)中所求區(qū)域有公共點(diǎn)．∵a>－1，∴當(dāng)直線l過頂點(diǎn)C時(shí)，f(x，y)最大，∵C點(diǎn)的坐標(biāo)為(－3,7)．∴f(x，y)的最大值為7＋3a.如果－1≤a≤2，那么當(dāng)直線l過頂點(diǎn)A(2，－1)時(shí)，f(x，y)最小，最小值為－1－2a.如果a>2，那么當(dāng)直線l過頂點(diǎn)B(3,1)時(shí)，f(x，y)最小，最小值為1－3a.解析：一般情況下，當(dāng)z取最大值時(shí)，直線所經(jīng)過的點(diǎn)都是唯一的，但若直線平行于邊界直線，如下圖所示，即直線z＝ax＋y(a>0)平行于直線AC，則直線經(jīng)過線段AC上任意一點(diǎn)時(shí)，z均取得最大值，此時(shí)滿足條件，即有無數(shù)多個(gè)點(diǎn)使函數(shù)取得最大值．分析知當(dāng)直線y＝－ax＋z剛好移動(dòng)到直線AC時(shí)，將會(huì)有無數(shù)多個(gè)點(diǎn)使函數(shù)取得最大值．題型四約束條件中含參數(shù)問題[變式訓(xùn)練4]如下圖，在約束條件下當(dāng)3≤s≤5時(shí)，目標(biāo)函數(shù)z＝3x＋2y的最大值的變化范圍是(

)A．[6,15]

B．[7,15]C．[6,8] D．[7,8]分析：本題考查簡單線性規(guī)劃問題，解題關(guān)鍵是在可行域條件下找出兩個(gè)最大值點(diǎn)．解析：如下圖所示，由圖形知A(2,0)，C′(0,4)．B(4－s,2s－4)，C(0，s)．(1)當(dāng)3≤s<4時(shí)，可行域是四邊形OABC，此時(shí)7≤z<8；(2)當(dāng)4≤s≤5時(shí)，可行域是△OAC′，此時(shí)，zmax＝8.故選D.答案：D[例5]設(shè)f(x)＝ax2－c，并且－4≤f(1)≤－1，－1≤f(2)≤5，那么f(3)適合的條件是 (

)A．－7≤f(3)≤26 B．－4≤f(3)≤5C．－1≤f(3)≤20 D.題型五線性規(guī)劃與不等式解析：由已知條件得記z＝f(3)，則z＝9a－c.如上圖，由約束條件作出可行域ABCD內(nèi)部(包括邊界)，由目標(biāo)函數(shù)作直線l：9a－c＝0，平移l到l1，l2.l1，l2與可行域分別相交于A，C兩點(diǎn)，解方程組答案：C[變式訓(xùn)練5]已知f(a，b)＝ax＋by，若1≤f(1,1)≤2，－1≤f(1，－1)≤1，求f(2,1)的取值范圍．解析：因?yàn)閒(a，b)＝ax＋by,1≤f(1,1)≤2，－1≤f(1，－1)≤1，所以畫出不等式組表示的平面區(qū)域．目標(biāo)函數(shù)為f(2,1)＝2x＋y.作出直線2x＋y＝0.評析：由已知可得關(guān)于x，y的不等式組，畫出其表示的平面區(qū)域，從而得到f(2,1)的取值范圍．題型六綜合應(yīng)用[變式訓(xùn)練6]已知變量x，y滿