第3章 运输问题 第1节运输问题的数学模型 第2节表上作业法 第3节产销不平衡的运输问题及其求解 方法 第4节应用举例
第3章 运输问题 第1节 运输问题的数学模型 第2节 表上作业法 第3节 产销不平衡的运输问题及其求解 方法 第4节 应用举例
第1节运输问题的数学模型 已知有m个生产地点A,i=1,2,.,m。可 供应某种物资，其供应量（产量）分别为 a,i=1,2,…,m,有n个销地B, j=1,2,..,n,其需要量分别为b, j=1,2,…,n,从A到B,运输单位物资的运 价（单价）为C,这些数据可汇总于产销平 衡表和单位运价表中，见表3-1，表3-2。 有时可把这两表合二为一
第 1节 运输问题的数学模型 • 已知有 m个生产地点 A i,i=1,2,… ， m。可 供应某种物资，其供应量 (产量 )分别为 a i ，i=1 ， 2 ， … ， m，有 n个销地 B j ， j=1,2,…,n，其需要量分别为 bj ， j=1,2,…,n，从 A i 到 B j运输单位物资的运 价 (单价 ) 为 cij，这些数据可汇总于产销平 衡表和单位运价表中，见表3-1，表3-2 。 有时可把这两表合二为一
表3-1产销平衡表 销地 产地 12..n 产量 1 2 2 i m a m 销量 bib2...bn
表3-1产销平衡表 销地 产地 1 2 … n 产量 1 2 ┆ m a 1 a2 ┆ am 销量 b1 b2 … bn
表3-2单位运价表 销地 12 n 产地 1 C11 C12 Cin 2 C21 C22 C2n m Cm1 Cm2 Cmn
表3-2单位运价表 销地 产地 1 2 ┉ n 1 2 ┆ m c11 c12 ┈ c1n c21 c22 ┈ c2n ┇ cm1 cm2 ┈ cmn
产销平衡表和单位运价表 销地 产地 12.n 产量 1 C11 12- Cin a1 2 C21 020 a2 m Cm1 Cm2-Cmn m 销量 b1 b2...bn
销地 产地 1 2 … n 产量 1 2 ┆ m c11 c12 ┈ c1n c21 c22 ┈ c2n ┇ cm1 cm2 ┈ cmn a1 a2 ┆ am 销量 b1 b2 … bn 产销平衡表和单位运价表
若用x:表示从A到B的运量，那么在产销平衡的 条件下，要求得总运费最小的调运方案， 数学模型 minz=∑∑cx i=1 i=1 ∑xg=b,j=1,2,n (3-1) =1 s.t. ∑)=4，i=1,2,,m (3-2) j X ≥0 m×n个变量，(m+n)个约束方程
若用xij表示从 A i到B j的运量，那么在产销平衡的 条件下，要求得总运费最小的调运方案， 数学模型 ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ == − == − = ∑ ∑ ∑∑ = = = = 0 ,,2,1 )23( ,,2,1 )13( .. min 1 1 1 1 ij n j iij m i jij m i n j ijij x iax m njbx ts xcz " " m × n个变量，(m+n)个约束方程
其系数矩阵的结构比较松散，且特殊 X1l七12·X1n七21X22·七2n…Xm1 Xm2·Xmn 41 山2 11…1 m行 Mm 1 …1 m+j 1 1 1 1 1 1 n行
其系数矩阵的结构比较松散，且特殊 行 行 n m v v v u u u xxxxxxxxx n m n n mm mn ⎪ ⎪ ⎭ ⎪ ⎪ ⎬ ⎫ ⎪ ⎪ ⎭ ⎪ ⎪ ⎬ ⎫ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ 1 1 1 1 1 1 1 1 1 111 111 111 2 1 2 1 1211 22211 2 21 " % "% % " " " % " " # # " "" " i m+j
该系数矩阵中对应于变量x的系数向量P' 其分量中除第i个和第m+j个为1以外，其余的都 为零。即 P(0,…,1,0,…,0,1,0,…,0)T=e+e时
该系数矩阵中对应于变量xij的系数向量Pij ， 其分量中除第i个和第m+j个为1以外，其余的都 为零。即 Pij=(0,… ,1,0,…,0,1,0,…,0) T=e i+em+j
对产销平衡的运输问题，有以下 关系式存在： i=1 模型最多只有n+m-1个独立约束方程 系数矩阵的秩≤n+m-1
对产销平衡的运输问题，有以下 关系式存在： 1 11 1 1 1 n nm mn m j ij ij i j ji i j i b x xa = == = = = ⎛ ⎞ ⎛ ⎞ = == ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ∑ ∑∑ ∑∑ ∑ 模型最多只有n+m-1个独立约束方程 系数矩阵的秩≤n+m-1
第2节 表上作业法 表上作业法是单纯形法在求解运输问题时的一种简 化方法，其实质是单纯形法。但具体计算和术语有 所不同。可归纳为： (1)找出初始基可行解。，即在(m×n)产销平衡表上用 西北角法或最小元素法，Vogel法给出m+n-1个数 字，称为数字格。它们就是初始基变量的取值。 (2)求各非基变量的检验数，即在表上计算空格的检 验数，判别是否达到最优解。如己是最优解，则停 止计算，否则转到下一步。 (3)确定换入变量和换出变量，找出新的基可行解。 在表上用闭回路法调整。 (4)重复(2)，(3)直到得到最优解为止
第2节 表上作业法 • 表上作业法是单纯形法在求解运输问题时的一种简 化方法，其实质是单纯形法。但具体计算和术语有 所不同。可归纳为： (1) 找出初始基可行解。即在(m×n)产销平衡表上 用 西北角法或最小元素法，Vogel法给出m+n-1个数 字，称为数字格。它们就是初始基变量的取值。 (2) 求各非基变量的检验数，即在表上计算空格的检 验数，判别是否达到最优解。如已是最优解，则停 止计算，否则转到下一步。 (3) 确定换入变量和换出变量，找出新的基可行解。 在表上用闭回路法调整。 (4) 重复(2)，(3)直到得到最优解为止