第2課簡單線性規(guī)劃ppt課件

1、xyo復(fù)習(xí)回顧：復(fù)習(xí)回顧：設(shè)設(shè)x、y滿足條件滿足條件5x + 6y 30y 3xy 1畫出以上不等式組所表示的范圍畫出以上不等式組所表示的范圍.5x + 6y 30y 3xy 1O3624引例：引例：設(shè)設(shè)x、y滿足條件滿足條件5x + 6y 30y 3xy 1畫出以上不等式組所表示的范圍畫出以上不等式組所表示的范圍.求求z = 2x + y 的最小值和最大值的最小值和最大值.考慮：考慮：x=1,y=2時(shí)時(shí)z=_ x=2,y=3時(shí)時(shí)z=_式子式子y=-2x+z中中z的幾何意義是什么？的幾何意義是什么？47Z表示該直線的縱截距表示該直線的縱截距這個(gè)問題可轉(zhuǎn)化為：當(dāng)點(diǎn)這個(gè)問題可轉(zhuǎn)化為：當(dāng)點(diǎn) (x ,

2、 y) 在公共區(qū)域內(nèi)在公共區(qū)域內(nèi)運(yùn)動時(shí)，求運(yùn)動時(shí)，求 y = -2x + z中截距中截距z的最小值和最大的最小值和最大值值.O3624如圖，令如圖，令z=0得直線得直線L0：y=-2x,平行移動平行移動直線直線L0與公共區(qū)域首與公共區(qū)域首先相交于頂點(diǎn)先相交于頂點(diǎn)A(1/3 , 1)，此時(shí)所對應(yīng)的，此時(shí)所對應(yīng)的z值最小；值最?。籓3624A直線直線L0繼續(xù)向上平移，繼續(xù)向上平移，z值繼續(xù)增大，最后相值繼續(xù)增大，最后相交于頂點(diǎn)交于頂點(diǎn)B(24/5 , 1)，此時(shí)所對應(yīng)的，此時(shí)所對應(yīng)的z值最大；值最大；故故 Zmax=224/5+1= 53/5故故 Zmin=21/3+1= 5/3 BL0 由由x，

3、y 的不等式的不等式(或方程或方程)組成的不等式組稱為組成的不等式組稱為x，y 的約束條件。的約束條件。 關(guān)于關(guān)于x，y 的一次不等式或方程組成的不等式組稱為的一次不等式或方程組成的不等式組稱為x，y 的線性約束條件。的線性約束條件。 欲達(dá)到最大值或最小值所涉及的變量欲達(dá)到最大值或最小值所涉及的變量x，y 的解析式的解析式稱為目標(biāo)函數(shù)。稱為目標(biāo)函數(shù)。 關(guān)于關(guān)于x，y 的一次目標(biāo)函數(shù)稱為線性目標(biāo)函數(shù)。的一次目標(biāo)函數(shù)稱為線性目標(biāo)函數(shù)。 求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值問題稱為線性規(guī)劃問題。值問題稱為線性規(guī)劃問題。 滿足線性約束條件的解滿足線

4、性約束條件的解x，y稱為可行解。稱為可行解。 所有可行解組成的集合稱為可行域。所有可行解組成的集合稱為可行域。 使目標(biāo)函數(shù)取得最大值或最小值的可行解稱為最優(yōu)解。使目標(biāo)函數(shù)取得最大值或最小值的可行解稱為最優(yōu)解。1255334xyxyx設(shè)設(shè)z=2x+y,求滿足求滿足時(shí)時(shí),求求z的最大值和最小值的最大值和最小值.線性目線性目標(biāo)函數(shù)標(biāo)函數(shù)線性約線性約束條件束條件線性規(guī)線性規(guī)劃問題劃問題任何一個(gè)滿足任何一個(gè)滿足不等式組的不等式組的x,yx,y）可行解可行解可行域可行域所有的所有的最優(yōu)解最優(yōu)解目標(biāo)函數(shù)所目標(biāo)函數(shù)所表示的幾何表示的幾何意義意義在在y軸上的截軸上的截距或其相反距或其相反數(shù)。數(shù)。9解線性規(guī)劃問題

5、的步驟：解線性規(guī)劃問題的步驟： 2. 2.畫：畫出線性約束條件所表示的可行域；畫：畫出線性約束條件所表示的可行域； 3. 3.移：在線性目標(biāo)函數(shù)所表示的一組平行線移：在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；且縱截距最大或最小的直線； 4. 4.求：通過解方程組求出最優(yōu)解；求：通過解方程組求出最優(yōu)解； 5. 5.答：作出答案。答：作出答案。 1. 1.找找: : 找出線性約束條件、目標(biāo)函數(shù)；找出線性約束條件、目標(biāo)函數(shù)； 例1已知 , z=2x+y，求z的最大值和最小值。1255334xyxyxxy123

6、4567O-1-1123456BACx=1x-4y+3=03x+5y-25=00l1l2l解：不等式組表示的平面區(qū)域如圖所示：所以，122523112maxminzzA(5,2), B(1,1),。)522,1(C過A(5,2)時(shí)，z的值最大，的值最小，當(dāng)0l0l過B(1,1)時(shí)，由圖可知,當(dāng)平移 使之與平面區(qū)域有公共點(diǎn),0lx2y： =作直線 0l分析：目標(biāo)函數(shù)變形為zxy2121最小截距為過A(5,2)的直線2l1l2l53952221minz1225maxzx=1AC最大截距為過的直線1l)522, 1(C變式1： 若改為求z=x-2y的最大值、最小值呢？y1234567O-1-1123

7、456x3x+5y-25=0Bx-4y+3=00l1255334xyxyxy1234567O-1-1123456變式2 求z=3x+5y的最大值、最小值呢？解：不等式組表示的平面區(qū)域如圖所示：所以，25255381513maxminzz作斜率為的直線，：0y53xzl53BACx3x+5y-25=0 x-4y+3=0l由圖可知,當(dāng)?shù)闹底钚?，過B(1,1)時(shí)，z的值最大， 當(dāng) 過 時(shí)， l)522, 1 (),2 , 5(CA25522513zmax或0l1lx=12l1255334xyxyx5 5y yX X0 01 12 23 34 46 67 71 12 23 34 45 5x-4y+3=

8、0 x-4y+3=03x+5y-25=03x+5y-25=0 x=1x=1，求，求z的最大值和最小值的最大值和最小值.2x-y=02x-y=0代入點(diǎn)代入點(diǎn)A A得最大值為得最大值為 8 8 代入點(diǎn)代入點(diǎn)C C得最小值為得最小值為 . .125-3X+5y 253X+5y 25 練習(xí)練習(xí) . . 設(shè)設(shè)z=2xz=2xy y，變量，變量x x、y y滿足下列條滿足下列條件件 X-4y -3X-4y -3X 1X 1 A5，2）B1,1）C1，4.4）歸納小結(jié)歸納小結(jié)1.1.在線性約束條件下求目標(biāo)函數(shù)的最大在線性約束條件下求目標(biāo)函數(shù)的最大值或最小值，是一種數(shù)形結(jié)合的數(shù)學(xué)思值或最小值，是一種數(shù)形結(jié)合的

9、數(shù)學(xué)思想，它將目標(biāo)函數(shù)的最值問題轉(zhuǎn)化為動想，它將目標(biāo)函數(shù)的最值問題轉(zhuǎn)化為動直線在直線在y y軸上的截距的最值問題來解決軸上的截距的最值問題來解決. .2.2.對于直線對于直線l l：z zAxAxBy(A0)By(A0)若若B B0,0,則當(dāng)直線則當(dāng)直線l l在在y y軸上的截距最大軸上的截距最大( (小小) )時(shí)，時(shí)，z z取最大取最大( (小小) )值；值；若若B B0 0，則當(dāng)直線，則當(dāng)直線l l在在y y軸上的截距最大軸上的截距最大( (小小) )時(shí)，時(shí)，z z取最小取最小( (大大) )值值. . 注意注意1.1.正確列出變量的不等關(guān)系式正確列出變量的不等關(guān)系式, ,準(zhǔn)確準(zhǔn)確作出可行域是解決目標(biāo)函數(shù)最值的作出可行域是解決目標(biāo)函數(shù)最值的關(guān)健關(guān)健2.2.把目標(biāo)函數(shù)轉(zhuǎn)化為某一直線把目標(biāo)函數(shù)轉(zhuǎn)化為某一直線, ,其斜其斜率與可行域邊界所在直線斜率的大率與可行域邊界所在直線斜率的大小關(guān)系一定要弄清楚小關(guān)系一定要弄清楚. .3.3.線性目標(biāo)函數(shù)的最值一般都是在線性目標(biāo)函數(shù)的最值一般都是在可行域的頂點(diǎn)或邊界取得可行域的頂點(diǎn)或邊界取得. .作業(yè)：設(shè)作業(yè)：設(shè) x、y 滿足約束條件滿足約束條件- 4x + 3y 124x + 3y 36x - 3y - 4 求目標(biāo)函數(shù)求目標(biāo)函數(shù) z = 2x + 3y 的最值的最值. 求目標(biāo)函數(shù)求目標(biāo)函數(shù) z =