《第四章：目标规划.ppt》由会员分享，可在线阅读，更多相关《第四章：目标规划.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运 筹 学张铭鑫机汽学院工业工程2006年4月目标规划的问题的提出目标规划的问题的提出目标规划的问题的提出目标规划的问题的提出 线性规划是单一的目标函数线性规划是单一的目标函数,它不适应复杂多变的经营管理它不适应复杂多变的经营管理中综合多指标的实际要求中综合多指标的实际要求.实际问题实际上都是多指标要求的实际问题实际上都是多指标要求的,是是一个体系一个体系,要求全面考虑要求全面考虑;而且各个指标的度量单位还不统一而且各个指标的度量单位还不统一,还还有各个指标在企业实际运作中的重要程度也是不同的有各个指标在企业实际运作中的重要程度也是不同的.在线性规划中的各个约束条件在线性规划中的各个约束条件,
2、我们要求都是必须要满足的我们要求都是必须要满足的.这些约束条件它们的刚性太强这些约束条件它们的刚性太强,就是缺乏柔性就是缺乏柔性,而实际中而实际中,我们在我们在企业生产实际中遇到的问题企业生产实际中遇到的问题,往往是具有一定的柔性的往往是具有一定的柔性的,一定的可一定的可调节性调节性.目标规划是数学规划中用于解决多目标决策的一个分支目标规划是数学规划中用于解决多目标决策的一个分支.就就是针对线性规划的单一目标值是针对线性规划的单一目标值,单一最优解这样一个局限性单一最优解这样一个局限性,以及以及线性规划约束条件缺乏柔性线性规划约束条件缺乏柔性,而发展起来的一个分支而发展起来的一个分支.我们称它
3、为我们称它为目标规划目标规划.是是19611961年年,是美国的两个数学家首次提出了目标规划是美国的两个数学家首次提出了目标规划.4 4目标规划问题目标规划问题(问题的提出问题的提出问题的提出问题的提出 )4 4 目目 标标 规规 划划 4.14.14.14.1目标规划的数学模型目标规划的数学模型目标规划的数学模型目标规划的数学模型 例例1 1 某工厂生产某工厂生产,两种产品两种产品,已知有关数据见下表已知有关数据见下表.试求试求获利最大的生产方案获利最大的生产方案.4.14.1目标规划的数学模型目标规划的数学模型目标规划的数学模型目标规划的数学模型 4 4 目目 标标 规规 划划 拥有量拥有
4、量拥有量拥有量原材料原材料原材料原材料设备设备设备设备2 21 11 12 211111010利润利润利润利润8 81010解解:设设X X1 1,X,X2 2表示生产表示生产,两种产品的产量两种产品的产量.目标函数目标函数:MaxZMaxZ=8X=8X1 1+10X+10X2 2约束条件约束条件:2X:2X1 1+X+X2 21111 X X1 1+2X+2X2 21010 X X1 1,X,X2 20 0最优决策方案为最优决策方案为X X1 1=4,X=4,X2 2=3,Z=62=3,Z=62 但实际上工厂在作决策时但实际上工厂在作决策时,要考虑市场等一系列的其要考虑市场等一系列的其它条件
5、它条件.(1)(1)根据市场信息根据市场信息,产品产品的销售量有下降的趋势的销售量有下降的趋势,故故考虑产品考虑产品的产量不大于产品的产量不大于产品的产量的产量.(2)(2)超过计划供应的原材料时超过计划供应的原材料时,需用高价采购需用高价采购,会使成会使成本大幅增加本大幅增加.(3)(3)尽可能充分利用设备台时尽可能充分利用设备台时,但不希望加班但不希望加班.(4)(4)尽可能的达到并超过计划利润指标尽可能的达到并超过计划利润指标5656元元.考虑条件考虑条件 在考虑产品决策时在考虑产品决策时,便为多目标决策问题便为多目标决策问题.目标规划方法是解目标规划方法是解决这类问题的方法之一决这类问
6、题的方法之一.下面引入与建立目标规划数学模型的有下面引入与建立目标规划数学模型的有关概念关概念.1.1.设设x x1 1,x,x2 2为决策变量为决策变量,此外此外,引进正、负偏差变量引进正、负偏差变量d d+,d,d-d d+表示实际的值超过目标值的部分表示实际的值超过目标值的部分,d,d-表示实际的值没有到表示实际的值没有到达目标值的那一部分达目标值的那一部分.因决策值不可能既超过目标值又低于目标因决策值不可能既超过目标值又低于目标值值.既有有既有有d d+dd-=0=0.2.2.绝对约束和目标约束绝对约束和目标约束 绝对约束绝对约束是指必须严格满足的等式约束或者是不等式约束是指必须严格满
7、足的等式约束或者是不等式约束.还有一些约束条件还有一些约束条件,不必严格满足不必严格满足,可能是等式可能是等式,也可能是不等式也可能是不等式.那么这样的一些约束条件那么这样的一些约束条件,它不定完全满足它不定完全满足,我们允许它发生一点我们允许它发生一点偏差偏差.那么这个偏差可能是正的那么这个偏差可能是正的,也可能是负的也可能是负的.我们称这样的约我们称这样的约束为束为软约束软约束.概念（概念（1 1，2 2）3.3.优先因子优先因子(优先等级优先等级)与权系数与权系数.因为在目标规划中常常有若干个目标因为在目标规划中常常有若干个目标,那我们作为一个决策那我们作为一个决策者在实现这个目标时者在
8、实现这个目标时,要分主次要分主次,要有轻重缓急的不同要有轻重缓急的不同,所以要赋所以要赋予不同的优先因子。予不同的优先因子。具有相同优先因子的两个目标，决策者可以根据实际情况具有相同优先因子的两个目标，决策者可以根据实际情况,对它们分别赋予不同的权系数对它们分别赋予不同的权系数 ，代表在相同优先等级的目标中，代表在相同优先等级的目标中相对重要的目标相对重要的目标.4.4.目标规划的目标函数目标规划的目标函数 目标规划的目标函数目标规划的目标函数(准则函数准则函数)是按各自目标约束的正负是按各自目标约束的正负偏差变量和赋予相应的优先因子及权系数构成的偏差变量和赋予相应的优先因子及权系数构成的.在
9、目标规划里在目标规划里面面,每当一个目标值确定以后每当一个目标值确定以后,决策者的要求是尽可能缩小偏离目决策者的要求是尽可能缩小偏离目标值标值,因此目标规划的目标函数只能是因此目标规划的目标函数只能是minzminzf(df(d+,d,d-)。概念（概念（3 3，4 4）4.4.目标规划的目标函数目标规划的目标函数 (1)(1)要求恰好达到目标值要求恰好达到目标值,即正即正,负偏差变量都要尽可负偏差变量都要尽可能地小能地小.MinzMinz=f(df(d+d+d-)(2)(2)要求不超过目标值要求不超过目标值 ,即正偏差变量要尽可能地小即正偏差变量要尽可能地小.MinzMinz=f(df(d+
10、)(3)(3)要求超过目标值要求超过目标值 ,即负偏差变量要尽可能地小即负偏差变量要尽可能地小.MinzMinz=f(df(d-)概念概念4 4（1-31-3）例例2.2.例例1 1的决策者在原材料供应受到严格限制的基础上考虑的决策者在原材料供应受到严格限制的基础上考虑,首先产品首先产品的产量不低于产品的产量不低于产品的产量的产量;其次是充分利用设备有其次是充分利用设备有效台时效台时,不加班不加班;再此是利润额不小于再此是利润额不小于5656元元.求决策方案求决策方案.解解:我们按决策者的要求我们按决策者的要求,分别赋予这三个目标分别赋予这三个目标P P1 1,P,P2 2,P,P3 3优先优
11、先因子。因子。例例2 2 目标规划的一般数学模型目标规划的一般数学模型.目标规划的一般数学模型目标规划的一般数学模型4.24.24.24.2目标规划的图解法目标规划的图解法.用图解法求解的时候用图解法求解的时候,先考虑决策变量先考虑决策变量,之后再之后再考虑偏差变量考虑偏差变量.把原来的线性规划中的约束条件把原来的线性规划中的约束条件都用直线表示出来都用直线表示出来.现在现在,没有考虑偏差变量没有考虑偏差变量.就就相当于没有偏差相当于没有偏差,正好在这个目标上正好在这个目标上.也就是说也就是说,我们在做目标约束的时候我们在做目标约束的时候,先令正偏差变量和负先令正偏差变量和负偏差变量都等于偏差
12、变量都等于0.0.然后然后,按照偏差变量的含义按照偏差变量的含义,在相应的直线旁边在相应的直线旁边标上正偏差变量和负偏差变量的相应的方向标上正偏差变量和负偏差变量的相应的方向.4.24.24.24.2目标规划的图解法目标规划的图解法x1x2OBACEFDJGd1+d1-d2+d2-d3+d3-绝对约束d1+=0d2-=0d2+=0d3-=0例例2 2图解法图解法 例例3.3.某电视厂装配黑白和彩色两种电视机某电视厂装配黑白和彩色两种电视机,每装配一台电视每装配一台电视机需占用装配线机需占用装配线1 1小时小时,装配线每周计划开动装配线每周计划开动4040小时小时.预计市场每预计市场每周彩色电视
13、机的销量是周彩色电视机的销量是2424台台,每台可获利每台可获利8080元元;黑白电视机的销量黑白电视机的销量是是3030台台,每台可获利每台可获利4040元元.该厂确定的目标为该厂确定的目标为:例例3 3第一优先级第一优先级,充分利用装配线每充分利用装配线每周计划开动周计划开动40小时；小时；第二优先级第二优先级,允许装配线加班允许装配线加班;但但加班时间每周尽量不超过加班时间每周尽量不超过10小时小时;第三优先级第三优先级,装配的电视机的数装配的电视机的数量尽量满足市场需要量尽量满足市场需要,但因彩色但因彩色电视机的利润高电视机的利润高,取其权系数为取其权系数为2.建立问题的目标规划模型建
14、立问题的目标规划模型,并求并求解黑白和彩色电视机的产量解黑白和彩色电视机的产量.解：设解：设x1和和x2分别表示彩色分别表示彩色和黑白电视机的产量和黑白电视机的产量.x1x202030A50101030D2050d1 1-d1 1+x x1 1+x+x2 2=40=40例例3 3图解法图解法(约束约束1)1)x1x202030AB101030D20Cd1 1+d2 2+d2 2-x x1 1+x+x2 2=50=50 x1x20203010103020d1 1-d1 1+例例3 3图解法图解法(约束约束2)2)x1x202030AB101030D20Cd1 1-d1 1+d2 2+d2 2-d
15、3 3-x x1 1=24=24d3 3+例例3 3图解法图解法(约束约束3)3)x1x202030AB101030D20Cd1 1-d1 1+d2 2+d2 2-d3 3-d4 4-x x2 2=30=30d4 4+d3 3+例例3 3图解法图解法(约束约束4)4)x1x202030AB101030D20Cd1 1+d2 2+d2 2-d3 3-Min d1-=0可行域如图d4 4-d4 4+d3 3+例例3 3图解法图解法(d1)(d1)x1x202030AB101030D20Cd1 1+d2 2-d3 3-Min d2+=0可行域如图d3 3+d4 4-d4 4+例例3 3图解法图解法(
16、d2)(d2)x1x202030AB101030D20Cd1 1+d2 2-Min d3-=0 可行域如图d4 4-d4 4+d3 3+d2 2-例例3 3图解法图解法(d3)(d3)x1x202030AB101030D20Cd1 1+d2 2-d4 4-d4 4+d3 3+Min d4-P=(24,26)满意解d4-=4例例3 3图解法图解法(d4)(d4)E 例例3.3.某电视厂装配黑白和彩色两种电视机某电视厂装配黑白和彩色两种电视机,每装配一台电视每装配一台电视机需占用装配线机需占用装配线1 1小时小时,装配线每周计划开动装配线每周计划开动4040小时小时.预计市场每预计市场每周彩色电视
17、机的销量是周彩色电视机的销量是2424台台,每台可获利每台可获利8080元元;黑白电视机的销量黑白电视机的销量是是3030台台,每台可获利每台可获利4040元元.该厂确定的目标为该厂确定的目标为:例例3 3第一优先级第一优先级,充分利用装配线每充分利用装配线每周计划开动周计划开动40小时；小时；第二优先级第二优先级,允许装配线加班允许装配线加班;但但加班时间每周尽量不超过加班时间每周尽量不超过10小时小时;第三优先级第三优先级,装配的电视机的数装配的电视机的数量尽量满足市场需要量尽量满足市场需要,但因彩色但因彩色电视机的利润高电视机的利润高,取其权系数为取其权系数为2.建立问题的目标规划模型建
18、立问题的目标规划模型,并求并求解黑白和彩色电视机的产量解黑白和彩色电视机的产量.解：设解：设x1和和x2分别表示彩色和分别表示彩色和黑白电视机的产量黑白电视机的产量.x1=24,x2=26.4.34.3解目标规划的单纯形法解目标规划的单纯形法 4.34.34.34.3解目标规划的单纯形法解目标规划的单纯形法 目标规划的特征：目标规划的特征：（1 1）检验数的行数不止一行）检验数的行数不止一行.检验数的行数是由目标优检验数的行数是由目标优先等级的个数来决定的先等级的个数来决定的.（2 2）在确定换入变量的时候）在确定换入变量的时候,不但要根据本优先级的检验不但要根据本优先级的检验数来考虑数来考虑
19、,还要根据比它更高的优先级的检验数来决定还要根据比它更高的优先级的检验数来决定.因此目标规划的单纯形法有以下的规定：因此目标规划的单纯形法有以下的规定：（1 1）因目标规划问题的目标函数都是求最小的）因目标规划问题的目标函数都是求最小的.j j0 0为为最优准则最优准则.（2 2）因目标规划中非基变量的检验数中含有不同等级的）因目标规划中非基变量的检验数中含有不同等级的优先因子，即优先因子，即 单纯形法计算步骤单纯形法计算步骤 解目标规划问题的单纯形法的计算步骤：解目标规划问题的单纯形法的计算步骤：（1 1）建立初始单纯形表，在表中将检验数行按优先因子）建立初始单纯形表，在表中将检验数行按优先
20、因子个数分别列成个数分别列成K K行行.（2 2）检查该行是否存在负数，且对应的前）检查该行是否存在负数，且对应的前k k1 1行的系数行的系数是零是零.若有负数取其中检验数最小值对应的变量作为换入变若有负数取其中检验数最小值对应的变量作为换入变量量,转转(3)(3)步步;若无负数若无负数,则转则转(5).(5).（3 3）按最小比值规则确定换出变量）按最小比值规则确定换出变量,当存在两个或两个当存在两个或两个以上相同的最小比值时以上相同的最小比值时,选取具有较高优先级别的变量作选取具有较高优先级别的变量作为换出变量为换出变量.（4 4）按单纯形法进行换基迭代）按单纯形法进行换基迭代,建立新的
21、计算表建立新的计算表,返回第返回第(2).(2).（5 5）当）当k kK K时时,计算结束计算结束.表中的解即为满意解表中的解即为满意解.否则按否则按k kk+1,k+1,返回第返回第(2).(2).例例4.4.试用单纯形法来求例试用单纯形法来求例2.2.将例将例2 2的数学模型化为标准形：的数学模型化为标准形：例例4 4数学模型数学模型表表4-14-1表表4-14-1cjP1P2P2P3CBXBbx1x2xsd d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+xs1121111/1d d1 1-01-11-1P2d d2 2-10121-110/2P3d d
22、3 3-568101-156/10j jP11P2-1-22P3-8-101表表4-24-2表表4-24-2cjP1P2P2P3CBXBbx1x2xsd d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+xs63/21-1/21/24d d1 1-53/21-11/2-1/210/3x251/211/2-1/2 10P3d d3 3-63-551-16/3j jP11P211P3-35-51表表4-34-3表表4-34-3cjP1P2P2P3CBXBbx1x2xsd d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+xs312-2-1/21/26d d1 1-21-13-3-1/21/24x2414/3-4/3-1/61/624P3 x121-5/35/31/3-1/3j jP11P211P31表表4-44-4表表4-44-4cjP1P2P2P3CBXBbx1x2xsd d1 1-d d1 1+d d2 2-d d2 2+d d3 3-d d3 3+xs11-11-11d d3 3+42-26-6-11x210/31-1/31/31/3-1/3 P3 x110/312/3-2/31/3-1/3j jP11P211P31