簡單線性規(guī)劃3

1、xyo可行域上的最優(yōu)解可行域上的最優(yōu)解問題問題1: 某工廠用某工廠用A,B兩種配件生產(chǎn)甲兩種配件生產(chǎn)甲, ,乙兩種產(chǎn)品乙兩種產(chǎn)品, ,每生產(chǎn)一件甲種產(chǎn)品使用每生產(chǎn)一件甲種產(chǎn)品使用4個個A配件耗時配件耗時1h,每生產(chǎn)一件乙種產(chǎn)品使用每生產(chǎn)一件乙種產(chǎn)品使用4個個B配件耗時配件耗時2h,該廠每天最多可從配件廠獲得該廠每天最多可從配件廠獲得16個個A配件和配件和12個個B配件配件, ,按每天工作按每天工作8小時小時計算計算, ,該廠所有該廠所有可能的日生產(chǎn)安排是什么可能的日生產(chǎn)安排是什么? 若生產(chǎn)若生產(chǎn)1件甲種產(chǎn)品獲利件甲種產(chǎn)品獲利2萬元萬元,生產(chǎn)生產(chǎn)1 件乙件乙種產(chǎn)品獲利種產(chǎn)品獲利3萬元萬元,采用哪

2、種生產(chǎn)安排利潤最大采用哪種生產(chǎn)安排利潤最大?32利潤利潤( (萬元萬元) )821所需時間所需時間1240B種配件種配件1604A種配件種配件資源限額資源限額 乙產(chǎn)品乙產(chǎn)品 (1件件)甲產(chǎn)品甲產(chǎn)品 (1件件)產(chǎn)品產(chǎn)品消消 耗耗 量量資資 源源把問題把問題1的有關(guān)數(shù)據(jù)列表表示如下的有關(guān)數(shù)據(jù)列表表示如下:設(shè)甲設(shè)甲, ,乙兩種產(chǎn)品分別生產(chǎn)乙兩種產(chǎn)品分別生產(chǎn)x,y件件, ,2841641200 xyxyxy 0 xy4348將上面不等式組表示成平面上的區(qū)域?qū)⑸厦娌坏仁浇M表示成平面上的區(qū)域, ,區(qū)域內(nèi)區(qū)域內(nèi)所有坐標(biāo)為整數(shù)的點所有坐標(biāo)為整數(shù)的點P(x,y),安排生產(chǎn)任務(wù)安排生產(chǎn)任務(wù)x,y都是有意義的都是有

3、意義的.設(shè)甲設(shè)甲, ,乙兩種產(chǎn)品分別生產(chǎn)乙兩種產(chǎn)品分別生產(chǎn)x,y件件, ,由己知條件可得由己知條件可得:問題：問題：求利潤求利潤2x+3y的最大值的最大值.若設(shè)利潤為若設(shè)利潤為z,則則z=2x+3y,這樣上述問題轉(zhuǎn)化為這樣上述問題轉(zhuǎn)化為:當(dāng)當(dāng)x,y在滿足上述約束條件時在滿足上述約束條件時,z的最大值為多少的最大值為多少?,2z22z2把把z=2x+3yz=2x+3y變變形形為為y=-x+,y=-x+,這這是是斜斜率率為為- -333333z z在在y y軸軸上上的的截截距距為為的的直直線線, ,3 3當(dāng)點當(dāng)點P在可允許的取值范圍變化時在可允許的取值范圍變化時,z z求求截截距距的的最最值值,

4、,即即可可得得z z的的最最值值. .3 32841641200 xyxyxy 0 xy4348233zyx M（4，2）142yx 問題：問題：求利潤求利潤z=2x+3y的最大值的最大值.143224max Z2841641200 xyxyxy 象這樣關(guān)于象這樣關(guān)于x,yx,y一次不等一次不等式組的約束條件稱為式組的約束條件稱為線性約束線性約束條件條件Z=2x+3yZ=2x+3y稱為目標(biāo)函數(shù)稱為目標(biāo)函數(shù), ,因這里因這里目標(biāo)函數(shù)為關(guān)于目標(biāo)函數(shù)為關(guān)于x,yx,y的一次式的一次式, ,又又稱為稱為線性目標(biāo)函數(shù)線性目標(biāo)函數(shù) 在線性約束下求線性目標(biāo)函數(shù)在線性約束下求線性目標(biāo)函數(shù)的最值問題的最值問題,

5、 ,統(tǒng)稱為統(tǒng)稱為線性規(guī)劃問題線性規(guī)劃問題滿足線性約束的解滿足線性約束的解( (x,yx,y) )叫做叫做可行解可行解, ,所有可行解組成的集合叫做所有可行解組成的集合叫做可行域可行域使目標(biāo)函數(shù)使目標(biāo)函數(shù)取得最值取得最值的可行解叫做這個的可行解叫做這個問題的問題的最優(yōu)解最優(yōu)解變式：變式：若生產(chǎn)一件甲產(chǎn)品獲利若生產(chǎn)一件甲產(chǎn)品獲利1萬元萬元，生產(chǎn)一件乙產(chǎn)品獲利生產(chǎn)一件乙產(chǎn)品獲利3萬元萬元，采用哪種采用哪種生產(chǎn)安排利潤最大？生產(chǎn)安排利潤最大？2841641200 xyxyxy 0 xy4348133zyx N N（2 2，3 3）142yx 變式：變式：求利潤求利潤z=x+3y的最大值的最大值.max

6、23 311z練習(xí)練習(xí)解下列線性規(guī)劃問題：解下列線性規(guī)劃問題：1、求、求z=2x+y的最大值，使式中的的最大值，使式中的x、y滿足約束條件：滿足約束條件：11yyxxyxOyABCy=x x+y=1y=-12x+y=011yyxxyB:(-1,-1)C:(2,-1)Zmin=-3Zmax=3 目標(biāo)函數(shù)：目標(biāo)函數(shù)： Z=2x+y解線性規(guī)劃問題的步驟：解線性規(guī)劃問題的步驟： （2 2）移：在線性目標(biāo)函數(shù)所表示的一組平行線中，）移：在線性目標(biāo)函數(shù)所表示的一組平行線中， 利用平移的方法找出與可行域有公共點且縱截距最利用平移的方法找出與可行域有公共點且縱截距最大或最小的直線大或最小的直線 ；; ;（3

7、3）求：通過解方程組求出最優(yōu)解；）求：通過解方程組求出最優(yōu)解； （4 4）答：作出答案。）答：作出答案。 （1 1）畫：畫出線性約束條件所表示的可行域；）畫：畫出線性約束條件所表示的可行域；體驗體驗: :二、二、最優(yōu)解最優(yōu)解一般在可行域的一般在可行域的頂點頂點處取得處取得三、在哪個頂點取得不僅與三、在哪個頂點取得不僅與B B的符號有關(guān)，的符號有關(guān)， 而且還與直線而且還與直線 Z=Z=Ax+ByAx+By的的斜率斜率有關(guān)有關(guān)一、一、先定先定可行域和平移方向，再找最優(yōu)解?？尚杏蚝推揭品较?，再找最優(yōu)解。例例2 2、一個化肥廠生產(chǎn)甲、乙兩種混合肥料，生產(chǎn)一個化肥廠生產(chǎn)甲、乙兩種混合肥料，生產(chǎn)1 1車車

8、皮甲種肥料的主要原料是磷酸鹽皮甲種肥料的主要原料是磷酸鹽4t4t、硝酸鹽、硝酸鹽18t18t；生產(chǎn)；生產(chǎn)1 1車皮乙種肥料需要的主要原料是磷酸鹽車皮乙種肥料需要的主要原料是磷酸鹽1t1t、硝酸鹽、硝酸鹽15t15t?，F(xiàn)庫存磷酸鹽?，F(xiàn)庫存磷酸鹽10t10t、硝酸鹽、硝酸鹽66t66t，在此基礎(chǔ)上生，在此基礎(chǔ)上生產(chǎn)這兩種混合肥料。列出滿足生產(chǎn)條件的數(shù)學(xué)關(guān)系式，產(chǎn)這兩種混合肥料。列出滿足生產(chǎn)條件的數(shù)學(xué)關(guān)系式，并畫出相應(yīng)的平面區(qū)域。并計算生產(chǎn)甲、乙兩種肥料并畫出相應(yīng)的平面區(qū)域。并計算生產(chǎn)甲、乙兩種肥料各多少車皮，能夠產(chǎn)生最大的利潤？各多少車皮，能夠產(chǎn)生最大的利潤？解：設(shè)解：設(shè)x x、y y分別為計劃生

9、產(chǎn)甲、乙兩種混合分別為計劃生產(chǎn)甲、乙兩種混合 肥料的車皮數(shù)，于是滿足以下條件：肥料的車皮數(shù)，于是滿足以下條件：xyo4 4 x x y y 1 1 0 01 1 8 8 x x 1 1 5 5 y y 6 6 6 6x x 0 0y y 0 0解：解：設(shè)生產(chǎn)甲種肥料設(shè)生產(chǎn)甲種肥料x x車皮、乙種肥料車皮、乙種肥料y y車皮，車皮， 能夠產(chǎn)生利潤能夠產(chǎn)生利潤Z Z萬元。目標(biāo)函數(shù)為萬元。目標(biāo)函數(shù)為Z Zx x0.5y0.5y， 可行域如圖可行域如圖： 把把Z Zx x0.5y0.5y變形變形為為y y2x2x2z2z，它表示斜率，它表示斜率為為2 2，在，在y y軸上的截距為軸上的截距為2z2z的

10、一組直線系。的一組直線系。 xyo由圖可以看出，當(dāng)直線經(jīng)過由圖可以看出，當(dāng)直線經(jīng)過可行域上的點可行域上的點MM時，時，截距截距2z2z最大，即最大，即z z最大。最大。 答：答：生產(chǎn)甲種、乙種肥料各生產(chǎn)甲種、乙種肥料各 2 2車皮，能夠產(chǎn)生最大利車皮，能夠產(chǎn)生最大利 潤，最大利潤為潤，最大利潤為3 3萬元。萬元。M容易求得容易求得MM（2 2，2 2），）， 則則Z Zmaxmax3 3練習(xí)題練習(xí)題某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入分別為某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入分別為30003000元、元、20002000元，甲、乙產(chǎn)品都需要在元，甲、乙產(chǎn)品都需要在A A、B B兩種

11、設(shè)兩種設(shè)備上加工，在每臺備上加工，在每臺A A、B B上加工上加工1 1件甲所需工時分別為件甲所需工時分別為1h1h、2h2h，加工，加工1 1件乙所需工時分別為件乙所需工時分別為2h,1h.A2h,1h.A、B B兩種兩種設(shè)備每月有效使用臺時數(shù)分別為設(shè)備每月有效使用臺時數(shù)分別為400h400h和和500h500h。如何安。如何安排生產(chǎn)可使收入最大？排生產(chǎn)可使收入最大？解：解： 設(shè)每月生產(chǎn)甲產(chǎn)品設(shè)每月生產(chǎn)甲產(chǎn)品x x件，生產(chǎn)乙產(chǎn)品件，生產(chǎn)乙產(chǎn)品y y件，每月收件，每月收入為入為Z Z千元，目標(biāo)函數(shù)為千元，目標(biāo)函數(shù)為Z Z3x3x2y2y，滿足的條件是，滿足的條件是x x 2 2 y y 4 4

12、 0 0 0 02 2 x x y y 5 5 0 0 0 0 x x 0 0y y 0 0 Z Z 3x3x2y2y 變形為變形為它表示斜率為它表示斜率為 的直線系，的直線系，Z Z與這條直線的截距有關(guān)。與這條直線的截距有關(guān)。223zxy23XYO400200250500 當(dāng)直線經(jīng)過點當(dāng)直線經(jīng)過點MM時，截距最大，時，截距最大，Z Z最大。最大。M解方程組解方程組50024002yxyx可得可得MM（200200，100100）Z Z 的最大值的最大值ZmaxZmax 3x3x2y2y800800（千元）（千元）故生產(chǎn)甲產(chǎn)品故生產(chǎn)甲產(chǎn)品200200件，件，乙產(chǎn)品乙產(chǎn)品100100件，收入最大

13、，件，收入最大，為為8080萬元。萬元。不等式組不等式組 表示的平面區(qū)域內(nèi)表示的平面區(qū)域內(nèi)的的整數(shù)點整數(shù)點共有（共有（ ）個）個123400yxyx鞏固練習(xí)鞏固練習(xí): 1 2 3 4 xy432104x+3y=12例例1 1、要將兩種大小不同規(guī)格的鋼板截成要將兩種大小不同規(guī)格的鋼板截成A A、 B B、C C三種規(guī)格，每張鋼板可同時截得三種三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示規(guī)格的小鋼板的塊數(shù)如下表所示 ： 規(guī)格類型規(guī)格類型鋼板類型鋼板類型第一種鋼板第一種鋼板第二種鋼板第二種鋼板A A規(guī)格規(guī)格B B規(guī)格規(guī)格C C規(guī)格規(guī)格2 21 12 21 13 31 1今需要今需要A

14、,B,CA,B,C三種規(guī)格的成品分別為三種規(guī)格的成品分別為1515，1818，2727塊，問各截這兩種鋼板多少張可得所需三塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。種規(guī)格成品，且使所用鋼板張數(shù)最少。解：設(shè)需截第一種鋼板解：設(shè)需截第一種鋼板x x張、第二種鋼板張、第二種鋼板y y張，可得張，可得x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN* 經(jīng)過可行域內(nèi)的整點經(jīng)過可行域內(nèi)的整點B(3,9)和和C(4,8)且和原點距且和原點距離最近的直線是離最近的直線是x+y=12，它們是最優(yōu)解它們是最優(yōu)

15、解.答答:(略略)作出一組平行直線作出一組平行直線z= x+y，目標(biāo)函數(shù)目標(biāo)函數(shù)z=z=x+yx+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)過點當(dāng)直線經(jīng)過點A A時時z=z=x+yx+y=11.4=11.4, ,但它不是最優(yōu)整數(shù)解，但它不是最優(yōu)整數(shù)解，將直線將直線x+y=11.4繼續(xù)向上平移繼續(xù)向上平移,例例3:某工廠生產(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種礦石種

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

17、利潤（元）利潤（元） 產(chǎn)品產(chǎn)品消耗量消耗量資源資源列表：列表：51046004491000300200360設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤總額為利潤總額為z元元返回返回 甲產(chǎn)品甲產(chǎn)品 （1t） 乙產(chǎn)品乙產(chǎn)品 （1t） 資源限額資源限額 （t）A種礦石（種礦石（t） B種礦石（種礦石（t） 煤（煤（t） 利潤（元）利潤（元） 產(chǎn)品產(chǎn)品消耗量消耗量資源資源列表：列表：51046004491000300200360把題中限制條件進(jìn)行把題中限制條件進(jìn)行轉(zhuǎn)化：轉(zhuǎn)化：約束條件約束條件10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1

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

19、x+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)過可行域上的點經(jīng)過可行域上的點M時時,目標(biāo)函數(shù)目標(biāo)函數(shù)在在y軸上截距最大軸上截距最大.ll l9030 0 xy10 201075405040此時此時z=600 x+1000y取得最大值取得最大值. 咖啡館配制兩種飲料甲種飲料每杯含奶粉咖啡館配制兩種飲料甲種飲料每杯含奶粉9g 、咖啡、咖啡4g、糖糖3g,乙種飲料每杯含奶粉乙種飲料每杯含奶粉4g 、咖啡、咖啡5g、糖、糖10g已知每天已知每天原料的使

20、用限額為奶粉原料的使用限額為奶粉3600g ，咖啡，咖啡2000g糖糖3000g,如果如果甲種飲料每杯能獲利甲種飲料每杯能獲利0.7元，乙種飲料每杯能獲利元，乙種飲料每杯能獲利1.2元，每元，每天在原料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種天在原料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種飲料各多少杯能獲利最大？飲料各多少杯能獲利最大？解：將已知數(shù)據(jù)列為下表：解：將已知數(shù)據(jù)列為下表： 消耗量消耗量資源資源甲產(chǎn)品甲產(chǎn)品（1 杯）杯）乙產(chǎn)品乙產(chǎn)品(1杯杯)資源限額（資源限額（g）奶粉（奶粉（g g）9 94 436003600咖啡咖啡(g)(g)4 45 520002000糖糖(g)(g)3 3101030003000利潤（元）利潤（元）0.70.71.21.2 產(chǎn)品產(chǎn)品設(shè)每天應(yīng)配制甲種飲料設(shè)每天應(yīng)配制甲種飲料x x杯，乙種飲料杯，乙種飲料y y杯，則杯，則003000103200054360049yxyxyxyx作出可行域：作出可行域：目標(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，把直線把直線l l向右上方平移至向右上方平移至l l1 1的位置時，的位置時，直線經(jīng)過可行域上的點直線經(jīng)過可行域上的點C C