《简单的线性规划》由会员分享,可在线阅读,更多相关《简单的线性规划(24页珍藏版)》请在金锄头文库上搜索。
1、xyoxOyx-4y+3=0x=13x+5y-25=0A BCA:(5,2)B:(1,1)C:(1,4.4)问题1:x 有无最大(小)值?问题2:y 有无最大(小)值?问题3:2x+y 有无最大(小)值?XOYX-4y+3=0X=13x+5y-25=0A BCA:(5,2)B:(1,1)C:(1,4.4)2x+y=02x+y=1此时Z=3此时Z=12 Zmax=12Zmin=3Z=2x+y有关概念(1)由x,y 的不等式(或方程)组成的不等式组称为 x,y 的约束条件。(2)关于x,y 的一次不等式或方程组成的不等式组称为x, y 的线性约束条件。(3)欲达到最大值或最小值所涉及的变量x,y
2、的解析式称 为目标函数。关于x,y 的一次目标函数称为线性目标函 数。求线性目标函数在线性约束条件下的最大值或最小 值问题称为线性规划问题。(4)满足线性约束条件的解(x,y)称为可行解。所有可行 解组成的集合称为可行域。(5)使目标函数取得最大值或最小值的可行解称为最优解。练习解下列线性规划问题:1、求z=2x+y的最大值,使式中的x、y满足约束条件:xOyABCy=xx+y=1y=-12x+y=0B:(-1,-1) C:(2,-1)Zmin=-3Zmax=3目标函数: z=2x+y解线性规划问题的步骤: (2)移:在线性目标函数所表示的一组平行 线中,利用平移的方法找出与可行域有公共 点且
3、纵截距最大或最小的直线; (3)求:通过解方程组求出最优解; (4)答:作出答案。 (1)画:画出线性约束条件所表示的可行域;2、求z=3x+y的最大值,使式中的x、y满足约束条件2x+3y 24x-y 7y 6x 0y 0讨论:XOYABC D712-768y=6x-y=72x+3y=24l0:3x+y=0l1思考:目标函数: Z=x+3y 目标函数: Z=3x+y 解线性规划问题的步骤: (2)移:在线性目标函数所表示的一组平行 线中,利用平移的方法找出与可行域有公共 点且纵截距最大或最小的直线; (3)求:通过解方程组求出最优解; (4)答:作出答案。 小结:(1)画:画出线性约束条件所
4、表示的可行域;结论:1、线性目标函数的最大(小)值一般 在可行域的顶点处取得,也可能在边界 处取得。2、求线性目标函数的最优解,要注意 分析线性目标函数所表示的几何意义.应用问题:1某工厂制造甲、乙两种产品,已知制造甲产品 1kg要用煤9吨,电力4kw,劳力(按工作日计算)3个 ;制造乙产品1kg要用煤4吨,电力5kw,劳力10个. 又知制成甲产品1kg可获利7万元,制成乙产品1kg 可获利12万元,现在此工厂只有煤360吨,电力 200kw,劳力300个,在这种条件下应生产甲、乙两 种产品各多少千克,才能获得最大经济效益?【解题回顾】(1)用线性规划的方法解题的一般步骤是:设未知 数、列出约
5、束条件及目标函数、作出可行域、求出 最优解、写出答案.(2)本例的关键是分析清楚在哪一个点取最大值. 结论:用线性规划的方法解题的一般步骤是:(1)充分理解题意建立数学模型,也就是设未知 数、列出约束条件及目标函数.(2)作图.作出可行域、求出最优解.(3)根据实际意义写出答案.小结:二元一次不等式 表示平面区域直线定界, 特殊点定域简单的线性规划约束条件目标函数可行解可行域最优解应用求解方法:画、 移、求、答2、咖啡屋配制两种饮料,成分配比和单价如下表: 饮料奶粉(杯 )咖啡(杯 )糖(杯)价格(杯 ) 甲种9(g)4(g)3(g)0.7(元)乙种4(g)5(g)10(g)1.2(元)每天使
6、用限额为奶粉3600g,咖啡 2000g,糖3000g,若每天在原料的使 用限额内饮料能全部售出,应配制两 种饮料各多少杯获利最大?9x+4y=36003x+10y=30004x+5y=2000OABCD200200正确答案: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杯时,获 利最大。3x+10y=3000 y=240解 4x+5y=2000 得 x=200 C(200,240)
7、l说明:约束条件要写全,求解过程要细心, 解题格式要规范。z=0.7x+1.2y 目标函数:yx三、最优整数解的求解方法: (一)运用枚举验证求最优整数解 某人有楼房一幢,室内面积共180m2,拟分隔成 两类房间作为旅游客房。大房间每间面积为 18m2,可住游客5名,每名游客每天住宿费为 40元;小房间每间面积为15m2,可住游客3名 ,每名游客每天住宿费为50元;装修大房间每 间需1000元,装修小房间每间需600元。如果 他只能筹款8000元用于装修,且游客能住满客 房,他应隔出大房间和小房间各多少间,能获 得最大收益?最大收益是多少?这些整点有:(0,12),(1,10),(2,9),(
8、3,8),(4,6),(5,5),(6,3),(7,1),(8,0),分别代入f=200x+150y,逐一验证,可得取整点(0,12)或(3,8)时,fmax=2000+15012=2003+1508=1800(元)。所以要获得最大收益,有两种方案:.只隔出小房间12间;.隔出大房间3间,小房间8间。最大收益为1800元。 (二)运用平移直线法求最优整数解某人准备用100元购买空白磁盘和空白光 盘,空白磁盘每张4元,空白光盘每张7 元。问他应该如何购买才能达到磁盘和 光盘都购买并且都不超过10张,而又使 得剩余的钱最少这个目的?为了寻找整数解,我们在可行域里作出最靠近 4x+7y=100且与之
9、平行的直线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)-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 。ac224646-2-28-4-4o说明:约束条件变化时要用等价变换DABC(3,7)当平行直线过A(0,1)时,tmin=90-1=-1过点C(3,7)时,tmax=93-7=20-1f(3)20