产 地 销 地 B1 4 B2 3 B3 5 B4 6 产量 10 4 9 A1 A2 A3 销量 解：由于总产量22大于总销量18，故本问题是个产销不平衡的运输问题，为求本问题可做假设增加一销地B5，则可将表3—2改写成表3—3 销 产 地 地 B1 4 B2 3 B3 5 B4 6 B5 22-18=4 产量 8 5 9 A1 A2 A3 销量 有了表3—3，就很容易用表上作业法求解了 例3．假设A1,A2两地各有某类物资8万吨与7万吨，而收点B2处至少需要这类物资3万吨，至多需要5万吨，B2处至少需要6万吨，至多8万吨，而B3处至少4万吨，至多5万吨，又从A1,A2运送这类物资去B1,B2与B3的运价为 表3—4
B1 2 5 B2 3 7 B3 10 1 A1 A2 单位为千元/万吨，问应如何组织运输，即把A1，A2两地的物资运完使总的
第 5 页 共 14 页
运费用为最少？
解：现在A1，A2共有物资15万吨，能够满足B1,B2,B3三地的最低总需要量13万吨，但离最高总需要量18万吨还少3万吨，为了求得平衡，我们虚设一个有3万吨物资的发点A3。另外，B1,B2与B3三地都有最低需求量与最高需求量两部分，我们可以把每一个B?,2,3)看成两个收点B?j与B?j?的重j(j?1合，B?j处的收量就是Bj处的最低需要量，这部分物资必须由A1或A2供应,所以可以假想由A3到B?,2,3)的运价为无穷,或为一很大的正数M;B?j?j(j?1处的收量则是Bj处的最高需求量与最低需求量之差,既然这部分需要可以满足也可以不满足,所以B?j?处的需要量可以由A1或A2供应一部分,再由A3供应剩余的部分(因为A3虚拟的发点,所以A3供应的部分实际上并不供应).
?由A3到B?,2,3)的运价为0,又由A1,A2到B?j与B?j?的运价由A1,A2到Bjj(j?1处的运价相同,所以现在的问题变成有三个发点(其中有一个是虚拟的),六个收点的收发平衡型问题,相应的运价表如下: 表3—5 B1? B1?? B1? B2?? B3? B3?? A1 A2 2 2 3 3 10 10 5 5 7 7 1 1 A3 M 0 M 0 M 0 根据最小元素法,得到初始调运方案为: 表3—6
第 6 页 共 14 页
B1? B1?? B1? B2?? B3? B3?? 8 7 3 A1 A2 3 -1 M?1 -1 -2 2 2 5 1 M 0 1 1 2 13 4 M?6 13 1 6 1 A3 3 6 4 因为检验数t22??2?0，所以经过调整得到新的调整方案为: 表3—7 B1? B1?? B1? B2?? B3? B3?? 8 7 3 A1 A2 3 －1 M 1 1 1 2 5 1 M?1 2 2 2 13 4 M?4 13 1 4 1 A3 3 6 4 又因为检验数t21??1?0,所以再一次调整得到新的调整方案为: 表3—8 B1?? B1? B2?? B3? B3?? 8 7 3 A1 A2 2 1 M 0 1 1 2 6 1 M?1 1 2 2 2 12 4 2 1 A3 M?4 4 3 6 4 1 现在检验数都为非负，所以上表给出了最优方案。在此最优方案中，由A1，
A2分别供应为2万吨，一共供应B14万吨比它的最低需求量多1万吨；又由
A1供应B26万吨，正好满足它的最低需求量；再由A2供应B35万吨物资，达到它的最高需求量，总的运输费用为
2×2＋2×5＋6×3＋5×1=37千元
第 7 页 共 14 页
四、线性规划的三种常用的计算方法
例4 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售,各工厂的生产量、各工厂的产量、各销售点的销售量（假定单位均为吨）以及各工厂到各销售点的单位运价（元/吨）示于表4—1中，要求研究产品如何调运才能使总运费最小？ 表4—1 产 地 销 地 B1 8 B2 14 B3 12 B4 14 产量 16 10 22 48 A1 A2 A3 销量 下面就用三种方法解决这道题: 1．最小元素法
人们容易直观想到，为了减少运费，应优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。即对所有i和j，找出ci0j0?min(cij)，并将xi0j0?xi0j0min(aij,bj0)的物品量由Ai0。若xi0j0?a?ai0；如果xi0j0?bj0。则销地Bj0的需求已全部得到满足，以后不再考虑这个销地，且Ai0的可供量由ai0减为少为aj0?bj0。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案（完 整的解）为止。这样就得到了运输问题的一个初始基可行解（初始调运方案）。
第 8 页 共 14 页