《ch05目标规划》PPT课件.ppt

教学要求： 第五章 目标规划 掌握目标规划的建模方法 掌握线性目标规划基本求解方法 目标规划概述 p 企业管理中经常碰到多目标决策的问题，例 如企业拟订生产计划时，不仅要考虑总产值，而 且要考虑利润、产品质量和设备利用率等。有些 目标之间往往互相矛盾。例如，企业利润可能同 环境保护目标相矛盾。如何统筹兼顾多种目标， 选择合理方案，是十分复杂的问题。应用目标规 划可以较好的解决这类问题。 p 对有矛盾的多种目标区别优先顺序或优先等 级，来解决多目标决策问题。 目标规划概述 p1961年，美国运筹学家查恩斯和库伯提出了一 种用于求解多于一个目标的线性决策模型的方法 ，并提出了目标规划的概念。 p目标规划概念：是在给定的决策环境中，使决策 结果与预定目标的偏差达到最小化的数学模型。 决策环境包括决策变量、约束条件和目标函数等 基本组成部分。 目标规划概述 p目标规划与线性规划的区别 n在线性规划中，要求单个目标的优化，而目标 规划则强调使多个目标得到满意的解答 。 n线性规划中，为得到一个可行解，必须满足所 有的约束条件。在目标规划中，并不认为所有 约束都是绝对的，因此对于非绝对的约束，目 标规划并不要求绝对满足，而是设法使各目标 离原先设定的意向指标值的偏差尽可能的小。 目 录 p目标规划实例与模型 p目标规划求解方法 p用Excel求解目标规划的解 目 录 p目标规划实例与模型 p目标规划求解方法 p用Excel求解目标规划的解 一、建立模型举例：例5.1 p 设某公司生产两种型号的电扇，一种为普通型，装配一个 需要1小时，另一种为豪华型，装配一个需要2小时。正常的 装配时间每周限定为40小时。市场调查表明每周销售普通型 不超过30件，豪华型不超过15件。普通型每件的净利润为 8元，豪华型为每件12元。 p公司经理提出如下优先次序的要求： n1总利润最大（显然的） n2装配线尽可能少加班（避免装配线超负荷损坏） n3销售尽可能多的电扇（这同尽可能获取最大利润一致 ）。 由于每件豪华型的利润是普通型的1.5倍，因此公司 对销售豪华型的愿望是销售普通型的1.5倍 同时，根据市场调研要求每周生产的产品数不能多 于销售的数量，即普通型电扇为30件，豪华型电扇为15 件。 目标规划数学模型有关概念 1. 决策变量，正负偏差变量 设X1，X2，,Xn为决策变量，同时引进 正负偏差变量 正偏差变量 表示决策值超过目标值的 部分，负偏差变量 表示决策值未达到目标 值的部分，恒有 正、负偏差变量的概念： 目标值 bi （未达目标的）实际值fi （超过目标的）实际值fi f(x ) 2.目标约束 p 绝对目标约束（或硬约束）是指必须要严格满 足的等式或不等式约束，如线性规划问题的所有 约束条件，具有最高优先级。 p 目标约束（软约束）是把约束右端项看作是目 标值，在达到此目标值时允许发生正或负偏差， 在约束中加入正、负偏差变量。 p 可根据问题的需要将绝对目标约束变换为目标 约束，目标约束的形式为： 3.优先权因子（优先等级）和权系数 p 要求达到第一位的目标赋予优先权因子P1，第 二位的目标赋予优先权因子P2，。并规定： P1 P2 Pn 即首先保证P1级目标的实现， P2级目标是在实 现P1级目标的基础上考虑的，以此类推。 p要区别具有相同优先权因子的两个目标的差别， 可分别赋予目标不同的权系数 4.指标偏离函数（目标规划的目标函数min） 将各目标约束的正负偏差变量和相应的优先权 因子及权系数一起组成的一个函数，称为指标偏 离函数或目标规划的目标函数。 在实际中，可以根据决策者的要求， 引入正、负偏差变量和目标约束，并给不 同目标赋予相应的优先因子和权系数，构 造目标函数，建立模型。 例5.1模型建立 第一优先级 决策目标 正偏差：决策 值超过目标值的 偏差部分 负偏差：决策 值小于目标值的 偏差部分 指标偏离函数 约束条件 在同一等级目标 中，赋予不同权 系数 目标规划的一般模型为： 不含有偏差变量，为绝对 目标约束 非负约束 目标约束 目标函数 其中 xj（ ）为决策变量； Pk（ ）为第k级优先因子； 分别为第l个目标约束的正负偏差变量的权 系数，在同一等级的目标中，根据对各因子考虑的先 后次序的不同，赋予不同权系数。 （ ）为目标的预期目标值； bj 为系统的资源量。 注：权系数这个概念可以省去，多定义一个优先级就可以区分出来 模型的基本思想 给定若干目标以及实现这些目标的优先 顺序，在有限的资源条件下，使总的偏离 目标值的偏差最小。 二、建立目标规划模型的步骤 p第一步：定义决策变量和有关的常量 建立模型的第一步就是定义决策变量和决策目 标约束等式右边的常数。等式右边的常数是可利 用的资源或是决策者特定的目标值。 p第二步：建立决策目标约束 通过分析决策变量之间的关系以及决策变量与 目标值之间的关系，建立一组目标约束。并从所 有的决策目标中，找出绝对决策目标（即，如果 不满足将导致最终结果无法实现的目标），将这 些目标作为第一优先级。而后再确定其余目标的 优先级。 p第三步：建立指标偏差函数 根据各目标的要求，对于每一个要达到的目 标，其相应的偏离变量赋予由第二步对各目标确 立的优先等级。通过使各偏差变量的极小化，建 立指标偏差函数，并写出目标规划模型。 示例二： 某工厂生产甲、乙两种产品，有关数据见下表 。试求获利最大的生产方案。 决策者在原材料供应受严格限制的基础上考虑 ：首先产品乙的产量不低于产品甲的产量；其次充 分利用设备台时，不加班；再次尽可能达到并超过 计划利润指标56元。求决策方案。 甲 乙 拥拥有量 原材料（kg） 设备设备 （hr） 2 1 1 2 11 10 利润润（元/件） 8 10 解：按决策者所要求的，分别赋予三个目标 P1，P2，P3优先因子。目标规划的模型为： 目 录 p目标规划实例与模型 p目标规划求解方法 p用Excel求解目标规划的解 再满足P4 ,使 , 极小化，由于 是 的 1.5倍，先考虑 先满足P1 =0, =0 一、图解法例5.2 再满足P2 使 =0 再满足P3 使 极小化 最优解X1*=25， X2*=15，a*=（ 0，0，60，5） 二、单纯形方法例5.4 p 某纺织厂生产两种布料，窗帘布和布料，平均生产能力 都是1000m/h。工厂的正常生产能力是每周80h，根据 市场预测，下周的最大销售量为：窗帘布70000m，衣料 45000m。窗帘布每m获利2.5元，衣料为每m1.5元。 从长远利益角度出发，工厂经理提出以下四个优先次序 的目标： pP1:避免开工不足； pP2:加班时间不超过10h； pP3:努力到达最大销售量，即窗帘布70千m，衣料45千m pP4:尽可能减少加班时间。 建立如下目标规划模型： 设x1，x2分别表示生产窗帘布和衣料的小时数 求解注意几点： 目标规划模型仍可以用单纯形方法求解 ，在求解 时作以下规定： p1.目标规划的目标优先等级和权系数取代了线 性规划目标函数中的价值系数Ci； p2.因为目标函数都是求最小值，所以，最优判 别检验数为 或者 检验数不能写成一行，而是一个mn的矩阵， m是优先等级的数目，n是变量的数目，包括决 策变量和偏差变量； p3.检验数是一个矩阵，在选择最优列时，必须 严格按优先等级次序考虑，Pi总是优先于Pi+1 求解步骤： p1.建立初始单纯形表，在表中按优先因子个数 （m个）以及优先次序和变量个数（n个）列出 检验数矩阵； p2.依据最优解判别规则进行最优解检验，当得 到满意解，计算结束，否则进行下一步； p3.从检验数栏中最优等级P1行开始寻找最大正 检验数，如果P1行内有最大正检验数，该数所 在列确定为最优列，该列对应的变量为换入变 量。若P1行内无最大正检验数，则在P2行内寻 找，依次类推； p4.按最小比值规则（常数项B被最优列系数（系 数0）除所得数的最小值）确定换出变量，当存 在两个和两个以上相同的最小比值时，选取具有 较高优先级别的变量为换出变量；（教材上定义 换出变量所在行为关键行） p5.最优列和关键行的交点为主元素，消元，按单 纯形法进行行变换运算，建立新的单纯形表，返 回2。 最优解判别规则 p从下往上检查B列下部元素（即检验数栏中对 应的B列元素）是否全部为0？如果全部为0， 表示全部目标已经达到，这就是最优解，此时 检验数全为 p如果B列下部元素中有正数，则这一等级目标 没有达到，检查这一行的检验数，如果这一行 有正检验数，再看正检验数所在列的下面（优 先级较高一级的检验数栏）是否有负检验数？ 如果没有负检验数，则尚未达到最优解，还可 以继续改进；如果这一行的全部正检验数的下 面都有负检验数，则这个目标虽未达到，但再 也不能改进了，所以也就是最优解。 例5.4 用单纯形法求解 ci P15P33P3 P4P2 ziVBx1x2d1 -d2-d3-d11-d1+d11+ P1d1 -80111 -1 5P3d2-701 1 3P3d3 -45 1 1 d11 -10 11-1 P40 -1 P348553 P20 -1 P18011 -1 在选择最优列时，先从检验数栏中最优等级 行开始寻找最大正检验数。 如 行内有最大正检验数，就确定它为最优列，进行迭代。直到 行内检验 数没有正值为止，再转入 行寻找最大检验数。如此继续下去，直到所有检 验数全部检查完毕。 检验数的计算：以 列为例，此时， ， 所以， 。故在