简单的线性规划PPT.ppt

xyoxOyx-4y+3=0x=13x+5y-25=0ABCA:(5,2)B:(1,1)C:(1,4.4)问题问题1 1：：x 有无最大（小）值？有无最大（小）值？问题问题2 2：：y 有无最大（小）值？有无最大（小）值？问题问题3 3：：2 2x+y 有无最大（小）值？有无最大（小）值？XOYX-4y+3=0X=13x+5y-25=0ABCA:(5,2)B:(1,1)C:(1,4.4)2x+y=02x+y=1此时此时Z=3此时此时Z=12Zmax=12Zmin=3Z=2x+y有关概念有关概念(1)由由x，，y 的不等式的不等式(或方程或方程)组成的不等式组称组成的不等式组称为为x，，y 的的约束条件约束条件2)关于关于x，，y 的一次不等式或方程组成的不等式组称为的一次不等式或方程组成的不等式组称为x，，y 的的线性约束条件线性约束条件3)欲达到最大值或最小值所涉及的变量欲达到最大值或最小值所涉及的变量x，，y 的解析式称的解析式称为为目标函数目标函数关于x，，y 的一次目标函数称为的一次目标函数称为线性目标函线性目标函数数求线性目标函数性约束条件下的最大值或最小求线性目标函数性约束条件下的最大值或最小值问题称为值问题称为线性规划问题线性规划问题。

4)满足线性约束条件的解（满足线性约束条件的解（x，，y）称为）称为可行解可行解所有可行所有可行解组成的集合称为解组成的集合称为可行域可行域5)使目标函数取得最大值或最小值的可行解称为使目标函数取得最大值或最小值的可行解称为最优解最优解[练习练习]解下列线性规划问题：解下列线性规划问题：1、求、求z=2x+y的最大值，使式中的的最大值，使式中的x、、y满足约束条件：满足约束条件：xOyABCy=x x+y=1y=-12x+y=0B:(-1,-1)C:(2,-1)Zmin=-3Zmax=3 目标函数：目标函数： z=2x+y解线性规划问题的步骤：解线性规划问题的步骤： （（2 2）移：性目标函数所表示的一组平行）移：性目标函数所表示的一组平行 线中，利用平移的方法找出与可行域有公共线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；点且纵截距最大或最小的直线； （（3 3）求：通过解方程组求出最优解；）求：通过解方程组求出最优解； （（4 4）答：作出答案答：作出答案 （（1 1）画：画出线性约束条件所表示的可行域；）画：画出线性约束条件所表示的可行域；2、求、求z=3x+y的最大值，使式中的的最大值，使式中的x、、y满足约束条件满足约束条件 2x+3y 24 x-y 7 y 6 x 0 y 0讨论：讨论：XOYABCD712-768y=6x-y=72x+3y=24l0:3x+y=0l1思考：思考： 目标函数：目标函数： Z=x+3y 目标函数：目标函数： Z=3x+y 解线性规划问题的步骤：解线性规划问题的步骤： （（2 2）移：性目标函数所表示的一组平行）移：性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；点且纵截距最大或最小的直线； （（3 3）求：通过解方程组求出最优解；）求：通过解方程组求出最优解； （（4 4）答：作出答案。

答：作出答案 小结：小结：（（1 1）画：画出线性约束条件所表示的可行域；）画：画出线性约束条件所表示的可行域；结论：结论：1、线性目标函数的最大（小）值一般、线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界在可行域的顶点处取得，也可能在边界处取得2、求线性目标函数的最优解，要注意、求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义分析线性目标函数所表示的几何意义.应用问题应用问题:1．．某某工工厂厂制制造造甲甲、、乙乙两两种种产产品品，，已已知知制制造造甲甲产产品品1kg要要用用煤煤9吨吨，，电电力力4kw，，劳劳力力(按按工工作作日日计计算算)3个个；；制制造造乙乙产产品品1kg要要用用煤煤4吨吨，，电电力力5kw，，劳劳力力10个个.又又知知制制成成甲甲产产品品1kg可可获获利利7万万元元，，制制成成乙乙产产品品1kg可可获获利利12万万元元，，现现在在此此工工厂厂只只有有煤煤360吨吨，，电电力力200kw，，劳劳力力300个个，，在在这这种种条条件件下下应应生生产产甲甲、、乙乙两两种种产产品品各多少千克，才能获得最大经济效益各多少千克，才能获得最大经济效益?【【解题回顾解题回顾】】(1)用用线线性性规规划划的的方方法法解解题题的的一一般般步步骤骤是是：：设设未未知知数数、、列列出出约约束束条条件件及及目目标标函函数数、、作作出出可可行行域域、、求求出出最优解、写出答案最优解、写出答案.(2)本例的关键是分析清楚在哪一个点取最大值本例的关键是分析清楚在哪一个点取最大值. 结论：结论：用线性规划的方法解题的一般步骤是：用线性规划的方法解题的一般步骤是：(1)充充分分理理解解题题意意建建立立数数学学模模型型,也也就就是是设设未未知数、列出约束条件及目标函数知数、列出约束条件及目标函数.(2)作图作图.作出可行域、求出最优解作出可行域、求出最优解.(3)根据实际意义写出答案根据实际意义写出答案.小结：二元一次不等式二元一次不等式表示平面区域表示平面区域直线定界，直线定界，特殊点定域特殊点定域简单的线性规划简单的线性规划约束条件约束条件目标函数目标函数可行解可行解可行域可行域最优解最优解应应用用求解方法：画、求解方法：画、移、求、答移、求、答2、咖啡屋配制两种饮料，成分配比和单价如下表： 饮料饮料奶粉（杯）奶粉（杯）咖啡（杯）咖啡（杯）糖（杯）糖（杯）价格（杯）价格（杯）甲种甲种9(g)9(g)4(g)4(g)3(g)3(g)0.70.7（元）（元）乙种乙种4(g)4(g)5(g)5(g)10(g)10(g)1.21.2（元）（元） 每天使用限额为奶粉3600g,咖啡2000g,糖3000g，若每天在原料的使用限额内饮料能全部售出，应配制两种饮料各多少杯获利最大？9x+4y=36003x+10y=30004x+5y=2000O OA AB BC CD D200200正确答案：正确答案：1 1）线性约束条件为：）线性约束条件为：9x+4y≤3600 9x+4y≤3600 4x+5y≤2000 4x+5y≤2000 3x+10y≤3000x3x+10y≤3000x∈N ∈N y∈Ny∈N 当当 l l 过点过点C C时，时，y y轴截距轴截距b b最大，即最大，即z z最大最大∴∴当当x=200x=200，，y=240y=240时，时，Z Zmaxmax=0.7×200+1.2×240=428=0.7×200+1.2×240=428（（元）元） 答：每天应配制甲种饮料答：每天应配制甲种饮料200200杯，乙种饮料杯，乙种饮料240240杯时，杯时，获利最大。

获利最大3x+10y=3000 y=2403x+10y=3000 y=240 解解 4x+5y=2000 4x+5y=2000 得得 x=200x=200∴ ∴ C(200,240)C(200,240)l l说明：约束条件要写全，求解过程要细心，说明：约束条件要写全，求解过程要细心，解题格式要规范解题格式要规范 z=0.7x+1.2y z=0.7x+1.2y 目标函数：目标函数：y yx x三、最优整数解的求解方法三、最优整数解的求解方法:•（一）运用枚举验证求最优整数解（一）运用枚举验证求最优整数解某人有楼房一幢，室内面积共某人有楼房一幢，室内面积共180m2，拟分隔成，拟分隔成两类房间作为旅游客房大房间每间面积为两类房间作为旅游客房大房间每间面积为18m2，可住游客，可住游客5名，每名游客每天住宿费为名，每名游客每天住宿费为40元；小房间每间面积为元；小房间每间面积为15m2，可住游客，可住游客3名，名，每名游客每天住宿费为每名游客每天住宿费为50元；装修大房间每间元；装修大房间每间需需1000元，装修小房间每间需元，装修小房间每间需600元。

如果他元如果他只能筹款只能筹款8000元用于装修，且游客能住满客房，元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最他应隔出大房间和小房间各多少间，能获得最大收益？最大收益是多少？大收益？最大收益是多少？这些整点有这些整点有:(0，，12),(1，，10),(2，，9),(3，，8),(4，，6),(5，，5)，，(6，，3),(7，，1),(8，，0),分别代入分别代入f=200x+150y，，逐一验证，可得取整点逐一验证，可得取整点(0,12)或或(3,8)时时,fmax=200×0+150×12=200×3+150×8=1800(元元)所以要获得最大收益，有两种方案：所以要获得最大收益，有两种方案：Ⅰ.只隔出小房间只隔出小房间12间；间；Ⅱ.隔出大房间隔出大房间3间，小房间间，小房间8间最大收益为最大收益为1800元•（二）运用平移直线法求最优整数解（二）运用平移直线法求最优整数解 某人准备用某人准备用100元购买空白磁盘和空白光元购买空白磁盘和空白光盘，空白磁盘每张盘，空白磁盘每张4元，空白光盘每张元，空白光盘每张7元问他应该如何购买才能达到磁盘和元问他应该如何购买才能达到磁盘和光盘都购买并且都不超过光盘都购买并且都不超过10张，而又使张，而又使得剩余的钱最少这个目的？得剩余的钱最少这个目的？为了寻找整数解，我们在可行域里作出最靠近为了寻找整数解，我们在可行域里作出最靠近4x+7y=100且与之平行的直线且与之平行的直线4x+7y=99。

这时，得到如图的可行解这时，得到如图的可行解P(7.25,10)和和Q(10,8.43)，，但它们都不是整数解，考虑线段但它们都不是整数解，考虑线段PQ上的点上的点(8,9.57)和和(9,9)，可知，可知(9,9)是整数最优解是整数最优解练习、已知函数练习、已知函数f(x)=axf(x)=ax2 2-c-c，，满足满足-4≤-4≤f(1)≤-f(1)≤-1,1, -1≤f(2)≤5, -1≤f(2)≤5,求求f(3)f(3)的取值范围的取值范围 -4≤-4≤f(1)≤-1 f(1)≤-1 -4≤a--4≤a-c≤-1 0≤a≤3c≤-1 0≤a≤3-1≤-1≤f(2)≤5 -1≤4a-c≤5 1≤c≤7f(2)≤5 -1≤4a-c≤5 1≤c≤7解：依题意：解：依题意：而所求而所求f(3)=9a-c f(3)=9a-c 0≤9a≤27 0≤9a≤27 -7≤-c≤-1 -7≤-c≤-1 ∴-1≤f(3)≤26∴-1≤f(3)≤26∴∴-7≤9a-c≤26-7≤9a-c≤26正解一： 依题意得： f(1)=a-c f(2)=4a-c可知 ：f(3)=9a-c=-5/3f(1)+8/3f(2)∵ -4≤f(1)≤ -1 , -1≤f(2)≤5∴ 5/3≤-5/3f(1)≤20/3 , -8/3≤8/3f(2)≤40/3∴ -1≤-5/3f(1)+8/3f(2)≤20即 : -1≤f(3)≤20正解二： 线性约束条件：线性约束条件： 目标函数目标函数: : t=f(3)=9a-ct=f(3)=9a-c-4≤-4≤a-c≤-1 a-c≤-1 -1≤4a-c≤5 -1≤4a-c≤5 作出约束条件的可行域：为作出约束条件的可行域：为平行四边形平行四边形ABCDABCD，， 平平行行直直线线系系t=9a-c t=9a-c , , c=9a-tc=9a-t，，斜斜率率为为9 9。

a ac c2 22 24 46 64 46 6-2-2-2-28 8-4-4-4-4o o说明：约束条件变化时要用等价变换说明：约束条件变化时要用等价变换DABC(3,7)当平行直线过当平行直线过A A（（0 0，，1 1））时，时， t tminmin=9×0-1=-1=9×0-1=-1过点过点C C（（3 3，，7 7））时，时，t tmaxmax=9×3-7=20=9×3-7=20 ∴-1≤f(3)≤20 ∴-1≤f(3)≤20。