3.3.2简单的线性规划问题ppt.ppt

1、3简单的线性规划问题日生产日生产满足满足4 40 02 2乙产品乙产品0 04 41 1甲产品甲产品B B配件配件（个）（个）A A配件配件（个）（个）每件耗时每件耗时（h h）12816如果若干年后的你成为某如果若干年后的你成为某工厂的厂长，你将会面对工厂的厂长，你将会面对生产安排、资源利用、人生产安排、资源利用、人力调配的问题力调配的问题【引例引例】：某工厂用某工厂用A A、B B两种配两种配件生产甲、乙两种产件生产甲、乙两种产品，每生产一件甲产品，每生产一件甲产品使用品使用4 4个个A A配件并耗配件并耗时时1h1h，每生产一件乙，每生产一件乙产品使用产品使用4 4个个B B配件并配件并

2、耗时耗时2h2h，该厂每天最，该厂每天最多可从配件厂获得多可从配件厂获得1616个个A A配件和配件和1212个个B B配件，配件，按每天工作按每天工作8h8h计算，计算，该厂所有可能的日生该厂所有可能的日生产安排是什么？产安排是什么？248642将上述不等式组表示成平面上的区域，图中的阴影部将上述不等式组表示成平面上的区域，图中的阴影部分中的分中的整点整点（坐标为整数的点坐标为整数的点）就代表所有可能的日）就代表所有可能的日生产安排，即当点生产安排，即当点P（x,y)在上述平面区域中时，所在上述平面区域中时，所安排的生产任务安排的生产任务x,y才有意义。才有意义。248642【进一步进一步】

3、：若生产一件甲产若生产一件甲产品获利品获利2 2万元，生万元，生产一件乙产品获产一件乙产品获利利3 3万元，采用哪万元，采用哪种生产安排获得种生产安排获得利润最大？利润最大？M M(4 4,2 2)233zyx 23zxy若设利润为若设利润为z,则则z=2x+3y,这样上述问题转化为这样上述问题转化为:当当x,y在满足上述二元一次不等式组且为非负整在满足上述二元一次不等式组且为非负整数时数时,z的最大值为多少的最大值为多少?,2z22z2把把z=2x+3yz=2x+3y变变形形为为y=-x+,y=-x+,这这是是斜斜率率为为-333333z z在在y y轴轴上上的的截截距距为为的的直直线线,3

4、 3当点当点P在可允许的取值范围变化时在可允许的取值范围变化时,z z求求截截距距的的最最大大值值,即即可可得得z z的的最最大大值值.3 32841641200 xyxyxy 0 xy4348233zyx M（4，2）142yx 问题：问题：求利润求利润z=2x+3y的最大值的最大值.143224max Z变式：变式：若生产一件甲产品获利若生产一件甲产品获利1万元万元，生产一件乙生产一件乙产品获利产品获利3万元万元，采用哪种生产安排利润最大？采用哪种生产安排利润最大？2841641200 xyxyxy 0 xy4348133zyx N N（2 2，3 3）142yx 变式：变式：求利润求利润

5、z=x+3y的最大值的最大值.max23 311z 二、基本概念二、基本概念yx4843o 把求最大值或求最小值的函数称为把求最大值或求最小值的函数称为目标函数目标函数，因为，因为它是关于变量它是关于变量x、y的一次解析式，又称的一次解析式，又称线性目标函数线性目标函数。满足线性约束的解满足线性约束的解（x x，y y）叫做）叫做可行解可行解。在线性约束条件下求线性目标函数的最大值或最小值在线性约束条件下求线性目标函数的最大值或最小值问题，统称为问题，统称为线性规划问题线性规划问题。一组关于变量一组关于变量x、y的一次不等式，称为的一次不等式，称为线性约束条线性约束条件。件。由所有可行解组成由

6、所有可行解组成的集合叫做的集合叫做可行域可行域。使目标函数取得最大值或最小值的可行解叫使目标函数取得最大值或最小值的可行解叫做这个问题的做这个问题的最优解最优解。可行域可行域可行解可行解最优解最优解1.约束条件要写全约束条件要写全;3.解题格式要规范解题格式要规范.2.作图要准确作图要准确,计算也要准确计算也要准确;注意注意:归纳总结：归纳总结：简单线性规划问题的求解步骤：简单线性规划问题的求解步骤：1、将已知数据列成表格形式，设出、将已知数据列成表格形式，设出x、y、z；2、找出约束条件和目标函数；、找出约束条件和目标函数；3、作出可行域，并结合图象求出最优解、作出可行域，并结合图象求出最优

7、解4、按照题意作答。、按照题意作答。转化转化转化转化转化转化四个步骤四个步骤：1。画画（画可行域）（画可行域）三个转化三个转化4。答答（求出点的坐标，并转化为最优解）（求出点的坐标，并转化为最优解）3。移移（平移直线（平移直线L。寻找使纵截距取得最值时的点）。寻找使纵截距取得最值时的点）2。作作（作（作z=Ax+By=0时的直线时的直线L。）。）图解法图解法线性约束条件线性约束条件可行域可行域线性目标函数线性目标函数Z=Ax+By一组平行线一组平行线BZxy最优解最优解寻找平行线组的寻找平行线组的 最大（小）纵截距最大（小）纵截距例例5、营养学家指出，成人良好的日常饮食应该至少提、营养学家指出

8、，成人良好的日常饮食应该至少提供供0.075kg的碳水化合物，的碳水化合物，0.06kg的蛋白质，的蛋白质，0.06kg的脂肪，的脂肪，1kg食物食物A含有含有0.105kg碳水化合物，碳水化合物，0.07kg蛋白质，蛋白质，0.14kg脂肪，花费脂肪，花费28元；而元；而1千克食物千克食物B含有含有0.105kg碳水化合物，碳水化合物，0.14kg蛋白质，蛋白质，0.07kg脂肪，脂肪，花费花费21元。为了满足营养专家指出的日常饮食要求，元。为了满足营养专家指出的日常饮食要求，同时使花费最低，需要同时食用食物同时使花费最低，需要同时食用食物A和食物和食物B多少多少kg？食物食物kg碳水化合物

9、碳水化合物kg蛋白质蛋白质/kg脂肪脂肪kgA0.1050.070.14B0.1050.140.07分析：将已知数据列成表格分析：将已知数据列成表格三、例题三、例题解：设每天食用解：设每天食用xkg食物食物A，ykg食物食物B，总成本为，总成本为z，那么那么0.1050.1050.0757750.070.140.0671460.140.070.0614760000 xyxyxyxyxyxyxxyy目标函数为：目标函数为：z28x21y作出二元一次不等式组所表示的平面区域，即可行域作出二元一次不等式组所表示的平面区域，即可行域把目标函数把目标函数z28x21y 变形为变形为xyo5/75/76/

10、73/73/76/72834zxy 它表示斜率为它表示斜率为随随z变化的一组平行直变化的一组平行直线系线系34 是直线在是直线在y轴上轴上的截距，当截距最的截距，当截距最小时，小时，z的值最小。的值最小。28zM 如图可见，当直线如图可见，当直线z28x21y 经过可经过可行域上的点行域上的点M时，截距时，截距最小，即最小，即z最小。最小。7757146147600 xyxyxyxyM点是两条直线的交点，解方程组点是两条直线的交点，解方程组6714577yxyx得得M点的坐标为：点的坐标为：7471yx所以所以zmin28x21y16 由此可知，每天食用食物由此可知，每天食用食物A143g，食

11、物，食物B约约571g，能够满足日常饮食要求，又使花费最低，能够满足日常饮食要求，又使花费最低，最低成本为最低成本为16元。元。例例6 要将两种大小不同规格的钢板截成要将两种大小不同规格的钢板截成A、B、C三种规格，三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示每张钢板可同时截得三种规格的小钢板的块数如下表所示：解：解：设需截第一种钢板设需截第一种钢板x张，第一种钢板张，第一种钢板y张，则张，则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y15,x+2y18,x+3y27,x0,y0 作出可行域（如图）

12、作出可行域（如图）目标函数为目标函数为 z=x+y今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，18，27块，问块，问各截这两种钢板多少张可得所需三种规格成品，且使所各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。用钢板张数最少。X张张y张张xNyNx0y2x+y=15x+3y=27x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,xNy0 yN直线直线x+y=12经过的经过的整点是整点是B(3,9)和和C(4,8)，它们是最优解，它们是最优解.作出一组平行直线作出一组平行直线z=x+y，目标函数目标函数z=x+yB(3,9)C(4,

13、8)A(18/5,39/5)当直线经过点当直线经过点A时时z=x+y=11.4,x+y=12解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)调整优值法调整优值法2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）x0y2x+y=15x+3y=27x+2y=18x+y=02x+y15,x+2y18,x+3y27,x0,xNy0 yN经过可行域内的整点经过可行域内的整点B(3,9)和和C(4,8)时，时，t=x+y=12是最优解是最优解.答答:(略略)作出一组平行直线作出一组平行直线t=x+y，目标函数目标函数t=x+

14、yB(3,9)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解但它不是最优整数解，将直线将直线x+y=11.4继续向上平移继续向上平移，1212182715978例例7 7、一个化肥厂生产甲、乙两种混合肥料，生产、一个化肥厂生产甲、乙两种混合肥料，生产1 1车车皮甲种肥料的主要原料是磷酸盐皮甲种肥料的主要原料是磷酸盐4t4t、硝酸盐、硝酸盐18t18t；生产；生产1 1车皮乙种肥料需要的主要原料是磷酸盐车皮乙种肥料需要的主要原料是磷酸盐1t1t、硝酸盐、硝酸盐15t15t。

15、现库存磷酸盐。现库存磷酸盐10t10t、硝酸盐、硝酸盐66t66t，在此基础上生产，在此基础上生产这两种混合肥料。若生产这两种混合肥料。若生产1 1车皮甲种肥料利润为车皮甲种肥料利润为1000010000元；生产元；生产1 1车皮乙种肥料利润为车皮乙种肥料利润为50005000元。分别生产甲、元。分别生产甲、乙两种肥料各多少车皮，能够产生最大的利润？乙两种肥料各多少车皮，能够产生最大的利润？解：设解：设x、y分别为计划生产甲、乙两种混合分别为计划生产甲、乙两种混合肥料的车皮数，于是满足以下条件：肥料的车皮数，于是满足以下条件：xyo0y0 x6615y18x10y4x解：设生产甲种肥料解：设生

16、产甲种肥料x车皮、乙种肥料车皮、乙种肥料y车皮，能够产车皮，能够产生利润生利润Z万元。目标函数为万元。目标函数为Zx0.5y，可行域如图：，可行域如图：把把Zx0.5y变形为变形为y2x2z，它表示斜率为，它表示斜率为2，在，在y轴上的截距为轴上的截距为2z的一组直线系。的一组直线系。xyo由图可以看出，当直线经过可行域上的点由图可以看出，当直线经过可行域上的点M时，时，截距截距2z最大，即最大，即z最大。最大。故生产甲种、乙种肥料各故生产甲种、乙种肥料各2车皮，能够产生最大利润，车皮，能够产生最大利润，最大利润为最大利润为3万元。万元。M 容易求得容易求得M点的坐标为点的坐标为（2，2），则

17、），则Zmin30y0 x6615y18x10y4xP91 练习 1P91 练习 2确定最优整数解的方法：确定最优整数解的方法：1若可行域的若可行域的“顶点顶点”处恰好为整点，那么它就是优解；处恰好为整点，那么它就是优解；（在包括边界的情况下）（在包括边界的情况下）2若可行域的若可行域的“顶点顶点”不是整点或不包括边界时，可以不是整点或不包括边界时，可以采用网格法，即先在可行域内打网格、描整点、平移直采用网格法，即先在可行域内打网格、描整点、平移直线线l、最先经过或最后经过的整点坐标是整数最优解；这、最先经过或最后经过的整点坐标是整数最优解；这种方法依赖作图，所以作图应尽可能精确，图上操作尽种方法依赖作图，所以作图应尽可能精确，图上操作尽可能规范可能规范归纳总结：归纳总结：二元一次不等式二元一次不等式表示平面区域表示平面区域直线定界，直线定界，特殊点定域特殊点定域简单的线性规划简单的线性规划约束条件约束条件目标函数目标函数可行解可行解可行域可行域最优解最优解应用应用求解方法：画、求解方法：画、移、求、答移、求、答小结小结: