《简单的线性规划》PPT课件

简单的线性规划 (第三课时 ) 5x+4y=20 2x+3y=12 线性目标函数 ),(M 720712 Z的最大值为 44 已知实数 x,y满足下列条件 : 5x+4y 20 2x+3y 12 x 0 y0 求 z=9x+10y的最大值 . 最优解 可行域 9x+10y=0 想一想 : 线性约束 条件 0 1 2 3 4 5 6 1 2 3 4 5 6 x y 代数问题 (线性约束条件 ) 图解法 转化 线性约 束条件 可行域 转化 线性目 标函数 Z=Ax+By 一组平行线 B Zxy 转化 最优解 图解法的步骤： 1。 画 可行域 ; 4。 求出最优解作 答 . 3。 平 移 直线 L0找最优解 ; 2。 作 Z=0时的直线 L0. 三个转化 一 .复习 平行线在 y轴上 的截距 最值 B Z 某工厂生产甲、乙两种产品 .已知生产甲种产品 1t需消 耗 A种矿石 10t、 B种矿石 5t、煤 4t；生产乙种产品 1t需 消耗 A种矿石 4t、 B种矿石 4t、煤 9t. 每 1t甲种产品的利润 是 600元 ,每 1t乙种产品的利润是 1000元 .工厂在生产这两 种产品的计划中要求消耗 A种矿石不超过 300t、 消耗 B种 矿石不超过 200t、消耗煤不超过 360t.你应如何安排甲乙 两种产品的产量 (精确到 0.1t),才能使利润总额达到最大 ? 二 .实际应用 探索问题一 : 某工厂生产甲、乙两种产品 .已知生产甲种产品 1t需消 耗 A种矿石 10t、 B种矿石 5t、煤 4t；生产乙种产品 1t需消 耗 A种矿石 4t、 B种矿石 4t、煤 9t.每 1t甲种产品的利润是 600元 ,每 1t乙种产品的利润是 1000元 .工厂在生产这两种 产品的计划中要求消耗 A种矿石不超过 300t、 消耗 B种 矿石不超过 200t、消耗煤不超过 360t. 你应如何安排甲乙 两种产品的产量 (精确到 0.1t),才能使利润总额达到最大 ? 分 析 问 题 : 2.本问题给定了哪些原材料？ 1.该工厂生产哪些产品 ? 3.每吨产品对原材料的消耗量各是多少 ? 4.该工厂对原材料有何限定条件 ? 5.每种产品的利润是多少 ? 原 材 料 每吨产品消耗的原材料 A种矿石 B种矿石 煤 甲产品 (t) 乙产品 (t) 10 5 4 4 4 9 原 材料 限 额 300 200 360 利 润 600 1000 xt yt 10 x+4y300 5x+4y200 4x+9y360 x0 y 0 z=600 x+1000y. 目标函数 ： 设生产甲、乙两种产品的产量分别为 x t、 yt,利润总额为 z元 解 :设生产甲 、 乙两种产品 .分别为 x t、 yt,利润总额为 z元 ,那么 10 x+4y300 5x+4y200 4x+9y360 x0 y 0 z=600 x+1000y. 画 出以上不等式组所表示的可行域 作 出直线 L 600 x+1000y=0. 解得交点 M的坐标为 (12.4,34.4) 5x+4y=200 4x+9y=360 由 10 x+4y=300 5x+4y=200 4x+9y=360 600 x+1000y=0 M 答 :应生产甲产品约 12.4吨 ， 乙产品 34.4吨 ， 能使利润总额达到最大 。 (12.4,34.4) 经过可行域上的点 M时 ,目标函数 在 y轴上截距最大 . 90 30 0 x y 10 20 10 75 40 50 40 此时 z=600 x+1000y取得最大值 . 4834 29 1000 4112 29 360 .y .x 把直线 L向右上方平 移 实际问题 线性规划问题 列 出约束条件 建 立目标函数 分析问题 (列表 ) 设 立变量 转 化 列约束条件时要注意到变量的范围 . 注意 : 解 决 问题 最 优 解 某工厂现有两种大小不同规格的钢板可截成 A、 B、 C三种规格 ， 每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 规格类型 钢板类型 第一种钢板 第二种钢板 A规格 B规格 C规格 2 1 2 1 3 1 某顾客需要 A,B,C三种规格的成品分别为 15， 18， 27块， 若你是 生产部经理 ,问各截这两种钢板多少张既能满足顾客要求又使所 用钢板张数最少。 探索问题二 : 解： 设需截第一种钢板 x张，第二种钢板 y张， 钢板 总 张数 为 Z,则 2x+y15, x+2y18, x+3y27, x0 y0 目标函数 : z=x+y )Ny,x( x 0 y 2x+y=15 x+3y=27 x+2y=18 x+y =0 2x+y15, x+2y18, x+3y27, x0, y0 在可行域内直线 x+y=12经过的 整点是 B(3,9)和 C(4,8)， 它 们是最优解 . 作出直线 L:x+y=0， 目标函数 :z= x+y B(3,9) C(4,8) A(3.6,7.8) 当直线 L经过点 A时 z=x+y=11.4, x+y=12 2 4 6 18 12 8 27 2 4 6 8 10 15 但它不是最优整数解 . 作直线 x+y=12 答（略） 约束条件 : 画可行域 平移 L找交点 及交点坐标 )Ny,x( 图 例题 4.gsp示 继续平移 L找最优整数解 调整 Z的值 , X+y=11.4 A 调整优值法 即先求非整数条件下的最优解， 调整 Z的值使不定方程 Ax+By=Z存在最大（小） 的整点值，最后筛选出整点最优解 即先打网格，描出可行域内的 整点 ， 平移直线，最先经过 (或最后 )经过的整点 坐标即为最优整解 线性规划求最优整数解的一般方法 : 1.平移找解法： 2.调整优值法 ： 小结 咖啡馆配制两种饮料甲种饮料每杯含奶粉 9g 、咖啡 4g、糖 3g,乙种饮料每杯含奶粉 4g 、 咖啡 5g、糖 10g已知每天原料的使用限额为 奶粉 3600g ，咖啡 2000g 糖 3000g,如果甲种饮 料每杯能获利 0.7元，乙种饮料每杯能获利 1.2 元每天在原料的使用限额内饮料能全部售出， 每天应配制两种饮料各多少杯能获利最大 ？ 练习一 .gsp - 巩固练习一 解 :设每天应配制甲种饮料 x杯 ， 乙种饮料 y杯 ， 则 0 0 30 00103 20 0054 36 0049 y x yx yx yx 作出可行域： 目标函数为： z =0.7x +1.2y 作直线 l:0.7x+1.2y=0， 把直线 l向右上方平移至 l1的位置时 ， 直线经过可行域上的点 C， 且与原点 距离最大 ， 此时 z =0.7x +1.2y取最大值 解方程组 得点 C的坐标为 （ 200， 240） ,3000103 ,200054 yx yx _ 0 _ 9 x + 4 y = 3600 _ C ( 200 , 240 ) _ 4 x + 5 y = 2000 _ 3 x + 10 y = 3000 _ 7 x + 12 y = 0 _ 400 _ 400 _ 300 _ 500 _ 1000 _ 900 _ 0 _ x _ y 目标函数为： z =0.7x +1.2y 答 :每天配制甲种饮料 200杯 ,乙种饮料 240杯可获取最大利润 . 小结 小结 : 实际问题 分析问题 设出变量 列出约束条件 建立目标函数 转化 建模 线性规划 问题 图解法 理论 最优解 三 个 转 化 四个步骤 调 整 实际 最优解 平移找解法 调整优值法 常用方法 整数 最优解 作 答 思考问题一 : 探索问题一 (课本例题 3)的最优解是 (12.4,34.4). 它存在最优整数解吗 ?若存在 ,求出最优整数解 . 若不存在 ,请说明理由 . 例 3.gsp图形 作业 :习题 7.4 第 3题 ;第 4题 结束 某货运公司拟用集装箱托运甲 .乙两种货物 ,一个大集装 箱所装托运货物的总体积不能超过 24 ,总重量不能 超过 1500kg,甲 .乙两种货物每袋的体积 .重量和可获得 的利润 ,列表如下 : 思考问题 二 3m 货物 每袋体积 (立方米 ) 每袋重量 (100kg) 每袋利润 (单位百元 ) 甲 5 2 20 乙 4 3 15 问在一个大集装箱内这两种 (不能只装一种 )货物各装多 少袋时 ,可获得最大的利润 ? 解 :设托运甲货物 x袋 , 托运乙货物 y袋 ,获得利润为 z(百元 ) 图象 Z=20 x+15y (x,y ) N 5x+4y 24 2x+3y 15 X0 Y0