运筹学运输问题

1、2021-10-161第一节第一节 运输问题及其数学模型运输问题及其数学模型第二节第二节 用表上作业法求解运输问题用表上作业法求解运输问题第三节第三节 运输问题的进一步讨论运输问题的进一步讨论第四节第四节 应用问题举例应用问题举例讲四节：2021-10-162一、运输问题的数学模型设某物品有m个产地A1, A2 , Am；各产地的产量分别是a1,a2,am；有n个销地B1, B2, Bn。各销地的销量分别是b1,b2,bn ；假如从产地Ai(i=1,2,m)向销地Bj( j= 1,2,n)运输单位物品的运价是cij；问怎样调运这些物品才能使总运费最小？这个问题是一个多产地多销地的单品种物品运输

2、问题。把这个问题整理成为一个表,称之为运价表。（见下页）返回第三章目录返回第三章目录返回第三章目录2021-10-163变量 xij( i = 1,2,.,m;j = 1,2,n )为由产地 Ai 运往销地 Bj 的物品数量。minjjiba11minjjiba11称为产销平衡运输问题称为产销不平衡运输问题2021-10-164这是一个线性规划问题，可以用单纯形法求解。但是，由于它所含变量多，求解极不方便。即使求解一个m3，n4的简单运输问题，变量数目也将达到19个之多。因此，必须寻找更简便的求解方法。njmixnjbxmiaxxczijjmiijnjiijminjijij,.,2 , 1;,

3、.,2 , 1;0,.,2 , 1;,.,2 , 1;min1111产量约束销量约束非负约束总运输费用极小化极小化由某一产地运往各由某一产地运往各个销地的物品数量个销地的物品数量之和等于该产地的之和等于该产地的产量产量由各个产地运往某由各个产地运往某一销地的物品数量一销地的物品数量之和等一该销地的之和等一该销地的销量销量非负条件非负条件2021-10-1651.运输问题有有限最优解对运输问题的数学模型，若令变量另外，在运输问题的数学模型中另外，在运输问题的数学模型中,目标函数是取最小值目标函数是取最小值,它它的值不会趋于无穷大的值不会趋于无穷大, 在实际问题中也不可能出现这种情况在实际问题中也

4、不可能出现这种情况,因此因此,运输问题有有限最优解。运输问题有有限最优解。对运输问题数学模型的约束条件进行整理对运输问题数学模型的约束条件进行整理,得其系数矩阵得其系数矩阵的结构形式为：的结构形式为：njmiQbaxjiij, 2 , 1;, 2 , 1,其中：njjmiibaQ11是运输问题的一个可行解2021-10-1662.运输问题约束条件的系数矩阵111111111111111111212222111211mnmmnnxxxxxxxxxm 行n 行TijA0 , 0 , 1 , 0 , 0 , 1 , 0 , 0第 i 个第(m+j)个系数列向量的结构：即除第i个和第( m + j )

5、个分量为1外，其它分量全等于0。2021-10-167(1) 约束条件系数矩阵的元素等于0或1；(2) 约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前 m 个约束方程中出现一次,在后 n 个约束方程中也出现一次。如果是产销平衡运输问题,还有以下特点：（3）所有结构约束条件都是等式约束；（4）各产地产量之和等于各销地销量之和。例1 某种物品先存放在两个仓库A1和A2中，再运往三个使用地B1，B2，B3，其间的运距（或单位运价）如表3-2小方格中的数据所示，试建立使总运输量（或总运费）最小的运输问题数学模型。2021-10-168表3-2 销地产地B1B2B3产量A134210A23

6、534销量356x11x12x13x21x22x230,653410353243min232221131211231322122111232221131211232221131211xxxxxxxxxxxxxxxxxxxxxxxxz解题思路：（1）假设变量（2）分析约束（3）明确目标（4）建立模型（5）求解变量（6）分析方案（7）得出决论66-6=010-6=434-3=13-3=011-1=05-1=444-4=04-4=000显然显然x11=3,x12=1,x13=6,x22=4,x21=0,x23=0是该运输问是该运输问题的一个可行解。题的一个可行解。目标函数值目标函数值z = 4520

7、21-10-169它是求解运输问题的一种简便而有效的方法,其求解过程在运输表上进行,它是一种迭代法,其步骤为：1. 先按某种规划找出一个初始解(初始调运方案）；2. 对现行解作最优性判别；3. 若不是最优解,就在表上对它进行调整改进,得出一个新解；4. 再判别,再改进,直到得到运输问题的最优解为止；在迭代过程中,得出的所有解都要求是运输问题的基可行解。例2 某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售地出售，各工厂的生产量，各销售地的销售量（假定单位均为吨）以及各工厂到各销售地的单位运价（元/吨）示于表3-4中，要求研究产品如何调运才能使总运费最小？返回第三章目录返回第三章目录

8、返回第三章目录2021-10-1610一、确定运输问题的初始基可行解（初始调运方案）1. 最小元素法： 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448810-8=222-2=0212-2=101016-10=610-10=031414-14=022-14=8488-8=014-8=6566-6=06-6=08-8=0661该运输问题一个初始可行解为：x13=10, x14=6, x21=8, x23=2, x32=14, x34=8.总运费 41011 62 8325 146 8 2462021-10-1611 销地产地B1B2B3B

9、4产量A141241116A22103910A38511622销量8141214482.西北角法88-8=0116-8=888-8=0148=62666=010-6=4344-4=012-4=8488-8=022-8=1451466初始可行解为：x11=8 ,x12=8 ,x22=6 ,x23=4 ,x33=8 ,x34=14 .总运输费用 z84 812 610 43 811 1463722021-10-1612 销地产地B1B2B3B4产量行罚数12345A141241116A22103910A38511622销量814121448列罚数12345011251314012213801212

10、8761212002243. 沃格尔法该运输问题的可行解为：x13=12 ,x14=4 ,x21=8 ,x24=2 ,x32=14 ,x34=8 ,其他变量等于0。总运输费 z24408 06020404 002021-10-1613最小元素法：z246西北角法：z372沃格尔法：z244沃格尔法解出的目标函数值最小，最小元素法次之，西北角法最大；一般说来，沃格尔法得出的解质量最好，在运输问题中，常用来作最优解的近似解。二、解的最优性检验2021-10-1614：为了减少运费,应优先考虑单位运价最小(或运距最短)的供销业务,最大限度地满足其供销量。：.),min(),min(,) 1 (000

11、00000jijijiijjiBAbaxccji供应给的物品量由并将找出和对所有.,)2(00000000ijjjiijiabbBAax减少为的需求量这个产地，且后不再考虑的可供物品已用完，以则若.,) 3(00000000jiiijjjibaaABbx减少为的可供量由不再考虑这个销地，且，以后的需求已全部得到满足则销地如果(4) 在余下的供销点的供销关系中,继续安排调运,直到 安排完成所有供销任务,得到一个完整的方案为止。确定初始基可行解（初始调运方案）2021-10-1615:优先满足运输表中西北角(即左上角)上空格的供销量需求.:(1). 最先填xij = min(ai,bj),即( A

12、i,Bj )；(2). 若 xij = ai ，则 Ai 行不在考虑,且 Bj 列剩下 bj - ai 来填左上角其它空格.(3). 若 xij = bj ，则 Bj 列不再考虑,且 Ai 行剩下 ai - bj 来填左上角其它空格.(4). 如此继续完成调运,最后得出一个初始方案。用西北角法确定运输问题的初始可行解2021-10-1616：对于每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价,并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，若罚数的值很大，不按最小运价组织运输

13、就会造成很大的损失；故应尽量按最小单位运价按排运输。：（1）先计算运输表中每一行和每一列的罚数值，并称为行罚数和列罚数。（2）将行罚数填入位于运输表右侧行罚数栏的左边第一列的相应格子中；列罚数填入位于运输表下边列罚数栏的第一行的相应格子中。（3）找出该列和该行的列罚数和行罚数中的最大值；根据最大罚数值的位置在运输表中运价最小的格中填入一个尽可能大的运输量，并划去对应的一行或一列。（4）继续找其它列和行的列罚数和行罚数；找出其它运输量；已划去的不再找。直到最后按排完，即得到一个初始运输方案。用沃尔沃法确定运输问题的初始可行解2021-10-16172021-10-16181012-1112s11

14、=c11-c21+c23-c14=4-2+3-4=1s31c31-c34+c14-c13+c23-c21=8-6+11-4+3-2=10s12=c12-c32+c34-c14=12-5+6-11=2s22=c22-c32+c34-c14+c13-c23=10-5+6-11+4-3=1s33=c33-c34+c14-c13=11-6+11-4=12s24c24-c14+c13-c23=9-11+4-3=-1由于s2410所以，上表中的解不是最优解。2021-10-1619解题思想：用u1,u2,um分别表示与前分别表示与前m个约束相对应的对偶变量，用v1,v2,vn分别表示与后n个约束相 对 应

15、 的 对 偶 变 量 ， 即 对 偶 变 量 向 量 ：Y=(u1,u2,um,v1,v2,vn)将运输问题的数学模型写成对偶规划：的符号不限jiijjiminjjjiivunjmiCvuvbuaZ,.,2 , 1,.,2 , 1max11njmixvbxuaxxczijjjmiijinjiijminjijij,.,2 , 1;,.,2 , 1;0min11112021-10-1620)(1jiijjijjBijijijijvucYPcPBCczcs的符号不限jiijjiminjjjiivunjmiCvuvbuaZ,.,2 , 1,.,2 , 1max112021-10-1621ssssjij

16、ijijijijicvucvucvu.22221111解题步骤：(一）在运输表右边增加一位势列ui；在下边增加一位势行vj；(二）计算位势 (三）计算检验数： sij=cij-(ui+vj)由于基变量的检验数sij0，故对这组基变量可以写出方程组：这个方程组有（m+n-1)方程，（m+n）个变量，所以它的解不是唯一解。这个方程组的解称为。2021-10-1622例3 用位势法对前例运输问题作最优性检验。（1）在运价表上增加一位势列 ui 和位势行 vj ，（上表）（2）建立位势方程组，计算位势。10-429310（3）计算检验数。sijcij（ui+vj)1102112-1由于s24= -10

17、，所以上表得出的可行解不是最优解。需要改进2021-10-1623建立位势方程组，计算位势u20 ， v12v33 ， u11v410 ，u34 v296532114432332124131vuvuvuvuvuvu任意指定某一位势等于一个较小的整数或零，如 u20将计算结果填入运输表的位势列和位势行。2021-10-16241.改进原因对运输问题来说,若某空格的检验数sij为负，说明将这个非基变量变为基变量时运费会减小，因而这个解不是最优解,还需要改进；2.改进方法在运输表中，找出sij0的空格对应的闭回路Lij，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其它顶点的运输量

18、,以得到另一个更好的基可行解。2021-10-1625(1) 以xij为换入变量，找出它在运输表中的闭回路； (2) 以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺时针或逆时针方向前进，对闭回路上的顶点依次编号；(3) 在闭回路上的所有偶数顶点中，找出运输量最小(minxij)的顶点(格子)，以该格中的变量为换出变量；(4) 以min xij为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减少这一数值，从而得出一新的运输方案。该方案的总运费比原运输方案的总运费减少，改变量等于sij(min xij)。（5）对得到的新解进行最优性判别。重复上述步骤，直到得

19、到最优解为止。2021-10-1626例 4 对例2用最小元素法得出的解进行改进（2）计算检验数，对解的最优性进行判断。 销地产地B1B2B3B4产量A1412101046 61116A28 82102 23910A3814145118 8622销量8 814121448（+2）（-2）（+2）（-2）124 21122109（1）因为s240，所以，以此格 （A2，B4）为顶点寻找一个闭回路，进行解的改进。2021-10-1627四、需要说明的几个问题1.若运输问题的某一基可行解中，有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取

20、sij0中最小者对应的变量为换入变量。2.当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重最优解。3.当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时，需同时划去运输表的一行和一列，即出现退化。退化是时有发生的，为使迭代进行下去，退化时在同时划去的一行或一列中的某个格中填入0，表示该格变量取值为0的基变量，使迭代过程中基可行解的分量恰好为( m + n 1 )个。2021-10-1628一、产销不平衡的运输问题解题思想：把产销不平衡的运输问题转化为产销平衡问题。0,.,2 , 1,.,2 , 1,min.11

21、11111ijmijijnjiijminjijijminjjixnjbxmiaxxczba其数学模型为：量时，即总产量大于总销）如果（返回第三章目录返回第三章目录返回第三章目录2021-10-1629可假想一个销地Bn+1，其销量为bn+1，其实质没有运输，只是就地储藏。设调运假想销地的物品数量为xi,n+1；故其单位运价ci,n+10;且01,.,2 , 1,.,2 , 1,min111111111ijjmiijinjijminjijijnjjmiinxnjbxmiaxxczbab产销平衡问题；则产销不平衡就变为此式对应的运输表见下页。2021-10-1630njjmiiba112021-1

22、0-1631(2)如果总销量大于总产量，则增加一个假想产地，它的产量等于总销量与总产量之差。xm+1,1xm+1,2xm+1,nmiinjjab112021-10-1632二、有转运的运输问题由于空间位置的需要，需考虑转运问题，才能使总运费最小。A1A2B2B1B3产地销地A2A1B2B1B3产地销地（a)无转运（a)包含转运比较以上两图。显然，包含转运的运输问题复杂得多。2021-10-1633假定m个产地A1,A2,Am和n个销地B1,B2,Bn都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个。ai ：第i个产地的产量（净供应量）；bj ：第j个销地的销量（净需要量

23、）；xij ：第i个发送地运到第j个接收地的物品数量；cij ：由第i个发送地运到第j个接收地的单位运价；ti ：第i个地点转运物品的数量；ci ：第i个地点转运单位物品的费用；则有：am+1=am+2=,am+n=0，b1=b2=,=bm=0Qbanmmjjmii11则如为平衡运输问题，n个销地的净产量等于零。m个产地地的净销量等于零。2021-10-1634有转运的运输问题模型：)(,.,2 , 1, 0,.,2, 1.,.,2 , 1.,.,2, 1.,.,2 , 1.min, 1, 121, 1, 121,1,1,21,1,1,21111jinmjixnmmmjtbxxxxxmjtxx

24、xxxnmmmitxxxxxmitaxxxxxtcxczijjjjnmjjjjjjjjnmjjjjjjinmiiiiiiiiinmiiiiiiinmiiinmjiinmijjijij由第i个产地发送到各个地方的物品数量之和，等于该产地的产量加上经它转运的物品数量。由第i个发送地发送到各个地方的物品数量之和，等于经它转运的物品数量。由各地运到第j地的物品数量之和，等于转运量。由各地运到第j地的物品数量之和，等于净需要量加上转运量。2021-10-1635nmjixnmmmjbQxmjQxnmmmiQxmiaQxQcxczijnmijijnmiijnmjijnmjiijnminmjnmiiijij

25、,.,2 , 1, 0,.,2, 1,.,2 , 1,.,2, 1,.,2 , 1,min1111111注意：在上式中，对所有ij，cijci。由于目标函数中是常数,故不影响求最优解。其对应的表如下nmiiQc12021-10-1636有转运问题的运输表表3-172021-10-1637表3-182021-10-1638 有一个运输系统包括二个产地（、）、二个销地（、）及一个中间转运站（），各产地的产量和各销地销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。解：a1=10, a2=40, a3=a4=a5=0b1=b2=b

26、3=0, b4=30, b5=20Q=10+40=30+20=50c1=4, c2=1, c3=3, c4=3, c5=512345105243402145536305320以以M表示足够大的正数，可得该问题的运输表表示足够大的正数，可得该问题的运输表3-192021-10-1639表3-19例6图2021-10-16402021-10-16412021-10-1642Excel求解2021-10-1643运用问题举例例题一：某公司承担4条航线的运输任务，已知：（1）各条航线的起点城市和终点城市及每天的航班数见表3-28；（2）各城市间的航行时间见表3-29；（3）所有航线都使用同一种船只，每次装船和卸船时间均为1天。问该公司至少应配备多少条船才能满足所有航线运输的需要？表3-29 各城市间的航行时间返回第三章目录返回第三章目录返回第三章目录2021-10-1644表3-29 各城市间的航行时间（天）解：所需船只可分为两部分：（1）各航线航行、装船、卸船所占用的船只，对各航线逐一分析，所需船只数列入表3-30中，累计共需91条船。返回表3-282021-10-1645表3-30 各航线航行、装船、卸船所占用的船只（2）各港口之间调度所需船只