运输问题08.10

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,运输问题,1,运输问题的数学模型,一,.,平衡运输问题的数学模型,设某种物品有,m,个产地,A,1,，,A,2,，,，,A,m,，,产量分别是,a,1,，,a,2,，,，,a,m,个单位,有,n,个销地,B,1,，,B,2,，,，,B,n,，,销量分别为,b,1,，,b,2,，,，,b,n,个单位；,假设产销是平衡的，即 ，总产量等于总销量；,从,A,i,到,B,j,运输单位物品的运价是,c,ij,；,其中,：,为了方便，把上面的关系转化成下面的,运输表,产地,销地,B,1,B,j,B,n,产量,A,1,A,i,A,m,销量,C,11,C,1j,C,1n,C,m1,C,mj,C,mn,C,i1,C,ij,C,in,x,11,x,1j,x,1n,x,i1,x,ij,x,in,x,m1,x,mj,x,mn,.,.,.,.,.,.,.,.,a,1,a,i,a,m,.,.,b,1,b,j,b,n,表格中的回路,定义,1.,闭回路,闭回路是能折成,形式的变量组集合。其中,i,1,i,2,，,i,s,互不相同，,j,1,j,2,，,j,s,互不相同。每个变量称为,闭回路的顶点,，连接闭回路相邻两顶点的直线段叫做,闭回路的边,。,例：,x,11,，,x,12,，,x,32,，,x,34,，,x,24,，,x,21,就是一个闭回路。,B,1,B,2,B,3,B,4,A,1,A,2,A,3,x,11,x,12,x,21,x,32,x,24,x,34,运输问题的,m,n,个变量恰好和运输表的,m,n,格子相对应,闭回路的特点：,1,.,每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的；,2,.,每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向；,3,.,每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数；,4,.,从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻,顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点，,但每一顶点和边在闭回路中只经过一次。,2,表上作业法,1,、最小元素法,基本思想,：按单位运价的大小决定供应的先后，优先满足单位运价最小者的供销要求。,从单位运价表中选最小元素，然后比较产量和销量，,如果产,销，则划去列，若销,产，则划去行；,修改,a,i,和,b,j,的值；,再从划去一列和一行后的单位运价表中找最小元素，,，继续下去；,直到单位运价表的所有元素划去为止。,步骤：,定理：,用最小元素法得到的初始解是运输问题的一组,基本可行解,。,所填的,x,ij,的值是对应基变量的取值。,一、初始基可行解的求法,3,1,2,4,4,3,3,4,3,6,供,销,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,销量,3,11,3,10,1,7,9,4,2,10,8,5,3 6 5 6,7,4,9,1,1,3,5,3,3,6,6,2,、西北角法,基本思想：,优先满足运输表中左上角（即西北角）空格的供销要求。,3,4,1,4,2,2,2,2,4,3,3,5,6,6,供,销,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,销量,3,11,3,10,1,7,9,4,2,10,8,5,3 6 5 6,7,4,9,6,6,3,2,3,、伏格尔法（,Vogel,逼近法,.VAM,）,最小元素法的缺点：,为了节省一处的费用，有时造成在其它处要多花几倍的运费。,若不能按最小运费就近供应，就选择次最小运费，差额越大，说明不能按最小运费调运时，运费增加越多。,每行（列）中次最小价格元素与最小价格元素的数值之差，称为该行（列）的行（列）,罚数,。,对,罚数最大,处，采用,最小运费,调运。,在求一个可行解的过程中注意到包含在矩阵模型中的成本信息。它通过建立,“,罚数,”,来达到此目的。罚数表示对一方格不进行分配的可能的成本罚款。,步 骤：,Step1.,给定一个平衡的运输矩阵，分别计算行罚数和列罚数；,Step2.,确定具有,最大罚数,的行或列，然后在罚数所在行（或,列）中选择,最小价格,元素，将可能的最大单位数分配,给此方格，将相应的行（或列）的供应量和需求量减,去这个量，并划去完全满足的行（或列）；,Step3.,重复,step1,，,step2,，,直到给出初始解为止。,例,见下页！,0,1,1,供,销,B,1,B,2,B,3,B,4,产量 行罚数,A,1,A,2,A,3,销量,3,11,3,10,1,7,9,4,2,10,8,5,3 6 5 6 20,7,4,9,列 罚 数,2,5,1 3,6,0,1,2,2 1,3,1,3,0,1,2,1 2,3,2,3,7,6,1 2,0,0,2,3,3,1,1,5,2,2,6,7,5,4,2,Z=5,3+210+31,+1 8+64+,3,5,=85,二、最优解的判别,1.,闭回路法,定理：,设 是一组基变量，,是一个非基变量，则变量组,中存在唯一的闭回路。,从每一空格出发一定存在并可找到唯一的闭回路,对调运方案中每一空格按闭回路法求出检验数,若所有检验数大于等于零,，,则此方案为最优方案；,若存在,检验数小于零，,则需对此方案进行调整。,x,uj,x,ij,x,lk,x,ls,x,us,x,ik,检验数,供,销,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,销量,3,11,3,10,1,7,9,4,2,10,8,5,3 6 5 6,7,4,9,3,6,4,1,3,3,1,2,1,-1,10,12,不是最优解,此种颜色代表检验数,产销平衡,的运输,问题：,对偶,模型,其中：,u,i,为前,m,个约束对应的对偶变量，,v,j,为后,n,个约束对应的对偶变量。,2,、位势法,结论,：对原运输问题，为满足对偶可行性,只要检验数,运输问题的解,X,*,即为最优解。,满足对偶可行性,实际上,所有基变量的检验数等于零,即,定理：任何基可行解对应的方程组都有解。,运输问题的基可行解,在这一组基变量下，建立求解,u,i,，,v,j,的方程组：,位势,：,方程组的任意一组解叫做位势,。,对于运输问题的一个基可行解,，,用位势法得到的检验数是唯一的,（,位势可能不同,）。,对基变量,，,反复利用公式,求出空格的检验数,。,求出位势后,，,就可由公式,0,-1,-5,1,2,1,-1,10,12,此种颜色代表检验数,10,3,11,3,10,1,7,9,4,2,10,8,5,供,销,B,1,B,2,B,3,B,4,u,i,A,1,A,2,A,3,V,j,3,6,4,1,3,3,此种颜色代表初始解,2,9,3,三、改进的方法,闭回路调整法,当,ij,总销量,供,销,B,1,B,2,B,3,B,4,产量,A,1,A,1,A,2,销量,2,4,3,M,2,1,4,5,3,6,0,M,10 4 6 5,6,5,7,3,3,2,2,4,4,M,0,A,3,A,3,4,3,在下列不平衡运输问题中，已知三个收点的需求量一旦不能满足，就要承担缺货损失费。单位物资的缺货损失费分别为,4,、,3,和,7,。试建立运输模型,使运输费用最小。,供,销,B,1,B,2,B,3,产量,A,1,A,2,销量,4,5,2,6,8,3,8 7 14,10,15,供,销,B,1,B,2,B,3,产量,A,1,A,2,A,3,销量,4,5,2,6,4,8,3,3,7,8 7 14,10,15,4,解：,增加虚拟产地,A,3,在下列不平衡运输问题中，假定任何一个发点的物资没运出时，都要支出存储费用，且已知三个发点的单位存储费用各为,5,、,4,和,3,。由于发点,2,为其他物资腾出地方，因而要求把现有物资全部运出，求最优解。,供,销,B,1,B,2,B,3,产量,A,1,A,2,A,3,销量,1,2,1,0,2,4,3,5,3,30 20,20,20,40,30,供,销,B,1,B,2,B,3,B,4,产量,A,1,A,2,A,3,销量,1,2,0,2,4,3,1,5,3,30 20,20,20,20,40,30,5,M,3,解：增加虚拟销地,B,4,航线 起点城市 终点城市 每天航班数,1 E D 3,2 B C 2,3 A F 1,4 D B 1,例,:,某航运公司承担六个港口城市,A,、,B,、,C,、,D,、,E,、,F,的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见表,1,。,又知每条 船只每次装卸的时间各需,1,天，则该航运公司至少应配备多少条船，才能满足所有航线的要求。,A B C D E F,A 0 1 2 14 7 7,B 1 0 3 13 8 8,C 2 3 0 15 5 5,D 14 13 15 0 17 20,E 7 8 5 17 0 3,F 7 8 5 20 3 0,到,从,解,该公司所需配备船只分两部分：,（,1,）载货航程需要的周转船只数,航线,装货天数,航程天数,卸货天数,小计,航班数,需周转船只数,1 1 17 1 19 3 57,2 1 3 1 5 2 10,3 1 7 1 9 1 9,4 1 13 1 15 1 15,载货需要,57+10+9+15=91,条船,（,2,）各港口调度所需船只数,港口城市,每天到达,每天需求 余缺数,A 0 1 -1,B 1 2 -1,C 2 0 2,D 3 1 2,E 0 3 -3,F 1 0 1,为使配备船只数最少，应做到周转空船数为最少。建立运输问题。,最少需周转空船数：,1,2+1,5+113+117+13=40,故至少应配备,91+47=138,条船,到,A B E,每天多余船只,C,D,F,每天缺少船只,2,3,5,14,7,13,8,17,3,1 1 3,2,2,1,从,1,1,1,1,1,作业一,:,用表上作业法求解表中给出的运输问 题的最优解,.,销地,产地,甲,乙,丙,丁,产量,1,3,7,6,4,5,2,2,4,3,2,2,3,4,3,8,5,3,销量,3,3,2,2,作业二,:,某百货公司去外地采购,A,、,B,、,C,、,D,四种规格的服装，数量分别为,A1500,套，,B2000,套，,C3000,套，,D3500,套，有三个城市可供应上述规格服装，供应数量为城市,12500,套，城市,22500,套，城市,35000,套。由于这些城市的服装质量、运价及销售情况不一，预计售出后的利润（元,/,套）也不同，详见表：,请帮助该公司确定一个预期盈利最大的采购方案。,A,B,C,D,1,10,5,6,7,2,8,2,7,6,3,9,3,4,8,