运筹学运输问题资料讲解

1、运筹学运输问题第1节 运输问题的数学模型一、运输问题运输问题属于线性规划问题，因为其约束方程组的系数矩阵A具有特殊的结构，所以专门介绍一种比单纯形法更简便的求解方法，以节约计算时间和费用。第1节 运输问题的数学模型例1：某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。销售点加工厂B1 B2 B3 B4产量A1A2A3749销量3 6

2、 5 6 销售点加工厂B1 B2 B3 B4A1A2A33 11 3 101 9 2 87 4 10 5第1节 运输问题的数学模型二、运输问题的数学模型已知有m个生产地点（简称产地） 可供应某种物资，其供应量（产量）分别为 ；有n个销售地点（简称销地） ，其需要量（销量）分别为 ，从 到 运输单位物资的运价（单位运价）为 ，将这些数据表示在如下页的两个表中。问应如何调运，在满足各销地销量的情况下，使总的运费支出最少？(1,2,)jBjn(1,2,)iA im(1,2,)ia im(1,2,)jbjnjBijciA第1节 运输问题的数学模型 产销平衡表 两个表合二为一 销地产地B1 B2 Bn产

3、量A1A2Ama1a2am销量b1 b2 bn 销地产地B1 B2 BnA1A2Amc11 c12 c1n c21 c22 c2n cm1 cm2 cmn销地产地B1 B2 Bn产量A1A2Amc11 c12 c1n c21 c22 c2n cm1 cm2 cmna1a2am销量b1 b2 bn 单位运价表第1节 运输问题的数学模型 产销平衡表 单位运价表销售点加工厂B1 B2 B3 B4产量A1A2A3749销量3 6 5 6 销售点加工厂B1 B2 B3 B4A1A2A33 11 3 101 9 2 87 4 10 5销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 3 10

4、1 9 2 8 7 4 10 5749销量 3 6 5 6 二表合一第1节 运输问题的数学模型例1：解：设xij为第i加工厂向第j销售点的甲产品的供应量，cij表示第i加工厂向第j销售点供应甲产品的单位运费34111213143411111213142122232431323334112131122232132333142434min311310574936560 ( 12 312 3 4)ijijijijzxxxxxc xxxxxxxxxxxxxxxxxxxxxxxxxxij，= ， ， ； = ， ， ，第1节 运输问题的数学模型产销平衡 运输问题的数学模型：设xij表示从产地Ai运往销地

5、Bj的产品数量mniji=1j=1（a =b）1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，第1节 运输问题的数学模型特征（1）决策变量：mn（2）约束方程：mn；都是等式约束（3）目标函数：最小化第1节 运输问题的数学模型34111213143411111213142122232431323334112131122232132333142434min311310574936560 ( 12 312 3 4)ijijijijzxxxxxc xxxxxxxxxxxxxxxxxxxxxxxxxxij，= ， ， ； =

6、， ， ，第1节 运输问题的数学模型123456789101112111213142122232431323334111100000000000011110000000000001111100010001000010001000100001000100010000100010001PPPPPPPPPPPPxxxxxxxxxxxxA（4）约束方程组系数矩阵AA中只有数字0或1A的每一列只有两个非零元素1第1节 运输问题的数学模型（6）基变量：mn1（7）对于产销平衡的运输问题必有可行解和最优解mniji=1j=1（a =b）第2节 表上作业法一、表上作业法的解题思路表上作业法的实质是单纯形法在求

7、解运输问题时的一种简化方法，属于单纯形法，又称为运输单纯形法。基可行解最优否结束换基是否第2节 表上作业法二、表上作业法的特点表上作业法是一种迭代法用表上作业法求解运输问题，直接在表上进行，不必写出数学模型第2节 表上作业法三、表上作业法的解题步骤（一）找出初始基可行解：在产销平衡表上找出 (m+n-1)个数字格，形成初始产销平衡表方法（二）求非基变量检验数：计算初始产销平衡表中空格的检验数，判别是否达到最优解，如果已达到，停止计算；否则转入3方法（三）确定换入变量和换出变量，找出新的基可行解方法：闭回路调整法（四）重复（二）（三），直到求出最优解说明：以例1为例解释表上作业法的解题步骤最小元

8、素法伏格尔法（Vogel法）闭回路法位势法（对偶变量法）第2节 表上作业法 产销平衡表 单位运价表销售点加工厂B1 B2 B3 B4产量A1A2A3749销量3 6 5 6 销售点加工厂B1 B2 B3 B4A1A2A33 11 3 101 9 2 87 4 10 5销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5749销量 3 6 5 6 二表合一第2节 表上作业法表上作业法解题步骤（一）：确定初始基可行解方法一：最小元素法1、基本思路从运费上考虑，优先安排单位运价最小的产地和销地之间的运输业务，最大限度地满足其产销量，从而实现“就近供

9、应”。第2节 表上作业法例2：用最小元素法找出例1的初始基可行解。第2节 表上作业法例2：解： 初始产销平衡表销售点加工厂B1 B2 B3 B4产量A1A2A3 4 33 1 6 3749销量3 6 5 6第2节 表上作业法2、求解步骤第一，从单位运价表中找出最小运价，（有两个或两个以上的最小单位运价，则任选其一），比较产量和销量：产量销量，则划去该运价所在列；产量销量，则划去该运价所在行。并在初始产销平衡表上填上相应的数字。第二，从单位运价表中未被划去的运价中再找最小运价，重复第一第二，直到单位运价表中所有运价都被划去，并找出(m+n-1)个数字格。第2节 表上作业法3、小结（1）在初始产销

10、平衡表上每填入一个数字，在单位运价表上就划去一行或一列（当表中只剩一个元素时，在初始产销平衡表上填数字时，在单位运价表上同时划去一行和一列）（2）在单位运价表上共划去（mn）条直线，（相当于单位运价表上所有cij都被划去两次）（3）在初始产销平衡表上填了（mn1）个数字格，每行数字之和该行产量，每列数字之和该列销量第2节 表上作业法例3：用最小元素法求出下述运输问题的初始基可行解。销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 4 5 7 7 3 8 1 2 10 6749销量 3 6 5 6第2节 表上作业法例3：解： 初始基可行解销售点加工厂B1 B2 B3 B4产量A1A2

11、A3 0 1 6 0 4 3 6 0 0749销量 3 6 5 6第2节 表上作业法例4：判断下表给出的运输方案能否作为用最小元素法 求解出的初始基可行解？销地产地1 2 3 4产量1230 15 15 10515255销量5 15 15 10第2节 表上作业法表上作业法解题步骤（一）：确定初始基可行解方法二：伏格尔法1、基本思路按某一最小单位运价优先安排物品调运时，可能导致其他产销点不得不采用很高的单位运价进行运输，从而使整个运输费用增加。对每一个产地或销地，找出最小单位运价和次小单位运价，求二者之差。若差值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，若二者之差很大，不按最

12、小单位运价组织运输就会造成很大损失，所以应尽量按最小单位运价安排运输。第2节 表上作业法例5：用伏格尔法找出例1的初始基可行解。第2节 表上作业法例5：解： 初始产销平衡表销售点加工厂B1 B2 B3 B4产量A1A2A3 5 23 1 6 3749销量3 6 5 6 第2节 表上作业法2、求解步骤第一，在单位运价表中分别计算各行和各列的最小运价与次小运价的差额，并填在该表的最右列和最下行。第二，从行或列差额中选出最大者，（有两个或两个以上的最大差额，则选择差额所在行（或列）中的最小单位运价），选择它所在行或列中的最小运价，按照最小元素法确定初始基可行解。第三，对单位运价表中未被划去的运价再计

13、算各行和各列的最小运价与次小运价的差额，并仍填入该表的最右列和最下行，重复第二、三，直至给出初始基可行解为止，即找出（m+n-1）个数字格。第2节 表上作业法3、小结（1）伏格尔法和最小元素法仅在确定产销关系的原则上不同，其余步骤都相同（伏格尔法是在最小元素法的基础上改进的一种方法）（2）伏格尔法给出的初始基可行解比用最小元素法给出的初始基可行解更接近最优解（伏格尔法给出的解的目标函数值比最小元素法给出的解的目标函数值小）（3）伏格尔法得出的初始基可行解常作为运输问题最优解的近似解作业4-1作业4-1：1、用最小元素法找出下述运输问题的初始基可行解。2、找出下述运输问题的近似最优解。（其中M为

14、任意大正数，表示含义为从A4到B4不存在运输路线）销地产地1 2 3产量1235 1 82 4 13 6 712144销量9 10 11 销地产地 1 2 3 4 5产量123410 2 3 15 9 5 10 15 2 415 5 14 7 1520 15 13 M 825302030销量20 20 30 10 25 第2节 表上作业法表上作业法解题步骤（二）：求检验数，判别最优解基本思路计算空格（非基变量）的检验数，（运输问题的目标函数要求实现最小化）当所有检验数0时，所得的解是最优解，否则要进行解的改进。第2节 表上作业法表上作业法解题步骤（二）：求检验数，判别最优解方法一：闭回路法例6

15、：用闭回路法求例2所得的初始基可行解的检验数。销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5749销量 3 6 5 6第2节 表上作业法例6：解： 检验数表销售点加工厂B1 B2 B3 B4A1A2A3 1 2 1 -110 12第2节 表上作业法1、检验数的含义检验数表示变化的运费。即：若某空格（Ai，Bj）的检验数0，表示将该空格变为数字格使运输费用减少，则当前这个解不是最优解；反之，若所有空格的检验数都0，表示不管怎样变换，都使运输费用增加，则目标函数已无法改进，当前这个解就是最优解第2节 表上作业法2、求解步骤第一，在初始产销平

16、衡表上，从每一空格出发找一条闭回路：以某空格为起点，用水平或垂直线向前画，碰到一数字格转90（有些情况下也可以不改变方向），然后继续前进，直到回到起始空格为止。第二，在一闭回路上，令某空格取值为+1，表示增加的运量，然后变化相应数字格的值，并计算该闭回路上运费的变化值，即为该空格的检验数，填入检验数表。第2节 表上作业法例7：用闭回路法求例5所得的初始基可行解的检验数。销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5749销量 3 6 5 6第2节 表上作业法例7：解： 检验数表销售点加工厂B1 B2 B3 B4A1A2A3 0 2 2

17、1 9 12第2节 表上作业法3、小结（1）闭回路的顶点，除出发点为空格外，其他均为数字格（2）每个空格唯一存在一条闭回路（3）对于产销点过多的运输问题，空格的数目很大，计算检验数很繁琐第2节 表上作业法表上作业法解题步骤（二）：求检验数，判别最优解方法二：位势法1、基本思路第2节 表上作业法 原问题 对偶问题1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，11max12.12.mniijjijijijijzaub vuvcimjnuv ， ， ， ， 取值无约束第2节 表上作业法2、求解步骤第一，仿照初始产销平衡表做

18、一个表，在对应的数字格处填入单位运价cij。第二，在表的最右列和最下行分别增加一列ui和一行vj，使表中的单位运价等于它所在行和列的ui与vj之和，求出所有的ui和vj，并填写在表中。第三，计算各空格的检验数，填入检验数表。第2节 表上作业法例8：用位势法求例2所得的初始基可行解的检验数。销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5749销量 3 6 5 6 第2节 表上作业法例8：解： 检验数表销售点加工厂B1 B2 B3 B4A1A2A3 1 2 1 -110 12第2节 表上作业法例9：用位势法求例5所得的初始基可行解的检验数。

19、销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5749销量 3 6 5 6 第2节 表上作业法例9：解： 检验数表销售点加工厂B1 B2 B3 B4A1A2A3 0 2 2 1 9 12第2节 表上作业法2、小结当运输问题的产地和销地很多时，空格的数目很大，采用位势法计算检验数简便第2节 表上作业法（三）确定换入和换出变量，找出新的基可行解，直至求出最优解方法：闭回路调整法1、基本思想在初始产销平衡表中，选取检验数为负的所有空格中的最小者作为换入格，以对应空格为出发点画出闭回路，在经过的数字格中选择（-1）的最小者，对应的数字格为换出格，

20、然后对闭回路上各顶点的数据进行调整，得到另一个更好的基可行解。第2节 表上作业法2、求解步骤第一，确定换入格。在初始产销平衡表上，最小的负检验数所在的空格为换入格，（有两个或两个以上的最小者，则任选其一），并以此空格为出发点，作一闭回路。第二，确定换出格：选择闭回路上标记为-1的数字格中的最小者，记做，则该数字格为换出格。第三，调整：将闭回路上标记为+1的数字格加，标记为-1的数字格减，得到新的基可行解。第四，采用闭回路法或位势法求空格的检验数，若所有检验数都0，则获得最优解；否则重复第一第三，直至求出最优解。第2节 表上作业法 最优解 检验数表 z*=85销售点加工厂B1 B2 B3 B4产

21、量A1A2A3 5 23 1 6 3749销量3 6 5 6 销售点加工厂B1 B2 B3 B4A1A2A3 0 2 2 1 9 12第2节 表上作业法例10：用表上作业法求解例3。销售点加工厂B1 B2 B3 B4产量A1A2A3 3 11 4 5 7 7 3 8 1 2 10 6749销量 3 6 5 6第2节 表上作业法 最优解 检验数表 z*=61销售点加工厂B1 B2 B3 B4产量A1A2A3 1 6 4 3 6 0749销量3 6 5 6 销售点加工厂B1 B2 B3 B4A1A2A3 3 10 8 7 4 5第2节 表上作业法四、表上作业法的解1、唯一最优解所有空格（非基变量）

22、的检验数大于0，该运输问题有唯一最优解。第2节 表上作业法 最优解 检验数表 z*=61销售点加工厂B1 B2 B3 B4产量A1A2A3 1 6 4 3 6 0749销量3 6 5 6 销售点加工厂B1 B2 B3 B4A1A2A3 3 10 8 7 4 5例3最优解的情况第2节 表上作业法2、无穷多（多重）最优解某个空格（非基变量）的检验数为0时，该运输问题有无穷多（多重）最优解。在已求得一个最优解的表中，以这样的空格出发做闭回路重新进行调整，得到另一个最优解。第2节 表上作业法例1最优解的情况 无穷多最优解 检验数表 z*=85销售点加工厂B1 B2 B3 B4产量A1A2A3 5 23

23、 1 6 3749销量3 6 5 6 销售点加工厂B1 B2 B3 B4A1A2A3 0 2 2 1 9 12第2节 表上作业法例1最优解的情况 无穷多最优解 检验数表 z*=85销售点加工厂B1 B2 B3 B4产量A1A2A32 51 3 6 3749销量3 6 5 6 销售点加工厂B1 B2 B3 B4A1A2A3 2 0 2 1 9 12第2节 表上作业法3、退化解某个数字格（基变量）为0时，该运输问题为退化解。退化解出现的情况：确定初始解的各供需关系时，若在某格填入某数字后，出现该处的供应量与需求量相等。用闭回路调整法调整时，在闭回路上出现两个或两个以上的具有（-1）标记的相等的最小

24、值。第2节 表上作业法例11：已知某初始产销平衡表，如下表：空格A2B4格的检验数0，其余空格的检验数均0 ，试确定换入、换出格，求出新的基可行解。销地产地B1 B2 B3 B4产量A1A2A3 4 13 1 6 3549销量3 6 5 4 第2节 表上作业法例11：解： 下一个基可行解销地产地B1 B2 B3 B4产量A1A2A3 5 03 1 6 3549销量3 6 5 4 第2节 表上作业法五、表上作业法计算步骤框图分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或伏格尔法）求检验数（闭回路法或位势法）所有检验数0唯一最优解算出总的运价找出最小的负检验数用闭回路调整，得

25、出新的调运方案是否某空格检验数0是否无穷多最优解第2节 表上作业法例12：已知三个产地A1，A2，A3，四个销地B1，B2，B3，B4的产销量即单位运价如下表所示，求使总运费最少的调运方案。销地产地 B1 B2 B3 B4产量A1A2A3 2 2 3 7 4 3 5 9 1 6 7 8 500600300销量300 200 500 400第2节 表上作业法例12：解： 无穷多最优解、退化解 z*=6000销地产地 B1 B2 B3 B4产量A1A2A3 0 500 200 0 400300 500600300销量300 200 500 400作业4-2作业4-2：用表上作业法求解下列运输问题的

26、最优解。1、要求采用伏格尔法、 位势法求解 2、要求采用伏格尔法、 闭回路法求解 销地产地 甲 乙 丙 丁产量1233 7 6 42 4 3 24 3 8 5 523销量3 3 2 2 销地产地甲 乙 丙 丁产量12310 6 7 1216 10 5 9 5 4 10 10 494销量 5 2 4 6 第3节 产销不平衡的运输问题及其求解方法一、求解思路总产量不等于总销量，为使用表上作业法求解，将产销不平衡运输问题转化为产销平衡运输问题。第3节 产销不平衡的运输问题及其求解方法二、求解方法1、总产量总销量（ ）11mnijijab销地产地B1 B2 Bn产量A1A2Amc11 c12 c1nc

27、21 c22 c2n cm1 cm2 cmna1a2am销量 b1 b2 bn第3节 产销不平衡的运输问题及其求解方法数学模型： 1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，第3节 产销不平衡的运输问题及其求解方法解题思路：为借助于产销平衡的表上作业法求解，增加一个假想的销地Bn+1，由于实际上它不存在，因而由产地Ai（i=1，2，m）调运到这个假想销地的物品数量xi,n+1，就是就地存贮在Ai的物品数量。就地存贮的物品未经运输，所以其单位运价ci,n+1=0（i=1，2，m）。第3节 产销不平衡的运输问题及其求解

28、方法销地产地B1 B2 Bn Bn+1产量A1A2Amc11 c12 c1n 0c21 c22 c2n 0 cm1 cm2 cmn 0a1a2am销量 b1 b2 bn bn+1 111mnnijijbab第3节 产销不平衡的运输问题及其求解方法数学模型：11111111min122110mmnijijijijijijijijmijjiijnnzc xc xxaimxbjnxn， = ， ， ， = ， ， ， ，第3节 产销不平衡的运输问题及其求解方法数学模型变化： 1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，1

29、1111111min122110mmnijijijijijijijijmijjiijnnzc xc xxaimxbjnxn， = ， ， ， = ， ， ， ，第3节 产销不平衡的运输问题及其求解方法2、总产量总销量（ ）11mnijijab销地产地B1 B2 Bn产量A1A2Amc11 c12 c1n c21 c22 c2n cm1 cm2 cmna1a2am销量 b1 b2 bn第3节 产销不平衡的运输问题及其求解方法数学模型：1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，第3节 产销不平衡的运输问题及其求解方法

30、解题思路：为借助于产销平衡的表上作业法求解，增加一个假想的产地Am+1，由于实际上它不存在，因而由它发往各个销地的物品数量xm+1,j（j=1，2，n），就是各销地Bj所需物品的欠缺额。欠缺的物品未经运输，所以其单位运价cm+1,j=0（j=1，2，n）。第3节 产销不平衡的运输问题及其求解方法销地产地B1 B2 Bn产量A1A2AmAm+1c11 c12 c1n c21 c22 c2n cm1 cm2 cmn 0 0 0a1a2amam+1销量 b1 b2 bn111nmmjijiaba第3节 产销不平衡的运输问题及其求解方法数学模型：11111111min112120nmnijijijij

31、ijijnijijijjiijmmzc xc xxaimxbjmnx， = ， ， ， ， = ， ， ，第3节 产销不平衡的运输问题及其求解方法数学模型变化： 1111min12120mnijijijnijijmijjiijzc xxaimxbjnx， = ， ， ， = ， ， ，11111111min112120nmnijijijijijijnijijijjiijmmzc xc xxaimxbjmnx， = ， ， ， ， = ， ， ，第3节 产销不平衡的运输问题及其求解方法例13：用表上作业法求解下述运输问题的最优解。销地产地B1 B2 B3 B4产量A1A2A3 2 11 3 41

32、0 3 5 9 7 8 1 2 7572 3 4 6 第3节 产销不平衡的运输问题及其求解方法例13：解： 产销不平衡产销平衡销地产地B1 B2 B3 B4 B5产量A1A2A3 2 11 3 4 010 3 5 9 0 7 8 1 2 0 757销量 2 3 4 6 4 1915+4第3节 产销不平衡的运输问题及其求解方法 无穷多最优解 z*=35销地产地B1 B2 B3 B4 B5产量A1A2A3 2 3 2 3 2 4 3 757销量 2 3 4 6 4 1915+4第3节 产销不平衡的运输问题及其求解方法小结采用最小元素法或伏格尔法求初始基可行解时，由于虚拟产地或销地不存在，所以尽管二

33、者的单位运价ci,n+1=0或cm+1,j=0，但不能作为最小运价（元素）优先使用。应从有实际运输任务的产地或销地之间安排运量，最后再考虑虚拟产、销地的0运价。作业4-3作业4-3：用表上作业法求解下列运输问题的最优调运方案和最小总运费。1、要求采用最小元素法、 位势法求解 2、要求采用最小元 素法、闭回路法求解 销地产地 B1 B2 B3 B4产量A1A2A3 3 5 9 4 7 4 8 5 9 7 5 2 300500600销量150 100 400 450销地产地B1 B2 B3产量A1A2 6 5 4 3 7 21525销量20 10 15第4节 应用问题举例例14：设有三个化肥厂（A，B，C）供应四个地区1，2，3，4的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调运方案。需求地区化肥厂 1 2 3 4产量（万吨）ABC16 13 22 1714 13 19 1519 20 23 506050最低需求（万吨）最高需求（万吨）30 70 0 1050 70 30 不限 第4节 应用问题举例例14：解： 产销不平衡产销平衡需求地区化肥厂 1122 3 344产量（万吨）ABCD16 16 13 13 22 22