2019/6/20 运输问感模型与性质 运输问题的一般数学模型 ·运输问愿的一般提法：某种物资有若干产地和销 ·有m个产地生产某种物资，有个地区需要该类物资 地，现在需要把这种物资从各个产地运到各个销 ，b.bbn表示各销地 地，产量总数等于销量总数。已知各产地的产量 和各销地的销量以及各产地到各销地的单位运价 min w- ==2n销量约 A性 0 A 运输问惠的特点与性质 ◆矩阵的元素均为1或0： 存获组的矩库具有特珠的结构写出式系 。每一列只有两个元素为1，其余元素均为0： 0.10.0r,其 △世 3.2运输问题的表上作业法 运输问题的表上作业法 表上作业法和单纯形法的求解思想完全一数，但 是具体作法更加简德。 A整 A性 22019/6/20 2 运输问题模型与性质 • 运输问题的一般提法： 某种物资有若干产地和销 地，现在需要把这种物资从各个产地运到各个销 地，产量总数等于销量总数。已知各产地的产量 和各销地的销量以及各产地到各销地的单位运价 （或运距），问应如何组织调运，才能使总运费 （或总运输量）最省？ 运输问题的一般数学模型 • 有m个产地生产某种物资，有n个地区需要该类物资 • 令a1 , a2 , …, am表示各产地产量， b1 , b2 , …, bn表示各销地 的销量，ai=bj称为产销平衡。 • 设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位 运费，则我们有运输问题的数学模型如下：           = = = = =    = = = = 0 1,2, , 1,2, , min 1 1 1 1 ij j m i ij n j ij i m i n j ij ij x x b j n x a i m w c x 销量约束 产地约束   运输问题的特点与性质 约束方程组的系数矩阵具有特殊的结构，写出式系 数矩阵A，形式如下： n n m m mn x , x ,  , x ; x , x , x ,  ,  ,  ,  , x , x , x 1 1 1 2 1 2 1 2 2 2 1 2                                 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1             m行 n行 ❖ 矩阵的元素均为1或0； ❖ 每一列只有两个元素为1，其余元素均为0； ❖ 列向量Pij =(0,…，0，1，0，…,0,1,0,…0)T，其中 两个元素1分别处于第i行和第m+j行。 3.2 运输问题的表上作业法 （1）单纯形法 （2）表上作业法 由于问题的特殊形式而采用的更简洁、更方 便的方法。 运输问题的表上作业法 表上作业法的基本思想是:先设法给出一个初始方 案,然后根据确定的判别准则对初始方案进行检查、调 整、改进，直至求出最优方案，如图3-1所示。 表上作业法和单纯形法的求解思想完全一致，但 是具体作法更加简捷