运筹学第三版之第三章运输问题

运筹学第三版之第三章运输问题第三章运输问题运输问题的数学模型表上作业法产销不平衡的运输问题求初始基可行解的方法：西北角法、最小元素法、元素差额法基可行解的改进方法：闭回路调整法、位势法例：某运输问题的资料如下：单位销地运价产地产量2910791342584257销量3846一、运输问题的数学模型试制定一个调运方案，使得总运费最省？

数学模型的一般形式

已知资料如下：单位销运价地产地产量销量当产销平衡时，其模型如下：(3.1)当产大于销时，其模型是：(3.2)当产小于销时，其模型是：(3.3)

运输问题的特征：1、平衡运输问题必有可行解，也必有最优解；证设m行n行第i行第m+j行3、运输问题的基可行解中应包括m+n－1个基变量。前2~m行后n行闭回路：凡是能排列成形式的变量集合，若用一条封闭折线将它们连接起来形成的图形称为一个闭回路，其中诸变量称为闭回路的顶点，连接相邻两个顶点及最后一个顶点与第一个顶点的线段称为闭回路的边。B1B2B3B4B5A1x11x14A2x21x22A3x32x35A4x44x45闭回路具有以下性质：(1)每一个顶点都是转角点；基格：闭回路的顶点闭回路在基格处可以直行，也可以拐弯，在空格处必须直行，不能拐弯。(2)每一条边都是水平线或垂直线，闭回路是由这些水平线或垂直线构成的一条封闭折线；(3)每一行(或列)若有闭回路的顶点，则必有两个。空格：基格外的格。闭回路的性质：充要条件是它不含闭回路。则加入空格后的m+n个格中必含有唯一的闭回路。二、初始基可行解的求法(表上作业法)运输问题(3.1)的解法主要有图上作业法和表上作业法两种。表上作业法又称为运输单纯形法，它是根据单纯形法的原理和运输问题的特征，设计出来的一种便于在表上运算的方法，作为一种迭代方法，它的主要步骤：(1)求一个初始基可行解(又称初始调运方案)；(2)判别当前的基可行解是否为最优解，若是，则迭代停止；否则，转下一步；(3)改进当前的基可行解，得新的基可行解，再返回(2)此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而备受欢迎。

1、西北角法（或左上角法）：遵循的原则：优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务。例1设有某物资共有3个产地A1,A2,A3,其产量分别为9,5,7个单位，另有4个销地B1,B2,B3,B4,其销量分别为3,8,4,6,已知由产地Ai运往销地Bj的单位运价见下表，问应如何调运,才能使总运费最省？1、求初始调运方案：单位销地运价产地B1B2B3B4产量A1291079A213425A384257销量3846单位销地运价产地B1B2B3B4产量A1291079A213425A384257销量3846首先安排产地A1与销地B1之间的运输业务，即从运价表上西北角(或左上角)位置x11开始分配运输量，并使x11取尽可能大的数值。现在产地A1的产量为9,而销地B1的需求量为3.故安排产地A1运送3个单位的货物给销地B1,即取x11=min{a1,b1}=min{3,9}=3，当产地A1运出3个单位货物后，还剩9-3=6个单位，此时销地B1的需求量已得到满足，此时A2,A3不可能再运送货物给销地B1了，此时将B1列划去；再在剩下的运价表上，重复上述过程，即决定x12306602203301160600A1运送6个单位货物给B2,此时A1的供应量为0，划去A1行，B2的需求量为2.用同样的方法得初始基可行解X(0)的各分量为：相应的目标函数值2、最小元素法遵循原则：优先安排单位运价最小的产地与销地之间的运输业务。依次安排最小元素、次小元素，从而得到一个初始基可行解。用此方法制定出来的调运方案，其总运费一般会比用西北角法制定的调运方案要省。单位销地运价产地B1B2B3B4产地A1291079A213425A384257销地3846例2用最小元素法制定例1的初始调运方案。第1个最小元素为c21=1,此时比较A2的产量和B1的销量此时取其最小值，x21=min{5,3}=3,则安排A2运送3个单位货物给B1,此时A2剩余2个单位，B1的需求量已满足，将B1列划去；再在剩余表格中找最小元素c24=2,此时令x24=min{2,6}=2则安排A2运送2个单位货物给B4,则A2的供应量已尽，B4余4个单位，则将A2行划去；再在剩余表格中重复以上过程，最终得初始调运方案。302204403305450500西北角法与最小元素法的比较西北角法的最大优点是实现简单，特别适合编制程序上机计算，但缺点是所制定的初始方案往往离最优解较远，后面的调整量较大。而最小元素法的最大优点是制定的初始方案一般离最优解较近，后面调整量较小。但要在一张大型的运价表上每次搜索最小元素，其计算量也是很可观的。当然，当问题的规模不大，用手工计算时，可以通过人的判断力，很快找到最小元素，因此，用手工计算时，一般采用最小元素法求初始调运方案较好。3、元素差额法元素差额法是在最小元素法的基础上改进的一种求初始方案的方法，在分配运量以确定产销关系时，不是从最小元素开始，而是从运价表中各行和各列的最小元素和次小元素之差额来确定产销关系，(按最大差额所在行或列中的最小元素安排产地与销地之间的运输业务)因此称为元素差额法。单位销地运价产地B1B2B3B4产地差额A1291079A213425A384257销地3846差额

3061512112212123358222500345221305972501100初始调运方案为1闭回路求检验数对于给定的调运方案(基可行解)，从非基变量xij出发作一条闭回路，要求该闭回路上其余的顶点均为基变量，并从xij开始将该闭回路上的顶点顺序编号(顺时针或逆时针均可)称编号为奇数的点为奇点，编号为偶数的点为偶点，则xij处对应的检验数为奇点处运价的总和与偶点处运价的总和之差。(理论依据：xij处的运量增加一个单位，则闭回路同行中顶点处运量减少一个单位,同列中顶点处运量增加一个单位，依此类推，直至考虑闭回路所有顶点.)闭回路的做法：从空格出发，遇基格可直行亦可拐弯，遇空格必须直行不可拐弯，目的是保证闭回路的顶点为基格。最优性判别与基可行解的改进检验数的求法单位销地运价产地B1B2B3B4产地A1

291079A213425A384257销地3846324345用最小元素法求出的例1的初始调运方案见下表-4x11的检验数为2-7+2-1=-4单位销地运价产地B1B2B3B4产地A1

291079A213425A384257销地3846324345用最小元素法求出的例1的初始调运方案见下表x13的检验数为10-2+4-9=33单位销地运价产地B1B2B3B4产地A1

291079A213425A384257销地3846324345用最小元素法求出的例1的初始调运方案见下表x22的检验数为3-9+7-2=-1-1单位销地运价产地B1B2B3B4产地A1

291079A213425A384257销地3846324345用最小元素法求出的例1的初始调运方案见下表x23的检验数为4-2+7-9+4-2=22单位销地运价产地B1B2B3B4产地A1

291079A213425A384257销地3846324345用最小元素法求出的例1的初始调运方案见下表x31的检验数为8-1+2-7+9-4=77单位销地运价产地B1B2B3B4产地A1

291079A213425A384257销地3846324345用最小元素法求出的例1的初始调运方案见下表x34的检验数为5-7+9-4=33单位销地运价产地B1B2B3B4产地A1

291079A213425A384257销地3846324345用最小元素法求出的例1的初始调运方案见下表-43-12732位势法求检验数首先写出运输问题的对偶问题由于运输问题的约束条件共有m+n个，前m个是关于产地的产量限制，后n个是关于销地销量的限制。因此对偶问题中的对偶变量也应有m+n个，前m个记为u1,u2,…,um,后n个记为v1,v2,…,vn,并记运输问题的对偶问题单纯形法中有一个重要的规定，即基变量对应的检验数为零，根据这一原理，可以建立关于ui,vj的方程组，可以很快求出ui,vj.设给定了一个初始调运方案，其基变量为于是得到如下的方程组这个方程组共有m+n-1个方程，可以证明此方程有解，而要确定的未知数共有m+n个，故其中必有一个自由未知量，取它为任意常数，就可以把其余的未知量解出来。例如取uij=0,就可以决定其余的ui和vj

vjui单位产地运价销地B1B2B3B4产地

0

A1

291079

A213425

A384257

销地3846324345用位势法求例1中的初始基可行解对应的检验数9－577－56由于闭回路法和位势法中，检验数的定义方式与单纯形法完全一致，因此最优性判别条件也完全一致。注意运输问题中的目标函数是求极小值，于是定理对于运输问题的一个基可行解，若所有的检验数则此基可行解必为最优解。基可行解的改进确定出基变量的方法利用闭回路调整法：从进基变量xrs出发作一条闭回路，并从xrs出发将该闭回路上的顶点顺序编号，则调整量为调整的方法是：在该闭回路上，将奇点处的运量加上Ө，偶点处的运量减去Ө，而表中的其余点处的运量不变，这样得到新的基可行解，进基变量的选择和单纯形法一样

vjui单位产地运价销地B1B2B3B4产地

0

A1

291079

A213425

A384257

销地3846324345对例1继续求解9－577－56

vjui单位产地运价销地B1B2B3B4产地

0

A1

291079

A213425

A384257

销地384643159－577－6235

vjui单位产地运价销地B1B2B3B4产地

0

A1

291079

A213425

A384257

销地384643609－577－6235由于检验数全非负，故现有的基可行解即为最优解，且最优调运方案为

1、产大于销：模型方法是先将原问题变成平衡问题，需假设一个销地(Bn+1)(实际上考虑产地的存量)，三、产销不平衡的运输问题及其求解方法模型为：2、销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例题：已知某运输问题的资料如下表所示B1B2B3B4产量A1265315A2132112A3327413销量10131251、表中的产量、销量单位为：吨，运价单位为：元/吨,试求出最优运输方案.练习1：2、如将A2的产量改为17，其它资料不变，试求最优调运方案。B1B2B3B4产量A112315A210212A313013销量1013125B1B2B3B4产量A1265315A2132112A3327413销量1013125解：1、用最小元素法求初始方案B1B2B3B4产量A112315A210212A313013销量1013125B1B2B3B4A153A211A324运费为108元/吨2、用位势法判断：B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4u1+v3=5u2+v4=1u1+v4=3u3+v2=2u2+v1=1u3+v4=4令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5v4＝3B1B2B3B4ui

A1530A211－2A3241vj

3153B1B2B3B4ui

A131530A21－131－2A342641vj

3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－131A34264cij－B1B2B3B4A1－1500A204－10A3－1010＝表中还有负数，说明没有得到最优解，调整运输方案。σij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的运送方案B1B2B3B4A153A212A324新的成本表B1B2B3B4ui

A141530A21－220－3A352641vj

4153(ui+vj)1

总的运费105元/吨B1B2B3B4A14153A21－220A35264B1B2B3B4A12653A21321A33274－＝B1B2B3B4A1－2500A20501A3－2010表中还有负数，说明没有得到最优解，继续调整运输方案。cij(ui+vj)1

(σij)1

013A3210A2510A1B4B3B2B13512vj

14623A3－302－2－1A203512A1ui

B4B3B2B1(ui+vj)2

42A32A2352A1B4B3B2B1新的成本表013A312A25010A1B4B3B2B1新的运送方案总的运费85元/吨B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A2－1－220A33264(ui+vj)2

－＝B1B2B3B4A10500A22501A30010

(σij)2

表中没有负数，说明已经得到最优解。但有无穷多最优解。013A312A2510A1B4B3B2B1最终的运送方案总的运费85元/吨B1B2B3B4产量A131215A27512A313013销量1013125B1B2B3B4产量A1265315A2132112A3327413销量1013125B1B2B3B4A125A211A327B1B2B3B4ui

A125u1A211u2A327u3vj

v1v2v3v4成本表u1+v1=2u2+v4=1u1+v3=5u3+v2=2u2+v1=1u3+v3=7令：u1＝0u1＝0v1＝2u2＝－1v2＝0u3＝2v3＝5v4＝2B1B2B3B4ui

A120520A21-141-1A342742vj

2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui

A10601A204-20A3-1000vj

σijB1B2B3B4产量A131215A27512A313013销量1013125B1B2B3B4产量A110515A27512A313013销量1013125B1B2B3B4B5产量A110515A2102517A313013销量10131255B1B2B3B4B5产量A12653015A21321017A33274013销量101312552.B1B2B3B4B5A150A2121A324B1B2B3B4B5ui

A150u1A2121u2A324u3vj

v1v2v3v4v5成本表u1+v3=5u2+v3=2u1+v5=0u2+v4=1u2+v1=1u3+v2=2u3+v4=4令：u1＝0u1＝0v1＝4u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1425400A21-121-3-3A3425400vj

42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1-240-10A204004A3-10200σij505B45121310销量1313A317210A215510A1产量B5B3B2B1B1B2B3B4B5产量A1100515A212517A313013销量10131255B1B2B3B4B5A1250A221A324B1B2B3B4B5ui

A1250u1A221u2A324u3vj

v1v2v3v4v5成本表u1+v1=2u2+v4=1u1+v3=5u3+v2=2u1+v5=0u3+v4=4u2+v3=2令：u1＝0u1＝0v1＝2u2＝-3v2＝2u3＝0v3＝5v4＝4v5＝0B1B2B3B4B5ui

A1225400A2-1-121-3-3A3225400vj

22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1040-10A224004A310200σijB1B2B3B4B5产量A1100515A212517A313013销量10131255B1B2B3B4B5产量A1100515A212517A313013销量10131255B1B2B3B4B5产量A110515A212517A31313销量10131255C=75已知资料如下表所示，问如何供电能使总的输电费用为最小？发电厂发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表B1B2B3B4A110523A24312A35634单位输电费用作业1单位城市输电发电厂费用B1B2B3B4发电量A1105