8 第8课 规划分析.ppt

第8章 规划分析 线性规划 目标规划 整数规划 动态规划 内容 提出问题 相关知识导入 基本概念解释 线性规划求解过程—图解法 线性规划结果调整 小结 要求 1 掌握线性规划的三要素 2 根据题目给出的条件能够建立线性规划的模型 3 利用图解法能够找到目标函数的最优解 4 理解线性规划结果的整数调整 提出问题 [例1] 资源合理利用问题 某工厂在某一计划期内准备生产甲、乙两种产品，生产需要消耗煤、电、油三种资源。有关数据列表如下。试拟订使计划期内总收入最大的生产计划方案？ 知识导入 基本概念 线性规划模型的三要素： 决策变量：需决策的量，即待求的未知数。 目标函数：需优化的量，即欲达到的目标，用决策变量的表达式表示。 约束条件：为实现优化目标受到的限制，用决策变量的等式或不等式表示。 在本例中 决策变量：甲、乙产品的计划产量，记为 , 目标函数：总收入记为 , 则 为体现追求极大化，在前面冠以极大号max； 约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为 线性规划模型的一个基本特点 目标和约束均为变量的线性表达式 如果模型中出现如 的非线性表达式，则不属于线性规划。 求解过程—图解法 结果调整 小 结 x2 50 40 30 20 10 10 20 30 40 x1 可行域 O（0，0） Q1（25，0） Q2（15，20） Q3（0，40） 可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解的集合。 该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是以Z作为参数的一组平行线 x2 = Z/30-（5/3）x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当Z值不断增加时，该直线 x2 = Z/30-（5/3）x1 沿着其法线方向向右上方移动。 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当该直线移到Q2点时，Z（目标函数）值达到最大： Max Z=50?15+30 ? 20=1350 此时最优解=（15，20） Q2（15，20） 某工厂生产甲、乙两种产品.已知生产甲种产品1t需消 耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1吨需 消耗A种矿石4t、B种矿石4t、煤9t。每1t甲种产品的利润 是600元,每1t乙种产品的利润是1000元。 工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、 消耗B种矿石不超过200t、消耗煤不超过360t。 若你是厂长,你应如何安排甲乙两种产品的产量(精确到0.1t),才能使利润总额达到最大? 例 请写出目标函数和约束条件 决策变量是什么？ 解： 设甲、乙产品的产量分别为 个单位（ ）, 获得总收入为z ，则上述问题的数学模型为 实例分析：设x,y满足以下条件： 求z=2x+y的最大值与最小值。 ① ② ③ 如图，分别作出 三条直线， o 5x+6y=30 y=1 y=3x y y=1, y=3x, 5x+6y=30 再找出不等式组 所表示的平面区域的公 共区域。 可行域 x 设z=0,画出直线l0， 即l0:2x+y=0。 o 5x+6y=30 y=1 y=3x y x l0:2x+y=0 如图，平移直线l0， 所对应的z随之增大； 所对应的z随之减小。 当直线l0向上平移时， 当直线l0向下平移 时, o 5x+6y=30 y=1 y=3x y l0:2x+y=0 l1:2x+y=2 l2:2x+y=4 l3:2x+y=-3 此时所对应的Z最小； 此时所对应的Z最大。 从而得到： zmin zmax =2× +1= =2× +1= o 5x+6y=30 y=1 y=3x y x A B C l0:2x+y=0 如图，在把l0向上平移过程中，直线与平面区 域首先相交于点A ， 当相交于点B ， l1 l2 总结： 从这个问题的求解过程可以 看出，最优解一般在可行域的边 界上，而且通常在可行域的顶点 处取得。 5x+4y=20 2x+3y=12 线性目标函数 Z的最大值为44 已知实数x,