簡單的線性規(guī)劃問題最新版本

1、3.3.2 簡單的線性規(guī)劃問題簡單的線性規(guī)劃問題(1)一一.問題情境問題情境1.在同一坐標(biāo)系上作出下列直線，你能得到什么結(jié)論？在同一坐標(biāo)系上作出下列直線，你能得到什么結(jié)論？2x+y=0;2x+y=1;2x+y=-3;2x+y=4;2x+y=7.02)0(2:平平行行的的直直線線與與形形如如結(jié)結(jié)論論 yxttyxxYo問題：你知道問題：你知道2x+y=t中中t的幾何意義么？的幾何意義么？2x-y=t中中t的的幾何意義呢？幾何意義呢？55x=1x-4y+3=03x+5y-25=01ABCC: (1, 4.4)A: (5, 2)B: (1, 1)Oxy問題問題1 1：x 有無最大（?。┲担坑袩o最大（

2、?。┲担繂栴}問題2 2：y 有無最大（小）值？有無最大（小）值？問題問題3 3：z=2z=2x+y 有無最大（?。┲?？有無最大（?。┲?？1255334xyxyx2.作出下列不作出下列不等式組的所表等式組的所表示的平面區(qū)域示的平面區(qū)域二二.提出問題提出問題把上面的問題綜合起來把上面的問題綜合起來:1255334xyxyx設(shè)設(shè)z=2x+y,求滿足求滿足時(shí)時(shí),求求z的最大值和最小值的最大值和最小值.55x=1x-4y+3=03x+5y-25=01ABCC: (1, 4.4)A: (5, 2)B: (1, 1)Oxy.1255334. 1所表示的區(qū)域所表示的區(qū)域先作出先作出 xyxyx02 yx02:

3、0. 20yxlz作直線令Rzzyxll,2:. 30直線平行的作一組與直線直線直線L L越往上平越往上平移移,z,z隨之增大隨之增大. .以經(jīng)過點(diǎn)以經(jīng)過點(diǎn)A(5,2)A(5,2)的的直線所對(duì)應(yīng)的直線所對(duì)應(yīng)的t t值值最大最大; ;經(jīng)過點(diǎn)經(jīng)過點(diǎn)B(1,1)B(1,1)的直線所對(duì)應(yīng)的的直線所對(duì)應(yīng)的t t值最小值最小. .3112,12252minmax ZZ 可以通過比較可行域頂點(diǎn)的可以通過比較可行域頂點(diǎn)的目標(biāo)函數(shù)值大小得到。目標(biāo)函數(shù)值大小得到。思考：還可以運(yùn)用怎樣的方法得到目標(biāo)函數(shù)思考：還可以運(yùn)用怎樣的方法得到目標(biāo)函數(shù)的最大、最小值？的最大、最小值？線性規(guī)劃問題：設(shè)z=2x+y，式中變量滿足下

4、列條件： 求z的最大值與最小值。 1255334xyxyx 目標(biāo)函數(shù)目標(biāo)函數(shù)（線性目標(biāo)函數(shù)）（線性目標(biāo)函數(shù)）線性約線性約束條件束條件象這樣對(duì)象這樣對(duì)變量變量x,yx,y的約束條的約束條件稱為件稱為線線性約束性約束條條件件Z=2x+yZ=2x+y稱為目標(biāo)函數(shù)稱為目標(biāo)函數(shù),( ,(因因這里目標(biāo)函數(shù)為關(guān)于這里目標(biāo)函數(shù)為關(guān)于x,yx,y的的一次式一次式, ,又稱為又稱為線性目標(biāo)函線性目標(biāo)函數(shù)數(shù)線性規(guī)劃定義線性規(guī)劃定義線性規(guī)劃：線性規(guī)劃：求線性目標(biāo)函數(shù)在線性約束條件下的最求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題 可行解可行解 ：滿足線

5、性約束條滿足線性約束條件的解件的解(x，y)叫可行解；叫可行解； 可行域可行域 ：由所有可行解組由所有可行解組成的集合叫做可行域；成的集合叫做可行域； 最優(yōu)解最優(yōu)解 ：使目標(biāo)函數(shù)取得使目標(biāo)函數(shù)取得最大或最小值的可行解叫最大或最小值的可行解叫線性規(guī)劃問題的最優(yōu)解。線性規(guī)劃問題的最優(yōu)解。 可行域可行域2x+y=32x+y=12(1,1)(5,2)1255334xyxyx設(shè)設(shè)z=2x+y,求滿足求滿足時(shí)時(shí),求求z的最大值和最小值的最大值和最小值.線性目線性目標(biāo)函數(shù)標(biāo)函數(shù)線性約線性約束條件束條件線性規(guī)線性規(guī)劃問題劃問題任何一個(gè)滿足任何一個(gè)滿足不等式組的不等式組的（x,yx,y）可行解可行解可行域可行域

6、所有的所有的最優(yōu)解最優(yōu)解目標(biāo)函數(shù)所表目標(biāo)函數(shù)所表示的幾何意義示的幾何意義在在y軸上軸上的截距或與其的截距或與其相關(guān)。相關(guān)。線性規(guī)劃相關(guān)名稱線性規(guī)劃相關(guān)名稱求線性規(guī)劃最優(yōu)解的方法：求線性規(guī)劃最優(yōu)解的方法：圖解法圖解法圖解法圖解法的一般步驟：的一般步驟：第一步：第一步：畫畫：在平面直角坐標(biāo)系中畫出可行域；：在平面直角坐標(biāo)系中畫出可行域；第二步：第二步：移移：平移初始直線：平移初始直線L0，在可行域內(nèi)找到最優(yōu)，在可行域內(nèi)找到最優(yōu)解所對(duì)應(yīng)的點(diǎn)；解所對(duì)應(yīng)的點(diǎn)；第三步：第三步：求求：通過解方程組求出最優(yōu)解。：通過解方程組求出最優(yōu)解。整理ppt10線性規(guī)劃例例1 解下列線性規(guī)劃問題： 求z=2x+y的最大值

7、和最小值，使式中x、y滿足下列條件：11yyxxy2x+y=02x+y=-32x+y=3答案：當(dāng)x=-1,y=-1時(shí)，z=2x+y有最小值3.當(dāng)x=2,y=-1時(shí)，z=2x+y有最大值3. 也可以通過比較可行域頂點(diǎn)也可以通過比較可行域頂點(diǎn)的目標(biāo)函數(shù)值大小得到。的目標(biāo)函數(shù)值大小得到。例例2.2.營養(yǎng)學(xué)家指出營養(yǎng)學(xué)家指出, ,成人良好的日常飲食應(yīng)該至少提供成人良好的日常飲食應(yīng)該至少提供0.075kg0.075kg的碳水化合物的碳水化合物,0.06kg,0.06kg的蛋白質(zhì)的蛋白質(zhì),0.06kg,0.06kg的脂肪的脂肪.1kg.1kg食物食物A A含有含有0.105kg0.105kg碳水化合物碳水

8、化合物,0.07 kg,0.07 kg的蛋白質(zhì)的蛋白質(zhì), 0.14kg, 0.14kg的脂肪的脂肪, ,花費(fèi)花費(fèi)2828元元; ;而而1kg1kg食物食物B B含有含有0.105kg0.105kg碳水化合物碳水化合物,0.14 kg,0.14 kg的蛋白質(zhì)的蛋白質(zhì), , 0.07kg0.07kg的脂肪的脂肪, ,花費(fèi)花費(fèi)2121元元. .為了滿足營養(yǎng)學(xué)家指出的日常飲食要為了滿足營養(yǎng)學(xué)家指出的日常飲食要求求, ,同時(shí)使花費(fèi)最低同時(shí)使花費(fèi)最低, ,需要同時(shí)食用食物需要同時(shí)食用食物A A和食物和食物B B多少多少kg?kg?分析分析: :將已知數(shù)據(jù)列成下表將已知數(shù)據(jù)列成下表0.070.140.105

9、0.140.070.105BA脂肪脂肪/kg蛋白質(zhì)蛋白質(zhì)/kg碳水化合物碳水化合物/kg食物食物/kg解解:設(shè)每天食用設(shè)每天食用xkg食物食物A, ykg食物食物B, 總成本為總成本為z元元. 那么那么x,y滿足的約束條件是滿足的約束條件是:0 1050 1050 0750 070 140 060 140 070 06 00.x.y.,.x.y.,.x.y.,x,y.目標(biāo)函數(shù)為目標(biāo)函數(shù)為z=28x+21y . 0, 0 , 6714, 6147, 577yxyxyxyx二元一次不等式組二元一次不等式組等價(jià)于等價(jià)于作出二元一次不等式組作出二元一次不等式組所所表示的平面區(qū)域，即可行域表示的平面區(qū)域

10、，即可行域. . 775xy1476xy7146xy42821321zzxyyx 可化為34 這是斜率為這是斜率為 、在、在y軸上的截距為軸上的截距為 的一組平行直線的一組平行直線. .21zxyo737475761737576由圖知由圖知,當(dāng)直線當(dāng)直線經(jīng)過可行域上點(diǎn)經(jīng)過可行域上點(diǎn)M時(shí)時(shí),截距截距21z最小最小, 即即z最小最小.解方程組解方程組7751476xy,xy, 得得M的坐標(biāo)為的坐標(biāo)為14()77,.所以所以zmin=28x+21y=16.答：每天食用食物答：每天食用食物A約為約為143g，食物，食物B約約571g，能夠滿足日常，能夠滿足日常飲食要求，又使花費(fèi)最低，最低成本為飲食要求

11、，又使花費(fèi)最低，最低成本為16元元.4321zyx 775xy1476xy7146xyxyo737475761737576M法法2 2：算線性目標(biāo)函數(shù)的最大（?。┲担核憔€性目標(biāo)函數(shù)的最大（小）值一般一般在可行域的頂點(diǎn)處取在可行域的頂點(diǎn)處取得得. .法法1 1：移在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的：移在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線； 解線性規(guī)劃應(yīng)用題的一般步驟解線性規(guī)劃應(yīng)用題的一般步驟：2）列列：列出約束條件和目標(biāo)函數(shù)：列出約束條件和目標(biāo)函數(shù)3）解解：利用：利用圖解法圖解

12、法尋求最優(yōu)解對(duì)應(yīng)的點(diǎn)尋求最優(yōu)解對(duì)應(yīng)的點(diǎn)4）聯(lián)聯(lián)：聯(lián)立方程組解出最優(yōu)解聯(lián)立方程組解出最優(yōu)解1）設(shè)設(shè)：設(shè)好變量設(shè)好變量5) 答答：回答實(shí)際問題：回答實(shí)際問題畫出線性約束條件所表示的可行域，畫圖力保準(zhǔn)確；畫出線性約束條件所表示的可行域，畫圖力保準(zhǔn)確；5315,1,53.xyyxxy 351ABxyo5315xy1yx53xy(1.5,2.5)(-2,-1)Z max=17Z min=-11求求z=3x+5y的最大值和最小值的最大值和最小值,使使x、y滿足約束條件滿足約束條件C3x+5y=0練習(xí)練習(xí)351ABxyo5315xy1yx53xy(1.5,2.5)(-2,-1)C變式變式1.若求若求z=x-

13、2y的最大值和最小值呢？的最大值和最小值呢？1222zz xyyx -z/2最小時(shí)，最小時(shí)，z最大最大 -z/2最大時(shí)，最大時(shí)，z最小最小故過點(diǎn)故過點(diǎn)C時(shí)，時(shí)，z最大，最大， 過點(diǎn)過點(diǎn)B時(shí)，時(shí)，z最小最小.zmax=3zmin=-3.5練習(xí)練習(xí)變式變式2.使使z=x-y取得最小值的最優(yōu)解有幾個(gè)取得最小值的最優(yōu)解有幾個(gè)?5315,1,53.xyyxxy 注：一般，目標(biāo)函數(shù)的最優(yōu)解是唯一的（在可行域的頂點(diǎn)處取得）注：一般，目標(biāo)函數(shù)的最優(yōu)解是唯一的（在可行域的頂點(diǎn)處取得），有時(shí)是不唯一的（在可行域的邊界取得）。，有時(shí)是不唯一的（在可行域的邊界取得）。02 yx0 yx練習(xí)練習(xí)2：已知已知(1)求求z=2x+y的最優(yōu)解。的最優(yōu)解。(2)求求z=2x-y的最優(yōu)解。的最優(yōu)解。01y01-yx0y-x整理ppt18法法2 2：算線性目標(biāo)函數(shù)的最大（?。┲担核憔€性目標(biāo)函數(shù)的最大（?。┲狄话阋话阍诳尚杏虻捻旤c(diǎn)處取在可行域的頂點(diǎn)處取得得. .法法1 1：移在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的：移在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；方法找