运筹学07-运输问题

1、第七章 运输问题7.1 运输问题的数学模型7.2 表上作业法7.3 产销不平衡问题15.1 运输问题的数学模型(1) 运输问题的引入例1 有一个地区有两个产棉区A1, A2向三个纺织厂B1 B2,B3供应棉花,产棉区每年的供应量分别为70kt和50kt;纺织厂每年的需求量分别为50kt,40kt和30kt.已知各产棉区到各纺织厂的单位运价如左表,问如何安排运输方案,使总运费最小.设由Ai运往Bj的棉花的运量为xij(kt),如右表: 销地产地 B1 B2 B3A1A2 5 8 6 4 3 8 销地产地 B1 B2 B3产量A1A2 x11 x12 x13 x21 x22 x23 70 50销量

2、 50 40 30 12025.1 运输问题的数学模型(1) 运输问题的引入由于各个产棉区Ai运往各个纺织厂Bj的总量应该等于它的产量，所以x11 + x12 + x13 =70 x21 + x22 + x23 =50另外,由于各个纺织厂收到各个产棉区运输的总量应该等于它的需求量x11 + x21 =50 x12 + x22 =40 x13 + x23 =30目标是总运费最小，即minz=5 x11 +8 x12 +6 x13 +4 x21 +3 x22 +8 x23 销地产地 B1 B2 B3产量A1A2 x11 x12 x13 x21 x22 x23 70 50销量 50 40 30 12

3、035.1 运输问题的数学模型(1) 运输问题的引入此运输问题的数学模型为:min z=5 x11 +8 x12 +6 x13 +4 x21 +3 x22 +8 x23 x11 + x12 + x13 =70 x21 + x22 + x23 =50 x11 + x21 =50 x12 + x22 =40 x13 + x23 =30 xij 0(i=1,2;j=1,2,3)45.1 运输问题的数学模型(2) 运输问题的一般数学模型运输问题的一般描述: m个产地Ai,I=1,2.,m,产量分别为ai个单位, n个产地Bj,j=1,2.,n,产量分别为bj个单位; Ai与Bj之间的单位运价爲Cij

4、,问如何安排运输方案,使总运费最少? 销地产地 B1 B2 Bn产量A1A2 Am c11 c12 c1n c21 c22 c2n cm1 cm2 cmn a1 a2 am销量 b1 b2 bn ai = bj 55.1 运输问题的数学模型(2) 运输问题的一般数学模型此问题的数学模型:min z= cij xij s.t xij = ai (i=1,2.m) xij = bj (j=1,2.n) xij0 (i=1,2.m ,j=1,2.n)i1j1mn65.2 表上作业法模型的矩阵表述表上作业法的计算步骤确定初始基可行解最优解的判别闭回路调整法7对于平衡运输问题化成矩阵形式:min z=C

5、X ; 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 。 1 1 1 1 1 1 A= 1 1 1 1 1 1 1 1 1 1 1 1R(A)=m+n-15.2.1 模型的矩阵表示8该系数矩阵中对应于变量xij的系数向量Pij ，其分量中除第i个和第m+j个为1外，其余的都为零。即Pij (0, 0, 0,1,0, ,0,1,0 , 0)T ei + em+j对产销平衡的运输问题，由于有以下关系式

6、存在： bj = ( xij )= ( xij )=ai所以模型最多只有m+n-1个独立约束方程。即系数矩阵的秩m+n-1。5.2.1 模型的矩阵表示9表上作业法的实质是单纯形法。其计算步骤为：（1）找出初始基可行解。即在（mn）产销平衡表上给出（m+n1）个数字格。（2）求各非基变量的检验数。在表上即是空格的检验数。判别是否达到最优解。如果已经是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。（4）重复（2），（3）直到得到最优解(肯定存在)为止。以上运算都可以在表上进行。5.2.2 表上作业法的矩阵表示10步骤详解（例2）例2 设某

7、物资从A1 , A2, A3处运往B1, B2, B3, B4处,各处供应量,需求量及单位运价见下表。问如何安排运输方案,才能使总运费最少? 销地产地 B1B2B3B4供应量A1 3 764 5A224 322A3 4385 3需求量32321011最小元素法伏格尔（Vogel）法5.2.3 确定初始基可行解12最小元素法根据单位运价最低处优先供应的原则依次安排运输量13最小元素法 销地产地 B1B2B3B4供应量A1 3 764 5A224 322A3 4385 3需求量323210单位运价14最小元素法 销地产地 B1B2B3B4供应量A13 7645A2224 322A343853需求量

8、32321015最小元素法 销地产地 B1B2B3B4供应量A131 7645A2224 322A343853需求量32321016最小元素法 销地产地 B1B2B3B4供应量A131 7645A2224 322A3432853需求量32321017最小元素法 销地产地 B1B2B3B4供应量A131 76425A2224 322A3432853需求量32321018最小元素法 销地产地 B1B2B3B4供应量A131 762425A2224 322A3432853需求量32321019最小元素法 销地产地 B1B2B3B4供应量A131 762425A2224 322A34328153需求量

9、32321020最小元素法运量初始基可行解21伏格尔（Vogel）法（推荐）比较最小运费与次小运费的差额，在差额最大处，采用最小运费调运。最小元素法的缺点是为了节省一处的费用，有时候造成在其它地方要多化几倍的运费。22伏格尔（Vogel）法运价行差额运价列差额23伏格尔（Vogel）法24伏格尔（Vogel）法25伏格尔（Vogel）法26伏格尔（Vogel）法27伏格尔（Vogel）法28伏格尔（Vogel）法29伏格尔（Vogel）法30伏格尔（Vogel）法31伏格尔（Vogel）法初始基可行解32闭回路法位势法判别的方法是计算空格（非基变量）的检验数C - CB B-1A 。因运输问题

10、的目标函数是要求实现最小化，故当所有的C - CB B-1A 0时，得最优解。5.2.4 最优解的判别333.2.4.1 闭回路法闭回路法:Xij对应的检验数ij=(闭回路上的偶数顶点运价之和 闭回路上的奇数顶点运价之和)闭回路: 以某空格为起点，用水平或垂直线向前划，每(?)碰到一数字格转90度后，继续前进，直到回到起始空格为止，得到一个闭回路。从每一个空格出发一定存在和可以找到一个惟一的闭回路。（非基变量对应的系数列向量由基唯一地线性表示）34闭回路法35闭回路法 销地产地 B1B2B3B4供应量A11+1 3 72-1 62 45A22-1 2 4 +1-2 3 22A3 42 31 8

11、 53需求量32321036闭回路法 销地产地 B1B2B3B4供应量A11+1 3 72-1 62 45A22-1 2 4 +1-2 3 22A3 42 31 8 53需求量32321023=3-6+3-2=-237闭回路法 销地产地 B1B2B3B4供应量A110 3 6 720 620 45A220 24 4 -2 3-1 22A3-1 420 310 8-1 53需求量32321038位势法（推荐）设u1, u2 , um;v1 , v2 , , vn是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量xa 的(m+n)(m+n)初始基矩阵。人工变量在目标函数中的系数ca

12、0，从线性规划的对偶理论可知：CB B-1 (u1, u2 , um;v1 , v2 , , vn)而每个决策变量xij的系数向量Pij = ei + em+j ，所以CB B-1 Pij = uivj 。于是检验数ij cij CB B-1 Pij = cij （ uivj ）当xij为基变量时，有cij （ uivj ）=0,即uivjcij非基变量的检验数为：ij cij （ uivj ）其中cij为对应的运价，称 ui为对应的行位势， vj为对应的列位势。39位势法（步骤）位势法：第一步：给出初始解，在对应的数字格处填入单位运价。第二步：在表中增加一行一列，在列中填入u1, u2 ,

13、, um，在行中填入v1 , v2 , , vn。先取定一个数u1 =0，根据uivjcij求得各个ui和vj值。第三步：再根据ij cij （ uivj ）求得非基变量（空格）的检验数。40位势法(第一步)41位势法(第二步)42位势法(第二步)【演排】43位势法(第二步)44位势法(第三步)【演排】45位势法(第三步)46观察与思考闭回路法与位势法所得的检验数是一样的，但位势法更简便一些。47闭回路调整法调整量=min(闭回路上的奇数顶点运量)（其原理与单纯形法中按最小比值规则来确定换出变量相同。）一般选择其中最小的负检验数，以它对应的空格为调入格。（即以它对应的非基变量为换入变量。）48

14、闭回路调整法 调入格（换入变量）49闭回路调整法（调整过程） 调出格（换出变量）50闭回路调整法51闭回路调整法（退化解）说明：（1）在用闭回路法调整时，若在闭回路上出现两个或两个以上的奇数顶点的相等的最小值，这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时有一个数字格必须填入一个零，表明它是基变量。（2）得到新的调整方案（新的解）后，再用闭回路法或位势法求各空格的检验数。（3）若仍有检验数为负，则继续调整。若所有检验数都非负，则表中的解为最优解。52闭回路调整法演排53闭回路调整法54闭回路调整法演排55闭回路调整法56闭回路调整法（调整过程）57闭回路调整法58闭回路调整法演排

15、59闭回路调整法60闭回路调整法所有检验数非负,此方案为最优方案61闭回路调整法运量62闭回路调整法（最优解）所有检验数非负,此方案爲最优方案,最小总运费为：f23162423142336(元)63闭回路调整法（无穷多最优解）由于A3行、B4列处的非基变量（空格）x34的检验数为零，因此该问题有无穷多最优解。可在表中以（3，4）为调入格，作闭回路(3，4)+ (1，4)- (1，1)+ (3，1)- (3，4)+确定min(2，1)1，经调整后得到另一最优解。64闭回路调整法65闭回路调整法66闭回路调整法67闭回路调整法68闭回路调整法运量69闭回路调整法（无穷多最优解）所有检验数非负,经调

16、整后得到另一最优方案,最小总运费为：f3316142 323 15 36(元)70无穷多最优解此运输问题的解为上述两个特解的凸组合。71表上作业法的解题过程分析实际问题建立运输表求出初始方案(最小元法或伏格尔法)找出绝对值最大的负检验数,经闭回路调整法得新方案得最优解,算出运费终止求出检验数(闭回路法或位势法)是否所有检验数072产大于销( ai bJ )的情况销大于产( ai bj )的情况Min f= Cij xij s.t xij ai (i=1,2,m) xij = bj (j=1,2,n) xij 0 (i=1,2,m ; j=1,2,n) 引人虚设的销地Bn+1其需要量为:bn+1

17、= ai - bj ,这样,m个产地、n个销地的不平衡运输问题,转换为m个产地,n+1个销地的平衡问题. 计算中,在运输表中添加Bn+1这列,其需求量为: bn+1= ai - bj, Ai到Bn+1的单位运价为单位存储费用(或为零)。5.3.1 产大于销的运输情况74销大于产( ai bj )的情况Min f= Cij xij s.t xij = ai (I=1,2,m) xij bj (j=1,2,n) xij 0 (i=1,2,m ; j=1,2,n)引人虚设的产地Am+1其产量为:am+1 bj - ai,等于销地的物資缺少量 。这样,m个产地、n个销地的不平衡运输问题就转换为m +1个产地,n个销地的平衡问题.计算中,在运输表中添加Am+1这行,其产量为am+1 bj - ai , Am+1到Bj的单位运价为单位缺货成本(或为零).5.3.2 销大于产的运输情况75习题试求出以下运输问题运费最少的运输方案。单位运费76习题解 销地产地 B1B