MBA学位课程-运筹学2(1)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2.6 运输问题及其解法,引例：某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A,1,-40吨，A,2,-40吨，A,3,-90吨。该公司把这些产品分别运往四个销售点，各销售点每日销量为：B,1,-30吨，B,2,-40吨，B,3,-60吨，B,4,-20吨, B,5,-20吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少,销地,产地,B1,B2,B3,B4,B5,产量（万吨）,A1,7,10,8,6,4,40,A2,5,9,7,12,6,40,A3,3,6,5,8,11,90,销量（万吨）,30,40,60,20,20,1,解：这是一个,产,产销平衡的运,输,输问题， 设X,ij,表示从A,i,调运产品到B,j,的数量（吨）,，,，其数学模型,是,是：,2,一,、,、,产,产,销,销,平,平,衡,衡,的,的,运,运,输,输,问,问,题,题,及,及,其,其,解,解,法,法,1.,产,产,销,销,平,平,衡,衡,的,的,运,运,输,输,问,问,题,题,的,的,数,数,学,学,模,模,型,型,及,及,其,其,特,特,点,点,：,：,特,点,点,：,：,（,（1,）,）,其,其,系,系,数,数,矩,矩,阵,阵,的,的,结,结,构,构,疏,疏,松,松,，,，,且,且,每,每,一,一,列,列,向,向,量,量,P,ij,=(0,1,1,0),T,=e,i,+e,m+j,可,以,以,证,证,明,明,，,，r(A)=m+n,1,。,。,即,即,有,有m+n,1,个,个,独,独,立,立,方,方,程,程,。,。,于,是,是,，,，,该,该LP,问,问,题,题,有,有,且,且,仅,仅,有,有m+n,1,个,个,基,基,变,变,量,量,。,。,3,（2） （产销平衡条件）,（3）因为 , 故必有可行解和最优解。,由,于,于,上,上,述,述,特,特,点,点,，,，,若,若,按,按,单,单,纯,纯,形,形,法,法,求,求,解,解,必,必,须,须,增,增,加,加,人,人,工,工,变,变,量,量,，,，,致,致,使,使,计,计,算,算,量,量,大,大,大,大,增,增,加,加,，,，,故,故,用,用,特,特,殊,殊,解,解,法,法,表,表,上,上,作,作,业,业,法,法,。,。,2.,表,表,上,上,作,作,业,业,法,法,表,上,上,作,作,业,业,法,法,实,实,质,质,上,上,还,还,是,是,单,单,纯,纯,形,形,法,法,，,，,但,但,具,具,体,体,计,计,算,算,和,和,术,术,语,语,上,上,有,有,所,所,不,不,同,同,。,。,其,其,计,计,算,算,步,步,骤,骤,和,和,方,方,法,法,，,，,我,我,们,们,通,通,过,过,对,对,引,引,例,例,的,的,求,求,解,解,过,过,程,程,说,说,明,明,之,之,。,。,（1,）,）,用,用,最,最,小,小,元,元,素,素,法,法,确,确,定,定,初,初,始,始,方,方,案,案,（,（,即,即,初,初,始,始,基,基,可,可,行,行,解,解,）,）,切,记,记,在,在,产,产,销,销,平,平,衡,衡,表,表,上,上,必,必,须,须,且,且,只,只,能,能,填,填,写,写m+n,1,个,个,数,数,字,字,格,格,4,例18,（,（P37,）,）,设,设,某,某,产,产,品,品,从,从,产,产,地,地A1,，,，A2,，,，A3,运,运,往,往,销,销,地,地B1,，,，B2,，,，B3,，,，B4,，,，B5,，,，,运,运,量,量,和,和,单,单,位,位,运,运,价,价,如,如,下,下,表,表,所,所,示,示,，,，,问,问,如,如,何,何,调,调,运,运,才,才,能,能,使,使,总,总,的,的,运,运,费,费,最,最,少,少,？,？,销地,运价,产地,B1,B2,B3,B4,B5,产量（万吨）,A1,7,10,8,6,4,40,A2,5,9,7,12,6,40,A3,3,6,5,8,11,90,销量（万吨）,30,40,60,20,20,解,：,：,用,用,最,最,小,小,元,元,素,素,法,法,或,或,伏,伏,格,格,尔,尔,法,法,求,求,得,得,其,其,初,初,始,始,调,调,运,运,方,方,案,案,如,如,下,下,：,：,5,销地,运价,产地,B1,B2,B3,B4,B5,产量（万吨）,A1,7,10,8,6,4,40,A2,5,9,7,12,6,40,A3,3,6,5,8,11,90,销量（万吨）,30,40,60,20,20,30,40,60,20,20,0,0,接,下,下,来,来,我,我,们,们,就,就,要,要,判,判,别,别,这,这,个,个,调,调,运,运,方,方,案,案,是,是,否,否,是,是,最,最,优,优,调,调,运,运,方,方,案,案,？,？,判,别,别,的,的,方,方,法,法,同,同,线,线,性,性,规,规,划,划,一,一,样,样,，,，,首,首,先,先,求,求,出,出,空,空,格,格,的,的,检,检,验,验,数,数,，,，,由,由,于,于,是,是,最,最,小,小,化,化,问,问,题,题,，,，,所,所,以,以,当,当,所,所,有,有,空,空,格,格,的,的,检,检,验,验,数,数,均,均,小,小,于,于0,时,时,得,得,到,到,的,的,解,解,为,为,最,最,优,优,解,解,。,。,求运输问题的空,格,格的检验数的方,法,法有闭回路法和,位,位势法。,6,（2）用闭回路,法,法或位势法求空,格,格的检验数,1) 用,闭,闭回路法求检验,数,数：,首先，每一个空,格,格有且仅有一个,闭,闭回路，而圈格,无,无闭回路。,闭回路是以空格为起点,，,，沿同一行或同,一,一列前进，遇上,圈,圈格可转90度,继,继续前进，按此,方,方法进行下去，,直,直到回到始点的,一,一个封闭折线。,以始点为第0个,点,点，依次给闭回,路,路上的每一个顶,点,点编号。其中奇,序,序数对应的为奇,顶,顶点，偶数对应,的,的为偶顶点。,其次，每一个空格的检,验,验数=奇顶点运,费,费之和 偶,顶,顶点运费之和。,7,2)用位势法求,出,出空格的检验数,并,并进行最优解的,判,判别,设u,1,u,2,u,m,; v,1,v,2,v,n,是对应运输问题m+n个约束条,件,件的对偶变量，B为含有人工变,量,量的初始可行基,，,，由LP问题的,对,对偶理论知：C,B,B,-1,=(u,1,u,2,u,m,; v,1,v,2,v,n,),而每个决策变量X,ij,相应的系数向量P,ij,=e,i,+e,m+j,，所以C,B,B,-1,P,ij,=u,i,+v,j，,于是，检验数,ij,=C,B,B,-1,P,ij,C,ij,=(u,i,+v,j,)C,ij,又各基变量的检,验,验数为0，故对,每,每个基变量所在,的,的圈格的检验数,有,有,即有方程组：,共m+n个未知,数,数 s=m+n1个方程,8,显然上述方程有,解,解，且由于含有,一,一个自由变量，,因,因此，令任一未,知,知数为0，就可,求,求出上述方程组,的,的解(u,i1,u,i2,u,im,v,j1,v,j2,v,jn,)称为位势,解,解。,如用位势法求引,例,例初始基可行解,的,的检验数：,销地,运价,产地,B,1,B,2,B,3,B,4,B,5,v,j,A,1,7,10,8,6,4,6,A,2,5,9,7,12,6,12,A,3,3,6,5,8,11,10,u,i,-7,-3,-5,0,-2,-8,-7,-7,0,4,1,2,-3,30,40,60,20,20,0,0,9,第一步：将运价表中增加v,j,和u,i,列。,第二步：利用圈格分别算,出,出u,i,和v,j,，即,令u,1,=0，然后按u,i,+v,j,=C,ij,(i,j,J,B,)，相继确定u,i,，v,j,的值。,第三步：按,ij,= (u,i,+v,j,)C,ij,(i,j,J,N,)算出表中各空,格,格（即非基变量,）,）的检验数：,由于运输问题的,目,目标函数是求最,小,小化，,故判别最优解的,准,准则是所有的非,基,基变量的检验数,：,：,ij,=C,B,B,-1,P,ij,C,ij,0,因为,25,=+4， ,32,=+1， ,34,=+2均为正数,，,，所以目前尚未,得,得到最优解（其,实,实只要有一个正,检,检验数，所对应,的,的方案就不是最,优,优方案），尚须,改,改进。,方案的调整（即,换,换基迭代）是在,闭,闭回路上进行,10,3）在调运平衡,表,表上用闭回路法,进,进行调整，得到,新,新的基可行解（,新,新的调运方案）,i)确定进基变量：,自,自上而下，自左,向,向右第一个正检,验,验数相应的非基,变,变量（空格）为,进,进基变量。,ii)作闭回路：以进,基,基变量空格为出,发,发点，用水平或,垂,垂直线向前划，,当,当碰到某一恰当,数,数格转90,后，继续前进，,直,直至回到起始空,格,格止。,iii)确定调整量,=min奇顶,点,点的调运量（即闭回路上奇,顶,顶点运量的最小,值,值为调整量）,iv)在闭回路上进行,调,调整：,对闭回路上每个,奇,奇顶点的调运量,，,对闭回路上每个,偶,偶顶点（含起始,格,格）的调运量+,。调整后，将闭,回,回路中为0的一,个,个数格作为空格,（,（即出基变量）,。,。闭回路外的各,调,调运量不变。这,样,样便得到新的调,运,运方案（新基可,行,行解),11,销地,运价,产地,B1,B2,B3,B4,B5,产量（万吨）,A1,7,10,8,6,+0,4,-0,40,A2,5,9,7,12,-0,6,+0,40,A3,3,6,5,8,11,90,销量（万吨）,30,40,60,20,20,20,B,1,B,2,B,3,B,4,B,5,产量（万吨）,A,1,7,10,8,6,4,40,A,2,5,9,7,12,6,40,A,3,3,6,5,8,11,90,销量（万吨）,30,40,60,20,20,20,0,0,40,30,60,20,30,60,40,0,20,20,0,12,4）表,上,上作业,法,法须注,意,意的问,题,题：,i)在最终,调,调运表,中,中，若,有,有某个,空,空格（,非,非基变,量,量）的,检,检验数,为,为0时,，,，则表,明,明该运,输,输问题,有,有多重,调,调运方,案,案；,ii)在确定,初,初始方,案,案时，,若,若某一,行,行的产,量,量与某,一,一列的,需,需求量,同,同时满,足,足，这,时,时也只,能,能划去,一,一行或,一,一列（,绝,绝对不,能,能同时,把,把行、,列,列划去,，,，否则,就,就不满,足,足圈格=m+n1,个,个的要,求,求，即,基,基变量,的,的个数,永,永远要,保,保持为m+n,1个,）,）；,iii)在用闭,回,回路法,调,调整时,，,，当闭,回,回路上,奇,奇顶点,有,有几个,相,相同的,最,最小值,时,时，调,整,整后只,能,能有一,个,个空格,，,，其余,均,均要保,留,留数“0”，,以,以保证,圈,圈格=m+n,1个,的,的需要,。,。,iv)用最小,元,元素法,所,所得到,的,的初始,方,方案可,以,以不唯,一,一。,13,二、产,销,销不平,衡,衡的运,输,输问题,及,及其求,解,解方法,1.数,学,学模型,：,：,产大于销,销大于产,14,然后再,用,用产销,平,平衡的,运,运输问,题,题的解,法,法进行,解,解之。,2.解法思路：,将不平衡运输问题转化为平衡运输问题。即当,时，考虑在平衡表中增加一虚拟列，表示增加一个销货点,(j=n+1)如仓库，其销货量为 ，且各运价,C,in+1,=0；当 时，考虑在平衡表中增加一虚拟,行，表示增加一个新产地，且各运价C,m+1j,=0。,15,例题19（P45）,三,三,个,个电视,机,机厂供,应,应四个,地,地区某,种,种型号,的,的电视,机,机，其,运,运价表,如,如下，,试,试求总,运,运费最,少,少的调,运,运方案,？,？,例18,下,下表是,一,一个运,输,输问题,的,的单位,运,运价表,。,。,B,1,B,2,B,3,B,4,产量（万吨）,A,1,10,3,5,6,50,A,2,2,11,3,12,70,A,3,7,8,1,8,70,销量（万吨）,20,30,40,60,比较总,产,产量和,总,总销量,可,可知，,这,这是一,个,个非平,衡,衡运输,问,问题（,属,属于产,大,大于销,的,的情况,）,），为,化,化为平,衡,衡运输,问,问题，,需,需虚设,一,一个销,点,点B,5,，其运,价,价为0,，,，其销,量,量为40。,B,5,0,0,0,40,16,销地,厂家,B,1,B,2,B,3,B,4,产量（万台）,A,1,6,3,12,6,10,A,2,4,3,9,12,A,3,9,10,13,10,10,最低需求,6,14,0,5,最高需求,10,14,6,不限(12),销地,厂家,B,1,B,1,B,2,B,3,B,4,B,4,产量（万台）,A,1,6,6,3,12,6,6,10,A,2,4,4,3,9,M,M,12,A,3,9,9,10,13,10,10,10,A,4,M,0,M,0,M,10,10,销量,6,4,14,6,5,7,化为产,销,销平衡,的,的运输,问,问题有,：,：,17,三、转,运,运问题,及,及其解,法,法,1.所,谓,谓转运,问,问题是,在,在以下,背,背景产,生,生的：,(1),每,每个工,厂,厂生产,的,的产品,不,不直接,运,运到销,地,地，可,以,以几个,产,产地集,中,中一起,运,运。,(2),运,运往各,销,销地的,物,物资可,先,先运给,其,其中的,几,几个销,地,地，再,转,转运给,其,其它销,地,地。,(3),除,除产、,销,销地之,外,外，还,可,可以有,几,几个中,间,间转运,站,站，在,产,产地之,间,间，销,地,地之间,或,或产销,地,地之间,转,转运。,凡类似,上,上述情,况,况下的,调,调运物,资,资并使,总,总运费,最,最小的,问,问题统,称,称为转,运,运问题,。,。,2.求,解,解“转,运,运问题,”,”的思,路,路是把,问,问题中,所,所有的,产,产地、,中,中转站,和,和销地,都,都既看,作,作产地,，,，又都,看,看作销,地,地，把,“,“转运,问,问题”,变,变成扩,大,大后的,产,产销平,衡,衡的运,输,输问题,处,处理。,18,3.求,解,解“转,运,运问题,”,”的方,法,法步骤,：,：,(1),建,建立扩,大,大的产,销,销平衡,运,运输问,题,题单位,运,运价表,。,。其中,1)对,两,两地不,能,能直接,运,运输的,单,单位运,价,价定为M（很,大,大的正,数,数）,3)对,产,产量列,的,的各数,据,据可按,下,下式计,算,算并填,入,入：,A,i,的产量=a,i,+,T,j,产量=,，B,j,的产量=,4)对,销,销量行,的,的各数,据,据可按,下,下式计,算,算并填,入,入：,A,j,的产量=,T,j,销量=,，B,j,的销量=,+b,j,(2),用,用表上,作,作业法,进,进行求,解,解,2)对所有中转站T,j,的产量和销量定为相等，设定为,19,例26,（,（P61）已,知,知甲、,乙,乙两处,分,分别有100,吨,吨和85吨同,种,种物质,外,外运，A、B,、,、C三,处,处各需,物,物质55，60，70（吨,）,），物,质,质可以,直,直接运,到,到目的,地,地，也,可,可以经,某,某些中,转,转点转,运,运，已,知,知各处,之,之间的,距,距离如,下,下表所,示,示，试,确,确定一,个,个最优,的,的调运,方,方案。,从 到,甲,乙,甲,乙,0,10,12,0,从 到,A,B,C,甲,乙,10,15,14,12,12,18,从 到,A,B,C,A,B,C,0,10,8,14,0,12,11,4,0,从 到,甲,乙,A,B,C,产量,甲,乙,A,B,C,0,10,M,M,M,12,0,M,M,M,10,15,0,10,8,14,12,14,0,12,12,18,11,4,0,285,270,185,185,185,销量,185,185,240,245,255,再用表,上,上作业,法,法进行,求,求解。,20,2.7,线,线性目,标,标规划,及,及其解,法,法,前面的,线,线性规,划,划问题,都,都是处,理,理单个,目,目标的,情,情况，,但,但是在,现,现实世,界,界中有,许,许多问,题,题具有,多,多个目,标,标，这,些,些目标,的,的重要,性,性各不,相,相同，,往,往往有,不,不同的,量,量纲，,有,有的目,标,标相互,依,依赖，,例,例如决,策,策者既,希,希望实,现,现利润,最,最大，,又,又希望,实,实现产,值,值最大,；,；有的,相,相互抵,触,触，如,决,决策者,既,既希望,充,充分利,用,用资源,，,，又不,希,希望超,越,越资源,限,限量。,而,而决策,者,者希望,在,在某些,限,限制条,件,件下，,依,依次实,现,现这些,目,目标。,这,这就是,目,目标规,划,划所要,解,解决的,问,问题。,当,当所有,的,的目标,函,函数和,约,约束条,件,件都是,线,线性时,，,，我们,称,称其为,线,线性目,标,标规划,问,问题。,在,在这里,我,我们主,要,要讨论,线,线性目,标,标规划,问,问题。,1、目,标,标规划,模,模型的,建,建立,21,引例：,对于生产计划问题：,甲 乙 资源限额,材料 2 3 24,工时 3 2 26,单位利润 4 3,现在工厂领,导,导要考虑市,场,场等一系列,其,其他因素，,提,提出如下目,标,标：,（1）根据,市,市场信息，,甲,甲产品的销,量,量有下降的,趋,趋势，而乙,产,产品的销量,有,有上升的趋,势,势，故考虑,乙,乙产品的产,量,量应大于甲,产,产品的产量,。,。,（2）尽可,能,能充分利用,工,工时，不希,望,望加班。,（3）应尽,可,可能达到并,超,超过计划利,润,润30元。,现在的问题,是,是：在原材,料,料不能超计,划,划使用的前,提,提下，如何,安,安排生产才,能,能使上述目,标,标依次实现,？,？,22,解：（1）,决,决策变量：,仍,仍设每天生,产,产甲、乙两,种,种产品各为x,1,和x,2,偏差变量：,对,对于每一目,标,标，我们引,进,进正、负偏,差,差变量。,如对于目标1，设d,1,-,表示乙产品,的,的产量低于,甲,甲产品产量,的,的数，d,1,+,表示乙产品,的,的产量高于,甲,甲产品产量,的,的数。称它,们,们分别为产,量,量比较的负,偏,偏差变量和,正,正偏差变量,。,。则对于目,标,标1，可将,它,它表示为等,式,式约束的形,式,式,-x,1,+x,2,+ d,1,-,- d,1,+,=0(目标约,束,束),同样设d,2,-,和d,2,+,分别表示安,排,排生产时，,低,低于可利用,工,工时和高于,可,可利用工时,，,，即加班工,时,时的偏差变,量,量，则对目,标,标2，有,-3x,1,+2x,2,+ d,2,-,-d,2,+,=26,对于目标3,，,，设d,3,-,和d,3,+,分别表示安,排,排生产时，,低,低于计划利,润,润30元和,高,高于计划利,润,润30元的,偏,偏差变量，,有,有：,23,4x,1,+3x,2,+ d,3,-,-d,3,+,=30,（2）约束,条,条件：有资,源,源约束和目,标,标约束,资源约束：2x,1,+3x,2,24,目标约束：,为,为上述各目,标,标中得出的,约,约束,（3）目标,函,函数：三个,目,目标依次为,：,：,minZ,1,=d,1,-,，minZ,2,=d,2,+,+d,2,-,，minZ,3,=d,3,-,因而该问题的数学模型可表述如下：,minZ,1,=d,1,-,，minZ,2,=d,2,+,+d,2,-,，minZ,3,=d,3,-,2x,1,+3x,2,24,st -x,1,+x,2,+ d,1,-,- d,1,+,=0,-3x,1,+2x,2,+ d,2,-,-d,2,+,=26,4x,1,+3x,2,+ d,3,-,-d,3,+,=30,24,例20（提,级,级加新问题,）,） 某公司,的,的员工工资,有,有四级，根,据,据公司的业,务,务发展情况,，,，准备招收,部,部分新员工,，,，并将部分,员,员工的工资,提,提升一级。,该,该公司的员,工,工工资及提,级,级前后的编,制,制表如下，,其,其中提级后,编,编制是计划,编,编制，允许,有,有变化，其,中,中1级员工,中,中有8%要,退,退休。公司,领,领导的目标,如,如下：,（1）提级,后,后在职员工,的,的工资总额,不,不超过550千元；,（2）各级,员,员工不要超,过,过定编人数,；,；,（3）为调,动,动积极性，,各,各级员工的,升,升级面不少,于,于现有人数,的,的18%；,（4）总提,级,级面不大于20%，但,尽,尽可能多提,；,；,（5）4级,不,不足编制人,数,数可录用新,工,工人。,25,问：应如何,拟,拟定一具满,意,意的方案，,才,才能接近上,述,述目标？,级别,1,2,3,4,工资（千元）,8,6,4,3,现有员工数,10,20,40,30,编制员工数,10,22,52,30,解：（1）,决,决策变量：,设,设x,1,x,2,x,3,x,4,分别表示提,升,升到1，2,，,，3级和新,录,录用的员工,数,数。,偏差变量：,为,为各目标的,正,正、负偏差,变,变量。,（2）约束,条,条件：,1）提级后在职,员,员工的工资,总,总额不超过550千元,；,；,8(10-10,8%+x,1,)+6(20-x,1,+x,2,)+4(40-x,2,+x,3,)+3(30-x,3,+x,4,)+d,1,-,-d,1,+,=550,26,2）,各级员工不,要,要超过定编,人,人数,1级有：10-10,8%+x,1,+d,2,-,-d,2,+,=10,2级有：20-x,1,+ x,2,+d,3,-,-d,3,+,=22,3级有：40-x,2,+ x,3,+d,4,-,-d,4,+,=52,4级有：30-x,3,+ x,4,+d,5,-,-d,5,+,=30,3）,各级员工的,升,升级面不少,于,于现有人数,的,的18%,对2级有：x,1,+d,6,-,-d,6,+,=22,18%,对3级有：x,2,+d,7,-,-d,7,+,=40,18%,对4级有：x,3,+d,8,-,-d,8,+,=30,18%,4）,总提级面人,数,数不大于20%，但尽,可,可能多提,x,1,+ x,2,+ x,3,+d,9,-,-d,9,+,=100,20%,27,（3）目标,函,函数：,minZ,1,=d,1,+,minZ,2,=d,2,+,+d,3,+,+ d,4,+,+ d,5,+,minZ,3,=d,6,-,+ d,7,-,+ d,8,-,minZ,4,=d,9,+,+ d,9,-,目标规划的,一,一般模型见,书,书本P48,二、目标规,划,划的解法,由于目标规,划,划有多个目,标,标，各个目,标,标又有相对,不,不同的重要,性,性，求解时,是,是首先满足,重,重要性权数,大,大的目标，,再,再满足重要,性,性权数次大,的,的目标，所,以,以并不能保,证,证所有的目,标,标都能达到,，,，所求的解,也,也不一定是,最,最优解，而,只,只能求出满,意,意解。,28,求解目标规,划,划有图解法,和,和单纯形法,，,，在这里我,们,们主要介绍,单,单纯形法。,求解目标规,划,划的单纯形,法,法与线性规,划,划的单纯形,法,法原理基本,一,一致，只是,此,此时检验数,行,行不再是一,行,行，而是变,化,化为一个检,验,验数矩阵。,例1 例20,用单纯形法求解如下线性目标规划模型,minZ,1,=d,1,-,，minZ,2,=d,2,+,+d,2,-,，minZ,3,=d,3,-,2x,1,+3x,2,24,加入松驰变量化为标准形,2x,1,+3x,2,+ x,3,=24,st -x,1,+x,2,+ d,1,-,- d,1,+,=0,-3x,1,+2x,2,+ d,2,-,-d,2,+,=26,4x,1,+3x,2,+ d,3,-,-d,3,+,=30,解：取x,3,，d,1,-,，d,2,-,，d,3,-,为基变量，,建,建立初始单,纯,纯形表,29,-1,-2,-1,1,2,3,-1,3,4,0,26,30,Z,1,Z,2,Z,3,0,0,0,-1,0,0,-1,0,0,-1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,3, 1 ,2,3,2,-1,3,4,24,0,26,30,x,3,d,1,-,d,2,-,d,3,-,d,3,+,d,2,+,d,1,+,d,3,-,d,2,-,d,1,-,x,3,x,2,x,1,b,X,B,迭代的步骤,完,完全与线性,规,规划的单纯,形,形法一样。,满意解的判,定,定：检验数,矩,矩阵的每一,列,列从上至下,第,第一个非零,元,元为负数，,则,则解为满意,解,解。迭代的,最,最优表如下,：,：,30,-2,-1,-1,-1,1,-1,0,2,0,Z,1,Z,2,Z,3,1,0,0,0,0,0,-1,0,6/5,-2/5,-1,3/5,-1,0,0,0,0,0,1,0,-6/5,2/5,1,-3/5,7/5,1/5,-1,1/5,0,1,0,0,0,0,0,1,18/5,24/5,2,24/5,d,3,+,x,2,d,2,-,x,1,d,3,+,d,2,+,d,1,+,d,3,-,d,2,-,d,1,-,x,3,x,2,x,1,b,X,B,因而满意解,为,为：x,1,=24/5,，,，x,2,=24/5,，,，d,2,-,=2，d,3,+,=18/5,其中第一、,三,三目标已达,到,到最优，第,二,二个目标未,达,达最优。,目标利润Z=4x,1,+3x,2,=168/5,31,2.8,评价相对有,效,效性的DEA模型,DEA模型,（,（也称数据,包,包络分析）,最,最早由美国,运,运筹学家A.Charnes等人于1978年,提,提出，在中,国,国最早由中,国,国人民大学,的,的魏权龄教,授,授于1985向国内介,绍,绍。,DEA是对,其,其决策单元,（,（同类型的,企,企业或部门,）,）的投入规,模,模、技术有,效,效性作出评,价,价，即对各,同,同类型的企,业,业投入一定,数,数量的资金,、,、劳动力等,资,资源后，其,产,产出的效益,（,（经济效益,和,和社会效益,）,）作一个相,对,对有效性评,价,价。,例如：区域,可,可持续发展,的,的DEA评,价,价、企业营,销,销效果的DEA评价、,企,企业竞争能,力,力的DEA,评,评价等。,为了说明DEA模型的,建,建模思路，,我,我们看下面,的,的例子：,32,例1：,某,某公司有,甲,甲、乙、丙,三,三个企业，,为,为评价这几,个,个企业的生,产,产效率，收,集,集到反映其,投,投入（固定,资,资产年净值x,1,、流动资金x,2,、职工人数x,3,）和产出（,总,总产值y,1,、利税总额y,2,）的有关数,据,据如下表,企业,指标,甲,乙,丙,x,1,（万元）,4,15,27,x,2,（万元）,15,4,5,x,3,（万元）,8,2,5,y,1,（万元）,60,22,24,y,2,（万元）,12,6,8,由于投入指,标,标和产出指,标,标都不止一,个,个，故通常,采,采用加权的,办,办法来综合,投,投入指标值,和,和产出指标,值,值。,33,对于第一个,企,企业，产出,综,综合值为60u,1,+12u,2,投入综合,值,值4v,1,+15v,2,+8v,3，,其中u,1,u,2,v,1,v,2,v,3,分别为产出,与,与投入的权,重,重系数。,我们定义第,一,一个企业的,生,生产效率为,：,：总产出与总,投,投入的比,即,类似，可知,第,第二、第三,个,个企业的生,产,产效率分别,为,为：,34,我们限定,所,所有的h,j,值不超过1，即,，,，这意,味,味着，若,第,第k个企,业,业h,k,=1，则,该,该企业相,对,对于其他,企,企业来说,生,生产率最,高,高，或者,说,说这一生,产,产系统是,相,相对有效,的,的，若h,k,1，那,么,么该企业,相,相对于其,他,他企业来,说,说，生产,效,效率还有,待,待于提高,，,，或者说,这,这一生产,系,系统还不,是,是有效的,。,。,即,max,因此，建,立,立第一个,企,企业的生,产,产效率最,高,高的优化,模,模型如下,：,：,这是一个,分,分式规划,，,，需要将,它,它化为线,性,性规划才,能,能求解。,35,设,则此分式,规,规划可化,为,为如下的,线,线性规划,其对偶问,题,题为,max,36,设v,i,为第i个指标x,i,的权重，u,r,为第r个产出y,r,指标的权重，,则第j个企业投入的综合值为 ，产出的综合值为,其生产效率定义为:,于是问题实际上是确定一组最佳的权变量v,1,v,2,v,3,和u,1,u,2,，使第j个企业的效率值h,j,最大。这个最大的效率评价值是该企业相对于其他企业来说不可能更高的相对效率评价值。,我们限定,所,所有的h,j,值(j=1,2,3)不超,过,过1，即maxh,j,1。这,意,意味着，,若,若第k个,企,企业h,k,=1，则,该,该企业相,对,对于其他,企,企业来说,生,生产率最,高,高，或者,说,说这一系,统,统是相对,而,而言有效,的,的；若h,k,1，那,么,么该企业,相,相对于其,他,他企业来,说,说，生产,率,率还有待,于,于提高，,或,或者说这,一,一生产系,统,统还不是,有,有效的。,37,根据上述,分,分析，可,以,以建立确,定,定任何一,个,个企业（,如,如第3,个,个企业即,丙,丙企业）,的,的相对生,产,产率最优,化,化模型如,下,下：,1、评价,决,决策单元,技,技术和规,模,模综合效,率,率的C,2,R模型,设有n个,同,同类型的,企,企业（也,称,称决策单,元,元），对,于,于每个企,业,业都有m,种,种类型的,“,“输入”,（,（表示该,单,单元对“,资,资源”的,消,消耗）以,及,及p种类,型,型的“输,出,出”（表,示,示该单元,在,在消耗了,“,“资源”,之,之后的产,出,出）。,这n个企,业,业及其输,入,入-输出,关,关系如下,：,：,38,:,:,y,1n,y,2n,:,y,pn,y,1j,y,2j,:,y,pj,:,y,12,y,22,:,y,p2,y,11,y,21,:,y,p1,u,1,u,2,:,u,p,1,2,:,p,输,出,x,1n,x,2n,:,x,mn,x,1j,x,2j,:,x,mj,:,x,12,x,22,:,x,m2,x,11,x,21,:,x,m1,v,1,v,2,:,v,m,1,2,:,m,输,入,n,j,2,1,部门,指标 权数,每个决策,单,单元的效,率,率评价指,数,数为：,j=1,2,n,39,而第j,0,个决策单,元,元的相对,效,效率优化,评,评价模型,为,为：,上述模型,中,中x,ij,y,rj,为已知数,（,（可由历,史,史资料或,预,预测数据,得,得到），v,i,u,r,为变量。,模,模型的含,义,义是以权,系,系数v,i,u,r,为变量，,以,以所有决,策,策单元的,效,效率指标h,j,为约束，,以,以第j,0,个决策单,元,元的效率,指,指数为目,标,标。即评,价,价第j,0,个决策单,元,元的生产,效,效率是否,有,有效，是,相,相对于其,他,他所有决,策,策单元而,言,言的。,s.t.,v,i,u,r,0, i=1,2,m; r=1,2,p,（1）,40,这是一个,分,分式规划,模,模型，我,们,们必须将,它,它化为线,性,性规划模,型,型才能求,解,解。为此,，,，令,则模型（1）转化,为,为：,（2）,41,其对偶问,题,题为：,（3）,写成向量,形,形式有：,s.t.,无约束,（4）,min,42,设问题（4）的最,优,优解为,*,，s,*-,s,*+,*,，则有如,下,下结论：,（1）若,*,=1，则DMU,j0,为弱DEA有效（总体）。,（2）若,*,=1，且s,*-,=0,s,*+,=0，则DMU,j0,为DEA有效（总体）,（3）令,0,=,*,x,0,- s,*-,0,=y,0,- s,*+,则为在有效前沿面上的投影，相对于原来的n个DMU是有效（总体）的。,（4）若存在,j,*,(j=1,2,m),使 =1成立，则DMU,j0,为规模效益不变；若不存在,j,*,(j=1,2,m)，使 =1成立，则 1,DMU,j0,为规模效益递减。,43,评价第j,0,决策单元DMU纯,技,技术效率C,2,GS,2,模型为：,min,s.t.,j=1,2,n,无约束,（5）,该模型计,算,算出的DMU效率,是,是纯技术,效,效率，反,映,映DMU,的,的纯技术,效,效率状况,，,，称为纯,技,技术效率,。,。设问题,（,（2）的,最,最优解为,*,，s,*-,s,*+,*,，则有如,下,下对结论,：,：,44,（1）若,*,=1，则DMU,j0,为弱DEA有效（,纯,纯技术）,。,。,（2）若,*,=1，且s,*-,=0,s,*+,=0，则DMU,j0,为DEA,有,有效（纯,技,技术）。,评价第j,0,决策单元DMU纯,规,规模效率,模,模型为：,（6）,根据DEA的理论,，,，总体效,率,率,*,、纯技术,效,效率,*,、纯规模,效,效率s,*,三个参数,之,之间存在,（,（6）式,所,所述的关,系,系，由（6）可直,接,接计算DMU的纯,规,规模效率,。,。,45,P63例28,以,以1997年全部,独,独立核算,企,企业为对,象,象,对安,徽,徽、江西,、,、湖南和,湖,湖北四省,进,进行生产,水,水平的比,较,较。投入,要,要素取固,定,定资产净,值,值年平均,余,余额(亿,元,元),流,动,动资金年,平,平均余额,及,及从业人,员,员(万人),产出,要,要素取总,产,产值(亿,元,元)和利,税,税总额(,亿,亿元).,安徽,江西,湖南,湖北,固定资产,932.66,583.08,936.84,1306.56,流动资金,980.45,581.64,849.31,1444.30,从业人员,401.8,294.2,443.20,461.00,利税总额,179.29,49.76,144.20,181.41,总产值,2196.09,930.22,1659.04,2662.21,全要素相对生产率,(即DEA评价值),1.000,0.7140,0.9285,1.000,排序,1,3,2,1,46,1. 建,立,立评价湖,南,南省的DEA模型,如,如下,求解结果,为,为:,调整方案,为,为:,输入调整前,输入调整后,输出调整前,输出调整后,936.84,936.84*0.9285-119.71,=750.15,144.20,144.20,849.31,849.31*0.9285=788.58,1659.04,1659.04+107.24=1766.28,443.20,443.2*0.9285-88.17=323.34,47,第二章,整,整数线,性,性规划问,题,题及其解,法,法,在上一章,讨,讨论的LP问题中,对决策,变,变量只限,于,于不能取,负,负值的连,续,续型数值,即可以,是,是正分数,或,或正小数,。,。然而在,许,许多经济,管,管理的实,际,际问题中,，,，决策变,量,量只有非,负,负整数才,有,有实际意,义,义。对求,整,整数最优,解,解的问题,，,，称为整,数,数规划(IntegerProgramming)(简记为IP)。,又,又称约束,条,条件和函,数,数均为线,性,性的IP,为,为整数线,性,性规划(IntegerLinear Programming)(,简,简记为ILP)。,根据变量取整,数,数的情况,将,整,整数规划分为,：,（1）纯整数,规,规划，所有变,量,量都取整数.,（2）混合整,数,数规划，一部,分,分变量取整数,一部分变量,取,取实数,（3）0-1,整,整数规划 ,所,所有变量均取0或1,求解整数规划,常,常用的算法有,分,分枝定界法、,割,割平面法,求,解,解0-1的还,有,有隐枚举法、,匈,匈牙利法。,48,一、整数线性,规,规划模型的建,立,立,例题2 P72 某单位,有,有5个拟选择,的,的投资项目，,其,其所需投资额,与,与期望收益如,下,下表。由于各,项,项目之间有一,定,定联系，A、C、E之间必,须,须选择一项且,仅,仅需选择一项,；,；B和D之间,需,需选择也仅需,选,选择一项；又,由,由于C和D两,项,项目密切相关,，,，C的实施必,须,须以D的实施,为,为前提条件，,该,该单位共筹集,资,资金15万元,，,，问应该选择,哪,哪些项目投资,，,，使期望收益,最,最大？,项目,所需投资额（万元）,期望收益（万元）,A,6,10,B,4,8,C,2,7,D,4,6,E,5,9,49,解：决策变量：设,目标函数：期,望,望收益最大,约束条件：投,资,资额限制条件6x,1,+4x,2,+2x,3,+4x,4,+5x,5,15,项目A、C、E之间必须且,只,只需选择一项,：,：x,1,+x,3,+x,5,=1,项目C的实施,要,要以项目D的,实,实施为前提条,件,件： x,3,x,4,项目B、D之,间,间必须且只需,选,选择一项：x,2,+x,4,=1,归纳起来，其,数,数学模型为：,50,由此，ILP,问,问题数学模型,的,的一般形式为,：,：求一组变量X,1,X,2,X,n,，使,此例还表明，,利,利用0-1变,量,量处理一类“,可,可供选择条件,”,”的问题非常,简,简明方便。下,面,面再进一步分,别,别说明对0-1变量的应用,。,。,假定现有m种,资,资源对可供选,择,择的n个项目,进,进行投资的数,学,学模型为：求,一,一组决策变量X,1,X,2,X,n,，使,（3.1）,（3.2）,（3.3）,51,1.对可供项,目,目的选择,（1）如果在可供选择的前k(k,n),个项目中，必须且只能选择一项，则在(3.2)中加入新的约束条件：,（2）如果可供选择的k(k,n),个项目是相互排斥的，则在(3.2)中加入新的约束条件：,同时它还表示,在,在第k个项目,中,中至多只能选,择,择一项投资。,（3）如果在可供选择的k(k,n),个项目中，至少应选择一项投资，则在(3.2)中加入新的约束条件：,52,（4）如果项,目,目j的投资必,须,须以项目i的,投,投资为前提，,则,则可在(3.2)中加入新,的,的约束条件：,X,j,X,i,（5）如果项,目,目i与项目j,要,要么同时被选,中,中，要么同时,不,不被选中，则,在,在(3.2),中,中加入新的约,束,束条件：,X,j,=X,i,(i,j),2.对可供资,源,源的选择,（1）如果对,第,第r种资源b,r,与第t种资源b,t,的投资是相互,排,排斥的，即只,允,允许对资源b,r,与b,t,中的一种进行,投,投资，则可将(3.2)的,第,第r个和第t,个,个约束条件改,写,写为：,53,其中y为新引,进,进的0-1变,量,量，M为充分,大,大正数。易见,，,，当y=0时,，,，式就是原,来,来的第r个约,束,束条件，具有,约,约束作用。此,时,时对式而言,，,，无论X,j,为何值都成,立,立，毫无约,束,束作用，这,就,就使问题仅,允,允许第r种,资,资源进行投,资,资。当y=1时，式,对,对X,j,起了约束作,用,用，而式,成,成了多余的,条,条件。到底,是,是满足还,是,是，则视,问,问题在求出,最,最优解后，y为0还是1而定。,54,（2）如果,问,问题是要求,在,在前m个约,束,束条件中至,少,少满足k(1km)个，则可,将,将(3.2)中的原约,束,束条件修改,为,为：,其中M为充,分,分大的正数,，,，k为整数,。,。,整数规划问,题,题的建模与,线,线性规划问,题,题的建模基,本,本一致，仍,按,按以下3个,步,步骤进行：,（1）确定,决,决策变量；,（2）确定,目,目标函数；,（3）确定,约,约束条件。,但0-1规,划,划要注意变,量,量的选择和,约,约束条件的,选,选择。,55,例8（P91）（仓库,选,选用问题）,某决策者拟,在,在n个仓库,中,中决定租用,其,其中的几个,，,，以满足m,个,个销售点对,货,货物的需要,。,。每个销售,点,点的需要量b,j,(j=1,2,m),必,必须从租用,的,的仓库中得,到,到满足，且,只,只能从租用,的,的仓库得到,满,满足。而对,租,租用的仓库,必,必须支付固,定,定的运营费,（,（如租金、,管,管理费等）,，,，同时，还,应,应决定从租,用,用的哪个仓,库,库中运多少,货,货物到销售,点,点处，以使,总,总的费用为,最,最小。,解：分析，,该,该问题是由,一,一个仓库选,用,用和一个运,输,输问题综合,而,而成。设,g,i,表示租用仓,库,库i的固定,运,运营费（即,固,固定成本）,；,；,d,i,表示仓库i,的,的允许容量,；,；,C,ij,表示从仓库i运送货物,到,到销售点j,处,处的单位费,用,用（即可变,成,成本）,56,（1）决策,变,变量：x,ij,表示从租用,的,的仓库i运,送,送给销售点j的货物量,；,；,（2）约束,条,条件：此处,的,的约束条件,只,只有运输问,题,题的产量约,束,束和销量约,束,束，表示为,（3）目标,函,函数：总费,用,用包括两部,分,分，一是仓,库,库租用费用,，,，二是运输,费,费用，因此,总,总费用表示,为,为,57,求解ILP,问,问题方法的,思,思考：,1）“舍入,取,取整”法：,即,即先不考虑,整,整数性约束,，,，而去求解,其,其相应的LP问题（称,为,为松驰问题,）,），然后将,得,得到的非整,数,数最优解用,“,“舍入取整,”,”的方法。,这,这样能否得,到,到整数最优,解,解？否！这,是,是因为“舍,入,入取整”的,解,解一般不是,原,原问题的最,优,优解，甚至,是,是非可行解,。,。,但,在,在,处,处,理,理,个,个,别,别,实,实,际,际,问,问,题,题,时,时,，,，,如,如,果,果,允,允,许,许,目,目,标,标,函,函,数,数,值,值,在,在,某,某,一,一,误,误,差,差,范,范,围,围,内,内,，,，,有,有,时,时,也,也,可,可,采,采,用,用,“,“,舍,舍,入,入,取,取,整,整,”,”,得,得,到,到,的,的,整,整,数,数,可,可,行,行,解,解,作,作,为,为,原,原,问,问,题,题,整,整,数,数,最,最,优,优,解,解,的,的,近,近,似,似,。,。,这,这,样,样,可,可,节,节,省,省,求,求,解,解,的,的,人,人,力,力,、,、,物,物,力,力,和,和,财,财,力,力,。,。,二,、,、,整,整,数,数,线,线,性,性,规,规,划,划,模,模,型,型,的,的,求,求,解,解,58,严,格,格,地,地,说,说,，,，IP,是,是,个,个,非,非,线,线,性,性,规,规,划,划,问,问,题,题,。,。,这,这,是,是,因,因,为,为IP,的,的,可,可,行,行,解,解,集,集,是,是,由,由,一,一,些,些,离,离,散,散,的,的,非,非,负,负,整,整,数,数,所,所,组,组,成,成,，,，,不,不,是,是,一,一,个,个,凸,凸,集,集,。,。,迄,迄,今,今,为,为,止,止,，,，,求,求,解,解IP,问,问,题,题,尚,尚,无,无,统,统,一,一,的,的,有,有,效,效,算,算,法,法,。,。,但,但,常,常,用,用,的,的,有,有,求,求,解,解,一,一,般,般,整,整,数,数,规,规,划,划,的,的,分,分,枝,枝,定,定,界,界,法,法,、,、,割,割,平,平,面,面,法,法,和,和,求,求,解,解0-1,规,规,划,划,的,的,隐,隐,枚,枚,举,举,法,法,。,。,在,在,这,这,里,里,我,我,们,们,只,只,介,介,绍,绍,分,分,枝,枝,定,定,界,界,法,法,和,和,隐,隐,枚,枚,举,举,法,法,。,。,1,、,、,整,整,数,数,规,规,划,划,的,的,分,分,枝,枝,定,定,界,界,法,法,（1,）,）,分,分,枝,枝,定,定,界,界,法,法,的,的,基,基,本,本,思,思,想,想P76,（2,）,）,分,分,枝,枝,定,定,界,界,法,法,的,的,求,求,解,解,步,步,骤,骤P76,例,求,求,解,解,下,下,列,列,整,整,数,数,规,规,划,划,问,问,题,题,：,：,59,解,：,：,首,首,先,先,不,不,考,考,虑,虑,整,整,数,数,约,约,束,束,，,，,相,相,应,应,的,的,问,问,题,题,称,称,为,为,原,原,问,问,题,题,的,的,松,松,驰,驰,问,问,题,题,松驰问题（0）,用,单,单,纯,纯,形,形,法,法,求,求,得,得,其,其,最,最,优,优,解,解,为,为x,1,=2.5,，,，x,2,=2.5,，,，z=87.5,具,体,体,求,求,解,解,过,过,程,程,见,见P76-78,，,，,其,其,求,求,解,解,框,框,图,图,如,如,下,下,：,：,60,问题（0）,x,1,=2.5，x,2,=2.5 z=87.5,问题（1）,x,1,=2，x,2,=2.67 z=83.3,问题（2）,x,1,=3，x,2,=1.75 z=80,问题（3）,x,1,=2，x,2,=2 z=70,问题（4）,x,1,=1，x,2,=3 z=75,问题（0）,x,1,=3.5，x,2,=1 z=72.5,问题（6）,无可行解