运筹学-目标规划_第1页
运筹学-目标规划_第2页
运筹学-目标规划_第3页
运筹学-目标规划_第4页
运筹学-目标规划_第5页
已阅读5页,还剩116页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第5 章 目标规划 了解目标规划与线性规划的异同了解目标规划与线性规划的异同 理解目标约束中的正负偏差变量理解目标约束中的正负偏差变量 思考目标约束与系统约束的差异思考目标约束与系统约束的差异 理解目标的优先级和目标权系数理解目标的优先级和目标权系数 了解目标规划图解法和单纯形法了解目标规划图解法和单纯形法运筹学-目标规划目标规划本章内容重点本章内容重点目标规划模型目标规划模型目标规划的几何意义目标规划的几何意义目标规划的单纯形方法目标规划的单纯形方法运筹学-目标规划 问题的提出线性规划的局限性线性规划的局限性线性规划只研究在满足一定条件下,单一目标函数取线性规划只研究在满足一定条件下,单一目

2、标函数取得最优解,而在企业管理中,经常遇到多目标决策问得最优解,而在企业管理中,经常遇到多目标决策问题,如拟订生产计划时,不仅考虑总产值,同时要考题,如拟订生产计划时,不仅考虑总产值,同时要考虑利润,产品质量和设备利用率等。这些指标之间的虑利润,产品质量和设备利用率等。这些指标之间的重要程度重要程度(即优先顺序即优先顺序)也不相同,有些目标之间往往也不相同,有些目标之间往往相互发生矛盾。相互发生矛盾。线性规划致力于某个目标函数的最优解,这个最优解线性规划致力于某个目标函数的最优解,这个最优解若是超过了实际的需要,很可能是以过分地消耗了约若是超过了实际的需要,很可能是以过分地消耗了约束条件中的某

3、些资源作为代价。束条件中的某些资源作为代价。运筹学-目标规划线性规划把各个约束条件的重要性都不分主次地等同看待,线性规划把各个约束条件的重要性都不分主次地等同看待,这也不符合实际情况。这也不符合实际情况。求解线性规划问题,首先要求约束条件必须相容,如果约求解线性规划问题,首先要求约束条件必须相容,如果约束条件中,由于人力,设备等资源条件的限制,使约束条束条件中,由于人力,设备等资源条件的限制,使约束条件之间出现了矛盾,就得不到问题的可行解,但生产还得件之间出现了矛盾,就得不到问题的可行解,但生产还得继续进行,这将给人们进一步应用线性规划方法带来困难。继续进行,这将给人们进一步应用线性规划方法带

4、来困难。为了弥补线性规划问题的局限性,解决有限资源和计划指为了弥补线性规划问题的局限性,解决有限资源和计划指标之间的矛盾,在线性规划基础上,建立目标规划方法,标之间的矛盾,在线性规划基础上,建立目标规划方法,从而使一些线性规划无法解决的问题得到满意的解答。从而使一些线性规划无法解决的问题得到满意的解答。 问题的提出运筹学-目标规划第一节第一节 多目标规划问题多目标规划问题一、线性规划的局限性一、线性规划的局限性线性规划的局限性线性规划的局限性 只能解决一组线性约束条件下,某一目标而且只能是一个目标只能解决一组线性约束条件下,某一目标而且只能是一个目标的最大或最小值的问题的最大或最小值的问题实际

5、决策中,衡量方案优劣考虑多个目标实际决策中,衡量方案优劣考虑多个目标 生产计划决策,通常考虑产值、利润、满足市场需求等生产计划决策,通常考虑产值、利润、满足市场需求等 生产布局决策,考虑运费、投资、供应、市场、污染等生产布局决策,考虑运费、投资、供应、市场、污染等 这些目标中,有主要的,也有次要的;有最大的,有最小的;这些目标中,有主要的,也有次要的;有最大的,有最小的;有定量的,有定性的;有互相补充的,有互相对立的,有定量的,有定性的;有互相补充的,有互相对立的,LP则则无能为力无能为力目标规划(目标规划(Goal Programming) 多目标线性规划多目标线性规划 含有多个优化目标的线

6、性规划含有多个优化目标的线性规划运筹学-目标规划目标规划与线性规划的比较线性规划只讨论一个线性目标函数在一组线性约束条线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题;而目标规划是多个目标决策,可求件下的极值问题;而目标规划是多个目标决策,可求得更切合实际的解。得更切合实际的解。线性规划求最优解;目标规划是找到一个满意解。线性规划求最优解;目标规划是找到一个满意解。线性规划中的约束条件是同等重要的,是硬约束;而线性规划中的约束条件是同等重要的,是硬约束;而目标规划中有轻重缓急和主次之分,即有优先权。目标规划中有轻重缓急和主次之分,即有优先权。线性规划的最优解是绝对意义下的最优,但需

7、花去大线性规划的最优解是绝对意义下的最优,但需花去大量的人力、物力、财力才能得到;实际过程中,只要量的人力、物力、财力才能得到;实际过程中,只要求得满意解,就能满足需要求得满意解,就能满足需要(或更能满足需要或更能满足需要)。运筹学-目标规划目标规划与线性规划的比较例例5-1:某厂计划在下一个生产周期内生产甲、乙两种产:某厂计划在下一个生产周期内生产甲、乙两种产品,已知资料如表所示。试制定生产计划,使获得的利品,已知资料如表所示。试制定生产计划,使获得的利润最大?同时,根据市场预测,甲的销路不是太好,应润最大?同时,根据市场预测,甲的销路不是太好,应尽可能少生产;乙的销路较好,可以扩大生产。试

8、建立尽可能少生产;乙的销路较好,可以扩大生产。试建立此问题的数学模型。此问题的数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲单位单位 产品产品资源资源 消耗消耗运筹学-目标规划目标规划数学模型设:甲产品设:甲产品x1 ,乙产品,乙产品 x2 根据市场预测:根据市场预测:maxZ=70 x1 + 120 x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 , x2 0maxZ1=70 x1 + 120 x2 minZ2= x1 maxZ3= x2 9 x1

9、 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 , x2 0这些目标之间这些目标之间相互矛盾,一相互矛盾,一般的线性规划般的线性规划方法不能求解方法不能求解 运筹学-目标规划第一节第一节 多目标规划问题多目标规划问题二、多目标规划的提出二、多目标规划的提出111 11221221 122221 122ln11 11221121 1222221 122max(min) max(min) max(min) ( , )( , )s.t. nnnnlllnnnnnmmGc xc xc xGc xc xc xGc xc xc xa xa xa xba xa

10、 xa xba xax 12( , ),0mnnmnaxbx xx 多目标线性规划模型的原始一般形式如下:多目标线性规划模型的原始一般形式如下: n n个决策变量,个决策变量,m m个约束条件,个约束条件,L L个目标函数。个目标函数。当当L L=1=1时,即为我们熟悉的单目标线性规划模型。时,即为我们熟悉的单目标线性规划模型。运筹学-目标规划二、多目标规划的提出二、多目标规划的提出10运筹学-目标规划11运筹学-目标规划12运筹学-目标规划13运筹学-目标规划上述上述14运筹学-目标规划15运筹学-目标规划16运筹学-目标规划17运筹学-目标规划18运筹学-目标规划19运筹学-目标规划20运

11、筹学-目标规划21运筹学-目标规划第一节第一节 多目标规划问题多目标规划问题三、多目标的处理方法三、多目标的处理方法 加权系数法:加权系数法: 为每一目标赋一权数,把多目标转化成单目标。 但权系数难以科学确定。 优先等级法:优先等级法: 各目标按重要性归不同优先级而化为单目标。 有效解法:有效解法: 寻求能照顾到各目标而使决策者感到满意的解。 但可行域大时难以列出所有有效解的组合。 目标规划法:目标规划法: 对每一个目标函数引入正的或负的偏差变量; 引入目标的优先等级和加权系数。22运筹学-目标规划第二节第二节 目标规划的数学模型目标规划的数学模型1.目标期望值目标期望值 每一个目标希望达到的

12、期望值每一个目标希望达到的期望值(或目标值、理想值或目标值、理想值)。 根据历史资料、市场需求或上级部门的布置等来确定。根据历史资料、市场需求或上级部门的布置等来确定。一、一、目标值和偏差变量目标值和偏差变量目标规划通过引入目标值和偏差变量,可目标规划通过引入目标值和偏差变量,可以将目标函数转化为目标约束。以将目标函数转化为目标约束。实现值或决策值:是指当决策变量实现值或决策值:是指当决策变量xj选定以后,选定以后,目标函数的对应值。目标函数的对应值。23运筹学-目标规划第二节第二节 目标规划的数学模型目标规划的数学模型2 2、偏差变量、偏差变量 正偏差变量正偏差变量dk+ 表示第k个目标超过

13、期望值的数值; 负偏差变量负偏差变量dk- 表示第k个目标未达到期望值的数值。 同一目标的dk+ 和dk- 中至少有一个必须为零。偏差变量偏差变量(事先无法确定的未知数事先无法确定的未知数):是指实现值和目标值:是指实现值和目标值之间的差异之间的差异,记为记为 d 。偏差可能存在正的或负的。正偏差变量正偏差变量:表示实现值超过目标值的部分,记为表示实现值超过目标值的部分,记为d。负偏差变量负偏差变量:表示实现值未达到目标值的部分,记为表示实现值未达到目标值的部分,记为d。运筹学-目标规划目标规划的数学模型在一次决策中,实现值不可能既超过目标值又未达在一次决策中,实现值不可能既超过目标值又未达到

14、目标值,故有到目标值,故有dd0,并规定并规定d0, d0当完成或超额完成规定的指标则表示:当完成或超额完成规定的指标则表示:d0, d0当未完成规定的指标则表示:当未完成规定的指标则表示: d0, d0当恰好完成指标时则表示:当恰好完成指标时则表示: d0, d0运筹学-目标规划目标规划的数学模型二二.目标约束和绝对约束目标约束和绝对约束引入了目标值和正、负偏差变量后,就对某一问题有了引入了目标值和正、负偏差变量后,就对某一问题有了新的限制,既目标约束。新的限制,既目标约束。目标约束即可对原目标函数起作用,也可对原约束起作目标约束即可对原目标函数起作用,也可对原约束起作用。目标约束是目标规划

15、中特有的,是软约束。用。目标约束是目标规划中特有的,是软约束。绝对约束绝对约束(系统约束系统约束)是指必须严格满足的等式或不等式是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束,否约束。如线性规划中的所有约束条件都是绝对约束,否则无可行解。所以,绝对约束是硬约束。则无可行解。所以,绝对约束是硬约束。运筹学-目标规划目标规划的数学模型例如:在例一中,规定例如:在例一中,规定Z1的目标值为的目标值为 50000,正、负偏差正、负偏差为为d、d ,则目标函数可以转换为目标约束,既则目标函数可以转换为目标约束,既:50000120701121 - - - -ddxx若规定若规

16、定3600的钢材必须用完,原式的钢材必须用完,原式9x1 +4x2 3600变为变为3600494421 - - - -ddxx运筹学-目标规划第二节第二节 目标规划的数学模型目标规划的数学模型-njkkjkjEddxc1* 引入正负偏差变量,对各个目标建立目标约束(软约束)1.目标约束表示目标约束表示运筹学-目标规划例:甲乙产品的最优生产计划。例:甲乙产品的最优生产计划。产品产品资源资源甲甲乙乙现有资源现有资源 设备设备A2016设备设备B0210设备设备C3432单位利润单位利润 35根据市场需求根据市场需求/合同规定:合同规定: 希望尽量扩大甲产品希望尽量扩大甲产品 减少乙产品产量。减少

17、乙产品产量。又增加二个目标:又增加二个目标: maxZ1=3x1+5x2 maxZ2=x1minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1,x2 0 运筹学-目标规划第二节第二节 目标规划的数学模型目标规划的数学模型 要求:要求:l目标一是利润最大,拟定利润目标是目标一是利润最大,拟定利润目标是30;l目标二是减少乙产品产量但希望不低于目标二是减少乙产品产量但希望不低于4件;件;l目标三是甲产品产量希望不少于目标三是甲产品产量希望不少于6件件 ;l对各目标引入正、负偏差变量:对各目标引入正、负偏差变量: 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d

18、2+ =4 x1 +d3 -d3+ = 6运筹学-目标规划目标规划的数学模型三三.优先因子优先因子(优先等级优先等级)与优先权系数与优先权系数目标等级化目标等级化:将目标按重要性程度不同依次分成一级目将目标按重要性程度不同依次分成一级目标、二级目标标、二级目标.。最次要的目标放在次要的等级中。最次要的目标放在次要的等级中。(1)对同一目标而言,若有几个决策方案都能使其达到,对同一目标而言,若有几个决策方案都能使其达到,可认为这些方案就这个目标而言都是最优方案;若达可认为这些方案就这个目标而言都是最优方案;若达不到,则与目标差距越小的越好。不到,则与目标差距越小的越好。(2)不同级别的目标的重要

19、性是不可比的。即较高级别不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失,任何较低级别目标上的收获的目标没有达到的损失,任何较低级别目标上的收获不可弥补。故在判断最优方案时,首先从较高级别的不可弥补。故在判断最优方案时,首先从较高级别的目标达到的程度来决策,然后再其次级目标的判断。目标达到的程度来决策,然后再其次级目标的判断。(3)同一级别的目标可以是多个。各自之间的重要程度同一级别的目标可以是多个。各自之间的重要程度可用数量(权数)来描述。因此,同一级别的目标的可用数量(权数)来描述。因此,同一级别的目标的其中一个的损失,可有其余目标的适当收获来弥补。其中一个的损失,可有其余

20、目标的适当收获来弥补。运筹学-目标规划目标规划的数学模型三三.优先因子优先因子(优先等级优先等级)与优先权系数与优先权系数优先因子优先因子Pk是将决策目标按其重要程度排序并表示出是将决策目标按其重要程度排序并表示出来。来。P1P2PkPk+1PK ,k=1,2,K。表。表示示Pk比比Pk+1有更大的优先权。即首先保证有更大的优先权。即首先保证P1级目标的实级目标的实现,这时可不考虑次级目标;而现,这时可不考虑次级目标;而P2级目标是在实现级目标是在实现P1级级目标的基础上考虑的;依此类推。目标的基础上考虑的;依此类推。若要区别具有相同优先因子的两个目标的差别,这时若要区别具有相同优先因子的两个

21、目标的差别,这时可分别赋予它们不同的权系数可分别赋予它们不同的权系数j,这些都由决策者按具这些都由决策者按具体情况而定。体情况而定。 运筹学-目标规划目标规划的数学模型四四.达成函数达成函数(即目标规划中的目标函数即目标规划中的目标函数)目标规划的目标函数目标规划的目标函数(准则函数准则函数)是按各目标约束的正、负是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后,决策者的要求是尽可能缩小偏离目标值。一目标值确定后,决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是因此目标规划的目标函数只能是m

22、inZ = f(d、d)。一般说来,有以下三种情况,但只能出现其中之一:一般说来,有以下三种情况,但只能出现其中之一:(1)要求恰好达到规定的目标值,即正、负偏差变量要尽要求恰好达到规定的目标值,即正、负偏差变量要尽可能小,则可能小,则minZ = f(d d)。(2)要求不超过目标值,即允许达不到目标值,也就是正要求不超过目标值,即允许达不到目标值,也就是正偏差变量尽可能小,则偏差变量尽可能小,则minZ = f(d)。(3)要求超过目标值,即超过量不限,但不低于目标值,要求超过目标值,即超过量不限,但不低于目标值,也就是负偏差变量尽可能小,则也就是负偏差变量尽可能小,则minZ = f(d

23、)。对由绝对约束转化而来的目标函数,也照上述处理即可。对由绝对约束转化而来的目标函数,也照上述处理即可。运筹学-目标规划例:甲乙产品的最优生产计划。例:甲乙产品的最优生产计划。产品产品资源资源甲甲乙乙现有资源现有资源 设备设备A2016设备设备B0210设备设备C3432单位利润单位利润 35根据市场需求根据市场需求/合同规定:合同规定: 希望尽量扩大甲产品希望尽量扩大甲产品 减少乙产品产量。减少乙产品产量。又增加二个目标:又增加二个目标: maxZ1=3x1+5x2 maxZ2=x1minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1,x2 0 运筹学-目标规划第二节第二

24、节 目标规划的数学模型目标规划的数学模型例如例如 P1 级目标实现利润至少30元; P2级目标是甲乙产品的产量 假设:乙产品产量不少于4件比甲产品产量不少于6件更重要,取其权重为2 minG= P1 d1- + P2(2d2- + d3- ) 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ = 4 x1 + d3- - d3+ = 6 x1 , x2 ,dk- , dk+ 0(k=1,2,3)运筹学-目标规划目标规划的数学模型五五.多目标规划的解多目标规划的解(1)若多目标规划问题的解能使所有的目标都达到,若多目标规划问题的解能使所有的目标都达到,就称该解为多目标规划的

25、最优解;就称该解为多目标规划的最优解;(2)若解只能满足部分目标,就称该解为多目标规划若解只能满足部分目标,就称该解为多目标规划的次优解;的次优解;(3)若找不到满足任何一个目标的解,就称该问题为若找不到满足任何一个目标的解,就称该问题为无解。无解。(4)前面的目标可以保证实现或部分实现,而后面的前面的目标可以保证实现或部分实现,而后面的目标就不一定能保证实现或部分实现,有些可能就目标就不一定能保证实现或部分实现,有些可能就不能实现,就称该解为多目标规划的不能实现,就称该解为多目标规划的满意解满意解(具有层具有层次意义的解次意义的解)运筹学-目标规划单目标规划例例5-2:某工厂生产某工厂生产A

26、,B两种产品,有关数据如下。实现目两种产品,有关数据如下。实现目标利润为标利润为140万元的最优生产方案万元的最优生产方案AB可用量可用量设备设备(台时台时)4260原材料原材料(KG)2448利润利润(万元万元)86从决策者的角度看,他希望超过利润目标值,若达不从决策者的角度看,他希望超过利润目标值,若达不到,也希望尽可能接近,即负偏差最小到,也希望尽可能接近,即负偏差最小 - - 0, 0,21ddxx 484221xx 602421xx - - - - 1406821ddxx st - -mindZ运筹学-目标规划级别相等的多目标规划例例5-3:若上例中假设决策者根据市场预测,产品:若上

27、例中假设决策者根据市场预测,产品A的销的销售量有下降的趋势,故考虑实现下列两个目标:售量有下降的趋势,故考虑实现下列两个目标:(1)实现利润目标实现利润目标122万元万元(2)产品产品A的产量不多于的产量不多于10分析分析:两个目标级别相等,即两个目标的重要程度一样,两个目标级别相等,即两个目标的重要程度一样,不存在谁优先的问题不存在谁优先的问题设设d,d-分别为超过目标值的部分,以及未完成目分别为超过目标值的部分,以及未完成目标值的部分,于是两个目标可以等价表示为:标值的部分,于是两个目标可以等价表示为:10122681211121 - - - - - - - -ddxddxx运筹学-目标规

28、划级别相等的多目标规划x1=10,x2=7,d10,d+20,利润为,利润为122,两个目标均,两个目标均已经实现已经实现 - - - - - - - - - - - - - -0,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ运筹学-目标规划具有优先级别的多目标规划对于多个目标,如果有一定的优先顺序,即第一位重对于多个目标,如果有一定的优先顺序,即第一位重要的目标,其优先因子为要的目标,其优先因子为P1,第二位重要的目标,其,第二位重要的目标,其优先因子为优先因子为P2,并规定,并规定P1P2优先保证优先保证P1级目标的

29、实现,此时不考虑次级目标;次级目标的实现,此时不考虑次级目标;次级目标级目标P2在实现了在实现了P1级目标的基础上再予以考虑。如级目标的基础上再予以考虑。如果无法实现果无法实现P1目标,则不考虑目标,则不考虑P2目标能否取得最优目标能否取得最优若有若有k个不同优先顺序的目标,则有个不同优先顺序的目标,则有P1P2Pk将权重与偏差相乘构成目标函数,这样,权重越大,将权重与偏差相乘构成目标函数,这样,权重越大,越先迫使相应的偏差等于零,这样可保证优先级高的越先迫使相应的偏差等于零,这样可保证优先级高的目标首先实现。目标首先实现。运筹学-目标规划具有优先级别的多目标规划例例5-4:若上例中决策者拟订

30、下列经营目标,并确定了目:若上例中决策者拟订下列经营目标,并确定了目标之间的优先顺序标之间的优先顺序P1级目标:充分利用设备有效台时,不加班;级目标:充分利用设备有效台时,不加班;P2级目标:产品级目标:产品B的产量不多于的产量不多于4;P3级目标:实现利润值级目标:实现利润值130万元万元分析:题目有三个目标层次,包含三个目标值。分析:题目有三个目标层次,包含三个目标值。 第一目标:第一目标: P1(d1+d1-) 第二目标:第二目标:P2d2 第二目标:第二目标:P3d3 - - - - - - - - - - - - - - - - - -0,48421306846024)(212133

31、2122211213322111iiddxxxxddxxddxddxxstdPdPddPMinZ运筹学-目标规划具有优先级别的多目标规划例例5-5:某厂计划下一个生产周期内生产甲、乙两种产品,:某厂计划下一个生产周期内生产甲、乙两种产品,已知资料如表所示。制定生产计划,满足下列目标:已知资料如表所示。制定生产计划,满足下列目标: P1级目标:完成或超额完成利润指标级目标:完成或超额完成利润指标 50000元;元;P2级目标:产品甲不超过级目标:产品甲不超过 200件,产品乙不低于件,产品乙不低于 250件;件;P3级目标:现有钢材级目标:现有钢材 3600吨必须用完吨必须用完12070单件利润

32、单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲单位单位 产品产品资源资源 消耗消耗运筹学-目标规划具有优先级别的多目标规划分析:题目有三个目标层次,包含四个目标值。分析:题目有三个目标层次,包含四个目标值。 第一目标:第一目标: P1d1- 第二目标:有两个要求即甲第二目标:有两个要求即甲d2,乙,乙d3-,但两个具,但两个具有相同的优先因子,需要确定权系数。本题可用单件利有相同的优先因子,需要确定权系数。本题可用单件利润比作为权系数即润比作为权系数即70:120,化简为,化简为7:12,P2(7d2+12d3 -) 第三目标:第三目标:

33、P3(d4+d4 -) - - - - - - - - - - - - - - - - - - - - - - -0,30001032000543600492502005000012070)()127(2121214421332221112144332211iiddxxxxxxddxxddxddxddxxstddPddPdPMinZ运筹学-目标规划六、目标规划数学模型的一般形式 - - - - - - - - - - - - - - - - - - - - )55(3 , 2 , 1, 0,)45(, 1, 0)35(, 1,),()25(, 1,) 15()(min1111kddnjxmib

34、xaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLll满足约束条件:满足约束条件:目标函数目标函数:w ww w其中其中Pl为优先因子,为优先因子, w w- -lk,w w lk为优先系数为优先系数运筹学-目标规划七、建模的步骤根据要研究的问题所提出的各目标与条件,确定目标根据要研究的问题所提出的各目标与条件,确定目标值,列出目标约束与绝对约束;值,列出目标约束与绝对约束; 可根据决策者的需要,将某些或全部绝对约束转化为可根据决策者的需要,将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏

35、差变量即可。减去正偏差变量即可。给各目标赋予相应的优先因子给各目标赋予相应的优先因子 Pk对同一优先等级中的各偏差变量,若需要可按其重要对同一优先等级中的各偏差变量,若需要可按其重要程度的不同,赋予相应的权系数程度的不同,赋予相应的权系数 kl+和和kl- 。根据决策者的要求,构造一个由优先因子和权系数相根据决策者的要求,构造一个由优先因子和权系数相对应的偏差变量组成的,要求实现极小化的目标函数,对应的偏差变量组成的,要求实现极小化的目标函数,即达成函数。即达成函数。运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划线性规划与目标规划线性规划线性规

36、划LP目标规划目标规划GP目标函数目标函数min, max系数可正负系数可正负min , 偏差变量偏差变量系数系数0变量变量xi , xs , xa xi , xs , xa , d约束条件约束条件系统约束系统约束(绝对约束绝对约束)目标约束目标约束系统约束系统约束解解最优最优满意满意运筹学-目标规划第三节 目标规划的图解法运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运

37、筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划112231211222133121212min(2)3530(1)4(2)(3)6(4)216s.t.(5)210(6)3432(7),0,0(1,2,3)llGPdPddxxddxddxddxxxxx xddl-F2x1 =162x2 =10BCx14A103x1 +4 x2 =326x20D2642EGH1d-1d2d-2d3d-3d满意解:满意解:x1=5, x2=473运筹学-目标规划第三节第三节 目标规划的图解法目标规划的图解法目标规划的图解法目标规划的图解法n首先,按照绝对约束画出可行域,首先,按照绝对约束画出可行域,

38、n其次,不考虑正负偏差变量,画出目标约束的边界线,其次,不考虑正负偏差变量,画出目标约束的边界线,n最后。按优先级别和权重依次分析各级目标。最后。按优先级别和权重依次分析各级目标。112231211222133121212min(2)3530(1)4(2)(3)6(4)216s.t.(5)210(6)3432(7),0,0(1,2,3)llGPdPddxxddxddxddxxxxx xddl-F2x1 =162x2 =10BCx14A103x1 +4 x2 =326x20D2642EGH1d-1d2d-2d3d-3d满意解:满意解:x1=5, x2=474运筹学-目标规划 - - - - -

39、- - - - - - - - - )2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B-1d1d2d-2dCB (0.6250 , 4.6875) C (0 , 5.2083) , B、C 线段上的所有点均线段上的所有点均是该问题的解是该问题的解 (无穷多最优解无穷多最优解)。第三节第三节 目标规划的图解法目标规划的图解法运筹学-目标规划 - - - - - - - - - - - - - - - - - - - - - -)4

40、. 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 0 x2 0(1)x11401201008060402020 40 60 80 100(2)(3)(4)-2d2d-1d1d-3d3d-4d4dABCD结论:结论:C(60 ,58.3)为所求的满意解。为所求的满意解。目标规划的图解法运筹学-目标规划目标规划的图解法图解法解题步骤如下:图解法解题步骤如下:1.确定各约束条件的可行域,即将所有约束条件确定各约束条件的可行域,即将所有约束条件(包括包括目标约束和

41、绝对约束,暂不考虑正负偏差变量目标约束和绝对约束,暂不考虑正负偏差变量)在坐在坐标平面上表示出来;标平面上表示出来;2.在目标约束所代表的边界线上,用箭头标出正、负偏在目标约束所代表的边界线上,用箭头标出正、负偏差变量值增大的方向;差变量值增大的方向;3.求满足最高优先等级目标的解;求满足最高优先等级目标的解;4.转到下一个优先等级的目标,在不破坏所有较高优先转到下一个优先等级的目标,在不破坏所有较高优先等级目标的前提下,求出该优先等级目标的解;等级目标的前提下,求出该优先等级目标的解;5.重复重复4,直到所有优先等级目标都已审查完毕为止;,直到所有优先等级目标都已审查完毕为止;6.确定最优解

42、和满意解。确定最优解和满意解。运筹学-目标规划 目标规划与线性规划的数学模型的结构相似目标规划与线性规划的数学模型的结构相似 可用前述单纯形算法求解目标规划模型:可用前述单纯形算法求解目标规划模型: 将优先等级Pk视为正常数(大法 ) 正负偏差变量dk+、dk-视为松弛变量 以负偏差变量dk-为初始基变量,建立初始单纯形表 检验数的计算与LP单纯形法相同,即j= cj - CBi Pj 最优性判别准则类似于LP的单纯形算法:检验数一般是各优先等级因子的代数和判断检验数的正负和大小 78运筹学-目标规划目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型结构形目标规划的数学模型结构与线性

43、规划的数学模型结构形式上没有本质的区别,所以可用单纯形法求解。但要考虑目式上没有本质的区别,所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点,作以下规定:标规划的数学模型一些特点,作以下规定:(1) 因目标规划问题的目标函数都是求最小化,所以以因目标规划问题的目标函数都是求最小化,所以以cj-zj0,j=1,2,,n为最优准则。为最优准则。(2)因非基变量的检验数中含有不同等级的优先因子,即因非基变量的检验数中含有不同等级的优先因子,即KknjPazckkjjj, 2 , 1;, 2 , 1 - - 因因P1P2PK;从每个检验数的整体来看:检验数;从每个检验数的整体来看:检验数的正、

44、负首先决定于的正、负首先决定于P1的系数的系数1j的正、负。若的正、负。若1j=0,这时此,这时此检验数的正、负就决定于检验数的正、负就决定于P2的系数的系数2j的正、负。的正、负。运筹学-目标规划例例运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划见表见表4-13.运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划运筹学-目标规划目标规划的单纯形法例例 :用单纯形法求解下列目标规划问题:用单纯形法求解下列目标规划问题 MinZ=P1 d

45、1- + P2(d2-+d2+)+P3(3d3-+5d4-) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+= 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 0运筹学-目标规划目标规划的单纯形法cj 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数检验数jP1P2P300P10 P2P23P305P3020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4-5-401000-4-3

46、22-535463-检验数检验数jP1P2P3d1-d2-x1d4-P1P205P331000001-1005041-100-55001203001-1-440050100001-11-10-40105-50-324-4-5-25513-P1 P23P35P3运筹学-目标规划目标规划的单纯形法cj00P10 P2P23P305P30 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数检验数jP1P2P3d3+d2-x1d4-0P205P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-

47、1/500001-1010001/54/5-4/52-9-1135-10-检验数检验数jP1P2P3d3+d1+x1d4-0005P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10100011-35/4-5/45/4354-832/7运筹学-目标规划目标规划的单纯形法cj00P10 P2P23P305P30 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数检验数jP1P2P3x2d1+x1d4-0005P3401001/3-1/3 -4/34/3001100

48、-114/3-4/3 -1/31/3003100000-110010000-1/31/37/3-7/31-10010 0115/3-5/3-26/335/35-3检验数检验数jP1P2P3x2d1+x1d3-0003P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-119/7-9/7001/7-1/718/710001/7-1/700-3/73/700100 0113/7-3/7326/79/7运筹学-目标规划目标规划的单纯形法例:用单纯形法求解下列目标规划问题例:用单纯形法求解下列目标规划问题 minZ=P1 d1+P2(d2-

49、+d2+)+P3d3- 2x1+ x2 + x3 = 11 x1 - x2 +d1- - d1+= 0 x1 + 2x2 +d2- - d2+ = 10 8x1 + 10 x2 +d3- - d3+ = 56 xi,dk- , dk+ 0运筹学-目标规划目标规划的单纯形法运筹学-目标规划运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例一、无穷多满意解一、无穷多满意解解:设解:设x1,x2表示表示A、B产品的产量。两个等级的目标:产品的产量。两个等级的目标:P1:充分利用电量限额,正负偏差之和为最小 目标达成函数目标达成函数 目标约束条件目标约束条件 P2 :利润额希望不能低于

50、100元,负偏差最小 目标达成函数目标达成函数 目标约束条件目标约束条件 )(111- ddP6612101121-ddxx-22dP10020102221-ddxx计划生产两种产品,计划生产两种产品,首先要充分利用设备工时而不加班;然首先要充分利用设备工时而不加班;然后考虑利润不低于后考虑利润不低于100元。问应如何制定产品元。问应如何制定产品A、B的产量。的产量。104运筹学-目标规划2A24BDx26810 x1第五节第五节 目标规划的应用案例目标规划的应用案例一、无穷多满意解一、无穷多满意解由于材料供应限量为由于材料供应限量为8单位,所以有系统约束条件,如下单位,所以有系统约束条件,如

51、下8221 xx该问题的目标规划模型如下,图解法求解如图该问题的目标规划模型如下,图解法求解如图111221211122212121122min()101266(1)(2)1020100s.t.(3)28,0,0GP ddP dxxddxxddxxx xdddd-CG1d-1d2d-2d105运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题例:某音像店有例:某音像店有5名全职售货员和名全职售货员和4名兼职售货员,全职名兼职售货员,全职售货员每月工作售货员每月工作160小时,兼职售货员每月工作小时,兼职售货员每月工作80小时。根小时。根据记录,全

52、职每小时销售据记录,全职每小时销售CD25张,平均每小时工资张,平均每小时工资15元,元,加班工资每小时加班工资每小时22.5元。兼职售货员每小时销售元。兼职售货员每小时销售CD10张,张,平均工资每小时平均工资每小时10元,加班工资每小时元,加班工资每小时10元。现在预测下元。现在预测下月月CD销售量为销售量为27500张,商店每周开门营业张,商店每周开门营业6天,所以可能天,所以可能要加班。每出售一张要加班。每出售一张CD盈利盈利1.5元。元。 商店经理认为,保持稳定的就业水平加上必要的加班,商店经理认为,保持稳定的就业水平加上必要的加班,比不加班就业水平要好,但全职销售员如果加班过多,就

53、比不加班就业水平要好,但全职销售员如果加班过多,就会因为疲劳过度而造成效率下降,因此不允许每月加班超会因为疲劳过度而造成效率下降,因此不允许每月加班超过过100小时,建立相应的目标规划模型。小时,建立相应的目标规划模型。106运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题首先,确定目标约束的优先级。如下:首先,确定目标约束的优先级。如下:P1:下月的:下月的CD销售量达到销售量达到27500张;张;P2:全职售货员加班时间不超过:全职售货员加班时间不超过100小时;小时;P3:保持全体售货员充分就业,对全职的要比兼职的加:保持全体售货员充分就

54、业,对全职的要比兼职的加倍优先考虑;倍优先考虑;P4:尽量减少加班时间,对两种售货员区别对待,权重:尽量减少加班时间,对两种售货员区别对待,权重由他们对利润的贡献而定。由他们对利润的贡献而定。其次,建立目标约束函数其次,建立目标约束函数(1)销售目标约束,设全体全职售货员下月的工作时)销售目标约束,设全体全职售货员下月的工作时间间x1,全体兼职售货员下月的工作时间,全体兼职售货员下月的工作时间 x2;达不到销售目;达不到销售目标的偏差标的偏差d1-,超过销售目标的偏差,超过销售目标的偏差 d1+。 1111211min251027500GPdxxdd- 107运筹学-目标规划第五节第五节 目标

55、规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题 (2)正常工作时间约束。设全体全职售货员下月的停工时间)正常工作时间约束。设全体全职售货员下月的停工时间d2-,加班时间加班时间d2+ ;全体兼职售货员下月的停工时间;全体兼职售货员下月的停工时间d3-,加班时间,加班时间d3+。(3)加班时间的限制。设全体全职售货员下月的加班不足)加班时间的限制。设全体全职售货员下月的加班不足100小时小时的偏差的偏差d4-,加班超过,加班超过100小时的偏差小时的偏差 d4+ 。两类售货员区别对待,权重比两类售货员区别对待,权重比d2+:d3+ =1:3,另一加班目标约束为,另一加班目标约束

56、为3323122233min(2)800320GPddxddxdd-224144min900GP dxdd-4423122233min(3)800320GP ddxddxdd-108运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例二、加班时间问题二、加班时间问题 第三,按目标的优先级,写出相应的目标规划模型:第三,按目标的优先级,写出相应的目标规划模型:1124323423121112223314412min(2)(3)251027500800320s.t.900,0,01,2,3,4llGPdP dPddP ddxxddxddxddxddx xddl-运用运用LINGO软件

57、求解得软件求解得 x1=900,x2=500,下月共销售,下月共销售CD盘盘27500张,获利张,获利275001.5-80015-10022.5-50010=22000。109运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例三、目标管理方案三、目标管理方案 例:某公司准备生产甲、乙产品,据市场调查:甲产品的最大例:某公司准备生产甲、乙产品,据市场调查:甲产品的最大市场需求市场需求3台,乙产品的最大市场需求台,乙产品的最大市场需求2台。台。 在满足现有电力资源严格供给约束的前提下,该厂长考虑两在满足现有电力资源严格供给约束的前提下,该厂长考虑两个目标:个目标:一是总利润不低于

58、一是总利润不低于36003600元;二是充分利用设备台时,元;二是充分利用设备台时,但尽量少加班。但尽量少加班。问应如何制定产品甲、乙的产量,试建立其目问应如何制定产品甲、乙的产量,试建立其目标规划的数学模型。标规划的数学模型。110运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例三、目标管理方案三、目标管理方案 1. 利润期望优先利润期望优先目标规划数学模型:目标规划数学模型: 1122212111222121212min()300400360030603605560s.t.86,0,01,2llGPdP ddxxddxxddxxxxx xddl-运用图解法进行求解运用图解

59、法进行求解 FECx1 =8x2 =65x1 +5x2 =600 x12410126ABx20842D10G1d-1d2d-2dx1 =8, x2 = 3111运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例1. 利润期望优先利润期望优先 总利润:总利润:3600单位甲:单位甲:300单位乙:单位乙:400生产部目标生产部目标甲产品的产量:甲产品的产量:8,成本:,成本:900乙产品的产量:乙产品的产量:3,成本:,成本:1400技术部目标技术部目标甲的设备单耗甲的设备单耗25,需降低,需降低5工时工时 乙的设备单耗乙的设备单耗50,需降低,需降低10工时工时 销售部目标销售

60、部目标甲产品的销量:甲产品的销量:8,单价:,单价:1200乙产品的销量:乙产品的销量:3,单价:,单价:1800满意解:满意解:x1 =8, x2 = 3设备能力:需求:设备能力:需求:30 8+60 3=420,实际:,实际:360实现实现目标目标P1和和P2,降低甲乙产品的设备消耗,降低甲乙产品的设备消耗:降低率降低率(420-360)/360=17%, 甲产品的设备消耗降为甲产品的设备消耗降为30 (1-17%)=25, 乙产品的设备消耗降为乙产品的设备消耗降为60 (1-17%)=50。112运筹学-目标规划第五节第五节 目标规划的应用案例目标规划的应用案例三、目标管理方案三、目标管

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论