金融学院-管理运筹学-04-运输模型.ppt

管理运筹学,运输问题,第三讲,6/8/2020,3,若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求。供应节点：这些工厂，它们是运输的起点；需求节点：用户所在点，它们是运输的终点或目的地。同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。公司面临的问题：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。这类问题就是运输问题。,一、问题的模型描述,6/8/2020,4,二、运输问题数学模型,xij-供应节点i至需求节点j的运输量；ai-供应节点i的可供应量，i=1,2,m；bj-需求节点j的需求量，j=1,2,n；cij-供应节点i至需求节点j的单位运输成本。,6/8/2020,5,平衡型运输问题:,二、运输问题数学模型,模型包含变量：mn个约束方程：m+n个秩：r(A)=m+n-1,6/8/2020,6,二、运输问题数学模型,m行,n行,稀疏矩阵,x11,x12,x1n,x21,x2n,xm1,xmn,6/8/2020,7,平衡型运输问题:,三、运输问题的基本性质,1.约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。2.存在最优解3.当供应量和需求量均为整数时，存在整数最优解。4.基可行解中基变量个数为m+n-1个5.基可行解中基变量的重要特征:不含闭回路。6.任何一个非基变量与基变量含且仅含一个闭回路。,6/8/2020,8,最小元素法西北角法Vogel法,四、初始基可行解的确定,6/8/2020,9,最小元素法,4,12,4,11,2,10,3,6,8,5,9,11,6/8/2020,10,4,12,4,11,2,10,3,6,8,5,9,11,8,2,2,10,10,14,8,8,6,6,X=(0,0,10,6,8,0,2,0,0,14,0,8),6/8/2020,11,西北角法,4,12,4,11,2,10,3,6,8,5,9,11,8,8,8,6,6,4,4,8,8,14,14,X=(8,8,0,0,0,6,4,0,0,0,8,14),6/8/2020,12,Vogel法(沃格尔法),4,12,4,11,2,10,3,6,8,5,9,11,0,1,1,2,5,1,3,14,0,1,2,2,1,3,8,0,1,2,1,2,8,7,6,1,2,12,0,0,2,2,4,6/8/2020,13,1.闭回路法(CycleMethod),五、最优性检验,定义：,凡能排列成,或者,形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。,6/8/2020,14,(1)x12,x13,x33,x32,(2)x23,x13,x14,x34,x31,x21,转角点,转角点,6/8/2020,15,4,12,4,11,2,10,3,6,8,5,9,11,8,2,10,14,8,6,以最小元素法求得的初始方案为例：,1,1,2,-1,10,12,6/8/2020,16,2.对偶变量法(DualVariableMethod)/位势法,6/8/2020,17,8,7,4,2,1,3,5,7,2,4,9,6,由基变量决定位势；计算非基变量的检验数,u1=0,v3=3,u2=2,v4=-1,v2=5,u3=-1,v1=3,5,2,3,-1,7,8,6/8/2020,18,1.确定进基变量,六、基可行解的改进,选择检验数绝对值最大的非基变量为进基变量(存在多个时任选一个),2.确定离基变量,选择包含进基变量的闭回路上偶数变量中运量最小的基变量为离基变量。,6/8/2020,19,4,12,4,11,2,10,3,6,8,5,9,11,8,2,10,14,8,6,以最小元素法求得的初始方案为例：,1,1,2,-1,10,12,2,12,4,6/8/2020,20,4,12,4,11,2,10,3,6,8,5,9,11,8,14,8,以最小元素法求得的初始方案为例：,1,2,2,9,12,0,2,12,4,6/8/2020,21,8,7,4,2,1,3,5,7,2,4,9,6,P101,u1=0,v3=3,u2=2,v4=-1,v2=5,u3=-1,v1=3,5,2,3,-1,7,8,6/8/2020,22,8,7,4,2,1,3,5,7,2,4,9,6,P101,u1=0,v3=3,u2=2,v4=-1,v2=4,u3=0,v1=2,6,7,3,1,3,6,6/8/2020,23,七、非平衡问题,22,18,3,12,3,4,11,2,5,9,1,7,6,5,6/8/2020,24,七、非平衡问题,3,12,3,4,11,2,5,9,1,7,6,5,0,0,0,请同学们自我完成！,6/8/2020,25,八、运输问题的应用,由于运输问题比一般单纯型计算简单，故有些实际问题可以转化为运输问题。,6/8/2020,26,例1,单位产品的保管费用为每季度0.1，求最优生产方案？,6/8/2020,27,生产,交货,6/8/2020,28,12.0,12.1,12.2,12.3,0,M,11.0,11.1,11.2,0,M,M,11.5,11.6,0,M,12.5,M,M,0,6/8/2020,29,16,14,13,19,15,17,22,13,-,23,20,19,例2,6/8/2020,30,16,14,13,19,15,17,22,13,M,23,20,19,16,14,19,17,1