9简单线性规划问题1.ppt

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

1、xyo可行域上的最优解可行域上的最优解问题问题1:某工厂用某工厂用A,B两种配件生产甲两种配件生产甲,乙两种产品乙两种产品,每生产一件甲种产品使用每生产一件甲种产品使用4个个A配件耗时配件耗时1h,每生产一件乙种产品使用每生产一件乙种产品使用4个个B配件耗时配件耗时2h,该厂每天最多可从配件厂获得该厂每天最多可从配件厂获得16个个A配件和配件和12个个B配件配件,按每天工作按每天工作8小时小时计算计算,该厂所有该厂所有可能的日生产安排是什么可能的日生产安排是什么?若生产若生产1件甲种产品获利件甲种产品获利2万元万元,生产生产1 件乙件乙种产品获利种产品获利3万元万元,采用哪种生产安排利润最大采

2、用哪种生产安排利润最大?32利润利润(万元万元)821所需时间所需时间1240B种配件种配件1604A种配件种配件资源限额资源限额 乙产品乙产品 (1件件)甲产品甲产品 (1件件)产品产品消消 耗耗 量量资资 源源把问题把问题1的有关数据列表表示如下的有关数据列表表示如下:设甲设甲,乙两种产品分别生产乙两种产品分别生产x,y件件,0 xy4348 将上面不等式组表示成平面上的区域将上面不等式组表示成平面上的区域,区域内区域内所有坐标为整数的点所有坐标为整数的点P(x,y),安排生产任务安排生产任务x,y都是有意义的都是有意义的.设甲设甲,乙两种产品分别生产乙两种产品分别生产x,y件件,由己知条

3、件可得由己知条件可得:问题：问题：求利润求利润2x+3y的最大值的最大值.若设利润为若设利润为z,则则z=2x+3y,这样上述问题转化为这样上述问题转化为:当当x,y在满足上述约束条件时在满足上述约束条件时,z的最大值为多少的最大值为多少?当点当点P在可允许的取值范围变化时在可允许的取值范围变化时,0 xy4348M（4，2）问题：问题：求利润求利润z=2x+3y的最大值的最大值.象这样关于象这样关于x,yx,y一次不等一次不等式组的约束条件称为式组的约束条件称为线性约束线性约束条件条件Z=2x+3yZ=2x+3y称为目标函数称为目标函数,(,(因这里因这里目标函数为关于目标函数为关于x,yx

4、,y的一次式的一次式,又又称为称为线性目标函数线性目标函数 在线性约束下求线性目标函数在线性约束下求线性目标函数的最值问题的最值问题,统称为统称为线性规划线性规划,满足线性约束的解满足线性约束的解(x,yx,y)叫做叫做可行解可行解,所有可行解组成的集合叫做所有可行解组成的集合叫做可行域可行域使目标函数使目标函数取得最值取得最值的可行解叫做这个的可行解叫做这个问题的问题的最优解最优解可行域可行域线性规划概念理解问题：问题：设设z z=2=2x x+y y，式中变量满足，式中变量满足下列条件：下列条件：求求z z的最大值与最小值。的最大值与最小值。目标函数（线性目标函数）线性约线性约束条件束条件

5、线性规划：线性规划：求线性目标函数在线性约束条件下的最求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题大值或最小值的问题，统称为线性规划问题 可行解可行解 ：满足线性约束条满足线性约束条件的解件的解(x(x，y)y)叫可行解；叫可行解；可行域可行域 ：由所有可行解由所有可行解组成的集合叫做可行域；组成的集合叫做可行域；最优解最优解 ：使目标函数取得使目标函数取得最大或最小值的可行解叫最大或最小值的可行解叫线性规划问题的最优解。线性规划问题的最优解。可行域可行域2x+y=32x+y=12(1,1)(5,2)复习复习线性规划线性规划0 xy4348N N（2 2，3 3）变

6、式：变式：求利润求利润z=x+3y的最大值的最大值.练习练习解下列线性规划问题：解下列线性规划问题：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）画：画出线性约束条件所表示的可行域；）画：画出线性约束条件所表示的可行域；体验体验:二、二、最优解最优解一般在可行域的一般在可行域的顶点顶点处取得处取得三、在哪个顶点取得不仅与三、在哪个顶点取得不仅与B B的符号有关，而的符号有关，而且还与直线且还与直线 Z=Z=Ax+ByAx+By的的斜率斜率有关有关一、一、先定先定可行域和平移方向，再找最优解。可行域和平移方向，再找最优解。课堂练习 课本课本P P8080 1 1、2 2题题