簡單的線性規(guī)劃問題復習

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

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

3、所有可行解組成的集合叫做可行域(6)最優(yōu)解：若可行解(x1，y1)和(x2，y2)分別使目標函數(shù)取得最大值和最小值，它們都叫做這個問題的最優(yōu)解(7)一般地，求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題1255334xyxyx設設z=2x+y,求滿足求滿足時時,求求z的最大值和最小值的最大值和最小值.線性目線性目標函數(shù)標函數(shù)線性約線性約束條件束條件線性規(guī)線性規(guī)劃問題劃問題任何一個滿足任何一個滿足不等式組的不等式組的（x,yx,y）可行解可行解可行域可行域所有的所有的最優(yōu)解最優(yōu)解 2xy60，3不等式組 xy30，所表示的平面區(qū)域的面積為_. y24若點(1,3)和點(

4、4，2)在直線 2xym0 的兩側，則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.設設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代入點代入點B B得最大為得最大為8 8，代入點代入點A A得得最小值為最小值為 . .125-3X+5y 253X+5y 25 例例1. 1. 設設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ī)格，每張鋼板可同時截得三種規(guī)示每張鋼板可同時截得三種規(guī)示 ：格的小鋼板的塊數(shù)如下表所格的小鋼板

6、的塊數(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塊，塊，若你是若你是經理經理,問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張數(shù)最少數(shù)最少。分分析析問問題題: :例例2 2目目標標函數(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經過的整點是經過的整點是B(3,9)和和C(4,8)，它們是最優(yōu)解，它們是最優(yōu)解. 作出直線作出直線L:x+y=0，目標函數(shù)目標函數(shù):z= x+yB(3,9)C(4,8)A(3.6,7.8)當直線當直線L經過點經過點A時時z=x+y=11.4,x+y=12解得交點解得交點B,C的坐標的坐標B(3,9)和和C(4,8)2 4 6181282724681015但它不是最優(yōu)整數(shù)解但它不是最優(yōu)整數(shù)解.作直線作直線x+y=12約束條件約束條件:畫

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

9、打出網格線，打出網格線，當直線經過點當直線經過點A時時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、移移： 在線性目標函數(shù)所表示的一組平行線中，在線性目標函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點利用平移的方法找出與可行域有公共點且縱截距最大或最小的直線；且縱截距最大或最小的直線； （3

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

11、優(yōu)整數(shù)解的一般方法:1. 1.打網格線法打網格線法： 2. 2.調整優(yōu)解法調整優(yōu)解法：說明：說明：69Px-2y7043120230u=z1t3xyxyyx22學案典型例題 例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時過點l(3,0)(9,8)(-2,5/2)12034UBCmax時過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( (包括邊界包括邊界) )點點C C的坐標為的坐標為(3,1)(3,1)，z z最最大時，即平移大時，即平移y yaxax時使直線在時使直線在y y軸上的軸上的截距最大，截距最大，a a k kCDCD，即，即a a 1.1. 例例4 4、已知變量已知變量x x，y y滿足約束條件滿足約束條件11x xy y44， 22x xy y2.2.若目標函數(shù)若目標函數(shù)z zaxaxy y( (其中其中a a0)0)僅僅在點在點(3,1)(3,1)處取得最大值，則處取得最大值，則a a的取值范圍為的取值范圍為_3x+5y=25 例例5、已知、已知x、y滿足滿足 ，設，設zaxy (a不為不為0)， 若取得最大值時，最優(yōu)解有無數(shù)個，求若取得最大值時，最優(yōu)解有無數(shù)個，求a 的值。的值。