第四章：目标规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,运筹学教学,第一章 绪论,第一节,1.1,运,筹,学,张铭鑫机汽学院工业工程,2006,年,4,月,目标规划的问题的提出,线性规划是单一的目标函数,它不适应复杂多变的经营管理,中综合多指标的实际要求,.,实际问题实际上都是多指标要求的,是,一个体系,要求全面考虑,;,而且各个指标的度量单位还不统一,还,有各个指标在企业实际运作中的重要程度也是不同的,.,在线性规划中的各个约束条件,我们要求都是必须要满足的,.,这些约束条件它们的刚性太强,就是缺乏柔性,而实际中,我们在,企业生产实际中遇到的问题,往往是具有一定的柔性的,一定的可,调节性,.,目标规划是数学规划中用于解决多目标决策的一个分支,.,就,是针对线性规划的单一目标值,单一最优解这样一个局限性,以及,线性规划约束条件缺乏柔性,而发展起来的一个分支,.,我们称它为,目标规划,.,是,1961,年,是美国的两个数学家首次提出了目标规划,.,4,目标规划问题,(,问题的提出,),4,目 标 规 划,4.1,目标规划的数学模型,例,1,某工厂生产,两种产品,已知有关数据见下表,.,试求,获利最大的生产方案,.,4.1,目标规划的数学模型,4,目 标 规 划,拥有量,原材料,设备,2,1,1,2,11,10,利润,8,10,解,:,设,X,1,X,2,表示生产,两种产品的产量,.,目标函数,:,MaxZ,=8X,1,+10X,2,约束条件,:2X,1,+X,2,11,X,1,+2X,2,10,X,1,X,2,0,最优决策方案为,X,1,=4,X,2,=3,Z=62,但实际上工厂在作决策时,要考虑市场等一系列的其,它条件,.,(1),根据市场信息,产品,的销售量有下降的趋势,故,考虑产品,的产量不大于产品,的产量,.,(2),超过计划供应的原材料时,需用高价采购,会使成,本大幅增加,.,(3),尽可能充分利用设备台时,但不希望加班,.,(4),尽可能的达到并超过计划利润指标,56,元,.,考虑条件,在考虑产品决策时,便为多目标决策问题,.,目标规划方法是解,决这类问题的方法之一,.,下面引入与建立目标规划数学模型的有,关概念,.,1.,设,x,1,x,2,为决策变量,此外,引进正、负偏差变量,d,+,d,-,d,+,表示实际的值超过目标值的部分,d,-,表示实际的值没有到,达目标值的那一部分,.,因决策值不可能既超过目标值又低于目标,值,.,既有有,d,+,d,-,=0,.,2.,绝对约束和目标约束,绝对约束,是指必须严格满足的等式约束或者是不等式约束,.,还有一些约束条件,不必严格满足,可能是等式,也可能是不等式,.,那么这样的一些约束条件,它不定完全满足,我们允许它发生一点,偏差,.,那么这个偏差可能是正的,也可能是负的,.,我们称这样的约,束为,软约束,.,概念（,1,，,2,）,3.,优先因子,(,优先等级,),与权系数,.,因为在目标规划中常常有若干个目标,那我们作为一个决策,者在实现这个目标时,要分主次,要有轻重缓急的不同,所以要赋,予不同的优先因子。,具有相同优先因子的两个目标，决策者可以根据实际情况,对它们分别赋予不同的权系数，代表在相同优先等级的目标中,相对重要的目标,.,4.,目标规划的目标函数,目标规划的目标函数,(,准则函数,),是按各自目标约束的正负,偏差变量和赋予相应的优先因子及权系数构成的,.,在目标规划里,面,每当一个目标值确定以后,决策者的要求是尽可能缩小偏离目,标值,因此目标规划的目标函数只能是,minz,f(d,+,d,-,),。,概念（,3,，,4,）,4.,目标规划的目标函数,(1),要求恰好达到目标值,即正,负偏差变量都要尽可,能地小,.,Minz,=,f(d,+,+d,-,),(2),要求不超过目标值,即正偏差变量要尽可能地小,.,Minz,=,f(d,+,),(3),要求超过目标值,即负偏差变量要尽可能地小,.,Minz,=,f(d,-,),概念,4,（,1-3,）,例,2.,例,1,的决策者在原材料供应受到严格限制的基础上考虑,首先产品,的产量不低于产品,的产量,;,其次是充分利用设备有,效台时,不加班,;,再此是利润额不小于,56,元,.,求决策方案,.,解,:,我们按决策者的要求,分别赋予这三个目标,P,1,P,2,P,3,优先,因子。,例,2,目标规划的一般数学模型,.,目标规划的一般数学模型,4.2,目标规划的图解法,.,用图解法求解的时候,先考虑决策变量,之后再考虑偏差变量,.,把原来的线性规划中的约束条件都用直线表示出来,.,现在,没有考虑偏差变量,.,就相当于没有偏差,正好在这个目标上,.,也就是说,我们在做目标约束的时候,先令正偏差变量和负偏差变量都等于,0.,然后,按照偏差变量的含义,在相应的直线旁边标上正偏差变量和负偏差变量的相应的方向,.,4.2,目标规划的图解法,x1,x2,O,B,A,C,E,F,D,J,G,d1,+,d1,-,d2,+,d2,-,d3,+,d3,-,绝对约束,d1,+,=0,d2,-,=0,d2,+,=0,d3,-,=0,例,2,图解法,例,3.,某电视厂装配黑白和彩色两种电视机,每装配一台电视,机需占用装配线,1,小时,装配线每周计划开动,40,小时,.,预计市场每,周彩色电视机的销量是,24,台,每台可获利,80,元,;,黑白电视机的销量,是,30,台,每台可获利,40,元,.,该厂确定的目标为,:,例,3,第一优先级,充分利用装配线每周计划开动,40,小时；,第二优先级,允许装配线加班,;,但加班时间每周尽量不超过,10,小时,;,第三优先级,装配的电视机的数量尽量满足市场需要,但因彩色电视机的利润高,取其权系数为,2.,建立问题的目标规划模型,并求解黑白和彩色电视机的产量,.,解：设,x1,和,x2,分别表示彩色,和黑白电视机的产量,.,x1,x2,0,20,30,A,50,10,10,30,D,20,50,d,1,-,d,1,+,x,1,+x,2,=40,例,3,图解法,(,约束,1),x1,x2,0,20,30,A,B,10,10,30,D,20,C,d,1,+,d,2,+,d,2,-,x,1,+x,2,=50,x1,x2,0,20,30,10,10,30,20,d,1,-,d,1,+,例,3,图解法,(,约束,2),x1,x2,0,20,30,A,B,10,10,30,D,20,C,d,1,-,d,1,+,d,2,+,d,2,-,d,3,-,x,1,=24,d,3,+,例,3,图解法,(,约束,3),x1,x2,0,20,30,A,B,10,10,30,D,20,C,d,1,-,d,1,+,d,2,+,d,2,-,d,3,-,d,4,-,x,2,=30,d,4,+,d,3,+,例,3,图解法,(,约束,4),x1,x2,0,20,30,A,B,10,10,30,D,20,C,d,1,+,d,2,+,d,2,-,d,3,-,Min d,1,-,=0,可行域如图,d,4,-,d,4,+,d,3,+,例,3,图解法,(d1),x1,x2,0,20,30,A,B,10,10,30,D,20,C,d,1,+,d,2,-,d,3,-,Min d2+=0,可行域如图,d,3,+,d,4,-,d,4,+,例,3,图解法,(d2),x1,x2,0,20,30,A,B,10,10,30,D,20,C,d,1,+,d,2,-,Min d3-=0,可行域如图,d,4,-,d,4,+,d,3,+,d,2,-,例,3,图解法,(d3),x1,x2,0,20,30,A,B,10,10,30,D,20,C,d,1,+,d,2,-,d,4,-,d,4,+,d,3,+,Min d4,-,P=(24,26),满意解,d,4,-,=4,例,3,图解法,(d4),E,例,3.,某电视厂装配黑白和彩色两种电视机,每装配一台电视,机需占用装配线,1,小时,装配线每周计划开动,40,小时,.,预计市场每,周彩色电视机的销量是,24,台,每台可获利,80,元,;,黑白电视机的销量,是,30,台,每台可获利,40,元,.,该厂确定的目标为,:,例,3,第一优先级,充分利用装配线每周计划开动,40,小时；,第二优先级,允许装配线加班,;,但加班时间每周尽量不超过,10,小时,;,第三优先级,装配的电视机的数量尽量满足市场需要,但因彩色电视机的利润高,取其权系数为,2.,建立问题的目标规划模型,并求解黑白和彩色电视机的产量,.,解：设,x1,和,x2,分别表示彩色和,黑白电视机的产量,.,x1=24,x2=26.,4.3,解目标规划的单纯形法,4.3,解目标规划的单纯形法,目标规划的特征：,（,1,）检验数的行数不止一行,.,检验数的行数是由目标优,先等级的个数来决定的,.,（,2,）在确定换入变量的时候,不但要根据本优先级的检验,数来考虑,还要根据比它更高的优先级的检验数来决定,.,因此目标规划的单纯形法有以下的规定：,（,1,）因目标规划问题的目标函数都是求最小的,.,j,0,为最优准则,.,（,2,）因目标规划中非基变量的检验数中含有不同等级的优先因子，即,单纯形法计算步骤,解目标规划问题的单纯形法的计算步骤：,（,1,）建立初始单纯形表，在表中将检验数行按优先因子,个数分别列成,K,行,.,（,2,）检查该行是否存在负数，且对应的前,k,1,行的系数,是零,.,若有负数取其中检验数最小值对应的变量作为换入变,量,转,(3),步,;,若无负数,则转,(5).,（,3,）按最小比值规则确定换出变量,当存在两个或两个以上相同的最小比值时,选取具有较高优先级别的变量作为换出变量,.,（,4,）按单纯形法进行换基迭代,建立新的计算表,返回第,(2).,（,5,）当,k,K,时,计算结束,.,表中的解即为满意解,.,否则按,k,k+1,返回第,(2).,例,4.,试用单纯形法来求例,2.,将例,2,的数学模型化为标准形：,例,4,数学模型,表,4-1,表,4-1,c,j,P,1,P,2,P,2,P,3,C,B,X,B,b,x,1,x,2,x,s,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,x,s,11,2,1,1,11/1,d,1,-,0,1,-1,1,-1,P,2,d,2,-,10,1,2,1,-1,10/2,P,3,d,3,-,56,8,10,1,-1,56/10,j,P,1,1,P,2,-1,-2,2,P,3,-8,-10,1,表,4-2,表,4-2,c,j,P,1,P,2,P,2,P,3,C,B,X,B,b,x,1,x,2,x,s,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,x,s,6,3/2,1,-1/2,1/2,4,d,1,-,5,3/2,1,-1,1/2,-1/2,10/3,x,2,5,1/2,1,1/2,-1/2,10,P,3,d,3,-,6,3,-5,5,1,-1,6/3,j,P,1,1,P,2,1,1,P,3,-3,5,-5,1,表,4-3,表,4-3,c,j,P,1,P,2,P,2,P,3,C,B,X,B,b,x,1,x,2,x,s,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,x,s,3,1,2,-2,-1/2,1/2,6,d,1,-,2,1,-1,3,-3,-1/2,1/2,4,x,2,4,1,4/3,-4/3,-1/6,1/6,24,P,3,x,1,2,1,-5/3,5/3,1/3,-1/3,j,P,1,1,P,2,1,1,P,3,1,表,4-4,表,4-4,c,j,P,1,P,2,P,2,P,3,C,B,X,B,b,x,1,x,2,x,s,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,x,s,1,1,-1,1,-1,1,d,3,+,4,2,-2,6,-6,-1,1,x,2,10/3,1,-1/3,1/