运筹学 (第三版) 第1节 《运筹学》教材编写组 运输问题 的数学模 第3章运输问题 型 第2节 表上作业 法 钱颂迪制作 清华大学出版社
第1节 运输问题 的数学模 型 第2节 表上作业 法 钱颂迪制作 运筹学 （第三版） 《运筹学》教材编写组 第3章 运输问题 清华大学出版社
第3章运输问题 第1节运输问题的数学模型 第2节表上作业法 第3节产销不平衡的运输问题及其求解 方法 第4节应用举例
第3章 运输问题 第1节 运输问题的数学模型 第2节 表上作业法 第3节 产销不平衡的运输问题及其求解 方法 第4节 应用举例
第1节运输问题的数学模型 已知有m个生产地点A,i=1,2,,m。 可供应某种物资,其供应量(产量)分别为 a,i=1,2,…,m,有n个销地B, 1,2,,n,其需要量分别为b;, j=1,2,,n,从A到B运输单位物资的运 价(单价)为c,这些数据可汇总于产销平 衡表和单位运价表中,见表3-1,表3-2。 有时可把这两表合二为
第1节 运输问题的数学模型 • 已知有m个生产地点Ai ,i=1,2,…，m。 可供应某种物资，其供应量(产量)分别为 ai，i=1，2，…，m，有n个销地Bj， j=1,2,…,n，其需要量分别为bj， j=1,2,…,n，从Ai到Bj运输单位物资的运 价(单价)为cij，这些数据可汇总于产销平 衡表和单位运价表中，见表3-1，表3-2。 有时可把这两表合二为一
表3-1 销地12 产量 产地 A A 销量 bi B2 --- BN
表3-1 销地 产地 1 2 ┉ n 产量 1 2 ┆ m A 1 A2 ┆ Am 销量 B1 B2 ┈ BNn
表3-2 销地|12-nm 产地 11C12 C 21C22 m CmI Cm2
表3-2 销地 产地 1 2 ┉ n 1 2 ┆ m C11 c12 ┈ c1n C21 c22 ┈ c2n ┇ cm1 cm2 ┈ cmn
若用x;表示从A到B的运量,那么在产销平衡的 条件下,要求得总运费最小的调运方案, 数学模型 minz=∑∑cnx i=1j=1 d J7 (3-1 s∑x=a=1,2, (3-2) ≥0
若用xij表示从Ai到Bj的运量，那么在产销平衡的 条件下，要求得总运费最小的调运方案， 数学模型 = = − = = − = = − = = 0 1,2, , (3 2) 1,2, , (3 1) . . min 1 1 1 1 i j n j i j i j m i i j j m i n j i j i j x x a i m x b j n st z c x
这就是运输问题的数学模型。它包含m×n 个变量,(m+n)个约束方程。其系数矩阵的 结构比较松散,且特殊 1112 x2n∵ xml dn2…xmm
这就是运输问题的数学模型。它包含m×n 个变量，(m+n)个约束方程。其系数矩阵的 结构比较松散，且特殊。 行 行 n m v v v u u u x x x x x x x x x n m n n m m mn 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 11 12 1 21 22 2 1 2
该系数矩阵中对应于变量x,的系数向量P 其分量中除第i个和第m+j个为1以外,其余的都 为零。即 (0,…,1,0,…,0,1,0,…,0)T=e;+ent 对产销平衡的运输问题,由于有以下关系式存 ∑x=∑
该系数矩阵中对应于变量xij的系数向量Pij， 其分量中除第i个和第m+j个为1以外，其余的都 为零。即 Pij=(0,… ,1,0,…,0,1,0,…,0)T=ei +em+j 对产销平衡的运输问题，由于有以下关系式存 在： = = = = = = = = = n j m i n j m i i m i ij n j bj xij x a 1 1 1 1 1 1
第2节表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化 方法,其实质是单纯形法。但具体计算和术语有所不 同。可归纳为: (1)找出初始基可行解。即在(ⅷm×n)产销平衡表上用 西北角法或最小元素法,Ⅴogel法给出m+n-1个数字 称为数字格。它们就是初始基变量的取值。 (2)求各非基变量的检验数,即在表上计算空格的检 验数,判别是否达到最优解。如已是最优解,则停止 计算,否则转到下一步。 ·(3)确定换入变量和换出变量,找出新的基可行解 在表上用闭回路法调整。 (4)重复(2),(3)直到得到最优解为止
第2节 表上作业法 • 表上作业法是单纯形法在求解运输问题时的一种简化 方法，其实质是单纯形法。但具体计算和术语有所不 同。可归纳为： • (1) 找出初始基可行解。即在(m×n)产销平衡表上用 西北角法或最小元素法，Vogel法给出m+n-1个数字， 称为数字格。它们就是初始基变量的取值。 。 • (2) 求各非基变量的检验数，即在表上计算空格的检 验数，判别是否达到最优解。如已是最优解，则停止 计算，否则转到下一步。 • (3) 确定换入变量和换出变量，找出新的基可行解。 在表上用闭回路法调整。 • (4) 重复(2)，(3)直到得到最优解为止
例1某公司经销甲产品。它下设三个加 工厂。每日的产量分别是:A1为7吨,A2为4 吨,A3为9吨。该公司把这些产品分别运往四 个销售点。各销售点每日销量为:B1为3吨, B2为6吨,B3为5吨,B4为6吨。已知从各工 厂到各销售点的单位产品的运价为表3-3所示。 问该公司应如何调运产品,在满足各销点的 需要量的前提下,使总运费为最少
例1 某公司经销甲产品。它下设三个加 工厂。每日的产量分别是：A1为7吨，A2为4 吨，A3为9吨。该公司把这些产品分别运往四 个销售点。各销售点每日销量为：B1为3吨， B2为6吨，B3为5吨，B4为6吨。已知从各工 厂到各销售点的单位产品的运价为表3-3所示。 问该公司应如何调运产品，在满足各销点的 需要量的前提下，使总运费为最少