簡單的線性規(guī)劃問題(一)

1、 在現(xiàn)實生產(chǎn)、生活中經(jīng)常會遇到資源利用、在現(xiàn)實生產(chǎn)、生活中經(jīng)常會遇到資源利用、人力調(diào)配、生產(chǎn)安排等問題人力調(diào)配、生產(chǎn)安排等問題. . 這類問題在數(shù)學(xué)中這類問題在數(shù)學(xué)中將其歸為線性規(guī)劃問題將其歸為線性規(guī)劃問題. . 線性規(guī)劃是利用數(shù)學(xué)為工具，來研究一定的線性規(guī)劃是利用數(shù)學(xué)為工具，來研究一定的人、財、物、時、空等資源在一定條件下，如何人、財、物、時、空等資源在一定條件下，如何精打細(xì)算巧安排，用最少的資源，取得最大的經(jīng)精打細(xì)算巧安排，用最少的資源，取得最大的經(jīng)濟(jì)效益濟(jì)效益. . 它是數(shù)學(xué)規(guī)劃中理論較完整、方法較成它是數(shù)學(xué)規(guī)劃中理論較完整、方法較成熟、應(yīng)用較廣泛的一個分支熟、應(yīng)用較廣泛的一個分支, ,

2、并能解決科學(xué)研究、并能解決科學(xué)研究、工程設(shè)計、經(jīng)常管理等許多方面的實際問題工程設(shè)計、經(jīng)常管理等許多方面的實際問題. . 某工廠用某工廠用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

3、萬元萬元,生產(chǎn)生產(chǎn)1 件乙件乙 種產(chǎn)品獲利種產(chǎn)品獲利3萬元萬元, 采用哪種生產(chǎn)安排利潤最采用哪種生產(chǎn)安排利潤最 大大?問題提出問題提出32利潤利潤( (萬元萬元) )821所需時間所需時間1240B種配件種配件1604A種配件種配件資源限額資源限額 乙產(chǎn)品乙產(chǎn)品 (1件件)甲產(chǎn)品甲產(chǎn)品 (1件件)產(chǎn)品產(chǎn)品消消 耗耗 量量資資 源源把引例的有關(guān)數(shù)據(jù)列表表示如下把引例的有關(guān)數(shù)據(jù)列表表示如下:設(shè)甲設(shè)甲, ,乙兩種產(chǎn)品分別生產(chǎn)乙兩種產(chǎn)品分別生產(chǎn)x, y件件, ,數(shù)學(xué)建模數(shù)學(xué)建模2841641200 xyxyxy 0 xy4348將上面不等式組表示成平面將上面不等式組表示成平面上的區(qū)域上的區(qū)域, , 區(qū)

4、域內(nèi)所有坐標(biāo)區(qū)域內(nèi)所有坐標(biāo)為整數(shù)的點為整數(shù)的點P (x,y) 就代表所就代表所有可能的日生產(chǎn)安排有可能的日生產(chǎn)安排, 當(dāng)點當(dāng)點P (x, y)在上述平面區(qū)域中在上述平面區(qū)域中時所時所安排的生產(chǎn)任務(wù)安排的生產(chǎn)任務(wù)x, y都是有意義的都是有意義的.設(shè)甲設(shè)甲, ,乙兩種產(chǎn)品分別生產(chǎn)乙兩種產(chǎn)品分別生產(chǎn)x, y件件, ,由己知條件可得由己知條件可得:問題：問題：求利潤求利潤2x+3y的最大值的最大值.28xy4x 3y 若設(shè)利潤為若設(shè)利潤為z,則則z=2x+3y,這樣上述問題轉(zhuǎn)化為這樣上述問題轉(zhuǎn)化為:當(dāng)當(dāng)x,y在滿足上述約束條件時在滿足上述約束條件時,z的最大值為多少的最大值為多少?2223-,-,33

5、3,3zzxyyxzy 把把變變形形為為這這是是斜斜率率為為在在 軸軸上上的的截截距距為為 的的直直線線當(dāng)點當(dāng)點P在可允許的取值范圍變化時在可允許的取值范圍變化時,.3zz求求截截距距 的的最最值值 即即可可得得 的的最最值值2841641200 xyxyxy 0 xy4348233zyx M（4，2）142yx 問題：問題：求利潤求利潤z=2x+3y的最大值的最大值.143224max Z問題解決問題解決2841641200 xyxyxy 象這樣關(guān)于象這樣關(guān)于x,y一次不等式組的一次不等式組的約束條件稱為約束條件稱為線性約束線性約束條件條件z=2x+3y稱為稱為目標(biāo)函數(shù)目標(biāo)函數(shù), (因這里目

6、標(biāo)函因這里目標(biāo)函數(shù)為關(guān)于數(shù)為關(guān)于x, y的一次式的一次式, 又稱為又稱為線性目線性目標(biāo)函數(shù)標(biāo)函數(shù))在線性約束下求線性目標(biāo)函數(shù)的最值問題在線性約束下求線性目標(biāo)函數(shù)的最值問題, ,統(tǒng)稱統(tǒng)稱為為線性規(guī)劃線性規(guī)劃滿足線性約束條件的解滿足線性約束條件的解(x,y)叫做叫做可行解可行解所有可行解組成的集合叫做所有可行解組成的集合叫做可行域可行域使目標(biāo)函數(shù)使目標(biāo)函數(shù)取得最值取得最值的可行解叫做這個問題的的可行解叫做這個問題的最優(yōu)解最優(yōu)解概念形成概念形成2841641200 xyxyxy 133zyx N（2 2，3 3）142yx 即求利潤即求利潤z=x+3y的最大值的最大值.max23 311zy0 x4

7、3481.上例中若生產(chǎn)一件甲產(chǎn)品獲利上例中若生產(chǎn)一件甲產(chǎn)品獲利1萬元萬元,生產(chǎn)一件生產(chǎn)一件乙產(chǎn)品獲利乙產(chǎn)品獲利3萬元萬元,采用哪種生產(chǎn)安排利潤最大采用哪種生產(chǎn)安排利潤最大?變式訓(xùn)練變式訓(xùn)練2. 求求z=2x+y的最大、小值的最大、小值,使使x、y滿足約束條件：滿足約束條件：11yyxxy3.求求z=3x+5y的最大、小值的最大、小值,使使x、y滿足約束條件：滿足約束條件：5315153xyyxxyxOyABCy=x x+y=1y=-12x+y=011yyxxyB(-1,-1)C(2,-1)zmin=-3zmax=3 目標(biāo)函數(shù)：目標(biāo)函數(shù)： z=2x+y例例1.營養(yǎng)學(xué)家指出，成人良好的日常飲食應(yīng)該

8、至少提供營養(yǎng)學(xué)家指出，成人良好的日常飲食應(yīng)該至少提供 0.075kg的碳水化合物，的碳水化合物，0.06kg的蛋白質(zhì)的蛋白質(zhì), 0.06kg的脂的脂 肪肪.1kg食物食物A含有含有0.105kg碳水化合物碳水化合物, 0.07kg蛋白質(zhì)蛋白質(zhì), 0.14kg脂肪，花費脂肪，花費28元；而元；而1kg食物食物B含有含有0.105kg碳碳 水化合物水化合物, 0.14kg蛋白質(zhì)蛋白質(zhì), 0.07kg脂肪脂肪, 花費花費21元元.為了為了 滿足營養(yǎng)專家指出的日常飲食要求滿足營養(yǎng)專家指出的日常飲食要求, 同時使花費最低同時使花費最低, 需要同時食用食物需要同時食用食物A和食物和食物B多少多少kg?規(guī)范

9、解答規(guī)范解答0 1050 1050 0757750 070 140 0671460 140 070 06147600002821:kg, kg,.,:.xA yBzxyxyxyxyxyxyxxyyzxy解解 設(shè)設(shè)每每天天食食用用食食物物食食物物總總成成本本為為 依依題題意意有有即即 目目標(biāo)標(biāo)函函數(shù)數(shù)為為,.作作出出以以上上不不等等式式組組所所表表示示的的平平面面區(qū)區(qū)域域 如如圖圖中中所所示示的的陰陰影影部部分分17374757671271727374757671Oxy7x+14y=614x+7y=67x+7y=577514761 47 714282128211677min,( , ) .xyx

10、yMzxyz解解方方程程組組得得代代入入得得:AB答答 每每天天食食用用食食物物 約約1 14 43 3g g, ,食食物物 約約5 57 71 1g g, ,能能夠夠滿滿足足日日常常飲飲食食要要 求求, ,又又使使花花費費最最低低, ,最最低低成成本本為為1 16 6元元. .282102821:,.lxylMzxy作作直直線線當(dāng)當(dāng)移移動動直直線線 過過圖圖中中的的點點時時取取得得最最小小值值17374757671271727374757671Oxy7x+14y=614x+7y=67x+7y=5M28x+21y=0例例2 . 要將兩種大小不同的鋼板截成要將兩種大小不同的鋼板截成A A、B B

11、、C C三種規(guī)格三種規(guī)格, ,每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表示：示： 鋼型鋼型A規(guī)格規(guī)格B B規(guī)格規(guī)格C C規(guī)格規(guī)格第一種鋼板第一種鋼板2 21 11 1第二種鋼板第二種鋼板1 12 23 3 今需要今需要A A、B B、C C三種規(guī)格的成品分別為三種規(guī)格的成品分別為1515、1818、2727塊，則截這兩種鋼板多少張可得所需塊，則截這兩種鋼板多少張可得所需A A、B B、C C三種三種規(guī)格成品，且使所用鋼板張數(shù)最少？規(guī)格成品，且使所用鋼板張數(shù)最少？規(guī)格規(guī)格解解：設(shè)需截第一種鋼板設(shè)需截第一種鋼板x張張,第二種鋼板第二種鋼板y張張,共

12、需這兩種鋼共需這兩種鋼 板共板共z張，根據(jù)題意可得：張，根據(jù)題意可得：21521832700, ,.xyxyxyzxyxy目目 標(biāo)標(biāo) 函函 數(shù)數(shù) 是是作出以上不等式組所作出以上不等式組所表示的平面區(qū)域，如表示的平面區(qū)域，如圖中所示的陰影部分圖中所示的陰影部分.0:, lxylM作作直直線線當(dāng)當(dāng)平平移移直直線線 過過圖圖中中的的點點時時,z,z取取最最小小值值. .x + 2 y = 18277.515180 xy2 x+ y = 15x + 3 y = 27M32718 392155518 3955,(,),( , ),(,).xyMxyx yx yM解解方方程程組組得得但但此此問問題題中中的

13、的最最優(yōu)優(yōu)解解中中的的都都是是整整數(shù)數(shù), ,所所以以不不是是最最優(yōu)優(yōu)解解x + 2 y = 18277.515180 xy2 x+ y = 15x + 3 y = 27C (4,8)B(3,9)M123 94 812 min,( , )( , ),zyxBCz經(jīng)經(jīng)過過可可行行域域內(nèi)內(nèi)整整點點且且使使 最最小小的的直直線線是是它它經(jīng)經(jīng)過過和和它它們們是是最最優(yōu)優(yōu)解解. . 12:,.答答 要要截截得得所所需需三三種種規(guī)規(guī)格格的的鋼鋼板板 且且使使所所截截兩兩種種鋼鋼板板張張數(shù)數(shù)最最小小的的方方法法有有兩兩種種, ,第第一一種種截截法法是是第第 一一種種鋼鋼板板3 3張張, ,第第二二種種鋼鋼板板

14、張張; ;第第二二種種截截法法是是截截第第一一種種鋼鋼板板4 4 張張, ,第第二二種種鋼鋼板板8 8張張. . 兩兩種種截截法法都都最最少少要要兩兩種種鋼鋼板板張張例例3.3.一個化肥廠生產(chǎn)甲、乙兩種混合肥料一個化肥廠生產(chǎn)甲、乙兩種混合肥料, ,生產(chǎn)生產(chǎn)1 1車皮甲車皮甲種肥料的主要原料是磷酸鹽種肥料的主要原料是磷酸鹽4t4t、硝酸鹽、硝酸鹽18t18t；生產(chǎn)；生產(chǎn)1 1車皮車皮乙種肥料需要的主要原料是磷酸鹽乙種肥料需要的主要原料是磷酸鹽1t1t、硝酸鹽、硝酸鹽15t.15t.現(xiàn)庫現(xiàn)庫存磷酸鹽存磷酸鹽10t10t、硝酸鹽、硝酸鹽66t66t，在此基礎(chǔ)上生產(chǎn)這兩種混合，在此基礎(chǔ)上生產(chǎn)這兩種混合

15、肥料肥料. .列出滿足生產(chǎn)條件的數(shù)學(xué)關(guān)系式列出滿足生產(chǎn)條件的數(shù)學(xué)關(guān)系式, ,并畫出相應(yīng)的平并畫出相應(yīng)的平面區(qū)域面區(qū)域. .若生產(chǎn)若生產(chǎn)1 1車皮甲種肥料，產(chǎn)生的利潤為車皮甲種肥料，產(chǎn)生的利潤為1000010000元元, ,生產(chǎn)生產(chǎn)1 1車皮的乙種肥料，產(chǎn)生的利潤為車皮的乙種肥料，產(chǎn)生的利潤為50005000元元, ,計算生產(chǎn)計算生產(chǎn)甲、乙兩種肥料各多少車皮，能夠產(chǎn)生最大的利潤？甲、乙兩種肥料各多少車皮，能夠產(chǎn)生最大的利潤？解：設(shè)生產(chǎn)甲種肥料解：設(shè)生產(chǎn)甲種肥料x車皮、乙種肥料車皮、乙種肥料y車皮，能夠產(chǎn)生利潤車皮，能夠產(chǎn)生利潤z萬萬 元元.依題意有依題意有 4101815660 500,.xyx

16、yzxyxy目目 標(biāo)標(biāo) 函函 數(shù)數(shù) 為為作出以上不等式組所表示的平面區(qū)域，如圖作出以上不等式組所表示的平面區(qū)域，如圖中所示的陰影部分中所示的陰影部分.xyoM0 50:., lxylMz作作直直線線當(dāng)當(dāng)平平移移直直線線 過過圖圖中中的的點點時時, , 取取最最大大值值. .容易求得容易求得M點的坐標(biāo)為點的坐標(biāo)為（2 2，2 2），），則則Zmaxmax3 3答：答：生產(chǎn)甲種、乙種肥料各生產(chǎn)甲種、乙種肥料各2 2車車 皮，能夠產(chǎn)生最大利潤，最皮，能夠產(chǎn)生最大利潤，最 大利潤為大利潤為3 3萬元。萬元。解線性規(guī)劃問題的步驟：解線性規(guī)劃問題的步驟： (3)(3)移移: :在線性目標(biāo)函數(shù)所表示的一組平

17、行線中，利用在線性目標(biāo)函數(shù)所表示的一組平行線中，利用 平移的方法找出與可行域有公共點且縱截距最平移的方法找出與可行域有公共點且縱截距最 大或最小的直線大或最小的直線; ; (4)(4)求求: :通過解方程組求出最優(yōu)解；通過解方程組求出最優(yōu)解； (5)(5)答答: :作出答案作出答案. . (2)(2)畫畫: :畫出線性約束條件所表示的可行域；畫出線性約束條件所表示的可行域；(1)(1)列列: :設(shè)變量，列出約束條件和目標(biāo)函數(shù)；設(shè)變量，列出約束條件和目標(biāo)函數(shù)；先定先定可行域和平移方向，再找最優(yōu)解可行域和平移方向，再找最優(yōu)解. .最優(yōu)解最優(yōu)解一般在可行域的一般在可行域的頂點頂點處取得處取得在哪個頂

18、點取得不僅與在哪個頂點取得不僅與B的符號有關(guān)的符號有關(guān), ,而且而且 還與直線還與直線 z=Ax+By的的斜率斜率有關(guān)有關(guān)體驗體驗方法總結(jié)方法總結(jié) 某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入分別為分別為30003000元、元、20002000元元, , 甲、乙產(chǎn)品都需要在甲、乙產(chǎn)品都需要在A A、B B兩兩種設(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