《3.3.2-简单的线性规划问题-PPT课件》由会员分享,可在线阅读,更多相关《3.3.2-简单的线性规划问题-PPT课件(19页珍藏版)》请在金锄头文库上搜索。
1、xyo如果若干年后的你成为某如果若干年后的你成为某工厂的厂长,你将会面对工厂的厂长,你将会面对生产安排、资源利用、人生产安排、资源利用、人力调配的问题力调配的问题数据分析表:数据分析表:日生产日生产满足满足4 40 02 2乙产品乙产品0 04 41 1甲产品甲产品B B配件配件(个)(个)A A配件配件(个)(个)每件耗时每件耗时(h h)【引例】:【引例】:某工厂用某工厂用A A、B B两种配两种配件生产甲、乙两种产件生产甲、乙两种产品,每生产一件甲产品,每生产一件甲产品使用品使用4 4个个A A配件并耗配件并耗时时1h1h,每生产一件乙,每生产一件乙产品使用产品使用4 4个个B B配件并
2、配件并耗时耗时2h2h,该厂每天最,该厂每天最多可从配件厂获得多可从配件厂获得1616个个A A配件和配件和1212个个B B配件,配件,按每天工作按每天工作8h8h计算,计算,该厂所有可能的日生该厂所有可能的日生产安排是什么?产安排是什么? 248642【引例】:【引例】:某工厂用某工厂用A A、B B两种配件生两种配件生产甲、乙两种产品,每生产甲、乙两种产品,每生产一件甲产品使用产一件甲产品使用4 4个个A A配配件并耗时件并耗时1h1h,每生产一件,每生产一件乙产品使用乙产品使用4 4个个B B配件并耗配件并耗时时2h2h,该厂每天最多可从,该厂每天最多可从配件厂获得配件厂获得1616个
3、个A A配件和配件和1212个个B B配件,按每天工作配件,按每天工作8h8h计算,该厂所有可能的计算,该厂所有可能的日生产安排是什么?日生产安排是什么? 【进一步】:【进一步】:若生产一件甲产若生产一件甲产品获利品获利2 2万元,万元,生产一件乙产品生产一件乙产品获利获利3 3万元,采万元,采用哪种生产安排用哪种生产安排获得利润最大?获得利润最大? 将上述不等式组表示成平面上的区域,图中的阴影部分中的整点(坐标为整数的点)就代表所有可能的日生产安排,即当点P(x, y)在上述平面区域中时,所安排的生产任务x, y才有意义。若设利润为若设利润为z,则则z=2x+3y,这样上述问题转化为这样上述
4、问题转化为:当当x, y在满足上述约束条件时在满足上述约束条件时,z的最大值为多少的最大值为多少?248642【进一步】:【进一步】:若生产一件甲产若生产一件甲产品获利品获利2 2万元,生万元,生产一件乙产品获产一件乙产品获利利3 3万元,采用哪万元,采用哪种生产安排获得种生产安排获得利润最大?利润最大? 由上图可以看出,经过直线x=4与直线x+2y-8=0的交点M(4,2)时,截距 的值最大,最大值为 ,这时2x+3y=14.所以,每天生产甲产品4件,乙产品2件时,工厂可获得最大利润14万元。yx4843o求最大值或求最小值的的函数称为求最大值或求最小值的的函数称为目标函数目标函数,因为它是
5、,因为它是关于变量关于变量 x、y 的一次解析式,又称的一次解析式,又称线性目标函数线性目标函数。 满足线性约束的解满足线性约束的解(x,y)叫做叫做可行解可行解。在线性约束条件下求线性目标函数的最大值或最小值问在线性约束条件下求线性目标函数的最大值或最小值问题,统称为题,统称为线性规划问题线性规划问题。关于变量关于变量 x、y 的一次不等式,称为的一次不等式,称为线性约束条件线性约束条件。由所有可行解组成的集由所有可行解组成的集合叫做合叫做可行域可行域。使目标函数取得最大值或最小值的可行解叫做这使目标函数取得最大值或最小值的可行解叫做这个问题的个问题的最优解最优解。可行域可行域可行解可行解最
6、优解最优解简单的线性规划问题基本概念简单的线性规划问题基本概念248642【变式【变式1 1】:】:若生产一件甲产若生产一件甲产品获利品获利1 1万元,生万元,生产一件乙产品获产一件乙产品获利利3 3万元,采用哪万元,采用哪种生产安排获得种生产安排获得利润最大?利润最大? 由上图可以看出,经过直线 y=3 与直线 x+2y-8=0 的交点N(2,3)时,截距 的值最大,最大值为 ,这时x+3y=11.所以,每天生产甲产品2件,乙产品3件时,工厂可获得最大利润11万元。248642【变式【变式2 2】:】:若生产一件甲产若生产一件甲产品获利品获利1 1万元,生万元,生产一件乙产品获产一件乙产品获
7、利利2 2万元,采用哪万元,采用哪种生产安排获得种生产安排获得利润最大?利润最大? 实际问题实际问题线性规划问题线性规划问题列列出约束条件出约束条件建建立目标函数立目标函数分析问题分析问题(列表列表)设设立变量立变量转转化化列约束条件时要注意到变量的范围列约束条件时要注意到变量的范围.注意注意: :解解决决问题问题最最优优解解线性规划问题解题步骤:线性规划问题解题步骤:转化转化转化转化转化转化四个步骤四个步骤:1. 画画(画可行域)(画可行域)三个转化三个转化4. 答答(求出点的坐标,并转化为最优解)(求出点的坐标,并转化为最优解)3. 移移(平移直线(平移直线L ,寻找使纵截距取得最值时的点
8、)寻找使纵截距取得最值时的点)2. 作作(作(作Z=Ax + By=0时的直线时的直线 L )图图解解法法线性约束条件线性约束条件可行域可行域线性目标函数线性目标函数Z =Ax + By一组平行线一组平行线最优解最优解寻找平行线组的寻找平行线组的 最大(小)纵截距最大(小)纵截距练习练习 1 1 解下列线性规划问题:求 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.xOy练习练习 2 2 解下列线性规划问题:求 z=3x+5y 的最大值和最小
9、值,使式中 x、y 满足下列条件:当 时, 有最大值答案:当 时, 有最小值xOy练习练习 2 2(变式)(变式) 解下列线性规划问题:求 z=3x-5y 的最大值和最小值,使式中 x、y 满足下列条件:当 时, 有最大值答案:当 时, 有最小值例例1、营养学家指出,成人良好的日常饮食应该至少提、营养学家指出,成人良好的日常饮食应该至少提供供0.075kg的碳水化合物,的碳水化合物,0.06kg的蛋白质,的蛋白质,0.06kg的脂肪,的脂肪,1kg食物食物A含有含有0.105kg碳水化合物,碳水化合物,0.07kg蛋白质,蛋白质,0.14kg脂肪,花费脂肪,花费28元;而元;而1千克食物千克食
10、物B含有含有0.105kg碳水化合物,碳水化合物,0.14kg蛋白质,蛋白质,0.07kg脂肪,脂肪,花费花费21元。为了满足营养专家指出的日常饮食要求,元。为了满足营养专家指出的日常饮食要求,同时使花费最低,需要同时食用食物同时使花费最低,需要同时食用食物A和食物和食物B多少多少kg?食物kg碳水化合物kg蛋白质/kg脂肪kgA0.1050.070.14B0.1050.140.07分析:将已知数据列成表格分析:将已知数据列成表格三、例题三、例题解:设每天食用解:设每天食用x kg食物食物A,y kg 食物食物B,总成本为,总成本为z,那么,那么目标函数为:目标函数为:z 28x21y作出二元
11、一次不等式组所表示的平面区域,即可行域作出二元一次不等式组所表示的平面区域,即可行域把目标函数把目标函数 z28x21y 变形为变形为xyo5/75/76/73/73/76/7 它表示斜率为它表示斜率为随随 z 变化的一组平行直变化的一组平行直线系线系 是直线在是直线在 y 轴上轴上的截距,当截距最小的截距,当截距最小时,时,z的值最小。的值最小。M 如图可见,当直线如图可见,当直线z28x21y 经过可行经过可行域上的点域上的点M时,截距最时,截距最小,即小,即 z 最小。最小。M点是两条直线的交点,解方程组点是两条直线的交点,解方程组 得得M点的坐标为:点的坐标为:所以所以 z min28
12、x21y16 由此可知,每天食用食物由此可知,每天食用食物A143g,食物,食物B约约571g,能够满足日常饮食要求,又使花费最低,能够满足日常饮食要求,又使花费最低,最低成本为最低成本为16元。元。小结小结: :实际问题实际问题列表列表设出变量设出变量寻找约束条件寻找约束条件建立目标函数建立目标函数转化转化建模建模线性规划问题线性规划问题图解法图解法最优解最优解三三个个转转化化四个步骤四个步骤作作答答图解法图解法:1. 画画(画可行域)(画可行域)4. 答答(求出点的坐标,并转化为最优解)(求出点的坐标,并转化为最优解)3. 移移(平移直线(平移直线L ,寻找使纵截距取得最值时的点)寻找使纵截距取得最值时的点)2. 作作(作(作Z=Ax + By=0时的直线时的直线 L )课本课本93页习题页习题3.3A组组 3,4作业