简单的线性规划.ppt

《简单的线性规划.ppt》由会员分享，可在线阅读，更多相关《简单的线性规划.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、简单线性规划,问题1：x 有无最大（小）值？,问题2：y 有无最大（小）值？,问题3：2x+y 有无最大（小）值？,此时Z=3,此时Z=12,Zmax=12 Zmin=3,有关概念,(1)由x，y 的不等式(或方程)组成的不等式组称为x，y 的约束条件。,(2)关于x，y 的一次不等式或方程组成的不等式组称为x，y 的线性约束条件。,(3)欲达到最大值或最小值所涉及的变量x，y 的解析式称为目标函数。关于x，y 的一次目标函数称为线性目标函数。求线性目标函数在线性约束条件下的最大值或最小值问题称为线性规划问题。,(4)满足线性约束条件的解（x，y）称为可行解。所有可行解组成的集合称为可行域。,

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

3、。,小结：,（1）画：画出线性约束条件所表示的可行域；,结论：,1、线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界处取得。 2、求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义.,应用问题: 1某工厂制造甲、乙两种产品，已知制造甲产品1kg要用煤9吨，电力4kw，劳力(按工作日计算)3个；制造乙产品1kg要用煤4吨，电力5kw，劳力10个.又知制成甲产品1kg可获利7万元，制成乙产品1kg可获利12万元，现在此工厂只有煤360吨，电力200kw，劳力300个，在这种条件下应生产甲、乙两种产品各多少千克，才能获得最大经济效益?,【解题回顾】 (1)用线性规划的方法

4、解题的一般步骤是：设未知数、列出约束条件及目标函数、作出可行域、求出最优解、写出答案. (2)本例的关键是分析清楚在哪一个点取最大值.,结论：,用线性规划的方法解题的一般步骤是： (1)充分理解题意建立数学模型,也就是设未知数、列出约束条件及目标函数. (2)作图.作出可行域、求出最优解. (3)根据实际意义写出答案.,小结：,二元一次不等式表示平面区域,直线定界，特殊点定域,简单的线性规划,约束条件,目标函数,可行解,可行域,最优解,求解方法：画、移、求、答,2、咖啡屋配制两种饮料，成分配比和单价如下表：,每天使用限额为奶粉3600g,咖啡2000g,糖3000g，若每天在原料的使用限额内饮

5、料能全部售出，应配制两种饮料各多少杯获利最大？,正确答案：1）线性约束条件为：,9x+4y3600 4x+5y2000 3x+10y3000 xN yN,当 l 过点C时，y轴截距b最大，即z最大,当x=200，y=240时，Zmax=0.7200+1.2240=428（元）,答：每天应配制甲种饮料200杯，乙种饮料240杯时，获利最大。,z=0.7x+1.2y,目标函数：,y,x,三、最优整数解的求解方法:,（一）运用枚举验证求最优整数解 某人有楼房一幢，室内面积共180m2，拟分隔成两类房间作为旅游客房。大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为1

6、5m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？最大收益是多少？,这些整点有:(0，12),(1，10),(2，9),(3，8),(4，6), (5，5)，(6，3),(7，1),(8，0),分别代入f=200 x+150y， 逐一验证，可得取整点(0,12)或(3,8)时, fmax=2000+15012=2003+1508=1800(元)。 所以要获得最大收益，有两种方案： .只隔出小房间12间； .隔出大房间3间，小房间8间。 最大收

7、益为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)=ax2-c，满足-4f(1)-1, -1f(2)5,求f(3)的取值范围。,-4f(1)-

8、1 -4a-c-1 0a3,-1f(2)5 -14a-c5 1c7,解：依题意：,而所求f(3)=9a-c 09a27 -7-c-1,-1f(3)26,-79a-c26,正解一： 依题意得： f(1)=a-c f(2)=4a-c,可知 ：f(3)=9a-c=-5/3f(1)+8/3f(2), -4f(1) -1 , -1f(2)5, 5/3-5/3f(1)20/3 , -8/38/3f(2)40/3, -1-5/3f(1)+8/3f(2)20,即 : -1f(3)20,正解二：,线性约束条件：,目标函数: t=f(3)=9a-c,-4a-c-1 -14a-c5,作出约束条件的可行域：为平行四边形ABCD，,平行直线系t=9a-c , c=9a-t，斜率为9。,a,c,2,2,4,6,4,6,-2,-2,8,-4,-4,o,说明：约束条件变化时要用等价变换,D,A,B,C(3,7),当平行直线过A（0，1）时， tmin=90-1=-1 过点C（3，7）时，tmax=93-7=20 -1f(3)20,