第3章运输问题

运筹学许弼第三章运输问题运筹学3.1运输模型运筹学例1.1-3表1.2B1B2B3供应量A1152118200A2202516150需求量1008090).3,2,1;2,1(0,90,80,100,150,200..,162520182115min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxzij运筹学运输问题的数学描述设某种物资有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，问怎样调运这些物资才能使总运费最少？运筹学收点发点B1B2…Bn发量A1x11x12…x1na1c11c12c1nA2x21x22…x2na2c21c22c2n………………Amxm1xm2…xmnamcm1cm2cmn收量b1b2…bn运筹学,0),,2,1(,),,2,1(,..min111111ijnjjmiijmiijinjijminjijijxbanjbxmiaxtsxcz运筹学nmmnmmnnbbbaaaxxxxxxxxx1111111111111111112121212222111211nmAr)(运筹学nmmnbbbaaaxxxxxx11111111121321312111211BABABABAnBmAnm)1(*0,*0阶为阶，为1)(nmAr定理3.1运输问题的任何一个基都由m+n-1个变量组成。运筹学收点发点B1B2B3B4A1x11x12x13x14c11c12c13c14A2x21x22x23x24c21c22c23c24A3x31x32x33x34c31c32c33c34收点发点B1B2B3B4A1x11x12x13x14c11c12c13c14A2x21x22x23x24c21c22c23c24A3x31x32x33x34c31c32c33c34闭回路：运筹学定理3.2运输问题中m+n-1个变量构成基的充分必要条件是它不包含闭回路。收点发点B1B2B3B4A1x11x12x13x14c11c12c13c14A2x21x22x23x24c21c22c23c24A3x31x32x33x34c31c32c33c34运筹学收点发点B1B2B3B4A1x11x12x13x14c11c12c13c14A2x21x22x23x24c21c22c23c24A3x31x32x33x34c31c32c33c34111111111111111111111111343332312423222114131211xxxxxxxxxxxx运筹学3.2初始基可行解的求法运筹学3.2.1最小元素法例3.2-1收点发点B1B2B3B4发量A19918110A210116818A361412216收量49757XX×29XX×12X×21X×11×55××运筹学3.2.1最小元素法例3.2-1收点发点B1B2B3B4发量A12X7X9918110A219XX10116818A31XX561412216收量4975运筹学例3.2-2收点发点B1B2B3发量A13316A25243A37655收量5373XX×05X×00X×7×00××运筹学例3.2-2收点发点B1B2B3发量A103X3316A25XX5243A30X77655收量537运筹学定理3.3由最小元素法得到的各变量的值是运输问题的一个基可行解，而所有打圈处的变量正好构成一个基。运筹学3.2.2沃格尔近似法收点发点B1B2B3B4发量A19918110A210116818A361412216收量4975行差列差102861626XXX×128871229X×1388725X×438721X×311921×33××运筹学3.2.2沃格尔近似法收点发点B1B2B3B4发量A13X159918110A219XX10116818A3XX6X61412216收量4975行差8888922331110列差261621278278272运筹学3.3最优解的获得运筹学1、解的最优性检验位势法：收点发点B1B2B3B4发量v1v2v3v4A1279u1918110A21910u2116818A3156u31412216收量4975运筹学收点发点B1B2B3B4发量v1v2v3v4A1279u1918110A21910u2116818A3156u31412216收量497509125411运筹学收点发点B1B2B3B4发量94111A12790918110A219102116818A315651412216收量4975ijjiijcvuσ运筹学收点发点B1B2B3B4发量94111A12-147190918110A219-5-5102116818A31-345651412216收量4975ijjiijcvuσ运筹学收点发点B1B2B3B4发量94111A12-147190918110A219-5-5102116818A31-345651412216收量4975闭回路法求检验数示意：运筹学收点发点B1B2B3B4发量94111A12-147190918110A219-5-5102116818A31-345651412216收量49752、解的改进：闭回路法：运筹学收点发点B1B2B3B4发量94111A13-146190918110A219-5-5102116818A3-315651412216收量49752、解的改进：闭回路法：运筹学收点发点B1B2B3B4发量94115A13-146190918110A219-5-5102116818A3-315611412216收量49752、解的改进：闭回路法：运筹学收点发点B1B2B3B4发量94115A13-146590918110A219-5-1102116818A3-4-715611412216收量49752、解的改进：闭回路法：运筹学收点发点B1B2B3B4发量94115A13-146590918110A219-5-1102116818A3-4-715611412216收量49752、解的改进：闭回路法：运筹学收点发点B1B2B3B4发量94115A13-141590918110A219-5-1102116818A3-4-76611412216收量49752、解的改进：闭回路法：运筹学收点发点B1B2B3B4发量94110A13-141590918110A219-5-6102116818A3-4-76-5611412216收量49752、解的改进：闭回路法：运筹学定理3.4在全体基变量中加入一个非基变量后，就一定存在一条，且只有唯一的一条闭回路。定理3.5如果一个运输问题中的所有发量和所有收量都是整数，那么它的每一个基可行解中的所有变量也都取整数值。运筹学3.4不平衡运输问题运筹学不平衡运输问题:总发量不等于总收量的运输问题，即：njjmiiba11运筹学njjmiiba11这时增加一个虚拟的收点Bn+1，它的收量为bn+1，即由于它实际上并不存在，所以从发点Ai(i=1,2,…,m)调运到这个虚拟收点的物资数量xi,n+1，实际上是就地储存在Ai的物资数量。就地储存的物资不经过运输，所以单位运价ci,n+1＝0(i=1,2,…,m)。njjmiinbab111运筹学例3.4-1B1B2B3B4发量A146287A253465A379648收量3642运筹学B1B2B3B4B5发量A1462807A2534605A3796408收量3642520运筹学njjmiiba11这时增加一个虚拟的发点Am+1，它的发量为am+1，即由于它实际上并不存在，所以从它调运到各个收点Bj(j=1,2,…,n)的物资数量xm+1,j，实际上是各收点Bj所需物资的欠缺额。同样，这些欠缺的物资的单位运价cm+1,j＝0(j=1,2,…,n)。miinjjmaba111运筹学例3.4-2B1B2B3B4发量A165736A224565A385745收量4736运筹学B1B2B3B4发量A165736A224565A385745A400004收量473620运筹学3.5指派问题运筹学例3.5-1B1B2B3B4A13452A28576A39645A45366运筹学指派问题的一般形式：有n个人和n件事，已知第i个人做第j件事的效率为cij(i,j＝1,2,…,n)，需要确定人和事之间的一一对应的指派方案，使完成这n件事的总效率最好。运筹学事人BjAixijcij运筹学事1事2…事n人1人2…人nnnnnnnxxxxxxxxx212222111211nnijxX)(解矩阵：引入n2个0－1变量：若指派Ai做Bj若不指派Ai做Bj01ijx运筹学效率矩阵：nnnnnnnnijccccccccccC212222111211)(运筹学标准指派问题的特征：人数和事数相等；一人做一事；优化目标为最小化，即为最小化指派问题。运筹学标准指派问题的数学模型：njixnjxnixtsxczijniijnjijijninjij,,2,1,10,,2,1,1,,2,1,1..min1111，或运筹学标准指派问题的数学模型：njixnjxnixtsxczijniijnjijijninjij,,2,1,0,,2,1,1,,2,1,1..min1111，且为整数定理3.5如果一个运输问题中的所有发量和所有收量都是整数，那么它的每一个基可行解中的所有变量也都取整数值。运筹学,0),,2,1(,),,2,1(,..min111111ijnjjmiijmiijinjijminjijijxbanjbxmiaxtsxcz运输问题的数学模型：运筹学111111111111111111111111212222111211nnnnnnxxxxxxxxxnAr2)(运筹学1111111111111111312111211nnxxxxxxBABABABAnBmAnm)1(*0,*0阶为阶，为12)(nAr运筹学指派问题解的特点：任何一个可行解由n2个xij组成；基变量为2n-1个；n个为1，其余为0；n个1位于解矩阵的不同行不同列上，对应的效率矩阵中的n个cij也位于不同行不同列上。运筹学nnnnnnccccccccc212222111211ijninjijxcz11minnnnnnnxxxxxxxxx212222111211运筹学匈牙利解法匈牙利解法是库恩于1955年利用匈牙利数学家康尼格的关于矩阵中独立0元素的定理，提出的一种算法，因而得名。运筹学匈牙利解法的关键是利用了指派问题最优解的以下性质：若从系数矩阵C的某行或某列各元素分别减去一个常数k，得到新矩阵C’，则以C和C’为系数矩阵的两个指派问题有相同的最优解。.)(,,,.)(6.3''''有相同的最优解与为效率矩阵的指派问题则以为常数其中改变为的元素现将指派问题为效率矩阵的设给定了以定理GGcCcccCGcCijjijiijijijij运筹学匈牙利解法的步骤：1、变换效率矩阵，使每行每列至少有一个0元素。方法：先对各行元素分别减去本行中的最小元素，再对各列元素分别减去本列中的最小元素。6635546967582543-2-5