[2018年必威体育精装版整理]03运输问题.ppt

* 第三章 运输问题 运输问题数学模型 例：某公司经销甲产品，下设3个加工厂4个销售点，其加工厂产量，销售地销量以及各工厂到各销售点单位运价见表，如何调运，总运费最小 20 6 5 6 3 销量 9 5 10 4 7 A3 4 8 2 9 1 A2 7 10 3 11 3 A1 产量 B4 B3 B2 B1 销地 产地 设Xij为Ai到Bj的销量 Minz=3X11+ 11X12+ 3X13 + 10X14+… + 7X31 +4X32 +10X33 + 5X34 X11+X12+X13+X14 =7 ← a1 X21+X22+X23+X24 =4 ←a2 X31+X32+X33+X34 =9 ←a3 该模型又可表示为 i =1，2，3 j =1，2，3，4 Xij≥0， i =1，2，3 j =1，2，3，4 X11+X21+X31 =3 ← b1 X12+X22+X32=6 ← b2 X13+X23+X33 =5 ← b3 X14+X24+X34 =9 ← b4 Xij≥0，i =1，2，3； j =1，2，3，4 上述问题可以扩展为m个产地n个销地的运输问题， 设ai为Ai产量，bj为Bj销地销量，Ai到Bj 单位运价Cij ， 则产销平衡的运输问题其数学模型为 i =1，2，…,m j =1，2，…n Xij≥0， i =1，2，…,m j =1，2，…n 模型特点： ◆模型有m×n个变量，m+n个方程 ◆对产销平衡问题∑ai= ∑bj ◆运输问题（产销平衡）总存在可行解和最优解 1、 ∵ cij≥0 Xij ≥0 ∴ cij Xij ≥0 ∴运输问题一定有界 2、一定有可行解Xij = aibj ∑ai 3、有界且有可行解，所以一定有最优解 ◆ 约束方程系数矩阵具有稀疏结构（见下页），秩r（A）=m+n-1