高中数学 教你如何做出最佳选择——简单线性规划求最优解素材 苏教版必修4

1 教你如何做出最佳选择教你如何做出最佳选择 简单的线性规划求最优解简单的线性规划求最优解 在线性约束条件下 求线性目标函数最值问题 称为 线性规划 目标函数 yxfz 取得最值时 变量yx 的对应解 yx称为最优解 若Zyx 时 z 取得最 值 称 yx为最优整数解 简称整解 点 yx的横 纵坐标都是整数 称为整点 求最优整解问题出现在高中数学新教材中 常见的实际应用题型有两种 1 给出一 定数量的人力 物力资源 问怎样安排能使完成的任务量最大 收益最大 2 给出一项 任务 问怎样统筹安排 能使完成这项任务投入的人力 物力最小 因为研究的对象是人 物等个体 故yx 往往是整数 较yx 不是整数时求解困难 所以这是一个应用数学知识 解决实际问题的新难点 加之教材介绍较为笼统简略 对教师和学生的理解掌握造成了一 定的困难 针对这一问题 总结两种寻找最优整解的方法与大家探讨 这两种求解方法分别是 调整优值法 简称调值法 枚举整点法 简称枚举法 调值法 是先求非整点最优解 再借助不定方程 调整最优解 最后筛选出最优解 枚举法 因为 取得最值的整点分布在可行域内 可从yx 中选取系数的绝对值较大的一个对其逐一取值 以此为标准分类讨论 取得另一变量的最值 代入目标函数 比较函数值大小 找到最优 解 下面通过几个典型例题 介绍一下这几种方法的具体运用 例 1 调整优值法 要将两种大小不同的钢板截成 A B C 三种规格 每张钢板可同时 截得三种规格的小钢板的块数如下表所示 规格类型 钢板类型 A 规格 B 规格 C 规格 第一种钢板 2 1 1 第二种钢板 1 2 3 今需 A B C 三种规格的成品分别为 15 18 27 块 问各截这两种钢板多少张可得 所需三种规格成品 且使所用钢板张数最少 解析 设需要第一种钢板 x 张 第二种钢板 y 张 钢板总数 z 张 则 NyNx yx yx yx 273 182 152 目标函数 zxy 2 作出可行域如图所示 作出直线0 xy 作出一组平行直线xyt 其中t为 参数 其中经过可行域内的点且和原点距离最近的直线 经过直线 273 yx 和直线 152 yx的交点 18 39 55 A 直线方程为 5 57 yx 由于 18 5 和 39 5 都不是整数 而最优解 x y中 x y必须都是整数 所以 可行域内 点 18 39 55 A不是最优解 经过可行域内的整点 横坐标和纵坐标都是整数的点 且与原点距离最近的直线是 12xy 经过的整点是 B 3 9 和 C 4 8 它们是最优解 故要截得所需三种规格的钢板 且使所截两种钢板的张数最少的方法有两种 第一种 截法是截第一种钢板 3 张 第二种钢板 9 张 第二种截法是截第一种钢板 4 张 第二种钢 板 8 张 两种方法都最少要截两种钢板共 12 张 点评 在解线性规划问题时 常有一些实际问题需要变量取整数解时才有实际意义 而当可行域中的最优解不是整数解时 需作出可行域的整点作出判断 当直接观察比较困 难时 应对可能的情况进行检验 线性规划整数解问题的一般处理方法是 若区域 顶点 处恰为整点 那么它的最优解在 顶点 处取得 在包括边界的情况下 若区域的 顶 点 不是整数点也不包括边界时 可以先算出目标函数z的值 在可行域内适当放缩目标 函数的值 使他为整数 且与z最接近 在这条对应的直线 取可行域内的整点 如果没 有整点 继续放缩 直至取到整点为止 这种方法称为调整优值法 也可以通过画出网格 平移直线 运用图解法求得 例 2 枚举法 某人有楼房一栋 室内面积共 180 2 m 拟分隔成两类房间作为旅游客房 大房间每间面积为 18 2 m 可住游客 5 名 每名游客每天住宿费为 40 元 小房间每间面 3 积为 15 2 m 可住旅客 3 名 每名游客每天住宿费为 50 元 装修大房间每间需 1000 元 装修小房间每间需 600 元 如果他只能筹款 8000 元用于装修 且假设游客能住满客房 它 隔出大房间和小房间各多少间会获得最大收益 最大收益是多少 解 设隔出大 小房间分别为x间 y间 收益为f元 则200150fxy 其中 x y满足 6560 5340 0 0 xy xy x y 如图所示 由图解法易得200150fxy 过点 20 60 77 时 目标函数 f取得最大值 但 x y必须是整数 还需在可行区域内找出使目标函数f取得最大值的整点 显然目标函 数f取得最大值的整点一定是分布在可行区域的右上侧 则利用枚举法即可求出整点最优 值 这些整点有 0 12 1 10 2 9 3 8 4 6 5 5 6 3 7 1 8 0 分别代入200150fxy 逐一验证 当取整点 0 12 或 3 8 时 获得最大收益 所以获得最大收益有两种方案 I 只隔出小房间 12 间 II 隔出大房间 3 间 小房间 8 间 最大收益均为 1800 元 注 如果把装修考虑在内 则选择第一方案好 枚举整点法的主要步骤是验算 筛选 而优值调整法更注重推理计