武汉理工大学《运筹学》课件-第7章运输问题

1第七章运输问题§1运输模型§2运输问题的计算机求解§3运输问题的应用§4*运输问题的表上作业法武汉理工大学2例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）

§1运输模型3§1运输模型一般运输模型：产销平衡

A1、A2、…、Am

表示某物资的m个产地；B1、B2、…、Bn

表示某物质的n个销地；si

表示产地Ai的产量；dj

表示销地Bj的销量；cij

表示把物资从产地Ai运往销地Bj的单位运价。设xij

为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：

mnMinf=

cijxiji=1j=1n

s.t.

xij=sii=1,2,…,m

j=1m

xij=djj=1,2,…,ni=1

xij≥0(i=1,2,…,m;j=1,2,…,n)变化：

1）有时目标函数求最大。如求利润最大或营业额最大等；

2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；

3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。4§2运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为05§2运输问题的计算机求解例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为06§3运输问题的应用一、产销不平衡的运输问题例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。解：根据题意，作出产销平衡与运价表：这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。7§3运输问题的应用一、产销不平衡的运输问题例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：

试求总费用为最低的化肥调拨方案。解：根据题意，作出产销平衡与运价表：

最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量

50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。

8§3运输问题的应用二、生产与储存问题例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。9§3运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：x11=10生产：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x4410§3运输问题的应用二、生产与储存问题例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？11§3运输问题的应用解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地

1）1--6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；

2）上年末库存103台，只有仓储费和运输费，把它列为第0行；

3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；

4）1--6表示1--6月份正常生产情况，1’--6’表示1--6月份加班生产情况。产销平衡与运价表：12§3运输问题的应用

用“管理运筹学”软件解得的结果是：1-6月最低生产费用为8307.5万元，每月的销售安排如下表所示13§3运输问题的应用三、转运问题：在原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？图中1-广州、2-大连、3-上海、4-天津、5-南京、6-济南、7-南昌、8-青岛14§3运输问题的应用解：设xij

为从i到j的运输量，可得到有下列特点的线性规划模型：目标函数：Minf=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量-输入量=产量对转运站（中转点）：输入量-输出量=0

对销地（收点）j：输入量-输出量=销量例8．（续）目标函数：Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

约束条件：

s.t.x13+x14≤600(广州分厂供应量限制）

x23+x24+x28≤400(大连分厂供应量限制）

-x13-x23+x35+x36+x37+x38=0（上海销售公司，转运站）

-x14-x24+x45+x46+x47+x48=0（天津销售公司，转运站）

x35+x45=200（南京的销量）

x36+x46=150（济南的销量）

x37+x47=350（南昌的销量）

x38+x48+x28=300（青岛的销量）

xij≥0,i,j=1,2,3,4,5,6,7,815§3运输问题的应用用“管理运筹学”软件求得结果：

x13=550x14=50；

x23=0x24=100x28=300；

x35=200x36=0x37=350x38=0；

x45=0x46=150x47=0x48=0。最小运输费用为：4600百元例9、某公司有A1、A2、A3三个分厂生产某种物资，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：

试求总费用为最少的调运方案。假设：

1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；

2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；

3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。16§3运输问题的应用运价如下表：解：把此转运问题转化为一般运输问题：

1、把所有产地、销地、转运站都同时看作产地和销地；

2、运输表中不可能方案的运费取作M，自身对自身的运费为0；

3、Ai：产量为20+原产量，销量为20；Ti

：产量、销量均为20；Bi：产量为20，销量为20+原销量，其中20为各点可能变化的最大流量；

4、对于最优方案，其中xii

为自身对自身的运量，实际上不进行运作。17§3运输问题的应用

扩大的运输问题产销平衡与运价表：18§4*运输问题的表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。运输问题都存在最优解。计算过程（假设产销平衡）：1.找出初始基本可行解。对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。2.求各非基变量的检验数，即检验除了上述m+n-1个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。3.确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。4.重复2、3直到得到最优解。19§4*运输问题的表上作业法运输问题的一般数学模型设有m个产地（记作A1，A2，A3,…,Am），生产某种物资，其产量分别为a1,a2，…，am；有n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，bn；且产销平衡，即。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为：20§4*运输问题的表上作业法设平衡运输问题的数学模型为：模型特征1.运输问题存在可行解，也一定存在最优解2.当供应量和需求量都是整数时，则一定存在整数最优解3.有m+n个约束，mn个变量4.有m+n－1个基变量21§4*运输问题的表上作业法【证】因为产销平衡，即，将前m个约束方程两边相加得再将后n个约束相加得显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。22§4*运输问题的表上作业法中任意m+n阶子式等于零，取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式23§4*运输问题的表上作业法故r(A)=m+n－1所以运输问题有m+n－1个基变量。为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。24§4*运输问题的表上作业法为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。

x25

x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31

x42表中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。25§4*运输问题的表上作业法x11x12x32x33x41

B1B2B3A1

A2

A3

A4

x43

一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，上表中的变量x32及x33不是回闭路的顶点，只是连线的交点。表中闭回路是例如变量组A不能组成一条闭回路，但A中包含有闭回路B的变量数是奇数，显然不是闭回路，也不含有闭回路；26§4*运输问题的表上作业法C是一条闭回路，若把C重新写成就不难看出C仍是一条闭回路。【定理2】若变量组B

包含有闭回路，则B中的变量对应的例向量线性相关。【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即因而C中的列向量线性相关，所以B中列向量线性相关。27§4*运输问题的表上作业法由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。求运输问题的一组基变量，就是要找到m+n－1个变量，使得它们对应的系数列向量线性无关，由定理2，找这样的一组变量是很容易的，只要m+n－1个变量中不包含闭回路，就可得到一组基变量。因而有：【定理3】m+n－1个变量组构成基变量的充要条件是它不包含任何闭回路。定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。28§4*运输问题的表上作业法

BjAiB1B2B3B4aiA1c11

c12c13c14

a1x11x12x13x14A2c21c22c23c24a2x21x22x23x24A3c31c32c2c34a3x31x32x33x34bjb1b2b3b4例如，m=3,n=4，将xij与运价Cij放在同一张表中，如表5-5所示。29§4*运输问题的表上作业法这个运输问题的基变量数目是3+4－1=6。变量组中有7个变量，显然不能构成一组基变量，又如中有6个变量，但包含有一条闭回路故不能构成一组基变量。变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。30§4*运输问题的表上作业法例10.喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？这是一个产销平衡的运输问题，因此不需要再设假想产地和销地了。

销地产地B1B2B3B4产量A13113107A219284A3741059销量3656202031§4*运输问题的表上作业法一、确定初始基本可行解

为了把初始基本可行解与运价区分开，我们把运价放在每一栏的右上角，每一栏的中间写上初始基本可行解（调运量）。

1.西北角法：先从表的左上角（即西北角）的变量x11开始分配运输量，并使x11取尽可能大的值，即x11=min(7,3)=3,则x21与x31必为零。同时把B1的销量与A1的产量都减去3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。

销地产地B1B2B3B4

产量A134740A222420A336960

销量3062053060202031131085102947132§4*运输问题的表上作业法2.最小元素法

西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3,把A1的产量改为1，B1的销量改为0，并把B1列划去。在剩下的3×3矩阵中再找最小运价，同理可得其他的基本可行解。一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。

销地产地B1B2B3B4

产量A1

43730A23

1410A363930

销量3060

540630202031131085102947133§4*运输问题的表上作业法在求初始基本可行解时要注意的两个问题：1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。34§4*运输问题的表上作业法二、最优解的判别1.闭回路法所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。所谓闭回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。35§4*运输问题的表上作业法从非基变量x11出发，找到一个闭回路如上表所示。回路有四个顶点，除x11外，其余都为基变量。现在把x11的调运量从零增加为1吨，运费也增加了3元，为了使A1产量平衡，x13必须减少1吨，运费减少3元。为了B3的销量平衡，x23必须增加1吨，运费增加2元。同理把x21减少1吨，运费减少1元。调整后，总运费增加了3-3+2-1=1元。说明如果让x11为基变量，运费就会增加，其增加值1作为x11的检验数，为了区别调整量，我们把1加圈。用同样的方法可以找出所有空格（即非基变量）的检验数。

销地产地B1B2B3B4

产量A11

47A23

14A39

销量3656202031131085102947136BjAiB1B2B3B4aiA1938470×6010×A2765150××2030A3210922010×10×bj1060403080966-3372．位势法求检验位势法求检验数是根据对偶理论推导出来的一种方法。设前m个约束对应的对偶变量为ui,i=1,2,…,m，后n个约束对应的对偶变量为vj,j=1,2,…,n则运输问题的对偶问题是§4*运输问题的表上作业法38§4*运输问题的表上作业法又因为：记原问题基变量XB的下标集合为I，有如下式子成立：解上面第一个方程，将ui、vj代入第二个方程求出λij39§4*运输问题的表上作业法2.位势法所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋予一个数值vj，它们的数值是由基变量xij的检验数所决定的，则非基变量xij的检验数就可以用公式求出。我们先给u1赋个任意数值，不妨设u1=0，则从基变量x13的检验数求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1等等见上表。检验值的求法即用公式，如。

销地产地B1B2B3B4uiA1

1

2430A23

11

-1-1A3

106

123-5vj29310202031131085102947140§4*运输问题的表上作业法三、改进运输方案的办法——闭回路调整法当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。本例中取，表明增加一个单位的x24运输量，可使得总运费减少1。在以x24为出发点的闭回路中，找出所有偶数的顶点的调运量：x14=3，x23=1，x24=min(3,1)=1。把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。

销地产地B1B2B3B4uiA1

4(+1)3(-1)0A23

1(-1)

+1-1A3

6

3-5vj29310202031131085102947141§4*运输问题的表上作业法对上表用位势法进行检验如下表

销地产地B1