简单的线性规划问题

3 3 2简单的线性规划问题 2 新课探究 某工厂用A B两种配件生产甲 乙两种产品 每生产一件甲产品使用4个A配件耗时1h 每生产一件乙产品使用4个B配件耗时2h 该厂每天最多可从配件厂获得16个A配件和12个B配件 按每天工作8h计算 该厂所有可能的日生产安排是什么 解 按甲 乙两种产品分别生产x y件 由已知条件可得二元一次不等式组 把问题1的有关数据列表表示如下 设甲 乙两种产品分别生产x y件 将上述不等式组表示成平面上的区域 y x 4 8 4 3 o 若生产一件甲产品获利2万元 生产一件乙产品获利3万元 采用那种生产安排利润最大 设工厂获得的利润为z 则z 2x 3y 把z 2x 3y变形为它表示斜率为的一组平行直线 z与这条直线的截距有关 如图可见 当直线经过区域上的点M时 截距最大 即z最大 M 甲 乙两种产品分别生产x y件 象这样关于x y一次不等式组的约束条件称为线性约束条件 Z 2x 3y称为目标函数 因这里目标函数为关于x y的一次式 又称为线性目标函数 在线性约束下求线性目标函数的最值问题 统称为线性规划 二 基本概念 二 基本概念 y x 4 8 4 3 o 满足线性约束的解 x y 叫做可行解 由所有可行解组成的集合叫做可行域 使目标函数取得最大值或最小值的可行解叫做这个问题的最优解 可行域 可行解 最优解 可行域 线性规划概念理解 问题 设z 2x y 式中变量满足下列条件 求z的最大值与最小值 目标函数 线性目标函数 线性约束条件 变式 求利润z x 4y的最大值 解 按甲 乙两种产品分别生产x y件 目标函数为Z 那么 约束条件为 目标函数为 作出上述约束条件所表示的可行域如下 N 由图可见 当直线经过可行域上的N点时最大 即最大 解方程组得N点的坐标为 2 3 所以 线性规划 求线性目标函数在线性约束条件下的最大值或最小值的问题 统称为线性规划问题 可行解 满足线性约束条件的解 x y 叫可行解 可行域 由所有可行解组成的集合叫做可行域 最优解 使目标函数取得最大或最小值的可行解叫线性规划问题的最优解 可行域 2x y 3 2x y 12 1 1 5 2 复习线性规划 练习 解下列线性规划问题 1 求z 2x y的最大值 使式中的x y满足约束条件 Zmin 3 Zmax 3 14 解线性规划问题的步骤 1 2 画 画出线性约束条件所表示的可行域 2 3 移 在线性目标函数所表示的一组平行线中 利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线 3 4 求 通过解方程组求出最优解 4 5 答 作出答案 1 找找出线性约束条件 目标函数 例2 二 练习 1 求z 3x 5y的最小值 使x y满足约束条件 1 解 作出平面区域 x y o A B C z 3x 5y 作出直线3x 5y z的图像 可知直线经过A点时 Z取最大值 直线经过B点时 Z取最小值 求得A 1 5 2 5 B 2 1 则Zmax 17 Zmin 11 第二课时 复习线性规划 线性规划 求线性目标函数在线性约束条件下的最大值或最小值的问题 统称为线性规划问题 可行解 满足线性约束条件的解 x y 叫可行解 可行域 由所有可行解组成的集合叫做可行域 最优解 使目标函数取得最大或最小值的可行解叫线性规划问题的最优解 可行域 2x y 3 2x y 12 1 1 5 2 20 解线性规划问题的步骤 1 2 画 画出线性约束条件所表示的可行域 2 3 移 在线性目标函数所表示的一组平行线中 利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线 3 4 求 通过解方程组求出最优解 4 5 答 作出答案 1 找找出线性约束条件 目标函数 一 线性规划在实际中的应用 线性规划的理论和方法主要在两类问题中得到应用 一是在人力 物力 资金等资源一定的条件下 如何使用它们来完成最多的任务 二是给定一项任务 如何合理安排和规划 能以最少的人力 物力 资金等资源来完成该项任务下面我们就来看看线性规划在实际中的一些应用 二 例题 例5 营养学家指出 成人良好的日常饮食应该至少提供0 075kg的碳水化合物 0 06kg的蛋白质 0 06kg的脂肪 1kg食物A含有0 105kg碳水化合物 0 07kg蛋白质 0 14kg脂肪 花费28元 而1kg食物B含有0 105kg碳水化合物 0 14kg蛋白质 0 07kg脂肪 花费21元 为了满足营养专家指出的日常饮食要求 同时使花费最低 需要同时食用食物A和食物B多少kg 分析 将已知数据列成表格 解 设每天食用xkg食物A ykg食物B 总成本为z 那么 目标函数为 z 28x 21y 作出二元一次不等式组所表示的平面区域 即可行域 1 找 把目标函数z 28x 21y变形为 x y o 57 5 7 6 7 3 7 3 7 6 7 它表示斜率为纵截距随z变化的一组平行直线 是直线在y轴上的截距 当截距最小时 z的值最小 M 如图可见 当直线z 28x 21y经过可行域上的点M时 纵截距最小 即z最小 2 画 3 移 M点是两条直线的交点 解方程组 得M点的坐标为 所以zmin 28x 21y 16 由此可知 每天食用食物A143g 食物B约571g 能够满足日常饮食要求 又使花费最低 最低成本为16元 4 求 5 答 例6 要将两种大小不同规格的钢板截成A B C三种规格 每张钢板可同时截得三种规格的小钢板的块数如下表所示 今需要A B C三种规格的成品分别为15 18 27块 问各截这两种钢板多少张可得所需三种规格成品 且使所用钢板张数最少 解 设需截第一种钢板x张 第二种钢板y张 可得 2x y 15 x 3y 27 x 2y 18 x y 0 经过可行域内的整点B 3 9 和C 4 8 且和原点距离最近的直线是x y 12 它们是最优解 答 略 作出一组平行直线z x y 目标函数z x y 打网格线法 在可行域内打出网格线 当直线经过点A时z x y 11 4 但它不是最优整数解 将直线x y 11 4继续向上平移 2x y 15 x 3y 27 x 2y 18 x y 0 直线x y 12经过的整点是B 3 9 和C 4 8 它们是最优解 作出一组平行直线z x y 目标函数z x y 当直线经过点A时z x y 11 4 但它不是最优整数解 作直线x y 12 x y 12 解得交点B C的坐标B 3 9 和C 4 8 调整优值法 即先求非整数条件下的最优解 调整Z的值使不定方程Ax By Z存在最大 小 的整点值 最后筛选出整点最优解 即先打网格 描出可行域内的整点 平移直线 最先经过或最后经过的整点坐标即为最优整解 线性规划求最优整数解的一般方法 1 平移找解法 2 调整优解法 小结 例7 一个化肥厂生产甲 乙两种混合肥料 生产1车皮甲种肥料的主要原料是磷酸盐4t 硝酸盐18t 获利10000元 生产1车皮乙种肥料需要的主要原料是磷酸盐1t 硝酸盐15t 获利5000元 现库存磷酸盐10t 硝酸盐66t 在此基础上生产这两种混合肥料 列出满足生产条件的数学关系式 并画出相应的平面区域 并计算生产甲 乙两种肥料各多少车皮 能够产生最大的利润 解 设x y分别为计划生产甲 乙两种混合肥料的车皮数 于是满足以下条件 x y o 解 设生产甲种肥料x车皮 乙种肥料y车皮 能够产生利润Z万元 目标函数为Z x 0 5y 可行域如图 把Z x 0 5y变形为y 2x 2z 它表示斜率为 2 在y轴上的截距为2z的一组直线系 x y o 由图可以看出 当直线经过可行域上的点M时 截距2z最大 即z最大 故生产甲种 乙种肥料各2车皮 能够产生最大利润 最大利润为3万元 M 容易求得M点的坐标为 2 2 则Zmin 3 例8 某人准备投资1200万元兴办一所完全中学 对教育市场进行调查后 他得到了下面的数据表格 以班级为单位 分别用数学关系式和图形表示上述限制条件 若根据有关部门的规定 初中每人每年可收学费1600元 高中每人每年可收学费2700元 那么开设初中班和高中班多少个 每年收费的学费总额最多 把上面四个不等式合在一起 得到 y x 20 30 40 20 30 o 另外 开设的班级不能为负 则x 0 y 0 而由于资金限制 26x 54y 2 2x 2 3y 1200 解 设开设初中班x个 高中班y个 因办学规模以20 30个班为宜 所以 20 x y 30 y x 20 30 40 20 30 o 由图可以看出 当直线Z 7 2x 10 8y经过可行域上的点M时 截距最大 即Z最大 设收取的学费总额为Z万元 则目标函数Z 0 16 45x 0 27 40y 7 2x 10 8y Z 7 2x 10 8y变形为它表示斜率为的直线系 Z与这条直线的截距有关 M 易求得M 20 10 则Zmax 7 2x 10 8y 252 故开设20个初中班和10个高中班 收取的学费最多 为252万元 咖啡馆配制两种饮料 甲种饮料每杯含奶粉9g 咖啡4g 糖3g 乙种饮料每杯含奶粉4g 咖啡5g 糖10g 已知每天原料的使用限额为奶粉3600g 咖啡2000g糖3000g 如果甲种饮料每杯能获利0 7元 乙种饮料每杯能获利1 2元 每天在原料的使用限额内饮料能全部售出 每天应配制两种饮料各多少杯能获利最大 解 将已知数据列为下表 原料 每配制1杯饮料消耗的原料 奶粉 g 咖啡 g 糖 g 甲种饮料 乙种饮料 9 4 3 4 5 1 2 原料限额 3600 2000 3000 利润 元 0 7 1 2 x y 设每天应配制甲种饮料x杯 乙种饮料y杯 则 目标函数为 z 0 7x 1 2y 巩固练习一 解 设每天应配制甲种饮料x杯 乙种饮料y杯 则 把直线l向右上方平移至l1的位置时 直线经过可行域上的点C 且与原点距离最大 此时z 0 7x 1 2y取最大值解方程组得点C的坐标为 200 240 目标函数为 z 0 7x 1 2y 答 每天配制甲种饮料200杯 乙种饮料240杯可获取最大利润 小结 作出可行域 目标函数为 z 0 7x 1 2y作直线l 0 7x 1 2y 0 巩固练习二 某厂拟生产甲 乙两种适销产品 每件销售收入分别为3000元 2000元 甲 乙产品都需要在A B两种设备上加工 在每台A B上加工1件甲所需工时分别为1h 2h 在每台A B上加工1件乙所需工时分别为2h 1h A B两种设备每月有效使用台数分别为400h和500h 如何安排生产可使收入最大 设每月生产甲产品x件 生产乙产品y件 每月收入为z 目标函数为Z 3x 2y 满足的条件是 Z 3x 2y变形为它表示斜率为的直线系 Z与这条直线的截距有关 X Y O 400 200 250 500 当直线经过点M时 截距最大 Z最大 M 解方程组 可得M 200 100 Z的最大值Z 3x 2y 800 故生产甲产品200件 乙产品100件 收入最大 为80万元 四 课时小结 线性规划的两类重要实际问题的解题思路 1 应准确建立数学模型 即根据题意找出约束条件 确定线性目标函数 2 用图解法求得数学模型的解 即画出可行域 在可行域内求得