简单线性规划课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,1947G.B.Dantzig,提出,是近一百年来最成功的,10,个算法之一,.,简单线性规划,x,y,o,1947G.B.Dantzig提出,是近一百年来最成功的10,1,5,5,x=1,x-4y+3=0,3x+5y-25=0,1,A,B,C,C:,(1.00,4.40),A:,(5.00,2.00),B:,(1.00,1.00),O,x,y,问题,1,：,x,有无最大（小）值？,问题,2,：,y,有无最大（小）值？,问题,3,：,2,x,+,y,有无最大（小）值？,55x=1x-4y+3=03x+5y-25=01ABCC:,2,一、实际问题,某工厂用,A、B,两种配件生产甲、乙两种产品，每生产一件甲产品使用4个,A,配件耗时1,h，,每生产一件乙产品使用4个,B,配件耗时2,h，,该厂每天最多可从配件厂获得16个,A,配件和12个,B,配件，按每天工作8,h,计算，该厂所有可能的日生产安排是什么？,按甲、乙两种产品分别生产,x、y,件，由已知条件可得二元一次不等式组,一、实际问题 某工厂用A、B两种配件生产甲、乙两,3,将上述不等式组表示成平面上的区域，图中的阴影部分中的整点（坐标为整数）就代表所有可能的日生产安排。,y,x,4,8,4,3,o,若生产一件甲产品获利2万元，生产一件乙产品获利3万元，采用那种生产安排利润最大？,设工厂获得的利润为,z，,则,z2x3y,把,z2x3y,变形为,它表示斜率为 的直线系，,z,与这条直线的截距有关。,如图可见，当直线,经过可行域上的点,M,时，截距最大，即,z,最大。,M,将上述不等式组表示成平面上的区域，图中的阴影部分中,4,探究：,1,.,在上述问题中，如果生产一件甲产品获利,3,万元，每生产一件乙产品获利,2,万元，有应当,如何安排生产才能获得最大利润？在换几组数,据试试。,2.,有上述过程，你能得出最优解与可行域之间,的关系吗,？,探究：1.在上述问题中，如果生产一件甲产品获利32.有上述,5,二、基本概念,y,x,4,8,4,3,o,把求最大值或求最小值的的函数称为目标函数，因为它是关于变量,x、y,的一次解析式，又称线性目标函数。,满足线性约束的解,（,x，y）,叫做可行解。,在线性约束条件下求线性目标函数的最大值或最小值问题，统称为线性规划问题。,一组关于变量,x、y,的一次不等式，称为线性约束条件。,由所有可行解组成的集合叫做可行域。,使目标函数取得最大值或最小值的可行解叫做这个问题的最优解。,可行域,可行解,最优解,二、基本概念yx4843o 把求最大值或求,6,例1、营养学家指出，成人良好的日常饮食应该至少提供0.075,kg,的碳水化合物，0.06,kg,的蛋白质，0.06,kg,的脂肪，1,kg,食物,A,含有0.105,kg,碳水化合物，0.07,kg,蛋白质，0.14,kg,脂肪，花费28元；而1食物,B,含有0.105,kg,碳水化合物，0.14,kg,蛋白质，0.07,kg,脂肪，花费21元。为了满足营养专家指出的日常饮食要求，同时使花费最低，需要同时食用食物,A,和食物,B,多少,kg？,食物,kg,碳水化合物,kg,蛋白质/,kg,脂肪,kg,A,0.105,0.07,0.14,B,0.105,0.14,0.07,分析：将已知数据列成表格,三、例题,例1、营养学家指出，成人良好的日常饮食应该至少提供0.075,7,解：设每天食用,xkg,食物,A，ykg,食物,B，,总成本为,z，,那么,目标函数为：,z28x21y,作出二元一次不等式组所表示的平面区域，即可行域,解：设每天食用xkg食物A，ykg食物B，总成本为z，那么目,8,把目标函数,z28x21y,变形为,x,y,o,5/7,5/7,6/7,3/7,3/7,6/7,它表示斜率为,随,z,变化的一组平行直线系,是直线在,y,轴上的截距，当截距最小时，,z,的值最小。,M,如图可见，当直线,z28x21y,经过可行域上的点,M,时，截距最小，即,z,最小。,把目标函数z28x21y 变形为xyo5/75/76/7,9,M,点是两条直线的交点，解方程组,得,M,点的坐标为：,所以,z,min,28x21y16,由此可知，每天食用食物,A143g，,食物,B,约571,g，,能够满足日常饮食要求，又使花费最低，最低成本为16元。,M点是两条直线的交点，解方程组得M点的坐标为：所以zmin,10,四、练习题,：,1、,求,z2xy,的最大值，使,x、y,满足约束条件,：,2、,求,z3x5y,的最大值，使,x、y,满足约束条件：,四、练习题：1、求z2xy的最大值，使x、y满足约束条件,11,解：作出可行域,x,y,A,B,C,x,y,o,o,A,B,C,作出直线,y=2xz,的图像，可知,z,要求最大值，即直线经过,C,点时。,求得,C,点坐标为（2，1），则,Z,max,=2xy3,作出直线,3x5y,z,的图像，可知直线经过,A,点时，,Z,取最大值；直线经过,B,点时，,Z,取最小值。,求得,A（1.5，2.5），B（2，1），,则,Zmax=17，Z,min,=11。,解：作出可行域xyABCxyooABC 作出直线y=2,12,解线性规划问题的步骤：,（,2,）移：在线性目标函数所表示的一组平行 线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；,（,3,）求：通过解方程组求出最优解；,（,4,）答：作出答案。,（,1,）画：画出线性约束条件所表示的可行域；,解线性规划问题的步骤：（2）移：在线性目标函数所表示的一组,13,几个结论：,1,、线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界处取得。,2,、求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义,在,y,轴上的截距或其相反数。,几个结论：1、线性目标函数的最大（小）值一般在可行域的顶点处,14,五、作业：,习题3.3,A,组 3、4,五、作业：习题3.3,15,