简单的线性规划问题复习

1、简单的线性规划问简单的线性规划问题复习题复习xyo1二元一次不等式表示的平面区域(1)一般地，在平面直角坐标系中，一般地，在平面直角坐标系中，二元一次不等式二元一次不等式 AxByC0 表示直线表示直线 AxByC0 某一侧所有点组成的平面区域，不含某一侧所有点组成的平面区域，不含边界线边界线不等式不等式 AxByC0 所表示的平面区域包括边界线所表示的平面区域包括边界线(2)对于直线对于直线 AxByC0 同一侧同一侧的所有点的所有点(x，y)，使得，使得 AxByC 的值的的值的符号相同符号相同，也就是说位于同一平面区域内的点，也就是说位于同一平面区域内的点，若其坐标适合若其坐标适合 Ax

2、ByC0，则位于另一个平面区域内的点，其，则位于另一个平面区域内的点，其坐标适合坐标适合 AxByC0(或或 AxByC0)所表示的区域所表示的区域直线定界，特殊点定域直线定界，特殊点定域2线性规划(1)线性约束条件：不等式组是一组对变量 x，y 的约束条件，由于这组约束条件都是关于 x，y 的一次不等式，所以又可称其为线性约束条件(2)目标函数：zAxBy 是欲达到最大值或最小值所涉及的变量 x，y 的解析式，我们把它称为目标函数(3)线性目标函数：由于 zAxBy 是关于 x，y 的一次解析式，所以又可叫做线性目标函数(4)可行解：满足线性约束条件的解(x，y)叫做可行解，(5)可行域：由

3、所有可行解组成的集合叫做可行域(6)最优解：若可行解(x1，y1)和(x2，y2)分别使目标函数取得最大值和最小值，它们都叫做这个问题的最优解(7)一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题1255334xyxyx设设z=2x+y,求满足求满足时时,求求z的最大值和最小值的最大值和最小值.线性目线性目标函数标函数线性约线性约束条件束条件线性规线性规划问题划问题任何一个满足任何一个满足不等式组的不等式组的（x,yx,y）可行解可行解可行域可行域所有的所有的最优解最优解 2xy60，3不等式组 xy30，所表示的平面区域的面积为_. 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）某工厂现有两种大小不同规格的钢板可截成某工厂现有两种大小不同规格的钢板可截成A、B、C三种规格，三种规格，每张钢板可同时截得三种规示每张钢板可同时截得三种规示 ：格的小钢板的块数如下表所格的小钢板

6、的块数如下表所解：解：设需截第一种钢板设需截第一种钢板x张，第二种钢板张，第二种钢板y张，张，钢板钢板总总张数为张数为Z则则,规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y15,x+2y18,x+3y27,x0y0 某顾客需要某顾客需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，块，若你是若你是经理经理,问各截这两种钢板多少张既能满足顾客要求又使所用钢板张问各截这两种钢板多少张既能满足顾客要求又使所用钢板张数最少数最少。分分析析问问题题: :例例2 2目目标标函数函数: 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)，它们是最优解，它们是最优解. 作出直线作出直线L:x+y=0，目标函数目标函数: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但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12约束条件约束条件:画

8、可行域画可行域平移平移L找交点及交点坐标找交点及交点坐标) )N Ny y, ,x x( ( 调整优解法调整优解法）或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，它们是最优解，它们是最优解.作出一组平行直线作出一组平行直线t = x+y，目标函数目标函数t = x+yB(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内在可行域内

9、打出网格线，打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向上平移继续向上平移，1212182715978）或1284Z(1293minminZ14解线性规划问题的步骤：解线性规划问题的步骤： （1 1）2 2、画画： 画出线性约束条件所表示的可行域；画出线性约束条件所表示的可行域； （2 2）3 3、移移： 在线性目标函数所表示的一组平行线中，在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；且纵截距最大或最小的直线； （3

10、 3）4 4、求求：通过解方程组求出最优解；：通过解方程组求出最优解； （4 4）5 5、答：作出答案。答：作出答案。 1 1、找、找 找出线性约束条件、目标函数；找出线性约束条件、目标函数； 即先求非整数条件下的最优解，即先求非整数条件下的最优解，调整调整Z的值的值使不定方程使不定方程Ax+By=Z存在最大（小）存在最大（小）的整点值，最后筛选出的整点值，最后筛选出整点最优解整点最优解 即先打即先打网格网格，描出可行域内的，描出可行域内的整点整点，平移直线，最先经过或最后经过的整点平移直线，最先经过或最后经过的整点坐标即为坐标即为整点整点最优解最优解线性规划求最优整数解的一般方法线性规划求最

11、优整数解的一般方法:1. 1.打网格线法打网格线法： 2. 2.调整优解法调整优解法：说明：说明：69Px-2y7043120230u=z1t3xyxyyx22学案典型例题 例1已知x,y满足现行约束条件求（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.若目标函数若目标函数z zaxaxy y( (其中其中a a0)0)仅仅在点在点(3,1)(3,1)处取得最大值，则处取得最大值，则a a的取值范围为的取值范围为_3x+5y=25 例例5、已知、已知x、y满足满足 ，设，设zaxy (a不为不为0)， 若取得最大值时，最优解有无数个，求若取得最大值时，最优解有无数个，求a 的值。的值。