《st-简单的线性规划应用问题最新版本》由会员分享，可在线阅读，更多相关《st-简单的线性规划应用问题最新版本（24页珍藏版）》请在金锄头文库上搜索。
1、 线性规划的应用问题 1 复习线性规划的有关概念 1 由x y的不等式 或方程 组成的不等式组称为x y的约束条件 2 关于x y的一次不等式或方程组成的不等式组称为x y的线性约束条件 3 欲求最大值或最小值所涉及的变量x y的解析式称为目标函数 关于变量x y的一次解析式称为线性目标函数 求线性目标函数在线性约束条件下的最大值或最小值问题称为线性规划问题 4 满足线性约束条件的解 x y 称为可行解 所有可行解组成的集合称为可行域 5 使目标函数取得最大值或最小值的可行解 x y 称为最优解 结论 2 把目标函数转化为某一直线 其斜率与可行域边界所在直线斜率的大小关系一定要弄清楚 解线性规
2、划问题的步骤 2 移 在线性目标函数所表示的一组平行线中 利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线 3 求 通过解方程组求出最优解 4 答 作出答案 1 画 画出线性约束条件所表示的可行域 归纳 例1 营养学家指出 成人良好的日常饮食应该至少提供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多
3、少kg 分析 将已知数据列成表格 解 设每天食用xkg食物A ykg食物B 总成本为Z 则 目标函数为 Z 28x 21y 作出二元一次不等式组所表示的平面区域 即可行域 把目标函数Z 28x 21y变形为 x y o 5 7 5 7 6 7 3 7 3 7 6 7 它表示斜率为随Z变化的一组平行直线系 是直线在y轴上的截距 当截距最小时 Z的值最小 M 如图可见 当直线Z 28x 21y经过可行域上的点M时 截距最小 即Z最小 M点是两条直线的交点 解方程组 得M点的坐标为 所以Zmin 28x 21y 16 由此可知 每天食用食物A约143g 食物B约571g 能够满足日常饮食要求 又使花
4、费最低 最低成本为16元 解线性规划应用问题的一般步骤 2 设好变元并列出不等式组和目标函数 3 由二元一次不等式表示的平面区域做出可行域 4 在可行域内求目标函数的最优解 1 理清题意 列出表格 5 还原成实际问题 准确作图 准确计算 例2 要将两种大小不同规格的钢板截成A B C三种规格 每张钢板可同时截得三种规格的小钢板的块数如下表所示 解 设需截第一种钢板x张 第一种钢板y张 则 2x y 15 x 2y 18 x 3y 27 x 0 y 0 作出可行域 如图 目标函数为z x y 今需要A B C三种规格的成品分别为15 18 27块 问各截这两种钢板多少张可得所需三种规格成品 且使
5、所用钢板张数最少 X张 y张 例题分析 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 解得交点B C的坐标B 3 9 和C 4 8 调整优值法 2 4 6 18 12 8 27 2 4 6 8 10 15 但它不是最优整数解 作直线x y 12 答 略 2x y 15 x 3y 27 x 2y 18 x y 0 经过可行域内的整点B 3 9 和C 4 8 时 t x y 12是最优解 答 略 作出一组平行直线t x
6、 y 目标函数t x y 打网格线法 在可行域内打出网格线 当直线经过点A时t x y 11 4 但它不是最优整数解 将直线x y 11 4继续向上平移 1 2 1 2 18 27 15 9 7 8 在可行域内找出最优解 线性规划整数解问题的一般方法是 1 若区域 顶点 处恰好为整点 那么它就是最优解 在包括边界的情况下 2 若区域 顶点 不是整点或不包括边界时 应先求出该点坐标 并计算目标函数值Z 然后在可行域内适当放缩目标函数值 使它为整数 且与Z最接近 在这条对应的直线中 取可行域内整点 如果没有整点 继续放缩 直至取到整点为止 3 在可行域内找整数解 一般采用平移找解法 即打网络 找整
7、点 平移直线 找出整数最优解 不等式组表示的平面区域内的整数点共有 个 巩固练习1 1234 4x 3y 12 x y 0 1 2 3 例3咖啡馆配制两种饮料 甲种饮料每杯含奶粉9g 咖啡4g 糖3g 乙种饮料每杯含奶粉4g 咖啡5g 糖10g 已知每天原料的使用限额为奶粉3600g 咖啡2000g糖3000g 如果甲种饮料每杯能获利0 7元 乙种饮料每杯能获利1 2元 每天在原料的使用限额内饮料能全部售出 每天应配制两种饮料各多少杯能获利最大 解 将已知数据列为下表 解 设每天应配制甲种饮料x杯 乙种饮料y杯 每天能获利Z元 则 把直线l向右平移 经过可行域上的点C时 Z 0 7x 1 2y
8、取得最大值 Z 0 7x 1 2y 作直线l 0 7x 1 2y 0 由解得点C的坐标为 200 240 则每天应配制两种饮料各200和240杯能获利最大 练习巩固 由上表可知 1 只生产书桌 用完木工板了 可生产书桌600 2 300张 可获利润 80 300 24000元 但木料没有用完 2 只生产书橱 用完方木料 可生产书橱90 0 2 450张 可获利润120 450 54000元 但木工板没有用完 分析 300 600 A 100 400 1 设生产书桌x张 书橱y张 利润为z元 则约束条件为 Z 80 x 120y 作出不等式表示的平面区域 当生产100张书桌 400张书橱时利润最
9、大为z 80 100 120 400 56000元 2 若只生产书桌可以生产300张 用完木工板 可获利24000元 3 若只生产书橱可以生产450张 用完方木料 可获利54000元 将直线z 80 x 120y平移可知 900 450 解 2 某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资的任务 该公司有8辆载重量为6吨的A型卡车和4辆载重量为10吨的B型卡车 有10名驾驶员 每辆卡车每天往返的次数为A型卡车4次 B型卡车3次 每辆卡车每天往返的成本费A型卡车为320元 B型卡车为504元 问如何安排车辆才能使该公司所花的成本费最低 最低为多少元 要求每型卡车至少安排一辆 4 x
10、 8 y 4 x y 10 4x 5y 30 320 x 504y 0 解 设每天调出的A型车x辆 B型车y辆 公司所花的费用为z元 则 Z 320 x 504y 作出可行域中的整点 可行域中的整点 5 2 使Z 320 x 504y取得最小值 且Zmin 2608元 作出可行域 小结 1 本节课主要学习的简单线性规划的实际应用 解决此类问题的步骤 1 理清题意 列出表格 2 设好变元并列出不等式组和目标函数 3 由二元一次不等式表示的平面区域做出可行域 4 在可行域内求目标函数的最优解 5 还原成实际问题 准确作图 准确计算 2 求最优整数解的方法 调整优值法 打网格线法 作业布置 P93A组3 4题
