运输问题与指派问题讲义

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,Chapter,5,运,运输,问,问题,与,与指,派,派问,题,题,Transportationand,AssignmentProblem,1,运,输,输,模,模,型,型,The,Transportation,model,2,运,输,输,问,问,题,题,网,网,络,络,模,模,型,型,TransportationNetwork,3,应,用,用,实,实,例,例,4,指,派,派,问,问,题,题,AssignmentProblem,物,流,流,中,中,的,的,一,一,个,个,普,普,遍,遍,问,问,题,题,是,是,如,如,何,何,以,以,尽,尽,可,可,能,能,小,小,的,的,成,成,本,本,把,把,货,货,物,物,从,从,一,一,系,系,列,列,起,起,始,始,地,地,（,（sources,）,）,（,（,如,如,工,工,厂,厂,、,、,仓,仓,库,库,）,）,运,运,输,输,到,到,一,一,系,系,列,列,终,终,点,点,地,地,（,（destinations,）,）,（,（,如,如,仓,仓,库,库,、,、,顾,顾,客,客,）,）,运,输,输,问,问,题,题,TheTransportationProblem,想想看！,如,何,何,分,分,析,析,这,这,类,类,问,问,题,题,1,运,运,输,输,问,问,题,题,模,模,型,型,实,实,例,例,TheP&TCompany,分,分,配,配,网,网,络,络,P189,P&T,公,公,司,司,是,是,一,一,家,家,由,由,家,家,族,族,经,经,营,营,的,的,小,小,公,公,司,司,。,。,它,它,收,收,购,购,生,生,菜,菜,并,并,在,在,食,食,品,品,罐,罐,头,头,厂,厂,中,中,把,把,它,它,们,们,加,加,工,工,成,成,为,为,罐,罐,头,头,，,，,然,然,后,后,再,再,把,把,这,这,些,些,罐,罐,头,头,食,食,品,品,分,分,销,销,到,到,各,各,地,地,卖,卖,出,出,去,去,。,。,豌,豌,豆,豆,罐,罐,头,头,在,在,三,三,个,个,食,食,品,品,罐,罐,头,头,厂,厂,（,（,靠,靠,近,近,华,华,盛,盛,顿,顿,的,的,贝,贝,林,林,翰,翰,；,；,俄,俄,勒,勒,冈,冈,州,州,的,的,尤,尤,基,基,尼,尼,；,；,明,明,尼,尼,苏,苏,达,达,州,州,的,的,艾,艾,尔,尔,贝,贝,李,李,）,）,加,加,工,工,，,，,然,然,后,后,用,用,卡,卡,车,车,把,把,它,它,们,们,运,运,送,送,到,到,美,美,国,国,西,西,部,部,的,的,四,四,个,个,分,分,销,销,仓,仓,库,库(,加,加,利,利,福,福,尼,尼,亚,亚,州,州,的,的,萨,萨,克,克,拉,拉,门,门,托,托,；,；,犹,犹,他,他,州,州,盐,盐,湖,湖,城,城,；,；,南,南,达,达,科,科,他,他,州,州,赖,赖,皮,皮,特,特,城,城,；,；,新,新,墨,墨,西,西,哥,哥,州,州,澳,澳,尔,尔,巴,巴,古,古),P&TCompanyDistributionProblem,贝,林,林,翰,翰,罐,罐,头,头,工,工,厂,厂,尤,基,基,尼,尼,工,厂,厂,艾,尔,尔,贝,贝,.,李,工,工,厂,厂,萨,克,克,拉,拉,门,门,托,托,仓,仓,库,库,奥,尔,尔,巴,巴,古,古,盐,湖,湖,城,城,P&T,公,公,司,司,问,问,题,题,中,中,的,的,仓,仓,库,库,和,和,加,加,工,工,厂,厂,位,位,置,置,图,图,赖,皮,皮,特,特,澳,尔,尔,巴,巴,古,古,相,关,关,数,数,据,据ShippingData,Cannery,Output产量,Warehouse,分配量Allocation,Bellingham,75 truckloads,Sacramento,80 truckloads,Eugene,125 truckloads,Salt Lake City,65 truckloads,Albert Lea,100 truckloads,Rapid City,70 truckloads,Total,300 truckloads,Albuquerque,85 truckloads,Total,300 truckloads,运输成本 per Truckload,Warehouse仓库,From,To,萨克拉门托,盐湖城,赖皮特,澳尔巴古,罐头厂,贝林翰,$464,$513,$654,$867,尤基尼,352,416,690,791,艾尔贝.李,995,682,388,685,总,产,产,量,量=,总,总,的,的,需,需,求,求,量,量=300,车,车,，,，,产,产,销,销,平,平,衡,衡,线,性,性,规,规,划,划,模,模,型,型,设Let,x,ij,=,从罐头,厂,厂,i,运往仓,库,库,j,卡车数,thenumber of truckloadstoshipfrom cannery,i,towarehouse,j,(,i,=1,2,3,分别表,示,示贝林,翰,翰罐头,厂,厂，尤,基,基尼罐,头,头厂，,艾,艾尔贝.李罐,头,头厂；,j,=1,2,3,4,分别表,示,示萨克,拉,拉门托,仓,仓库，,盐,盐湖城,仓,仓库，,赖,赖皮特,仓,仓库和,澳,澳尔巴,古,古仓库)则线性,规,规划模,型,型为,MinimizeCost=464,x,11,+513,x,12,+654,x,13,+867,x,14,+352,x,21,+416,x,22,+690,x,23,+791,x,24,+995,x,31,+682,x,32,+388,x,33,+685,x,34,subject toCannery 1:,x,11,+,x,12,+,x,13,+,x,14,=75Cannery 2:,x,21,+,x,22,+,x,23,+,x,24,=125Cannery3:,x,31,+,x,32,+,x,33,+,x,34,=100Warehouse 1:,x,11,+,x,21,+,x,31,=80Warehouse2:,x,12,+,x,22,+,x,32,=65Warehouse3:,x,13,+,x,23,+,x,33,=70Warehouse4:,x,14,+,x,24,+,x,34,=85,x,ij,0(,i,=1,2,3;,j,=1,2,3,4),TransportationProblem Example,运输问,题,题举例,实际举例,作为一个运,输,输问题的P&T公司电,子,子表格描述,运输问题一,般,般模型,general The,Transportationproblem,model,Terminology术语 for aTransportationProblem,P&T Company Problem,Truckloads of canned peas,Canneries,Warehouses,Output from a cannery,Allocation to a warehouse,Shipping cost per truckload from a cannery to a warehouse,General Model,Units of a commodity商品单位,Sources运出地,Destinations目的地,Supply from a source运出量,Demand at a destination需求量,Cost per unit distributed from a source to a destination单位成本,一般模型表,示,示：,设,A,1,、A,2,、A,m,表示m个产,地,地；,B,1,、B,2,、B,n,表示n个销,地,地；,a,i,表示产地,A,i,的产量；,b,j,表示销地,B,j,的销量,；,c,ij,表示把物资,从,从产地,A,i,运往销地,B,j,的单位运价,设,x,ij,为从产地A,i,运往销地,B,j,的运输量，,得,得到下列一,般,般运输量问,题,题的模型：,mn,Minf=,c,ij,x,ij,i=1,j,=1,s.t.,x,ij,=,a,i,i=1,2,m,x,ij,=,b,j,j=1,2,n,x,ij,0,(i=1,2,m;j=1,2,n),运输问题的,特,特征,Characteristicsof Transportation Problems,运输问题的,假,假定数学模,型,型为：,1、,需求假设：,每一个出发,地,地都有一个,固,固定的供应,量,量，所有的,供,供应量都必,须,须配送到目,的,的地。与之,相,相类似，每,一,一个目的地,都,都有一个固,定,定的需求量,，,，整个需求,量,量都必须由,出,出发地满足,2、,可行解假定,：当且仅当,供,供应量的,总和,等于需求量,的,的总和时，,运,运输问题才,有,有可行解，,且,且有最优解,3、,成本假设：,从任何一个,出,出发地到任,何,何一个目的,地,地的货物配,送,送成本和所,配,配送的数量,成,成线性比例,关,关系，因此,这,这个成本就,等,等于配送的,单,单位成本乘,以,以所配送的,数,数量,4、,整数解性质,：,：,当供应量和,需,需求量都是,整,整数，必存,在,在决策变量,均,均为整数的,最,最优解,例1、,某公司从两,个,个产地A,1,、A,2,将物品运往,三,三个销地B,1,、B,2,、B,3,，各产地的,产,产量、各销,地,地的销量和,各,各产地运往,各,各销地每件,物,物品的运费,如,如下表所示,，,，问：应如,何,何调运可使,总,总运输费用,最,最小？,解：,产销平衡问,题,题：总产,量,量=总,销,销量,设,x,ij,为从产地A,i,运往销地B,j,的运输量,，,，得到下,列,列运输量,表,表：,运 输,模,模 型,销地,产地,B,1,B,2,B,3,产量,A,1,x,11,x,12,x,13,200,A,2,x,21,x,22,x,23,300,销量,150,150,200,销地,产地,B,1,B,2,B,3,产量,a,i,A,1,6,4,6,200,A,2,6,5,5,300,销量,b,j,150,150,200,数学模型,为,为,Min,f,=6,x,11,+4,x,12,+6,x,13,+6,x,21,+5,x,22,+5,x,23,s.t.,x,11,+,x,12,+,x,13,=200,x,21,+,x,22,+,x,23,=300,x,11,+,x,21,=150,x,12,+,x,22,=150,x,13,+,x,23,=200,x,ij,0(i=1,、,、2；j=1,、,、2、3,）,）,3,Transportation Network 运,输,输问题的,网,网络表示,销地,产地,B,1,B,2,B,3,B,3,供应量,a,i,A,1,6,7,5,3,25,A,2,8,4,2,7,10,A,2,5,9,10,16,15,需求量,b,j,13,21,9,7,Transportation Network 运,输,输问题的,网,网络表示,每一个节,点,点建立一,个,个约束方,程,程，目标,函,函数为每,一,一条箭线,上,上的决策,变,变量,x,i j,乘以单位,运,运价,c,i j,之和,2,3,2,1,3,4,1,a,2,=10,a,3,=15,b,1,=13,b,2,=21,b,3,=9,b,4,=7,a,1,=25,供应量,sources,运价,需求量,Destinations,需求地,6,7,5,3,8,4,2,7,5,9,10,6,x,11,x,12,x,13,x,14,A,1,A,2,A,3,B,1,B,2,B,3,B,4,supplies,demands,供,应,应,地,地,约,约,束,束,需,求,求,地,地,约,约,束,束,LPMo