332第1課時簡單的線性規(guī)劃問題

1、3.3.2 簡單的線性規(guī)劃問題第1課時 簡單的線性規(guī)劃問題 1.1.了解線性規(guī)劃的意義及線性約束條件、線性目標函數(shù)、了解線性規(guī)劃的意義及線性約束條件、線性目標函數(shù)、可行域、可行解等基本概念；可行域、可行解等基本概念；2.2.了解線性規(guī)劃問題的圖解法，并能解決一些簡單的問了解線性規(guī)劃問題的圖解法，并能解決一些簡單的問題題. .1.1.某工廠用某工廠用A A、B B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，每生產(chǎn)兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，每生產(chǎn)一件甲產(chǎn)品使用一件甲產(chǎn)品使用4 4個個A A配件耗時配件耗時1h1h，每生產(chǎn)一件乙產(chǎn)品使，每生產(chǎn)一件乙產(chǎn)品使用用4 4個個B B配件耗時配件耗時2h2h，該廠每天最多可

2、從配件廠獲得，該廠每天最多可從配件廠獲得1616個個A A配件和配件和1212個個B B配件，按每天工作配件，按每天工作8h8h計算，該廠所有可能的計算，該廠所有可能的日生產(chǎn)安排是什么？日生產(chǎn)安排是什么？(1)(1)設(shè)甲、乙兩種產(chǎn)品分設(shè)甲、乙兩種產(chǎn)品分別生產(chǎn)別生產(chǎn)x x、y y件，由已知件，由已知條件可得二元一次不等條件可得二元一次不等式組：式組：2841641200.xyxyxy ，將上面不等式組表示成平面上的區(qū)域?qū)⑸厦娌坏仁浇M表示成平面上的區(qū)域, ,區(qū)域內(nèi)所有坐標區(qū)域內(nèi)所有坐標為整數(shù)的點為整數(shù)的點 時時 , ,安排生產(chǎn)任務(wù)安排生產(chǎn)任務(wù) 都是有意義的都是有意義的. .( , )P x y,x

3、 yy0 x434828xy4x =3y簡單線性規(guī)劃問題及有關(guān)概念簡單線性規(guī)劃問題及有關(guān)概念 進一步，若生產(chǎn)一件甲種產(chǎn)品獲利進一步，若生產(chǎn)一件甲種產(chǎn)品獲利2 2萬元萬元, ,生產(chǎn)一生產(chǎn)一件乙種產(chǎn)品獲利件乙種產(chǎn)品獲利3 3萬元萬元, ,采用哪種生產(chǎn)安排利潤最大采用哪種生產(chǎn)安排利潤最大? ?設(shè)生產(chǎn)甲產(chǎn)品設(shè)生產(chǎn)甲產(chǎn)品x x件，乙產(chǎn)品件，乙產(chǎn)品y y件時，工廠獲得的利潤為件時，工廠獲得的利潤為z,z,則則z=2x+3y.z=2x+3y.上述問題就轉(zhuǎn)化為：當上述問題就轉(zhuǎn)化為：當x x、y y滿足不等式組并且為非滿足不等式組并且為非負整數(shù)時，負整數(shù)時，z z的最大值是多少？的最大值是多少？2223,333

4、3zzxyyxzy 把變形為,這是斜率為在 軸上的截距為 的直線,3Pzz當點在可允許的取值范圍內(nèi)變化時，求截距的最值,即可得 的最值.z當 變化時，可以得到一組互相平行的直線002:.3lyxl 故可先作出過原點的直線，再作 的平行線02:3lyx 0 x434828xy4x =3y(4,2)M233428zyxxxy 由圖可知當直線經(jīng)過直線與直線即即 的最大值為的最大值為2 43214.z z所以，每天生產(chǎn)甲產(chǎn)品所以，每天生產(chǎn)甲產(chǎn)品4 4件，乙產(chǎn)品件，乙產(chǎn)品2 2件時，工廠獲得最件時，工廠獲得最大利潤大利潤1414萬元萬元. .3z最大值為最大值為14.3的交點的交點(4,2)M時，截距時

5、，截距的值最大，的值最大，y y上述問題中，不等式組上述問題中，不等式組 是一組對變量是一組對變量 x x、y y的約束條件，這組約束條件都是關(guān)于的約束條件，這組約束條件都是關(guān)于x x、y y的一次不等式，所以又稱為線性約束條件的一次不等式，所以又稱為線性約束條件. .2841641200 xyxyxy ，1.1.線性約束條件線性約束條件 我們把要求最大值的函數(shù)我們把要求最大值的函數(shù)z=2x+3yz=2x+3y稱為稱為目標函目標函數(shù)數(shù). .又因為又因為z=2x+3yz=2x+3y是關(guān)于變量是關(guān)于變量x x、y y的一次解析式，的一次解析式，所以又稱為所以又稱為線性目標函數(shù)線性目標函數(shù). . 2

6、.2.線性目標函數(shù)線性目標函數(shù)3.3.線性規(guī)劃線性規(guī)劃 一般一般的的，在線性約束條件下求線性目標函數(shù)，在線性約束條件下求線性目標函數(shù)的最大值或最小值問題，統(tǒng)稱為的最大值或最小值問題，統(tǒng)稱為線性規(guī)劃線性規(guī)劃問題問題. . 滿足線性約束條件的解滿足線性約束條件的解( (x,yx,y) )叫做叫做可行解可行解. . 由所有可行解組成的集合叫做由所有可行解組成的集合叫做可行域可行域. . 使目標函數(shù)取得最大值或最小值的可行解叫做這個使目標函數(shù)取得最大值或最小值的可行解叫做這個問題的問題的最優(yōu)解最優(yōu)解. .4.4.可行解、可行域、最優(yōu)解可行解、可行域、最優(yōu)解 （1 1）在上述問題中，如果每生產(chǎn)一件甲產(chǎn)品

7、）在上述問題中，如果每生產(chǎn)一件甲產(chǎn)品 獲利獲利3 3萬元，每生產(chǎn)一件乙產(chǎn)品獲利萬元，每生產(chǎn)一件乙產(chǎn)品獲利2 2萬元，萬元， 又當如何安排生產(chǎn)才能獲得最大利潤？又當如何安排生產(chǎn)才能獲得最大利潤？（2 2）由上述過程，你能得出最優(yōu)解與可行域之間的關(guān)）由上述過程，你能得出最優(yōu)解與可行域之間的關(guān)系嗎？系嗎？設(shè)生產(chǎn)甲產(chǎn)品設(shè)生產(chǎn)甲產(chǎn)品x x件乙產(chǎn)品件乙產(chǎn)品y y件時，工廠獲得的利潤為件時，工廠獲得的利潤為z,z,則則z=3x+2y.z=3x+2y.3332,2222zzxyyxzy 把變形為,這是斜率為在 軸上的截距為 的直線.03:2lyx Ox434828xy4x =3y(4,2)My322428zy

8、xxxy 由圖可知當直線經(jīng)過直線與2z最大值為最大值為8.的交點的交點(4,2)M時截距時截距的值最大，的值最大，即即 的最大值為的最大值為3 42216.z z所以，每天生產(chǎn)甲產(chǎn)品所以，每天生產(chǎn)甲產(chǎn)品4 4件，乙產(chǎn)品件，乙產(chǎn)品2 2件時，工廠獲得最件時，工廠獲得最大利潤大利潤1616萬元萬元. .（2 2）將目標函數(shù)）將目標函數(shù) 變形為變形為 將求將求 的的 最值問題轉(zhuǎn)化為求直線最值問題轉(zhuǎn)化為求直線 在在 軸上的截距軸上的截距 的最值問題；的最值問題；(0)z ax byb ,azyxbb zyzb 在確定約束條件和線性目標函數(shù)的前提下，在確定約束條件和線性目標函數(shù)的前提下， 用圖解法求最優(yōu)

9、解的步驟為：用圖解法求最優(yōu)解的步驟為：（1 1）在平面直角坐標系內(nèi)畫出可行域；）在平面直角坐標系內(nèi)畫出可行域；azyxbb （3 3）畫出直線）畫出直線=0axby 并平行移動，并平行移動，或最后經(jīng)過的點為最優(yōu)解；或最后經(jīng)過的點為最優(yōu)解；平移過程中最先平移過程中最先（4 4）求出最優(yōu)解并代入目標函數(shù)，從而求出目標函數(shù)的）求出最優(yōu)解并代入目標函數(shù)，從而求出目標函數(shù)的 最值最值. .簡單線性規(guī)劃問題的圖解方法簡單線性規(guī)劃問題的圖解方法 例例1 1 設(shè)設(shè) z2xy，式中變量式中變量x、 y滿足下列條件：滿足下列條件： 求求z z的最大值和最小值的最大值和最小值. .43,3525, 1, xyxyx

10、 分析：分析：作可行域，畫平行線，解方程組，求最值作可行域，畫平行線，解方程組，求最值. .42246 6yxOCAB B35250 xy 430 xy 1x 解：解：作出如圖所示的可行域，作出如圖所示的可行域， 0:20lxy作作0:20,lxy0/ / .ll及及當直線當直線 經(jīng)過點經(jīng)過點B B時，對應時，對應的的 最小，當直線最小，當直線 經(jīng)過經(jīng)過點點A A時，對應的時，對應的 最大最大. .lzlz1,(1,1),430.3525,(5,2).430.=2 1+1=3=2 5+2=12.xBxyxyAxyzz 最小值最大值由得由得，,解線性規(guī)劃問題的步驟：解線性規(guī)劃問題的步驟： （2

11、2）移：移：在線性目標函數(shù)所表示的一組平行線中，在線性目標函數(shù)所表示的一組平行線中， 利用平移的方法找出與可行域有公共點利用平移的方法找出與可行域有公共點 且縱截距最大或最小的直線；且縱截距最大或最小的直線； （3 3）求：求：通過解方程組求出最優(yōu)解；通過解方程組求出最優(yōu)解； （4 4）答：答：作出答案作出答案. . （1 1）畫：畫：畫出線性約束條件所表示的可行域；畫出線性約束條件所表示的可行域；最優(yōu)解一般在可行域的頂點處取得最優(yōu)解一般在可行域的頂點處取得43,2,3525,(0),1.xyx yxyzaxy axza 例已知滿足設(shè)若 取得最大值時，對應點有無數(shù)個，求 的值分析：分析：對應無

12、數(shù)個點，即直線與邊界線重合時對應無數(shù)個點，即直線與邊界線重合時. . 作出可行域，結(jié)合圖形，看直線作出可行域，結(jié)合圖形，看直線 與哪條邊界線重合時，可取得最大值與哪條邊界線重合時，可取得最大值. .:lyaxz 解：解：當直線當直線 與邊界與邊界 線重合時，有無數(shù)個點，線重合時，有無數(shù)個點， 使函數(shù)值取得最大值，使函數(shù)值取得最大值，33,.553.5AClkkaa 即:lyaxz .lACkk 此時有此時有yxOCB1x 43xy 3525xy且且z2x4y的最小值為的最小值為6 6，則常數(shù)，則常數(shù)k等于等于( ).( ).1. 1. 已知已知 x、y滿足滿足50,3,0,xyxxyk A.

13、2 B. 9 C. 3 10 D. 0D D求求 的的最大值和最小值最大值和最小值. .2.2.已知已知 滿足滿足1,53,5315.yxxyxy , x y2zxy12.22由得zzxyyx解：解：作出如圖所示的可行域，作出如圖所示的可行域，0:20,lxy作并平行移動,351xO O5315xy1yx53xyB(1.5,2.5)B(1.5,2.5)A A(-2,-1)Cy20 xy當直線當直線l經(jīng)過點經(jīng)過點B B時，對應時，對應的的z z最小，當直線最小，當直線l經(jīng)過經(jīng)過C C時，對應的時，對應的z z最大最大. .zz最小值最小值=1.5-2=1.5-22.5=-3.52.5=-3.5z z最大值最大值=3-0=3.=3-0=3.2.2.線性目標函數(shù)的最值的圖解法及其步驟線性目標函數(shù)的最值的圖解法及其步驟. .最優(yōu)解在可