第5章-运输问题a

第五章运输问题5.1运输问题的数学模型5.2初始基可行解的确定5.3最优性检验与基可行解的改进5.4其他运输问题1§5.1运输问题的数学模型及其特征●有m个产地A1,A2,…,Am生产某种物资，另有n个销地B1,B2,…,Bm需要该类物资；●令a1,a2,…,am表示各产地产量，b1,b2,…,bn表示各销地的销量,若

ai=

bj，则称产销平衡；●设xij表示产地i运往销地j的物资量，cij表示对应的单位运费。2如何调运，使总的运输费用最小？供需平衡表bn…b2b1销量BnB2B1需方供方AmA2A1ama2a1产量cmncm2cm1c2nc22c21c1nc12c11…………3

销产B1B2…Bn产量A1c11x11c12x12…c1nx1na1A2c21x21c22x22…c2nx2na2┇┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnam销量b1b1…bn平衡表、运价表合二为一4(1)运输问题数学模型xij——供应节点i至需求节点j的运输量；aij

——供应节点i的可供应量，i=1,2,…,m；bij——需求节点j的需求量，j=1,2,…,n；cij

——供应节点i至需求节点j的单位运输成本。5根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题和不平衡型运输问题。平衡型运输问题：不平衡型运输问题：对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。(2)运输问题的分类6产销平衡运输问题的数学模型：Ai的产品全部供应出去Bj的需求全部得到满足7平衡型运输问题的数学模型模型包含变量：m×n个约束方程：m+n个秩：r(A)=m+n-1m行n行稀疏矩阵8产大于销运输问题的数学模型：Ai的产品没有全部供应出去Bj的需求全部得到满足9销大于产运输问题的数学模型：Ai的产品全部供应出去Bj的需求没有全部得到满足以下主要讨论产销平衡运输问题的数学模型10例1.现有A1，A2，A3三个产地，可供应物资分别为10，8，5个单位，现将物资运往B1，B2，B3，B4四个销地，销量分别为5，7，8，3个单位。产地到销地的单位运价cij如表1所示，问如何安排一个运输计划，使总的运输费用最少。销地产地B1B2B3B4产量A1326310A253828A341295需要量578323表111解：设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：Min

z=3x11+2x12+6x13+3x14+5x21+3x22+8x23+2x24

+4x31+x32+2x33+9x34xij0,i=1,2,3;j=1,2,3,412有些问题表面上与运输问题没有多大关系，但经过转换，也可以建立与运输问题形式相同的数学模型。例2.有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如表2所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150表213解：设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为14(3)平衡型运输问题的对偶问题由于r(A’)=m+n-1，独立的约束方程个数为m+n-1;而变量个数为m+n，则其中有一个自由变量15(4)运输问题的特征定理1：平衡运输问题必有可行解与最优解。证：对于平衡运输问题令：16则有所以是运输问题的一个可行解。又由于所以且为极小化问题，故一定存在最优解。17定理2平衡运输问题的约束方程系数矩阵A的秩r(A)=m+n-1。证：因为产销平衡，即，将前m个约束方程两边相加得再将后n个约束相加得显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的,所以A中任意m+n阶子式等于零.18A中任意m+n阶子式等于零.再取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式Bm行n行19故r(A)=m+n－1.推论1平衡运输问题的基可行解中应包含m+n-1个基变量。20为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。定义1凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。或21

x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12

x25x31

x42表3表3中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表3中的变量x32及x33不是回闭路的顶点，只是连线的交点。22表4中闭回路是例如变量组A不能组成一条闭回路，但A中包含有闭回路B的变量数是奇数，显然不是闭回路，也不含有闭回路.x11x12x32x33x41

B1B2B3A1

A2

A3

A4

x43表423（1）每个顶点都是转角点；（2）每一条边都是水平线段或垂直线段；（3）每一行（或列）若有闭回路的顶点，则必有两个.闭回路的几何性质：x11x12x32x33x41

B1B2B3A1

A2

A3

A4

x43表424性质1若变量组B包含有闭回路，则B中的变量对应的列向量线性相关。证：由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即因而C中的列向量线性相关，所以B中列向量线性相关。闭回路的代数性质：推论：若一个变量组对应的系数列向量线性无关，则该变量组一定不包含闭回路。25定义2在变量组中，若有某一变量xij是它所在的行（第i行）或列（第j列）中出现在该变量组中的唯一变量，则称该变量为孤立点。x12x32x41

B1B2B3A1

A2

x21

x23A3

A4

性质2若变量组C中不包含任何闭回路，则该变量组中必有孤立点。26求运输问题的一组基变量，就是要找到m+n－1个变量，使得它们对应的系数列向量线性无关，由性质1，找这样的一组变量是很容易的，只要m+n－1个变量中不包含闭回路，就可得到一组基变量。因而有：定理3平衡运输问题中的一组m+n－1个变量构成基变量的充要条件是它不包含任何闭回路。（证略）定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个平衡运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。27例如，m=3,n=4，在运价表cij的格子的右上方填上相应的xij，如表5所示。表5

BjAiB1B2B3B4aiA1

x11

x12

x13

x14

a1C11C12C13C14A2

x21

x22

x23

x24a2C21C22C23C24A3

x31

x32

x33

x34a3C31C32C33C34bjb1b2b3b4

基变量：28这个运输问题的基变量数目是3+4－1=6。变量组中有7个变量，显然不能构成一组基变量，又如中有6个变量，但包含有一条闭回路故不能构成一组基变量。变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。29运输问题是一类特殊的线性规划问题对于平衡型运输问题：约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。存在最优解当供应量和需求量均为整数时，存在整数最优解。基可行解中基变量个数为m+n-1个基可行解中基变量的重要特征：不含闭回路。小结：运输问题的基本性质30本节介绍了具有m个产地n个销地的平衡运输问题1.具有m+n－1个基变量2.闭回路的概念3.怎样判断m+n－1个变量是否构成一组基变量1、单纯形法（为什么？）2、表上作业法由于问题的特殊形式而采用的更简洁、更方便的方法运输问题的解法:31(1)找出初始调运方案（初始基可行解）。即在(m×n)产销平衡表上给出m+n-1个数字格。(4)重复（2）、（3），直到求得最优调运方案。计算步骤：(2)求检验数。（闭回路法或位势法）判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)对方案进行改善（改进当前的基可行解），找出新的调运方案（新的基可行解）。（表上闭回路法调整）运输问题的解法——表上作业法32§5.2初始基可行解的求法获得初始基可行解（初始方案）的常用方法:(1)西北角法(2)最小元素法(3)*元素差额法（Vogel近似法）33

例3运输问题供需平衡表和运价表如下，求初始调运方案。

供需B1B2B3B4产量A13113107A219284A3741059销量36562034（1）西北角法----“就近供应”

该方案总运费Z=3×3+4×11+2×9+2×2+3×10+6×5=135优先满足运输表中西北角(即左上角)上空格的供销需求7-3=46-4=24-2=25-2=39-3=6修正量修正量例3初始调运方案:x11=3,x12=4,x22=2,x23=2,x33=3,x34=6(基变量)35813131466(1)西北角法西北角法的缺点：没有考虑运价大小，不尽合理总运费Z=35036（2）最小元素法优先安排单位运价最小的产销之间的业务314

633该方案总运费Z=4×3+3×10+3×1+1×2+6×4+3×5=86例337最小元素法实施步骤口诀《运价表》上找最小，《平衡表》上定产销；满足销量划去“列”，修改“行产”要记牢；（满足产量划去“行”，修改“列销”要记牢）划去列(行)对《运价》，修改“行产(列销)”在《产销》；余表再来找最小，方案很快就找到。38(2)最小元素法(0)39(2)最小元素法(1)40(2)最小元素法(2)41(2)最小元素法(3)42(2)最小元素法(4)43(2)最小元素法(5)44(2)最小元素法(6)总运费Z=22245课堂练习1用最小元素法求下列运输问题的初始方案销地产地ABC产量甲8574乙9464丙1323销量326111146课堂练习解答销地产地ABC产量甲8574乙9464丙1323销量32611114220347课堂练习答案销地产地ABC产量甲8574乙9464丙1323销量326111142203运费z=51退化的基可行解(x33=0)48（3）(元素差额法)Vogel法分别计算各行、各列最小与次小运价的差额，优先在最大差额处进行供需搭配。步骤：10计算未划去行、列的差额；20找出最大差额对应的最小元素cij进行供需分配；30在未被划去的行、列重新计算差额。例349销产B1B2B3B4供量A17A24A39销量

3656

6B1B2B3B4行差额A13113100A219281A3741051列差额251350销产B1B2B3B4供量A17A24A3

9销量

3656

6B1B2B3B4行差额A13113100A219281A3741052列差额213351销产B1B2B3B4供量A17A24A3

9销量

36566B1B2B3B4行差额A13113100A219281A374105列差额2123352

销产B1B2B3B4供量A17A24A3

39销量

3656

6B1B2B3B4差额A13113107A219286A374105差额12

3

5

1

2该方案总运费Z=1×3+4×6+3×5+10×2+8×1+5×3=8553(3)Vogel法（元素差额法）2211333123311331314413131912总运费Z=22254课堂练习2销地产地ABC产量甲51710乙64680丙32520销量402050110110用Vogel法求下列运输问题的初始方案55课堂练习2解答销地产地ABC产量甲51710乙64680丙32520销量402050110110行差额421211*1032*2000020501056课堂练习2答案销地产地ABC产量甲51710乙64680丙32520销量4020501101101020205010运费Z=53057§5.3最优性检验与基可行解的改进1.最优性检验充要条件由于基变量的检验数σij=0,只需确定非基变量的检验数！确定非基变量检验数的常用方法主要是：闭回路法——非基变量与基变量构成唯一闭回路位势法——利用对偶变量58（1）闭回路法

●以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。

●该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。

●可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。59检验数的求法:闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90°，然后继续前进，直到到达出发的空格所形成的闭合回路。销产B1B2B3B4供量A1527A2314A36

39销量

3656差额法方案(1)闭回路法例3σij=闭回路上奇点运价之和-闭回路上偶点运价之和60调运方案的任意空格存在唯一闭回路。销产B1B2B3B4供量A1527A2314A36

39销量

365661314

633最小元素法方案+-+-经济解释：若x11为换入变量，则x11增加1，x13减少1…,运费的变化为(+1)×3+(-1)×3+(+1)×2+(-1)×1=c11-c13+c23-c21=1，总运费将增加，不合理。这个变化就是x11的检验数，故σ11=1例362空格闭回路检验数σij

(11)(12)(22)(24)(31)(33)(11)-(13)-(23)-(21)-(11)(12)-(14)-(34)-(32)-(12)(22)-(23)-(13)-(14)-(34)-(32)-(22)(24)-(23)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)121-11012销产B1B2B3B4产量A1A2A3364133749销量3656例3最小元素法方案σ24=-1＜0，当前方案不是最优方案。63(1)闭回路法(0)645(1)闭回路法(1)σ12=c12-c11+c21-c22=7-6+8-4=565-55(1)闭回路法(2)σ13=c13-c11+c21-c23=5-6+8-2=566557(1)闭回路法(3)σ14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=7677559σ24=c24-c23+c33-c34=7-2+10-6=9(1)闭回路法(4)687955-11σ31=c31-c33+c23-c21=5-10+2-8=-11(1)闭回路法(5)697559-11-3σ32=c32-c33+c23-c22=9-10+2-4=-3(1)闭回路法(6)70(2)位势法对偶规划由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-1，我们可以通过设定自由变量的值得到所有对偶变量。——位势71基变量(xij)的检验数为：σij=cij

-(ui

+vj)=0(2)位势法

标准型运输问题的对偶问题：

得m+n-1个方程，令某个ui

(或vj)=0，可解出m+n个ui

和vj；由此得非基变量的检验数:非基变量(xij)的检验数为:σij=cij

-(ui

+vj)

72销产B1B2B3B4产量A1A2A3364133749销量3656例3在例3的由最小元素法得到的初始解中x23，x34，x21，x32，x13，x14是基变量。最小元素法方案73基变量检验数x23c23-(u2+v3)=0即2-(u2+v3)=0x34c34-(u3+v4)=05-(u3+v4)=0x21c21-(u2+v1)=01-(u2+v1)=0x32c32-(u3+v2)=04-(u3+v2)=0x13c13-(u1+v3)=03-(u1+v3)=0x14c14-(u1+v4)=010-(u1+v4)=0从以上7个方程中,由u1=0可求得u2=-1,u3=-5,v1=2,v2=9,v3=3,v4=10因非基变量的检验数这就可以从已知的ui，vj值中求得。这些计算可在表格中进行。74314

633（2）位势法

令v1=0,由c21=1=u2+v1，得u2=1最小元素法方案例375

0112例3最小元素法（2）位势法——基变量7601128-37位势表2989-3-2检验数(空格中数字为ui+vj

)例37701128-37检验数表121-11012σ24=-1＜0，当前方案不是最优方案。例378(2)位势法(0)79选择含基变量最多的行或列，令相应的u或v为零。(2)位势法(1)80v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2(2)位势法(2)81u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8(2)位势法(3)82v4=c34-u3=6-8=-2(2)位势法(4)83(2)位势法(5)5σ12=c12-(u1+

v2)=7-(-2+4)=5845(2)位势法(6)5σ13=c13-(u1+

v3)=5-(-2+2)=585(2)位势法(7)755σ14=c14-(u1+

v4)=3-(-2-2)=786(2)位势法(8)755σ24=c24-(u2+

v4)=7-(0-2)=9987(2)位势法(9)7559σ31=c31-(u3+

v1)=5-(8+8)=-11-1188(2)位势法(10)7559-11σ32=c32-(u3+

v2)=9-(8+4)=-3-3892.基可行解的改进（闭回路调整法）选择检验数绝对值最大的非基变量为进基变量(存在多个时任选一个)确定进基变量确定离基变量选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基变量为离基变量。运量调整重复上述步骤直至所有检验数大于零，即获得最优解。9001128-37检验数表121-11012σ24=-1＜0，当前方案不是最优方案。例391闭回路调整法改进方案（基可行解）pqijj,i)(minσ

σ=<0xpq为换入变量

从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量θ。换出变量换出变量92新的调运方案为：初始方案为：93需供B1B2B3B4uiA10210A2218A39125Vj

-7-1-70713491110231085所有σij>0,方案最优94表上作业法计算中的问题(1)有无穷多最优解最终解中有非基变量检验数为零时，则该问题有无穷多个最优解。以此非基变量为换入变量，可求得另一基最优解。基最优解的任一凸组合都是最优解。如例3另一基最优解是：

95(2)退化解中非零基变量个数小于m+n-1时，为退化解。求初始解时，当min{ai，bj}=ai=bj，在第i行或第j列任一空格上加0,表示这个格中的基变量的取值是0。

96已知

运输问题供需表和运价表如下，求最优调运方案。课堂练习979755-11-3确定进基变量选择检验数绝对值最大的非基变量为进基变量989755-11-3确定闭回路999755-11-3确定离基变量1009755-3调整运量6x31=6,x21=8-6=2,x23=6+6=12101-2-4558进一步优化(0)11102-2-4558进一步优化(1)11x13

进基，x34离基。10324558进一步优化(2)11所有非基变量的检验数均大于零，即为最优解。1041.产销不平衡的运输问题

在很多运输问题中，总产量不等于总销量。这时，为了使用前述表上作业法求解，就需将产销不平衡运输问题化为产销平衡运输问题。

§5.4其他运输问题105这时的数学模型是：如果总产量大于总销量，即

106若令假想销地的销量为，且

为借助于产销平衡时的表上作业法求解，可增加一个假想的销地

Bn+1，由于实际上它不存在，因而由产地调运到这个假想销地的物品数量(相当于松弛变量)，实际上是就地存贮在的物品数量。就地存贮的物品不经运输，故其单位运价。

107则模型变为：

108B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因为有：看一个例题：求下列表中极小化运输问题的最优解。109所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180－160=20，Ci5=0，i=1，2，3，4。表的右边增添一列这样我们可得新的运价表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180110B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表为计算结果。可看出：产地A4还有20个单位没有运出。111

总销量大于总产量的情形可仿照上述类似处理，即增加一个假想的产地，它的产量等于：

由于这个假想的产地并不存在，求出的由它发往各个销地的物品数量，实际上是各销地，所需物品的欠缺额，显然有：1122、有转运的运输问题

在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运到某个中间转运站(可能是另外的产地、销地或中间转运仓库)，然后再转运到销售目的地。有时，经转运比直接运到目的地更为经济。总之，在很多情况下，在决定运输方案时有必要把转运也考虑进去。显然，考虑转运将使运输问题变得更为复杂。113(1)产销不平衡的运输问题例：有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。需求地区化肥厂B1B2B3B4产量（万吨）A11613221750A21413191560A3192023---50最低需求（万吨）最高需求（万吨）3050707003010不限运价：万元/万吨5.4其他运输问题114分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表——115产销平衡表A1A2A3DB'1B''1B2B3B'4B''4产量销量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M13152050M116产销平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232M-19162217171415191920MMM0M16030202030117产销平衡表

A1A2A3DB'1B''1B2B3B'4B''4UiVj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M16118产销平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M10200119产销平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M1010302040120产销平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM16121产销平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj1613502217171414132019151015301930192020230MMM0M030M02016008-1511111315151555722334-1M-23M-23M+44M+2M203030200122产销平衡表A1A2A3DB'1B''1B2B3B'4B''4UiVj135013201510153019301920200030020007-15121213151515447222241M-22M-22M+33M+2M1622171714141923MMM0MM16123产销平衡表A1A2A3D1613502217171414132019151