《多目标函数》PPT课件.ppt

,第四章 目标规划,第一节 目标规划的数学模型,本节内容的安排,目标规划（Goal Programming，简记为GP)是在线性规划 的基础 上，为适应经济管理中多目标决策的需要而逐步发展起来的一个运筹学分支，是实行目标管理这种现代化管理技术的一个有效工具.目标规划的有关概念和模型最早在1961年由美国学者查恩斯（A.Charnes）和库伯（W.W.Coopor）在他们合著的管理模型和性规划的工业应用一书中提出，以后这种模型又先后经尤吉艾吉里（Yuji.Ijiri）等人的不断完善改进，1976年伊格尼齐奥（J.P.Ignizio）发表了目标规划及其扩展一书，系统归纳总结了目标规划的理论和方法目前研究较多的有线性目标规划、非线性目标规划、线性整数目标规划和01目标规划等.本章主要研究线性目标规划,线性规划只研究在满足一定条件下，单一目标 函数取得最优解.,线性规划致力于某个目标函数的最优解，缺点是：这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。,从线性规划问题可看出：,而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。,求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但实际中出现矛盾时，生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。,目标规划正是在线性规划的基础上为适应这种复杂的多目标最优决策的需要，而发展起来的它对众多的目标分别确定一个希望实现的目标值然后按目标的重要程度（级别）依次进行考虑与计算，以求得最接近各目标预定数值的方案如果某些目标由于种种约束不能完全实现，它也能指出目标值不能实现的程度以及原因，以供决策者参考,引例1：某生物药厂需在市场上采购某种原料，现市场上有甲、乙两个等级，单价分别为 2 千元/kg和 1 千元/kg，要求采购的总费用不得超过 20 万元，购得原料的总重量不少于 100 kg，而甲级原料又不得少于 50 kg，问如何确定最好的采购方案?（即用最少的钱、采购最多数量的原料）,一、问题的提出,目标函数为：,约束条件有：,分析：这是一个含有两个目标的数学规划问题 设 x1,x2分别为采购甲级、乙级原材料的数量（单位：kg）y1 为花掉的资金，y2为所购原料总量则：,若只考虑花钱最少，则显然属于线性规划问题，由（1），（3）至（6）构成它的数学模型,若只考虑采购数量最多，则也属于线性规划问题，由（2），（3）至（6）构成它的数学模型,某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测:甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产，在此基础上使产量达到最大。试建立此问题的数学模型。,引例2:,设：甲，乙产品的产量分别为X1,X2,一般有：,maxZ=70 x1+120 x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,同时：,maxZ1=70 x1+120 x2 maxZ2=x1 maxZ3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,显然，这是一个多目标规划问题，用线性规划方法很难找到最优解。,对于多目标问题，线性规划很难为其找到最优方案极有可能出现：第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法目标规划,目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。,2、线性规划求最优解；目标规划是找到一个满意解。,1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。,二 目标规划概述,（一）目标规划与线性规划的比较,3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权是软约束。,4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。,因此，目前，目标规划已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。,(二)、目标规划的基本概念,多目标规划问题的一般形式如下(简记为：GP1),矩阵表示为：,其他情况：如目标函数为 min y,约束条件为“”，都可作适当的变换，调整为上面的形式.,对于多目标问题中大多的情况是：由于多目标之间存在相互矛盾，最优解往往不可能存在，这就要求我们退而求其次，根据目标之间的相对重要程度，分等级和权重，求出相对最优解有效解（满意解），为此引入以下概念，对目标函数和约束条件作适当处理,目标值和偏差变量目标约束和绝对约束达成函数（即目标规划中的目标函数）优先因子（优先等级）与优先权系数满意解（具有层次意义的解）,目标规划的基本概念：,目标规划通过引入目标值和偏差变量，将原目标函数和原约束条件转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实际值或决策值：是指当决策变量xj 选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实际值和目标值之间的差异,记为 d（d0)。正偏差变量：表示实际值超过目标值的部分，记为 d。负偏差变量：表示实际值未达到目标值的部分，记为 d。,1、目标值和偏差变量,当完成或超额完成规定的指标则表示：d0,d0当未完成规定的指标则表示：d0,d0当恰好完成指标时则表示：d0,d0,在一次决策中，实际值不可能既超过目标值又未达到目标值，故有 d d 0,并规定d0,d0,d d 0 成立。,实际操作中，当目标值确定时，所做的决策只可能出现以下三种情况（即由d+和d-所构成的3种不同组合表示的含义）：,（1）目标约束是目标规划中所特有的，可把约束条件的右端项看作要追求的目标值；也可以对目标函数规定一个目标值。在达到此目标值时允许发生正或负偏差，因此可在这些约束或目标函数中加入正、负偏差变量；引入目标值和正、负偏差变量后，把原目标函数和原约束条件转化成约束方程，都并入到约束条件中，我们称这类具有机动余地的约束为目标约束。也称为软约束。,2、目标约束和绝对约束,（2）绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。,例如：在下例中，规定Z1 的目标值为 50000,正、负偏差为d、d,则目标函数可以转换为目标约 束，即70 x1+120 x2 50000，同样，若规定产品甲期望值是 200件，产品乙期望值是 250件,则有：,若规定3600的钢材必须用完，原式9 x1+4 x2 3600则变为,将原目标函数转化为目标约束：（需引入目标值和正、负偏差变量）,maxZ1=70 x1+120 x2 maxZ2=x1 maxZ3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,将原约束条件转化为目标约束。,maxZ1=70 x1+120 x2 maxZ2=x1 maxZ3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同。优先因子Pk 是将决策目标按其重要程度排序并表示出来。,3、优先因子（优先等级）与优先权系数,要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，并规定PkPk+1，表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。即不管Pk+1乘以一个多大的正数M，总成立PkMPk+1,表示Pk比Pk+1具有绝对的优先权因此，不同的优先因子代表着不同的优先等级,若要进一步区别具有相同优先级的多个目标，则可分别赋予它们不同的权系数j(j 可取一确定的非负实数)，根据目标的重要程度而给它们赋值，重要的目标，赋值较大，反之j 值就小,目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是一个使总偏差量为最小的目标函数，记为 minZ=f（d、d）。,4、达成函数（即目标规划中的目标函数）,通过引入目标值和偏差变量，使原规划问题中的目标函数变成了目标约束，那么现在问题的目标是什么呢？,这样根据各个目标的不同要求，可确定出总的目标函数,一般说来，对于达成函数有以下三种情况，但只能出现其中之一：.要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f（d d）。.要求不超过目标值，即允许达不到目标值，也就是 正偏差变量尽可能小，则minZ=f（d）。.要求超过目标值，即超过量不限，但不低于目标 值，也就是负偏差变量尽可能小，则minZ=f（d）。,对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。,5、满意解（具有层次意义的解）,某厂生产、两种产品，有关数据如表所示。,例1：,（三）目标规划的数学模型,解：这是求获利最大的单目标的规划问题，用x1，x2分别表示，产品的产量，其线性规划模型表述为：,用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62(元)。,(4,3),1、产品的产量不大于的产量；2、超过计划供应的原材料时，需要高价采购，会 使成本大幅度增加。(硬约束）3、充分利用设备有效台时，不加班；4、利润不小于 56 元。,解：设x1，x2分别表示产品和产品的产量。,这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解这类决策问题的方法之一。下面通过前面引入的概念建立目标规划数学模型。,现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序如下：,引进正、负偏差变量d+，d-。正偏差变量d表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分。,（1）.建立目标约束和系统约束：,产品的产量不大于的产量:,充分利用设备有效台时，但不希望加班:,利润不小于 56 元:,原材料约束:,d1-:X1产量不足X2 部分d1+:X1产量超过X2 部分d2-:设备使用不足10 部分d2+:设备使用超过10 部分d3-:利润不足56 部分d3+:利润超过56 部分,第一目标：即产品的产量不大于的产量。,第二目标：,即充分利用设备有效台时，不加班,第三目标：,即利润不小于 56 元,（2）确定优先等级:,（3）达成函数：,目标函数 先满足 minZ1=d1+再满足 minZ2=d2-+d2+后满足 minZ3=d3-,或 minZ=P1d1+P2(d2-+d2+)+P3(d3-)minP1d1+,P2(d2-+d2+),P3(d3-),一般记作：,目标规划模型：,例：常山机器厂生产、两种产品.这两种产品都要分别在A、B、C三种不同设备上加工.按工艺资料规定，生产每件产品需占用各设备分别为2h、4h、0h，生产每件产品，需占用各设备分别为2h、0h、5h.已知各设备计划期内用于生产这两种产品的能力分别为12h、16h、15h，又知每生产一件产品企业能获得2元利润，每生产一件产品企业能获得3元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大.,最优解为x1=3，x2=3，z*=15元.,解：设x1和x2分别为、两种产品在计划期内 的产量.,(1)力求使利润指标不低于15元；(2)考虑到市场需求，、两种产品的生产量需 保持1：2的比例；(3)A为贵重设备，严格禁止超时使用；（硬约束）(4)设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，又在重要性上设备B是C的3倍.,但企业的经营不仅仅是利润，而是考虑如下 多方面：,1.设置偏差变量，用来表明实际值同目标值之间 的差异.d+超出目标的差值，称正偏差变量d 未达到目标的差值，称负偏差变量d+和d 两者中必有一个为零.,2.统一处理目标函数和约束条件,设备A严格禁止超时使用（硬约束）2x1+2x212 要求、两种产品保持1：2的比例x1/x2=1/2或2x1-x2=0,(1)力求使利润指标不低于15元；(2)考虑到市场需求，、两种产品的生产量需 保持1：2的比例；(3)A为贵重设备，严格禁止超时使用；（硬约束）(4)设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，又在重要性上设备B是C的3倍.,力求使利润指标不低于15元,设备C可以适当加班，但要控制,设备B既要求充分利用，又尽可能不加班,(1)力求使利润指标不低于15元；(2)考虑到市场需求，、两种产品的生产量需 保持1：2的比例；(3)A为贵重设备，严格禁止超时使用；（硬约束）(4)设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，又在重要性上设备B是C的3倍.,3.目标的优先级与权系数,优先因子用P1，P2，表示，并规定Pk Pk+1权系数该厂必须满足设备A的硬性约束（不在目标约束中）第一优先级：利润第二优先级：、产品的产量尽可能保持1：2 的比例第三优先级：设备C、B的工作时间所控制第三优先级：设备B的重要性比设备C大三倍目标函数中在设备B的偏差变量前冠以权系数3,(1)力求使利润指标不低于15元；(2)考虑到市场需求，、两种产品的生产量需保持 1：2的比例；(3)A为贵重设备，严格禁止超时使用；(4)设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，又在重要性上设备B是C的3倍.,目标规划的一般数学模型,Pk为第k级优先因子，k=1,K;-kl，+kl为分别赋予第l个目标约束的正负偏差变量的权系数gl为第l个目标的预期目标值，l=1,L.,引例2:某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产 计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产，在此基础上使产量达到最大，试建立此问题的数学模型。,maxZ1=70 x1+120 x2 maxZ2=x1 maxZ3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,若在引例中提出下列要求：1、完成或超额完成利润指标 50000元；2、产品甲不超过 200件，产品乙不低于 250件；3、现有钢材 3600吨必须用完。试建立目标规划模型。,系统约束与目标约束,maxZ1=70 x1+120 x2 maxZ2=x1 maxZ3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,解：设x1，x2分别表示产品甲和产品乙的产量。di+,di-分别为第i个目标的正、负偏差变量,优先等级：题目有三个目标层次，包含四个目标值。第一目标：第二目标：有两个要求即甲，乙，但两个具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即 70:120，化简为7:12。,第三目标：,达成函数：,若在引例中提出下列要求：1、完成或超额完成利润指标 50000元；2、产品甲不超过 200件，产品乙不低于 250件；3、现有钢材 3600吨必须用完。试建立目标规划模型。,目标规划模型为：,maxZ1=70 x1+120 x2 maxZ2=x1 maxZ3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,(一)目标规划模型一般形式：,三.目标规划的数学模型：,(二)建模的步骤：,1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；,4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。,3、给各目标赋予相应的优先因子 Pk（k=1.2K）。,2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量 和减去正偏差变量即可。,5、根据决策者的要求，按下列情况之一 构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。,.恰好达到目标值，取。,.允许超过目标值，取。,.不允许超过目标值，取。,(三).小结,测验题：,某彩电组装厂，生产A、B、C三种规格电视机，装配工作在同一生产线上完成。三种产品装配时的工时消耗分别为 6小时、8小时和10小时。生产线每月正常工作时间为200小时，三种产品销售后，每台可获利分别为 500元，650元和800元，每月销售量预计为12台、10台、6台。该厂经营目标如下：P1：每月利润指标尽可能达到并超过16000元；P2：充分利用生产能力；P3：加班时间不超过24小时；P4；产量以预计销量为标准；为确定生产计划，请建立该问题的GP模型。,P1：每月利润指标尽可能达到并超过16000元；P2：充分利用生产能力；P3：加班时间不超过24小时；P4；产量以预计销量为标准；,总有效工时：120小时,设x1,x2分别为计划生产产品1和产品2的数量。,(2)P1：利润不低于400元,例4-5（例4-4)解：引进级别系数P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）,数学模型：目标函数：Min S=P1d1-+P2(5d2+d3+)约束方程：6X1+4X2+d1-d1+=280 2X1+3X2+d2-d2+=100 4X1+2X2+d3-d3+=120 X1,X2,di-,di+0(i=1,2,3),例4-6（例4-2)某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划：,（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。,解：设A，B生产线每周工作时间为X1，X2。A，B的产量比例2：1.5=4:3目标函数：Min S=P1d1-+P2d2+4 P3d3-+3 P3d4-约束方程：2X1+1.5X2+d1-d1+=210（生产量达到210件/周）X1+d2-d2+=60（A生产线加班时间限制在15小时内）,X1+d3-d3+=45（充分利用A的工时指标）X2+d4-d4+=45（充分利用B的工时指标）X1,X2,di-,di+0(i=1,2,3,4),A，B的产量比例2：1.5=4:3目标函数：Min S=P1d1-+P2d2+4 P3d3-+3 P3d4-约束方程：2X1+1.5X2+d1-d1+=210 X1+d2-d2+=60 X1+d3-d3+=45 X2+d4-d4+=45 X1,X2,di-,di+0(i=1,2,3,4),例4-7(例4-3)：(1)库存费用不超过4600元；(2)每月销售唱机不少于80台；(3)不使A、B车间停工（权数由生产费用确定）；(4)A车间加班时间限制在20小时内；,（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1,目标函数：Min S=P1d1+P2d2-+2 P3d4-+P3d5-+P4d41+P5d3-+P5d3+2P6d4+P6d5+约束方程：50X1+30X2+d1-d1+=4600（库存费用不超过4600元）X1+d2-d2+=80（每月销售唱机不少于80台）,X2+d3-d3+=100（每月销售录音机为100台）2X1+X2+d4-d4+=180（不使A车间停工）X1+3X2+d5-d5+=200（不使B车间停工）d4+d41-d41+=20（A车间加班时间限制在20小时内）X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5),目标函数：Min S=P1d1+P2d2-+2 P3d4-+P3d5-+P4d41+P5d3-+P5d3+2P6d4+P6d5+约束方程：50X1+30X2+d1-d1+=4600 X1+d2-d2+=80 X2+d3-d3+=100 2X1+X2+d4-d4+=180 X1+3X2+d5-d5+=200 d4+d41-d41+=20 X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5),