1、簡單的線性規(guī)劃,第三課時,宜豐中學(xué)歡迎您,宜豐中學(xué),江西省宜豐中學(xué),羅柳英,微軟公司董事長比爾蓋茨,簡單的線性規(guī)劃,簡單的線性規(guī)劃,(第三課時),線性目標函數(shù),Z的最大值為44,想一想:,線性約束條件,代數(shù)問題 (線性約束條件),圖解法,線性約 束條件,可行域,線性目 標函數(shù) Z=Ax+By,最優(yōu)解,圖解法的步驟：,1。畫可行域;,4。求出最優(yōu)解作答.,3。平移直線L0找最優(yōu)解;,2。作Z=0時的直線L0.,三個轉(zhuǎn)化,一.復(fù)習,平行線在y軸上 的截距 最值,某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品1t需消 耗A種礦石10t、B種礦石5t、煤4t；生產(chǎn)乙種產(chǎn)品1t需 消耗A種礦石4t、B種礦石

2、4t、煤9t. 每1t甲種產(chǎn)品的利潤 是600元,每1t乙種產(chǎn)品的利潤是1000元.工廠在生產(chǎn)這兩 種產(chǎn)品的計劃中要求消耗A種礦石不超過300t、 消耗B種 礦石不超過200t、消耗煤不超過360t.你應(yīng)如何安排甲乙 兩種產(chǎn)品的產(chǎn)量(精確到0.1t),才能使利潤總額達到最大?,二.實際應(yīng)用,探索問題一:,某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品1t需消耗A種礦石10t、B種礦石5t、煤4t；生產(chǎn)乙種產(chǎn)品1t需消耗A種礦石4t、B種礦石4t、煤9t.每1t甲種產(chǎn)品的利潤是600元,每1t乙種產(chǎn)品的利潤是1000元.工廠在生產(chǎn)這兩種產(chǎn)品的計劃中要求消耗A種礦石不超過300t、 消耗B種礦石不超過

3、200t、消耗煤不超過360t. 你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到0.1t),才能使利潤總額達到最大?,分 析 問 題:,2.本問題給定了哪些原材料？,1.該工廠生產(chǎn)哪些產(chǎn)品?,3.每噸產(chǎn)品對原材料的消耗量各是多少?,4.該工廠對原材料有何限定條件?,5.每種產(chǎn)品的利潤是多少?,原 材 料,每噸產(chǎn)品消耗的原材料,A種礦石,B種礦石,煤,甲產(chǎn)品(t),乙產(chǎn)品(t),10,5,4,4,4,9,原 材料 限 額,300,200,360,利 潤,600,1000,xt,yt,10 x+4y300,5x+4y200,4x+9y360,x0,y 0,z=600 x+1000y.,目標函數(shù)：,設(shè)生產(chǎn)甲

4、、乙兩種產(chǎn)品的產(chǎn)量分別為x t、yt,利潤總額為z元,解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為x t、yt,利潤總額為z元,那么,10 x+4y300,5x+4y200,4x+9y360,x0,y 0,z=600 x+1000y.,畫出以上不等式組所表示的可行域,作出直線L 600 x+1000y=0.,10 x+4y=300,5x+4y=200,4x+9y=360,600 x+1000y=0,M,答:應(yīng)生產(chǎn)甲產(chǎn)品約12.4噸，乙產(chǎn)品34.4噸，能使利潤總額達到最大。,(12.4,34.4),經(jīng)過可行域上的點M時,目標函數(shù)在y軸上截距最大.,90,30,75,40,50,40,此時z=600 x+10

5、00y取得最大值.,把直線L向右上方平移,線性規(guī)劃問題,列出約束條件 建立目標函數(shù),列約束條件時要注意到變量的范圍.,注意:,探索問題二:,目標函數(shù): z=x+y,2x+y=15,x+3y=27,x+2y=18,x+y =0,在可行域內(nèi)直線x+y=12經(jīng)過的整點是B(3,9)和C(4,8)，它們是最優(yōu)解.,作出直線L:x+y=0，,目標函數(shù):z= x+y,A(3.6,7.8),當直線L經(jīng)過點A時z=x+y=11.4,x+y=12,2,4,6,18,12,8,27,2,4,6,8,10,15,但它不是最優(yōu)整數(shù)解.,作直線x+y=12,答（略）,約束條件:,畫可行域,平移L找交點 及交點坐標,圖例

6、題4.gsp示,繼續(xù)平移L找最優(yōu)整數(shù)解,調(diào)整Z的值,X+y=11.4,A,調(diào)整優(yōu)值法,即先求非整數(shù)條件下的最優(yōu)解，調(diào)整Z的值使不定方程Ax+By=Z存在最大（小）的整點值，最后篩選出整點最優(yōu)解,即先打網(wǎng)格，描出可行域內(nèi)的整點，平移直線，最先經(jīng)過(或最后)經(jīng)過的整點坐標即為最優(yōu)整解,線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:,1.平移找解法：,2.調(diào)整優(yōu)值法：,小結(jié),咖啡館配制兩種飲料甲種飲料每杯含奶粉9g 、咖啡4g、糖3g,乙種飲料每杯含奶粉4g 、咖啡5g、糖10g已知每天原料的使用限額為奶粉3600g ，咖啡2000g糖3000g,如果甲種飲料每杯能獲利0.7元，乙種飲料每杯能獲利1.2元每天在原

7、料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種飲料各多少杯能獲利最大？,練習一.gsp -,鞏固練習一,解:設(shè)每天應(yīng)配制甲種飲料x杯，乙種飲料y杯，則,作出可行域： 目標函數(shù)為：z =0.7x +1.2y 作直線l:0.7x+1.2y=0， 把直線l向右上方平移至l1的位置時， 直線經(jīng)過可行域上的點C，且與原點距離最大， 此時z =0.7x +1.2y取最大值 解方程組 得點C的坐標為（200，240）,目標函數(shù)為：z =0.7x +1.2y,答:每天配制甲種飲料200杯,乙種飲料240杯可獲取最大利潤.,小結(jié),小結(jié):,實際問題,線性規(guī)劃 問題,圖解法,理論 最優(yōu)解,實際 最優(yōu)解,平移找解法,調(diào)整優(yōu)值法,整數(shù) 最優(yōu)解,思考問題一:,探索問題一(課本例題3)的最優(yōu)解是(12.4,34.4). 它存在最優(yōu)整數(shù)解嗎?若存在,求出最優(yōu)整數(shù)解. 若不存在,請說明理由.,例3.gsp圖形,作業(yè):習題7.4 第3題;第4題,結(jié)束,某貨運公司擬用集裝箱托運甲.乙兩種貨物,一個大集裝箱所裝托運貨物的總體積不能超過24 ,總重量不能超過1500kg,甲.乙兩種貨物每袋的體積.重量和可獲得的利潤,列表如下:,思考問題 二,問在一個大集裝箱內(nèi)這兩種(不能只裝一種)貨物各裝