3[1]34簡單的線性規(guī)劃問題(實(shí)際應(yīng)用)

1、3.3.3簡單的線性規(guī)劃問題簡單的線性規(guī)劃問題 實(shí)際應(yīng)用實(shí)際應(yīng)用5x+4y=202x+3y=12線性目標(biāo)函數(shù)),(M720712Z的最大值為的最大值為44已知實(shí)數(shù)已知實(shí)數(shù)x,y滿足下列條件滿足下列條件:5x+4y 202x+3y 12x 0y0求求z=9x+10y的最大值的最大值.最優(yōu)解可行域9x+10y=0想一想想一想: :線性約束條件 01 2345 6123456xy代數(shù)問題代數(shù)問題(線性約束條件線性約束條件)圖解法圖解法轉(zhuǎn)化轉(zhuǎn)化線性約線性約束條件束條件可行域可行域轉(zhuǎn)化轉(zhuǎn)化線性目線性目標(biāo)函數(shù)標(biāo)函數(shù)Z=Ax+By一組平行線一組平行線B BZ Zx xy y 轉(zhuǎn)化轉(zhuǎn)化最優(yōu)解最優(yōu)解尋找平行線組

2、尋找平行線組的縱截距的縱截距 最值最值 四個(gè)步驟：四個(gè)步驟：1、畫畫4、答答3、移移2、作作三個(gè)轉(zhuǎn)化三個(gè)轉(zhuǎn)化一一. .復(fù)習(xí)復(fù)習(xí)轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化四個(gè)步驟四個(gè)步驟：1。畫畫（畫可行域）（畫可行域）三個(gè)轉(zhuǎn)化三個(gè)轉(zhuǎn)化4。答答（求出點(diǎn)的坐標(biāo)，并轉(zhuǎn)化為最優(yōu)解）（求出點(diǎn)的坐標(biāo)，并轉(zhuǎn)化為最優(yōu)解）3。移移（平移直線（平移直線L 。尋找使縱截距取得最值時(shí)的點(diǎn)）。尋找使縱截距取得最值時(shí)的點(diǎn)）2。作作（作（作z=Ax+By=0時(shí)的直線時(shí)的直線L 。）。）圖解法圖解法想一想想一想( (結(jié)論結(jié)論): ):線性約束條件線性約束條件可行域可行域線性目標(biāo)函數(shù)線性目標(biāo)函數(shù)Z=Ax+By一組平行線一組平行線BZxy最優(yōu)解最

3、優(yōu)解尋找平行線組的尋找平行線組的 最大（小）縱截距最大（?。┛v截距給定一定量的給定一定量的人力人力.物力物力,資金等資源資金等資源完成的任務(wù)量最大完成的任務(wù)量最大經(jīng)濟(jì)效益最高經(jīng)濟(jì)效益最高給定一項(xiàng)任務(wù)給定一項(xiàng)任務(wù)所耗的人力所耗的人力.物力資源最小物力資源最小降低成本降低成本獲取最大的利潤獲取最大的利潤精打細(xì)算精打細(xì)算最優(yōu)方案最優(yōu)方案統(tǒng)籌安排統(tǒng)籌安排最佳方案最佳方案實(shí)際應(yīng)用實(shí)際應(yīng)用例例1某工廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)某工廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)1t甲兩甲兩種產(chǎn)品需要種產(chǎn)品需要A種原料種原料4t、 B種原料種原料12t，產(chǎn)生的，產(chǎn)生的利潤為利潤為2萬元；生產(chǎn)乙種產(chǎn)品需要萬元；生產(chǎn)乙種產(chǎn)品需要A種原

4、料種原料1t、 B種原料種原料9t，產(chǎn)生的利潤為，產(chǎn)生的利潤為1萬元?，F(xiàn)有庫存萬元?，F(xiàn)有庫存A種原料種原料10t、 B種原料種原料60t，如何安排生產(chǎn)才能，如何安排生產(chǎn)才能使利潤最大？使利潤最大？分析：在關(guān)數(shù)據(jù)列表如下：分析：在關(guān)數(shù)據(jù)列表如下：A種原料 B種原料利潤甲種產(chǎn)品4 122 乙種產(chǎn)品1 9 1現(xiàn)有庫存10 60 設(shè)生產(chǎn)甲、乙兩種產(chǎn)品的噸數(shù)分別為設(shè)生產(chǎn)甲、乙兩種產(chǎn)品的噸數(shù)分別為x、y0060912104yxyxyxyxP 2利潤利潤何時(shí)達(dá)到最大？何時(shí)達(dá)到最大？xYo4x4xy=10y=1012x12x9y=609y=602x+y=02x+y=05(, 5 )45(, 0)21522xy

5、max152Z 例例2某工廠生產(chǎn)甲、乙兩種產(chǎn)品某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品已知生產(chǎn)甲種產(chǎn)品1t需消耗需消耗A種礦石種礦石10t、B種礦石種礦石5t、煤、煤4t；生產(chǎn)乙種產(chǎn)品；生產(chǎn)乙種產(chǎn)品1噸需消耗噸需消耗A種礦石種礦石4t、B種礦石種礦石4t、煤、煤9t.每每1t甲種產(chǎn)品甲種產(chǎn)品的利潤是的利潤是600元元,每每1t乙種產(chǎn)品的利潤是乙種產(chǎn)品的利潤是1000元元.工廠在工廠在生產(chǎn)這兩種產(chǎn)品的計(jì)劃中要求消耗生產(chǎn)這兩種產(chǎn)品的計(jì)劃中要求消耗A種礦石不超過種礦石不超過300t、 消耗消耗B種礦石不超過種礦石不超過200t、消耗煤不超過、消耗煤不超過360t.若你是若你是廠長廠長,你應(yīng)如何安排

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

7、不超過種礦石不超過200t、消耗煤不超過、消耗煤不超過360t.若你若你是廠長是廠長,你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到精確到0.1t),才能使利才能使利潤總額達(dá)到最大潤總額達(dá)到最大?分分析析問問題題:1.本問題給定了哪些原材料本問題給定了哪些原材料(資源資源)?2.該工廠生產(chǎn)哪些產(chǎn)品該工廠生產(chǎn)哪些產(chǎn)品?3.各種產(chǎn)品對原材料各種產(chǎn)品對原材料(資源資源)有怎樣的要求有怎樣的要求?4.該工廠對原材料該工廠對原材料(資源資源)有何限定條件有何限定條件?5.每種產(chǎn)品的利潤是多少每種產(chǎn)品的利潤是多少?利潤總額如何計(jì)算利潤總額如何計(jì)算? 原原 材材料料每噸產(chǎn)品消耗的原材料

8、每噸產(chǎn)品消耗的原材料A種礦石種礦石B種礦石種礦石煤煤甲產(chǎn)品甲產(chǎn)品(t)乙產(chǎn)品乙產(chǎn)品(t)1054449原原 材料限材料限 額額300200360利利 潤潤6001000 xtyt把題中限制條件進(jìn)行轉(zhuǎn)化：把題中限制條件進(jìn)行轉(zhuǎn)化：約束條件約束條件10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y. 目標(biāo)函數(shù)目標(biāo)函數(shù)：設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤總額為利潤總額為z元元解解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤總額為利潤總額為z元元,那么那么10 x+4y3005x+4y2004x+

9、9y360 x0y 0z=600 x+1000y.畫畫出以上不等式組所表示的可行域出以上不等式組所表示的可行域作作出直線出直線L 600 x+1000y=0.解得交點(diǎn)解得交點(diǎn)M的坐標(biāo)為的坐標(biāo)為(12.4,34.4)5x+4y=2004x+9y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M答答:應(yīng)生產(chǎn)甲產(chǎn)品約應(yīng)生產(chǎn)甲產(chǎn)品約12.4噸，乙產(chǎn)品噸，乙產(chǎn)品34.4噸，能使利潤總額達(dá)到最大。噸，能使利潤總額達(dá)到最大。(12.4,34.4)經(jīng)過可行域上的點(diǎn)經(jīng)過可行域上的點(diǎn)M時(shí)時(shí),目標(biāo)函數(shù)目標(biāo)函數(shù)在在y軸上截距最大軸上截距最大.9030 0 xy10 20

10、1075405040此時(shí)此時(shí)z=600 x+1000y取得最大值取得最大值.4834291000411229360.y.x例3.gsp圖形把直線把直線L向右上方平向右上方平移移實(shí)際問題實(shí)際問題線性規(guī)劃問題線性規(guī)劃問題尋找約束條件尋找約束條件建立目標(biāo)函數(shù)建立目標(biāo)函數(shù)列表列表設(shè)立變量設(shè)立變量轉(zhuǎn)化轉(zhuǎn)化1.約束條件要寫全約束條件要寫全; 3.解題格式要規(guī)范解題格式要規(guī)范. 2.作圖要準(zhǔn)確作圖要準(zhǔn)確,計(jì)算也要準(zhǔn)確計(jì)算也要準(zhǔn)確;注意注意: :結(jié)論結(jié)論1: 1:例例3.某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成A、B、C三種規(guī)三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊

11、數(shù)如下表所示格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 ： 解：解：設(shè)需截第一種鋼板設(shè)需截第一種鋼板x張，第二種鋼板張，第二種鋼板y張，張，鋼板鋼板總總張數(shù)為張數(shù)為Z,則則 規(guī)格類型規(guī)格類型鋼板類型鋼板類型第一種鋼板第一種鋼板第二種鋼板第二種鋼板A規(guī)格規(guī)格B規(guī)格規(guī)格C規(guī)格規(guī)格2121312x+y15,x+2y18,x+3y27,x0y0 某顧客需要某顧客需要A,B,C三種規(guī)格的成品分別為三種規(guī)格的成品分別為15，18，27塊，塊，若你是若你是經(jīng)理經(jīng)理,問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張數(shù)最少。數(shù)最少。x張張y張張

12、分分析析問問題題: :目標(biāo)函數(shù)目標(biāo)函數(shù): z=x+y) )N Ny y, ,x x( ( x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, y0直線直線x+y=12經(jīng)過的經(jīng)過的整點(diǎn)是整點(diǎn)是B(3,9)和和C(4,8)，它們是最優(yōu)解，它們是最優(yōu)解. 作出直線作出直線L:x+y=0，目標(biāo)函數(shù)目標(biāo)函數(shù):z= x+yB(3,9)C(4,8)A(3.6,7.8)當(dāng)直線當(dāng)直線L經(jīng)過點(diǎn)經(jīng)過點(diǎn)A時(shí)時(shí)z=x+y=11.4,x+y=12解得交點(diǎn)解得交點(diǎn)B,C的坐標(biāo)的坐標(biāo)B(3,9)和和C(4,8)2 4 6181282724681015但它不是最優(yōu)整數(shù)解

13、但它不是最優(yōu)整數(shù)解.作直線作直線x+y=12答（略）答（略）約束條件約束條件:畫可行域畫可行域平移平移L找交點(diǎn)及交點(diǎn)坐標(biāo)找交點(diǎn)及交點(diǎn)坐標(biāo)) )N Ny y, ,x x( ( 調(diào)整優(yōu)解法調(diào)整優(yōu)解法1.滿足哪些條件的解才是最優(yōu)解滿足哪些條件的解才是最優(yōu)解?2.目標(biāo)函數(shù)經(jīng)過目標(biāo)函數(shù)經(jīng)過A(3.6,7.8)時(shí)時(shí)Z的值是多少的值是多少?你能否猜測一下你能否猜測一下Z的最小值可能是多少的最小值可能是多少?3.最優(yōu)解的幾何意義是什么最優(yōu)解的幾何意義是什么 (最優(yōu)解可以轉(zhuǎn)化為什么幾何意義最優(yōu)解可以轉(zhuǎn)化為什么幾何意義)?圖例題4.gsp示x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,

14、x+2y18,x+3y27,x0, xN*y0 yN*經(jīng)過可行域內(nèi)的整點(diǎn)經(jīng)過可行域內(nèi)的整點(diǎn)B(3,9)和和C(4,8)且和原點(diǎn)距離最近的直線是且和原點(diǎn)距離最近的直線是x+y=12，它們是最優(yōu)解，它們是最優(yōu)解.作出一組平行直線作出一組平行直線t = x+y，目標(biāo)函數(shù)目標(biāo)函數(shù)t = x+yB(3,9)C(4,8)A(18/5,39/5)打網(wǎng)格線法打網(wǎng)格線法在可行域內(nèi)打出網(wǎng)格線，在可行域內(nèi)打出網(wǎng)格線，當(dāng)直線經(jīng)過點(diǎn)當(dāng)直線經(jīng)過點(diǎn)A時(shí)時(shí)t=x+y=11.4,但它不是最優(yōu)整數(shù)解，但它不是最優(yōu)整數(shù)解，將直線將直線x+y=11.4繼續(xù)向上平移，繼續(xù)向上平移，1212182715978 把把實(shí)際問題實(shí)際問題轉(zhuǎn)化成

15、轉(zhuǎn)化成線性規(guī)劃問題線性規(guī)劃問題即建立數(shù)學(xué)即建立數(shù)學(xué)模型的方法。大致可分為以下三個(gè)模型的方法。大致可分為以下三個(gè)步驟：步驟： （1）準(zhǔn)確建立數(shù)學(xué)模型，即根據(jù)題意找）準(zhǔn)確建立數(shù)學(xué)模型，即根據(jù)題意找出約束條件，確定線性目標(biāo)函數(shù)；出約束條件，確定線性目標(biāo)函數(shù)； （2）用圖解法求得數(shù)學(xué)模型的解，即畫）用圖解法求得數(shù)學(xué)模型的解，即畫出可行域，在可行域內(nèi)求得使目標(biāo)函數(shù)取得出可行域，在可行域內(nèi)求得使目標(biāo)函數(shù)取得最值的解；最值的解； （3）根據(jù)實(shí)際意義將數(shù)學(xué)模型的解轉(zhuǎn)化）根據(jù)實(shí)際意義將數(shù)學(xué)模型的解轉(zhuǎn)化為實(shí)際問題的解，即結(jié)合實(shí)際情況求得最優(yōu)為實(shí)際問題的解，即結(jié)合實(shí)際情況求得最優(yōu)解。解。 即先求非整數(shù)條件下的最優(yōu)解

16、，即先求非整數(shù)條件下的最優(yōu)解，調(diào)整調(diào)整Z的值使不定方程的值使不定方程Ax+By=Z存在最大（小）存在最大（?。┑恼c(diǎn)值，最后篩選出整點(diǎn)最優(yōu)解的整點(diǎn)值，最后篩選出整點(diǎn)最優(yōu)解 即先打網(wǎng)格，描出可行域內(nèi)的即先打網(wǎng)格，描出可行域內(nèi)的整點(diǎn)整點(diǎn)，平移直線，最先經(jīng)過或最后經(jīng)過的整點(diǎn)平移直線，最先經(jīng)過或最后經(jīng)過的整點(diǎn)坐標(biāo)即為最優(yōu)整解坐標(biāo)即為最優(yōu)整解線性規(guī)劃求最優(yōu)整數(shù)解的一般方法線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:1. 1.平移找解法：平移找解法： 2. 2.調(diào)整優(yōu)解法調(diào)整優(yōu)解法：結(jié)論結(jié)論2: 2:咖啡館配制兩種飲料甲種飲料每杯含奶粉咖啡館配制兩種飲料甲種飲料每杯含奶粉9g 、咖啡、咖啡4g、糖、糖3g,乙種飲料每

17、杯含奶粉乙種飲料每杯含奶粉4g 、咖啡、咖啡5g、糖、糖10g已知每天原料已知每天原料的使用限額為奶粉的使用限額為奶粉3600g ，咖啡，咖啡2000g糖糖3000g,如果甲種飲如果甲種飲料每杯能獲利料每杯能獲利0.7元，乙種飲料每杯能獲利元，乙種飲料每杯能獲利1.2元，每天在原料元，每天在原料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種飲料各多少的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種飲料各多少杯能獲利最大杯能獲利最大？解：將已知數(shù)據(jù)列為下表：解：將已知數(shù)據(jù)列為下表： 原原 料料每配制每配制1杯飲料消耗的原料杯飲料消耗的原料奶粉奶粉(g)咖啡咖啡(g)糖糖(g)甲種飲料甲種飲料乙種飲料乙種飲

18、料9434510原原 料限料限 額額360020003000利利 潤潤(元元)0.71.2xy003000103200054360049yxyxyxyx設(shè)每天應(yīng)配制甲種飲料設(shè)每天應(yīng)配制甲種飲料x杯，乙種飲料杯，乙種飲料y杯，則杯，則目標(biāo)函數(shù)為：目標(biāo)函數(shù)為：z =0.7x +1.2y鞏固練習(xí)一鞏固練習(xí)一解解: :設(shè)每天應(yīng)配制甲種飲料設(shè)每天應(yīng)配制甲種飲料x x杯，乙種飲料杯，乙種飲料y y杯，則杯，則003000103200054360049yxyxyxyx把直線把直線l l向右上方平移至向右上方平移至l l1 1的位置時(shí)，的位置時(shí)，直線經(jīng)過可行域上的點(diǎn)直線經(jīng)過可行域上的點(diǎn)C C，且與原點(diǎn)，且與原

19、點(diǎn)距距 離最大，離最大，此時(shí)此時(shí)z =0.7x +1.2yz =0.7x +1.2y取最大值取最大值解方程組解方程組 得點(diǎn)得點(diǎn)C C的坐標(biāo)為（的坐標(biāo)為（200200，240240）,3000103,200054yxyx_0_ 9 x + 4 y = 3600_ C (200,240)_ 4 x + 5 y = 2000_ 3 x + 10 y = 3000_ 7 x + 12 y = 0_ 400_ 400_ 300_ 500_ 1000_ 900_ 0_ x_ y目標(biāo)函數(shù)為：目標(biāo)函數(shù)為：z =0.7x +1.2y答答:每天配制甲種飲料每天配制甲種飲料200杯杯,乙種飲料乙種飲料240杯可獲取最大利潤