簡(jiǎn)單的線性規(guī)劃問題zst教程課件

3.3.3簡(jiǎn)單的線性規(guī)劃問題—實(shí)際應(yīng)用二、Ax+By+C>0(A2+B2≠0)直線定界，特殊點(diǎn)定域一、直線y=kx+b把平面分成兩個(gè)區(qū)域y>kx+b表示直線上方的平面區(qū)域；

y<kx+b表示直線下方的平面區(qū)域.畫出不等式組OXYx+y=0表示的平面區(qū)域。x-y+5=0x=3注：不等式組表示的平面區(qū)域是各不等式所表示平面區(qū)域的公共部分。例1某工廠生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)1t甲兩種產(chǎn)品需要A種原料4t、B種原料12t，產(chǎn)生的利潤(rùn)為2萬元；生產(chǎn)乙種產(chǎn)品需要A種原料1t、B種原料9t，產(chǎn)生的利潤(rùn)為1萬元。現(xiàn)有庫(kù)存A種原料10t、B種原料60t，如何安排生產(chǎn)才能使利潤(rùn)最大？分析：在關(guān)數(shù)據(jù)列表如下：A種原料B種原料利潤(rùn)甲種產(chǎn)品4122乙種產(chǎn)品191現(xiàn)有庫(kù)存1060設(shè)生產(chǎn)甲種產(chǎn)品x噸，乙種產(chǎn)品y噸。設(shè)生產(chǎn)甲、乙兩種產(chǎn)品的噸數(shù)分別為x、y利潤(rùn)何時(shí)達(dá)到最大？Yo4x＋y=10x12x＋9y=602x+y=0轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化四個(gè)步驟：1。畫（畫可行域）2。作（作z=Ax+By=0時(shí)的直線L

。）3。移（平移直線L。尋找使縱截距取得最值時(shí)的點(diǎn)）4。答（求出點(diǎn)的坐標(biāo)，并轉(zhuǎn)化為最優(yōu)解）圖解法想一想(結(jié)論):三個(gè)轉(zhuǎn)化線性約束條件可行域線性目標(biāo)函數(shù)Z=Ax+By一組平行線最優(yōu)解尋找平行線組的最大（小）縱截距例2.某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入分別為3000元、2000元，甲、乙產(chǎn)品都需要在A、B兩種設(shè)備上加工，在每臺(tái)A、B上加工1件甲所需工時(shí)分別為

1h、2h，A、B兩種設(shè)備每月有效使用臺(tái)數(shù)分別為400h和500h。如何安排生產(chǎn)可使收入最大？解：設(shè)每月生產(chǎn)甲產(chǎn)品x件，生產(chǎn)乙產(chǎn)品y件，每月收入為z，目標(biāo)函數(shù)為Z＝3x＋2y，滿足的條件是Z＝

3x＋2y

變形為XYO400200250500它表示斜率為 的直線系，Z與這條直線的截距有關(guān)。當(dāng)直線經(jīng)過點(diǎn)M時(shí)，截距最大，Z最大。M解方程組可得M（200，100）Z的最大值Z＝3x＋2y＝800故生產(chǎn)甲產(chǎn)品200件，乙產(chǎn)品100件，收入

最大，為80萬元。給定一定量的人力.物力,資金等資源完成的任務(wù)量最大經(jīng)濟(jì)效益最高給定一項(xiàng)任務(wù)所耗的人力.物力資源最小降低成本獲取最大的利潤(rùn)精打細(xì)算最優(yōu)方案統(tǒng)籌安排最佳方案實(shí)際應(yīng)用三、練習(xí)題：1、求z＝2x＋y的最大值，使x、y滿足約束條件：2、求z＝3x＋5y的最大值，使x、y滿足約束條件：1.解：作出平面區(qū)域xyABCoz＝2x＋y作出直線y=－2x＋z的圖像，可知z要求最大值，即直線經(jīng)過C點(diǎn)時(shí)。求得C點(diǎn)坐標(biāo)為（2，－1），則Zmax=2x＋y＝32.解：作出平面區(qū)域xoyABCz＝3x＋5y作出直線3x＋5y

＝z

的圖像，可知直線經(jīng)過A點(diǎn)時(shí)，

Z取最大值；直線經(jīng)過B點(diǎn)時(shí)，Z取最小值。求得A（1.5，2.5），B（－2，－1），則Zmax=17，Zmin=－11。課堂練習(xí)課本P80,練習(xí)1——4轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化四個(gè)步驟：1。畫（畫可行域）2。作（作z=Ax+By=0時(shí)的直線L

。）3。移（平移直線L。尋找使縱截距取得最值時(shí)的點(diǎn)）4。答（求出點(diǎn)的坐標(biāo)，并轉(zhuǎn)化為最優(yōu)解）圖解法小結(jié):三個(gè)轉(zhuǎn)化線性約束條件可行域線性目標(biāo)函數(shù)Z=Ax+By一組平行線最優(yōu)解尋找平行線組的最大（小）縱截距課后作業(yè)雙測(cè)P53,P54例2某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品1t需消耗A種礦石10t、B種礦石5t、煤4t；生產(chǎn)乙種產(chǎn)品1噸需消耗A種礦石4t、B種礦石4t、煤9t.每1t甲種產(chǎn)品的利潤(rùn)是600元,每1t乙種產(chǎn)品的利潤(rùn)是1000元.工廠在生產(chǎn)這兩種產(chǎn)品的計(jì)劃中要求消耗A種礦石不超過300t、消耗B種礦石不超過200t、消耗煤不超過360t.若你是

廠長(zhǎng),你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到0.1t),才能使利潤(rùn)總額達(dá)到最大?過300t、消耗B種礦石不超過200t、消耗煤不超過360t.若你是廠長(zhǎng),你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到0.1t),才能使利潤(rùn)總額達(dá)到最大?分析問題:1.本問題給定了哪些原材料(資源)?2.該工廠生產(chǎn)哪些產(chǎn)品3.各種產(chǎn)品對(duì)原材?料(資源)有怎樣的要求?4.該工廠對(duì)原材料(資源)有何限定條件5.每種?產(chǎn)品的利潤(rùn)是多少?利潤(rùn)總額如何計(jì)算?原材料每噸產(chǎn)品消耗的原材料種礦石種礦石煤甲產(chǎn)品乙產(chǎn)品原材料限額利潤(rùn)xtyt目標(biāo)函數(shù)：某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品1t需消耗A種礦石10t、B設(shè)種生礦產(chǎn)石甲5、t、乙煤兩種4t產(chǎn)；品生分產(chǎn)別乙為種產(chǎn)、品利1噸潤(rùn)總需額消為耗元A種礦石4t、B種礦把石題4t中、限煤制9條t.件每進(jìn)1t行甲轉(zhuǎn)種化產(chǎn)：品的利潤(rùn)約是束條60件0元,每1t乙種產(chǎn)品的利潤(rùn)是1000元.工廠在生產(chǎn)這兩種產(chǎn)品的計(jì)劃中要求消耗A種礦石不超5x+4y=2004x+9y=360{由10x+4y=3004x+9y=360600x+1000y=0M

(12.4,34.4)90300xt、yt,利潤(rùn)總額為z元,那么

y10

20107540

5x+4y=2005040解得交點(diǎn)M的坐標(biāo)為(12.4,34.4)例3.gsp圖形答:應(yīng)生產(chǎn)甲產(chǎn)品約12.4噸，乙產(chǎn)品34.4噸，能使利潤(rùn)總額達(dá)到最大。解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為x10x+4y≤3005x+4y≤2004x+9y≤360x≥0y≥0z=600x+1000y.畫出以上不等式組所表示的可行域作出直線L600x+1000y=0.把直線L向右上方平移經(jīng)過可行域上的點(diǎn)M時(shí),目標(biāo)函數(shù)在y軸上截距最大.此時(shí)z=600x+1000y取得最大值.實(shí)際問題尋找約束條件建立目標(biāo)函數(shù)列表設(shè)立變量線性規(guī)劃問題注意:約束條件要寫全;作圖要準(zhǔn)確,計(jì)算也要準(zhǔn)確;解題格式要規(guī)范.轉(zhuǎn)化結(jié)論1:例3.某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成A、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：鋼板總張數(shù)為Z,則數(shù)最少。解：設(shè)需截第一種鋼板x張，第二種鋼板y張，規(guī)格類型鋼板類型A規(guī)格B規(guī)格C規(guī)格第一種鋼板x張211第二種鋼板y張1232x+y≥15,x+2y≥18,x+3y≥27,x≥0y≥0某顧客需要A,B,C三種規(guī)格的成品分別為15，18，27塊，若你是經(jīng)理,問各截這兩種鋼板多少?gòu)埣饶軡M足顧客要求又使所用鋼板張分析問題:目標(biāo)函數(shù):z=x+yxy{x+2y≥18,x+3y≥27,x≥0,y≥0目標(biāo)函數(shù):z=x+yC(4,8)A(3.6,7.8)B(3,9)和C(4,8)2

4

6

8

12

182x+y=15

x+y=12

x+2y=1827x+3y=27作出直線L:x+y=0，2046810

B(3,9)15約束條件:2x+y≥15,畫可行域x+y

=0平移L找交點(diǎn)及交點(diǎn)坐標(biāo)調(diào)整優(yōu)解法當(dāng)直線L經(jīng)過點(diǎn)A時(shí)z=x+y=11.4,但它1不.滿是最足優(yōu)哪整些數(shù)條解件.的作解直才線x是+y最=1優(yōu)2

解?解得交點(diǎn)B,C的坐標(biāo)

2.目標(biāo)函數(shù)經(jīng)過A(3.6,7.8)時(shí)Z的值是多少?直線x+y=12經(jīng)過的整點(diǎn)你是B能(3否,9)猜和C測(cè)(4一,8)下，它Z的們是最最小優(yōu)值解可.

能是答多（少略?）3.最優(yōu)解的幾何意義是什么(最優(yōu)解可以轉(zhuǎn)化為什么幾何意義)?圖例題4.gsp示xy2x+y=15x+2y=18

x+3y=27x+y

=0{2x+y≥15,x+2y≥18,x+3y≥27,x≥0,

x∈N*y≥0

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

1

21218271597

8把實(shí)際問題轉(zhuǎn)化成線性規(guī)劃問題即建立數(shù)學(xué)模型的方法。大致可分為以下三個(gè)步驟：

（1）準(zhǔn)確建立數(shù)學(xué)模型，即根據(jù)題意找出約束條件，確定線性目標(biāo)函數(shù)；

（2）用圖解法求得數(shù)學(xué)模型的解，即畫出可行域，在可行域內(nèi)求得使目標(biāo)函數(shù)取得最值的解；

（3）根據(jù)實(shí)際意義將數(shù)學(xué)模型的解轉(zhuǎn)化為實(shí)際問題的解，即結(jié)合實(shí)際情況求得最優(yōu)解。線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:平移找解法：即先打網(wǎng)格，描出可行域內(nèi)的整點(diǎn)，平移直線，最先經(jīng)過或最后經(jīng)過的整點(diǎn)坐標(biāo)即為最優(yōu)整解．調(diào)整優(yōu)解法即：先求非整數(shù)條件下的最優(yōu)解，調(diào)整Z的值使不定方程Ax+By=Z存在最大（小）的整點(diǎn)值，最后篩選出整點(diǎn)最優(yōu)解．結(jié)論2:小結(jié):實(shí)際問題列表設(shè)出變量尋找約束條件建立目標(biāo)函數(shù)轉(zhuǎn)化建模線性規(guī)劃問題圖解法最優(yōu)解三個(gè)轉(zhuǎn)化四個(gè)步驟作答調(diào)整最優(yōu)整數(shù)解平移找解法常用方法調(diào)整優(yōu)值法目標(biāo)函數(shù)距離,斜率等5x+4y=202x+3y=12線性目標(biāo)函數(shù)Z的最大值為44y≥0求z=9x+10y的最大值.最優(yōu)解可行域．0．

．．

．．

．

．1

2

3

4