簡單的線性規(guī)劃問題.ppt

,3.3.2簡單的線性規(guī)劃問題（2課時）,一、導學提示，自主學習 二、新課引入，任務驅動 三、新知建構，典例分析 四、當堂訓練，針對點評 五、課堂總結，布置作業(yè),3. 3.2簡單線性規(guī)劃問題（2課時）,一、導學提示，自主學習,1.本節(jié)學習目標 （1）了解線性規(guī)劃的意義以及約束條件、線性目標函數(shù)、可行域、最優(yōu)解等相關的基本概念 （2）了解線性規(guī)劃的圖解法，并會用圖解法求線性目標函數(shù)的最大（?。┲?. （3）掌握對一些實際優(yōu)化問題建立線性規(guī)劃數(shù)學 模型并運用圖解法進行求解的基本方法和步驟 學習重點：線性規(guī)劃的圖解法 學習難點：尋求線性規(guī)劃問題的最優(yōu)解,一、導學提示，自主學習,2.本節(jié)主要題型 題型一 求線性目標函數(shù)的最值 題型二 線性規(guī)劃的實際應用 3.自主學習教材P87-P91 3. 3.2簡單的線性規(guī)劃問題,1、二元一次不等式表示哪個平面區(qū)域的判斷方法：,2、二元一次不等式組表示的平面區(qū)域,“直線定界、特殊點定域”,各個不等式所表示的平面區(qū)域的公共部分,二、新課引入，任務驅動,一.知識回顧：,通過本節(jié)的學習你能掌握簡單的線性規(guī) 劃問題的解法及步驟嗎？,二.任務驅動：,二、新課引入，任務驅動,三、新知建構，典例分析,一.簡單線性規(guī)劃有關概念 二.簡單線性規(guī)劃問題解題步驟,某工廠用A,B兩種配件生產甲,乙兩種產品, 每生產一件甲種產品使用4個A配件耗時1h, 每生產一件乙種產品使用4個B配件耗時2h, 該廠每天最多可從配件廠獲得16個A配件和 12個B配件,按每天工作8小時計算,該廠所有 可能的日生產安排是什么?,若生產1件甲種產品獲利2萬元,生產1 件乙 種產品獲利3萬元,采用哪種生產安排利潤最大?,三、新知建構，典例分析,問題引入:,把問題1的有關數(shù)據(jù)列表表示如下:,設甲,乙兩種產品分別生產x,y件,將上面不等式組表示成平面上的區(qū)域,區(qū)域內 所有坐標為整數(shù)的點P(x,y),安排生產任務x,y 都是有意義的.,設甲,乙兩種產品分別生產x,y件,由己知條件可得:,問題：求利潤2x+3y的最大值.,若設利潤為z,則z=2x+3y,這樣上述問題轉化為:,當x,y在滿足上述約束條件時,z的最大值為多少?,當點P在可允許的取值范圍變化時,M（4，2）,問題：求利潤z=2x+3y的最大值.,象這樣關于x,y一次不等 式組的約束條件稱為 線性約束條件,Z=2x+3y稱為目標函數(shù),(因這里 目標函數(shù)為關于x,y的一次式,又 稱為線性目標函數(shù),在線性約束下求線性目標函數(shù) 的最值問題,統(tǒng)稱為線性規(guī)劃,一.線性規(guī)劃有關概念:,滿足線性約束的解(x,y)叫做可行解,所有可行解組成的集合叫做可行域,使目標函數(shù)取得最值的可行解叫做這個 問題的最優(yōu)解,變式：若生產一件甲產品獲利1萬元， 生產一件乙產品獲利3萬元，采用哪種 生產安排利潤最大？,N（2，3）,變式：求利潤z=x+3y的最大值.,線性規(guī)劃有關概念:,17,2、畫： 畫出線性約束條件所表示的可行域；,3、移： 在線性目標函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點 且縱截距最大或最小的直線；,4、求：通過解方程組求出最優(yōu)解；,5、答：作出答案。,1、找 找出線性約束條件、目標函數(shù)；,二.線性規(guī)劃問題解題步驟:,三、新知建構，典例分析,說明:,二、最優(yōu)解一般在可行域的頂點處取得，也有可能在邊界處取得,四、在哪個頂點取得不僅與B的符號有關， 而且還與直線 Z=Ax+By的斜率有關,一、先定可行域和平移方向，再找最優(yōu)解。,三、新知建構，典例分析,三、求線性目標函數(shù)的最優(yōu)解，要注意分析線性目標函數(shù)所表示的幾何意義 -與y軸上的截距相關的數(shù)。,2 .典例分析： 題型一 求線性目標函數(shù)的最值 題型二 線性規(guī)劃的實際應用,三、新知建構，典例分析,x4y3，,例1.已知變量 x，y滿足 3x5y25，,求 z2xy 的,x1， 最大值和最小值 思維突破：把z 看成直線在y 軸上的截距，先畫出可行域， 再求z 的最值,三、新知建構，典例分析,題型一.求線性目標函數(shù)的最值:,自主解答：作出不等式組 所表示的可行域，如圖 :,設直線 l0：2xy0，直線 l：2xyz，則 z 的幾何意義,是直線 y2xz 在 y 軸上的截距,顯然，當直線越往上移動時，對應在 y 軸上的截距越大， 即 z 越大；當直線越往下移動時，對應在 y 軸上的截距越小， 即 z 越小,三、新知建構，典例分析,作一組與直線 l0 平行的直線系 l，上下平移，可得：,點 A(5,2)時，zmax25212； 當直線 l 移動到直線 l2 時，即過,當直線 l 移動到直線 l1 時，即過 點 B(1,1)時，zmin211,正確作出可行域后，將目標函數(shù)變?yōu)橹本€方程,的斜截式的形式，應注意該直線在y 軸上的截距與目標函數(shù)z 取值的關系再注意該直線的斜率與可行域邊界直線的斜率關 系，以便準確找到最優(yōu)解,3.,三、新知建構，典例分析,y1，,例2.已知實數(shù) x，y 滿足 y2x1， xym，,如果目標函數(shù) z,xy 的最小值為1，則實數(shù) m(,),A7,B5,C4,D3,思維突破：畫出x，y 滿足的可行域，可得直線y2x1 與直線xym 的交點使目標函數(shù)zxy 取得最小值,三、新知建構，典例分析,答案：B,三、新知建構，典例分析,線性規(guī)劃的理論和方法主要在兩類問題中得到應用: 一、在人力、物力、資金等資源一定的條件下，如何使用它們來完成最多的任務； 二、給定一項任務，如何合理安排和規(guī)劃，能以最少的人力、物力、資金等資源來完成該項任務 下面我們就來看看線性規(guī)劃在實際中的一些應用：,三、新知建構，典例分析,題型二.線性規(guī)劃的實際應用:,例3. 營養(yǎng)學家指出,成人良好的日常飲食應該至少提供0.075kg的碳水化合物,0.06kg的蛋白質,0.06kg的脂肪.1kg食物A含有0.105kg碳水化合物,0.07kg蛋白質,0.14kg脂肪,花費28元;而1kg食物B含有0.105kg碳水化合物,0.14kg蛋白質,0.07kg脂肪,花費21元.為了滿足營養(yǎng)專家指出的日常飲食要求,同時使花費最低,需要同時食用食物A和食物B多少kg？,三、新知建構，典例分析,分析：將已知數(shù)據(jù)列成表格,三、新知建構，典例分析,解：設每天食用xkg食物A，ykg食物B，總成本為z，那么,目標函數(shù)為：z28x21y,作出二元一次不等式組所表示的平面區(qū)域，即可行域,1、找,三、新知建構，典例分析,把目標函數(shù)z28x21y 變形為,x,y,o,/ 57,5/7,6/7,3/7,3/7,6/7,它表示斜率為 縱截距隨z變化的一組平行直線,是直線在y軸上的截距，當截距最小時，z的值最小。,M,如圖可見，當直線z28x21y 經過可行域上的點M時，縱截距最小，即z最小。,2、畫,3、移,M點是兩條直線的交點，解方程組,得M點的坐標為：,所以zmin28x21y16,由此可知，每天食用食物A143g，食物B約571g，能夠滿足日常飲食要求，又使花費最低，最低成本為16元。,4、求,5、答,31,解線性規(guī)劃問題的步驟：,（1）2、畫： 畫出線性約束條件所表示的可行域；,（2）3、移： 在線性目標函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點 且縱截距最大或最小的直線；,（3）4、求：通過解方程組求出最優(yōu)解；,（4）5、答：作出答案。,1、找 找出線性約束條件、目標函數(shù)；,三、新知建構，典例分析,例4.某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)示 ：格的小鋼板的塊數(shù)如下表所,解：設需截第一種鋼板x張，第二種鋼板y張，鋼板總張數(shù)為Z則,2x+y15,x+2y18,x+3y27,x0,y0,某顧客需要A,B,C三種規(guī)格的成品分別為15，18，27塊，若你是經理,問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張數(shù)最少。,分 析 問 題:,標目函數(shù): z=x+y,2x+y=15,x+3y=27,x+2y=18,x+y =0,直線x+y=12經過的整點是B(3,9)和C(4,8)，它們是最優(yōu)解.,作出直線L:x+y=0，,目標函數(shù):z= x+y,A(3.6,7.8),當直線L經過點A時z=x+y=11.4,x+y=12,解得交點B,C的坐標B(3,9)和C(4,8),2,4,6,18,12,8,27,2,4,6,8,10,15,但它不是最優(yōu)整數(shù)解.,作直線x+y=12,約束條件:,畫可行域,平移L找交點及交點坐標,調整優(yōu)解法,2x+y=15,x+3y=27,x+2y=18,x+y =0,經過可行域內的整點B(3,9)和C(4,8)且和原點距離最近的直線是x+y=12，它們是最優(yōu)解.,作出一組平行直線t = x+y，,目標函數(shù)t = x+y,打網格線法,在可行域內打出網格線，,當直線經過點A時t=x+y=11.4,但它不是最優(yōu)整數(shù)解，,將直線x+y=11.4繼續(xù)向上平移，,1,2,1,2,18,27,15,9,7,8,在可行域內找出最優(yōu)解、線性規(guī)劃整數(shù)解問題的一般方法是：,1.若區(qū)域“頂點”處恰好為整點，那么它就是最優(yōu)解；（在包括邊界的情況下） 2.若區(qū)域“頂點”不是整點或不包括邊界時，應先求出該點坐標，并計算目標函數(shù)值Z，然后在可行域內適當放縮目標函數(shù)值，使它為整數(shù)，且與Z最接近，在這條對應的直線中，取可行域內整點，如果沒有整點，繼續(xù)放縮，直至取到整點為止。 3.在可行域內找整數(shù)解，一般采用平移找解法，即打網絡、找整點、平移直線、找出整數(shù)最優(yōu)解,例5.一個化肥廠生產甲、乙兩種混合肥料，生產1車皮甲種肥料的主要原料是磷酸鹽4t、硝酸鹽18t；生產1車皮乙種肥料需要的主要原料是磷酸鹽1t、硝酸鹽15t?，F(xiàn)庫存磷酸鹽10t、硝酸鹽66t，在此基礎上生產這兩種混合肥料。列出滿足生產條件的數(shù)學關系式，并畫出相應的平面區(qū)域。并計算生產甲、乙兩種肥料各多少車皮，能夠產生最大的利潤？,解：設x、y分別為計劃生產甲、乙兩種混合肥料的車皮數(shù)，于是滿足以下條件：,x,y,o,例6 在上一節(jié)例4（P85）中，若生產1車皮甲種肥料，產生的 利潤為10000元；生產1車皮乙種肥料，產生的利潤為5000元， 那么分別生產甲、乙兩種肥料各多少車皮，能夠產生最大利潤？,解：設生產甲種肥料x車皮、乙種肥料y車皮，能夠產生利潤 Z萬元。,目標函數(shù)為：,可行域如圖。,把z=x+0.5y變形為,得到斜率為-2，在y軸上的截距為2z, 隨z變化的一族平行直線。,由圖可以看出，當直線y=-2x+2z經過 可行域上的點M時，截距2z最大，即 Z最大。,解方程組,得M的坐標為（2，2）,所以,答：生產甲種、乙種肥料各2車皮，能夠 產生最大利潤，最大利潤為3萬元。,即先求非整數(shù)條件下的最優(yōu)解，調整Z的值使不定方程Ax+By=Z存在最大（小）的整點值，最后篩選出整點最優(yōu)解,即先打網格，描出可行域內的整點，平移直線，最先經過或最后經過的整點坐標即為最優(yōu)整解,線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:,1.平移找解法：,2.調整優(yōu)解法：,三、新知建構，典例分析,x2y40，,1已知實數(shù) x，y 滿足約束條件 2xy20， 3xy30，,則目標,函數(shù) zx2y 的最大值的可行解為_,(2,3),四、當堂訓練，針對點評,變式訓練1-1：,xy50，,2已知 x，y 滿足 x3， xyk0，,且 z2x4y 的最小值,),為6，則常數(shù) k( A2,B9,C3,D0,解析：畫圖后知：當 x3 時 z2x4y 取最小值6.,D,四、當堂訓練，針對點評,2.某廠擬生產甲、乙兩種適銷產品，每件銷售收入分別為3000元、2000元，甲、乙產品都需要在A、B兩種設備上加工，在每臺A、B上加工1件甲所需工時分別為1h、2h，A、B兩種設備每月有效使用臺數(shù)分別為400h和500h。如何安排生產可使收入最大？,解：設每月生產甲產品x件，生產乙產品y件，每月收入為z，目標函數(shù)為Z3x2y，滿足的條件是：,變式訓練2-1：,Z 3x2y 變形為 它表示斜率為 的直線系，Z與這條直線的截距有關。,X,Y,O,400,200,250,500,當直線經過點M時，截距最大，Z最大。,M,解方程組,可得M（200，100）,Z 的最大值Z 3x2y800,故生產甲產品200件，乙產品100件，收入最大，為80萬元。,五、課堂總結，布置作業(yè),1課堂總結： （1）涉及知識點： 簡單的線性規(guī)劃問題。 （2）涉及數(shù)學思想方法： 轉化與回歸思想；數(shù)形結合思想；分類與整合 思想。,線性目標函數(shù)目標函數(shù)是關于變量的一次解析式,1.目標函數(shù)要求最值的函數(shù),線性規(guī)劃在線性約束條件下求線性目標函數(shù)的最大值或最小值問題,可行解滿足線形約束條件的解叫做可行解,可行域由所有可行解