运输问题的典例

运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划运输问题的典例例1.某食品公司经销的主要产品之一是糖果.它下面设有三个加工厂,每天的糖果产量分别为:A1-7t,A2-4t,A3-9t.该公司把这些糖果分别运往四个地区的门市销售,各地区每天的销售量分别为：B1-3t,B2-5t,B3-6t.已知从每个加工厂到各销售门市部每吨的运价如表3-1所示，问该食品公司应如何调运,在满足各门市部销售需要的情况下，使得总的运费支出为最少.8291A251047A3103113A1B4B3B2B1门市部加工厂表3-1单位：元/t

运输问题的一般提法现有一批货物,从m个供应地运往n个销售地,Ai(i=1,‥‥,m)处有货物aj吨，Bj(j=1,‥‥,n)处需货物bj吨,已知从Ai到Bj的运价为cij

元/吨.问如何安排，既可以满足各销地需要，又使总费用最小？A1A2Am︰︰B1B2Bn︰︰a1a2am︰︰b1b2bm︰︰运输问题的框图表示供应量需求地供应地需求量运价xij产销平衡表运输问题的数学模型单位运价表运输问题的数学模型运输表（运价，运量）销量产量销地产地产销平衡条件下设xij为从产地Ai运往销地Bj的物资数量(i=1,…m;j=1,…n）从Ai运出的物资总量应等于Ai的产量ai，xij应满足：

运到Bj的物资总量应该等于Bj的销量bj，xij还应满足：运输问题的数学模型总运费为：运输问题的数学模型运输问题的数学模型1.约束条件都是等式约束2.总产量＝总销量产销平衡的运输问题的特点与性质3.系数矩阵是一个结构特殊的稀疏矩阵将约束方程组展开约束方程组共包含m×n个变量，(m+n)个约束条件产销平衡的运输问题的特点与性质系数矩阵A：m行n行

矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；将矩阵分块,特点是:前m行构成m个m×n阶矩阵,而且第k个矩阵只有第k行元素全为1,其余元素全为0（k=1,…,m）;后n行构成m个n阶单位阵。A的秩为m+n-1m行n行为什么？第i行第m+j行

运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划运输问题的典例运输问题的数学模型求解方法——表上作业法第三章运输问题特殊的线性规划表上作业法作业表（产销平衡表）：将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。运输问题的典例1023206563销量9563474829217101143

3产量销地产地填有数字的格:对应运输问题解中的基变量取值，这里为3+4-1=6个空格：对应解中非基变量表上作业法的基本思想是:先设法给出一个初始方案(如典例所示),然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。表上作业法

确定初始方案(初始基可行解)

改进调整（换基迭代）否

判定是否最优？是结束最优方案——求解思路图表上作业法1.最小元素法2.沃格尔（Vogel）法(一)初始方案的给定给定初始方案的方法很多(如前例)，一般来说，希望方法简便易行，并能给出较好的方案。减少迭代次数。这里介绍1.最小元素法基本思想：就近供应，即优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。3－3－31－1－1－4－4-6－66433－3－3-3-3316433Z=4*3+3*10+3*1+1*2+6*4+3*5=86最小元素法的说明退化现象：

部分产量和＝部分销量和在迭代过程中，可能出现一行和一列同时被划去。34－4－4－1－1-6－6616－3－3－6-60为使迭代过程中基变量的个数恰好为(m+n-1)个，应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量。以便当做有数字的格看待。346160(一)初始方案的给定基本思想：优选考虑最大差额（最小运价优势）方案行（列）差额（罚数）=次小运价系数-最小运价系数2.沃格尔（Vogel）法(差额法)1023206563销量95474891710113产量

销地产地0112513()6220071312121162()33()521108()1023206563销量95474891710113产量

销地产地633521一般当产销地数量不多时，(Vogel)法给出的初始方案有时就是最优方案。沃格尔法Z=5*3+2*10+3*1+1*8+6*4+3*5=85最小元素法Z=4*3+3*10+3*1+1*2+6*4+3*5=86>8530练习.求下表给出的运输问题的初始基本可行解．

(一)初始方案的给定315100151010(一)初始方案的给定325100151010(一)初始方案的给定

最小元素法或Vogel法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化.(二)最优性检验与方案的调整基本思想：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。1.闭回路法2.对偶变量法（位势法）在已给出的初始调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。运输问题中的闭回路注意：由于任意非基变量均可表示为基向量的唯一线性组合，因此通过任一空格可以找到唯一的闭回路

x25

x23B1B2B3B4B5A1A2A3

x35A4

x43x11x12x31

x42表中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。

运输问题中的闭回路将如下表中6个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。1023206563销量95346748191371034113产量

销地产地(A2,B1),(A3,B2)无法连入闭回路中运输问题中的闭回路孤立格是指在所在行或列中唯一出现的变量。孤立格一定不会成为闭回路的顶点目的：计算解中各非基变量(空格)的检验数基本思路：对于代表非基变量的空格（其调运量为零），把它的调运量调整为1；由于产销平衡的要求我们必须对这个空格的闭回路的顶点的调运量加上或减少1(可行条件)；计算出由这些变化给整个运输方案的总运输费带来的变化，这里称之为检验数。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则进行方案调整（后续）闭回路法求检验数23206563销量9544

11

3710产量

销地产地64333同理可以找出所有空格（即非基变量）的检验数。+1－1＋1－1总运费变化＝即此新可行解较原来解运费增加1元闭回路法求检验数闭回路法求检验数23206563销量954411

3710产量

销地产地6433-1+1-1+1-1+1总运费变化＝7

约定作为起始顶点的非基变量为第一个奇数次顶点，相邻顶点为偶次顶点，其它顶点依次排列，那么，该非基变量xij的检验数：=（闭回路上奇数次顶点运价之和）－（闭回路上偶数次顶点运价之和）

-11A21210A321A1B4B3B2B1销地产地检验数表闭回路法求检验数当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。闭回路法求调整方案选一个非基变量变为基变量进基选一个基变量变为非基变量离基反映在运输表上就是要选一个空格填上大于0的数选择入基的原则是：从绝对值最大的负检验数格(k,l)出发闭回路法求调整方案-11A21210A321A1B4B3B2B1销地产地检验数表（A2,B4）为起点作一条除该空格外其余顶点均为有数字格组成的闭回路闭回路法求调整方案（A2,B4）为起点作一条出该空格外其余顶点均为有数字各组成的闭回路206563销量94

1

374产量

销地产地

6

33

调运方案（最小元素法得到）+1-1+1-1=min{3,1}=1离基？在这条闭回路上，在保持产销平衡的条件下对偶数顶点格子的运量做最大可能的调整闭回路法求调整方案（A2,B4）为起点作一条出该空格外其余顶点均为有数字各组成的闭回路206563销量94

375产量

销地产地

6

32

调运方案（最小元素法得到）1=min{3,1}=14.在作业表上从绝对值最大的负检验数格(k,l)出发,即xkl为起始变量作出闭回路。5.以空格(k,l)为第一个奇数顶点，沿闭回路的顺（或逆）时针方向依次对顶点编号。6.在闭回路上的所有偶数顶点中，找出运输量最小的格子，以该格对应的变量为离基变量。7.调整量8.将该闭回路上所有奇数顶点处的运输量都增加

所有偶数顶点处的运输量都减去ij

=min{该闭回路中偶数次顶点运输量xij}运输量的变化＝闭回路法求调整方案位势法

在闭回路方法当中，要判断一个方案是否最优，需要通过每一个空格来寻找回路，以及根据闭回路求出每个空格的检验数，当一个运输问题的产地和销地很多时，用此方法工作量十分繁重.位势法是根据对偶理论推导出来的一种求解检验数方法.运输方案的调整同前面的闭回路法.47位势法求检验数原问题对偶问题48记原问题基变量XB的下标集合为I，有如下式子成立：解上面第一个方程，将ui、vj代入第二个方程求出检验数,称ui(i=1,…,m),vj(