运输问题运筹学

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第五章,运输问题,一、运输问题,1,，运输问题的模型表示,2,，运输问题的求解方法,3,，各种运输问题变体,二、转运问题,三、指派问题,第五章,运输、转运和指派问题,*,物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（,sources,）（如工厂、仓库）运输到一系列终点地（,destinations,）（如仓库、顾客）,一、运输问题,你怎么去分析这类问题呢？,想想看！,*,1,、运输问题的模型表示,*,2,3,2,1,3,4,1,s,2,=10,s,3,=15,d,1,=13,d,2,=21,d,3,=9,d,4,=7,s,1,=25,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,运输问题的网络表示,*,运输问题的表格表示,需求地,供应地,1,2,3,4,合计,1,6,7,5,3,25,2,8,4,2,7,10,3,5,9,10,6,15,合计,13,21,9,7,*,供应地约束,需求地约束,运输问题线性规划模型,*,运输问题的一般数学模型,设,从第,i,产地到第,j,销地的物资运输量为,x,ij,，则,目标函数：,约束条件：,由于产销平衡，因此有,*,实例分析：,仓库,罐头厂,一,二,三,四,合计,一,3,11,3,10,7,二,1,9,2,8,4,三,7,4,10,5,9,合计,3,6,5,6,x,11,x,12,x,13,x,14,x,21,x,22,x,23,x,24,x,34,x,31,x,32,x,33,s.t.,a,1,a,2,a,3,b,1,b,2,b,3,b,4,*,每一个出发地都有一定的,供应量（,supply,）,配送到目的地，每一个目的地都有需要从一定的,需求量（,demand,）,，接收从出发地发出的产品,需求假设,：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足,成本假设,：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成,线性比例,关系，因此这个成本就等于,配送的单位成本乘以所配送的数量,整数解性质,：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件,运输问题的特征,*,2,、运输问题的求解方法,步骤,1,，确定初始基可行解,最小元素法,就近运输，即从单位运价表中最小的运价处开始确定运输关系，以此类推，直到给出全部方案为止,2,，求各非基变量（在表格中即为空格）的检验数，判别是否达到最优。是，则停止；否则转下一步,3,，确定换入变量和换出变量，利用闭回路法对检验数为负的格进行调整，找出新的基可行解,4,，重复以上步骤，直到找到最优解,*,1,、初始,基,基可行,解,解的确,定,定,-,最小元,素,素法,从单位,运,运价表,中,中最小,的,的运价,处,处开始,确,确定运,输,输关系,，,，依此,类,类推，,直,直到给,出,出全部,方,方案,例,1,*,2,、求检,验,验数,-,闭回路,法,法,:,例,1,1,2,1,-1,10,12,注,:1),数字格,检,检验数,均,均为,0,显然该,问,问题至,此,此尚未,达,达到最,优,优解。,*,3,、调,整,整,从最小,负,负检验,数,数所对,应,应的空,格,格进行,调,调整,例,1,对由最,小,小元素,法,法得出,的,的初始,解,解进行,调,调整,调整方,法,法：,1,2,1,-1,10,12,1,）找出,具,具有负,检,检验数,的,的闭回,路,路,2,）使最,小,小负检,验,验数所,对,对应的,空,空格达,到,到最大,的,的调整,量,量,1,再按调,整,整后的,解,解由位,势,势法计,算,算空格,的,的检验,数,数,*,用计算,机,机求解,1,，线性,规,规划方,法,法,2,，,WINQSB,软件的,NET,程序,*,供应总,量,量超出,了,了需求,总,总量,供应总,量,量小于,需,需求总,量,量,一个目,的,的地同,时,时存在,着,着最小,需,需求和,最,最大需,求,求,在配送,中,中不能,使,使用特,定,定的出,发,发地,目的地,组,组合,目标是,与,与配送,量,量有关,的,的总利,润,润最大,不,不是成,本,本最小,3,、各种,运,运输问,题,题变体,*,（,1,）运输,不,不平衡,问,问题,如果,销地,产地,B1,B2,B3,产量,A1,6,4,6,300,A2,6,5,5,300,销量,150,150,200,销地,产地,B1,B2,B3,产量,A1,6,4,6,200,A2,6,5,5,300,销量,250,200,200,或者,650 500,500 600,*,产大于,销,销的运,输,输方案,可,可设为,建模,销地,产地,B1,B2,B3,产量,A1,X11,X12,X13,300,A2,X21,X22,X23,300,销量,150,150,200,*,销大于,产,产的运,输,输模型,销地,产地,B1,B2,B3,产量,A1,X11,X12,X13,200,A2,X21,X22,X23,300,销量,250,200,200,*,（,2,）有区,间,间约束,的,的需求,例：石,家,家庄北,方,方研究,院,院有三,个,个区，,即,即一区,、,、二区,、,、三区,，,，每年,分,分别需,要,要生取,暖,暖用煤,3000t,，,1000t,，,2000t,，由河,北,北临城,，,，山西,孟,孟县两,处,处煤矿,负,负责供,应,应。两,处,处煤矿,能,能供应,北,北方研,究,究院的,煤,煤的数,量,量，山,西,西孟县,为,为,4000t,，河北,临,临城为,1500t,。由于,需,需大于,供,供，经,院,院研究,平,平衡决,定,定一区,供,供应量,可,可减少,0,300t,，二区,需,需要量,应,应全部,满,满足，,三,三区供,应,应量不,少,少于,1500t,。由煤,矿,矿至北,方,方研究,院,院的单,位,位运价,(,百元,t),如下表,所,所示。,试,试求总,运,运费为,最,最低的,调,调运方,案,案。,运费,一区,二区,三区,供应量,山西盂县,1.65,1.7,1.75,4000,河北临城,1.6,1.65,1.7,1500,需求量,2700-3000,1000,1500-2000,*,运输方,案,案,运量,运费,一区,二区,三区,供应量,山西盂县,1.65,1.7,1.75,4000,河北临城,1.6,1.65,1.7,1500,需求量,2700-3000,1000,1500-2000,*,模型：,Min1.65x11+1.7x12+1.75x13+1.6x21+1.65x22+1.7x23,S.t.,x11+x12+x13=4000,x21+x22+x23=1500,x11+x21 3000,x11+x21 2700,x12+x22=1000,x13+x23 2000,x13+x23 1500,x,ij,0,*,用网络,优,优化软,件,件,运费,一区,1,一区,2,二区,三区,1,三区,2,供应量,山西盂县,1.65,1.65,1.7,1.75,1.75,4000,河北临城,1.6,1.6,1.65,1.7,1.7,1500,假想地点,M,0,M,M,0,500,需求量,2700,300,1000,1500,500,6000,6000,*,（,3,）具有,出,出发地,约,约束的,问,问题,例：设,有,有三个,化,化肥厂,供,供应四,个,个地区,的,的农用,化,化肥，,假,假定等,量,量的化,肥,肥在这,些,些地区,使,使用效,果,果相同,。,。各化,肥,肥厂年,产,产量、,各,各地区,年,年需求,量,量及从,各,各化肥,厂,厂到各,地,地区运,送,送单位,化,化肥的,运,运价如,下,下表所,示,示，试,求,求出总,的,的运费,最,最节省,的,的化肥,调,调拨方,案,案。,*,方法,1,：线性,规,规划方,法,法,*,方法,2,：用网,络,络优化,软,软件,这是一,个,个产销,不,不平衡,的,的运输,问,问题，,总,总产量,为,为,160,万吨，,四,四个地,区,区的最,低,低需求,为,为,110,万吨，,最,最高需,求,求为无,限,限，根,据,据现有,产,产量，,在,在满足,I,，,II,，,IV,三个地,区,区的最,低,低需求,量,量的前,提,提下，,第,第,IV,地区的,最,最高需,求,求改为,60,万吨，,总,总的最,高,高需求,为,为,210,万吨。,为了求,得,得平衡,，,，在产,销,销平衡,表,表上增,加,加一个,假,假想的,化,化肥厂,D,，其年,产,产量为,50,万吨。,由,由于各,地,地区的,需,需要量,包,包含两,个,个部分,，,，如地,区,区,I,其中,30,万吨是,最,最低需,求,求，必,须,须满足,，,，不能,由,由假想,的,的化肥,厂,厂,D,供给，,令,令其运,价,价为,M,；而另,一,一部分,20,万可以,不,不满足,，,，故可,以,以由假,想,想化肥,厂,厂,D,供给，,令,令其运,价,价为零,。,。,对需求,分,分两种,情,情况的,地,地区，,实,实际上,可,可按两,个,个地区,看,看待，,这,这样得,到,到下表,所,所示的,产,产销平,衡,衡与运,价,价表。,*,二、转,运,运问题,一些运,输,输问题,中,中常常,涉,涉及到,中,中间转,运,运站的,问,问题，,这,这些转,运,运在起,点,点和最,终,终目的,地,地之间,起,起到一,个,个暂时,存,存放货,物,物的作,用,用，这,些,些转运,站,站既是,起,起点同,时,时也是,目,目的地,。,。这些,问,问题的,目,目标和,运,运输问,题,题是一,样,样的：,转,转运成,本,本最小,化,化。,转运问,题,题可以,用,用线性,规,规划模,型,型来建,模,模和求,解,解，其,中,中需要,注,注意的,是,是转运,节,节点的,进,进和出,的,的量要,相,相等。,书,P104,页，例,5-2,*,*,现实生,活,活之中,，,，我们,也,也经常,遇,遇到指,派,派人员,做,做某项,工,工作的,情,情况。,指,指派问,题,题的许,多,多应用,都,都用来,帮,帮助管,理,理人员,解,解决如,何,何为一,项,项将要,开,开展进,行,行的工,作,作指派,人,人员的,问,问题。,其,其他的,一,一些应,用,用如为,一,一项任,务,务指派,机,机器、,设,设备或,者,者是工,厂,厂,三、,指,指派,问,问题（,分,分配问,题,题）,还有哪,些,些这样,的,的问题,呢,呢？,想想看！,*,指派问,题,题的形,式,式表述,:,给定了,一,一系列,所,所要完,成,成的任,务,务（,tasks,）以及,一,一系列,完,完成任,务,务的被,指,指派者,（,（,assignees,），所,需,需要解,决,决的问,题,题就是,要,要确定,出,出哪一,个,个人被,指,指派进,行,行哪一,项,项任务,？,？,指派问,题,题模型,*,例：员,工,工分配,临时工,每项任务所需要的时间,每小时,工资,文字处理 幻灯片 材料准备 记录,A,B,C,D,35 41 27 40,47 45 32 51,39 56 36 43,32 51 25 46,14,12,13,15,*,设,x,ij,1,或,0,分别表,示,示第,i,人做或,不,不做第,j,项工作，,i,j,=1,2,3,4,则其数学,模,模型为,临时工,每项任务所需要的时间,每小时,工资,文字处理,1,幻灯片,2,材料准备,3,记录,4,1 A,2 B,3 C,4 D,35 41 27 40,47 45 32 51,39 56 36 43,32 51 25 46,14(,w,1,),12(,w,