《线性规划常见题型及解法》由会员分享，可在线阅读，更多相关《线性规划常见题型及解法（11页珍藏版）》请在金锄头文库上搜索。
1、线性规划常见题型及解法线性规划是新教材中新增的内容之一，由已知条件写出约束条件，并作出可行域，进而通 过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常 见题型。一、求线性目标函数的取值范围x乞2I例1、 若x、y满足约束条件 y乞2，则z=x+2y 的取值范围是 （）x=2x y _2A、2,6 B、2,5 C、3,6 D、（ 3,5解：如图，作出可行域，作直线I : x+2y = 0,将l向右上方平移，过点A （ 2,0 ）时，有最小值2,过点B （ 2,2 ）时，有最大值6 ,故选A、求可行域的面积2x y -6 _ 0I 例2、不等式组 x y-30表示
2、的平面区域的面积为（）.八2A、4 B、1 C、5 D、无穷大解：如图，作出可行域， ABC 的面积即为所求，由梯形OMBC 的面积减去梯形OMAC 的面积即可，选B三、求可行域中整点个数例3、满足|x| + |y| 2的点（x, y）中整点（横纵坐标都是整数） 有（）A、9 个 B、10 个13个D、 14 个:|x| +2(x0,y 0) (x 0,y V0) (x 0,y0) (xY0,yY0)x 一 y|y| w 2等价于_x y _ 2_ x _ y _ 2可行域如右图，是正方形内部（包括边界），13个，选D|y| 0）x岂3取得最小值的最优解有无数个，则a的值为（）A、一 3 B、
3、3 C、一 1 D、1解：如图，作出可行域，作直线I: x+ay = 0 ,要使目标函数 z=x+ay（a0） 取得最小值的最优解有无数个，则将I向右上方 平移后与直线x+y = 5重合，故a=1 ,选D五、求非线性目标函数的最值2x y - 2 _ 0例5、已知x、y满足以下约束条件 x _2y 4 _0,贝U z=x 2+y 2的最大值和最小值分别是3x - y - 3_0()A、13 ,1B、13 , 2C、13 ,4D、卫,55解：如图，作出可行域，X2+y2是点（x， y）到原 平方，故最大值为点A（ 2,3 ）到原点的距离的平 |AO| 2=13，最小值为原点到直线2x + y 2
4、=0 的4方，即为4 ,选C5六、求约束条件中参数的取值范围-2= 0点的距离的 方， 即 距离的平例6、已知|2x y + m| v 3表示的平面区域包含点（0,0 ）和（一1,1 ），则m的取值范围是A、（ -3,6 ） B、（ 0,6 ） C、（ 0,3 ） D、（-3,3 ）2x - y m 3 0解：|2x y + m| v 3等价于7Zx _ y + m _3 35000/一、一yJx解:设每周需用谷物饲料x kg,动物饲料y kg,每周总的饲料费用为z兀，那么5,而0 兰 x 兰 50000 胪0 z=0.28x+0.9y如下图所示，作出以上不等式组所表示的平面区域，即可行域.1
5、 作一组平行直线 0.28x+0.9y =t,其中经过可行域内的点且和原点最近的直线，经过直线x+y=35000和直线y x5砧、上 87500 17500、8750017500的父点A（,），即x, y时,饲料费用最低.3333所以，谷物饲料和动物饲料应按5:1的比例混合，此时成本最低.指出：要完成一项确定的任务，如何统筹安排，尽量做到用最少的资源去完成它，这是线性规划中最常见的问题之一.（例3图）（例4图）例3、下表给出甲、乙、丙三种食物的维生素A、B的含量及成本甲乙丙维生素A（单位/千克）400600400维生素B（单位/千克）800200400成本（元/千克）765营养师想购这三种食物
6、共10千克，使之所含维生素 A不少于4400单位,维生素B不少于4800单位，问三种食物各购多少时，成本最低？最低成本是多少？解:设所购甲、乙两种食物分别为x千克、y千克,则丙种食物为（10-xy）千克.x、y应满足线性条件为N00x+600y+400（10xy） 44002丿，化简得i-500x +200y +400（10 x y）色 4800l2x y 色 4作出可行域如上图中阴影部分目标函数为z=7x+6y+5（10 x y）=2x+y+50,令m=2x+y,作直线l:2x+y=0,则直线2x+y=m经过可行域中 A（3,2）时,m 最小，即mmin=2 3+2=8，二Zmin = mm
7、in+50=58答：甲、乙、丙三种食物各购 3千克、2千克、5千克时成本最低,最低 成本为58元.指出：本题可以不用图解法来解，比如由 / -2 得2x - y 兰 4z=2x+y+50=(2xy)+2y+504+22+50=58,当且仅当 y=2,x=3 时取等号总结：(1)设出决策变量，找出线性规划的约束条件和线性目标函数；(2)利用图象,在线性约束条件下找出决策变量，使线性目标函数达到最大(或最小).4兀 +a!2X2 + +aifmXma2iX! +a22x2 +八 +a2mxm 兰 b22.线性规划问题的一般数学模型是：已知 21 122 22 (这n个式子中的“”也可以是“”或aM
8、Xi .2X2* anmXm 岂 g“ =号)其中 aj(i=i,2，,n, j=1,2,m),bi (i=1,2,n)都是常量,xj (j=1,2,m)是非负变量，求 z=cixi+C2X2+cmXm的最大值 或最小值，这里Cj (j=i,2，,m)是常量.线性规划的理论和方法主要在以下两类问题中得到应用：一是在人力、物力资金等资源一定的条件下，如何使用它们来完成最多的任务；二是给一项任务，如何合理安排和规划，能以最少的人力、物力、资金等资源来完成该项任务.线性规划中整点最优解的求解策略在工程设计、经营管理等活动中，经常会碰到最优化决策的实际问题，而解决此类问题一般以线性规划为其重 要的理论
9、基础。然而在实际问题中，最优解(x,y)通常要满足x,y N，这种最优解称为整点最优解，下面通过具体例子谈谈如何求整点最优解1 平移找解法作出可行域后，先打网格，描出整点，然后平移直线I，直线I最先经过或最后经过的那个整点便是整点最优解72m3，第二种有56m3,假设生产每种产品.每生产一只圆桌可获利6元，生产一个衣柜可，才使获得产品木料(单位m3)第一种第二种圆桌0.180.08衣柜0.090.28获利10元.木器厂在现有木料条件下，圆桌和衣柜各生产多少多？利润最例1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有 都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示S.1
10、8x + 0.09y 兰 720.080.2856而z=6x+10y.如图所示,作出解：设生产圆桌 x只，生产衣柜y个，利润总额为z元，那么x兰07-0以上不等式组所表示的平面区域，即可行域.作直线l:6x+10y=0,即l:3x+5y=0，把直线I向右上方平移至li的位置时，直线经过可行域上点 M,且与原点距离最大350只，生产衣柜1000.18x +0.09y =72此时z=6x+10y取最大值。解方程组b8x+0.28y=56，得M点坐标何，100).答：应生产圆桌 个,能使利润总额达到最大.点评：本题的最优点恰为直线 0.18x+0.09y=72和0.08x+0.28y=56的交点M。
11、1例2有一批钢管，长度都是 4000mm要截成500mm和 600mm两种毛坯，且这两种毛坯按数量比不小于-配套,3怎样截最合理?解：设截500mm的钢管x根，600mm勺y根，5x + 6y 40总数为z根。根据题意，得？ ：丿矿,目标函数为，八作出如图所示的可行域内的整点，作一组平行直线 x+y=t，经过可行域内的点且和原点距离最远的直线为过B （8， 0）的直线，这时 x+y=8.由于x,y为正整数，知（8,0）不是最优解。显然要往下平移该直线，在可行域内找整点，使x+y=7，可知点（2,5），（ 3,4），（4，3），（5，2），（6，1）均为最优解答：略.点评：本题与上题的不同之处在于，直线x+y=t经过可行域内且和原点距离最远的点B （8, 0）并不符合题意，此时必须往下平移该直线，在可行域内找整点，比如使x+y=7，从而求得最优解。从这
