第五章目标规划08-11-16

第五章目标规划北京物资学院运筹学教学课件信息学院数学教研室2008年11月GoalProgramming本章主要内容：一、问题提出与目标规划的数学模型二、目标规划的解法一、问题提出与目标规划的数学模型线性规划：在一组线性约束下一个线性函数的极值问题。线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。实际决策中，衡量方案优劣常常需要考虑多个目标生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等；生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，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寻求最优解，但很多问题只要找到满意解即可。目标规划法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目标约束：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小结课堂练习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作业：P146.第5.6,5.7题二、目标规划的解法（一）目标规划的图解法（二）目标规划的单纯形解法(一)、目标规划的图解法•只含有两个决策变量的目标规划模型•线性规划是在可行域中寻找一点，使单个目标极大或极小；•目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。•目标规划的图解法的思路首先是在可行域内寻找一个使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)iizPdPddPddPdxxxxddxxddxxddxxddxxddi1d4d选择F点作为满意解即x1=3,x2=3,企业的利润是15百元。FGHx1x2(1)(2)(3)(4)(5)(6)例2用图解法求解目标规划课堂练习：用图解法求解目标规划11223341211122213324412min(2)40(1)50(2)24(3)30(4),0,,0(1,2,3,4)iizPdPdPddxxddxxddxddxddxxddi1d2dx1x2(1)(2)(3)(4)3d4d由于E点使得d4-取值最小，故E点为满意解(24,26)E(二)、求解目标规划的单纯形法目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：由于检验数一般是各优先等级因子的代数和，为方便可以将检验数行根据优先因子分成K行，判断检验数的正负和大小主要根据优先因子的系数正负和大小。由于目标规划是极小化问题，最优性标准是：检验数非负。•将优先等级Pk视为正常数(类似于大Ｍ法)(P1P2P3….PK);•正负偏差变量dk+,dk-视为松弛变量;•以负偏差变量dk-为初始基变量，建立初始单纯形表•检验数的计算与LP单纯形表检验数的计算完全相同•最优性判别准则类似于LP的单纯形算法：例3：用单纯形法求解下列目标规划问题1112231111222123312min1024032100,,0(1,2,3)iizPdPdPdxddxxddxxddxxddi以负偏差变量作为第一组基变量，填入单纯形表00P100P1P20CBBbx1x2d1-d1+d2-d2+d3-d3+P1d1-10101-100000d2-4021001-100P2d3-1003200001-11020100/3jP1-10010100P2-3-20000010x110101-100000d2-2001-221-100P2d3-7002-33001-1jP100100100P20-23-300011070/30d1+1001/2-111/2-1/2000x12011/2001/2-1/200P2d3-4001/200-3/23/21-1jP100100100P20-1/2003/2-3/2014020800d1+1001/2-111/2-1/2000x12011/2001/2-1/200P2d3-4001/200-3/23/21-1jP100100100P20-1/2