简单的线性规划典型例题

1、简单的线性规划典型例题例1画出不等式组0,0,x y 2x y 4 0,表示的平面区域.x 3y 3 0.分析：采用“图解法”确定不等式组每一不等式所表示的平面区域，然后求其公共部分.解：把x 0 , y 0代入x y 2中得0 0 2 0不等式x y 2 0表示直线x y 2 0下方的区域(包括边界)，即位于原点的一侧，同理可画出其他两部分，不等式组所表示的区域如图所示.说明：“图解法”是判别二元一次不等式所表示的区域行之有效的一种方法.例2画出2x 3 y有的正整数解(x,y).3表示的区域，并求所分析：原不等式等价于yy2x 33.，而求正整数解则意味着x，yx 0, y0,有限制条件，

2、即求x Z,y Z,y 2x 3,y 3.解：依照二元一次不等式表示的平面区域，知2x3表示的区域如下图:对于2x 3 y 3的正整数解，先画出不等式组.0, y乙y 2x 3,3.0,z,所表示的平面区域，如图所示.容易求得，在其区域内的整数解为（1,1）、（1,2）、（1,3）、（2,2）、（2,3）.说明：这类题可以将平面直角坐标系用网络线画出来，然后在不等式组所表示的平面区域内找出符合题设要求的整数点来.例3求不等式组yy1所表示的平面区域的面积.1分析：本题的关键是能够将不等式组所表示的平面区域作出来,判断其形状进而求出其面积.而要将平面区域作出来的关键又是能够对不等式组中的两个不等

3、式进行化简和变形， 如何变形？需对绝对值加以讨论.解：不等式y |x 1 1可化为yx(x 1)或 y x 2(x1);0.不等式y ix 1可化为y x 1(x 0)或y x 1(x 0).在平面直角坐标系内作出四条射线AB: y x(x 1) , AC: y x 2(x1)DE: y x 1(x0) , DF: y x 1(x0)则不等式组所表示的平面区域如图由于AB与AC、DE与DF互相垂直,所以平面区域是一个矩形.根据两条平行线之间的距离公式可得矩形的两条边的长度分别为所以其面积为3.例4 若x、y满足条件2x y 123x 2y 100,求x 4y 100,z x 2y的最大值和最小

4、值.分析：画出可行域，平移直线找最优解.解：作出约束条件所表示的平面区域，即可行域，如图所示.作直线l: x 2y z，即y -x -z ,它表示斜率为-,纵截距2 2 2为兰的平行直线系，当它在可行域内滑动时，由图可知，直线2l过点时，z取得最大值，当I过点B时，z取得最小值.zmax2 2 8 18Zmin2222说明：解决线性规划问题，首先应明确可行域，再将线性目标函 数作平移取得最值.例 5用不等式表示以A(1,4), B( 3,0) , C( 2, 2)为顶点的三角形内部的平面区域.分析：首先要将三点中的任意两点所确定的直线方程写出来，然后结合图形考虑三角形内部区域应怎样表示。解：直

5、线AB的斜率为:kAB1 其方程为yx3.可求得直线BC的方程为y 2x 6 .直线AC的方程为y 2x 2 .ABC的内部在不等式x y 3 0所表示平面区域内，同时在不等式2x y 6 0所表示的平面区域内，同时又在不等式2x y 2 0所表示的平面区域内(如图).示.yTz / yIA所以已知三角形内部的平面区域可由不等式组x2x2x0,6 0,表0说明：用不等式组可以用来平面内的一定区域,注意三角形区域内部不包括边界线.例6已知x y 5 0 , x y 10 0 .求x2 y2的最大、最小值.f 2分析：令z x2 y2，目标函数是非线性的.而z x2 y2 Jx2 y2可看做区域内

6、的点到原点距离的平方.问题转化为点到直线的距离问题.解：由51000得可行域（如图所示）为z.22J 22y Vx y100 ,J所以z的最大x y 10 0的距离分别为5而(0,0)到x2说明：题目中的目标函数是非线性的.解决的方法类似于线性规划问题.可做出图，利用图进行直观的分析.3y 200,3y 20,求 zN*, y N *.4x例7设z 7x 5y式中的变量X、y满足下列条件xx的最大值.分析：先作出不等式组所表示的可行域，需要注意的是这里的X、y N*，故只是可行域内的整数点，然后作出与直线7x 5y 0平等的直线再进行观察.解：作出直线li：4x 3y 20 0和直线l2： x

7、 3y 2 0，得可行域如图所示.解方程组4x 3 2又作直线l ：7x 5y 0 ,平等移动过点A时，7x 5y取最大值，然而点A不是整数点，故对应的z值不是最优解，此时过点 A的直线为 7x 5y 344，应考虑可行域中距离直线 7x 5y 34-最近的整点，即55B（2,4），有z（B）7 2 5 4 34，应注意不是找距点A最近的整点，如点C（4,1）为可行域中距A最近的整点，但z（c） 7 4 5 1 33，它小于 z（B），故z的最大值为34.说明：解决这类题的关键是在可行域内找准整点. 若将线性目标 函数改为非线性目标函数呢?x 4y 3,z x2 y2，式中的变量X、y满足3x

8、 5y 25,试求z的最大x 1.值、最小值.分析：作出不等式组所表示的平面区域，本题的关键是目标函数解：作出直线z x2 y2应理解为可行域中的点与坐标原点的距离的平方.li： x 4y 3 0 , l2：3x 5y 25 0 , I3： x 1 得到如图所示的可行域.由x4y3 0 得 A(5,2)3x5y25 0由x4y3 0得 C(1,1)x1由3x5y25 0 得 B(1 , 22).x15由图可知:当（X, y）为点C（11）时，z取最小值为2;当（xy）为点A（5,2）时，z取最大值29.说明：若将该题中的目标函数改为z -，如何来求z的最大值、y最小值呢？请自己探求.（将目标函

9、数理解为点（x,y）与点（0,0）边线的 斜率）例 9 设 x 0 , y 0, z 0 ； p 3x y 2z, q x 2y 4z, x y z 1 ,用图表示出点（P ,q）的范围.可借助于x，分析：题目中的P , q与x , y , z是线性关系.z的范围确定（P ,q）的范围.解:3x y 2z p,由 x 2y 4z q,得x y z 1,1习(8 q 6p),7(14 5q 3p),由 x127(5 4p 3q),6p3p3p8 0,14 0,做出不等式所示平面区域如图所示.y，q5qz的取值范围.借p, q所满足的不助于三元一次方程组分别求出x , y , z，从而求出等式组找

10、出（P ,q）的范围.例10 某糖果厂生产A、B两种糖果，A种糖果每箱获利润40元,B种糖果每箱获利润50元，其生产过程分为混合、烹调、包装三道 工序，下表为每箱糖果生产过程中所需平均时间（单位：分钟）混合烹调包装A153B241每种糖果的生产过程中，混合的设备至多能用12机器小时，烹 调的设备至多只能用机器30机器小时，包装的设备只能用机器15机器小时，试用每种糖果各生产多少箱可获得最大利润.分析：找约束条件，建立目标函数.解：设生产A种糖果x箱，B种糖果y箱，可获得利润z元，则此5x问题的数学模式在约束条件3xxyx 2y 720 4y 1800 y00900下，求目标函数40x 50 y

11、的最大值,作出可行域,其边界OA: y0 AB:3xy 900BC:5x 4y 1800CD : x2y 7200DO : x由 z 40x 50y得 y它表示斜率为4 zcA蛊-x ,5 504，截距为的平行直线系，越大，z越大,55050从而可知过C点时截距最大，z取得了最大值.解方程组 x 2y 720 C 120,3005x 4y 1800Zmax 40 120 50 300 19800即生产A种糖果120箱，生产B种糖果300箱，可得最大利润19800元.说明：由于生产A种糖果120箱，生产B种糖果300箱，就使得两种糖果共计使用的混合时间为120+ 2X300= 720 （分）,烹

12、调时间 5X 120 + 4X 300= 1800 （分）,包装时间 3X 120 + 300= 660 （分）,这说明该计划已完全利用了混合设备与烹调设备的可用时间，但对包 装设备却有240分钟的包装时间未加利用，这种“过剩”问题构成了 该问题的“松驰”部分，有待于改进研究.例11 甲、乙、丙三种食物的维生素A、B含量及成本如下表:甲乙丙维生素A （单位/千克）600700400维生素B （单位/千克）800400500成本（兀/千克）1194某食物营养研究所想用x千克甲种食物，y千克乙种食物，z千 克丙种食物配成100千克的混合食物，并使混合食物至少含56000单位维生素A和63000单位

13、维生素B . （ 1）用X、y表示混合物成本C . （ 2）确定x、y、z的值，使成本最低.分析：找到线性约束条件及目标函数，用平行线移动法求最优解.示.解：（1）依题意:x、y、z 满足 x y z 100 z 100成本 C 11x 9y 4z 7x 5y 400 （元）（2）依题意800xz 100 X y作出不等式组所对应的可行域，如图700y 400z 56000400y 500z 630002x 3y 160 3x y 130X 0, y 0联立3x y 130 、片2x 3y 160 交点 A 50,20作直线7x 5y 400 C则易知该直线截距越小，C越小,所以该直线过A 5

14、0,0时，直线在y轴截距最小，从而C最小，此时7X 50+ 5X 20+ 400= C = 850 元x 50千克，z 30千克时成本最低.例12某工厂有甲、乙两种产品，按计划每天各生产不少于15t, 已知生产甲产品1t需煤9t，电力4kW，劳力3个（按工作日计算）； 生产乙产品1t需煤4t，电力5kW，劳力10个；甲产品每吨价7万 元，乙产品每吨价12万元；但每天用煤最不得超过 300吨，电力不 得超过200kW，劳力只有300个.问每天各生产甲、乙两种产品多 少t，才能既保定完成生产任务，又能为国家创造最多的财富.分析：先设每天生产甲、乙两种产品的产量分别为 xt和yt，建立 约束条件和目

15、标函数后，再利用图形直观解题.解：设每天生产甲产品xt，乙产品yt，总产值St，依题意约束条 件为:x15,y15,9x4y300,4x5y200,3x10y300.目标函数为S 7x 12y .约束条件表示的可行域是五条直线所围成区域的内部的点加上它的边线上的点（如图阴影部分）.（X, y）.作直 线S 7x 12y，随着S取值的变化，得到一束平行直线，其纵截距为12,可以看出，当直线的纵截距越大,S值也越大.从图中可以看出，当直线S7X 12y经过点A时，直线的纵截距最大，所以S也取最大值.解方程组 4X 150y 2300 00,得 A(20,24).故当 X 20 , y24时,S最大

16、值7 20 12 24428(万元).答：第天生产甲产品20t，乙产品24t，这样既保证完成任务，又 能为国家创造最多的财富428万元.说明：解决简单线性规划应用题的关键是：（1）找出线性约束条 件和目标函数；（2）准确画出可行域；（3）利用S的几何意义，求出最 优解.如本例中，5是目标函数S 7X 12y的纵截距.12例13有一批钢管，长度都是4000mm ,要截成500 mm和600mm两种毛坯，且这两种毛坯数量比大于1配套，怎样截最合理？3分析：先设出未知数，建立约束条件和目标函数后，再按求最优 解是整数解的方法去求.解：设截500mm的x根，600mm的y根，根据题意，得5x 6y 4

17、0,y 3x, 冃且 X,y z .X 0,y 0.作出可行域，如下图中阴影部分.目标函数为z X且和原点距离最远的直线为过B(0,8)的直线，这时X y 8 .由x , y为正整数，知(0,8)不是最优解.在可行域内找整点，使X y 7可知点(2,5) , (3,4) , (4,3) , (5,2) , (6,1)均为最优解.答：每根钢管截500mm的2根，600mm的5根，或截500mm的3 根，600mm的4根或截500mm的4根，600mm的3根或截500mm的5根，600 mm的2根或截500mm的6根，600mm的1根最合理.说明：本题易出现如下错解:设截500mm的x根，600

18、mm的y根，500X 600yX 1y 3,X 0,y 0-4000,5x即yXy6y 40,3x,0,0.其中X、y均为整数.作出可行域，如下图所示中阴影部分.目标函数为z X y，作一组平行直线X y t，经过可行域内的点且和2312023故a43,10，即xy 7，调整为x 2 , y 5 .原点相距最远的直线为过A点的直线.先求A点的坐标,解y 3x 得5x 6y 40经检验满足条件，所以每根截 500mm的2根，600mm的5根最 合理.本题解法错误主要是在作一组平行直线 x y t时没能准确作出, 而得到经过可行域内的点且和原点距离最远的直线为过 A点的直线.此错误可检验如下: 如

19、果直线x y t通过A点，它是经过可行域内的点且到原点距离最远 的直线，那么40 120 t，即x y 7 .由于x , y为整数，所以点2323AoU , 5盘）不是最优解但在可行域内除A点外，不可能再有其他点满 足x y 7，只能在可行域内找满足x y 6的点.如果还没有整数点,则只能在可行域内找满足x y 5的整数点.但我们知道x 2 , y 5满足题意，这样，就出现了矛盾，从而判断解法错误，即x y t通过A 点的直线并不是通过可行域内的点且和原点距离最远的直线.例14某工厂生产A、B两种产品，已知生产A产品1kg要用煤9t , 电力4kW , 3个工作日；生产B产品1kg要用煤4t，

20、电力5kW ,10 个工作日.又知生产出A产品1kg可获利7万元，生产出B产品1kg可 获利12万元，现在工厂只有煤360t，电力200kW，300个工作日, 在这种情况下生产A， B产品各多少千克能获得最大经济效益.分析：在题目条件比较复杂时，可将题目中的条件列表.产品工作日煤/电力kW利润/万元A产品3947B产品104512解：设这个工厂应分别生产A , B产品xkg , ykg ,可获利z万元.根据上表中的条件，列出线性约束条件为3x10y300,9x4y360,4x5y200,x0,y0,目标函数为z 7x 12y （万元）.画出如图所示的可行域，做直线|：7x 12y0 ,做一组直

21、线7x 12y t与1平行，当1过点A时t最大.由3： 50y 20；得A点坐标为(20,24).把A点坐标代入I的方程，得t 428(万元).答:428万元.说明：把实际问题转化为线性规划问题的难点在于找出题目中的所有线性约束条件.同时本题的可行域形状较复杂，要注意分析目标 函数的斜率和各边界斜率的关系：从而确定在何处取得最优解.解应 用题时还应注意设出未知量和做答这两个必要步骤.例15某公司每天至少要运送180t货物.公司有8辆载重为6t的A型 卡车和4辆载重为10t的B型卡车，A型卡车每天可往返4次，B型卡车可往返3次，A型卡车每天花费320元，B型卡车每天花费504元,问如何调配车辆才

22、能使公司每天花费最少.分析：设A型卡车x辆,B型卡车y辆.问题转化为线性规划问题.同时应注意到题中的x ,y只能取整数.解：设A型卡车x辆,B型卡车y辆，则0x8,0 y 4,即x y 10,24x 30 y 180,00x4x8,4,10,5y 30,目标函数z320x 504y .做如图所示的可行域,找出(8,0) , (8,1),做直线l：320x 504y 0 .在可行域中打上网格,(8,2) , (7,1) , (7,2) , (7,3)，等整数点.做 l :320x 504y t 与 l平行,可见当l过(8,0)时t最小，即Zmin 8 320 2560(元).说明：整数解的线性规

23、划问题.如果取最小值时不是整数点，则考虑此点附近的整数点.例16某工厂利用两种燃料生产三种不同的产品A、B、C,每消耗 一吨燃料与产品A、B、C有下列关系:5产品A1产品B产品C燃料甲iOC 吨7（吨）5（吨燃料乙5（吨）9（吨）1旅吨现知每吨燃料甲与燃料乙的价格之比为2:3，现需要三种产品A、B、C各50吨、63吨、65吨.问如何使用两种燃料，才能使该厂成 本最低?分析：由于该厂成本与两种燃料使用量有关， 而产品A、B、C又 与这两种燃料有关，且这三种产品的产量也有限制，因此这是一道求 线性目标函数在线性约束条件下的最小值问题， 这类简单的线性规划 问题一般都可以利用二元一次不等式求在可行域上