簡單的線性規(guī)劃問題演示文稿

簡單的線性規(guī)劃問題演示文稿目前一頁\總數(shù)五十頁\編于七點(diǎn)簡單的線性規(guī)劃問題目前二頁\總數(shù)五十頁\編于七點(diǎn)3新課探究

某工廠用A、B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，每生產(chǎn)一件甲產(chǎn)品使用4個A配件耗時1h，每生產(chǎn)一件乙產(chǎn)品使用4個B配件耗時2h，該廠每天最多可從配件廠獲得16個A配件和12個B配件，按每天工作8h計算，該廠所有可能的日生產(chǎn)安排是什么？解：按甲、乙兩種產(chǎn)品分別生產(chǎn)x、y件，由已知條件可得二元一次不等式組目前三頁\總數(shù)五十頁\編于七點(diǎn)32利潤(萬元)821所需時間1240B種配件1604A種配件資源限額

乙產(chǎn)品(1件)甲產(chǎn)品(1件)產(chǎn)品消耗量資源把問題1的有關(guān)數(shù)據(jù)列表表示如下:設(shè)甲,乙兩種產(chǎn)品分別生產(chǎn)x,y件,目前四頁\總數(shù)五十頁\編于七點(diǎn)將上述不等式組表示成平面上的區(qū)域yx4843o

若生產(chǎn)一件甲產(chǎn)品獲利2萬元，生產(chǎn)一件乙產(chǎn)品獲利3萬元，采用那種生產(chǎn)安排利潤最大？

設(shè)工廠獲得的利潤為z，則z＝2x＋3y把z＝2x＋3y變形為

它表示斜率為的一組平行直線，z與這條直線的截距有關(guān)。如圖可見，當(dāng)直線經(jīng)過區(qū)域上的點(diǎn)M時，截距最大，即z最大。M甲、乙兩種產(chǎn)品分別生產(chǎn)x、y件目前五頁\總數(shù)五十頁\編于七點(diǎn)象這樣關(guān)于x,y一次不等式組的約束條件稱為線性約束條件Z=2x+3y稱為目標(biāo)函數(shù),(因這里目標(biāo)函數(shù)為關(guān)于x,y的一次式,又稱為線性目標(biāo)函數(shù)在線性約束下求線性目標(biāo)函數(shù)的最值問題,統(tǒng)稱為線性規(guī)劃,

二、基本概念目前六頁\總數(shù)五十頁\編于七點(diǎn)

二、基本概念yx4843o

滿足線性約束的解（x，y）叫做可行解。

由所有可行解組成的集合叫做可行域。

使目標(biāo)函數(shù)取得最大值或最小值的可行解叫做這個問題的最優(yōu)解?？尚杏蚩尚薪庾顑?yōu)解目前七頁\總數(shù)五十頁\編于七點(diǎn)可行域線性規(guī)劃概念理解問題：設(shè)z=2x+y，式中變量滿足下列條件：求z的最大值與最小值。

目標(biāo)函數(shù)（線性目標(biāo)函數(shù)）線性約束條件目前八頁\總數(shù)五十頁\編于七點(diǎn)變式：求利潤z=x+4y的最大值.目前九頁\總數(shù)五十頁\編于七點(diǎn)解:按甲、乙兩種產(chǎn)品分別生產(chǎn)x、y件，目標(biāo)函數(shù)為Z,那么：約束條件為目標(biāo)函數(shù)為作出上述約束條件所表示的可行域如下：yx48oM將變形為這是斜率為，隨z變化的平行直線系，是直線在Y軸上的截距，當(dāng)最大時，z取得最大值。所以直線與可行域相交且在Y軸上的截距最大時，目標(biāo)函數(shù)取得最大值。N由圖可見，當(dāng)直線經(jīng)過可行域上的N點(diǎn)時最大，即最大。目前十頁\總數(shù)五十頁\編于七點(diǎn)解方程組得N點(diǎn)的坐標(biāo)為（2，3）。所以目前十一頁\總數(shù)五十頁\編于七點(diǎn)線性規(guī)劃：求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題．

可行解：滿足線性約束條件的解(x，y)叫可行解；

可行域：由所有可行解組成的集合叫做可行域；

最優(yōu)解：使目標(biāo)函數(shù)取得最大或最小值的可行解叫線性規(guī)劃問題的最優(yōu)解。

可行域2x+y=32x+y=12(1,1)(5,2)復(fù)習(xí)線性規(guī)劃目前十二頁\總數(shù)五十頁\編于七點(diǎn)[練習(xí)]解下列線性規(guī)劃問題：1、求z=2x+y的最大值，使式中的x、y滿足約束條件：目前十三頁\總數(shù)五十頁\編于七點(diǎn)xOyABCy=xx+y=1y=-12x+y=0B:(-1,-1)C:(2,-1)Zmin=-3Zmax=3目標(biāo)函數(shù)：Z=2x+y目前十四頁\總數(shù)五十頁\編于七點(diǎn)15解線性規(guī)劃問題的步驟：

（1）2、畫：

畫出線性約束條件所表示的可行域；

（2）3、移：

在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；

（3）4、求：通過解方程組求出最優(yōu)解；

（4）5、答：作出答案。

1、找

找出線性約束條件、目標(biāo)函數(shù)；

目前十五頁\總數(shù)五十頁\編于七點(diǎn)例2：xy0目前十六頁\總數(shù)五十頁\編于七點(diǎn)二、練習(xí)1、求z＝3x＋5y的最小值，使x、y滿足約束條件：目前十七頁\總數(shù)五十頁\編于七點(diǎn)1.解：作出平面區(qū)域xyoABCz＝3x＋5y作出直線3x＋5y＝z的圖像，可知直線經(jīng)過A點(diǎn)時，Z取最大值；直線經(jīng)過B點(diǎn)時，Z取最小值。求得A（1.5，2.5），B（－2，－1），則Zmax=17，Zmin=－11。目前十八頁\總數(shù)五十頁\編于七點(diǎn)第二課時簡單的線性規(guī)劃問題xyo目前十九頁\總數(shù)五十頁\編于七點(diǎn)復(fù)習(xí)線性規(guī)劃線性規(guī)劃：求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題．

可行解：滿足線性約束條件的解(x，y)叫可行解；

可行域：由所有可行解組成的集合叫做可行域；最優(yōu)解：使目標(biāo)函數(shù)取得最大或最小值的可行解叫線性規(guī)劃問題的最優(yōu)解?？尚杏?x+y=32x+y=12(1,1)(5,2)目前二十頁\總數(shù)五十頁\編于七點(diǎn)21解線性規(guī)劃問題的步驟：

（1）2、畫：

畫出線性約束條件所表示的可行域；

（2）3、移：

在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；

（3）4、求：通過解方程組求出最優(yōu)解；

（4）5、答：作出答案。

1、找

找出線性約束條件、目標(biāo)函數(shù)；

目前二十一頁\總數(shù)五十頁\編于七點(diǎn)一、線性規(guī)劃在實(shí)際中的應(yīng)用：線性規(guī)劃的理論和方法主要在兩類問題中得到應(yīng)用，一是在人力、物力、資金等資源一定的條件下，如何使用它們來完成最多的任務(wù)；二是給定一項任務(wù)，如何合理安排和規(guī)劃，能以最少的人力、物力、資金等資源來完成該項任務(wù)下面我們就來看看線性規(guī)劃在實(shí)際中的一些應(yīng)用：

目前二十二頁\總數(shù)五十頁\編于七點(diǎn)二、例題例5、營養(yǎng)學(xué)家指出，成人良好的日常飲食應(yīng)該至少提供0.075kg的碳水化合物，0.06kg的蛋白質(zhì)，0.06kg的脂肪，1kg食物A含有0.105kg碳水化合物，0.07kg蛋白質(zhì)，0.14kg脂肪，花費(fèi)28元；而1kg食物B含有0.105kg碳水化合物，0.14kg蛋白質(zhì)，0.07kg脂肪，花費(fèi)21元。為了滿足營養(yǎng)專家指出的日常飲食要求，同時使花費(fèi)最低，需要同時食用食物A和食物B多少kg？分析：將已知數(shù)據(jù)列成表格食物／kg碳水化合物／kg蛋白質(zhì)/kg脂肪／kgA0.1050.070.14B0.1050.140.07目前二十三頁\總數(shù)五十頁\編于七點(diǎn)解：設(shè)每天食用xkg食物A，ykg食物B，總成本為z，那么目標(biāo)函數(shù)為：z＝28x＋21y作出二元一次不等式組所表示的平面區(qū)域，即可行域1、找目前二十四頁\總數(shù)五十頁\編于七點(diǎn)把目標(biāo)函數(shù)z＝28x＋21y變形為xyo/575/76/73/73/76/7它表示斜率為縱截距隨z變化的一組平行直線

是直線在y軸上的截距，當(dāng)截距最小時，z的值最小。M如圖可見，當(dāng)直線z＝28x＋21y經(jīng)過可行域上的點(diǎn)M時，縱截距最小，即z最小。2、畫3、移目前二十五頁\總數(shù)五十頁\編于七點(diǎn)M點(diǎn)是兩條直線的交點(diǎn)，解方程組得M點(diǎn)的坐標(biāo)為：所以zmin＝28x＋21y＝16

由此可知，每天食用食物A143g，食物B約571g，能夠滿足日常飲食要求，又使花費(fèi)最低，最低成本為16元。4、求5、答目前二十六頁\總數(shù)五十頁\編于七點(diǎn)例6、要將兩種大小不同規(guī)格的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：

規(guī)格類型鋼板類型第一種鋼板第二種鋼板A規(guī)格B規(guī)格C規(guī)格212131今需要A,B,C三種規(guī)格的成品分別為15，18，27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。解：設(shè)需截第一種鋼板x張、第二種鋼板y張，可得目前二十七頁\總數(shù)五十頁\編于七點(diǎn)x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*

經(jīng)過可行域內(nèi)的整點(diǎn)B(3,9)和C(4,8)且和原點(diǎn)距離最近的直線是x+y=12，它們是最優(yōu)解.答:(略)作出一組平行直線z=x+y，目標(biāo)函數(shù)z=x+yB(3,9)C(4,8)A(18/5,39/5)打網(wǎng)格線法在可行域內(nèi)打出網(wǎng)格線，當(dāng)直線經(jīng)過點(diǎn)A時z=x+y=11.4,但它不是最優(yōu)整數(shù)解，將直線x+y=11.4繼續(xù)向上平移,目前二十八頁\總數(shù)五十頁\編于七點(diǎn)2x+y=15x+3y=27x+2y=18x+y=0直線x+y=12經(jīng)過的整點(diǎn)是B(3,9)和C(4,8)，它們是最優(yōu)解.

作出一組平行直線z

=

x+y，目標(biāo)函數(shù)z=x+yB(3,9)C(4,8)A(18/5,39/5)當(dāng)直線經(jīng)過點(diǎn)A時z=x+y=11.4,但它不是最優(yōu)整數(shù)解.作直線x+y=12x+y=12解得交點(diǎn)B,C的坐標(biāo)B(3,9)和C(4,8)調(diào)整優(yōu)值法2x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*x0y目前二十九頁\總數(shù)五十頁\編于七點(diǎn)即先求非整數(shù)條件下的最優(yōu)解，調(diào)整Z的值使不定方程Ax+By=Z存在最大（?。┑恼c(diǎn)值，最后篩選出整點(diǎn)最優(yōu)解．即先打網(wǎng)格，描出可行域內(nèi)的整點(diǎn)，平移直線，最先經(jīng)過或最后經(jīng)過的整點(diǎn)坐標(biāo)即為最優(yōu)整解．線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:1.平移找解法：

2.調(diào)整優(yōu)解法：小結(jié)：目前三十頁\總數(shù)五十頁\編于七點(diǎn)例7、一個化肥廠生產(chǎn)甲、乙兩種混合肥料，生產(chǎn)1車皮甲種肥料的主要原料是磷酸鹽4t、硝酸鹽18t，獲利10000元；生產(chǎn)1車皮乙種肥料需要的主要原料是磷酸鹽1t、硝酸鹽15t，獲利5000元?，F(xiàn)庫存磷酸鹽10t、硝酸鹽66t，在此基礎(chǔ)上生產(chǎn)這兩種混合肥料。列出滿足生產(chǎn)條件的數(shù)學(xué)關(guān)系式，并畫出相應(yīng)的平面區(qū)域。并計算生產(chǎn)甲、乙兩種肥料各多少車皮，能夠產(chǎn)生最大的利潤？解：設(shè)x、y分別為計劃生產(chǎn)甲、乙兩種混合肥料的車皮數(shù)，于是滿足以下條件：xyo目前三十一頁\總數(shù)五十頁\編于七點(diǎn)解：設(shè)生產(chǎn)甲種肥料x車皮、乙種肥料y車皮，能夠產(chǎn)生利潤Z萬元。目標(biāo)函數(shù)為Z＝x＋0.5y，可行域如圖：把Z＝x＋0.5y變形為y＝－2x＋2z，它表示斜率為－2，在y軸上的截距為2z的一組直線系。

xyo由圖可以看出，當(dāng)直線經(jīng)過可行域上的點(diǎn)M時，截距2z最大，即z最大。

故生產(chǎn)甲種、乙種肥料各2車皮，能夠產(chǎn)生最大利潤，最大利潤為3萬元。M容易求得M點(diǎn)的坐標(biāo)為（2，2），則Zmin＝3目前三十二頁\總數(shù)五十頁\編于七點(diǎn)例8、某人準(zhǔn)備投資1200萬元興辦一所完全中學(xué)。對教育市場進(jìn)行調(diào)查后，他得到了下面的數(shù)據(jù)表格（以班級為單位）

分別用數(shù)學(xué)關(guān)系式和圖形表示上述限制條件。若根據(jù)有關(guān)部門的規(guī)定，初中每人每年可收學(xué)費(fèi)1600元，高中每人每年可收學(xué)費(fèi)2700元。那么開設(shè)初中班和高中班多少個？每年收費(fèi)的學(xué)費(fèi)總額最多？

學(xué)段班級學(xué)生數(shù)配備教師數(shù)初中45226／班2／人高中40354／班2／人目前三十三頁\總數(shù)五十頁\編于七點(diǎn)把上面四個不等式合在一起，得到y(tǒng)x2030402030o

另外，開設(shè)的班級不能為負(fù)，則x≥0，y≥0。而由于資金限制，26x＋54y＋2×2x＋2×3y≤1200

解：設(shè)開設(shè)初中班x個，高中班y個。因辦學(xué)規(guī)模以20～30個班為宜，所以，20≤x＋y≤30目前三十四頁\總數(shù)五十頁\編于七點(diǎn)yx2030402030o

由圖可以看出，當(dāng)直線Z＝7.2x＋10.8y經(jīng)過可行域上的點(diǎn)M時，截距最大，即Z最大。

設(shè)收取的學(xué)費(fèi)總額為Z萬元，則目標(biāo)函數(shù)Z＝0.16×45x＋0.27×40y＝7.2x＋10.8y。Z＝7.2x＋10.8y變形為它表示斜率為的直線系，Z與這條直線的截距有關(guān)。M易求得M（20，10），則Zmax＝7.2x＋10.8y＝252故開設(shè)20個初中班和10個高中班，收取的學(xué)費(fèi)最多，為252萬元。目前三十五頁\總數(shù)五十頁\編于七點(diǎn)咖啡館配制兩種飲料．甲種飲料每杯含奶粉9g、咖啡4g、糖3g,乙種飲料每杯含奶粉4g、咖啡5g、糖10g．已知每天原料的使用限額為奶粉3600g，咖啡2000g糖3000g,如果甲種飲料每杯能獲利0.7元，乙種飲料每杯能獲利1.2元，每天在原料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種飲料各多少杯能獲利最大？

解：將已知數(shù)據(jù)列為下表：

3

原料每配制1杯飲料消耗的原料奶粉(g)咖啡(g)糖(g)甲種飲料乙種飲料943451.2原料限額360020003000利潤(元)0.71.2xy設(shè)每天應(yīng)配制甲種飲料x杯，乙種飲料y杯，則目標(biāo)函數(shù)為：z=0.7x+1.2y鞏固練習(xí)一目前三十六頁\總數(shù)五十頁\編于七點(diǎn)解:設(shè)每天應(yīng)配制甲種飲料x杯，乙種飲料y杯，則把直線l向右上方平移至l1的位置時，直線經(jīng)過可行域上的點(diǎn)C，且與原點(diǎn)距離最大，此時z=0.7x+1.2y取最大值解方程組得點(diǎn)C的坐標(biāo)為（200，240）_0_9x+4y=3600_C(200,240)_4x+5y=2000_3x+10y=3000_7x+12y=0_400_400_300_500_1000_900_0_x_y目標(biāo)函數(shù)為：z=0.7x+1.2y答:每天配制甲種飲料200杯,乙種飲料240杯可獲取最大利潤.小結(jié)作出可行域：目標(biāo)函數(shù)為：z=0.7x+1.2y作直線l:0.7x+1.2y=0，目前三十七頁\總數(shù)五十頁\編于七點(diǎn)鞏固練習(xí)二

某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入分別為3000元、2000元，甲、乙產(chǎn)品都需要在A、B兩種設(shè)備上加工，在每臺A、B上加工1件甲所需工時分別為1h、2h，在每臺A、B上加工1件乙所需工時分別為2h、1h，A、B兩種設(shè)備每月有效使用臺數(shù)分別為400h和500h。如何安排生產(chǎn)可使收入最大？

設(shè)每月生產(chǎn)甲產(chǎn)品x件，生產(chǎn)乙產(chǎn)品y件，每月收入為z，目標(biāo)函數(shù)為Z＝3x＋2y，滿足的條件是目前