2.4运输问题(修改)解析

第2.4节运输问题一、运输问题的数学模型二、表上作业法三、产销不平衡的运输问题及其求解方法1

例1

某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。单位运价表产销平衡表2一、运输问题的数学模型已知有m个生产地点Ai,i=1,2,…，m。可供应某种物资，其供应量(产量)分别为：ai，i=1，2，…，m有n个销地Bj，j=1,2,…,n，其需要量分别为：bj，j=1,2,…,n从

Ai到

Bj

运输单位物资的运价(单价)为：cij这些数据可汇总于产销平衡表和单位运价表中，见下表。有时可把这两表合二为一。销地产地12┉n产量12┆m

a1a2┆am销量b1b2┈bn

3若用

xij

表示从Ai到Bj

的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案的数学模型为：4一、运输问题的数学模型这就是运输问题的数学模型。它包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。5一，运输问题的数学模型该系数矩阵中对应于变量xij

的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即

Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j

对产销平衡的运输问题，由于有以下关系式存在：运输问题是否一定有解？(见后面)运输问题的基变量共有m+n-1个，A的秩为m+n-1？

最后一行可由前m+n-1行线性表示。其中任何一行都是一样。6二，表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：

(1)

找出初始基可行解。即在(m×n)产销平衡表上用西北角法或最小元素法，Vogel法给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。

(2)

求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。

(3)

确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。

(4)

重复(2)，(3)直到得到最优解为止。72.1确定初始基可行解与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有：必存在xij≥0，i=1，…，m，j=1，…，n，如：Xij

=aibj

/d就是可行解。又因0≤xij≤min(aj，bj)，故运输问题必存在最优解。

82.1确定初始基可行解确定初始基可行解的方法很多，有西北角法，最小元素法和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍最小元素法：9

1.最小元素法最小元素法的基本思路是以运价最低者优先为原则安排初始的调运方案，即从单位运价表中最小运价处开始确定供销关系。若产量大于销量，则用加工厂的产量满足对应销地的全部日销量，在对应的空格内填入相应的调运量。并用垂直直线划去销售地所在列，表明该销地的日销量已经全部满足，同时从对应加工厂的日产量中减去调运量。反之，若产量小于销售量。则把加工厂的日产量全部分配给对应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在行，并从对应销地的日销量中减去调运量。依次类推，逐步推出初始方案。由于最小元素法已经考虑到了运价最低者优先为原则，因此所求的初始基本可行解通常比较接近最优解。经过若干次调整即可求得最有解。

10例1

某公司经销甲产品。下设三个加工厂Ａ1，Ａ2，Ａ3，每天把产品分别运往四个销地Ｂ1，Ｂ2，Ｂ3，Ｂ4。各加工厂的日产量，各销地的日销量以及从各加工厂运送单位产品至各销售地的运价如下表：

销地产地B1

B2

B3

B4

日产量（吨）A1

3113107A2

19284A3

741059日销量（吨）3656单位：千元/吨问该公司应如何确定调运方案，在满足各销地需求量的前提下可使得总运费最小？116563销量（吨）951047A3

482913A2

7103113A1

产量（吨）

B4

B3

B2

B1

销售地加工厂①

为了用最小元素法确定初始基本可行解，可先画出综合运输表。然后按以下步骤确定初始调运方案。①从全部单位运价中找出最低单位运价（若有两个以上最低单位运价，则可在其中任选其一）。然后比较最低运价所对应的加工厂的日产量和销地的日销量，并且确定第一笔供销关系。-3126563销量（吨）951047A3

4821913A2

7103113A1

产量（吨）

B4

B3

B2

B1

销售地加工厂①

-3②在未被划去的单位运价中再找寻最低运价，比较最低运价对应的加工厂的日产量（或剩余量）和销地的日销量（或尚缺量）来确定供销关系。基本原则与①中描述过程相同。

-1136563销量（吨）95310467A3

4821913A2

710334113A1

产量（吨）

B4

B3

B2

B1

销售地加工厂①

-3-1

重复步骤②可逐个确定从加工厂到销地的供销关系。基本原则是在空格内内每填入一个调运量必须划去一行或一列。填入最后一个调运量后则同时划去一行和一列．这样在运输表中共计填入了m＋n－1个数字。这些数字对应了一个初始基本可行解。④

-6③-4⑤

②

-3146563销量（吨）95310467A3

4821913A2

710334113A1

产量（吨）

B4

B3

B2

B1

销售地加工厂①

-3-1③

-6④

-4⑤

②

-3所填入的m＋n－1＝3＋4－1＝6个数字为对应初始基本可行解的

6个初始基变量的值。即对应的总运费为Z＝4×3＋3×10＋3×1＋1×2＋6×4＋3×5＝86（千元）15必须补充说明的是：利用最小元素法确定初始调运方案过程中，可能出现最低单位运价对应的产地的产量和销地的销量恰好相等的情形。此时在运输表中填入一个数字后，必须同时划去产地所在行和销地所在列，这和每填入一个数字只划一条直线的基本原则相违背（最后一个数字除外）。这时我们称运输问题出现了退化。为了使运输表中有m＋n－1个数字格。需要添加一个“0”调运量，它的位置可在同时划去的那行或那列的任一空格处。这个“0”调运量是不可缺少的。因为运输问题的基本解中基变量的个数必须是m＋n－1个。不能多，也不能少。出现了数字为0的数字格只是说明在初始基本可行解中有一个基变量为零。即该初始基本可行解是退化解。162.1确定初始基可行解用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列，这时就出现退化。关于退化时的处理详见教材。172.1确定初始基可行解

2.伏格尔法（略）

182.2最优解的判别回顾利用单纯形法求解线性规划的步骤：在求出基本可行解以后，就必须检验该基本可行解是否为最优解，为此给出一个检验标准。在求极大化的线性规划时，若初始基本可行解所有非基变量检验数（j为非基变量下标）则初始可行解为最优解，停止计算。否则将进行基变换，对初始基本可行解进行改进。运输问题初始基本可行解的最优性检验也必须设定一个标准。由于运输问题目标函数是求极小化问题，因此检验标准是计算所有非基变量（空格）的检验数

(i,j为非基变量下标)．如果所有非基变量检验数则初始基本可行解为最优解。下面介绍两种计算检验数的方法。191.闭回路法。利用闭回路的概念计算非基变量的检验数，以判别基本可行解是否为最优解。定义：若运输表中的一组变量经过适当排列以后，可写成如下形式：其中互不相同，互不相同。那么这些变量集合就构成了一个闭回路。其中的每一个变量称为这个闭回路的顶点。由闭回路定义可知，若用水平和垂直的线段将这个变量集合中处于同行同列的相邻顶点相连接。就能构成一个封闭的回路。而且该闭回路的每一条边（水平或垂直）上只包含两个顶点。且都处于每条边的两个端点上。如20表中变量集合,变量集合,变量集合等均构成闭回路．

B1

B2

B3

B4

B5

B6

B7

B8

B9

产量

A1

a1A2

a2A3

a3A4

a4销量

b1

b2b3b4b5b6b7b8b9常见的几种闭回路见表：21性质定理1

运输问题模型中，系数矩阵A的一组系数列向量线性无关的充分必要条件是这组向量所对应的变量不包含闭回路。本定理证明从略。

变量组不包含闭回路的含义是该变量组中任何一个变量子集合均不构成闭回路。由定理１可得如下推论：推论1.若一组变量包含闭回路，那么这组变量所对应得系数列向量线性相关。推论2.m＋n－1个变量构成基本可行解的基变量的充分必要条件是它们不包含闭回路。22定理2

若变量组(s=m+n-1)是运输问题基本可行解的基变量，是一个非基变量，则变量组中存在包含的唯一闭回路。由定理2可知，从任何一个非基变量对应的空格出发，用水平或垂直线向前划，遇到某个基变量对应的数字格，试转90o后继续前进，最后总能找到一条闭回路，回到起始空格。23

闭回路法。设是一个非基变量，根据定理2，在运输表中可以找到以为第一个顶点，其他顶点均为基变量的唯一闭回路。然后沿一个方向将闭回路中奇数顶点对应的值取为正，偶数顶点对应的值为负。求它们的代数和，即为非基变量对应的检验数。填入相应的空格。做上记号以便与数字格的基变量值（调运量）相区别。242.2最优解的判别闭回路法计算检验数的经济解释为：在已给出初始解的表中，可从任一空格出发，如(A1，B1)。若让A1的产品调运1吨给B1。为了保持产销平衡，就要依次作调整：

在(A1，B3)处减少1吨，(A2，B3)处增加1吨，(A2，B1)处减少1吨，即构成了以(A1，B1)空格为起点，其他为数字格的闭回路。如表中的虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价。252.2最优解的判别可见这调整的方案使运费增加

(+1)×3+(−1)×3+(+1)×2+(−1)×１=1(元)

这表明若这样调整运量将增加运费。将“1”这个数填入(A1，B1)格，这就是检验数。266563销量（吨）95310467A3

4821913A2

710334113１A1

产量（吨）

B4

B3

B2

B1

销售地加工厂例2

在例1中用最小元素法求出初始基本可行解为下表所示。试用闭回路法求各非基变量（空格）的检验数．解：非基变量为起点的闭回路为，如表所示。因此所对应的检验数276563销量（吨）953101246710A3

48-１219１13A2

71033411２3１A1

产量（吨）

B4

B3

B2

B1

销售地加工厂而非基变量对应的检验数：其他非基变量的检验数用同样方法求解，结果下表。本例中，则必存在对现行调运方案的改进办法。可使得总费用进一步降低。282.2最优解的判别当检验数还存在负数时，说明原方案不是最优解，要继续改进，改进方法见2.3小节。292.2最优解的判别2.位势法（略）

302.3

改进的方法——闭回路调整法当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。以(2，4)为调入格。以此格为出发点，作一闭回路，如下表所示。312.3

改进的方法——闭回路调整法(2，4)格的调入量θ是选择闭回路上具有(-1)的数字格中的最小者。即θ=min(1,3)=1(其原理与单纯形法中按θ规划来确定换出变量相同)。然后按闭回路上的正、负号，加入和减去此值，得到调整方案，如下表所示。322.3

改进的方法——闭回路调整法对上表给出的解，再用闭回路法或位势法求各空格的检验数，见下表。表中的所有检验数都非负，故此表中的解为最优解。这时得到的总运费最小是85元。B1B2B3B4A1A2A30922112332.4

表上作业法计算中的问题1.无穷多最优解2.退化34三产销不平衡的运输问题及其求解方法前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。当产大于销时

35三、产销不平衡的运输问题及其求解方法运输问题的数学模型可写成=36三、产销不平衡的运输问题及其求解方法1.由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。设xi,n+1是产地Ai的储存量，于是有：37三，产销不平衡的运输问题及其求解方法令当i=1,…，m，j=1,…，n时

当i=1,…，m，j=n+1时将其分别代入，得到38三、产销不平衡的运输问题及其求解方法39三、产销不平衡的运输问题及其求解方法由于该模型中有所以这是一个产销平衡的运输问题。当产大于销时，只要增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为