第五章运筹学目标规划

第五章目标规划(GoalProgramming)本章基本要求：1.理解目标规划概念2.掌握目标规划建模技巧3.能够运用图解法求解模型一、问题提出与目标规划的数学模型线性规划：在一组线性约束下一个线性函数的极值问题。线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。实际决策中，衡量方案优劣常常需要考虑多个目标,比如1）.生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等；2）.生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。目标规划（GoalProgramming）在线性规划的基础上发展起来的解决多目标规划问题的最有效的方法之一。美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版的《管理模型及线性规划的工业应用》一书中，首先提出的。1976年伊格尼齐奥发表了《目标规划及其扩展》一书，系统归纳总结了目标规划的理论和方法。例1.某企业计划生产甲、乙两种产品，这些产品分别要在A、B、C、D四种不同的设备上加工。各产品占用资源数量，资源拥有量及产品利润见下表。问如何安排生产，才能获得最大的总利润？32利润（百元/件）1240D1604C821B1222A设备工作台时乙甲消耗产品设备解：设x1，x2分别表示甲乙产品的产量，则相应的线性规划模型为：它的最优解为:x1=4,x2=2,z=141212121212max23221228..416412,0zxxxxxxstxxxx假设企业的经营目标不仅仅是利润，而是要考虑多个方面的目标:（1）企业利润不低于12（百元）。（2）力争使甲乙两种产品的比例大致为1：1。（3）设备B必要时可以加班，但不希望加班；设备A既要充分利用，又尽可能不加班。是否可以用线性规划解决上述多目标的问题？为了解决上述多目标的规划问题，就需要使用目标规划的方法。线性规划模型存在以下几方面的局限性:1.LP只能处理单目标优化问题。因此，线性规划模型中人为地将一些次要目标转化为约束。（在实际中，目标和约束可以相互转化）2.LP要求问题的解必须满足全部约束条件，但实际中并非所有约束都必须严格满足。3.LP中各个约束（实际上也可以看作目标）都处于同等重要地位，但实际问题中各个目标既有层次上的差别，又有权重上的区分。4.LP寻求最优解，但很多问题只要找到满意解即可。目标规划解决上述LP建模中的局限性的方法：1.对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到；2.对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况；3.对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件；4.引入目标的优先等级和加权系数；建立使组合偏差最小的目标函数。1.确定目标函数的期望值每一个目标函数希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。2.设置偏差变量，用来表明实际值同目标值之间的差异。ｄ＋——超出目标的差值，称正偏差变量；ｄ-——未达到目标的差值，称负偏差变量。ｄ＋与ｄ－两者必有一个为零（1）ｄ-＝0，ｄ＋0表示实际值超出规定目标值；（2）ｄ-0，ｄ＋＝0表示实际值未达到目标值；（3）ｄ-=0，ｄ＋＝0表示实际值同规定目标值恰好一致。3.统一处理目标和约束系统约束(硬约束)：对资源使用上有严格限制的约束，用严格的等式或不等式表示（同线性规划中的约束）。如：4x116(设备C的使用时间)4x212(设备D的使用时间)目标约束（软约束）：引入正、负偏差变量后，对各个目标建立的目标约束方程。1nkjjkkkjcxddE原来的目标函数变成了约束条件的一部分，即目标约束(软约束)设备A既要充分利用，又尽可能不加班,可以写成min{d3-+d3+}2x1+2x2+d3--d3＋=12(设备A)•设备B允许加班，只是不希望加班或少加班，可以写成min{d4＋}x1+2x2+d4--d4＋=8(设备B)原来的目标函数，在目标规划中只是成了问题要达到的目标之一,“目标利润不低于12（百元）”,可以表示成min{d1-}2x1+3x2+d1--d1＋=12要求甲、乙两种产品的比例尽可能接近1∶1，可以表示成min{d2-+d2＋}x1-x2+d2--d2＋=04.目标函数、目标的优先级和权系数（1）在目标规划中，如果两个不同目标的重要程度相差悬殊，为达到某一目标可牺牲其他目标，称这些目标是属于不同层次的优先级。优先级层次的高低可通过优先因子P1，P2……表示。并规定Pk»Pk+1，即不同优先级之间的差别无法用数字大小衡量。（2）对属于同一层次优先级的不同目标，其重要程度的差别可以通过设置权系数来表达。权系数越大，表示目标越重要。目标规划中的目标函数是各个实际值与目标值之间的最小差距。本例中，假设：P1：企业利润目标；P2：甲、乙产品的产量尽可能达到1∶1的要求；P3：设备A、B尽量不超负荷工作，在第三优先级中，设备A的重要性是设备B的三倍。112223333412121112221233124412min()3()416(1)412(2)2312(3)0(4)2212(5)28(6),0,,0(1,2,3,4)iizPdPddPddPdxxxxddxxddxxddxxddxxddi本例中，假设：P1：企业利润目标；P2：甲、乙产品的产量尽可能达到1∶1的要求；P3：设备A、B尽量不超负荷工作，在第三优先级中，设备A的重要性是设备B的三倍。目标约束：f(x)+d--d＋=f0;1.要求性能指标f(x)尽量达到目标值f0（即不足f0不好，超出f0也不好）min(d-+d＋)……=f02.要求性能指标f(x)的值不少于目标值f0(即允许超过f0，但尽可能不要少于f0）min（d-）……f03.要求性能指标f(x)的值不超过目标值f0(即允许少于f0，但尽可能不要超过f0）min（d＋）……f0小结二、建立目标规划模型的步骤•第一步：定义决策变量和有关的常量定义决策变量和决策目标约束等式右边的常数。等式右边的常数是可利用的资源或是决策者特定的目标值。•第二步：建立决策目标约束通过分析决策变量之间的关系以及决策变量与目标值之间的关系，建立一组目标约束。并从所有的决策目标中，找出绝对决策目标（即，如果不满足将导致最终结果无法实现的目标），将这些目标作为第一优先级。而后再确定其余目标的优先级。•第三步：建立指标偏差函数目标规划的一般模型为：),,2,1(0,),,2,1(0),,2,1(),(..)(~min1n111LlddnjxLleddxcbxatsdwdwPalljlllnjjljjjjijKkLllkllklk例2•某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见下表产品III资源限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68•设产品I和II的产量分别为X1和X2，当用线性规划来描述和解决这个问题时，其数学模型为：0,40446010586max21212121xxxxxxxxz其最优解，即最优生产计划为X1=8，X2=2，maxz=64•假设计划人员还被要求考虑如下意见：•（1）由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。•（2）原材料严重短缺，生产中应避免过量消耗。•（3）最好能节约4小时设备工时；•（4）计划利润不少于48元。•面对这些意见，计划人员作出如下意见，首先原材料使用额不得突破；产品II产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。例2的目标规划模型如下：minZ=P1d1-+P2d2++P3d3-5x1+10x2=60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48课堂练习1：某工厂计划生产A、B两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。厂长首先考虑要充分利用供电部门分配的电量限额66，然后考虑利润不低于100元；其次据市场调查结果，希望B产品的产量不低于A产品的产量，问应如何安排产品A、B的产量。2010单位产品利润812原材料661210电力资源限量BA消耗产品资源解：设x1、x2分别表示A、B两种产品的产量，则目标规划模型如下：11122331212111222123312min()28101266..10201000,,,0(1,2,3)iizPddPdPdxxxxddstxxddxxddxxddi课堂练习2：某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需要占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量为24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：第一优先级：充分利用装配线每周计划开动的40小时；第二优先级：允许装配线加班，但加班的时间尽量不超过10小时；第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权为2。试确定该厂为达到以上目标的最优生产计划。（建立数学模型）解：设x1,x2分别表示彩色和黑白电视机的产量。该问题的目标规划模型为：11223341211122213324412min(2)4050..2430,,,0(1,2,3,4)iizPdPdPddxxddxxddstxddxddxxddi二、目标规划的解法（一）目标规划的图解法（二）目标规划的单纯形解法第二节目标规划的图解法由于目标规划是在线性规划的基础上建立，并弥补了部分不足．所以两种规划模型结构没有本质区别，解法也非常类似．形式上的区别主要在于：①线性规划只能处理一个目标，而目标规划能统筹兼顾地处理多个目标关系，以求得切合实际需求的解；②线性规划是求满足所有约束条件的最优解，而目标规划是要在多个目标或约束条件下找到尽量好的满意解；③线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际需要给予轻重缓急的考虑．(一)、目标规划的图解法•只含有两个决策变量(不考虑偏差变量)的目标规划模型•线性规划是在可行域中寻找一点，使单个目标极大或极小；•目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。•目标规划的图解法的思路首先是在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3R2R1)；如此继续，直到寻找到一个区域RK(RKRK-1…R3R2R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。目标规划的图解法的步骤第一步：按照系统约束画出可行域，第二步：不考虑正负偏差变量，画出目标约束的边界线，第三步：按优先级别和权重依次分析各级目标。112223333412121112221233124412min()3()416(1)412(2)2312(3)0(4)2212(5)28(6),0,,0(1,2,3,4)iizPdPddPddPdxxxxddxxddx