目标规划与求解.ppt

第四章 目标规划购买电视机 1、类型2、品牌3、价位4、质量5、尺寸液晶、等离子、背投、纯屏、超屏 一般来说，一个计划问题要满足多方面的要求财务部门可能希望尽可能大的利润，以实现其利润指标物资部门希望尽可能小的物资消耗，以节约储备资金占用销售部门希望产品品种多样，适销对路计划部门可能希望有尽可能大的产品批量一个计划问题实际是一个多目标决策的问题只是用线性规划来处理，计划人员不得不从众多目标要求中硬性选择其一，作为线性规划的目标函数线性规划问题有最优解的必要条件是其可行解集 非空，即各约束条件彼此相容在生产计划中，由于储备资金的限制，原材料的最大供应量不能满足计划产量的需要时，从供给和需求两方面产生的约束条件彼此就是互不相容的由此可见，线性规划并不是完美无缺的在处理问题时它存在着由本身的“刚性”所注定的某些固有的限制性定量与定性、硬技术与软技术、矛盾与冲突的合理妥协与避让1961年，查恩斯和库柏提出了目标规划在处理问题时，承认各项决策要求（冲突）的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性第一节第一节 目标规划的基本概念与数学模型目标规划的基本概念与数学模型一、问题的提出一、问题的提出例例1 1：TM公司是一家规模较小的化妆品生产企业，以前 仅生产一种指甲上光油。

一次一个雇员偶然把一罐花生 酱倒入上光油中，结果发现这种混合物能够暂时去除脸 部的皱纹这样，公司就开始生产两种产品：指甲上光 油和皱纹去除霜改进后的产品配方需要两种不同的基 本化学物列于下表两种化学物的日用量是限定的，其 生产能力已达最大由于配方保密的原因，公司每天购 买的花生酱不超过6磅产产品每加仑仑利 润润每加仑仑所需化学 物A的磅数每加仑仑所需化 学物B的磅数每加仑仑所需花 生酱酱的磅数青春霜80441指甲上光油100520日供应应量（ 磅80486 公司经理提出如下要求： 1）A、B两种化学品的日用量无论如何不能超过规定； 2）希望每天利润超过﹩ ﹩ 1800； 3）每天订购的花生酱保持在6磅水平； 4）每天两种产品生产的加仑总数应尽可能少，以便节省装运和人力费用 试为该公司指定合理的生产方案例例2 2：某生物药厂需在市场上采购某种原料，现市场上有甲、乙两个等级，单价分别为2千元/kg和1千元/kg，要求采购的总费用不得超过20万元，购得原料的总重量不少于100kg，而甲级原料又不得少于50kg，问如何确定最好的采购方案（即用最少的钱、采购最多数量的原料）． 目标函数为：解：设 分别为采购甲级、乙级原材料的数量（单位：kg）约束条件有：约束条件有： 例例2 2：某生物药厂需在市场上采购某种原料，现市场上有甲、乙两个等级，单价分别为2千元/kg和1千元/kg，要求采购的总费用不得超过20万元，购得原料的总重量不少于100kg，而甲级原料又不得少于50kg，问如何确定最好的采购方案（即用最少的钱、采购最多数量的原料）． 目标函数为：约束条件有：约束条件有： 分析分析：：这是一个含有两个目标的数学规划问题． 设 分别为采购甲级、乙级原材料的数量（单位：kg）为花掉的资金， 为所购原料总量．则：例例3 3 某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如表所示．试确定计划期内的生产计划，使利润最大，同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标 规划问题． 甲（每件 ）乙（每件 ）现有资源钢 材 （ kg ）9.243600木 材 ( m3 )452000 设备负荷（台小时 ）3103000单位产品利润 (元)70120例例3 3 某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如表所示．试确定计划期内的生产计划，使利润最大，同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产，同时考虑这些问题，就形成多目标 规划问题． 分析分析: : 设 分别是计划期内甲、乙产品的产量．则该问 题的数学模型为 甲（每件 ）乙（每件 ）现有资源钢 材 （ kg ）9.243600木 材 ( m3 )452000 设备负荷（台小时 ）3103000单位产品利润 (元)70120分析分析: : 设 分别是计划期内甲、乙产品的产 量．则该问题的数学模型为 二、目标规划的基本概念二、目标规划的基本概念多目标规划问题的一般形式如下(简记为：GP1)但更多的情况是：由于多目标之间存在相互矛盾，最优解往往不可能存在，这就要求我们退而求其次，根据目标之间的相对重要程度，分等级和权重，求出相对最优解相对最优解——有效解有效解（满意解满意解），为此引入以下概念，对目标函数和约束条件作适当处理． 1 1．决策变量与偏差变量．决策变量与偏差变量 决策变量也称控制变量，用x1、x2、…、xn表示． 理想目标：是反映决策者欲望的一个比较笼统的提法，譬如：“利润最大”、“消除贫困”、“每天两种产品生产的加仑总数尽可能少”等。

期望值：是达到理想目标的满意的、或可接受的一个特定值，它可以用来度量理想达到的程度从实际出发，根据经验、历史资料或市场的需求、上级部门的任务下达等来给每个目标确定一个希望达到的期望值期望值ei , (i =1，2，…，m)．称实际值（实际结果）与期望值（愿望）的差距为偏差变量．除特殊情况外，一般问题都需计算其目标偏差这个偏差即有正的差异，也有负的差异——第i个目标的实际值超出目标值的部分，称 为正偏差变量． ——第i个目标的实际值不足目标值的差距，称为负偏差变量．规定表示第i个目标的实际值超出超出目标值表示第i个目标的实际值恰好等于恰好等于目标值．并且无论发生哪种情况均有:表示第i个目标的实际值未达到未达到目标值前面通过确定各目标的目标值目标值、引入偏差变量，把目标函数转化成约束方程目标函数转化成约束方程，从而并入原约束条件中，我们称这类具有机动余地的约束具有机动余地的约束为目标约束目标约束．因它具有一定的弹性，不会不满足，只是可能偏差要大一些，故也称为软约束软约束． ２．目标约束与绝对约束２．目标约束与绝对约束实际值+负偏差变量-正偏差变量=目标值 分析分析: : 设 分别是计划期内甲、乙产品的产 量．则该问题的数学模型为 绝对约束绝对约束是指必须严格满足的等式或不等式约束，也称为系统约束系统约束．它对应于线性规划中的约束条件（如资源、客观条件约束等），不能满足绝对约束的解即为不可行解，因此也称为硬约束硬约束． 我们设想将约束条件“放松放松”，对约束方程也引入引入偏差变量偏差变量，使矛盾的方程不再矛盾！然后通过适当的方法，找出问题的关键，即需要增加的资源品种与数量或需降低的产品产量等，就会获得较好的决策效果．这说明两种约束在一定条件下可以转换．硬约束+负偏差变量-正偏差变量=右端项 分析分析: : 设 分别是计划期内甲、乙产品的产 量．则该问题的数学模型为 ３．目标规划的目标函数３．目标规划的目标函数( (达成函数达成函数) )通过引入偏差变量，使原规划问题中的目标函数变成了目标约束目标函数变成了目标约束，那么现在问题的目标是什么呢？判断其优劣的依据是决策值与目标值的判断其优劣的依据是决策值与目标值的偏差越小越好偏差越小越好．① 要求恰好达到目标值的，即正、负偏差变量都要 尽可能小． 构造目标函数为： ．② 要求不能超过目标值的，即允许达不到目标值， 但即使超过，一定要越小越好．构造目标函数为： ．③ 要求超过目标值的，即允许超过目标值，但即使 不足，一定要使缺少量越少越好．构造目标函数为 ： ． 这样根据各个目标的不同要求，确定出总的目标函数总的目标函数分析分析: : 设 分别是计划期内甲、乙产品的产 量．则该问题的数学模型为 ４．优先因子与权系数４．优先因子与权系数第一位要求达到的目标，赋予优先因子优先因子P P1 1，在它实现的前提下再去解决次要目标．依次把第二位达到的目标赋予优先因子优先因子P P2 2……，并规定P Pk k» »P Pk+1k+1若要进一步区别具有相同优先级的多个目标，则 可分别赋予它们不同的权系数 ( 可取一确定的 非负实数)，根据目标的重要程度而给它们赋值，重要的目标，赋值较大，反之值就小．分析分析: : 设 分别是计划期内甲、乙产品的产 量．则该问题的数学模型为 分析分析: : 设 分别是计划期内甲、乙产品的产 量．则该问题的数学模型为 三、目标规划的数学模型三、目标规划的数学模型一般地，对于n个决策变量，m个目标约束，目 标函数中有k个优先级的目标规划问题，其数学模型的标准型如下：其中：Pi 为优先等级； , 为权系数．建立目标规划模型的步骤建立目标规划模型的步骤1） 根据问题所提出的各目标与条件，确定目标值（期望值），设定决策变量并列出目标约束与绝对约束；2） 根据决策者的需要将某些或全部绝对约束，通过引入偏差变量转换为目标约束；3） 给各级目标赋予相应的优先因子 ，对同一优先级的各目标，按重要程度不同赋予相应的权系数 ；4）根据决策者的要求，各目标按三种情况取值： ①恰好达到目标值，取 ；②允许超过目标值，取 ；③不允许超过目标值，取 ．然后构造一个由优先因子、权系数与偏差变量组成的、要求最小化的目标函数最小化的目标函数．最重要的目标、必须严格实现的目标及无法再增 加的资源约束均应列入P1级，其余按重要程度分别列入后面各级，并在同一级中确定权系数．一般地，如 果问题的P1级目标不能完全实现，则我们就认为该问题不可行． 例例1 1：TM公司是一家规模较小的化妆品生产企业，以前 仅生产一种指甲上光油。

一次一个雇员偶然把一罐花生 酱倒入上光油中，结果发现这种混合物能够暂时去除脸 部的皱纹这样，公司就开始生产两种产品：指甲上光 油和皱纹去除霜改进后的产品配方需要两种不同的基 本化学物列于下表两种化学物的日用量是限定的，其 生产能力已达最大由于配方保密的原因，公司每天购 买的花生酱不超过6磅练习：产产品每加仑仑利 润润每加仑仑所需化学 物A的磅数每加仑仑所需化 学物B的磅数每加仑仑所需花 生酱酱的磅数青春霜80441指甲上光油100520日供应应量（ 磅）80486 公司经理提出如下要求： 1）A、B两种化学品的日用量无论如何不能超过规定； 2）希望每天利润超过﹩ ﹩ 1800； 3）每天订购的花生酱保持在6磅水平； 4）每天两种产品生产的加仑总数应尽可能少，以便节省装运和人力费用 试为该公司指定合理的生产方案例例3 3 某制药公司有甲、乙两个工厂，现要生产A、B 两 种药品均需在两个工厂生产．A药品在甲厂加工2h， 然后送到乙厂检测包装2.5h才能成品，B药在甲厂加 工4h，再到乙厂检测包装1.5h才能成品．A、B药在 公司内的每月存贮费分别为8元和15元．甲厂有12台 制造机器，每台每天工作8h，每月正常工作25天， 乙厂有7台检测包装机，每天每台工作16h，每月正 常工作25天，每台机器每小时运行成本：甲厂为18 元，乙厂为15元，单位产品A销售利润为20元，B为 23元，依市场预测次月A、B销售量估计分别为1500 单位和1000单位． 该公司依下列次序为目标的优先次序，以实现 次月的生产与销售目标． P1：厂内的储存成本不超过23000元． P2：A销售量必须完成1500单位． P3：甲、乙两工厂的设备应全力运转，避免有空闲时 间，两厂的单位运转成本当作它们的权系数． P4：甲厂的超过作业时间全月不宜超过30h． P5：B药的销量必须完成1000单位． P6：两个工厂的超时工作时间总和要求限制，其限制 的比率依各厂每小时运转成本为准． 试确定A、B药各生产多少，使目标达到最好，建立目标规划模型并化成标准型． （2。