中南民族大学：《运筹学》第六章 运输问题（叶娟）

第六章运输问题

1 第六章运输问题

运输问题的模型

2 运输问题的模型

运输问题的描述 运输问题的一般提法是这样的:某种物资 有若干个产地和销地,若已知各个产地 的产量、各个销地的销量以及各产地到 各销地的单位运价(或运输距离)。问 应如何组织调运,才能使总运费(或总 的运输量)最省? 将此问题更具体化,假定有m个产地,n 个销地

3 运输问题的描述 运输问题的一般提法是这样的：某种物资 有若干个产地和销地，若已知各个产地 的产量、各个销地的销量以及各产地到 各销地的单位运价（或运输距离）。问 应如何组织调运，才能使总运费（或总 的运输量）最省？ 将此问题更具体化，假定有m个产地，n 个销地

a1第i产地的供应量,i=1,2 b第销地的需求量,j=1,2,…,n Cn-从i产地到j销地的单位运费,i=1, 2,…,m,j=1,2,…,n xi产地到销地的调运数量。 则该问题为求解最佳调运方案,即求解所 有x的值,使总的运输费用m、达到 最少。决策变量为x1 ∑∑cnx i=1j=1

4 ai—第i产地的供应量，i=1，2，…，m。 bj—第j销地的需求量，j=1，2，…，n。 cij—从i产地到j销地的单位运费，i=1， 2，…，m，j=1，2，…，n。 xij—i产地到j销地的调运数量。 则该问题为求解最佳调运方案，即求解所 有xij的值，使总的运输费用 达到 最少。决策变量为xij 。 1 1 m n ij ij i j c x = =  

般模型形式 minZ=∑∑c,x i=1j=1 ∑x≥b,j=1,2,…,n s. x≤a i=1.2 x≥0,所有的i,j

5 一般模型形式 1 1 min m n ij ij i j Z c x = = =  1 1 , 1,2, , . . , 1,2, , 0, m ij j i n ij i j ij x b j n s t x a i m x = =   =       =         所有的i，j

类型 (1)当∑a=∑b时,为平衡型运输问题 (2)当Σ4≠b时,为不平衡型运输问题

6 类型 （1）当 时，为平衡型运输问题。 （2）当 时，为不平衡型运输问题。 1 1 m n i j i j a b = =  = 1 1 m n i j i j a b = =  

平衡型运输问题的模型 minZ=∑∑cx ∑x=b,j=1,2,…,n L- 1∑x=a1,1=12,m x≥0,所有的i,j

7 平衡型运输问题的模型 1 1 min m n ij ij i j Z c x = = =  1 1 , 1,2, , . . , 1,2, , 0, m ij j i n ij i j ij x b j n s t x a i m x = =  = =      = =         所有的i，j

平衡型运输问题的矩阵表示 该模堑苞含有m*n个苓量,m+n个药束方蓕, 其系数矩阵A如下: x12∵x1n m行 11…1 A

8 平衡型运输问题的矩阵表示 该模型包含有m*n个变量，m+n个约束方程， 其系数矩阵A如下： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A         =       11 12 1n x x x  21 22 2n x x x   m m mn 1 2   x x x m行 n行

闭回路

9 闭回路

闭回路的意义 X X13 2 23 X 42 44

10 闭回路的意义 x11 x21 x12 x13 x14 x23 x42 x44