资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
线性规划常见题型及解法线性规划是新教材中新增的内容之一,由已知条件写出约束条件,并作出可行域,进而通 过平移直线在可行域内求线性目标函数的最优解是最常见的题型,除此之外,还有以下六类常 见题型。一、求线性目标函数的取值范围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表示的平面区域的面积为().八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 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=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 作一组平行直线 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营养师想购这三种食物共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 = mmin+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个式子中的“”也可以是“”或aMXi .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)是常量.线性规划的理论和方法主要在以下两类问题中得到应用:一是在人力、物力资金等资源一定的条件下,如何使用它们来完成最多的任务;二是给一项任务,如何合理安排和规划,能以最少的人力、物力、资金等资源来完成该项任务.线性规划中整点最优解的求解策略在工程设计、经营管理等活动中,经常会碰到最优化决策的实际问题,而解决此类问题一般以线性规划为其重 要的理论基础。然而在实际问题中,最优解(x,y)通常要满足x,y N,这种最优解称为整点最优解,下面通过具体例子谈谈如何求整点最优解1 平移找解法作出可行域后,先打网格,描出整点,然后平移直线I,直线I最先经过或最后经过的那个整点便是整点最优解72m3,第二种有56m3,假设生产每种产品.每生产一只圆桌可获利6元,生产一个衣柜可,才使获得产品木料(单位m3)第一种第二种圆桌0.180.08衣柜0.090.28获利10元.木器厂在现有木料条件下,圆桌和衣柜各生产多少多?利润最例1、某木器厂生产圆桌和衣柜两种产品,现有两种木料,第一种有 都需要用两种木料,生产一只圆桌和一个衣柜分别所需木料如下表所示S.18x + 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。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,从而求得最优解。从这
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号