运筹学运输问题(3)

第七章运输问题,7.1运输问题的数学模型7.2表上作业法7.3产销不平衡问题,5.1运输问题的数学模型,(1)运输问题的引入,例1有一个地区有两个产棉区A1,A2向三个纺织厂B1B2,B3供应棉花,产棉区每年的供应量分别为70kt和50kt;纺织厂每年的需求量分别为50kt,40kt和30kt.已知各产棉区到各纺织厂的单位运价如左表,问如何安排运输方案,使总运费最小.设由Ai运往Bj的棉花的运量为xij(kt),如右表:,5.1运输问题的数学模型,(1)运输问题的引入,由于各个产棉区Ai运往各个纺织厂Bj的总量应该等于它的产量，所以x11+x12+x13=70 x21+x22+x23=50另外,由于各个纺织厂收到各个产棉区运输的总量应该等于它的需求量x11+x21=50 x12+x22=40 x13+x23=30目标是总运费最小，即minz=5x11+8x12+6x13+4x21+3x22+8x23,5.1运输问题的数学模型,(1)运输问题的引入,此运输问题的数学模型为:minz=5x11+8x12+6x13+4x21+3x22+8x23x11+x12+x13=70 x21+x22+x23=50 x11+x21=50 x12+x22=40 x13+x23=30 xij0(i=1,2;j=1,2,3),5.1运输问题的数学模型,(2)运输问题的一般数学模型,运输问题的一般描述:m个产地Ai,I=1,2.,m,产量分别为ai个单位,n个产地Bj,j=1,2.,n,产量分别为bj个单位;Ai与Bj之间的单位运价爲Cij,问如何安排运输方案,使总运费最少?,5.1运输问题的数学模型,(2)运输问题的一般数学模型,此问题的数学模型:minz=cijxijs.txij=ai(i=1,2.m)xij=bj(j=1,2.n)xij0(i=1,2.m,j=1,2.n),i1,j1,m,n,5.2表上作业法,模型的矩阵表述表上作业法的计算步骤确定初始基可行解最优解的判别闭回路调整法,对于平衡运输问题化成矩阵形式:minz=CX;AX=b;X0其中C=(c11,c12,.,C1n,.,cm1,cm2,cmn)，b=(a1,a2,am,b1,b2,bn)T,X=(x11,x12,x1n,xm1,xm2,xmn)T。111111A=111111111111R(A)=m+n-1,5.2.1模型的矩阵表示,该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1外，其余的都为零。即Pij(0,0,0,1,0,0,1,0,0)Tei+em+j对产销平衡的运输问题，由于有以下关系式存在：bj=(xij)=(xij)=ai所以模型最多只有m+n-1个独立约束方程。即系数矩阵的秩m+n-1。,5.2.1模型的矩阵表示,表上作业法的实质是单纯形法。其计算步骤为：（1）找出初始基可行解。即在（mn）产销平衡表上给出（m+n1）个数字格。（2）求各非基变量的检验数。在表上即是空格的检验数。判别是否达到最优解。如果已经是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。（4）重复（2），（3）直到得到最优解(肯定存在)为止。以上运算都可以在表上进行。,5.2.2表上作业法的矩阵表示,步骤详解（例2）,例2设某物资从A1,A2,A3处运往B1,B2,B3,B4处,各处供应量,需求量及单位运价见下表。问如何安排运输方案,才能使总运费最少?,最小元素法伏格尔（Vogel）法,5.2.3确定初始基可行解,最小元素法,根据单位运价最低处优先供应的原则依次安排运输量,最小元素法,单位运价,最小元素法,最小元素法,最小元素法,最小元素法,最小元素法,最小元素法,最小元素法,运量,初始基可行解,伏格尔（Vogel）法（推荐）,比较最小运费与次小运费的差额，在差额最大处，采用最小运费调运。,最小元素法的缺点是为了节省一处的费用，有时候造成在其它地方要多化几倍的运费。,伏格尔（Vogel）法,运价行差额,运价列差额,伏格尔（Vogel）法,伏格尔（Vogel）法,伏格尔（Vogel）法,伏格尔（Vogel）法,伏格尔（Vogel）法,伏格尔（Vogel）法,伏格尔（Vogel）法,伏格尔（Vogel）法,伏格尔（Vogel）法,初始基可行解,闭回路法位势法,判别的方法是计算空格（非基变量）的检验数C-CBB-1A。因运输问题的目标函数是要求实现最小化，故当所有的C-CBB-1A0时，得最优解。,5.2.4最优解的判别,3.2.4.1闭回路法,闭回路法:Xij对应的检验数ij=(闭回路上的偶数顶点运价之和闭回路上的奇数顶点运价之和),闭回路:以某空格为起点，用水平或垂直线向前划，每(?)碰到一数字格转90度后，继续前进，直到回到起始空格为止，得到一个闭回路。从每一个空格出发一定存在和可以找到一个惟一的闭回路。（非基变量对应的系数列向量由基唯一地线性表示）,闭回路法,闭回路法,闭回路法,23=3-6+3-2=-2,闭回路法,位势法（推荐）,设u1,u2,um;v1,v2,vn是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量xa的(m+n)(m+n)初始基矩阵。人工变量在目标函数中的系数ca0，从线性规划的对偶理论可知：CBB-1(u1,u2,um;v1,v2,vn)而每个决策变量xij的系数向量Pij=ei+em+j，所以CBB-1Pij=uivj。于是检验数ijcijCBB-1Pij=cij（uivj）当xij为基变量时，有cij（uivj）=0,即uivjcij非基变量的检验数为：ijcij（uivj）其中cij为对应的运价，称ui为对应的行位势，vj为对应的列位势。,位势法（步骤）,位势法：第一步：给出初始解，在对应的数字格处填入单位运价。第二步：在表中增加一行一列，在列中填入u1,u2,um，在行中填入v1,v2,vn。先取定一个数u1=0，根据uivjcij求得各个ui和vj值。第三步：再根据ijcij（uivj）求得非基变量（空格）的检验数。,位势法(第一步),位势法(第二步),位势法(第二步)【演排】,位势法(第二步),位势法(第三步)【演排】,位势法(第三步),观察与思考,闭回路法与位势法所得的检验数是一样的，但位势法更简便一些。,闭回路调整法,调整量=min(闭回路上的奇数顶点运量),（其原理与单纯形法中按最小比值规则来确定换出变量相同。）,一般选择其中最小的负检验数，以它对应的空格为调入格。,（即以它对应的非基变量为换入变量。）,闭回路调整法,调入格（换入变量）,闭回路调整法（调整过程）,调出格（换出变量）,闭回路调整法,闭回路调整法（退化解）,说明：（1）在用闭回路法调整时，若在闭回路上出现两个或两个以上的奇数顶点的相等的最小值，这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时有一个数字格必须填入一个零，表明它是基变量。（2）得到新的调整方案（新的解）后，再用闭回路法或位势法求各空格的检验数。（3）若仍有检验数为负，则继续调整。若所有检验数都非负，则表中的解为最优解。,闭回路调整法演排,闭回路调整法,闭回路调整法演排,闭回路调整法,闭回路调整法（调整过程）,闭回路调整法,闭回路调整法演排,闭回路调整法,闭回路调整法,所有检验数非负,此方案为最优方案,闭回路调整法,运量,闭回路调整法（最优解）,所有检验数非负,此方案爲最优方案,最小总运费为：f23162423142336(元),闭回路调整法（无穷多最优解）,由于A3行、B4列处的非基变量（空格）x34的检验数为零，因此该问题有无穷多最优解。可在表中以（3，4）为调入格，作闭回路(3，4)+(1，4)-(1，1)+(3，1)-(3，4)+确定min(2，1)1，经调整后得到另一最优解。,闭回路调整法,闭回路调整法,闭回路调整法,闭回路调整法,闭回路调整法,运量,闭回路调整法（无穷多最优解）,所有检验数非负,经调整后得到另一最优方案,最小总运费为：f33161423231536(元),无穷多最优解,此运输问题的解为上述两个特解的凸组合。,表上作业法的解题过程,分析实际问题,建立运输表,求出初始方案(最小元法或伏格尔法),找出绝对值最大的负检验数,经闭回路调整法得新方案,得最优解,算出运费,终止,求出检验数(闭回路法或位势法),是,否,所有检验数0,产大于销(aibJ)的情况销大于产(aibj)的情况Minf=Cijxijs.txijai(i=1,2,m)xij=bj(j=1,2,n)xij0(i=1,2,m;j=1,2,n)引人虚设的销地Bn+1其需要量为:bn+1=ai-bj,这样,m个产地、n个销地的不平衡运输问题,转换为m个产地,n+1个销地的平衡问题.计算中,在运输表中添加Bn+1这列,其需求量为:bn+1=ai-bj,Ai到Bn+1的单位运价为单位存储费用(或为零)。,5.3.1产大于销的运输情况,销大于产(aibj)的情况Minf=Cijxijs.txij=ai(I=1,2,m)xijbj(j=1,2,n)xij0(i=1,2,m;j=1,2,n)引人虚设的产地Am+1其产量为:am+1bj-ai,等于销地的物資缺少量。这样,m个产地、n个销地的不平衡运输问题就转换为m+1个产地,n个销地的平衡问题.计算中,在运输表中添加Am+1这行,其产量为am+1bj-ai,Am+1到Bj的单位运价为单位缺货成本(或为零).,5.3.2销大于产的运输情况,习题,试求出以下运输问题运费最少的运输方案。,单