3.3.2簡單線性規(guī)劃(最終版)

1、2021/2/111 x y o 2021/2/112 復習復習: 1、直線的截距: 注意注意:截距不是距離截距不是距離,有正負有正負 y=x+1 y= -x+3 橫截距:直線與X軸交 點橫坐標 縱截距:直線與Y軸 交點縱坐標 2021/2/113 復習復習: 2、在同一坐標系上作出下列直線、在同一坐標系上作出下列直線: 2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7 .02 )0(2: 平平行行的的直直線線與與 形形如如結結論論 yx ttyx x Y o 觀察圖像觀察圖像:形如形如2x+y=t （t0）的直線有什么特）的直線有什么特 點點? 2021/2/114 復

2、習: : 二元一次不等式（組）表示平面區(qū) 域的方法: Ox y 1 1 x+y-1=0 x+y-10 x+y-10 （3 3）二元一次不等式組）二元一次不等式組 表示的平面區(qū)域是各個不表示的平面區(qū)域是各個不 等式表示的平面區(qū)域的交等式表示的平面區(qū)域的交 集集, ,即各個不等式表示的即各個不等式表示的 平面區(qū)域的公共部分。平面區(qū)域的公共部分。 （1 1）直線定界）直線定界: :Ax+By+C=0Ax+By+C=0 （注意實線和虛線的區(qū)別）（注意實線和虛線的區(qū)別）; ; （2 2）特殊點定域）特殊點定域: :一般的一般的, ,選選 取原點（取原點（0,00,0）。）。 2021/2/115 問題問

3、題1:某工廠用A,B兩種配件生產甲,乙兩種產品,每 生產一件甲種產品使用4個A配件耗時1h,每生產一件乙 種產品使用4個B配件耗時2h,該廠每天最多可從配件廠 獲得16個A配件和12個B配件,按每天工作8小時計算, 該廠所有可能的日生產安排是什么? 821所需時間所需時間 1240B種配件種配件 1604A種配件種配件 資源限額資源限額 乙產品乙產品 (1件件) 甲產品甲產品 (1件件) 產品產品 消消 耗耗 量量 資資 源源 分析分析:把問題把問題1的有關數據列表表示如下的有關數據列表表示如下: 設甲設甲, ,乙兩種產品分別生產乙兩種產品分別生產x,y件件, , 2021/2/116 28

4、416 412 0 0 xy x y x y 將上面不等式組表示成平面上的區(qū)域將上面不等式組表示成平面上的區(qū)域 設甲設甲, ,乙兩種產品分別生產乙兩種產品分別生產x,y件件, ,由己知條件可得由己知條件可得: y y 4 48 8 4 4 3 3 o o 區(qū)域內所有坐標為整數的點區(qū)域內所有坐標為整數的點P(x,y),安排生安排生 產任務產任務x,y都是有意義的都是有意義的. 2021/2/117 思考思考: 若生產若生產1件甲種產品獲利件甲種產品獲利2萬元萬元,生產生產1 件乙件乙 種產品獲利種產品獲利3萬元萬元,采用哪種生產安排利潤最大采用哪種生產安排利潤最大? 若設利潤為若設利潤為z,則則

5、z=2x+3y,這樣上述問題轉化為這樣上述問題轉化為: 當當x,y在滿足上述約束條件時在滿足上述約束條件時,z的最大值為多少的最大值為多少? 分析分析:設設甲甲, ,乙兩種產品分別生產乙兩種產品分別生產x,y件件, ,則則 利潤可以表示為利潤可以表示為: :2x+3y 2021/2/118 , 2 3 2 2z z2 2 把把z z= =2 2x x+ +3 3y y變變形形為為y y= =- -x x+ +, ,這這是是斜斜率率為為- - 3 33 33 3 z z 在在y y軸軸上上的的截截距距為為的的一一族族與與y y= =- -x x平平行行直直線線, , 3 3 z z 求求截截距距

6、的的最最值值, ,即即可可得得z z的的最最值值. . 3 3 z=2x+3y表示與表示與2x+3y=0平行的一組直線平行的一組直線 2021/2/119 28 416 412 0 0 xy x y x y 問題問題:求利潤求利潤z=2x+3y的最大值的最大值. 143224 max Z 轉化為轉化為求直線求直線 的截距的截距 的的 最大值最大值 2 33 z yx 3 z 0 x y 4 3 4 8 2 3 yx M（4,2） 1 4 2 yx 2021/2/1110 28 416 412 0 0 xy x y x y 象這樣關于象這樣關于x,yx,y一次不等一次不等 式組的約束條件稱為式組

7、的約束條件稱為 線性約束線性約束條件條件 Z=2x+3yZ=2x+3y稱為目標函數稱為目標函數,( ,(因這里因這里 目標函數為關于目標函數為關于x,yx,y的一次式的一次式, ,又又 稱為稱為線性目標函數線性目標函數 在線性約束下求線性目標函數的最值問題在線性約束下求線性目標函數的最值問題, ,統(tǒng)統(tǒng) 稱為稱為線性規(guī)劃線性規(guī)劃. . 2021/2/1111 滿足線性約束的解滿足線性約束的解(x,y)(x,y)叫做叫做可行解可行解, , 所有可行解組成的集合叫做所有可行解組成的集合叫做可行域可行域 使目標函數使目標函數取得最值取得最值的可行解叫做這個的可行解叫做這個 問題的問題的最優(yōu)解最優(yōu)解 變

8、式變式:若生產一件甲產品獲利若生產一件甲產品獲利1萬元萬元, 生產一件乙產品獲利生產一件乙產品獲利3萬元萬元,采用哪種采用哪種 生產安排利潤最大生產安排利潤最大? 2021/2/1112 28 416 412 0 0 xy x y x y 0 x y 4 3 4 8 1 33 z yx N N（2 2, ,3 3） 1 4 2 yx 變式變式:求利潤求利潤z=x+3y的最大值的最大值. max 23 311z 2021/2/1113 解線性規(guī)劃問題的步驟解線性規(guī)劃問題的步驟: : （2 2）移）移: :在線性目標函數所表示的一組平行線在線性目標函數所表示的一組平行線 中中, ,利用平移的方法找

9、出與可行域利用平移的方法找出與可行域 有公共點且縱截距最大或最小的直線有公共點且縱截距最大或最小的直線 （3 3）求）求: :通過解方程組求出最優(yōu)解通過解方程組求出最優(yōu)解; ; （4 4）答）答: :作出答案。作出答案。 （1 1）畫）畫: :畫出線性約束條件所表示的可行域畫出線性約束條件所表示的可行域; ; 2021/2/1114 練習練習解下列線性規(guī)劃問題解下列線性規(guī)劃問題: 1、求、求z=2x+y的最值，使式中的的最值，使式中的x、y滿足約束條件：滿足約束條件： 1 1 y yx xy 2021/2/1115 x O y A BC y= x x+y=1 y=-1 2x+y=0 1 1 y

10、 yx xy B:(-1,-1) C:(2,-1) Zmin=-3 Zmax=3 目標函數：目標函數： Z=2x+y 2021/2/1116 線性規(guī)劃線性規(guī)劃 問題問題: 設設z=2x+3y,式中變量滿足式中變量滿足 下列條件下列條件: 求求z的最大值與最小值。的最大值與最小值。 目標函數目標函數 （線性目標函數）（線性目標函數） 線性約線性約 束條件束條件 任何一個滿足 不等式組的 （x,yx,y） 可行解可行解 可行域可行域 所有的所有的 最優(yōu)解最優(yōu)解 線性規(guī)線性規(guī) 劃問題劃問題 28 416 412 0 0 xy x y x y 2021/2/1117 解決線性規(guī)劃問題的步驟解決線性規(guī)劃

11、問題的步驟: : 畫畫畫出線性約束條件所表示的可行域畫出線性約束條件所表示的可行域 答答做出答案做出答案 求求根據觀察的結論根據觀察的結論, ,先求交點的坐標先求交點的坐標, ,再求再求 出最優(yōu)解出最優(yōu)解 移移在目標函數所表示的一組平行線（與目標函在目標函數所表示的一組平行線（與目標函 數中數中z=0z=0平行）中平行）中, ,利用平移的方法找出與可行域有利用平移的方法找出與可行域有 公共點且縱截距最大或最小的直線公共點且縱截距最大或最小的直線 小結小結 2021/2/1118 小小 結結 本節(jié)主要學習了線性約束下如何求目本節(jié)主要學習了線性約束下如何求目 標函數的標函數的最值問題最值問題 正確

12、列出變量的不等關系式正確列出變量的不等關系式, ,準確準確作出作出 可行域可行域是解決目標函數最值的關健是解決目標函數最值的關健 線性目標函數的最值一般都是在可行域線性目標函數的最值一般都是在可行域 的的頂點或邊界頂點或邊界取得取得. . 把目標函數轉化為某一直線把目標函數轉化為某一直線, ,其斜率與其斜率與 可行域邊界所在直線可行域邊界所在直線斜率的大小關系斜率的大小關系一定要一定要 弄清楚弄清楚. . 2021/2/1119 體驗體驗: : 二、二、最優(yōu)解最優(yōu)解一般在可行域的一般在可行域的頂點頂點處取得處取得 三、在哪個頂點取得不僅與三、在哪個頂點取得不僅與B B的符號有關的符號有關, ,

13、 而且還與直線而且還與直線 Z=Ax+ByZ=Ax+By的的斜率斜率有關有關 一、一、先定先定可行域和平移方向可行域和平移方向, ,再找最優(yōu)解。再找最優(yōu)解。 2021/2/1120 32利潤利潤( (萬元萬元) ) 821所需時間所需時間 1240B種配件種配件 1604A種配件種配件 資源限額資源限額 乙產品乙產品 (1件件) 甲產品甲產品 (1件件) 產品產品 消消 耗耗 量量 資資 源源 把問題把問題1的有關數據列表表示如下的有關數據列表表示如下: 設甲設甲, ,乙兩種產品分別生產乙兩種產品分別生產x,y件件, , 2021/2/1121 0 x y 4 3 4 8 2021/2/112

14、2 y y 4 48 8 4 4 3 3 o o MM 2021/2/1123 0 x y 4 3 4 8 2 33 z yx M（4,2） 1 4 2 yx 2021/2/1124 y y 4 48 8 4 4 3 3 o o MM 2x+3y=0 2021/2/1125 x y o 簡單的線性規(guī)劃問題（二）簡單的線性規(guī)劃問題（二） 2021/2/1126 一一、復習概念、復習概念 y x 48 4 3 o 把求最大值或求最小值的的函數稱為目標函數把求最大值或求最小值的的函數稱為目標函數, ,因為它因為它 是關于變量是關于變量x x、y y的一次解析式的一次解析式, ,又稱線性目標函數。又稱

15、線性目標函數。 滿足線性約束的解滿足線性約束的解 （x x, ,y y）叫做可行解。）叫做可行解。 在線性約束條件下求線性目標函數的最大值或最小值在線性約束條件下求線性目標函數的最大值或最小值 問題問題, ,統(tǒng)稱為統(tǒng)稱為線性規(guī)劃問題線性規(guī)劃問題。 一組關于變量一組關于變量x x、y y的一次不等式的一次不等式, ,稱為稱為線性約束條件線性約束條件 由所有可行解組成由所有可行解組成 的集合叫做可行域。的集合叫做可行域。 使目標函數取得最大值或最小值的可行解叫做使目標函數取得最大值或最小值的可行解叫做 這個問題的最優(yōu)解。這個問題的最優(yōu)解。 可行域可行域 可行解可行解 最優(yōu)解最優(yōu)解 2021/2/1

16、127 二二. .回顧回顧解線性規(guī)劃問題的步驟解線性規(guī)劃問題的步驟 （2 2）移）移: :在線性目標函數所表示的一組平行線在線性目標函數所表示的一組平行線 中中, ,利用平移的方法找出與可行域有利用平移的方法找出與可行域有 公共點且縱截距最大或最小的直線公共點且縱截距最大或最小的直線 （3 3）求）求: :通過解方程組求出最優(yōu)解通過解方程組求出最優(yōu)解; ; （4 4）答）答: :作出答案。作出答案。 （1 1）畫）畫: :畫出線性約束條件所表示的可行域畫出線性約束條件所表示的可行域; ; 2021/2/1128 練習練習解下列線性規(guī)劃問題解下列線性規(guī)劃問題: 1、求、求z=2x+y的最大值，使

17、式中的的最大值，使式中的x、y滿足約束條件：滿足約束條件： 1 1 y yx xy 2021/2/1129 x O y A BC y= x x+y=1 y=-1 2x+y=0 1 1 y yx xy B:(-1,-1) C:(2,-1) Zmin=-3 Zmax=3 目標函數：目標函數： Z=2x+y 2021/2/1130 例例2 2、一個化肥廠生產甲、乙兩種混合肥料一個化肥廠生產甲、乙兩種混合肥料, ,生產生產1 1車皮車皮 甲種肥料的主要原料是磷酸鹽甲種肥料的主要原料是磷酸鹽4t4t、硝酸鹽、硝酸鹽18t18t; ;生產生產1 1車車 皮乙種肥料需要的主要原料是磷酸鹽皮乙種肥料需要的主要

18、原料是磷酸鹽1t1t、硝酸鹽、硝酸鹽15t15t。 現庫存磷酸鹽現庫存磷酸鹽10t10t、硝酸鹽、硝酸鹽66t66t, ,在此基礎上生產這兩種在此基礎上生產這兩種 混合肥料。列出滿足生產條件的數學關系式混合肥料。列出滿足生產條件的數學關系式, ,并畫出相并畫出相 應的平面區(qū)域。并計算生產甲、乙兩種肥料各多少車應的平面區(qū)域。并計算生產甲、乙兩種肥料各多少車 皮，能夠產生最大的利潤皮，能夠產生最大的利潤? ? 解解: :設設x x、y y分別為計劃生產甲、乙兩種混合分別為計劃生產甲、乙兩種混合 肥料的車皮數肥料的車皮數, ,于是滿足以下條件于是滿足以下條件: : x y o 4 4 x x y y

19、 1 1 0 0 1 1 8 8 x x 1 1 5 5 y y 6 6 6 6 x x 0 0 y y 0 0 2021/2/1131 解解: :設生產甲種肥料設生產甲種肥料x x車皮、乙種肥料車皮、乙種肥料y y車皮車皮, , 能夠產生利潤能夠產生利潤Z Z萬元。目標函數為萬元。目標函數為Z Zx x0.5y0.5y, , 可行域如圖可行域如圖: : 把把Z Zx x0.5y0.5y變形變形為為y y2x2x2z2z, ,它表示斜率它表示斜率 為為2 2, ,在在y y軸上的截距為軸上的截距為2z2z的一組直線系。的一組直線系。 x y o 由圖可以看出由圖可以看出, ,當直線經過當直線經

20、過可行域上的點可行域上的點MM時時, , 截距截距2z2z最大最大, ,即即z z最大。最大。 答答: :生產甲種、乙種肥料各生產甲種、乙種肥料各 2 2車皮車皮, ,能夠產生最大利能夠產生最大利 潤潤, ,最大利潤為最大利潤為3 3萬元。萬元。 M 容易求得容易求得MM點的坐標為點的坐標為 （2 2, ,2 2）, ,則則Z Zmax max 3 3 2021/2/1132 3 3、制定投資計劃時、制定投資計劃時, ,不僅要考慮可能獲得的不僅要考慮可能獲得的 盈利盈利, ,而且要考慮可能出現的虧損而且要考慮可能出現的虧損. . 某投資人打算投資甲、乙兩個項目某投資人打算投資甲、乙兩個項目.

21、. 根據根據 預測預測, ,甲、乙項目可能的最大盈利率分別為甲、乙項目可能的最大盈利率分別為 100100和和5050，可能的最大虧損率分別為，可能的最大虧損率分別為3030 和和1010. . 投資人計劃投資金額不超過投資人計劃投資金額不超過1010萬萬 元，要求確保可能的資金虧損不超過元，要求確?？赡艿馁Y金虧損不超過1.81.8萬萬 元元. . 問投資人對甲、乙兩個項目各投資多少問投資人對甲、乙兩個項目各投資多少 萬元，才能使可能的盈利最大萬元，才能使可能的盈利最大? ? 【解題回顧解題回顧】要能從實際問題中要能從實際問題中, ,建構有關線建構有關線 性規(guī)劃問題的數學模型性規(guī)劃問題的數學模

22、型. .關鍵求出關鍵求出 約束條件和目標函數約束條件和目標函數. . 2021/2/1133 解解: :設投資方對甲、乙兩個項目各投資設投資方對甲、乙兩個項目各投資x x、y y萬元萬元 依題意線性約束條件為：依題意線性約束條件為： 0 0 183 10 y x yx yx 目標函數為：目標函數為： yxZ5 . 0 作出可行域作出可行域 可知直線可知直線Z=x+0.5yZ=x+0.5y通過點通過點A A時利潤最大時利潤最大 由由 6 4 183 10 y x yx yx 6,4A 75 . 064 max Z（萬元）（萬元） 答答: : 2021/2/1134 練習題 1、某廠擬生產甲、乙兩

23、種適銷產品某廠擬生產甲、乙兩種適銷產品, ,每件銷售收入分別每件銷售收入分別 為為30003000元、元、20002000元元, ,甲、乙產品都需要在甲、乙產品都需要在A A、B B兩種設兩種設 備上加工備上加工, ,在每臺在每臺A A、B B上加工上加工1 1件甲所需工時分別為件甲所需工時分別為1h1h、 2h2h，加工，加工1 1件乙所需工時分別為件乙所需工時分別為2h,1h.A2h,1h.A、B B兩種設備兩種設備 每月有效使用臺時數分別為每月有效使用臺時數分別為400h400h和和500h500h。如何安排生。如何安排生 產可使收入最大產可使收入最大? ? 解解: : 設每月生產甲產品

24、設每月生產甲產品x x件件, ,生產乙產品生產乙產品y y件件, ,每月收入為每月收入為Z Z 千元千元, ,目標函數為目標函數為Z Z3x3x2y2y，滿足的條件是，滿足的條件是 x x 2 2 y y 4 4 0 0 0 0 2 2 x x y y 5 5 0 0 0 0 x x 0 0 y y 0 0 2021/2/1135 Z Z 3x3x2y2y 變形為變形為 它表示斜率為它表示斜率為 的直線系的直線系, ,Z Z與這條直線的截距有關。與這條直線的截距有關。 22 3z xy 2 3 X Y O 400 200 250 50 0 當直線經過點當直線經過點MM時時, ,截距最大截距最大

25、, ,Z Z最大。最大。 M 解方程組解方程組 5002 4002 yx yx 可得可得MM（200200, ,100100） Z Z 的最大值的最大值Zmax Zmax 3x3x2y2y800800（千元）（千元） 故生產甲產品故生產甲產品200200件件, , 乙產品乙產品100100件件, ,收入最大收入最大, , 為為8080萬元。萬元。 2021/2/1136 小 結: 二元一次不等式二元一次不等式 表示平面區(qū)域表示平面區(qū)域 直線定界直線定界, 特殊點定域特殊點定域 簡單的線性規(guī)劃簡單的線性規(guī)劃 約束條件約束條件 目標函數目標函數 可行解可行解 可行域可行域 最優(yōu)解最優(yōu)解 應用應用

26、求解方法求解方法: :畫、畫、 移、求、答移、求、答 2021/2/1137 作作 業(yè)業(yè): 課本課本 P106 4 2021/2/1138 x y o 簡單的線性規(guī)劃問題（三）簡單的線性規(guī)劃問題（三） 2021/2/1139 復習回顧: 二元一次不等式二元一次不等式 表示平面區(qū)域表示平面區(qū)域 直線定界直線定界, 特殊點定域特殊點定域 簡單的線性規(guī)劃簡單的線性規(guī)劃 約束條件約束條件 目標函數目標函數 可行解可行解 可行域可行域 最優(yōu)解最優(yōu)解 應用應用 求解方法求解方法: :畫、畫、 移、求、答移、求、答 2021/2/1140 例、例、要將兩種大小不同規(guī)格的鋼板截成要將兩種大小不同規(guī)格的鋼板截成

27、A A、 B B、C C三種規(guī)格三種規(guī)格, ,每張鋼板可同時截得三種規(guī)每張鋼板可同時截得三種規(guī) 格的小鋼板的塊數如下表所示格的小鋼板的塊數如下表所示 : : 規(guī)格類型規(guī)格類型 鋼板類型鋼板類型 第一種鋼板第一種鋼板 第二種鋼板第二種鋼板 A A規(guī)格規(guī)格B B規(guī)格規(guī)格C C規(guī)格規(guī)格 2 2 1 12 2 1 1 3 3 1 1 今需要今需要A,B,CA,B,C三種規(guī)格的成品分別為三種規(guī)格的成品分別為 1515, ,1818, ,2727塊塊, ,問各截這兩種鋼板多少張可得問各截這兩種鋼板多少張可得 所需三種規(guī)格成品，且使所用鋼板張數最少。所需三種規(guī)格成品，且使所用鋼板張數最少。 解解: :設需截

28、第一種鋼板設需截第一種鋼板x x張、第二種鋼板張、第二種鋼板y y張張, ,可得可得 2021/2/1141 x 0 y 2x+y=15x+3y=2 7 x+2y=18 x+y =0 2x+y15, x+2y18, x+3y27, x0, xN* y0 yN* 經過可行域內的整點經過可行域內的整點B(3,9)和和C(4,8)且和原點距且和原點距 離最近的直線是離最近的直線是x+y=12,它們是最優(yōu)解它們是最優(yōu)解.答答:(略略) 作出一組平行直線作出一組平行直線z= x+y, 目標函數目標函數 z=x+yz=x+y B(3,9) C(4,8) A(18/5,39/5) 打網格線法打網格線法 在可行域內打出網格線在可行域內打出網格線, 當直線經過點當直線經過點A A時時z=x+y=11.4z=x+y=11.4, ,但它不是最優(yōu)整數解但它不是最優(yōu)整數解, , 將直線將直線x+y=11.4繼續(xù)向上平移繼續(xù)向上平移,