第五章 目标规划,北京物资学院运筹学教学课件,信息学院数学教研室 2011年4月,Goal Programming,本章主要内容： 一、问题提出与目标规划的数学模型 二、目标规划的解法,一、问题提出与目标规划的数学模型,线性规划：在一组线性约束下一个线性函数的极值问题。,线性规划的局限性 只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。,实际决策中，衡量方案优劣常常需要考虑多个目标,比如 1）.生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等； 2）.生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。 这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。,目标规划（Goal Programming） 在线性规划的基础上发展起来的解决多目标规划问题的最有效的方法之一。 美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版的管理模型及线性规划的工业应用一书中，首先提出的。 1976年伊格尼齐奥发表了目标规划及其扩展一书，系统归纳总结了目标规划的理论和方法。,例1.某企业计划生产甲、乙两种产品，这些产品分别要在A、B、C、D四种不同的设备上加工。各产品占用资源数量，资源拥有量及产品利润见下表。问如何安排生产，才能获得最大的总利润？,3,2,利润（百元/件）,12,4,0,D,16,0,4,C,8,2,1,B,12,2,2,A,设备工作台时,乙,甲,消耗 产品 设备,解：设 x1， x2 分别表示甲乙产品的产量，则相应的线性规划模型为：,它的最优解为: x1 =4, x2 =2, z =14,假设企业的经营目标不仅仅是利润，而是要考虑多个方面的目标:,（1）企业利润不低于12（百元）。 （2）力争使甲乙两种产品的比例大致为1：1。 （3）设备B必要时可以加班，但不希望加班；设备A既要充分利用，又尽可能不加班。,是否可以用线性规划解决上述多目标的问题？,为了解决上述多目标的规划问题，就需要使用目标规划的方法。,线性规划模型存在以下几方面的局限性:,1.LP只能处理单目标优化问题。因此，线性规划模型中人为地将一些次要目标转化为约束。（在实际中，目标和约束可以相互转化） 2.LP要求问题的解必须满足全部约束条件，但实际中并非所有约束都必须严格满足。 3.LP中各个约束（实际上也可以看作目标）都处于同等重要地位，但实际问题中各个目标既有层次上的差别，又有权重上的区分。 4.LP寻求最优解，但很多问题只要找到满意解即可。,目标规划解决上述LP建模中的局限性的方法： 对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到； 对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况； 对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件； 引入目标的优先等级和加权系数；建立使组合偏差最小的目标函数。,1.确定目标函数的期望值 每一个目标函数希望达到的期望值(或目标值、理想值)。 根据历史资料、市场需求或上级部门的布置等来确定。,2.设置偏差变量，用来表明实际值同目标值之间的差异。,超出目标的差值，称正偏差变量； -未达到目标的差值，称负偏差变量。 与两者必有一个为零 （1）-0，0 表示实际值超出规定目标值； （2）-0，0 表示实际值未达到目标值； （3）-=0，0 表示实际值同规定目标值恰好一致。,3.统一处理目标和约束,系统约束(硬约束)：对资源使用上有严格限制的约束，用严格的等式或不等式表示（同线性规划中的约束）。 如：4x1 16 (设备C的使用时间) 4x2 12 (设备D的使用时间),目标约束（软约束）：引入正、负偏差变量后，对各个目标建立的目标约束方程。,原来的目标函数变成了约束条件的一部分，即目标约束(软约束),设备A既要充分利用，又尽可能不加班,可以写成 mind3- +d3+ 2x1+2x2+ d3- d3=12 (设备A) 设备B允许加班，只是不希望加班或少加班，可以写成 mind4 x1+2x2+ d4- - d4=8 (设备B),原来的目标函数，在目标规划中只是成了问题要达到的目标之一 ,“目标利润不低于12（百元 ）”, 可以表示成 mind1- 2x1 +3x2 + d1- - d1=12,要求甲、乙两种产品的比例尽可能接近11，可以表示成 mind2- + d2 x1-x2 +d2- - d2 = 0,4.目标函数、目标的优先级和权系数,（1）在目标规划中，如果两个不同目标的重要程度相差悬殊，为达到某一目标可牺牲其他目标，称这些目标是属于不同层次的优先级。优先级层次的高低可通过优先因子P1，P2表示。 并规定P k P k+1 ，即不同优先级之间的差别无法用数字大小衡量。 （2）对属于同一层次优先级的不同目标，其重要程度的差别可以通过设置权系数来表达。权系数越大，表示目标越重要。,目标规划中的目标函数是各个实际值与目标值之间的最小差距。,本例中，假设： P1 ：企业利润目标； P2 ：甲、乙产品的产量尽可能达到11的要求； P3 ：设备A、B尽量不超负荷工作，在第三优先级中，设备A的重要性是设备B的三倍。,本例中，假设： P1 ：企业利润目标； P2 ：甲、乙产品的产量尽可能达到11的要求； 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,小结,课堂练习1： 某工厂计划生产A、B两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。 厂长首先考虑要充分利用供电部门分配的电量限额66， 然后考虑利润不低于100元； 其次据市场调查结果，希望B产品的产量不低于A产品的产量， 问应如何安排产品A、B的产量。,20,10,单位产品利润,8,1,2,原材料,66,12,10,电力,资源限量,B,A,消耗 产品 资源,解：设x1 、x2分别表示A、B两种产品的产量，则目标规划模型如下：,课堂练习2： 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需要占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量为24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为： 第一优先级：充分利用装配线每周计划开动的40小时； 第二优先级：允许装配线加班，但加班的时间尽量不超过10小时； 第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权为2。 试确定该厂为达到以上目标的最优生产计划。（建立数学模型）,解：设 x1, x2 分别表示彩色和黑白电视机的产量。该问题的目标规划模型为：,作业：,P145. 第 5.8题,二、目标规划的解法,（一）目标规划的图解法 （二）目标规划的单纯形解法,(一)、目标规划的图解法,只含有两个决策变量(不考虑偏差变量)的目标规划模型 线性规划是在可行域中寻找一点，使单个目标极大或极小； 目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的 折衷方案。 目标规划的图解法的思路,首先是在可行域内寻找一个使P1级各目标均满足的区域R1； 然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2 R1)； 接着再在R2中寻找一个满足P3级各目标的区域R3(R3 R2 R1)； 如此继续，直到寻找到一个区域RK(RK RK-1 R3 R2 R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。,目标规划的图解法的步骤 第一步：按照系统约束画出可行域， 第二步：不考虑正负偏差变量，画出目标约束的边界线， 第三步：按优先级别和权重依次分析各级目标。,选择F点作为满意解 即x1=3,x2=3,企业的利润是15百元。,F,G,H,x1,x2,(1),(2),(3),(4),(5),(6),例2 用图解法求解目标规划,课堂练习： 用图解法求解目标规划,x1,x2,(1),(2),(3),(4),由于E点使得d4-取值最小，故E点为满意解 (24,26),E,(二)、求解目标规划的单纯形法,目标规划与线性规划的数学模型的结构相似 可用前述单纯形算法求解目标规划模型：,由于检验数一般是各优先等级因子的代数和，为方便可以将检验数行根据优先因子分成K行，判断检验数的正负和大小主要根据优先因子的系数正负和大小。,由于目标规划是极小化问题，最优性标准是：检验数非负。,将优先等级Pk视为正常数(类似于大 法)(P1P2P3.PK); 正负偏差变量dk+, dk- 视为松弛变量; 以负偏差变量 dk- 为初始基变量，建立初始单纯形表 检验数的计算与LP单纯形表检验数的计算完全相同 最优性判别准则类似于LP的单纯形算法：,例3：用单纯形法求解下列目标规划问题,以负偏差变量作为第一组基变量，填入单纯形表,虽然P2行有负检验数，但由于其对应的P1行的检验数均为正，所以计算停止，得到目标规划的满意解：x1=10,x2=20。,注意： 对目标的优化是按优先级顺序逐级进行的，当P1行的所有检验数均为非负时，说明第一优先级的目标已得到优化，可转入下一级，再考察P2行的检验数是否存在负值，依次类推。 考察P2行的检验数时,注意应包括更高级别的优先因子在内,例如,上面的最后一张单纯形表中最下面的P2行有两个负值，其对应的变量d1-的检验数为P1-P20,变量d2+的检验数为P1-2P20。因此判断迭代计算应否停止的准则为：,检验数P1,P2,PK行的所有值均非负； 若P1,P2,Pi行的所有值均非负，第Pi+1行存在负检验数，但在负检验数所在列的上面行中有正的检验数。,作业： P145. 第 5.3(a)题(图解法) 第 5.3(c)题(单纯形法),课后习题讲解: P145 5.8 某牌号的酒系由三种酒兑制而成，已知各种等级的酒的每天供应量和单位成本如下：,该种牌号的酒有三种商标，各种商标酒的混合比及售价如下,P1：兑制要求配比必须严格满足； P2：企业获取尽可能多的利润；P3：红色商标酒每天的产量不低于2000单位。,解：设生产红色商标酒使用的三种原料的数量分别为x11,x12,x13; 生产黄色商标酒使用的三种原料的数量分别为x21,x22,x23; 生产蓝色商标酒使用的三种原料的数量分别为x31,x32,x33;,原料限制,配比要求,