二、销大于产
销大于产的运输问题的特征是Σai < Σbj，其数学模型为：
mnminf???cijxiji?1j?1?ni?1,?,m??xij?ai ?j?1??mj?1,?n??xij?bj?i?1?xij?0,i?1,?,m;j?1,?,n???解此问题可假想一个产地Am+1，其产量为：am+1 = Σbj－Σai； 若用xm+1，j表
示从Am+1到Bj的运量，可令cm+1，j=0或等于第Bj产地每缺单位物资的损失。因为xm+1，j实际上表示Bj销地所缺的物资数量。经处理后，问题变成了产销平衡的运输问题，其数学模型为：
minf???cijxiji?1j?1m?1n?ni?1,?,m?1??xij?ai ?j?1??m?1j?1,?n??xij?bji?1??xij?0,i?1,?,m?1;j?1,?,n???此时，可用表上作业法求解。在用最小元素法求解该问题初始基可行解时，若
某行的运价全为零时，则该行最后考虑。
第四节 运输问题的应用
一、一般的产销不平衡运输问题
例3.3 表3—12给出了三个产地及四个销地的某物资供应量与需求量及从各产到各销地的单位物资运价（元/单位物资），试求出运费最小的运输方案。
第三章——11
表3—12 销 地 产地 A1 A2 A3 需求量(t) B1 3 7 9 50 B2 2 5 6 100 B3 4 2 3 150 B4 5 1 5 50 供应量(t) 200 100 150 450 350 解 由表可知，总供应量为450(t)，总需求量为350(t)，即问题为产大于销的运输问题。因此，需要假想一个销地B5，其需求量为450－350=100(t)。问题并未给出物资的存储费用，因此，从各产地到B5的单位运价视为零，即ci5=0（i=1，2，3）。这样得到新的产销平衡表如表3—13。 表3—13 销 地 产地 A1 A2 A3 需求量(t) B1 3 7 9 50 B2 2 5 6 100 B3 4 2 3 150 B4 5 1 5 50 B5 0 0 0 100 供应量(t) 200 100 150 450 450 用表上作业法解得该问题的最优运输方案为：x11=50，x12=100，x15=50，x23=50，x24=50，x33=100，x35=50。其中x15=50，x35=50表示A1，A3各有50个单位的物资库存。总运费为800元。
例3.4 某运输问题有三个产地和三个销地，产地的总供应量小于销地的最高需求量之和，但超过了销地的最小需求量之和。现在，各销地的最低需求必须满足，最低需求到最高需求的之间的需求若不能满足，会造成经济损失，其中B1销量必须满足，B2、B3不能满足的单位损失分别为3元和2元。单位运价、供应量与需求量见表3—14。求出最优调运方案。
表3—14 销 地 产地 A1 A2 A3 最低需求 最高需求
B1 5 6 3 600 600 B2 1 4 2 120 200 第三章——12
B3 7 6 5 300 430 供应量 200 800 150 1150 解 B2的最高需求与最低需求不相等，而B1的最低需求必须满足，因此可将B2看成两个销地B21和B22，其中B21的需求量为B2的最低需求量，该需求量必须全部满足；B22的需求量为B2的最高需求量减去最低需求量，即为200－120=80，该需求量可以不被满足。对销地B3也可作同样的处理。这样问题就变为一个三个产地、五个销地的运输问题，其中总产量为1150，总供应量为1230，因此是一个销大于产的问题。为解此问题，又要假设一个产地A4，其产量为1230－1150 = 80。为了使各销地的最低销量得到满足，可令A4运往B1、B21、B31的运价为M，即给出一个很高的运价。这样就可以得到如下产销平衡表，见表3—15。
表3—15 产销平衡表 销 地 产地 A1 A2 A3 A4 需求量 B1 5 6 3 M 600 B21 1 4 2 M 120 B22 1 4 2 3 80 B31 7 6 5 M 300 B32 7 6 5 2 130 供应量(t) 200 800 150 80 1230 1230
用表上作业法求解，可以得到如表3—16所示的调运方案。
表3—16 最优调运表 销 地 产地 A1 A2 A3 A4 需求量
从最优调运表中可以看出，B1和B2的需求量得到全部满足，而B3的需求量满足了350。总费用（包括缺货损失费160元）为8100元。
B1 B21 120 120 B22 80 80 B31 300 300 B32 50 80 130 供应量(t) 200 800 150 80 1230 1230 450 150 600 二、生产与存储问题
例3.5 某高科技企业生产某种光电通讯产品，现要安排今后4个季度的生产计划。已知今后四个季度的合同签定数，企业各季度生产能力以及各季度的生产成本
第三章——13
如表3—15所示。考虑资金的机会成本，预计每件产品每存储一个季度的费用为0.1千元。在完成合同的条件下，试安排这四个季度的生产计划，使生产成本与存储费用之和最小。
表3—17 季 度 1 2 3 4 解 设xij表示第i季度生产第j季度交货的该种产品的数量，考虑生产成本与存储费用后，xij所对应的目标函数中的价格系数cij如表3—18所示。
表3—18 xij所对应的价格系数cij j i 1 2 3 4 这样问题的数学模型可以描述为：
min f = 3.2x11+3.3x12+3.4x13+3.5x14+3.33x22+3.43x23
+3.53x24+3.31x33+3.41x34+3.42x44 x11+x12+x13+x14≤270 x22+x23+x24≤260
x33+x34≤280
x44≤270
x11 =230 x12+x22 =265 x13+x23+x33 =255 x14+x24+x34+x44 =245
xij≥0，i=1，?，4；j=1，?，4；i≥j
模型中，前4个条件为生产能力约束，后四各条件为合同限制约束。观察该模型，若将x21、x31、x32、x41、x42、x43等变量补齐，则模型变为一个标准的运输问题数学模型。为了保证模型的性质不变，必须使这些补齐的变量为0。为此，可在目标函数中令这些变量的系数为M，这样就得到一个产销不平衡的运输问题。此时，
1 3.2 2 3.3 3.33 3 3.4 3.43 3.31 4 3.5 3.53 3.41 3.42 合同签定数（台） 230 265 255 245 生产能力（台） 270 260 280 270 生产成本（千元） 3.2 3.33 3.31 3.42 第三章——14
可假设一个销地，变成产销平衡问题。产销表及运价表如表3—19所示。
表3—19 销地 产地 1 2 3 4 销量
用表上作业法，可求得四个季度的生产计划如表3—20所示。 表3—20 销地 产地 1 2 3 4 销量 从最优调运表中可以看出，第1季度生产270台，其中40台用于满足第季度需要，第2季度生产225台，第3季度生产260台，其中5台用于满足第4季度的需要，第4季度则生产240台。总费用为3299.15千元。
1 230 230 2 40 225 265 3 255 255 4 5 240 245 5 55 30 85 产量 270 280 260 270 1080 1080 1 3.2 M M M 230 2 3.3 3.33 M M 265 3 3.4 3.43 3.31 M 255 4 3.5 3.53 3.41 3.42 245 5 0 0 0 0 85 产量 270 280 260 270 1080 1080 三、转运问题
例3.6 某公司生产某种高科技产品。该公司在大连和广州设有两个分厂生产这种，在上海和天津设有两个销售公司负责对南京、济南、南昌和青岛四个城市进行产品供应。因大连与青岛相距较近，公司同意也可以向青岛直接供货。各厂产量、各地需要量、线路网络及相应各城市间的每单位产品的运费均标在图4—1中，单位为百元。现在的问题是：如何调运这种产品使公司总的运费最小？
解 如图所示，给各城市编号，即i=1，2，?，8分别代表广州、大连、上海、天津、南京、济南、南昌和青岛。
设xij表示从i到j的调运量（台），则问题的目标函数为
min f = 2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37
+6x38+4x45+4x46+6x47+5x48
第三章——15