《线性规划ppt课件》由会员分享，可在线阅读，更多相关《线性规划ppt课件（31页珍藏版）》请在金锄头文库上搜索。
1、1求求z=2x+y的最大值，使式中的的最大值，使式中的x,y满足约束条件满足约束条件2 一般地，求线性目标函数在线性约束一般地，求线性目标函数在线性约束条件下的最大值或最小值问题，统称为条件下的最大值或最小值问题，统称为线性规划问题线性规划问题 满足线性规划条件的解满足线性规划条件的解(x,y)叫做叫做可行解可行解由所有可行解组成的集合叫做由所有可行解组成的集合叫做可行域可行域满足条件的可行解叫做这个问题的满足条件的可行解叫做这个问题的最优解最优解定义定义 由由x,y的一次不等式的一次不等式(或方程或方程)组成的不等式组成的不等式（或方程）组，它是对（或方程）组，它是对x,y的约束条件，称为的
2、约束条件，称为线性约束条件线性约束条件 z=Ax+By是欲达到最大值或最小值所涉及的是欲达到最大值或最小值所涉及的变量变量x,y的解析式，叫做的解析式，叫做目标函数目标函数.由于由于z=Ax+By是是x,y的一次解析式的一次解析式,所以又叫做所以又叫做线性目标函数线性目标函数.3问题问题 某工厂计划生产甲、乙两种产品，这两某工厂计划生产甲、乙两种产品，这两种产品都需要两种原料。生产甲种产品种产品都需要两种原料。生产甲种产品1工时工时需要需要A种原料种原料3kg，B种原料种原料1kg;生产乙种产品生产乙种产品1工时需要工时需要A种原料种原料2kg，B种原料种原料2kg。现有。现有A种原料种原料1
3、200kg， B种原料种原料800kg。如果生产甲。如果生产甲种产品每工时的平均利润是种产品每工时的平均利润是30元，生产乙种产元，生产乙种产品每工时的平均利润是品每工时的平均利润是40元，问甲、乙两种产元，问甲、乙两种产品各生产多少工时能使利润总额最大？最大利品各生产多少工时能使利润总额最大？最大利润是多少？润是多少？4解：依题意可列表如下解：依题意可列表如下 产品原料A数量（kg）原料B数量（kg）利润（元）生产甲种产品1工时3130生产乙种产品1工时2240限额数量12008005设计划生产甲种产品设计划生产甲种产品x工时，乙甲种工时，乙甲种产品产品y工时工时,则获得利润总额为：则获得利
4、润总额为：F=30x+40y 其中其中x、y满足下列条件满足下列条件令令30x+40y=0，记作，记作6如图在可行域内如图在可行域内B点为最优解点为最优解B(200,300)yoxABC7代入式子代入式子得得答：用答：用200工时生产甲种产品，用工时生产甲种产品，用300工时生产乙种产品，能获得利工时生产乙种产品，能获得利润润18000元，此时利润总额最大。元，此时利润总额最大。8例例3、A，B两个居民小区的居委会组织本小两个居民小区的居委会组织本小区的中学生，利用双休日去市郊的敬老院参区的中学生，利用双休日去市郊的敬老院参加献爱心活动，两个小区都有同学参加。已加献爱心活动，两个小区都有同学参
5、加。已知知A区的每位同学往返车费是区的每位同学往返车费是3元，每人可元，每人可为为5位老人服务；位老人服务；B区的每位同学往返车费区的每位同学往返车费是是5元，每人可为元，每人可为3位老人服务。如果要求位老人服务。如果要求B区参与活动的同学比区参与活动的同学比A区的同学多，且去敬区的同学多，且去敬老院的往返车费不超过老院的往返车费不超过37元，怎样安排元，怎样安排A，B两区参与活动的同学人数，才能使受到服两区参与活动的同学人数，才能使受到服务的老人多？受到服务的老人最多是多少？务的老人多？受到服务的老人最多是多少？9解：设解：设A,B两区参与活动的人数分别两区参与活动的人数分别为为x,y,受到
6、服务的老人的人数为受到服务的老人的人数为z，则，则应满足的约束条件是应满足的约束条件是即即10oyx11根据不等式组，作出可行域内的整根据不等式组，作出可行域内的整点（如图）点（如图）M点为最优解。点为最优解。解方程组解方程组当当x=4,y=5时时答：答：A，B两区参与活动的同学人数两区参与活动的同学人数分别为分别为4，5时，才能使受到服务的时，才能使受到服务的老人最多。受到服务的老人最多是老人最多。受到服务的老人最多是多为多为35人。人。12x-y=0x+y-1=0y=-12x+y=0练习练习1：求：求z=2x+y的最大值，使式中的的最大值，使式中的x,y满足约束条件满足约束条件13设 z=
7、2x+y，式中变量 x,y 满足下列条件，求，求 z 的最大值和最小值的最大值和最小值1415l0l1ll2A(5,2)B(1,1)作直线作直线l0:2x+y=0作一组与作一组与l0平行的直线平行的直线 l:2x+y=t以经过点以经过点A的直线的直线l2所对应的所对应的t最大最大以经过点以经过点B的直线的直线l1所对应的所对应的t最小最小xyo16zmax=25+2=12zmin=21+1=317例下表给出甲，乙，丙三种食物中的例下表给出甲，乙，丙三种食物中的维生素维生素A,B的含量及单价：的含量及单价：甲乙丙维生素A(单位千克） 维生素B(单位千克） 单价（元千克）营养师想购买这三种食物共千
8、克，使它们所营养师想购买这三种食物共千克，使它们所含的维生素含的维生素A不少于单位，维生素不少于单位，维生素B不少不少于单位，而且要使付出的金额最低，这于单位，而且要使付出的金额最低，这三种食物应各购买多少千克？三种食物应各购买多少千克？18解：设购买甲种食物解：设购买甲种食物x千克，乙种食物千克，乙种食物y千千克，则购买丙种食物克，则购买丙种食物(10-x-y)千克又设总千克又设总支出为支出为z元，依题意得元，依题意得z=7x+6y+5(10-x-y),化简得化简得z=2x+y+50.x,y应满足的约束条件应满足的约束条件19yoxY=2M化简得化简得根据上述不等式组，根据上述不等式组，作出
9、表示可行域的平作出表示可行域的平面区域，如图阴影部面区域，如图阴影部分所示分所示20解方程组解方程组得点得点M(3,2)因此，当因此，当x=3.y=2时，时，z取得最小值为取得最小值为答：购买甲种食物千克，乙种食物千克，答：购买甲种食物千克，乙种食物千克，丙种食物千克时，付出的金额为千克丙种食物千克时，付出的金额为千克21例例2某货运公司拟用集装箱托运甲，乙两种货物，一某货运公司拟用集装箱托运甲，乙两种货物，一个大集装箱能够装所托运货物的总体积不能超过个大集装箱能够装所托运货物的总体积不能超过24立方米，总重量不能低于立方米，总重量不能低于650千克。甲，乙两种货物千克。甲，乙两种货物每袋的体
10、积，重量和可获得的利润，列表如下：每袋的体积，重量和可获得的利润，列表如下：货物货物 每袋体积（单位：每袋体积（单位：立方米）立方米）每袋重量（单每袋重量（单位：百千克）位：百千克）每袋利润（单每袋利润（单位：百元）位：百元）甲甲乙乙.问；在一个大集装箱内，这两种货物各装多少袋问；在一个大集装箱内，这两种货物各装多少袋（不一定都是整袋）时，可获得最大例润？（不一定都是整袋）时，可获得最大例润？22解：设托运甲种货物解：设托运甲种货物x袋，乙种货物袋，乙种货物y袋获得袋获得利润利润z百元，则百元，则z=20x+10y依题意，可得关于依题意，可得关于x,y的约束条件的约束条件根据上述不等式组，作出
11、表示可行域的平根据上述不等式组，作出表示可行域的平面区域，如图阴影部分所示。面区域，如图阴影部分所示。23记记:20x+10y=0,即即2x+y=0 yoxM24解方程组解方程组得点得点M(4,1)因此当因此当x=4,y=1时，时，z取得最大值。此时取得最大值。此时答：装甲种货物答：装甲种货物4袋，乙种货物袋，乙种货物1袋，袋，可获得最大利润可获得最大利润9000元元25练习练习2：求：求z=5y-3x的最大值和最小值，使式的最大值和最小值，使式中的中的x,y满足约束条件满足约束条件zmin=3(-2)+5 (-1)= -11zmax=3 +5 = 26x-y=72x+3y=24y=6练习练习3：求：求z=x+3y的最大值，使式中的的最大值，使式中的x,y满满足约束条件足约束条件zmax=3+36=21A(3,6)27练习练习4：28pqo点点(p,q)在阴影表示在阴影表示的平面区域内的平面区域内29(2000，上海上海)图中阴影部分的点满足不等式组图中阴影部分的点满足不等式组在这些点中，使目标函数在这些点中，使目标函数k=6x+8y取得最大值取得最大值的点的坐标是的点的坐标是53(1,4)(0,5)3031
