《简单的线性规划问题》由会员分享，可在线阅读，更多相关《简单的线性规划问题（38页珍藏版）》请在金锄头文库上搜索。
1、授课教师：辛荣华授课教师：辛荣华2014年年10月月23日日2一一. .复习回顾复习回顾1.在同一坐标系上作出下列直线在同一坐标系上作出下列直线:2x+3y=0;2x+3y=1;2x+3y=3;2x+3y=4;2x+3y=7xYo2x+3y=t3x+5y25x- -4y- -3x1在该平面区域上 问题 1 1：有无最大(小)值？问题：有无最大(小)值？xyox-4y=-33x+5y=25x=1问题：2 2+ +有无最大(小)值？CAB40xy4348表示的平面区域表示的平面区域2.画出不等式组画出不等式组求求z=2x+3y的最大值的最大值yx4843oM 把把z2x3y变形为变形为解方程组解方
2、程组 得点得点M的坐标（的坐标（4，2）所以所以它表示斜率为它表示斜率为 ，在，在y轴的截距为轴的截距为 的一族平行直线的一族平行直线 平移直线平移直线 经过平面区域的经过平面区域的点点M时时在在y轴上的轴上的截距最大截距最大即即z有最大值有最大值作直线作直线x+2y=8y=3X=4 二二. .抽象思维，形成概念：抽象思维，形成概念：yx4843o 把求最大值或求最小值的的函数把求最大值或求最小值的的函数z=2x+3yz=2x+3y称为称为目标函数目标函数，因为，因为它是关于变量它是关于变量x、y的一次解析式，又称的一次解析式，又称线性目标函数线性目标函数。 满足线性约束的解满足线性约束的解（
3、x x，y y）叫做叫做可行解可行解。 在线性约束条件下求线性目标函数的最大值或最小值问题，统在线性约束条件下求线性目标函数的最大值或最小值问题，统称为称为线性规划问题线性规划问题。 不等式组是一组对变量不等式组是一组对变量不等式组是一组对变量不等式组是一组对变量x x、y y的的的的约束条件约束条件约束条件约束条件，这组约束条件都是关，这组约束条件都是关，这组约束条件都是关，这组约束条件都是关于于于于x x、y y的一次不等式，所以又称为的一次不等式，所以又称为的一次不等式，所以又称为的一次不等式，所以又称为线性约束条件线性约束条件线性约束条件线性约束条件 。 由所有可行解组成的集合由所有可
4、行解组成的集合叫做叫做可行域可行域。使目标函数取得最大值或最小值的可行解叫做这使目标函数取得最大值或最小值的可行解叫做这个问题的个问题的最优解最优解。可行域可行域可行解可行解最优解最优解xyox-4y=-3x=1C3.设z z2 2+ +, ,式中变量、满足下列条件 ， 求的最大值和最小值。3x+5y253x+5y25x-4y-3x-4y-3x1x1B3x+5y=25问题问题 1: 将z z2 2+ +变形?问题问题 2: z几何意义是_。斜率为斜率为-2的直线在的直线在y轴上的截距轴上的截距 则直线 l： 2 2+ +=z=z是一簇与 l0平行的直线,故 直线 l 可通过平移直线l0而得，当
5、直 线往右上方平移时z 逐渐增大： 当l 过点 B(1,1)时,z 最小,即zmin=3 当l 过点A(5,2)时，最大,即 zmax25+212 。 析析: 作直线l0 ：2 2+ +=0 ,=0 , -2-2+ z+ z8设设z=2x+y,求满足求满足时时,求求z的最大值和最小值的最大值和最小值.线性目线性目标函数标函数线性约线性约束条件束条件线性规线性规划问题划问题任何一个满足任何一个满足不等式组的不等式组的（x,yx,y）可行解可行解可行域可行域所有的所有的最优解最优解目标函数所表目标函数所表示的几何意义示的几何意义在在y轴上轴上的截距或其相的截距或其相反数。反数。9三.例题例例1 解
6、下列线性规划问题： 求z=2x+y的最大值和最小值，使式中x、y满足下列条件：探索结论2x+y=02x+y=-32x+y=3答案：当x=-1,y=-1时，z=2x+y有最小值3.当x=2,y=-1时，z=2x+y有最大值3.5 5y yX X0 01 12 23 34 46 67 71 12 23 34 45 5x-4y+3=0x-4y+3=03x+5y-25=03x+5y-25=0x=1x=1，求求z的最大的最大值和最小和最小值.2x-y=02x-y=0B B B BA A A AC C C C代入点代入点B B得最大为得最大为8 8，代入点，代入点A A得得最小值为最小值为 . .3X+5
7、y 253X+5y 25 例例2. 2. 设z=2xz=2xy y，变量量x x、y y满足下列条件足下列条件 X-4y -3X-4y -3X 1X 1A（1，4.4） B（5，,2）C（1,1）解线性规划问题的步骤：解线性规划问题的步骤： （2 2）移：在线性目标函数所表示的一组平行）移：在线性目标函数所表示的一组平行 线中，利用平移的方法找出与可行域有公共线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；点且纵截距最大或最小的直线； （3 3）求：通过解方程组求出最优解；）求：通过解方程组求出最优解； （4 4）答：作出答案。）答：作出答案。 （1 1）画：画出线性约束条件
8、所表示的可行域；）画：画出线性约束条件所表示的可行域；练习练习1已知已知求求z=2x+y的最大值和最小值。的最大值和最小值。13551Oxyy-x=0x+y-1=01-1y+1=0A(2,-1)B(-1,-1)y=xy= 1x= 2x+ 2y-2=0Oyx15例例3: 某工厂用某工厂用A,B两种配件生产甲两种配件生产甲, ,乙两种产品乙两种产品, ,每生产一件甲种产每生产一件甲种产品使用品使用4个个A配件耗时配件耗时1h,每生产一件乙种产品使用每生产一件乙种产品使用4个个B配件耗时配件耗时2h,该厂每天最多可从配件厂获得该厂每天最多可从配件厂获得16个个A配件和配件和12个个B配件配件, ,按
9、每天工作按每天工作8小时小时计算计算, ,该厂所有可能的日生产安排是什么该厂所有可能的日生产安排是什么? 若生产若生产1件甲种产品获利件甲种产品获利2万元万元,生产生产1 件乙件乙种产品获利种产品获利3万元万元,采用哪种生产安排利润最大采用哪种生产安排利润最大?把例把例3的有关数据列表表示如下的有关数据列表表示如下:32利润利润( (万元万元) )821所需时间所需时间1240B种配件种配件1604A种配件种配件资源限额资源限额 乙产品乙产品 (1件件)甲产品甲产品 (1件件)产产品品消消 耗耗 量量资资 源源160xy4348将上面不等式组表示成平面上的区域将上面不等式组表示成平面上的区域,
10、 ,区域内区域内所有坐标为整数的点所有坐标为整数的点P(x,y),安排生产任务安排生产任务x,y都是有意义的都是有意义的.解：设甲解：设甲, ,乙两种产品分别生产乙两种产品分别生产x,y件件, ,由己知条件可得由己知条件可得:问题：问题：求利润求利润2x+3y的最大值的最大值.线线性性约约束束条条件件17若设利润为若设利润为z,则则z=2x+3y,这样上述问题转化为这样上述问题转化为:当当x,y在满足上述约束条件时在满足上述约束条件时,z的最大值为多少的最大值为多少?当点当点P在可允许的取值范围变化时在可允许的取值范围变化时,180xy4348M（4，2）问题：问题：求利润求利润z=2x+3y
11、的最大值的最大值.例例4、营养学家指出，成人良好的日常饮食应该至少提、营养学家指出，成人良好的日常饮食应该至少提供供0.075kg的碳水化合物，的碳水化合物，0.06kg的蛋白质，的蛋白质，0.06kg的脂肪，的脂肪，1kg食物食物A含有含有0.105kg碳水化合物，碳水化合物，0.07kg蛋白质，蛋白质，0.14kg脂肪，花费脂肪，花费28元；而元；而1kg食物食物B含有含有0.105kg碳水化合物，碳水化合物，0.14kg蛋白质，蛋白质，0.07kg脂肪，脂肪，花费花费21元。为了满足营养专家指出的日常饮食要求，元。为了满足营养专家指出的日常饮食要求，同时使花费最低，需要同时食用食物同时使
12、花费最低，需要同时食用食物A和食物和食物B多少多少kg？分析：将已知数据列成表格分析：将已知数据列成表格食物kg碳水化合物kg蛋白质/kg脂肪kgA0.1050.070.14B0.1050.140.07解：设每天食用解：设每天食用xkg食物食物A，ykg食物食物B，总成本为，总成本为z，那么，那么目标函数为：目标函数为：z28x21y作出二元一次不等式组所表示的平面区域，即可行域作出二元一次不等式组所表示的平面区域，即可行域1、列、列把目标函数把目标函数z28x21y 变形为变形为xyo/ 575/76/73/73/76/7 它表示斜率为它表示斜率为 纵截纵截距随距随z变化的一组平行变化的一组
13、平行直线直线 是直线在是直线在y轴上轴上的截距，当截距最的截距，当截距最小时，小时，z的值最小。的值最小。M如图可见，当直线如图可见，当直线z28x21y 经过可行经过可行域上的点域上的点M时，纵截距时，纵截距最小，即最小，即z最小。最小。2、画、画3 3、移移M点是两条直线的交点，解方程组点是两条直线的交点，解方程组得得M点的坐标为：点的坐标为：所以所以zmin28x21y16 由此可知，每天食用食物由此可知，每天食用食物A143g，食物，食物B约约571g，能够满足日常饮食要求，又使花费最低，能够满足日常饮食要求，又使花费最低，最低成本为最低成本为16元。元。4 4、求求5 5、答答（3
14、3）移：）移：在线性目标函数所表示的一组平行线在线性目标函数所表示的一组平行线 中，利用平移的方法找出与可行域有公共点且使最中，利用平移的方法找出与可行域有公共点且使最大或最小成立的直线大或最小成立的直线; ; （4 4）求：）求：通过解方程组求出最优解；通过解方程组求出最优解； （5 5）答：）答：作出答案。作出答案。 （2 2）画：）画：画出线性约束条件所表示的可行域；画出线性约束条件所表示的可行域；（1 1）列：）列：根据题意列出线性约束条件及目标函数；根据题意列出线性约束条件及目标函数； 解线性规划问题的步骤：解线性规划问题的步骤：五步法：五步法：“列列. .画画. .移移. .求求.
15、 .答答” 方法归纳24四四. .练习练习某工厂生产甲、乙两种产品，生产某工厂生产甲、乙两种产品，生产1t甲种产品需要甲种产品需要A种原料种原料4t、 B种原料种原料12t，产生的利润为，产生的利润为2万元；生产万元；生产1t乙种产品需要乙种产品需要A种原料种原料1t、 B种原料种原料9t，产生的利润，产生的利润为为1万元。现有库存万元。现有库存A种原料种原料10t、 B种原料种原料60t，如何安，如何安排生产才能使利润最大？排生产才能使利润最大？相关数据列表如下：相关数据列表如下：A种原料 B种原料利润甲种产品4 122 乙种产品1 9 1现有库存10 60 25设生产甲、乙两种产品的吨数设生产甲、乙两种产品的吨数分别为分别为x、y利润利润何时达到最大？何时达到最大？五五. .课时小结课时小结简单的线性规划简单的线性规划约束条件约束条件目标函数目标函数可行解可行解可行域可行域最优解最优解求解方法：列画、求解方法：列画、移、求、答移、求、答1. 阅读教科书阅读教科书P.87-P.88；2. 教科书教科书P.91面练习第面练习第1题题(2)；3.预习预习P.89-P.90六六.课外作业课外作业课后练习
