3.3.2簡單的線規(guī)劃1.ppt

1、1,一.復習回顧,1.在同一坐標系上作出下列直線:,2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7,x,Y,o,簡單線性規(guī)劃(1)-可行域上的最優(yōu)解,2,y,問題1：x 有無最大（?。┲担?問題2：y 有無最大（?。┲?？,問題3：2x+y 有無最大（?。┲担?2.作出下列不等式組的所表示的平面區(qū)域,3,二.提出問題,把上面兩個問題綜合起來:,設z=2x+y,求滿足,時,求z的最大值和最小值.,4,y,直線L越往右平移,t隨之增大.,以經(jīng)過點A(5,2)的直線所對應的t值最大;經(jīng)過點B(1,1)的直線所對應的t值最小.,可以通過比較可行域邊界頂點的目標函數(shù)值大小得到。,思

2、考：還可以運用怎樣的方法得到目標函數(shù)的最大、最小值？,5,線性規(guī)劃,問題： 設z=2x+y，式中變量滿足 下列條件： 求z的最大值與最小值。,目標函數(shù) （線性目標函數(shù)）,線性約 束條件,象這樣關于x,y一次不等式組的約束條件稱為線性約束條件,Z=2x+y稱為目標函數(shù),(因這里目標函數(shù)為關于x,y的一次式,又稱為線性目標函數(shù),6,線性規(guī)劃,線性規(guī)劃：求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題,可行解 ：滿足線性約束條件的解(x，y)叫可行解；,可行域 ：由所有可行解組成的集合叫做可行域；,最優(yōu)解 ：使目標函數(shù)取得最大或最小值的可行解叫線性規(guī)劃問題的最優(yōu)解。,可行域,

3、2x+y=3,2x+y=12,(1,1),(5,2),7,線性目標函數(shù),線性約束條件,線性規(guī)劃問題,任何一個滿足不等式組的（x,y）,可行解,可行域,所有的,最優(yōu)解,目標函數(shù)所表示的幾何意義在y軸上的截距或其相反數(shù)。,8,線性規(guī)劃,例1 解下列線性規(guī)劃問題： 求z=2x+y的最大值和最小值，使式中x、y滿足下 列條件：,解線性規(guī)劃問題的一般步驟： 第一步：在平面直角坐標系中作出可行域； 第二步：在可行域內(nèi)找到最優(yōu)解所對應的點； 第三步：解方程的最優(yōu)解，從而求出目標函數(shù)的最大值或最小值。,探索結論,2x+y=0,2x+y=-3,2x+y=3,答案：當x=-1,y=-1時，z=2x+y有最小值3.

4、,當x=2,y=-1時，z=2x+y有最大值3.,也可以通過比較可行域邊界頂點的目標函數(shù)值大小得到。,9,線性規(guī)劃,例2 解下列線性規(guī)劃問題： 求z=300 x+900y的最大值和最小值，使式中x、y滿足下列條件：,探索結論,x+3y=0,300 x+900y=0,300 x+900y=112500,答案：當x=0,y=0時，z=300 x+900y有最小值0.,當x=0,y=125時，z=300 x+900y有最大值112500.,10,例3: 某工廠用A,B兩種配件生產(chǎn)甲,乙兩種產(chǎn)品,每生產(chǎn)一件甲種產(chǎn)品使用4個A配件耗時1h,每生產(chǎn)一件乙種產(chǎn)品使用4個B配件耗時2h,該廠每天最多可從配件廠

5、獲得16個A配件和12個B配件,按每天工作8小時計算,該廠所有可能的日生產(chǎn)安排是什么?,若生產(chǎn)1件甲種產(chǎn)品獲利2萬元,生產(chǎn)1 件乙 種產(chǎn)品獲利3萬元,采用哪種生產(chǎn)安排利潤最大?,把例3的有關數(shù)據(jù)列表表示如下:,11,將上面不等式組表示成平面上的區(qū)域,區(qū)域內(nèi) 所有坐標為整數(shù)的點P(x,y),安排生產(chǎn)任務x,y 都是有意義的.,解：設甲,乙兩種產(chǎn)品分別生產(chǎn)x,y件,由己知條件可得:,問題：求利潤2x+3y的最大值.,線性約束條件,12,若設利潤為z,則z=2x+3y,這樣上述問題轉(zhuǎn)化為:,當x,y在滿足上述約束條件時,z的最大值為多少?,當點P在可允許的取值范圍變化時,13,M（4，2）,問題：求

6、利潤z=2x+3y的最大值.,變式：若生產(chǎn)一件甲產(chǎn)品獲利1萬元，生產(chǎn)一件乙產(chǎn)品獲利3萬元，采用哪種生產(chǎn)安排利潤最大？,14,N（2，3）,變式：求利潤z=x+3y的最大值.,15,解線性規(guī)劃應用問題的一般步驟：,2）設好變元并列出不等式組和目標函數(shù),3）由二元一次不等式表示的平面區(qū)域作出可行域；,4）在可行域內(nèi)求目標函數(shù)的最優(yōu)解,1）理清題意，列出表格：,5)還原成實際問題,(準確作圖，準確計算),畫出線性約束條件所表示的可行域，畫圖力保準確；,法1：移在線性目標函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點且縱截距最大或最小的直線；,法2：算線性目標函數(shù)的最大（?。┲狄话阍诳尚?/p>

7、域的頂點處取得，也可能在邊界處取得（當兩頂點的目標函數(shù)值相等時最優(yōu)解落在一條邊界線段上）。此法可彌補作圖不準的局限。,16,例4、一個化肥廠生產(chǎn)甲、乙兩種混合肥料，生產(chǎn)1車皮甲種肥料的主要原料是磷酸鹽4t、硝酸鹽18t；生產(chǎn)1車皮乙種肥料需要的主要原料是磷酸鹽1t、硝酸鹽15t。現(xiàn)庫存磷酸鹽10t、硝酸鹽66t，在此基礎上生產(chǎn)這兩種混合肥料。列出滿足生產(chǎn)條件的數(shù)學關系式，并畫出相應的平面區(qū)域。并計算生產(chǎn)甲、乙兩種肥料各多少車皮，能夠產(chǎn)生最大的利潤？,分析：設x、y分別為計劃生產(chǎn)甲、乙兩種混合肥料的車皮數(shù)，于是滿足以下條件：,x,y,o,17,解：設生產(chǎn)甲種肥料x車皮、乙種肥料y車皮， 能夠產(chǎn)生

8、利潤Z萬元。目標函數(shù)為Zx0.5y， 約束條件為下例不等式組，可行域如圖紅色陰影部分：,把Zx0.5y變形為y2x2z，它表示斜率為2，在y軸上的截距為2z的一組直線系。,x,y,o,由圖可以看出，當直線經(jīng)過可行域上的點M時，截距2z最大，即z最大。,答：生產(chǎn)甲種、乙種肥料各2車皮，能夠產(chǎn)生最大利潤，最大利潤為3萬元。,M,容易求得M點的坐標為 （2，2），則Zmax3,線性約束條件,18,三、課堂練習,(1)已知 求z=2x+y的最大值和最小值。,19,5,5,1,O,x,y,y-x=0,x+y-1=0,1,-1,y+1=0,A(2,-1),B(-1,-1),20,練習2、已知 求z=3x+5y的最大值和最小值。,21,5,5,1,O,x,y,1,-1,5x+3y=15,X-5y=3,y=x+1,A(-2,-1),B(3/2,5/2),22,練習3：,某工廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)1t甲種產(chǎn)品需要A種原料4t、 B種原料1