簡(jiǎn)單的線性規(guī)劃問題復(fù)習(xí)

1、簡(jiǎn)單的線性規(guī)劃問簡(jiǎn)單的線性規(guī)劃問題復(fù)習(xí)題復(fù)習(xí)xyo1二元一次不等式表示的平面區(qū)域(1)一般地，在平面直角坐標(biāo)系中，一般地，在平面直角坐標(biāo)系中，二元一次不等式二元一次不等式 AxByC0 表示直線表示直線 AxByC0 某一側(cè)所有點(diǎn)組成的平面區(qū)域，不含某一側(cè)所有點(diǎn)組成的平面區(qū)域，不含邊界線邊界線不等式不等式 AxByC0 所表示的平面區(qū)域包括邊界線所表示的平面區(qū)域包括邊界線(2)對(duì)于直線對(duì)于直線 AxByC0 同一側(cè)同一側(cè)的所有點(diǎn)的所有點(diǎn)(x，y)，使得，使得 AxByC 的值的的值的符號(hào)相同符號(hào)相同，也就是說位于同一平面區(qū)域內(nèi)的點(diǎn)，也就是說位于同一平面區(qū)域內(nèi)的點(diǎn)，若其坐標(biāo)適合若其坐標(biāo)適合 Ax

2、ByC0，則位于另一個(gè)平面區(qū)域內(nèi)的點(diǎn)，其，則位于另一個(gè)平面區(qū)域內(nèi)的點(diǎn)，其坐標(biāo)適合坐標(biāo)適合 AxByC0(或或 AxByC0)所表示的區(qū)域所表示的區(qū)域直線定界，特殊點(diǎn)定域直線定界，特殊點(diǎn)定域2線性規(guī)劃(1)線性約束條件：不等式組是一組對(duì)變量 x，y 的約束條件，由于這組約束條件都是關(guān)于 x，y 的一次不等式，所以又可稱其為線性約束條件(2)目標(biāo)函數(shù)：zAxBy 是欲達(dá)到最大值或最小值所涉及的變量 x，y 的解析式，我們把它稱為目標(biāo)函數(shù)(3)線性目標(biāo)函數(shù)：由于 zAxBy 是關(guān)于 x，y 的一次解析式，所以又可叫做線性目標(biāo)函數(shù)(4)可行解：滿足線性約束條件的解(x，y)叫做可行解，(5)可行域：由

3、所有可行解組成的集合叫做可行域(6)最優(yōu)解：若可行解(x1，y1)和(x2，y2)分別使目標(biāo)函數(shù)取得最大值和最小值，它們都叫做這個(gè)問題的最優(yōu)解(7)一般地，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題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)解 2xy60，3不等式組 xy30，所表示的平面區(qū)域的面積為_. y24若點(diǎn)(1,3)和點(diǎn)(

4、4，2)在直線 2xym0 的兩側(cè)，則m 的取值范圍是_.5m101，求，求z的最大值和最小值的最大值和最小值.y yX X0 01 12 23 34 45 56 67 71 12 23 34 45 5x-4y+3=0 x-4y+3=03x+5y-25=03x+5y-25=0 x=1x=1 例例1.1.設(shè)設(shè)z=2xz=2xy y，變量，變量x x、y y滿足下列條件滿足下列條件 X-4y -3X-4y -33X+5y3X+5y2525X 1X 15 5y yX X0 01 12 23 34 46 67 71 12 23 34 45 5x-4y+3=0 x-4y+3=03x+5y-25=03x+

5、5y-25=0 x=1x=1，求，求z的最大值和最小值的最大值和最小值.2x-y=02x-y=0代入點(diǎn)代入點(diǎn)B B得最大為得最大為8 8，代入點(diǎn)代入點(diǎn)A A得得最小值為最小值為 . .125-3X+5y 253X+5y 25 例例1. 1. 設(shè)設(shè)z=2xz=2xy y，變量，變量x x、y y滿足下列條滿足下列條件件 X-4y -3X-4y -3X 1X 1A（1，4.4） B（5，,2）C（1,1）某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成A、B、C三種規(guī)格，三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)示每張鋼板可同時(shí)截得三種規(guī)示 ：格的小鋼板的塊數(shù)如下表所格的小鋼板

6、的塊數(shù)如下表所解：解：設(shè)需截第一種鋼板設(shè)需截第一種鋼板x張，第二種鋼板張，第二種鋼板y張，張，鋼板鋼板總總張數(shù)為張數(shù)為Z則則,規(guī)格類型規(guī)格類型鋼板類型鋼板類型第一種鋼板第一種鋼板第二種鋼板第二種鋼板A規(guī)格規(guī)格B規(guī)格規(guī)格C規(guī)格規(guī)格2121312x+y15,x+2y18,x+3y27,x0y0 某顧客需要某顧客需要A,B,C三種規(guī)格的成品分別為三種規(guī)格的成品分別為15，18，27塊，塊，若你是若你是經(jīng)理經(jīng)理,問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張數(shù)最少數(shù)最少。分分析析問問題題: :例例2 2目目標(biāo)標(biāo)函數(shù)函數(shù): z=x+y) )N N

7、y y, ,x x( ( x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, y0直線直線x+y=12經(jīng)過的整點(diǎn)是經(jīng)過的整點(diǎn)是B(3,9)和和C(4,8)，它們是最優(yōu)解，它們是最優(yōu)解. 作出直線作出直線L:x+y=0，目標(biāo)函數(shù)目標(biāo)函數(shù):z= x+yB(3,9)C(4,8)A(3.6,7.8)當(dāng)直線當(dāng)直線L經(jīng)過點(diǎn)經(jīng)過點(diǎn)A時(shí)時(shí)z=x+y=11.4,x+y=12解得交點(diǎn)解得交點(diǎn)B,C的坐標(biāo)的坐標(biāo)B(3,9)和和C(4,8)2 4 6181282724681015但它不是最優(yōu)整數(shù)解但它不是最優(yōu)整數(shù)解.作直線作直線x+y=12約束條件約束條件:畫

8、可行域畫可行域平移平移L找交點(diǎn)及交點(diǎn)坐標(biāo)找交點(diǎn)及交點(diǎn)坐標(biāo)) )N Ny y, ,x x( ( 調(diào)整優(yōu)解法調(diào)整優(yōu)解法）或1284Z(1293minminZx0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*經(jīng)過可行域內(nèi)的整點(diǎn)經(jīng)過可行域內(nèi)的整點(diǎn)B(3,9)和和C(4,8)且和原點(diǎn)距離最近的直線是且和原點(diǎn)距離最近的直線是x+y=12，它們是最優(yōu)解，它們是最優(yōu)解.作出一組平行直線作出一組平行直線t = x+y，目標(biāo)函數(shù)目標(biāo)函數(shù)t = x+yB(3,9)C(4,8)A(18/5,39/5)打網(wǎng)格線法打網(wǎng)格線法在可行域內(nèi)在可行域內(nèi)

9、打出網(wǎng)格線，打出網(wǎng)格線，當(dāng)直線經(jīng)過點(diǎn)當(dāng)直線經(jīng)過點(diǎn)A時(shí)時(shí)t=x+y=11.4,但它不是最優(yōu)整數(shù)解，但它不是最優(yōu)整數(shù)解，將直線將直線x+y=11.4繼續(xù)向上平移繼續(xù)向上平移，1212182715978）或1284Z(1293minminZ14解線性規(guī)劃問題的步驟：解線性規(guī)劃問題的步驟： （1 1）2 2、畫畫： 畫出線性約束條件所表示的可行域；畫出線性約束條件所表示的可行域； （2 2）3 3、移移： 在線性目標(biāo)函數(shù)所表示的一組平行線中，在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；且縱截距最大或最小的直線； （3

10、 3）4 4、求求：通過解方程組求出最優(yōu)解；：通過解方程組求出最優(yōu)解； （4 4）5 5、答：作出答案。答：作出答案。 1 1、找、找 找出線性約束條件、目標(biāo)函數(shù)；找出線性約束條件、目標(biāo)函數(shù)； 即先求非整數(shù)條件下的最優(yōu)解，即先求非整數(shù)條件下的最優(yōu)解，調(diào)整調(diào)整Z的值的值使不定方程使不定方程Ax+By=Z存在最大（?。┐嬖谧畲螅ㄐ。┑恼c(diǎn)值，最后篩選出的整點(diǎn)值，最后篩選出整點(diǎn)最優(yōu)解整點(diǎn)最優(yōu)解 即先打即先打網(wǎng)格網(wǎng)格，描出可行域內(nèi)的，描出可行域內(nèi)的整點(diǎn)整點(diǎn)，平移直線，最先經(jīng)過或最后經(jīng)過的整點(diǎn)平移直線，最先經(jīng)過或最后經(jīng)過的整點(diǎn)坐標(biāo)即為坐標(biāo)即為整點(diǎn)整點(diǎn)最優(yōu)解最優(yōu)解線性規(guī)劃求最優(yōu)整數(shù)解的一般方法線性規(guī)劃求最

11、優(yōu)整數(shù)解的一般方法:1. 1.打網(wǎng)格線法打網(wǎng)格線法： 2. 2.調(diào)整優(yōu)解法調(diào)整優(yōu)解法：說明：說明：69Px-2y7043120230u=z1t3xyxyyx22學(xué)案典型例題 例1已知x,y滿足現(xiàn)行約束條件求（1）4x-3y的最大值與最小值。（2） =(x+3) +(y+1)的最大值和最小值。（3） =的最值。例例3 34x-3y-12=0 x+2y-3=0X-2y+7=0334Zxy231253) 2 - (4UAmin時(shí)過點(diǎn)l(3,0)(9,8)(-2,5/2)12034UBCmax時(shí)過l4x-3y-12=0 x+2y-3=0X-2y+7=0P(-3,-1)55853) 1(23 dPE15

12、) 81() 93(22PC225Z56422即PCZPE(9,8)(-2,5/2)(3,0)Ex+2y-3=0X-2y+7=04x-3y-12=0P(-3,-1)Q(x,y)13ytx2761tktkPAPB即(3,0)(9,8)(-2,5/2)解由約束條件畫出可行域，為矩形由約束條件畫出可行域，為矩形ABCDABCD( (包括邊界包括邊界) )點(diǎn)點(diǎn)C C的坐標(biāo)為的坐標(biāo)為(3,1)(3,1)，z z最最大時(shí)，即平移大時(shí)，即平移y yaxax時(shí)使直線在時(shí)使直線在y y軸上的軸上的截距最大，截距最大，a a k kCDCD，即，即a a 1.1. 例例4 4、已知變量已知變量x x，y y滿足約束條件滿足約束條件11x xy y44， 22x xy y2.2.若目標(biāo)函數(shù)若目標(biāo)函數(shù)z zaxaxy y( (其中其中a a0)0)僅僅在點(diǎn)在點(diǎn)(3,1)(3,1)處取得最大值，則處取得最大值，則a a的取值范圍為的取值范圍為_3x+5y=25 例例5、已知、已知x、y滿足滿足 ，設(shè)，設(shè)zaxy (a不為不為0)， 若取得最大值時(shí)，最優(yōu)解有無數(shù)個(gè)，求若取得最大值時(shí)，最優(yōu)解有無數(shù)個(gè)，求a 的值。的值。