《《簡單的線性規(guī)劃》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《簡單的線性規(guī)劃》PPT課件（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、簡單的線性規(guī)劃 (第三課時 ) 5x+4y=20 2x+3y=12 線性目標(biāo)函數(shù) ),(M 720712 Z的最大值為 44 已知實數(shù) x,y滿足下列條件 : 5x+4y 20 2x+3y 12 x 0 y0 求 z=9x+10y的最大值 . 最優(yōu)解 可行域 9x+10y=0 想一想 : 線性約束 條件 0 1 2 3 4 5 6 1 2 3 4 5 6 x y 代數(shù)問題 (線性約束條件 ) 圖解法 轉(zhuǎn)化 線性約 束條件 可行域 轉(zhuǎn)化 線性目 標(biāo)函數(shù) Z=Ax+By 一組平行線 B Zxy 轉(zhuǎn)化 最優(yōu)解 圖解法的步驟： 1。 畫 可行域 ; 4。 求出最優(yōu)解作 答 . 3。 平 移 直線 L0

2、找最優(yōu)解 ; 2。 作 Z=0時的直線 L0. 三個轉(zhuǎn)化 一 .復(fù)習(xí) 平行線在 y軸上 的截距 最值 B Z 某工廠生產(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種 礦石不超過 200t、消耗煤不超過 360t.你應(yīng)如何安排甲乙 兩種產(chǎn)品的產(chǎn)量 (精確到 0.1t),才能使利潤總額達到最大 ? 二 .實際應(yīng)用 探索

3、問題一 : 某工廠生產(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種 礦石不超過 200t、消耗煤不超過 360t. 你應(yīng)如何安排甲乙 兩種產(chǎn)品的產(chǎn)量 (精確到 0.1t),才能使利潤總額達到最大 ? 分 析 問 題 : 2.本問題給定了哪些原材料？ 1.該工廠生產(chǎn)哪些產(chǎn)品 ? 3.每噸產(chǎn)品對原材料的消耗量各是多少 ?

4、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. 目標(biāo)函數(shù) ： 設(shè)生產(chǎn)甲、乙兩種產(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

5、 z=600 x+1000y. 畫 出以上不等式組所表示的可行域 作 出直線 L 600 x+1000y=0. 解得交點 M的坐標(biāo)為 (12.4,34.4) 5x+4y=200 4x+9y=360 由 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時 ,目標(biāo)函數(shù) 在 y軸上截距最大 . 90 30 0 x y 10 20 10 75 40 50 40 此時 z=600 x+1000y取得最大值 . 4834 29

6、1000 4112 29 360 .y .x 把直線 L向右上方平 移 實際問題 線性規(guī)劃問題 列 出約束條件 建 立目標(biāo)函數(shù) 分析問題 (列表 ) 設(shè) 立變量 轉(zhuǎn) 化 列約束條件時要注意到變量的范圍 . 注意 : 解 決 問題 最 優(yōu) 解 某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成 A、 B、 C三種規(guī)格 ， 每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 ： 規(guī)格類型 鋼板類型 第一種鋼板 第二種鋼板 A規(guī)格 B規(guī)格 C規(guī)格 2 1 2 1 3 1 某顧客需要 A,B,C三種規(guī)格的成品分別為 15， 18， 27塊， 若你是 生產(chǎn)部經(jīng)理 ,問各截這兩種鋼板多少張既能滿足顧客要求又使所 用鋼

7、板張數(shù)最少。 探索問題二 : 解： 設(shè)需截第一種鋼板 x張，第二種鋼板 y張， 鋼板 總 張數(shù) 為 Z,則 2x+y15, x+2y18, x+3y27, x0 y0 目標(biāo)函數(shù) : z=x+y )Ny,x( x 0 y 2x+y=15 x+3y=27 x+2y=18 x+y =0 2x+y15, x+2y18, x+3y27, x0, y0 在可行域內(nèi)直線 x+y=12經(jīng)過的 整點是 B(3,9)和 C(4,8)， 它 們是最優(yōu)解 . 作出直線 L:x+y=0， 目標(biāo)函數(shù) :z= x+y B(3,9) C(4,8) A(3.6,7.8) 當(dāng)直線 L經(jīng)過點 A時 z=x+y=11.4, x+y=

8、12 2 4 6 18 12 8 27 2 4 6 8 10 15 但它不是最優(yōu)整數(shù)解 . 作直線 x+y=12 答（略） 約束條件 : 畫可行域 平移 L找交點 及交點坐標(biāo) )Ny,x( 圖 例題 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)過的整點 坐標(biāo)即為最優(yōu)整解 線性規(guī)劃求最優(yōu)整數(shù)解的一般方法 : 1.平移找解法： 2.調(diào)整優(yōu)值法 ： 小結(jié) 咖啡館配制兩

9、種飲料甲種飲料每杯含奶粉 9g 、咖啡 4g、糖 3g,乙種飲料每杯含奶粉 4g 、 咖啡 5g、糖 10g已知每天原料的使用限額為 奶粉 3600g ，咖啡 2000g 糖 3000g,如果甲種飲 料每杯能獲利 0.7元，乙種飲料每杯能獲利 1.2 元每天在原料的使用限額內(nèi)飲料能全部售出， 每天應(yīng)配制兩種飲料各多少杯能獲利最大 ？ 練習(xí)一 .gsp - 鞏固練習(xí)一 解 :設(shè)每天應(yīng)配制甲種飲料 x杯 ， 乙種飲料 y杯 ， 則 0 0 30 00103 20 0054 36 0049 y x yx yx yx 作出可行域： 目標(biāo)函數(shù)為： z =0.7x +1.2y 作直線 l:0.7x+1.2

10、y=0， 把直線 l向右上方平移至 l1的位置時 ， 直線經(jīng)過可行域上的點 C， 且與原點 距離最大 ， 此時 z =0.7x +1.2y取最大值 解方程組 得點 C的坐標(biāo)為 （ 200， 240） ,3000103 ,200054 yx yx _ 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ù)為： z =0.7x +1.2y 答 :每天配制甲種飲

11、料 200杯 ,乙種飲料 240杯可獲取最大利潤 . 小結(jié) 小結(jié) : 實際問題 分析問題 設(shè)出變量 列出約束條件 建立目標(biāo)函數(shù) 轉(zhuǎn)化 建模 線性規(guī)劃 問題 圖解法 理論 最優(yōu)解 三 個 轉(zhuǎn) 化 四個步驟 調(diào) 整 實際 最優(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è) :習(xí)題 7.4 第 3題 ;第 4題 結(jié)束 某貨運公司擬用集裝箱托運甲 .乙兩種貨物 ,一個大集裝 箱所裝托運貨物的總體積不能超過 24 ,總重量不能 超過 1500kg,甲 .乙兩種貨物每袋的體積 .重量和可獲得 的利潤 ,列表如下 : 思考問題 二 3m 貨物 每袋體積 (立方米 ) 每袋重量 (100kg) 每袋利潤 (單位百元 ) 甲 5 2 20 乙 4 3 15 問在一個大集裝箱內(nèi)這兩種 (不能只裝一種 )貨物各裝多 少袋時 ,可獲得最大的利潤 ? 解 :設(shè)托運甲貨物 x袋 , 托運乙貨物 y袋 ,獲得利潤為 z(百元 ) 圖象 Z=20 x+15y (x,y ) N 5x+4y 24 2x+3y 15 X0 Y0