簡(jiǎn)單線性規(guī)劃專題

1、例例1 作不等式組作不等式組 表示的平面區(qū)域表示的平面區(qū)域02022yxyxy0 1 2 3 x 2 112解：解：022 yx不等式不等式 表示表示的區(qū)域是直線的區(qū)域是直線 左下半平面區(qū)域并且包括直左下半平面區(qū)域并且包括直線線 ；022 yx022 yx022 yx不等式不等式 表示表示的區(qū)域是直線的區(qū)域是直線 右下半平面區(qū)域并且包括直右下半平面區(qū)域并且包括直線線 ；02 yx02 yx02 yx所以黑色陰影部分即所以黑色陰影部分即為所求。為所求。02 yx例例2 2 畫出不等式組畫出不等式組 表示的平面區(qū)域。表示的平面區(qū)域。xyox-4y=-33x+5y=25x=1問題：?jiǎn)栴}：2 2+ +

2、有無(wú)最大有無(wú)最大( (小小) )值？值？cab3x+5y25x- -4y- -3x1 設(shè)z z2 2+ +, ,式中變量、滿足下列條件 ， 求的最大值和最小值。xyox-4y=-3x=1c3x+5y253x+5y25x-4y-3x-4y-3x1x1b3x+5y=25問題問題 1: 將z z2 2+ +變形?問題問題 2: z幾何意義是_。斜率為斜率為-2的直線在的直線在y軸上的截距軸上的截距 則直線 l：2 2+ +=z=z是一簇與 l0平行的直線,故直線 l 可通過平移直線l0而得，當(dāng)直線往右上方平移時(shí)z 逐漸增大： 當(dāng)l 過點(diǎn)b(1,1)時(shí),z最小,即zmin=3 當(dāng)l 過點(diǎn)a(5,2)時(shí)

3、,z最大,即 zmax25+212 。 析析: 作直線l0 ：2 2+ +=0 ,=0 , -2-2+ z+ z設(shè)z z2 2+ +, ,式中變量、滿足下列條件，求的最大值和最小值。xyox=1cb3x+ +5y25x- -4y- -3x1x-4y=-3x-4y=-33x+5y=253x+5y=25最優(yōu)解最優(yōu)解：使使目標(biāo)函數(shù)達(dá)到目標(biāo)函數(shù)達(dá)到最大值最大值或或 最小值最小值 的可的可 行行 解。解。 線性約束條件：線性約束條件：約束條件中均為關(guān)于約束條件中均為關(guān)于x、y的一次不等式或方程。的一次不等式或方程。有關(guān)概念有關(guān)概念約束條件約束條件：由、的不等式（方程）構(gòu)成的不等式組。由、的不等式（方程）

4、構(gòu)成的不等式組。目標(biāo)函數(shù)：目標(biāo)函數(shù)：欲求最值的關(guān)于欲求最值的關(guān)于x、y的一次解析式的一次解析式。線性目標(biāo)函數(shù)：線性目標(biāo)函數(shù)：欲求最值的解析式是關(guān)于欲求最值的解析式是關(guān)于x、y的一次解析式。的一次解析式。線性規(guī)劃：線性規(guī)劃：求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值。可行解：可行解：滿足線性約束條件的解（滿足線性約束條件的解（x，y）。）。 可行域：可行域：所有可行解組成的集合。所有可行解組成的集合。xyox-4y=-3x=1cb3x+5y=25 設(shè)z2+,式中變量、 滿足下列條件 ， 求的最大值和最小值。3x+5y25x-4y-3x1若題設(shè)更換

5、若題設(shè)更換 z2xy, 其中其中x、y滿足下列條件滿足下列條件 求的最大值和最小值。求的最大值和最小值。b cxyox4y=33x+5y=25x=13x+5y25x 4y3x1解：作出可行域如圖解：作出可行域如圖：當(dāng)當(dāng)0時(shí)，設(shè)直線時(shí)，設(shè)直線 l l0 0：2xy0 當(dāng)當(dāng)l l0 0經(jīng)過可行域上點(diǎn)經(jīng)過可行域上點(diǎn)a時(shí)，時(shí)，z 最小，即最小，即最大。最大。 當(dāng)當(dāng)l l0 0經(jīng)過可行域上點(diǎn)經(jīng)過可行域上點(diǎn)c時(shí)，時(shí)，最大，即最大，即最小。最小。由由 得得a點(diǎn)坐標(biāo)點(diǎn)坐標(biāo)_； x4y3 3x5y25由由 得得c點(diǎn)坐標(biāo)點(diǎn)坐標(biāo)_； x=1 3x5y25zmax2528 zmin214.4 2.4(5,2)(5,2

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

7、 ，設(shè)，設(shè)zaxy (a0)， 若若 取得最大值時(shí)，對(duì)應(yīng)點(diǎn)有無(wú)數(shù)個(gè)，求取得最大值時(shí)，對(duì)應(yīng)點(diǎn)有無(wú)數(shù)個(gè)，求a 的值。的值。3x+5y=253x+5y25 x 4y3x1xyox-4y=-3x=1cb b解：解：當(dāng)直線當(dāng)直線 l l ：y ax z 與與直線重合時(shí)，有無(wú)數(shù)個(gè)點(diǎn)，使直線重合時(shí)，有無(wú)數(shù)個(gè)點(diǎn)，使函數(shù)值取得最大值，此時(shí)有：函數(shù)值取得最大值，此時(shí)有： k l l kac 535124 . 4 kack l l = -a53 -a = a =53例例3：滿足線性約束條件：滿足線性約束條件 的可行域中共有的可行域中共有 多少個(gè)整數(shù)解。多少個(gè)整數(shù)解。x+4y113x +y10 x0y01223314

8、455xy03x +y=10 x +4y=11解：解：由題意得可行域如圖由題意得可行域如圖: 由圖知滿足約束條件的由圖知滿足約束條件的可行域中的整點(diǎn)為可行域中的整點(diǎn)為(1,1)、(1,2)、(2,1)、(2,2) 故有四個(gè)整點(diǎn)可行解故有四個(gè)整點(diǎ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)c3x+5y=0變式變式1.若求若求z=x-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=-