簡(jiǎn)單的線性規(guī)劃3

1、x y o 線性規(guī)劃的簡(jiǎn)單應(yīng)用線性規(guī)劃的簡(jiǎn)單應(yīng)用 使使z=2x+y取得取得最大值最大值的可行解為的可行解為 ， 且最大值為且最大值為 ； 復(fù)習(xí)引入復(fù)習(xí)引入 1.已知二元一次不等式組已知二元一次不等式組 x-y0 x+y-10 y-1 （1）畫出不等式組所表示的平面區(qū)域；）畫出不等式組所表示的平面區(qū)域； 滿足滿足 的的解解(x,y)都叫做都叫做可行解可行解； z=2x+y 叫做叫做 ； （2）設(shè)）設(shè)z=2x+y，則式中變量，則式中變量x,y滿足的二元一滿足的二元一 次不等式組叫做次不等式組叫做x,y的的 ； y=-1 x-y=0 x+y=1 2x+y=0 返回返回 (-1,-1) (2,-1)

2、使使z=2x+y取得取得最小值最小值的可行解的可行解 ， 且最小值為且最小值為 ； 這兩個(gè)這兩個(gè)最值最值都叫做問題的都叫做問題的 。 線性約束條件線性約束條件 線性目標(biāo)函數(shù)線性目標(biāo)函數(shù) 線性約束條件線性約束條件 (2,-1) (-1,-1) 3 -3 最優(yōu)解最優(yōu)解 x y 0 1 1 例題分析例題分析 例例1:某工廠生產(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)品的利潤(rùn)是甲種產(chǎn)品的利

3、潤(rùn)是600 元元,每每1t乙種產(chǎn)品的利潤(rùn)是乙種產(chǎn)品的利潤(rùn)是1000元元.工廠在生產(chǎn)這兩種產(chǎn)品的工廠在生產(chǎn)這兩種產(chǎn)品的 計(jì)劃中要求消耗計(jì)劃中要求消耗A種礦石不超過種礦石不超過300t、消耗、消耗B種礦石不超過種礦石不超過 200t、消耗煤不超過、消耗煤不超過360t.甲、乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少甲、乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少(精精 確到確到0.1t),能使利潤(rùn)總額達(dá)到最大能使利潤(rùn)總額達(dá)到最大? 甲產(chǎn)品甲產(chǎn)品 （1t） 乙產(chǎn)品乙產(chǎn)品 （1t） 資源限額資源限額 （t） A種礦石（種礦石（t） B種礦石（種礦石（t） 煤（煤（t） 利潤(rùn)（元）利潤(rùn)（元） 產(chǎn)品產(chǎn)品 消耗量消耗量 資源資源 列表列表： 5 1

4、0 4 600 4 4 9 1000 300 200 360 設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤(rùn)總額為利潤(rùn)總額為z元元 例題分析例題分析 甲產(chǎn)品甲產(chǎn)品 （1t） 乙產(chǎn)品乙產(chǎn)品 （1t） 資源限額資源限額 （t） A種礦石（種礦石（t） B種礦石（種礦石（t） 煤（煤（t） 利潤(rùn)（元）利潤(rùn)（元） 產(chǎn)品產(chǎn)品 消耗量消耗量 資源資源 列表列表： 5 10 4 600 4 4 9 1000 300 200 360 把題中限制條件進(jìn)行把題中限制條件進(jìn)行轉(zhuǎn)化：轉(zhuǎn)化： 約束條件約束條件 10 x+4y300 5x+4y200 4x+9y360 x0 y 0 z=600

5、x+1000y. 目標(biāo)函數(shù)：目標(biāo)函數(shù)： 設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤(rùn)總額為利潤(rùn)總額為z元元 xtyt 例題分析 解解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤(rùn)總額為利潤(rùn)總額為z=600 x+1000y. 元元, 那么那么 10 x+4y300 5x+4y200 4x+9y360 x0 y 0 z=600 x+1000y. 作出以上不等式組所表示的可行域作出以上不等式組所表示的可行域 作出一組平行直線作出一組平行直線 600 x+1000y=t， 解得交點(diǎn)解得交點(diǎn)M的坐標(biāo)為的坐標(biāo)為(12.4,34.4) 5x+4y=20

6、0 4x+9y=360 由由 10 x+4y=300 5x+4y=200 4x+9y=360 600 x+1000y=0 M 答答:應(yīng)生產(chǎn)甲產(chǎn)品約應(yīng)生產(chǎn)甲產(chǎn)品約12.4噸，乙產(chǎn)品噸，乙產(chǎn)品34.4噸，能使利潤(rùn)總額達(dá)到最大。噸，能使利潤(rùn)總額達(dá)到最大。 (12.4,34.4) 經(jīng)過可行域上的點(diǎn)經(jīng)過可行域上的點(diǎn)M時(shí)時(shí),目標(biāo)函數(shù)目標(biāo)函數(shù) 在在y軸上截距最大軸上截距最大. l l l 90 30 0 x y 10 20 10 75 40 50 40 此時(shí)此時(shí)z=600 x+1000y取得最大值取得最大值. 例題分析 例例2 要將兩種大小不同規(guī)格的鋼板截成要將兩種大小不同規(guī)格的鋼板截成A、B、C三種規(guī)格，

7、三種規(guī)格， 每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 ： 解：解：設(shè)需截第一種鋼板設(shè)需截第一種鋼板x張，第一種鋼板張，第一種鋼板y張，則張，則 規(guī)格類型規(guī)格類型 鋼板類型鋼板類型 第一種鋼板第一種鋼板 第二種鋼板第二種鋼板 A規(guī)格規(guī)格B規(guī)格規(guī)格C規(guī)格規(guī)格 2 12 1 3 1 2x+y15, x+2y18, x+3y27, x0 y0 作出可行域（如圖作出可行域（如圖） 目標(biāo)函數(shù)為目標(biāo)函數(shù)為 z=x+y 今需要今需要A,B,C三種規(guī)格的成品分別為三種規(guī)格的成品分別為15，18，27塊，問塊，問 各截這兩種鋼板多少?gòu)埧傻盟枞N規(guī)格成品

8、，且使所各截這兩種鋼板多少?gòu)埧傻盟枞N規(guī)格成品，且使所 用鋼板張數(shù)最少。用鋼板張數(shù)最少。 X張張 y張張 例題分析 x 0 y 2x+y=15 x+3y=27 x+2y=18 x+y =0 2x+y15, x+2y18, x+3y27, x0, xN y0 yN 直線直線x+y=12經(jīng)過的經(jīng)過的整點(diǎn)是整點(diǎn)是B(3,9)和和C(4,8)，它們是最優(yōu)解，它們是最優(yōu)解. 作出一組平行直線作出一組平行直線z=x+y， 目標(biāo)函數(shù)目標(biāo)函數(shù)z= x+y B(3,9) C(4,8) A(18/5,39/5) 當(dāng)直線經(jīng)過點(diǎn)當(dāng)直線經(jīng)過點(diǎn)A時(shí)時(shí)z=x+y=11.4, x+y=12 解得交點(diǎn)解得交點(diǎn)B,C的坐標(biāo)的坐

9、標(biāo)B(3,9)和和C(4,8) 調(diào)整優(yōu)值法調(diào)整優(yōu)值法 2 4 618128 27 2 4 6 8 10 15 但它不是最優(yōu)整數(shù)解但它不是最優(yōu)整數(shù)解.作直線作直線x+y=12 答（略）答（略） 例題分析 x 0 y 2x+y=15 x+3y=27x+2y=18 x+y =0 2x+y15, 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)時(shí)，時(shí)，t=x+y=12是最優(yōu)解是最優(yōu)解.答答:(略略) 作出一組平行直線作出一組平行直線t = x+y， 目標(biāo)函數(shù)目標(biāo)函數(shù)t = x+y B(3,9) C(4,8) A(18/5,3

10、9/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ù)向上平移， 12 1 2 1827 15 9 78 不等式組不等式組 表示的平面區(qū)域內(nèi)的表示的平面區(qū)域內(nèi)的整數(shù)點(diǎn)整數(shù)點(diǎn)共有共有 （ ）個(gè)）個(gè) 1234 0 0 yx y x 鞏固練習(xí)鞏固練習(xí)1: 1 2 3 4 x y 4 3 2 1 0 4x+3y=12 在可行域內(nèi)找出最優(yōu)解、線性規(guī)劃整數(shù)在可行域內(nèi)找出最優(yōu)解、線性規(guī)劃整數(shù) 解問題的一般方法是：解問題的一般方法是： 1.若區(qū)域若區(qū)域

11、“頂點(diǎn)頂點(diǎn)”處恰好為整點(diǎn)，那么它就是最優(yōu)解；處恰好為整點(diǎn)，那么它就是最優(yōu)解； （在包括邊界的情況下）（在包括邊界的情況下） 2.若區(qū)域若區(qū)域“頂點(diǎn)頂點(diǎn)”不是整點(diǎn)或不包括邊界時(shí)，應(yīng)先求出不是整點(diǎn)或不包括邊界時(shí)，應(yīng)先求出 該點(diǎn)坐標(biāo)，并計(jì)算目標(biāo)函數(shù)值該點(diǎn)坐標(biāo)，并計(jì)算目標(biāo)函數(shù)值Z，然后在可行域內(nèi)適當(dāng)，然后在可行域內(nèi)適當(dāng) 放縮目標(biāo)函數(shù)值，使它為整數(shù)，且與放縮目標(biāo)函數(shù)值，使它為整數(shù)，且與Z最接近，在這條最接近，在這條 對(duì)應(yīng)的直線中，取可行域內(nèi)整點(diǎn)，如果沒有整點(diǎn)，繼續(xù)對(duì)應(yīng)的直線中，取可行域內(nèi)整點(diǎn)，如果沒有整點(diǎn)，繼續(xù) 放縮，直至取到整點(diǎn)為止。放縮，直至取到整點(diǎn)為止。 3.在可行域內(nèi)找整數(shù)解，一般采用平移找解法

12、，即打網(wǎng)在可行域內(nèi)找整數(shù)解，一般采用平移找解法，即打網(wǎng) 絡(luò)、找整點(diǎn)、平移直線、找出整數(shù)最優(yōu)解絡(luò)、找整點(diǎn)、平移直線、找出整數(shù)最優(yōu)解 解線性規(guī)劃應(yīng)用問題的一般步驟解線性規(guī)劃應(yīng)用問題的一般步驟： 2）設(shè)好變?cè)⒘谐霾坏仁浇M和目標(biāo)函數(shù)）設(shè)好變?cè)⒘谐霾坏仁浇M和目標(biāo)函數(shù) 3）由二元一次不等式表示的平面區(qū)域做出可行域；由二元一次不等式表示的平面區(qū)域做出可行域； 4）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解 1）理清題意，列出表格：）理清題意，列出表格： 5)還原成實(shí)際問題還原成實(shí)際問題 ( (準(zhǔn)確作圖，準(zhǔn)確計(jì)算準(zhǔn)確作圖，準(zhǔn)確計(jì)算) 咖啡館配制兩種飲料甲種飲料每杯含奶粉咖啡館配制兩種飲料甲種

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

14、乙產(chǎn)品乙產(chǎn)品(1 杯杯) 資源限額（資源限額（g） 奶粉（奶粉（g g）9 94 436003600 咖啡咖啡(g)(g)4 45 520002000 糖糖(g)(g)3 3101030003000 利潤(rùn)（元）利潤(rùn)（元）0.70.71.21.2 產(chǎn)品產(chǎn)品 設(shè)每天應(yīng)配制甲種飲料設(shè)每天應(yīng)配制甲種飲料x x杯，乙種飲料杯，乙種飲料y y杯，則杯，則 0 0 3000103 200054 360049 y x yx yx yx 作出可行域：作出可行域： 目標(biāo)函數(shù)為：目標(biāo)函數(shù)為：z =0.7x +1.2yz =0.7x +1.2y 作直線作直線l:0.7x+1.2y=0l:0.7x+1.2y=0， 把直

15、線把直線l l向右上方平移至向右上方平移至l l1 1的位置的位置 時(shí)，時(shí)， 直線經(jīng)過可行域上的點(diǎn)直線經(jīng)過可行域上的點(diǎn)C C，且與原，且與原 點(diǎn)距離最大，點(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 ,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 _

16、500 _ 1000 _ 900 _ 0 _ x _ y 二元一次不等式二元一次不等式 表示平面區(qū)域表示平面區(qū)域 直線定界，直線定界， 特殊點(diǎn)定域特殊點(diǎn)定域 簡(jiǎn)單的線性規(guī)劃簡(jiǎn)單的線性規(guī)劃 約束條件約束條件 目標(biāo)函數(shù)目標(biāo)函數(shù) 可行解可行解 可行域可行域 最優(yōu)解最優(yōu)解 應(yīng)用應(yīng)用 求解方法：畫、求解方法：畫、 移、求、答移、求、答 練習(xí)鞏固 1.某家具廠有方木材某家具廠有方木材90m3，木工板，木工板600m3，準(zhǔn)備加工成，準(zhǔn)備加工成 書桌和書櫥出售，已知生產(chǎn)每張書桌需要方木料書桌和書櫥出售，已知生產(chǎn)每張書桌需要方木料0.1m3、 木工板木工板2m3；生產(chǎn)每個(gè)書櫥需要方木料；生產(chǎn)每個(gè)書櫥需要方木料0

17、.2m3，木工板，木工板 1m3，出售一張書桌可以獲利，出售一張書桌可以獲利80元，出售一張書櫥可以元，出售一張書櫥可以 獲利獲利120元；元； （1）怎樣安排生產(chǎn)可以獲利最大？）怎樣安排生產(chǎn)可以獲利最大？ （2）若只生產(chǎn)書桌可以獲利多少？）若只生產(chǎn)書桌可以獲利多少？ （3）若只生產(chǎn)書櫥可以獲利多少？）若只生產(chǎn)書櫥可以獲利多少？ 由上表可知： （1）只生產(chǎn)書桌，用完木工板了，可生產(chǎn)書桌 6002=300張, 可獲利潤(rùn):80300=24000元,但木料沒有用完 （2）只生產(chǎn)書櫥，用完方木料，可生產(chǎn)書櫥900.2=450 張,可 獲利潤(rùn)120450=54000元,但木工板沒有用完 產(chǎn)品 資源 書桌

18、（張） 書櫥（張） 資源限額 m 3 方木料 m 3 01 02 90 木工板 m 3 21600 利潤(rùn) （元） 80120 分析：分析： x y 0 2x+y-600=0 300 600 x+2y-900=0 A(100,400) 1.某家具廠有方木材某家具廠有方木材90m3，木工板，木工板600m3，準(zhǔn)備加工成書桌和書櫥出售，準(zhǔn)備加工成書桌和書櫥出售， 已知生產(chǎn)每張書桌需要方木料已知生產(chǎn)每張書桌需要方木料0.1m3、木工板、木工板2m3；生產(chǎn)每個(gè)書櫥需要方木；生產(chǎn)每個(gè)書櫥需要方木 料料0.2m3，木工板，木工板1m3，出售一張書桌可以獲利，出售一張書桌可以獲利80元，出售一張書櫥可以獲元，

19、出售一張書櫥可以獲 利利120元；元； （1）怎樣安排生產(chǎn)可以獲利最大？）怎樣安排生產(chǎn)可以獲利最大？ （2）若只生產(chǎn)書桌可以獲利多少？）若只生產(chǎn)書桌可以獲利多少？ （3）若只生產(chǎn)書櫥可以獲利多少？）若只生產(chǎn)書櫥可以獲利多少？ （1）設(shè)生產(chǎn)書桌）設(shè)生產(chǎn)書桌x張，書櫥張，書櫥y張，利張，利 潤(rùn)為潤(rùn)為z元，元， 則約束條件為則約束條件為 0.1x+0.2y900.1x+0.2y90 2x+y6002x+y600 x x，yNyN* * Z=80 x+120yZ=80 x+120y 作出不等式表示的平面區(qū)域，作出不等式表示的平面區(qū)域， 當(dāng)生產(chǎn)當(dāng)生產(chǎn)100張書桌，張書桌，400張書櫥時(shí)利潤(rùn)最大為張書櫥時(shí)

20、利潤(rùn)最大為 z=80100+120400=56000元元 （2）若只生產(chǎn)書桌可以生產(chǎn)）若只生產(chǎn)書桌可以生產(chǎn)300張，用完木工板，可獲利張，用完木工板，可獲利 24000元；元； （3）若只生產(chǎn)書櫥可以生產(chǎn)）若只生產(chǎn)書櫥可以生產(chǎn)450張，用完方木料，可獲利張，用完方木料，可獲利54000元。元。 將直線將直線z=80 x+120y平移可知：平移可知： 900 450 求解：求解： X y 08 4 x=8 y=4 7654321 3 2 1 x+y=104x+5y=30 320 x+504y=0 2.某運(yùn)輸公司接受了向抗洪搶險(xiǎn)地區(qū)每天至少運(yùn)送某運(yùn)輸公司接受了向抗洪搶險(xiǎn)地區(qū)每天至少運(yùn)送180噸支援物資噸支援物資 的任務(wù)，該公司有的任務(wù)，該公司有8輛載重量為輛載重量為6噸的噸的A型卡車和型卡車和4輛載重量為輛載重量為10噸噸 的的B型卡車，有型卡車，有10名駕駛員；每輛卡車每天往返的次數(shù)為名駕駛員；每輛卡車每天往返的次數(shù)為A型卡車型卡車 4