《运筹学》课程教学课件（PPT讲稿）第三章 运输问题

第三章运输问题运输问题的数学模型表上作业法产销不平衡的运输问题及应用2025/4/5

2025/4/5 2 第三章 运输问题 ◼ 运输问题的数学模型 ◼ 表上作业法 ◼ 产销不平衡的运输问题及应用

S1运输问题的典例及数学模型引例某公司从三个产地A，A，将产品运往四个销地BBB，B各产地的产量，各销地的销量，及各产地往各销地的运费单价如表所示。应如何调运可使运费最小？销地B1B2B3B4产量运费单价(吨)产地A131131071928A24As741059366销量 (吨)52025/4/53

2025/4/5 3 §1 运输问题的典例及数学模型 一、 引例 某公司从三个产地 ， ， 将产品运往四个销地 ， ， ，各产地的产量，各销地的销量，及各产地往各销 地的运费单价如表所示。应如何调运可使运费最小？ A1 A2 B1 B2 B3 A3 B4 销地 运费单价 产地 B1 B2 B3 B4 产量 （吨） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（吨） 3 6 5 6

解：从表中可知：总产量=总销量。这是一个产销平衡的的产j运输问题。假设表示从产地运往销地品数量，建立如下表格：i= 1,2,3:销地产量B1B2B3B4运费单价（吨）产地A13Xi11137X1310 X14Xi2A219284X22X21X23X24A3745910X33X31X32X343656销量 (吨）于是可建立如下的数学模型2025/4/5

2025/4/5 4 解：从表中可知：总产量 = 总销量。这是一个产销平衡的 运输问题。假设 表示从产地 运往销地 的产 品数量， 建立如下表格： ij x i j i =1,2,3; j =1,2,3,4. 于是可建立如下的数学模型： 销地 运费单价 产地 B1 B2 B3 B4 产量 （吨） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（吨） 3 6 5 6 11 x 12 x 13 x 21 x 22 x 23 x 31 x 32 x 33 x 14 x 24 x 34 x

目标函数：MinZ=3x+11xi2+3x13+10x14+X21 +9x22 +2X23 +8X24+7x31 +4X32 +10x33 +5X34约束条件：X11+X12+X13+X14=720X21+X22+X23+ X24 = 4产量约束X31 + X32+ X33+X34=9Xi1 + X21 + X31 = 3X12 + X22 + X32 = 620销量约束X13 + X23 + X33 = 5X14 + X24 + X34 = 6x ≥ 0,i=1,2,3; j= 1,2,3,42025/4/5

2025/4/5 5 目标函数 ： 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 7 4 10 5 9 2 8 3 11 3 10 x x x x x x x x MinZ x x x x + + + + + + + + = + + + 约束条件： 947 3 1 3 2 3 3 3 4 2 1 2 2 2 3 2 4 1 1 1 2 1 3 1 4 + + + = + + + = + + + = x x x x x x x x x x x x 产量约束 销量约束 20 20 0, 1,2,3; 1,2,3,4 6563 1 4 2 4 3 4 1 3 2 3 3 3 1 2 2 2 3 2 1 1 2 1 3 1  = = + + = + + = + + = + + = x i j x x x x x x x x x x x x i j

二、一般运输问题数学模型设有m个产地，分别为A，A22.n个销地，分别是B.B2.....Bn从产地A,运往销地B，的单位运价是Cij，运量XiS；是产地A,的产量；d，是销地B,的销量。则该运输问题的模型如下：2025/4/5

2025/4/5 6 设有m个产地，分别为 ; n 个销地，分别是 ； 从产地 运往销地 的单位运价是 ，运量 是产地 的产量； 是销地 的销量。 A1 , A2 ,.Am B B Bn , ,. 1 2 Ai Bj cij xij si Ai d j Bj 二、一般运输问题数学模型 则该运输问题的模型如下：

Min f =cyxi"is.tx=dj = l...., n"i- 1....m=SiX1Xi ≥ 0,i = 1....m,ji = 1,...,nZs,=2d,说明：当时，称其为产销平衡的运输问题i=lj=l否则产销不平衡。2025/4/5

2025/4/5 7 j n x i m x s i m st x d j n Min f c x i j i n j i j j m i i j m i n j i j i j 1,., 0, 1,. , 1,. . 1,., 1 1 1 1 =  = = = = = =    = = = = 说明：当 时，称其为产销平衡的运输问题， 否则产销不平衡。   = = = n j j m i si d 1 1

说明：从上述模型可以看出：（1）这是一个线性规划的模型；（2）变量有m×n个；（3）约束条件有m+n个；（4）系数矩阵非常稀疏；系数矩阵的秩一般为（m+n-1)而非m+n若直接用单纯形法求解，显然单纯形表比较庞大，于是在单纯形法的基础上创建了表上作业法求解运输问题这一特殊的线性规划问题2025/4/5

2025/4/5 8 说明：从上述模型可以看出： （1）这是一个线性规划的模型； （2）变量有m×n个； （3）约束条件有 m+n 个； （4）系数矩阵非常稀疏；系数矩阵的秩一般为（m+n-1), 而非m+n 。 若直接用单纯形法求解，显然单纯形表比较庞大，于是在 单纯形法的基础上创建了表上作业法求解运输问题这一特 殊的线性规划问题

82运输问题的表上作业法从第一节的运输问题的数学模型可知，运输问题实际上也属于线性规划，但由于运输问题的特殊性（变量个数较多系数矩阵的特点），如果用单纯形表格方法送代，计算量很大。今天介绍的“表上作业法”，是针对运输问题的特殊求解方法，实质还是单纯形法，但减少了计算量。表上作业法适用于求解产销平衡的运输问题。（产销不平衡的问题可转化为平衡问题）2025/4/5

2025/4/5 9 从第一节的运输问题的数学模型可知，运输问题实际上 也属于线性规划，但由于运输问题的特殊性（变量个数较多， 系数矩阵的特点），如果用单纯形表格方法迭代，计算量很 大。今天介绍的 “表上作业法” ，是针对运输问题的特殊求解 方法，实质还是单纯形法，但减少了计算量。 表上作业法适用于求解产销平衡的运输问题。（产销不平 衡的问题可转化为平衡问题） §2 运输问题的表上作业法

表上作业法一般步骤1、找出初始基本可行解；2、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优解；否则转第三步；3、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可行解；4、重复第二、第三步，直至得到最优解。销地产量B1B2B3B4运费单价(吨）产地A1311310792A2184A37410593656销量 (吨）2025/4/510

2025/4/5 10 表上作业法一般步骤： 1、找出初始基本可行解； 2、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优 解；否则 转第三步； 3、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可 行解； 4、重复第二、第三步，直至得到最优解。 销地 运费单价 产地 B1 B2 B3 B4 产量 （吨） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（吨） 3 6 5 6

确定初始基本可行解：对于有m个产地n个销地的产销平衡问题，有m个关于产量的约束方程和n个关于销量的约束方程。表面上，共有m+n个约束方程。但由于产销平衡，其模型最多只有m+n-1个独立的约束方程，所以运输问题实际上有m+n-1个基变量。在mxn的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。那么在该例中，应有3+4-1=6个基变量。2025/4/511

2025/4/5 11 一、确定初始基本可行解： 对于有m个产地n个销地的产销平衡问题，有m个关于产量 的约束方程和n个关于销量的约束方程。表面上，共有m+n个 约束方程。 但由于产销平衡，其模型最多只有m+n-1个独立的约束方 程，所以运输问题实际上有m+n-1个基变量。在m×n的产销 平衡表上给出m+n-1个数字格，其相对应的调运量的值即为 基变量的值。 那么在该例中，应有 3+4-1=6个基变量