目标规划培训教材

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 目标规划,北京物资学院运筹学教学课件,信息学院数学教研室,20,11,年,4,月,Goal Programming,本章主,要,要内容,：,：,一、问,题,题提出,与,与目标,规,规划的,数,数学模,型,型,二、目,标,标规划,的,的解法,一、问,题,题提出,与,与目标,规,规划的,数,数学模,型,型,线性规,划,划：在一,组,组线性,约,约束下,一,一个线,性,性函数,的,的极值,问,问题。,线性规,划,划的局,限,限性,只能解,决,决一组,线,线性约,束,束条件,下,下，某,一,一目标,而,而且只,能,能是一,个,个目标,的,的最大,或,或最小,值,值的问,题,题。,实际决,策,策中，,衡,衡量方,案,案优劣,常,常常需,要,要考虑,多,多个目,标,标,比如,1,）,.,生产计,划,划决策,中,中，通,常,常要考,虑,虑产值,、,、利润,、,、满足,市,市场需,求,求、降,低,低消耗,、,、提高,质,质量、,提,提高劳,动,动生产,率,率等；,2,）,.,生产布,局,局决策,中,中，除,了,了要考,虑,虑运输,费,费用、,投,投资、,原,原料供,应,应、产,品,品需求,量,量等经,济,济指标,外,外，还,要,要考虑,到,到污染,和,和其它,社,社会因,素,素等。,这些目,标,标中，,有,有主要,的,的，也,有,有次要,的,的；有,最,最大的,，,，也有,最,最小的,；,；有定,量,量的，,也,也有定,性,性的；,有,有互相,补,补充的,，,，也有,互,互相对,立,立的，,LP,则无能,为,为力。,目标规,划,划（,Goal Programming）,在线性,规,规划的,基,基础上,发,发展起,来,来的解,决,决多目标,规,规划问,题,题的最有,效,效的方,法,法之一,。,。,美国经,济,济学家,查,查恩斯(,A.Charnes),和库柏(,W.W.Cooper),在1961年,出,出版的,管理,模,模型及,线,线性规,划,划的工,业,业应用,一书,中,中，首,先,先提出,的,的。,1976年伊,格,格尼齐,奥,奥发表,了,了目,标,标规划,及,及其扩,展,展一,书,书，系,统,统归纳,总,总结了,目,目标规,划,划的理,论,论和方,法,法。,例1.,某,某企业,计,计划生,产,产甲、,乙,乙两种,产,产品，,这,这些产,品,品分别,要,要在,A、B,、,、C、D,四,种不同,的,的设备,上,上加工,。,。各产,品,品占用,资,资源数,量,量，资,源,源拥有,量,量及产,品,品利润,见,见下表,。,。问如,何,何安排,生,生产，,才,才能获,得,得最大,的,的总利,润,润？,3,2,利润（,百,百元/,件,件）,12,4,0,D,16,0,4,C,8,2,1,B,12,2,2,A,设备工,作,作台时,乙,甲,消耗,产,产品,设备,解：设,x,1,， x,2,分别表,示,示甲乙,产,产品的,产,产量，,则,则相应,的,的线性,规,规划模,型,型为：,它的最,优,优解为:,x,1,=4,x,2,=2,z,=14,假设企,业,业的经,营,营目标,不,不仅仅,是,是利润,，,，而是,要,要考虑,多,多个方,面,面的目,标,标,:,（1）,企,企业利,润,润不低,于,于12,（,（百元,）,）。,（2）,力,力争使,甲,甲乙两,种,种产品,的,的比例,大,大致为1：1,。,。,（3）,设,设备,B,必要时,可,可以加,班,班，但,不,不希望,加,加班；,设,设备,A,既要充,分,分利用,，,，又尽,可,可能不,加,加班。,是否可,以,以用线,性,性规划,解,解决上,述,述多目,标,标的问,题,题？,为了解,决,决上述,多,多目标,的,的规划,问,问题，,就,就需要,使,使用目,标,标规划,的,的方法,。,线性规,划,划模型,存,存在以,下,下几方,面,面的局,限,限性,:,1.LP,只能处,理,理单目,标,标优化,问,问题。,因,因此，,线,线性规,划,划模型,中,中人为,地,地将一,些,些次要,目,目标转,化,化为约,束,束。（,在,在实际,中,中，目,标,标和约,束,束可以,相,相互转,化,化）,2.,LP,要求问,题,题的解,必,必须满,足,足全部,约,约束条,件,件，但,实,实际中,并,并非所,有,有约束,都,都必须,严,严格满,足,足。,3.,LP,中各个,约,约束（,实,实际上,也,也可以,看,看作目,标,标）都,处,处于同,等,等重要,地,地位，,但,但实际,问,问题中,各,各个目,标,标既有,层,层次上,的,的差别,，,，又有,权,权重上,的,的区分,。,。,4.,LP,寻求,最,最优,解,解，,但,但很,多,多问,题,题只,要,要找,到,到满,意,意解,即,即可,。,。,目标,规,规划,解,解决,上,上述,LP,建模,中,中的,局,局限,性,性的,方,方法,：,：,对每,个,个目,标,标函,数,数确,定,定一,个,个希,望,望达,到,到的期望,值,值(目,标,标值,或,或理,想,想值)；,由,由于,各,各种,条,条件,的,的限,制,制，,这,这些,目,目标,值,值往,往,往不,可,可能,全,全部,都,都达,到,到；,对每,一,一个,目,目标,函,函数,引,引入,正,正的,或,或负,的,的偏差,变,变量，分,别,别表,示,示超,过,过或,未,未达,到,到目,标,标值,的,的情,况,况；,对所,有,有的,目,目标,函,函数,建,建立约束,方,方程，并,入,入原,来,来的,约,约束,条,条件,中,中，,组,组成,新,新的,约,约束,条,条件,；,；,引入,目,目标,的,的优先,等,等级,和,和加,权,权系,数,数；建,立,立使,组,组合,偏,偏差,最,最小,的,的目,标,标函,数,数。,1.,确,确定,目,目标,函,函数,的,的期,望,望值,每一,个,个目,标,标函,数,数希,望,望达,到,到的,期,期望,值,值(,或,或目,标,标值,、,、理,想,想值)。,根据,历,历史,资,资料,、,、市,场,场需,求,求或,上,上级,部,部门,的,的布,置,置等,来,来确,定,定。,2.,设,设置,偏,偏差,变,变量,，,，用,来,来表,明,明实,际,际值,同,同目,标,标值,之,之间,的,的差,异,异。,超,超出,目,目标,的,的差,值,值，,称,称正,偏,偏差,变,变量,；,；,-,未,未达,到,到目,标,标的,差,差值,，,，称,负,负偏,差,差变,量,量。,与,两者,必,必有,一,一个,为,为零,（1,）,）,-,0,，,，,0,表,表,示,示实,际,际值,超,超出,规,规定,目,目标,值,值；,（2,）,）,-,0,，,，,0,表,表,示,示实,际,际值,未,未达,到,到目,标,标值,；,（3,）,）,-,=0，,0 表示,实,实际值同规,定,定目标值恰,好,好一致。,3.统一处,理,理目标和约,束,束,系统约束(,硬,硬约束)：对资源使用,上,上有严格限,制,制的约束，,用,用严格的等,式,式或不等式,表,表示（同线,性,性规划中的,约,约束）。,如：,4,x,1,16,(设备,C,的使用时间),4x,2,12 (设,备,备,D,的使用时间,),目标约束（,软,软约束）：,引入正、负,偏,偏差变量后,，,，对各个目,标,标建立的目,标,标约束方程,。,。,原来的目标,函,函数变成了,约,约束条件的,一,一部分，即,目,目标约束(,软,软约束),设备,A,既要充分利,用,用，又尽可,能,能不加班,可,可以写成,mind,3,-,+d,3,+,2,x,1,+2x,2,+ d,3,-,- d,3,=12,(设备,A),设备,B,允许加班，,只,只是不希望,加,加班或少加,班,班，可以写,成,成,min,d,4,x,1,+2x,2,+,d,4,-,- d,4,=8,(设备,B),原来的目标,函,函数，在目,标,标规划中只,是,是成了问题,要,要达到的目,标,标之一 ,“,“目标利润,不,不低于12,（,（百元 ）,”,”, 可以,表,表示成,mind,1,-,2,x,1,+3x,2,+ d,1,-,- d,1,=12,要求甲、乙,两,两种产品的,比,比例尽可能,接,接近11,，,，可以表示,成,成,mind,2,-,+ d,2,x,1,-x,2,+d,2,-,- d,2,= 0,4.,目标函数、,目,目标的优先,级,级和权系数,（1）在目,标,标规划中，,如,如果两个不,同,同目标的重,要,要程度相差,悬,悬殊，为达,到,到某一目标,可,可牺牲其他,目,目标，称这,些,些目标是属,于,于不同层次,的,的优先级。,优,优先级层次,的,的高低可通,过,过优先因子,P,1,，P,2,表示。,并规定,P,k, P,k+1,，,即不同优先,级,级之间的差,别,别无法用数,字,字大小衡量,。,。,（2）对属,于,于同一层次,优,优先级的不,同,同目标，其,重,重要程度的,差,差别可以通,过,过设置权系,数,数来表达。,权,权系数越大,，,，表示目标,越,越重要。,目标规划中,的,的目标函数,是,是各个实际,值,值与目标值,之,之间的最小,差,差距。,本例中，假,设,设：,P,1,：企业利润,目,目标；,P,2,：甲、乙产,品,品的产量尽,可,可能达到1,1的要求,；,；,P,3,：设备,A、B,尽量不超负,荷,荷工作，在,第,第三优先级,中,中，设备,A,的重要性是,设,设备,B,的三倍。,本例中，假,设,设：,P,1,：企业利润,目,目标；,P,2,：甲、乙产,品,品的产量尽,可,可能达到1,1的要求,；,；,P,3,：设备,A、B,尽量不超负,荷,荷工作，在,第,第三优先级,中,中，设备,A,的重要性是,设,设备,B,的三倍。,目标约束：,f(x)+ d,-,-,d,= f,0,;,1.,要求性能指,标,标,f(x),尽量达到目,标,标值,f,0,（即不足,f,0,不好，超出,f,0,也不好）,min(d,-,+ d,),=,f,0,2.要求性,能,能指标,f(x),的值不少于,目,目标值,f,0,(即允许超,过,过,f,0,，但尽可能,不,不要少于,f,0,）,min（d,-,）,f,0,3.要求性,能,能指标,f(x),的值不超过,目,目标值,f,0,(即允许,少,少于,f,0,，但尽可,能,能不要超,过,过,f,0,）,min（d,）,f,0,小结,课堂练习1：,某工厂计,划,划生产,A、B,两种产品,，,，每吨产,品,品的耗电,量,量指标、,原,原材料消,耗,耗、单位,产,产品利润,及,及资源限,量,量如表所,示,示。,厂长首先,考,考虑要充,分,分利用供,电,电部门分,配,配的电量,限,限额66,，,，,然后考虑,利,利润不低,于,于100,元,元；,其次据市,场,场调查结,果,果，希望,B,产品的产,量,量不低于,A,产品的产,量,量，,问应如何,安,安排产品,A、B,的产量。,20,10,单位产品,利,利润,8,1,2,原材料,66,12,10,电力,资源限量,B,A,消耗,产,产品,资源,解：设,x,1,、x,2,分别表示,A、B,两种产品,的,的产量，,则,则目标规,划,划模型如,下,下：,课堂练习2：,某电视机,厂,厂装配黑,白,白和彩色,两,两种电视,机,机，每装,配,配一台电,视,视机需要,占,占用装配,线,线,1,小时，装,配,配线每周,计,计划开动,40,小时。预,计,计市场每,周,周彩色电,视,视机的销,量,量为,24,台，每台,可,可获利,80,元；黑白,电,电视机的,销,销量是,30,台，每台,可,可获利,40,元。该厂,确,确定的目,标,标为：,第一优先,级,级：充分利,用,用装配线,每,每周计划,开,开动的,40,小时；第二优先,级,级：允许装,配,配线加班,，,，但加班,的,的时间尽,量,量不超过,10,小时；第三优先,级,级：装配电,视,视机的数,量,量尽量满,足,足市场需,要,要。因彩,色,色电视机,利,利润高，,取,取其权为,2,。,试确定该,厂,厂为达到,以,以上目标,的,的最优生,产,产计划。,（,（建立数,学,学模型）,解：设,x,1, x,2,分别表示,彩,彩色和黑,白,白电视机,的,的产量。,该,该问题的,目,目标规划,模,模型为：,作业：,P145.,第 5.,8,题,二、目标,规,规划的解,法,法,（一）目,标,标规划的,图,图解法,（二）目,标,标规划的,单,单纯形解,法,法,(一)、,目,目标规划,的,的图解法,只含有两,个,个决策变,量,量,(,不考虑偏,差,差变量,),的目标规,划,划模型,线性规划,是,是在可行,域,域中寻找,一,一点，使,单,单个目标,极,极大或极,小,小；,目标规划,则,则是寻找,一,一个区域,，,，这个区,域,域提供了,相,相互矛盾,的,的目标集,的,的,折,折衷方案,。,。,目标规划,的,的图解法,的,的思路,首先是在,可,可行域内,寻,寻找一个,使,使,P,1,级各目标,均,均满足的,区,区域,R,1,；,然后再在,R,1,中寻找一,个,个使,P,2,级各目标,均,均满足的,区,区域,R,2,(R,2,R,1,)；,接着再在,R,2,中寻找一,个,个满足,P,3,级各目标,的,的区域,R,3,(R,3,R,2,R,1,)；,如此继续,，,，直到寻,找,找到一个,区,区域,R,K,(R,K,R,K-1,R,3,R,2,R,1,)，,满足,P,K,级各目标,，,，这时,R,K,即为这个,目,目标规划,的,的最优解,空,空间，其,中,中的任一,点,点均为这,个,个目标规,划,划的满意,解,解。,目标规划,的,的图解法,的,的步骤,第一步：,按,按照系统,约,约束画出,可,可行域，,第二步：,不,不考虑正,负,负偏差变,量,量，画出,目,目标约束,的,的边界线,，,，,第三步：,按,按优先级,别,别和权重,依,依次分析,各,各级目标,。,。,选择,F,点作为满,意,意解,即,x,1,=3,x,2,=3,企业的利,润,润是15,百,百元。,F,G,H,x,1,x,2,(1),(2),(3),(4),(5),(6),例2 用,图,图解法求,解,解目标规,划,划,课堂练习,：,： 用图,解,解法求解,目,目标规划,x,1,x,2,(1),(2),(3),(4),由于,E,点使得,d,4,-,取值最小,，,，故,E,点为满意,解,解,(24,26),E,(二,)、,求解目标,规,规划的单,纯,纯形法,目标规划,与,与线性规,划,划的数学,模,模型的结,构,构相似,可用前述,单,单纯形算,法,法求解目,标,标规划模,型,型：,由于检验,数,数一般是,各,各优先等,级,级因子的,代,代数和，,为,为方便可,以,以将检验,数,数行根据,优,优先因子,分,分成,K,行，判断,检,检验数的,正,正负和大,小,小主要根,据,据优先因,子,子的系数,正,正负和大,小,小。,由于,目,目标,规,规划,是,是极,小,小化,问,问题,，,，最,优,优性,标,标准,是,是：,检,检验,数,数非,负,负。,将优,先,先等,级,级,P,k,视为,正,正常,数,数(,类,类似,于,于大,法,法)(,P,1,P,2,P,3,.P,K,);,正负,偏,偏差,变,变量,d,k,+,d,k,-,视为,松,松弛,变,变量;,以负,偏,偏差,变,变量,d,k,-,为初,始,始基,变,变量,，,，建,立,立初,始,始单,纯,纯形,表,表,检验,数,数的,计,计算,与,与,LP,单纯,形,形表,检,检验,数,数的,计,计算,完,完全,相,相同,最优,性,性判,别,别准,则,则类,似,似于,LP,的单,纯,纯形,算,算法,：,：,例3,：,：用,单,单纯,形,形法,求,求解,下,下列,目,目标,规,规划,问,问题,以负,偏,偏差,变,变量,作,作为,第,第一,组,组基,变,变量,，,，填,入,入单,纯,纯形,表,表,0,0,P,1,0,0,P,1,P,2,0,C,B,B,b,x,1,x,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,P,1,d,1,-,10,1,0,1,-1,0,0,0,0,0,d,2,-,40,2,1,0,0,1,-1,0,0,P,2,d,3,-,100,3,2,0,0,0,0,1,-1,10,20,100/3,j,P,1,-1,0,0,1,0,1,0,0,P,2,-3,-2,0,0,0,0,0,1,0,x,1,10,1,0,1,-1,0,0,0,0,0,d,2,-,20,0,1,-2,2,1,-1,0,0,P,2,d,3,-,70,0,2,-3,3,0,0,1,-1,j,P,1,0,0,1,0,0,1,0,0,P,2,0,-2,3,-3,0,0,0,1,10,70/3,0,d,1,+,10,0,1/2,-1,1,1/2,-1/2,0,0,0,x,1,20,1,1/2,0,0,1/2,-1/2,0,0,P,2,d,3,-,40,0,1/2,0,0,-3/2,3/2,1,-1,j,P,1,0,0,1,0,0,1,0,0,P,2,0,-1/2,0,0,3/2,-3/2,0,1,40,20,80,0,d,1,+,10,0,1/2,-1,1,1/2,-1/2,0,0,0,x,1,20,1,1/2,0,0,1/2,-1/2,0,0,P,2,d,3,-,40,0,1/2,0,0,-3/2,3/2,1,-1,j,P,1,0,0,1,0,0,1,0,0,P,2,0,-1/2,0,0,3/2,-3/2,0,1,0,0,P,1,0,0,P,1,P,2,0,C,B,B,b,x,1,x,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,0,x,2,20,0,1,-2,2,1,-1,0,0,0,x,1,10,1,0,1,-1,0,0,0,0,P,2,d,3,-,30,0,0,1,-1,-2,2,1,-1,j,P,1,0,0,1,0,0,1,0,0,P,2,0,0,-1,1,2,-2,0,1,虽然,P,2,行有,负,负检,验,验数,，,，但,由,由于,其,其对,应,应的,P,1,行的,检,检验,数,数均,为,为正,，,，所,以,以计,算,算停,止,止，,得,得到,目,目标,规,规划,的,的满,意,意解,：,：,x,1,=10,x,2,=20。,注意,：,：,对目,标,标的,优,优化,是,是按,优,优先,级,级顺,序,序逐,级,级进,行,行的,，,，当,P,1,行的,所,所有,检,检验,数,数均,为,为非,负,负时,，,，说,明,明第,一,一优,先,先级,的,的目,标,标已,得,得到,优,优化,，,，可,转,转入,下,下一,级,级，,再,再考,察,察,P,2,行的,检,检验,数,数是,否,否存,在,在负,值,值，,依,依次,类,类推,。,。,考察,P,2,行的,检,检验,数,数时,注,意,意应,包,包括,更,更高,级,级别,的,的优,先,先因,子,子在,内,内,例,例如,上,面,面的,最,最后,一,一张,单,单纯,形,形表,中,中最,下,下面,的,的,P,2,行有,两,两个,负,负值,，,，其,对,对应,的,的变,量,量,d,1,-,的检,验,验数,为,为,P,1,-P,2,0,变量,d,2,+,的检,验,验数,为,为,P,1,-2P,2,0。,因此判断迭代计,算,算应否停止的准,则,则为：,检验数,P,1,P,2,P,K,行的所有值均非,负,负；,若,P,1,P,2,P,i,行的所有值均非,负,负，第,P,i+1,行存在负检验数,，,，但在负检验数,所,所在列的上面行,中,中有正的检验数,。,。,作业：,P145.,第 5.,3(a),题,(,图解法,),第 5.,3(c),题,(,单纯形法,),课后习题讲解,:P14,5,5.8,某牌号的酒系由,三,三种酒兑制而成,，,，已知各种等级,的,的酒的每天供应,量,量和单位成本如,下,下：,等级,供应量（单位,/,天）,成本（元,/,单位）,I,1500,6,II,2000,4.5,III,1000,3,该种牌号的酒有,三,三种商标，各种,商,商标酒的混合比,及,及售价如下,商标,兑制配比要求,单位售价（元）,红,I,多于,50%,，,III,少于,10%,5.5,黄,I,多于,20%,，,III,少于,70%,5.0,蓝,I,多于,10%,，,III,少于,50%,4.8,P1,：兑制要求配比,必,必须严格满足；,P2,：企业获取尽可,能,能多的利润；,P3,：红色商标酒每,天,天的产量不低于,2000,单位。,解：设生产红色,商,商标酒使用的三,种,种原料的数量分,别,别为,x,11,x,12,x,13,;,生产黄色商标酒,使,使用的三种原料,的,的数量分别为,x,21,x,22,x,23,;,生产蓝色商标酒,使,使用的三种原料,的,的数量分别为,x,31,x,32,x,33,;,原料限制,配比要求,