线性规划问题图解法PPT课件.ppt

二元一次不等式表示的平面区域 判断二元一次不等式表示哪一侧平面区域的方法 例1 已知线性约束条件为 求线性目标函数z=x+2y满足线性约束条件的最优解即最大值、最小值。 三、练习题： 1、求z＝2x＋y的最大值，使x、y满足约束条件： 1.解：作出平面区域 2.解：作出平面区域 用图解法解线性规划问题的一般步骤： （1）在直角坐标系中画出线性约束条件下的可行域。 （2）将目标函数变为斜截式，并指出当截距取最大值（或最小值）时，目标函数取得最大值还是最小值。 （3）令目标函数的值取0，画出直线Ax+By=0。然后根据图形，找出直线经过可行域时目标函数的最优解。 （4）确定最优解的坐标（x，y）。 （5）把最优解的坐标代入线性目标函数，求出最大值或最小值。 * * * 书 山 有 路 勤 为 径，学 海 无 崖 苦 作 舟 少 小 不 学 习，老 来 徒 伤 悲 成功=艰苦的劳动+正确的方法+少谈空话 天才就是百分之一的灵感，百分之九十九的汗水！ 天 才 在 于 勤 奋，努 力 才 能 成 功！ 勤劳的孩子展望未来, 但懒惰的孩子享受现在!!! 什 么 也 不 问 的 人 什 么 也 学 不 到 !!! 求 真 知 ， 学 做 人 第十九章 线性规划初步 O x y 在平面直角坐标系中，以二元一次方程x+y-1=0的解为坐标的点的集合{(x，y)|x+y-1=0}是经过点(0，1)和(1，0)的一条直线l，那么以二元一次不等式x+y-10的解为坐标的点的集合{(x，y)|x+y-10}是 什么图形? 1 1 x+y-1=0 x+y-10 x+y-10 复习回顾 O x y 1 1 x+y-1=0 x+y-10 x+y-10 （1）法向量法 （2）试点法 由于对在直线Ax+By+C=0同一侧所有点(x，y)，把它的坐标(x，y)代入Ax+By+C，所得的实数的符号都相同，故只需在这条直线的某一侧取一特殊点(x0，y0)以Ax0+By0+C的正负的情况便可判断Ax+By+C0表示这一直线哪一侧的平面区域，特殊地，当 C≠0时常把原点作为此特殊点。 复习回顾 某工厂用A、B两种配件生产甲、乙两种产品，每生产一件甲产品使用4个A配件耗时1h，每生产一件乙产品使用4个B配件耗时2h，该厂每天最多可从配件厂获得16个A配件和12个B配件，按每天工作8h计算，该厂所有可能的日生产安排是什么？ 解：按甲、乙两种产品分别生产x、y件， 由已知条件可得二元一次不等式组 简单的线性规划问题 将上述不等式组表示成平面上的区域，图中的阴影部分中的整点（坐标为整数）就代表所有可能的日生产安排。 x 若生产一件甲产品获利2万元，生产一件乙产品获利3万元，采用那种生产安排利润最大？ y 4 8 4 3 o ? ? ? ? ? ? ? í ì 3 3 ￡ ￡ ￡ + 0 0 3 4 8 2 y x y x y x y x 4 8 4 3 o M 设工厂获得的利润为z，则z＝2x＋3y 将z看成常数，当z变化时，可以得到一组互相平行的直线，而由于这些直线的斜率是确定的，因此给定一个点就能确定一条直线。这说明截距 可以由平面内的一个点的坐标唯一确定。 3 z 在不等式组表示的平面区域内，直线经过点M时截距最大，从而z值最大。 y M 由图可知： 当直线 经过直线x=4与 直线x+2y-8=0的交点M(4，2)时，截距 的值最大，最大值为14/3。 此时2x+3y=14. y x 4 8 4 3 o 求最大值或求最小值的的函数称为目标函数，因为它是关于变量x、y的一次解析式，又称线性目标函数。 满足线性约束的解 （x，y）叫做可行解。 在线性约束条件下求线性目标函数的最大值或最小值问题，统称为线性规划问题。 关于变量x、y的一次不等式，称为线性约束条件。 由所有可行解组成的集合叫做可行域。 使目标函数取得最大值或最小值的可行解叫做这个问题的最优解。 可行域 可行解 最优解 简单的线性规划问题 ? ? í ì 3 ≥ ￡ - 0 11 5 0 x 4y 2x y x 1 — y + - 0 - + 2、求z＝3x＋5y的最值，使x、y满足约束条件： x y A B C o z＝2x＋y 作出直线y=－2x＋z的图像，可知z要求最大值，即直线经过C点时。 求得C点坐标为（2，－1），则Zmax=2x＋y＝3 若把目标函数换为 z＝2x－y，则Z的 最大值为？ x y o A B C