运筹学3.运输问题

1、1第三章第三章 运输问题运输问题本章主要内容本章主要内容： 运输问题的数学模型运输问题的数学模型 运输问题的求解运输问题的求解表上作业法表上作业法 运输问题应用运输问题应用建模建模2 第一节第一节 运输问题的数学模型运输问题的数学模型 第二节第二节 表上作业法表上作业法 第三节第三节 产销不平衡的运输问题产销不平衡的运输问题 第四节第四节 应用举例应用举例3第一节第一节 运输问题的数学模型运输问题的数学模型一、数学模型一、数学模型的运量。则的运量。则到到表示表示设设jiijBAx232221131211556646xxxxxxMinZ 3 , 2 , 1; 2 , 1; 02001501503

2、00200.231322122111232221131211 jixxxxxxxxxxxxxtsij例例1 1销地销地产地产地B1B2B3aiA1646200A2655300bj150150200500产地：货物发出的地点产地：货物发出的地点销地：货物接收的地点销地：货物接收的地点产量：各产地的可供货量产量：各产地的可供货量销量：各销地的货物需求量销量：各销地的货物需求量运输问题就是研究如何组织调运，既满足各销运输问题就是研究如何组织调运，既满足各销售地的需求，又使得总运费最小。售地的需求，又使得总运费最小。4二、运输问题的一般数学模型二、运输问题的一般数学模型 设设xij表示产地表示产地 i

3、 运往销地运往销地 j 的物资量，的物资量，cij表示对应的单位运费表示对应的单位运费 令令a1, a2, , am表示各产地产量表示各产地产量, b1, b2, , bn表示各销地的销量表示各销地的销量 有有m个地区生产某种物资，有个地区生产某种物资，有n个地区需要该类物资个地区需要该类物资产销平衡表产销平衡表单位运价表单位运价表 销地销地产地产地1 2 n 1 2 m a1 a2 am销量销量b1 b2 bn 销地销地产地产地 1 2 n 1 2 mc11 c12 c1nc21 c22 c2n.cm1 cm2 cmn5 0 , 2 , 1 , 2 , 1.1111ijjmiijnjiijm

4、injijijxnjbxmiaxtsxwMinZ销销量量约约束束产产地地约约束束cij xij产量约束产量约束一般满足产销平衡：一般满足产销平衡：11mnijijab 产量约束：由某一产地运往各个销售地的物品数产量约束：由某一产地运往各个销售地的物品数量之和等于该产地的产量。量之和等于该产地的产量。销量约束：由各个产地运往某一销售地的物品数销量约束：由各个产地运往某一销售地的物品数量之和等于该销售地的销量。量之和等于该销售地的销量。6产大于销产大于销 njjmiiba11 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 销地销地产

5、地产地1 2 n 1 2 m a1 a2 am销量销量b1 b2 bn7产小于销（销大于产）产小于销（销大于产） njjmiiba11 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 销地销地产地产地1 2 n 1 2 m a1 a2 am销量销量b1 b2 bn8定理定理1 运输问题的数学模型必有最优解。运输问题的数学模型必有最优解。 首先，运输问题一定有可行解；其次，任何单位运价cij0，从而对于任一可行解，必有目标函数值大于或等于零，即目标函数有下界。所以，求解运输问题时，不需要进行无最优解的判别。1112112122221

6、211211112222212nnmmmnmmmnnmnnxxxaxxxaxxxaxxxbxxxbxxxb产量平衡产量平衡（m个）个）销量平衡销量平衡（n个）个）9在例在例1 1中，运输问题的系数矩阵为：中，运输问题的系数矩阵为：1.1.一般情况下一般情况下, ,运输问题运输问题决策变量决策变量xij的的系数列向量为系数列向量为: :三、变量三、变量xij的系数列向量的特征的系数列向量的特征 000000000000001111111111100100 )(Ar111213212223xxxxxx0110ijimjiPeemj 位位置置位位置置4132 2.2.系数矩阵的元素等于系数矩阵的元素

7、等于0 0或或1 1。101112112122221211211112222212nnmmmnmmmnnmnnxxxaxxxaxxxaxxxbxxxbxxxb3.3.运输问题系数矩阵的秩为运输问题系数矩阵的秩为m+n-1。3.3.运输问题基变量的个数为运输问题基变量的个数为m+n-1。111. 概念概念例例21)1)数字格数字格2)空格空格3)3)闭回路闭回路四、闭回路四、闭回路销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620闭回路：闭回路：以某空格为起点，用水平或垂直线向前划，当碰到某以某空格为起点，用水平或垂直线向前划，当碰到某恰当的数字

8、格后，转恰当的数字格后，转90900 0继续前进，直到回到起始空格为止。继续前进，直到回到起始空格为止。12销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620（1 1）每个顶点都是转角；）每个顶点都是转角；（2 2）每行或每列有且仅有两个顶点；）每行或每列有且仅有两个顶点；（3 3）每个顶点的连线都是水平的或垂直的；）每个顶点的连线都是水平的或垂直的；（4 4）除起点外，其余各顶点都是数字格。）除起点外，其余各顶点都是数字格。13销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj36562014销地销地产地

9、产地B1B2B3B4aiA13113107A219284A3741059bj36562015 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj36562016 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj36562017 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620182.2.闭回路与变量所对应的系数列向量组线性相关性的关系闭回路与变量所对应的系数列向量组线性相关性的关系结论结论1 1 运输问题一组变量构成闭回路的充要条件是这组运输问题一组变量构成闭回路的

10、充要条件是这组变量所对应的系数列向量线性相关变量所对应的系数列向量线性相关例如，闭回路（例如，闭回路（x11, x21, x23, x13） 000000000000001111111111100100111213212223PPPPPP销地销地产地产地B1B2B3aiA1646200A2655300bj150150200500192.2.闭回路与变量所对应的系数列向量组线性相关性的关系闭回路与变量所对应的系数列向量组线性相关性的关系结论结论2 2 运输问题的一个可行解是基可行解的充要条件是：运输问题的一个可行解是基可行解的充要条件是：1 1）数字格的个数为）数字格的个数为m+n-1个；个；2

11、 2） 这这m+n-1个数字格不构成闭回路。个数字格不构成闭回路。（x11, x21, x23, x12） 000000000000001111111111100100111213212223PPPPPP结论结论3 3 对每一个空格处，有且仅有一条闭回路。对每一个空格处，有且仅有一条闭回路。销地销地产地产地B1B2B3aiA1646200A2655300bj15015020050020一、表上作业法的步骤一、表上作业法的步骤第二节第二节 表上作业法表上作业法最优性检验最优性检验结结 束束Y调调 整整N确定初始确定初始基可行解基可行解在在m mn n维产销维产销平衡表上找到平衡表上找到m+n-1

12、m+n-1个数字格个数字格0?ij 确定进基确定进基变量和出变量和出基变量基变量21 表上作业法步骤：初始方案、最优性检验、改进方案表上作业法步骤：初始方案、最优性检验、改进方案一、初始方案的确定一、初始方案的确定1.1.最小元素法最小元素法2.2.伏格尔法伏格尔法二、最优性检验二、最优性检验1.1.闭回路法闭回路法2.2.位势法位势法三、改进方案三、改进方案 在闭回路内改进在闭回路内改进221.1.最小元素法最小元素法( (就近供应就近供应) )就进供应，即从单位运价表中最小的运价开始确定供销就进供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到求出初始基可行解为止。关系，然

13、后次小，一直到求出初始基可行解为止。例例3 3865310334214613 Z二、初始基可行解的确定二、初始基可行解的确定销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj36562023例例3 3865310334214613 Z销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620最小元素法给出的初始解是运输问题的基可行解。最小元素法给出的初始解是运输问题的基可行解。242.2.伏格尔法（伏格尔法（VogelVogel）第一步：求出每行次小运价与最小运价之差；同时求第一步：求出每行次小运价与最小运价之差；

14、同时求出每列次小运价和最小运价之差；出每列次小运价和最小运价之差；第二步：找出所有行、列差额的最大值，差额最大值第二步：找出所有行、列差额的最大值，差额最大值所对应的行或列中的最小运价处先调运；所对应的行或列中的最小运价处先调运；第三步：这时必有一列或一行调运完毕，划去该列或第三步：这时必有一列或一行调运完毕，划去该列或该行，在剩下的运价中再求最大差额，进行第二次调该行，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，得到一运，依次进行下去，直到最后全部调运完毕，得到一个调运方案。个调运方案。一产地的产品假如不能够按照最小运价就近供应，就一产地的产品假如不能够按

15、照最小运价就近供应，就考虑次小运价。最小运价和次小运价的差额越大，说考虑次小运价。最小运价和次小运价的差额越大，说明不能按最小运价调运时，运费增加越多。明不能按最小运价调运时，运费增加越多。252.2.伏格尔法（伏格尔法（VogelVogel）85538335461132 Z例例4 4销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620011012 2 5 1 32-1301-2-1201-2-1- 26在以上两种方法中，有几点需要注意：在以上两种方法中，有几点需要注意： 这两种方法得出的解均为初始可行解。这两种方法得出的解均为初始可行解。 一般

16、由伏格尔法得出的解比最小元素法得出的解一般由伏格尔法得出的解比最小元素法得出的解更接近最优解。更接近最优解。 在以上方法过程中，不可同时划去行和列。在以上方法过程中，不可同时划去行和列。271.1.闭回路法闭回路法 例例5 5注注: 1)数字格检数字格检验数均为验数均为0显然该问题至此尚未达到最优解。显然该问题至此尚未达到最优解。三、求检验数并进行最优解的判定三、求检验数并进行最优解的判定销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620121-110121133211 121110542 偶偶奇奇空格检验数空格检验数ijijijcc)2解。解

17、。时，运输问题达到最优时，运输问题达到最优当所有当所有最优性判别准则：最优性判别准则：0 ij2811(32)(13)1 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj3656202912(115)(410)2 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj3656203022(953)(4102)1 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj3656203124(83)(210)1 销地销地产地产地B1B2B3B4aiA13113107A219284A374105

18、9bj3656203231(7102)(531)10 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj3656203333(1010)(53)12 销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620342.2.位势法位势法例例6 6 由最小元素法得出初始解由最小元素法得出初始解, ,如下表如下表ijjicvu 对对数数字字格格而而言言计计算算）行行势势、列列势势的的定定义义与与注注：:13）行势、列势可不唯一，但检验数是一致的。）行势、列势可不唯一，但检验数是一致的。销地销地产地产地B1B2B3B4aiA

19、13113107A219284A3741059bj3656200),()2 ijjiijijvuc数字格数字格检验数的计算：空格检验数的计算：空格35 ), 1;, 1( , 0.)(1111njmixbxaxtsxcMinZLijjmiijinjijminjijij 无约束无约束jiijjinjjjmiiivucvutsvbuaMaxZD,.)(110)()()(),(,)()(),()0(0)0()0()0()0()0(0)0( ijjiijjiijjiijcvuxDLvuxDLvux）（）（的的最最优优解解的的充充要要条条件件是是、是是、则则的的可可行行解解、是是、结结论论：设设位势法的

20、理论依据（互补松弛定理）位势法的理论依据（互补松弛定理）36位势法的理论依据位势法的理论依据运输问题运输问题min0fCXAXbX 设设B B为一可行基，则相为一可行基，则相应的基可行解的各变应的基可行解的各变量的检验数为量的检验数为运输问题的对偶问题运输问题的对偶问题maxzYbYACY 不不受受限限制制11(,)mnYuuvv 由对偶理论有由对偶理论有 Y=CBB-1ijijijcYp ijimjpee 11(,)()ijijijijmnijijijcYpcuuvvpcuv 基变量的检验数等于基变量的检验数等于0()0( , )ijijijijcuvuvci jI即即1ijijBijcC

21、Bp （I：基变量下标集基变量下标集）37位势法的计算过程位势法的计算过程 令令u1=0 按按ui+vj=cij相相继确定其他数继确定其他数字格的字格的ui和和vj 计算空格的检验数。如计算空格的检验数。如 11=3-(0+2)=1因为因为24=-10,因而该问题至此尚未达到最优解因而该问题至此尚未达到最优解.销地销地产地产地B1B2B3B4A1311310A21928A374105uivj0310-1-529121-1101238位势法的步骤位势法的步骤 对于每一个基变量（数字格）都按照公式对于每一个基变量（数字格）都按照公式 ui+vj=cij 列列出一个位势方程，形成位势方程组（出一个位

22、势方程，形成位势方程组（m+n-1个）；个）； 任意决定其中一个位势的数值，然后求出其他位势的任意决定其中一个位势的数值，然后求出其他位势的数值；数值； 按照公式按照公式 计算非基变量（空格处）计算非基变量（空格处）的检验数（的检验数（mn-(m+n-1)个）。个）。()ijijijcuv 39 从最小负检验数所对应的空格进行调整从最小负检验数所对应的空格进行调整例例7 7 对由最小元素法得出的初始解进行调整对由最小元素法得出的初始解进行调整调整方法：调整方法：1）找出负检验）找出负检验数所在空格处的数所在空格处的闭回路闭回路2）在闭回路上找到）在闭回路上找到偶数点所对应的基偶数点所对应的基变

23、量的最小值变量的最小值514; 110; 213; 011 即即再再按调整后的解由位势法计算空格的检验数按调整后的解由位势法计算空格的检验数四、调整四、调整销地销地产地产地B1B2B3B4A1311310A21928A374105121-11012 x23 x14 x24 x133 3）以此最小值）以此最小值为为调整量，在奇数格加调整量，在奇数格加上该调整量，在偶数上该调整量，在偶数格上减去该调整量格上减去该调整量换入变量：换入变量：x24换出变量：换出变量：x23401.1.由最小元素法求得初始基可行解由最小元素法求得初始基可行解865310334214613 Z五、典型运输问题解题步骤示例

24、五、典型运输问题解题步骤示例销地销地产地产地B1B2B3B4aiA13113107A219284A3741059bj365620412.2.由位势法求检验数由位势法求检验数 令令u1=0 按按ui+vj=cij相相继确定其他数继确定其他数字格的字格的ui和和vj 计算空格的检验数计算空格的检验数因为因为24=-10,因而该问题至此尚未达到最优解因而该问题至此尚未达到最优解.销地销地产地产地B1B2B3B4A1311310A21928A374105uivj0310-1-529121-11012()ijijijcuv 如如11=3-(0+2)=1423.3.从最小负检验数所对应的空格进行调整从最小

25、负检验数所对应的空格进行调整调整方法：调整方法：1）找出闭回路）找出闭回路2）使最小负检验数）使最小负检验数所对应的空格达到所对应的空格达到最大的调整量最大的调整量1514; 110; 213; 011 即即销地销地产地产地B1B2B3B4A1311310A21928A374105121-1101243 令令u1=0 按按ui+vj=cij相相继确定其他数继确定其他数字格的字格的ui和和vj 计算空格的检验数。如计算空格的检验数。如11=3-(3+0)=0因为所有的因为所有的ij0,至此该问题已经达到最优解至此该问题已经达到最优解.855346811310235 Z最最优优解解4.4.再按调整

26、后的解由位势法计算空格的检验数再按调整后的解由位势法计算空格的检验数销地销地产地产地B1B2B3B4A1311310A21928A374105 uivj0310-2-539022 912144表上作业法的步骤：表上作业法的步骤：（1 1）编制调运表（产销平衡表、单位运价表）编制调运表（产销平衡表、单位运价表）（2 2）在调运表上求出初始基可行解）在调运表上求出初始基可行解（3 3）用位势法或闭回路法计算非基变量的检验数，若所）用位势法或闭回路法计算非基变量的检验数，若所有非基变量的检验数均大于等于有非基变量的检验数均大于等于0 0，则已得到问题的最，则已得到问题的最优解优解（4 4）选取小于）

27、选取小于0 0的检验数中的最小者所对应的非基变量的检验数中的最小者所对应的非基变量作为进基变量，用闭回路法进行基可行解的转换，得作为进基变量，用闭回路法进行基可行解的转换，得到新的基可行解，转入步骤（到新的基可行解，转入步骤（3 3）。）。45可能出现的几种情况可能出现的几种情况（1 1）无穷多最优解无穷多最优解 某一个非基变量（空格处）的检验数为某一个非基变量（空格处）的检验数为0 0；销地销地产地产地B1B2B3B4A1311310A21928A374105 022 912146可能出现的几种情况可能出现的几种情况（2 2）退化退化 同时划去一行和一列；同时划去一行和一列； 在用闭回路法调

28、整时，同时有两个或两个以上的偶在用闭回路法调整时，同时有两个或两个以上的偶数顶点具有最小值数顶点具有最小值销地销地产地产地B1B2B3B4aiA1311457A277384A3121069bj36562047一、原理一、原理 njjmiiijjmiijinjijbanjmixbxax1111), 1;, 1( ,000有有解解的的充充要要条条件件是是：定定理理：方方程程组组第三节第三节 产销不平衡的运输问题产销不平衡的运输问题48证明：证明： njjnjmiijminjijmiijmiijinjijijijbxxabxaxxx111)0(11)0(11)0(1)0()0()0(,01而而则则是

29、是方方程程组组的的解解，且且设设）先先证证必必要要性性（jmiijinjjinjjinjijjiijijjijinjjmiinjjmiibxababaxbaxiixbabaibaba 1)0(111)0()0()0(11110000000,)2(同同理理。则则，令令）又又若若（是是方方程程组组的的解解。则则，则则，由由于于）若若（记记若若再再证证充充分分性性49结论：结论： 1. 1. 运输问题有可行解运输问题有可行解 产销平衡产销平衡 2. 2. 运输问题有可行解运输问题有可行解 运输问题有最优解运输问题有最优解 3. 3. 运输问题有最优解运输问题有最优解 产销平衡产销平衡500,),(.

30、11,11,1111111111 ninininjjmiinjjmiinnnnjjmiicBAxbababBBba的的运运量量，且且到到表表示示从从，的的需需要要量量为为销销地地则则虚虚设设一一个个销销地地销销若若产产二、产销不平衡问题的处理二、产销不平衡问题的处理 销地销地产地产地1 2 n n+1 1 2 m a1 a2 am销量销量b1 b2 bn bn+151 1111111,2,. .1,2,10m nijijijnijijmijjiijMinZc xxaimstxbjnx 地地 束束量量 束束产量约束产量约束销量约束销量约束m+n+1个约束条件个约束条件m(n+1)个决策变个决策变

31、量量 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 520,),(.2,11,11111111111 jmjmjmnjjmiimiinjjmmmnjjmiicBAxbaabaAAba的的运运量量，且且到到表表示示从从，的的产产量量为为：则则虚虚设设一一个个产产地地销销若若产产二、产销不平衡问题的处理二、产销不平衡问题的处理 销地销地产地产地1 2 n 1 2 mm+1 a1 a2 amam+1销量销量b1 b2 bn53 1111111,2,1. .1,2,0mnijijijnijijmijjiijMinZc xxaimstxb

32、jnx 地地 束束量量 束束产量约束产量约束销量约束销量约束m+n+1个约束条件个约束条件(m+1)n个决策变个决策变量量 11111,2,. .1,2,0mnijijijnijijmijjiijMinZc xxaims txbjnx 54例例8 8 求下面运输问题的最优解求下面运输问题的最优解 这是一个产大于销的运输问题，增加一个假想的销这是一个产大于销的运输问题，增加一个假想的销售地，可以将其转化为产销平衡问题。售地，可以将其转化为产销平衡问题。销地销地产地产地甲甲乙乙丙丙丁丁戊戊产量产量12341021820102065873930107106455629销量销量4462455 假设假设

33、“己己”的虚拟销量为的虚拟销量为2 2，各实际产地到其的运费为，各实际产地到其的运费为0 0。如下表所示：。如下表所示：用用表上作业法可以求出最优解。表上作业法可以求出最优解。销地销地产地产地甲甲乙乙丙丙丁丁戊戊己己产量产量123410218201020658739301071064500005629销量销量44624222注：用最小元素法时，某列单位运价为注：用最小元素法时，某列单位运价为0，应该最后考虑，应该最后考虑56例例9 9 产销不平衡问题（书产销不平衡问题（书P90P90例例2 2） 在产销平衡表中增加一个假想的化肥厂在产销平衡表中增加一个假想的化肥厂D D，年产量为年产量为505

34、0万吨；将需求分两种情况的地区，实际按两个地区看待。万吨；将需求分两种情况的地区，实际按两个地区看待。需求地区需求地区化肥厂化肥厂IIIIIIIV产量产量（万吨）（万吨）ABC1614191313202219231715-506050最低需求（万吨）最低需求（万吨）最高需求（万吨）最高需求（万吨）305070700301060 160110,21057这样可将该问题化为产销平衡问题：这样可将该问题化为产销平衡问题：需求地区需求地区化肥厂化肥厂IIIIIIIIVIV产量产量（万吨）（万吨）ABCD161419M1614190131320M22192301715MM1715M050605050销量（万吨）销量（万吨）30207030105021058根据表上作业法计算，可得该