北京理工大学：《运筹学》课程电子教案（PPT教学课件）第七章 目标规划

第嶂 制作:北京理工大学吴祈宗等

运筹学课件 第七章 目标规划 制作：北京理工大学 吴祈宗等

第七章 目标规划

第 七 章 目 标 规 划

第七章目标规划 在科学研究、经济建设和生产实践中,人们 经常遇到一类含有多个目标的数学规划问题,我 们称之为多目标规划。本章介绍一种特殊的多目 标规划叫目标规划( goal programming),这是美 国学者 Charnes等在1952年提出来的。目标规划 在实践中的应用十分广泛,它的重要特点是对各 个目标分级加权与逐级优化,这符合人们处理问 题要分别轻重缓急保证重点的思考方式。 本章分目标规划模型、目标规划的几何意义 与图解法和求解目标规划的单纯形方法等三个部 分进行介绍

第七章 目标规划 在科学研究、经济建设和生产实践中，人们 经常遇到一类含有多个目标的数学规划问题，我 们称之为多目标规划。本章介绍一种特殊的多目 标规划叫目标规划(goal programming)，这是美 国学者Charnes等在1952年提出来的。目标规划 在实践中的应用十分广泛，它的重要特点是对各 个目标分级加权与逐级优化，这符合人们处理问 题要分别轻重缓急保证重点的思考方式。 本章分目标规划模型、目标规划的几何意义 与图解法和求解目标规划的单纯形方法等三个部 分进行介绍

目标规划模型 1问题提出 为了便于理解目标规划数学模型的特征及 建模思路,我们首先举一个简单的例子来说明 例7.1某公司分厂用一条生产线生产两种 产品A和B,每周生产线运行时间为60小时, 生产一台A产品需要4小时,生产一台B产品需 要6小时.根据市场预测,A、B产品平均销售 量分别为每周9、8台,它们销售利润分别为12 18万元。在制定生产计划时,经理考虑下述4项 目标:

目标规划模型 1.问题提出 为了便于理解目标规划数学模型的特征及 建模思路, 我们首先举一个简单的例子来说明. 例7.1 某公司分厂用一条生产线生产两种 产品A和B ，每周生产线运行时间为60小时， 生产一台A产品需要4小时，生产一台B产品需 要6小时．根据市场预测，A、B产品平均销售 量分别为每周9、8台，它们销售利润分别为12、 18万元。在制定生产计划时，经理考虑下述4项 目标：

目标规划模型 1问题提出(续) 首先,产量不能超过市场预测的销售量; 其次,工人加班时间最少; 第三,希望总利润最大 最后,要尽可能满足市场需求,当不能满 足时,市场认为B产品的重要性是产品的2 倍 试建立这个问题的数学模型 讨论: 若把总利润最大看作目标,而把产量不能 超过市场预测

目标规划模型 1.问题提出 (续) 首先，产量不能超过市场预测的销售量； 其次，工人加班时间最少； 第三，希望总利润最大； 最后，要尽可能满足市场需求, 当不能满 足时, 市场认为B产品的重要性是A产品的2 倍． 试建立这个问题的数学模型． 讨论： 若把总利润最大看作目标，而把产量不能 超过市场预测

目标规划模型 1问题提出(续) 的销售量、工人加班时间最少和要尽可能满足 市场需求的目标看作约束,则可建立一个单目 标线性规划模型 设决策变量x,x2分别为产品A,B的产量 Max z=12x, +8x st.4xn+6x,≤s60 x,≤9 x2≤8 x,x,≥0

目标规划模型 1.问题提出 (续) 的销售量、工人加班时间最少和要尽可能满足 市场需求的目标看作约束，则可建立一个单目 标线性规划模型 设决策变量 x1，x2分别为产品A，B的产量  Max Z = 12x1+ 18x2  s.t. 4x1+ 6x2  60  x1  9  x2  8  x1 , x2  0

目标规划模型 1问题提出(续 容易求得上述线性规划的最优解为(9,4)T 到(3,8)所在线段上的点最优目标值为z 180,即可选方案有多种 在实际上,这个结果并非完全符合决策者 的要求,它只实现了经理的第 条目 标,而没有达到最后的一个目标。进一步分析 可知,要实现全体目标是不可能的

目标规划模型 1.问题提出 (续) 容易求得上述线性规划的最优解为(9,4)T 到 (3,8)T 所在线段上的点, 最优目标值为Z* = 180, 即可选方案有多种. 在实际上, 这个结果并非完全符合决策者 的要求, 它只实现了经理的第一、二、三条目 标，而没有达到最后的一个目标。进一步分析 可知，要实现全体目标是不可能的

目标规划模型 2.目标规划模型的基本概念 把例71的4个目标表示为不等式仍设决 策变量x,x2分别为产品4,B的产量那麽, 第一个目标为:x≤9,x2≤8; 第二个目标为:4x+6x2≤60; 第三个目标为:希望总利润最大,要表示成 不等式需要找到一个目标上界,这里可以估 计为252(=12×9+18×8),于是有 12x,+18x,≥252 第四个目标为:x1≥9,x2≥8;

目标规划模型 2. 目标规划模型的基本概念 把例7.1的4个目标表示为不等式.仍设决 策变量 x1，x2分别为产品A，B的产量. 那麽, 第一个目标为: x1  9 ，x2  8 ； 第二个目标为: 4x1+ 6x2  60 ； 第三个目标为: 希望总利润最大，要表示成 不等式需要找到一个目标上界，这里可以估 计为252（=129 + 188），于是有 12x1+ 18x2  252； 第四个目标为: x1  9，x2  8；

目标规划模型 2.目标规划模型的基本概念(续) 下面引入与建立目标规划数学模型有关的 概念 (1)正、负偏差变量d+,d 我们用正偏差变量d+表示决策值超过目 标值的部分;负偏差变量d-表示决策值不足目 标值的部分。因决策值不可能既超过目标值同 时又末达到目标值,故恒有d+×l=0 (2)绝对约束和目标约束 我们把所有等式、不等式约束分为两部分: 绝对约束和目标约束

目标规划模型 2. 目标规划模型的基本概念 （续） 下面引入与建立目标规划数学模型有关的 概念． （1）正、负偏差变量d + ，d - 我们用正偏差变量d + 表示决策值超过目 标值的部分；负偏差变量d - 表示决策值不足目 标值的部分。因决策值不可能既超过目标值同 时又末达到目标值，故恒有 d + d - ＝ 0 ． （2）绝对约束和目标约束 我们把所有等式、不等式约束分为两部分： 绝对约束和目标约束

目标规划模型 2.目标规划模型的基本概念(续) 绝对约束是指必须严格满足的等式约束和 不等式约束;如在线性规划问题中考虑的约 束条件,不能满足这些约束条件的解称为非 可行解,所以它们是硬约束。设例71.1中生 产A,B产品所需原材料数量有限制,并且无 法从其它渠道予以补充,则构成绝对约束。 目标约束是目标规划特有的,我们可以把 约束右端项看作要努力追求的目标值,但允 许发生正式负偏差,用在约束中加入正、负 偏差变量来表示,于是称它们是软约束

目标规划模型 2. 目标规划模型的基本概念 （续） 绝对约束是指必须严格满足的等式约束和 不等式约束；如在线性规划问题中考虑的约 束条件，不能满足这些约束条件的解称为非 可行解，所以它们是硬约束。设例7.1.1 中生 产A，B产品所需原材料数量有限制，并且无 法从其它渠道予以补充，则构成绝对约束。 目标约束是目标规划特有的，我们可以把 约束右端项看作要努力追求的目标值，但允 许发生正式负偏差，用在约束中加入正、负 偏差变量来表示，于是称它们是软约束