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

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

2、并能解決科學研究、并能解決科學研究、工程設計、經常管理等許多方面的實際問題工程設計、經常管理等許多方面的實際問題. . 某工廠用某工廠用A,B兩種配件生產甲兩種配件生產甲, ,乙兩種產品乙兩種產品, ,每生產一件甲種產品使用每生產一件甲種產品使用4個個A配件耗時配件耗時1h,每每生產一件乙種產品使用生產一件乙種產品使用4個個B配件耗時配件耗時2h,該廠該廠每天最多可從配件廠獲得每天最多可從配件廠獲得16個個A配件和配件和12個個B配件配件, ,按每天工作按每天工作8小時小時計算計算, ,該廠所有可能的該廠所有可能的日生產安排是什么日生產安排是什么? 若生產若生產1件甲種產品獲利件甲種產品獲利2

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

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

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

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

7、3481.上例中若生產一件甲產品獲利上例中若生產一件甲產品獲利1萬元萬元,生產一件生產一件乙產品獲利乙產品獲利3萬元萬元,采用哪種生產安排利潤最大采用哪種生產安排利潤最大?變式訓練變式訓練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 目標函數：目標函數： z=2x+y例例1.營養(yǎng)學家指出，成人良好的日常飲食應該

8、至少提供營養(yǎng)學家指出，成人良好的日常飲食應該至少提供 0.075kg的碳水化合物，的碳水化合物，0.06kg的蛋白質的蛋白質, 0.06kg的脂的脂 肪肪.1kg食物食物A含有含有0.105kg碳水化合物碳水化合物, 0.07kg蛋白質蛋白質, 0.14kg脂肪，花費脂肪，花費28元；而元；而1kg食物食物B含有含有0.105kg碳碳 水化合物水化合物, 0.14kg蛋白質蛋白質, 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解解 設設每每天天食食用用食食物物食食物物總總成成本本為為 依依題題意意有有即即 目目標標函函數數為為,.作作出出以以上上不不等等式式組組所所表表示示的的平平面面區(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作作直直線線當當移移動動直直線線 過過圖圖中中的的點點時時取取得得最最小小值值17374757671271727374757671Oxy7x+14y=614x+7y=67x+7y=5M28x+21y=0例例2 . 要將兩種大小不同的鋼板截成要將兩種大小不同的鋼板截成A A、B B

11、、C C三種規(guī)格三種規(guī)格, ,每張鋼板可同時截得三種規(guī)格的小鋼板的塊數如下表每張鋼板可同時截得三種規(guī)格的小鋼板的塊數如下表示：示： 鋼型鋼型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ī)格成品，且使所用鋼板張數最少？規(guī)格成品，且使所用鋼板張數最少？規(guī)格規(guī)格解解：設需截第一種鋼板設需截第一種鋼板x張張,第二種鋼板第二種鋼板y張張,共

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

13、的最最優(yōu)優(yōu)解解中中的的都都是是整整數數, ,所所以以不不是是最最優(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經經過過可可行行域域內內整整點點且且使使 最最小小的的直直線線是是它它經經過過和和它它們們是是最最優(yōu)優(yōu)解解. . 12:,.答答 要要截截得得所所需需三三種種規(guī)規(guī)格格的的鋼鋼板板 且且使使所所截截兩兩種種鋼鋼板板張張數數最最小小的的方方法法有有兩兩種種, ,第第一一種種截截法法是是第第 一一種種鋼鋼板板3 3張張, ,第第二二種種鋼鋼板板

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

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

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

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

18、點取得不僅與在哪個頂點取得不僅與B的符號有關的符號有關, ,而且而且 還與直線還與直線 z=Ax+By的的斜率斜率有關有關體驗體驗方法總結方法總結 某廠擬生產甲、乙兩種適銷產品，每件銷售收入某廠擬生產甲、乙兩種適銷產品，每件銷售收入分別為分別為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。如。如何何安排生產可使收入最大？安排生產可使收入最大？解解設每月生產甲產品設每月生產甲產品x x件，生產乙產品件，生產乙產品y y件，每月收入件，每月收入 為為Z Z千元，目標函數為千元，目標函數為Z Z3x3x2y2y，滿足的條件是，滿足的條件是x x 2 2 y y