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

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

)A．[6,15]

B．[7,15]C．[6,8] D．[7,8]分析：本題考查簡單線性規(guī)劃問題，解題關鍵是在可行域條件下找出兩個最大值點．解析：如下圖所示，由圖形知A(2,0)，C′(0,4)．B(4－s,2s－4)，C(0，s)．(1)當3≤s<4時，可行域是四邊形OABC，此時7≤z<8；(2)當4≤s≤5時，可行域是△OAC′，此時，zmax＝8.故選D.答案：D[例5]設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)部(包括邊界)，由目標函數(shù)作直線l：9a－c＝0，平移l到l1，l2.l1，l2與可行域分別相交于A，C兩點，解方程組答案：C[變式訓練5]已知f(a，b)＝ax＋by，若1≤f(1,1)≤2，－1≤f(1，－1)≤1，求f(2,1)的取值范圍．解析：因為f(a，b)＝ax＋by,1≤f(1,1)≤2，－1≤f(1，－1)≤1，所以畫出不等式組表示的平面區(qū)域．目標函數(shù)為f(2,1)＝2x＋y.作出直線2x＋y＝0.評析：由已知可得關于x，y的不等式組，畫出其表示的平面區(qū)域，從而得到f(2,1)的取值范圍．題型六綜合應用[變式訓練6]已知變量x，y滿