第5章目标规划11-4-26

1、 第五章第五章 目标规划目标规划 北京物资学院运筹学教学课件北京物资学院运筹学教学课件信息学院数学教研室信息学院数学教研室20201111年年4 4月月Goal Programming本章主要内容：本章主要内容：一、问题提出与目标规划的数学模型一、问题提出与目标规划的数学模型二、目标规划的解法二、目标规划的解法一、问题提出与目标规划的数学模型一、问题提出与目标规划的数学模型线性规划线性规划：在一组线性约束下一个线性函数的极值问题。：在一组线性约束下一个线性函数的极值问题。 线性规划的局限性线性规划的局限性 只能解决一组线性约束条件下，某一目标而且只能是只能解决一组线性约束条件下，某一目标而且只

2、能是一个目标的最大或最小值的问题。一个目标的最大或最小值的问题。实际决策中，衡量方案优劣常常需要考虑多个目标实际决策中，衡量方案优劣常常需要考虑多个目标, ,比如比如1 1）. .生产计划决策中，通常要考虑产值、利润、满足市场生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等；需求、降低消耗、提高质量、提高劳动生产率等；2 2）. .生产布局决策中，除了要考虑运输费用、投资、原料生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。社会因素等。 这些目标

3、中，有主要的，也有次要的；有最大的，也有这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，相对立的，LP则无能为力。则无能为力。目标规划（目标规划（Goal ProgrammingGoal Programming） 在在线性规划线性规划的基础上发展起来的解决的基础上发展起来的解决多目标规划问题多目标规划问题的最有效的方法之一。的最有效的方法之一。 美国经济学家查恩斯美国经济学家查恩斯( (A.CharnesA.Charnes) )和库柏和库柏( (W.W.Cooper)W.W.Coope

4、r)在在19611961年出版的管理模型及线性规划的工业应用一年出版的管理模型及线性规划的工业应用一书中，首先提出的。书中，首先提出的。 1976 1976年伊格尼齐奥发表了目标规划及其扩展一书，年伊格尼齐奥发表了目标规划及其扩展一书，系统归纳总结了目标规划的理论和方法。系统归纳总结了目标规划的理论和方法。例例1.1.某企业计划生产甲、乙两种产品，这些产品分别要在某企业计划生产甲、乙两种产品，这些产品分别要在A、B、C、D四四种不同的设备上加工。各产品占用资源数量，种不同的设备上加工。各产品占用资源数量，资源拥有量及产品利润见下表。问如何安排生产，才能获资源拥有量及产品利润见下表。问如何安排生

5、产，才能获得最大的总利润？得最大的总利润？32利润（百元利润（百元/ /件）件）1240D1604C821B1222A设备工作设备工作台时台时乙乙甲甲 消耗消耗 产品产品设备设备解：设解：设 x1， x2 分别表示甲乙产品的产量，则相应的线性分别表示甲乙产品的产量，则相应的线性规划模型为：规划模型为：它的最优解为它的最优解为: x1 =4, x2 =2, z =141212121212max23221228. .416412,0zxxxxxxs txxxx 假设企业的经营目标不仅仅是利润，而是要考虑多个方面的目标假设企业的经营目标不仅仅是利润，而是要考虑多个方面的目标:（1 1）企业利润不低于

6、）企业利润不低于1212（百元）。（百元）。（2 2）力争使甲乙两种产品的比例大致为）力争使甲乙两种产品的比例大致为1 1：1 1。（3 3）设备）设备B B必要时可以加班，但不希望加班；设备必要时可以加班，但不希望加班；设备A A既要充分利用，既要充分利用，又尽可能不加班。又尽可能不加班。是否可以用线性规划解决上述多目标的问题？是否可以用线性规划解决上述多目标的问题？为了解决上述多目标的规划问题，就需要使用目标规划的方法为了解决上述多目标的规划问题，就需要使用目标规划的方法。线性规划模型存在以下几方面的局限性线性规划模型存在以下几方面的局限性:1.LP1.LP只能处理单目标优化问题。因此，线

7、性规划模型中人为地将一只能处理单目标优化问题。因此，线性规划模型中人为地将一些次要目标转化为约束。（在实际中，目标和约束可以相互转化）些次要目标转化为约束。（在实际中，目标和约束可以相互转化）2.2.LPLP要求问题的解必须满足全部约束条件，但实际中并非所有约束要求问题的解必须满足全部约束条件，但实际中并非所有约束都必须严格满足。都必须严格满足。3.3.LPLP中各个约束（实际上也可以看作目标）都处于同等重要地位，中各个约束（实际上也可以看作目标）都处于同等重要地位，但实际问题中各个目标既有层次上的差别，又有权重上的区分。但实际问题中各个目标既有层次上的差别，又有权重上的区分。4.4.LPLP

8、寻求最优解，但很多问题只要找到满意解即可。寻求最优解，但很多问题只要找到满意解即可。目标规划解决上述目标规划解决上述LPLP建模中的局限性的方法：建模中的局限性的方法：1.1. 对每个目标函数确定一个希望达到的对每个目标函数确定一个希望达到的期望值期望值( (目标值目标值或理想值或理想值) )；由于各种条件的限制，这些目标值往往；由于各种条件的限制，这些目标值往往不可能全部都达到；不可能全部都达到；2.2. 对每一个目标函数引入正的或负的对每一个目标函数引入正的或负的偏差变量偏差变量，分别表，分别表示超过或未达到目标值的情况；示超过或未达到目标值的情况；3.3. 对所有的目标函数建立对所有的目

9、标函数建立约束方程约束方程，并入原来的约束条，并入原来的约束条件中，组成新的约束条件；件中，组成新的约束条件；4.4. 引入目标的引入目标的优先等级和加权系数优先等级和加权系数；建立使组合偏差最；建立使组合偏差最小的目标函数。小的目标函数。1.1.确定目标函数的期望值确定目标函数的期望值 每一个目标函数希望达到的期望值每一个目标函数希望达到的期望值( (或目标值、理想值或目标值、理想值) )。 根据历史资料、市场需求或上级部门的布置等来确定。根据历史资料、市场需求或上级部门的布置等来确定。2.2.设置偏差变量，用来表明实际值同目标值之间的差异。设置偏差变量，用来表明实际值同目标值之间的差异。超

10、出目标的差值，称正偏差变量；超出目标的差值，称正偏差变量；- -未达到目标的差值，称负偏差变量。未达到目标的差值，称负偏差变量。与与两者必有一个为零两者必有一个为零 （1）- -0，0 表示实际值超出规定目标值；表示实际值超出规定目标值； （2）- -0，0 表示实际值未达到目标值表示实际值未达到目标值； （3）- -=0，0 表示实际值同规定目标值恰好一致。表示实际值同规定目标值恰好一致。3.3.统一处理目标和约束统一处理目标和约束系统约束系统约束( (硬约束硬约束) )：对资源使用上有严格限制的约束，对资源使用上有严格限制的约束，用严格的等式或不等式表示（同线性规划中的约束）。用严格的等式

11、或不等式表示（同线性规划中的约束）。如：如：4x1 16 (设备设备C的使用时间的使用时间) 4x2 12 (设备设备D的使用时间的使用时间) 目标约束（软约束）目标约束（软约束）：引入正、负偏差变量后，对各引入正、负偏差变量后，对各个目标建立的目标约束方程。个目标建立的目标约束方程。1nkjjkkkjc xddE 原来的目标函数变成了约束条件的一部分，即目标约原来的目标函数变成了约束条件的一部分，即目标约束束( (软约束软约束) )l设备设备A A既要充分利用，又尽可能不加班既要充分利用，又尽可能不加班, ,可以写成可以写成 mind3- - +d3+ 2x1+2x2+ d3- - d3=1

12、2 (设备设备A)设备设备B B允许加班，只是不希望加班或少加班，可以写成允许加班，只是不希望加班或少加班，可以写成 mind4 x1+2x2+ d4- - - d4=8 (设备设备B)l原来的目标函数，在目标规划中只是成了问题要达到的原来的目标函数，在目标规划中只是成了问题要达到的目标之一目标之一 ,“ ,“目标利润不低于目标利润不低于1212（百元（百元 ）”, ”, 可以表示可以表示成成 mind1- 2x1 +3x2 + d1- - - d1=12l要求甲、乙两种产品的比例尽可能接近要求甲、乙两种产品的比例尽可能接近1111，可以表示成，可以表示成 mind2- - + d2 x1-x

13、2 +d2- - - d2 = 04.4.目标函数、目标的优先级和权系数目标函数、目标的优先级和权系数（1 1）在目标规划中，如果两个不同目标的重要程度相差悬殊，为达）在目标规划中，如果两个不同目标的重要程度相差悬殊，为达到某一目标可牺牲其他目标，称这些目标是属于不同层次的优先级。到某一目标可牺牲其他目标，称这些目标是属于不同层次的优先级。优先级层次的高低可通过优先因子优先级层次的高低可通过优先因子P P1 1，P P2 2表示。表示。并规定并规定P P k k P P k+1k+1 ，即不同优先级之间的差别无法用数字大小衡量。即不同优先级之间的差别无法用数字大小衡量。（2 2）对属于同一层次

14、优先级的不同目标，其重要程度的差别可以通）对属于同一层次优先级的不同目标，其重要程度的差别可以通过设置权系数来表达。权系数越大，表示目标越重要。过设置权系数来表达。权系数越大，表示目标越重要。目标规划中的目标函数是各个实际值与目标值之间的最小差距。目标规划中的目标函数是各个实际值与目标值之间的最小差距。本例中，假设：本例中，假设：P P1 1 ：企业利润目标；：企业利润目标；P P2 2 ：甲、乙产品的产量尽可能达到：甲、乙产品的产量尽可能达到1111的要求；的要求；P P3 3 ：设备：设备A A、B B尽量不超负荷工作，在第三优先级中，设备尽量不超负荷工作，在第三优先级中，设备A A的重的

15、重要性是设备要性是设备B B的三倍。的三倍。112223333412121112221233124412min()3()416(1)412(2)2312(3)0(4)2212(5)28(6),0,0 (1,2,3,4)iizPdP ddP ddP dxxxxddxxddxxddxxddxxddi 本例中，假设：本例中，假设：P P1 1 ：企业利润目标；：企业利润目标；P P2 2 ：甲、乙产品的产量尽可能达到：甲、乙产品的产量尽可能达到1111的要求；的要求；P P3 3 ：设备：设备A A、B B尽量不超负荷工作，在第三优先级中，设备尽量不超负荷工作，在第三优先级中，设备A A的重的重要性

16、是设备要性是设备B B的三倍。的三倍。l目标约束：目标约束：f(x) + d- - - d = f0 ;l1.要求性能指标要求性能指标f(x) 尽量达到目标值尽量达到目标值f0 （即不足（即不足f0不好，不好，超出超出f0也不好）也不好） min(d- -+ d) = f0l2.要求性能指标要求性能指标f(x)的值不少于目标值的值不少于目标值f0 (即允许超过即允许超过f0，但尽可能不要少于但尽可能不要少于f0） min（d- -） f0l3.要求性能指标要求性能指标 f(x) 的值不超过目标值的值不超过目标值 f0 (即允许少于即允许少于f0，但尽可能不要超过但尽可能不要超过f0） min（

17、d） f0小结小结课堂练习课堂练习1 1：某工厂计划生产某工厂计划生产A、B两种产品，每吨产品的耗电量指标、两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。原材料消耗、单位产品利润及资源限量如表所示。 厂长首先考虑要充分利用供电部门分配的电量限额厂长首先考虑要充分利用供电部门分配的电量限额66， 然后考虑利润不低于然后考虑利润不低于100元；元； 其次据市场调查结果，希望其次据市场调查结果，希望B产品的产量不低于产品的产量不低于A产品的产产品的产量，量， 问应如何安排产品问应如何安排产品A、B的产量。的产量。2010单位产品利润单位产品利润812原材料原材料6612

18、10电力电力资源限量资源限量BA 消耗消耗 产品产品资源资源解：解：设设x1 、x2分别表示分别表示A、B两种产品的产量，则目标规划两种产品的产量，则目标规划模型如下：模型如下：11122331212111222123312min()28101266. . 10201000,0(1,2,3)iizP ddP dP dxxxxdds txxddxxddxx ddi 课堂练习课堂练习2 2：某电视机厂装配黑白和彩色两种电视机，每装配一台电视机某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需要占用装配线需要占用装配线1 1小时，装配线每周计划开动小时，装配线每周计划开动4040小时。预计市小时

19、。预计市场每周彩色电视机的销量为场每周彩色电视机的销量为2424台，每台可获利台，每台可获利8080元；黑白电元；黑白电视机的销量是视机的销量是3030台，每台可获利台，每台可获利4040元。该厂确定的目标为：元。该厂确定的目标为：第一优先级第一优先级：充分利用装配线每周计划开动的：充分利用装配线每周计划开动的4040小时；小时； 第二优先级第二优先级：允许装配线加班，但加班的时间尽量不超过：允许装配线加班，但加班的时间尽量不超过1010小时；小时； 第三优先级第三优先级：装配电视机的数量尽量满足市场需要。因彩色：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权为电视机利润高，取其

20、权为2 2。试确定该厂为达到以上目标的最优生产计划。（建立数学模试确定该厂为达到以上目标的最优生产计划。（建立数学模型）型）解：设解：设 x1, x2 分别表示彩色和黑白电视机的产量。该问分别表示彩色和黑白电视机的产量。该问题的目标规划模型为：题的目标规划模型为：11223341211122213324412min(2)4050. .2430,0(1,2,3,4)iizPdP dPddxxddxxdds txddxddxx ddi 作业：作业：P145. 第第 5.8题题二、目标规划的解法二、目标规划的解法（一）目标规划的图解法（一）目标规划的图解法（二）目标规划的单纯形解法（二）目标规划的单

21、纯形解法( (一一) )、目标规划的图解法、目标规划的图解法 只含有两个决策变量只含有两个决策变量( (不考虑偏差变量) )的目标规划模型的目标规划模型 线性规划是在可行域中寻找一点，使单个目标极大或极小；线性规划是在可行域中寻找一点，使单个目标极大或极小； 目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的 折衷方案。折衷方案。 目标规划的图解法的思路目标规划的图解法的思路 首先是在可行域内寻找一个使首先是在可行域内寻找一个使P1级各目标均满足的区域级各目标均满足的区域R1； 然后再在然后再在R1中寻找一个使中寻找一个使P2级

22、各目标均满足的区域级各目标均满足的区域R2(R2 R1)； 接着再在接着再在R2中寻找一个满足中寻找一个满足P3级各目标的区域级各目标的区域R3(R3 R2 R1)； 如此继续，直到寻找到一个区域如此继续，直到寻找到一个区域RK(RK RK-1 R3 R2 R1)，满足满足PK级各目标，这时级各目标，这时RK即为这个目标规划的最优解空间，其即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。中的任一点均为这个目标规划的满意解。目标规划的图解法的步骤目标规划的图解法的步骤 第一步：按照系统约束画出可行域，第一步：按照系统约束画出可行域， 第二步：不考虑正负偏差变量，画出目标约束的

23、边界线，第二步：不考虑正负偏差变量，画出目标约束的边界线， 第三步：按优先级别和权重依次分析各级目标。第三步：按优先级别和权重依次分析各级目标。112223333412121112221233124412min()3()416(1)412(2)2312(3)0(4)2212(5)28(6),0,0 (1,2,3,4)iizPdP ddP ddP dxxxxddxxddxxddxxddxxddi 1d4d选择选择F点作为满意解点作为满意解即即x1=3,x2=3,企业的利润是企业的利润是15百元。百元。FGHx1x2(1)(2)(3)(4)(5)(6)例例2 2 用图解法求解目标规划用图解法求解目

24、标规划课堂练习：课堂练习： 用图解法求解目标规划用图解法求解目标规划11223341211122213324412min(2)40(1)50(2)24(3)30(4),0,0 (1,2,3,4)iizPdP dPddxxddxxddxddxddxxddi 1d2dx1x2(1)(2)(3)(4)3d4d由于由于E点使得点使得d4- -取值最小，取值最小，故故E点为满意解点为满意解 (24,26)E( (二二) )、求解目标规划的单纯形法求解目标规划的单纯形法 目标规划与线性规划的数学模型的结构相似目标规划与线性规划的数学模型的结构相似 可用前述单纯形算法求解目标规划模型：可用前述单纯形算法求解

25、目标规划模型： 由于检验数一般是各优先等级因子的代数和，为方便可以将检验由于检验数一般是各优先等级因子的代数和，为方便可以将检验数行根据优先因子分成数行根据优先因子分成K K行，判断检验数的正负和大小主要根据优行，判断检验数的正负和大小主要根据优先因子的系数正负和大小。先因子的系数正负和大小。 由于目标规划是极小化问题，最优性标准是：检验数非负。由于目标规划是极小化问题，最优性标准是：检验数非负。 将优先等级将优先等级P Pk k视为正常数视为正常数( (类似于类似于大大 法法)()(P P1 1PP2 2PP3 3.P.PK K);); 正负偏差变量正负偏差变量d dk k+ +, , d

26、dk k- - 视为松弛变量视为松弛变量; ; 以负偏差变量以负偏差变量 d dk k- - 为初始基变量，建立初始单纯形表为初始基变量，建立初始单纯形表 检验数的计算与检验数的计算与LPLP单纯形表检验数的计算完全相同单纯形表检验数的计算完全相同 最优性判别准则类似于最优性判别准则类似于LPLP的单纯形算法：的单纯形算法：例例3 3：用单纯形法求解下列目标规划问题：用单纯形法求解下列目标规划问题1112231111222123312min1024032100,0(1,2,3)iizPdPdP dxddxxddxxddxx ddi 以负偏差变量作为第一组基变量，填入单纯形表以负偏差变量作为第一

27、组基变量，填入单纯形表00P100P1P20CBBbx1x2d d1 1- -d d1 1+ +d d2 2- -d d2 2+ +d d3 3- -d d3 3+ +P1d d1 1- -10101-100000d d2 2- -4021001-100P2d d3 3- -1003200001-1 1020100/3 jP P1 1-10010100P P2 2-3-20000010 x110101-100000d d2 2- -2001-221-100P2d d3 3- -7002-33001-1 jP P1 100100100P P2 20-23-300011070/30d d1 1+

28、+1001/2-111/2-1/2000 x12011/2001/2-1/200P2d d3 3- -4001/200-3/23/21-1 jP P1 100100100P P2 20-1/2003/2-3/2014020800d d1 1+ +1001/2-111/2-1/2000 x12011/2001/2-1/200P2d d3 3- -4001/200-3/23/21-1 jP P1 100100100P P2 20-1/2003/2-3/20100P100P1P20CBBbx1x2d d1 1- -d d1 1+ +d d2 2- -d d2 2+ +d d3 3- -d d3 3+

29、 +0 x x2 22001-221-1000 x110101-10000P2d d3 3- -30001-1-221-1 jP P1 100100100P P2 200-112-201虽然虽然P P2 2行有负检验数，但由于其对应的行有负检验数，但由于其对应的P P1 1行的检验数均为正，行的检验数均为正，所以计算停止，得到目标规划的满意解：所以计算停止，得到目标规划的满意解：x1=10,x2=20。注意：注意：对目标的优化是按优先级顺序逐级进行的，当对目标的优化是按优先级顺序逐级进行的，当P P1 1行的所行的所有检验数均为非负时，说明第一优先级的目标已得到优有检验数均为非负时，说明第一优

30、先级的目标已得到优化，可转入下一级，再考察化，可转入下一级，再考察P2行的检验数是否存在负值，行的检验数是否存在负值，依次类推。依次类推。考察考察P2行的检验数时行的检验数时, ,注意应包括更高级别的优先因子注意应包括更高级别的优先因子在内在内, ,例如例如, ,上面的最后一张单纯形表中最下面的上面的最后一张单纯形表中最下面的P2行有行有两个负值，其对应的变量两个负值，其对应的变量d1 1- -的检验数为的检验数为P1-P20,0,变量变量d d2 2+ +的检验数为的检验数为P1-2P200。因此判断迭代计算应否停止的准因此判断迭代计算应否停止的准则为：则为：1)1)检验数检验数P1,P2,PK行的所有值均非负；行的所有值均非负；2)2)若若P1,P2,Pi行的所有值均非负，第行的所有值均非负，第Pi+1行存在负检验行存在负检验数，但在负检验数所在列的上面行中有正的