题目

五运输问题-|||-有三个造纸厂A1,A2,A2,其纸的产量分别为8,5和9个单位,有4个集中-|||-用户B1,B2,B2,B4,其需用量分别为4,3,5和6个单位。由各造纸厂到各用-|||-户的单位运价如下表所示,请确定总运费最少的调运方案。-|||-销地 地 B1 B2 B3 B4 产量-|||-产-|||-A 3 12 3 4 8-|||-A2 11 2 5 9 5-|||-A3 6 7 1 5 9-|||-销量 4 3 5 6

题目解答

答案

   

解析

运输问题的核心是寻找总运费最小的调运方案。本题属于不平衡运输问题（总产量22 > 总销量18），需通过虚拟用户平衡供需。解题关键在于：

  1. 最小元素法：优先满足单位运价最低的路线，逐步分配运量；
  2. 供需匹配：确保产量不超过各厂能力，销量满足各用户需求；
  3. 检验最优性：通过计算检验数确认方案是否最优。

步骤1：平衡供需

  • 总产量22，总销量18，需添加虚拟用户B5，销量4，运价为0。

步骤2：按最小运价分配

  1. A3→B3（运价1）：B3需5，A3产9 → 分配5单位，A3剩余4，B3满足。
  2. A2→B2（运价2）：B2需3，A2产5 → 分配3单位，A2剩余2，B2满足。
  3. A1→B1（运价3）：B1需4，A1产8 → 分配4单位，A1剩余4，B1满足。
  4. A1→B4（运价4）：B4需6，A1剩余4 → 分配4单位，A1产尽，B4剩余2。
  5. A3→B4（运价5）：B4剩余2，A3剩余4 → 分配2单位，B4满足，A3剩余2。
  6. A3→B5（运价0）：A3剩余2 → 分配2单位至虚拟用户，产尽。

步骤3：计算总运费

  • A3→B3：$5 \times 1 = 5$
  • A2→B2：$3 \times 2 = 6$
  • A1→B1：$4 \times 3 = 12$
  • A1→B4：$4 \times 4 = 16$
  • A3→B4：$2 \times 5 = 10$
  • 总运费：$5 + 6 + 12 + 16 + 10 = 49$

步骤4：检验最优性

所有非基变量检验数均非负，方案最优。