第三章 运输问题-1

第三章运输问题3.1运输问题及其数学模型3.2用表上作业法求解运输问题3.3运输问题的进一步讨论3.4应用问题举例§3运输问题§3.1运输问题及其数学模型日常生活中人们常需将某些物品（包括自身）由一个空间位置移动到另一个空间位置——运输

单一品种物资运输调度典型应用产地A1（产量a1）销地B1（销量b1）产地A2（产量a2）销地B2（销量b2）…………产地Am（产量am）销地Bn（销量bn）运价cij怎样调运这些物品使总运费最小？决策变量Xij表示由产地Ai到销地Bj的物品数量Cij为Ai到Bj的单位运价销地产地销量产量运价表产销平衡问题——总产量=总销量即产销不平衡问题——总产量=总销量§3.1运输问题及其数学模型§3.1运输问题及其数学模型典型案例

某企业有三个工厂（B1,B2,B3）和三座仓库（A1,A2,A3）根据生产需要要将仓库的原材料运输到工厂。由于工厂和仓库位置不同，单位运价cij也不同，具体数据如下表。请您为该企业安排一个使总运费最小的运输方案。运价B1B2B3产量A148856A216241682A38162477销量7210241215一数学模型法求解§3.1运输问题及其数学模型由某一产地运往各个销地的物品数量之和等于该产地的产量由各产地运往某一销地的物品数量之和等于该销地的销量单纯形法求解？引入人工变量运输问题数学模型的特点运输问题数学模型的特点运输问题有有限最优解运输问题约束条件的系数矩阵约束条件系数矩阵每一列只有两个1，其余为0；

对产销平衡问题约束条件均为等式，且产量之和=销量之和；求解思路一数学模型法二表上作业法（运输单纯形法）1列出产销平衡表2确定初始调运方案（1）最小元素法（2）西北角法（3）沃格尔（Vogel）法3位势法判定是否最优解4解的改进1列出产销平衡表产销平衡及运价表运价B1B2B3产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量72102412152确定初始调运方案（1）最小元素法

减少运费——单位运价最小的供销业务运价B1B2B3产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量721024121556××产地销地1616×041004161416141×000这时得到该运输问题的一个初始解：x11=56,x22=41,x23=41,x31=16,x32=61,其余为0总运费（目标函数值）=2968元运价B1B2B3产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量721024121556××1616×041004161416141×0002确定初始调运方案（2）西北角法运价B1B2B3产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量721024121556××161600×6666360×3641041至此得到该运输问题的初始基可行解：x11=56,x21=16,x22=66,x32=36,x33=41,其余为0总运费（目标函数值）=3624元运价B1B2B3产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量721024121556××161600×6666360×36410412确定初始调运方案（3）沃格尔（Vogel）法按最小单位运价优先安排物品调运→不得不采用运费很高的其它供销点对→整个运输费增加

罚数=次小单位运价-最小单位运价罚数值较小——不能按最小运价安排运输造成的损失不大罚数值很大——不按最小运价组织运输会造成很大损失

8

总运费=2744元行罚数123运价B1B2B3产量A14x118x128x1356A216x2124x2216x2382A38x3116x3224x3377销量7210241215列罚数1235604640848088887205888885041410414108088以行罚数最大者分配运输方案结果如何？2确定初始调运方案比较上述三种方法给出的初始基可行解，以沃格尔法给出的解的目标函数值最小，最小元素法次之，西北角法解的目标函数值最大。一般，沃格尔法给出的初始解质量最好，常用来作为运输问题最优解的近似解。3位势法判定是否最优解步骤（1）在（最小元素法）初始解表上增加一位势列ui和位势行vj运价B1B2B3产量uiA14x118x128x1356u1A216x2124x2216x2382u2A38x3116x3224x3377u3销量7210241215vjv1v2v356××16×416141×3位势法判定是否最优解（2）计算位势，即建立方程组：运价B1B2B3产量uiA14x118x128x1356u1A216x2124x2216x2382u2