求线性目标函数在线性约束条件下的最大值或最小值问题

共57页1第三十四讲简单的线性规划共57页2共57页3回归课本1.二元一次不等式表示平面的区域：直线Ax＋By＋C＝0将平面划分为三部分，即点在直线上；点在直线的上方区域；点在直线的下方区域，若满足B(Ax＋By＋C)＞0，则点P(x，y)在直线Ax＋By＋C＝0的上方；若满足B(Ax＋By＋C)＜0，则点P(x，y)在直线Ax＋By＋C＝0的下方．二元一次平面区域的判定方法是：“直线定界、特殊点定域．”共57页42．线性规划：求线性目标函数在线性约束条件下的最大值或最小值问题，称为线性规划问题，满足线性约束条件的解(x，y)叫做可行解，由所有可行解组成的集合叫做可行域，使目标函数取得最大值或最小值的可行解叫做最优解．3．用图解法解线性规划问题的步骤：(1)分析并将已知数据列出表格；(2)确定线性约束条件；(3)确定线性目标函数；(4)画出可行域；(5)利用线性目标函数(直线)求出最优解；(6)据实际问题的需要，适当调整最优解(如整数解等)．共57页5点评：(1)用图解法解决线性规划问题时，分析题目的已知条件找出约束条件和目标函数是关键，可先将题目中的量分类、列出表格，理清头绪，然后列出不等式组(方程组)寻求约束条件，并就题目所述找到目标函数．(2)可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域．如果可行域是一个多边形，那么一般在其顶点处使目标函数取得最大值或最小值，最优解一般就是多边形的某个顶点．特别地，当表示线性目标函数的直线与可行域的某条边平行时(k＝ki)，其最优解可能有无数个．共57页6(3)若实际问题要求的最优解是整数解，而利用图解法得到的解为非整数解(近似解)，应作适当的调整，其方法应以与线性目标函数的直线的距离为依据，在直线的附近寻求与此直线距离最近的整点，不要在用图解法所得到的近似解附近寻找．这个问题我们将在后面的例题中详细说明．如果可行域中的整点数目很少，采用逐个试法也可．共57页7考点陪练1.已知点(3,1)和(4，－6)在直线3x－2y＋a＝0的两侧，则a的取值范围是()A．(－24,7)B．(7,24)C．(－7,24)D．(－24，－7)共57页8解析：联想“代点法”判断Ax＋By＋C的符号法则．若两点在直线3x－2y＋a＝0的两侧，把点的坐标代入3x－2y＋a所得两式的符号一定相反．把点(3,1)和(4，－6)分别代入3x－2y＋a，得7＋a,24＋a.由题意知：(7＋a)(24＋a)＜0⇔－24＜a＜－7.答案：D共57页9答案：C2．(2010·石家庄质检一)已知变量x，y满足约束条件y≤xx＋y≥2y≥3x－6，则目标函数z＝2x＋y的最大值为()A．3B．4C．9D．12共57页103．(2011·名校模拟)已知函数f(x)＝x2－2x，则满足条件fx＋fy≤0fx－fy≥0的点(x，y)所形成区域的面积为()A．4πB．2πC.3π2D．π共57页11答案：D解析：不等式f(x)＋f(y)≤0可转化为(x－1)2＋(y－1)2≤2，不等式f(x)－f(y)≥0可转化为(x－y)(x＋y－2)≥0.于是点(x，y)所形成的区域为两个14圆面，而圆面积是2π.共57页12点评：学习数学要在“做中学”，勤动笔，勤动脑，这里的“动”是没有人可以替代的．共57页134．某公司有60万元资金，计划投资甲、乙两个项目，按要求对项目甲的投资不小于对项目乙投资的23，且对每个项目的投资不能低于5万元，对项目甲每投资1万元可获得0.4万元的利润，对项目乙每投资1万元可获得0.6万元的利润，该公司正确规划投资后，在这两个项目上共可获得的最大利润为()A．36万元B．31.2万元C．30.4万元D．24万元共57页14解析：设对甲项目投资x万元，对乙项目投资y万元，获得总利润为z万元，则z＝0.4x＋0.6y，且x＋y≤60，x≥23y，x≥5，y≥5，作出不等式组表示的平面区域，共57页15如图所示，作直线l0：0.4x＋0.6y＝0，并将l0向上平移，过点C时z取得最大值，即zmax＝0.4×24＋0.6×36＝31.2(万元)．故选B.答案：B共57页16解析：如右图，作出可行域，z＝2x－y可化为y＝2x－z.由图可知直线y＝2x－z经过点A(3，－3)时，z有最大值，最大值为z＝9.答案：95．(全国卷Ⅰ)若x、y满足约束条件x＋y≥0，x－y＋3≥0，0≤x≤3，则z＝2x－y的最大值为________．共57页17共57页18类型一二元一次不等式表示的平面区域及整点问题解题准备：不等式组表示的平面区域是各个不等式所表示的平面点集的交集，即是各个不等式所表示的平面区域的公共部分．整点：区域内横、纵坐标为整数的点．共57页19[分析](1)数形结合；(2)整点是指横、纵坐标均为整数的点．【典例1】画出不等式组x－y＋5≥0，x＋y≥0，x≤3.表示的平面区域，并回答下列问题：(1)指出x，y的取值范围；(2)平面区域内有多少个整点？共57页20[解析](1)不等式x－y＋5≥0表示直线x－y＋5＝0上及右下方的点的集合，x＋y≥0表示直线x＋y＝0上及右上方的点的集合，x≤3表示直线x＝3上及左方的点的集合．所以，不等式组x－y＋5≥0x＋y≥0x≤3表示的平面区域如图所示．结合图中可行域得x∈[－52，3]，y∈[－3,8]．共57页21(2)由图形及不等式组知－x≤y≤x＋5－2≤x≤3且x∈Z，当x＝3时，－3≤y≤8，有12个整点；当x＝2时，－2≤y≤7，有10个整点；当x＝1时，－1≤y≤6，有8个整点；当x＝0时，0≤y≤5，有6个整点；当x＝－1时，1≤y≤4，有4个整点；当x＝－2时，2≤y≤3，有2个整点；∴平面区域内的整点共有2＋4＋6＋8＋10＋12＝42(个)．共57页22[误区指津]确定平面区域时应对每一个不等式表示的平面区域作出正确的判断，避免因某一个不等式表示的平面区域的失误而产生错误．[点评]本题主要考查不等式表示的平面区域、数列求和及不等式的应用等基础知识，考查了数形结合的方法和逻辑推理能力．(1)不等式组表示的平面区域是各个不等式所表示的平面区域点集的交集，因而是各个不等式所表示的平面区域的公共部分．(2)在封闭区域内找整点数目时，若数目较小时，可画网格逐一数出；若数目较大，则可分x＝m逐条分段统计．共57页23探究1：画出不等式组x－2y＋1＞0，x＋2y＋1≥0，1＜|x－2|≤3表示的平面区域．共57页24解析：不等式x－2y＋1＞0表示直线x－2y＋1＝0右下方的点的集合；不等式x＋2y＋1≥0表示直线x＋2y＋1＝0上及其右上方的点的集合；不等式1＜|x－2|≤3可化为－1≤x＜1或3＜x≤5，它表示夹在两平行线x＝－1和x＝1之间或在两平行线x＝3和x＝5之间的带状区域，但不包括直线x＝1和x＝3上的点．∴原不等式组表示的区域如图所示．共57页25类型二求线性目标函数的最值问题解题准备：1.利用线性规划求最值，一般用图解法求解，其步骤是：第一步：画：在平面直角坐标系内作出可行域；第二步：移：利用平移直线的方法在可行域内找到最优解所对应的点；第三步：求：将最优解代入目标函数求出最大值或最小值；2．线性目标函数的最大值和最小值一般在可行域的顶点处或边界上取得．共57页26【典例2】已知x，y满足4x＋3y－20≤0x－3y－2≤0x，y∈N*，求S＝7x＋5y的最大值．共57页27[解析]满足条件的平面区域为四边形ADOE内部，如图所示，作直线l0：7x＋5y＝0的平行直线l：7x＋5y＝t，当直线l经过A点时，S可取最大值．由方程组4x＋3y－20＝0x－3y－2＝0，可得A点坐标225，45，然而点A不是整数，A点坐标不能作为最优解．共57页28因经过点A的目标函数所确定的直线l为：7x＋5y＝3445，令7x＋5y＝34，经验证可得：在可行域中与此直线l距离最近的整点为B(2,4)，使SB＝7×2＋4×5＝34为最大．共57页29[点评]由于点A不是整点，在可行域中寻找满足条件的整点时，不能以与A点的距离为依据，应以与过点A的直线l的距离为依据，从图可知整点C(4,1)，距点A最近，然而SC＝7×4＋1×5＝33，而点C到l的距离dC＝14574，点B到l的距离为dB＝4574，因此，应舍C而取B.用数形结合的观点看，直线l：7x＋5y＝t在y轴上的截距为t5，l只有过可行域中与直线7x＋5y＝3445距离最近的点，在y轴上的截距t5才最大，即t最大，使S＝7x＋5y达到最共57页30另外，此题在可行域中整点有(1,1)，(1,2)，(1,3)，(1,4)，(1,5)，(2,1)，(2,2)，(2,3)，(2,4)，(3,1)，(3,2)，(4,1)共12个．结合图形便知离直线7x＋5y＝3445距离较近的点有(1,5)，(2,4)，(3,2)，(4,1)，可以代入S＝7x＋5y进行验证，则得点(2,4)为最优解，使S最大．共57页31类型三求非线性目标函数的最值解题准备：注意分析目标函数所表示的几何意义，通常与截距、斜率、距离等联系．【典例3】变量x，y满足x－4y＋3≤0，3x＋5y－25≤0，x≥1，(1)设z＝yx，求z的最小值；(2)设z＝x2＋y2，求z的取值范围．共57页32[解析]由约束条件x－4y＋3≤0，3x＋5y－25≤0，x≥1，作出(x，y)的可行域如图所示．共57页33由x＝1，3x＋5y－25＝0，解得A1，225.由x＝1，x－4y＋3＝0，解得C(1,1)，由x－4y＋3＝0，3x＋5y－25＝0，解得B(5,2)．共57页34(1)∵z＝yx＝y－0x－0.∴z的值即是可行域中的点与原点O连线的斜率．观察图形可知zmin＝kOB＝25.(2)z＝x2＋y2的几何意义是可行域上的点到原点O的距离的平方．结合图形可知，可行域上的点到原点的距离中，dmin＝|OC|＝2，dmax＝|OB|＝29.∴2≤z≤29.共57页35探究2：已知2x＋y－5≥0，3x－y－5≤0，x－2y＋5≥0，则(x＋1)2＋(y＋1)2的最大值、最小值分别是________、________.解析：作出不等式组2x＋y－5≥03x－y－5≤0x－2y＋5≥0表示的可行域．如图所示．共57页36由x－2y＋5＝0，2x＋y－5＝0，可得点A(1,3)；由x－2y＋5＝0，3x－y－5＝0，可得点B(3,4)；由2x＋y－5＝0，3x－y－5＝0，可得点C(2,1)．共57页37答案：4113z＝(x＋1)2＋(y＋1)2表示可行域内的点到点(－1，－1)的距离的平方，以(－1，－1)为圆心，z为半径画圆，当圆经过点B时，z最大；当圆经过点C时，z最小．所以当x＝3，y＝4时，(x＋1)2＋(y＋1)2＝41为所求最大值；当x＝2，y＝1时，(x＋1)2＋(y＋1)2＝13为所求最小值．共57页38类型四简单的线性规划的实际应用解题准备：对于线性规划中的最优整数解的问题，当解方程组得到的解不是整数解时，可用下面的方法求解：1．平移直线法：先在可行域内打网格，再描整点，平移直线l，最先经过或最后经过的整点坐标是整点最优解；2．检验优值法：当可行域内整点个数较少时，也可将整点坐标逐一代入目标函数求值，经比较得出最优解；3．调整优值法：先求非整点最优解及最优值，再借助不定方程知识调整最优值，最后筛选出最优解．共57页39【典例4】某人有楼房一幢，室内面积共180m2，拟分隔成两类房间作为旅游客房．大房间每间面积18m2，可住游客5名，每名游客每天住宿费为40元；小房间