简单线性规划问题3.ppt

例题分析 例题分析 例题分析 例题分析 例题分析 例题分析 在可行域内找出最优解、线性规划整数解问题的一般方法是： 1.若区域“顶点”处恰好为整点，那么它就是最优解；（在包括边界的情况下） 2.若区域“顶点”不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值Z，然后在可行域内适当放缩目标函数值，使它为整数，且与Z最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。 3.在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解 练习巩固 * x y o ——线性规划的简单应用 使z=2x+y取得最大值的可行解为 　 ， 且最大值为 ； 复习引入 1.已知二元一次不等式组 { x-y≥0 x+y-1≤0 y≥-1 （1）画出不等式组所表示的平面区域； 满足 　　　 的解(x,y)都叫做可行解； z=2x+y 叫做 　　 ； （2）设z=2x+y，则式中变量x,y满足的二元一次不等式组叫做x,y的 　　　　 ； y=-1 x-y=0 x+y=1 2x+y=0 返回 (-1,-1) (2,-1) 使z=2x+y取得最小值的可行解 　 ， 且最小值为 ； 这两个最值都叫做问题的 。 线性约束条件 线性目标函数 线性约束条件 (2,-1) (-1,-1) 3 -3 最优解 x y 0 1 1 例1:某工厂生产甲、乙两种产品.已知生产甲种产品1t需消耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1吨需消耗A种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润是600元,每1t乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、消耗B种矿石不超过200t、消耗煤不超过360t.甲、乙两种产品应各生产多少(精确到0.1t),能使利润总额达到最大? 利润（元） 煤（t） B种矿石（t） A种矿石（t） 资源限额 （t） 乙产品 （1t） 甲产品 （1t） 产品 消耗量 资源 列表： 5 10 4 600 4 4 9 1000 300 200 360 设生产甲、乙两种产品.分别为x t、yt,利润总额为z元 利润（元） 煤（t） B种矿石（t） A种矿石（t） 资源限额 （t） 乙产品 （1t） 甲产品 （1t） 产品 消耗量 资源 列表： 5 10 4 600 4 4 9 1000 300 200 360 把题中限制条件进行转化： 约束条件 10x+4y≤300 5x+4y≤200 4x+9y≤360 x≥0 y ≥0 z=600x+1000y. 目标函数： 设生产甲、乙两种产品.分别为x t、yt,利润总额为z元 xt yt 解:设生产甲、乙两种产品.分别为x t、yt,利润总额为z=600x+1000y. 元,那么 { 10x+4y≤300 5x+4y≤200 4x+9y≤360 x≥0 y ≥0 z=600x+1000y. 作出以上不等式组所表示的可行域 作出一组平行直线 600x+1000y=t， 解得交点M的坐标为(12.4,34.4) 5x+4y=200 { 4x+9y=360 由 10x+4y=300 5x+4y=200 4x+9y=360 600x+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=600x+1000y取得最大值. 例2 要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：设需截第一种钢板x张，第一种钢板y张，则 规格类型 钢板类型 第一种钢板 第二种钢板 A规格 B规格 C规格 2 1 2 1 3 1 2x+y≥15, { x+2y≥18, x+