运输问题(Transportation Problem)是运筹学中的经典问题,通常涉及将资源从供应点转移到需求点,以最小化运输成本或满足需求。这个问题在各种实际场景中都有广泛的应用,包括但不限于以下几个方面:供应链管理:在供应链中,最小化运输问题可用于确定最有效的货物运输方式,以满足各个节点之间的需求。这包括原材料从供应商到制造商、成品从制造商到分销商、以及最终产品从分销商到消费者的运输;生产计划:在制造业中,通过最小化运输问题可以优化原材料的运输和配送,以确保生产线上的原材料及时到达,从而最大程度地减少生产停滞和库存成本;市场营销:在市场营销中,最小化运输问题可以用于确定最佳的销售区域和分销网络,以最大程度地减少产品运输成本,并确保产品能够快速到达目标市场;资源分配:在人力资源管理和项目管理中,最小化运输问题可用于确定最佳的人员分配和资源调配方案,以确保项目在时间和成本方面的有效执行;网络流量优化:在计算机网络中,最小化运输问题可以用于优化数据包的传输路径,以最大程度地减少网络拥塞和延迟等。有许多最大化的问题也可以通过适当的转化转换为最小化运输问题,例如,在最大化利润的问题中,可以通过将成本取负值,并将问题转化为最小化成本的运输问题来求解。
一、最小化运输问题
最小化运输问题(transportation problem) 属于线性规划问题,可以根据模型按照线性规划的方式求解,但由于其特殊性,用常规的线性规划来求解并不是最有效的方法,它是运输问题的标准型,后面简称为运输问题。
1.1运输问题的数学模型
一般地,产销平衡的运输问题可以表述为:设有\(m\)个地点(称为产地或发地)\(A_1\),\(A_2\),...,\(A_m\)的某种物资调至\(n\)个地点(称为销地或收地)\(B_1\),\(B_2\),...,\(B_n\),各个产地需要调出的物资量分别为\(a_i\)单位,各个销地需要调进的物资量分别为\(b_j\) 单位,且各个发点的供应量之和等于各个收点的需求量之和。已知每个发点\(A_i\) 到每个收点\(B_j\) 调运单位物资的价格为\(c_{ij}\),现问如何安排调运,才能使总运费最小。
于是得产销平衡运输问题的数学模型:
\(min\) \(z\) = \(\sum_{i=1}^m\)\(\sum_{j=1}^n\)\(c_{ij}\)\(x_{ij}\)
\(\sum_{j=1}^n\)\(x_{ij}\)=\(a_i\) \(i=1,2,...,m\)
\(\sum_{i=1}^m\)\(x_{ij}\)=\(b_j\) \(j=1,2,...,n\)
\(x_{ij} \geq 0\) \(i,j=1,2,...,n\)
不平衡运输问题只要简单地调整约束的松紧关系即得。
1.2 Python计算程序
例1: 有三个造纸厂A1、A2 和A3,造纸量分别为16 个单位、10 个单位和22 个单位,四个客户B1、B2、B3 和B4 的需求量分别为8 个单位、14 个单位、12 个单位和14 个单位。造纸厂到客户之间的单位运价如表所示,确定总运费最少的调运方案。单位运价表如下所示:
[[ 4 12 4 11]
[ 2 10 3 9]
[ 8 5 11 6]]
总产量等于总销量,都为48个单位,这是一个产销平衡的运输问题。
Python代码及运行结果如下:
import pulp
import numpy as np
from pprint import pprint
def transportation_problem(costs, x_max, y_max):
row = len(costs)
col = len(costs[0])
prob = pulp.LpProblem('Transportation Problem', sense=pulp.LpMinimize)
var = [[pulp.LpVariable(f'x{i}{j}', lowBound=0, cat=pulp.LpInteger) for j in range(col)] for i in range(row)]
flatten = lambda x: [y for l in x for y in flatten(l)] if type(x) is list else [x]
prob += pulp.lpDot(flatten(var), costs.flatten())
for i in range(row):
prob += (pulp.lpSum(var[i]) == x_max[i])
for j in range(col):
prob += (pulp.lpSum([var[i][j] for i in range(row)]) == y_max[j])
prob.solve()
return {'objective':pulp.value(prob.objective), 'var': [[pulp.value(var[i][j]) for j in range(col)] for i in range(row)]}
if __name__ == '__main__':
costs = np.array([[4, 12, 4, 11],
[2, 10, 3, 9],
[8, 5, 11, 6]])
max_plant = [16, 10, 22]
max_cultivation = [8, 14, 12, 14]
res = transportation_problem(costs, max_plant, max_cultivation)
print(f'最小值为{res["objective"]}')
print('各变量的取值为:')
pprint(res['var'])
二、最大化运输问题
随着所给已知条件的不同,比如在运输中考虑的是单位利润,就得到最大化运输问题。这里借一个实例进行描述,一般情况可平行推广。
2.1 最大化运输问题
运输问题是一个经典的线性规划问题,涉及到如何在满足一定约束条件的情况下,最小化或最大化某种运输成本或收益。产销平衡的运输问题可以表述为:设有\(m\)个地点(称为产地或发地)\(A_1\),\(A_2\),...,\(A_m\)的某种物资调至\(n\)个地点(称为销地或收地)\(B_1\),\(B_2\),...,\(B_n\),各个产地需要调出的物资量分别为\(a_i\)单位,各个销地需要调进的物资量分别为\(b_j\) 单位,且各个发点的供应量之和等于各个收点的需求量之和。已知每个发点\(A_i\) 到每个收点\(B_j\) 调运单位物资的利润为\(r_{ij}\),见下表,现问如何安排调运,才能使总利润最大。
产地 销地 | \(B_1\) | \(B_2\) | ... | \(B_n\) | 供应量 |
---|---|---|---|---|---|
\(A_1\) | \(r_{11}\) | \(r_{12}\) | ... | \(r_{1n}\) | \(a_1\) |
\(A_2\) | \(r_{21}\) | \(r_{22}\) | ... | \(r_{2n}\) | \(a_2\) |
... | ... | ... | ... | ... | ... |
\(A_m\) | \(r_{m1}\) | \(r_{m2}\) | ... | \(r_{mn}\) | \(a_m\) |
需求量 | \(b_1\) | \(b_2\) | ... | \(b_n\) | \(\sum_{j=1}^{n}{b_j}=\sum_{i=1}^{m}{a_i}\) |
设\(x_{ij}\)表示从从第\(i\)个产地到第\(j\)个销地的货物运输量。于是得产销平衡最大化运输问题的数学模型:
\(max\) \(z\) = \(\sum_{i=1}^m\)\(\sum_{j=1}^n\)\(r_{ij}\)\(x_{ij}\)
\(\sum_{j=1}^n\)\(x_{ij}\)=\(a_i\) \(i=1,2,...,m\)
\(\sum_{i=1}^m\)\(x_{ij}\)=\(b_j\) \(j=1,2,...,n\)
\(x_{ij} \geq 0\) \(i,j=1,2,...,n\)
不平衡运输问题只要简单地调整约束的松紧关系即得。
例2: 某三个煤炭厂供应3个地区,假定等量的煤炭在这些地区使用效果相同,已知各煤炭厂年产量,各地区的需要量及从各煤炭厂到各地区的单位利润如下表所示,试决定最优的调运方案。
表1 | \(B_1\) | \(B_2\) | \(B_3\) | 产量 |
---|---|---|---|---|
\(A_1\) | 2 | 5 | 8 | 9 |
\(A_2\) | 9 | 10 | 7 | 10 |
\(A_3\) | 6 | 5 | 4 | 12 |
销量 | 8 | 14 | 9 |
若产地(煤炭厂)\(A_i(i = 1,2,3 )\) 到销地(地区)\(B_j( j = 1,2,3 )\)的运量为\(x_{ij}\),建立的数学模型如下形式:
\begin{array}{lcl} \rm maxZ = \sum_{i = 1}^{m} \sum_{j = 1}^{n} r_{ij} x_{ij} \\\\ \rm s.t\begin{cases} \rm \sum_{j = 1}^{n} x_{ij} = a_i \ \ \ \ ( \ i = 1, 2,3, \cdots , m \ ) \\\\ \rm \sum_{i = 1}^{m} x_{ij} = b_j \ \ \ \ ( \ j = 1, 2,3, \cdots , n \ ) \\\\ \rm x_{ij} \geq 0 \ \ \ \ ( \ i = 1, 2,3, \cdots , m \ \ ; \ \ j = 1, 2,3, \cdots , n \ ) \end{cases}\end{array}
该模型就是最大化运输问题的数学模型,目标函数求最大。为不重复建立理论可将最大化运输问题转化为最小化的运输问题, 给目标函数所有的数都乘以-1,得表2
表2 | \(B_1\) | \(B_2\) | \(B_3\) | 产量 |
---|---|---|---|---|
\(A_1\) | -2 | -5 | -8 | 9 |
\(A_2\) | -9 | -10 | -7 | 10 |
\(A_3\) | -6 | -5 | -4 | 12 |
销量 | 8 | 14 | 9 |
在所有值都变为负数后, 为了方便计算, 给所有的值都加上一个正数, 计算的数值虽然不同, 但是最终的运输方案相同,最后重新代入原模型计算最优值即可。
如加上 14 , 表格变为:
表3 | \(B_1\) | \(B_2\) | \(B_3\) | 产量 |
---|---|---|---|---|
\(A_1\) | 12 | 9 | 6 | 9 |
\(A_2\) | 5 | 4 | 7 | 10 |
\(A_3\) | 8 | 9 | 10 | 12 |
销量 | 8 | 14 | 9 |
求解最小化运输问题得出最优解,然后代入原目标函数即可求出最大利润。
3.2 考研试题1
某超市在外地采购 A,B,C,D四种规格的服装,数量分别为:A——1300套,B——2000套,C——3000套,D——3500套。有三个城市供应上述规格的服装且质量、运价和销量情况不同, 预计售出后的利润也不同, 详见下表。请为该公司制定一个预期总利润最大的采购方案。
城市 | 服装 A | 服装 B | 服装 C | 服装D | 产量/套 |
---|---|---|---|---|---|
I | 10 | 5 | 6 | 7 | 2500 |
II | 8 | 2 | 7 | 6 | 2500 |
III | 9 | 3 | 4 | 8 | 5000 |
采购量/套 | 1500 | 2000 | 3000 | 3500 | 10000\10000 |
该运输问题的数学模型为
\[\max z=\sum_{i=1}^m \sum_{j=1}^n r_{i j} x_{i j}\\ \begin{aligned} & \sum_{j=1}^n x_{i j}=a_i \quad(i=1,2, \cdots, m) \\ & \sum_{i=1}^m x_{i j}=b_j \quad(j=1,2, \cdots, n) \\ & x_{i j} \geqslant 0\end{aligned} \]由于是最大化运输问题,所以用一个常数(常选择单位利润中的最大数) 减去单位利润表本中的各数, 再运用表上作业法求出最优解,然后代入原目标函数就得最大值。利用上表中最大的数 10 减去表中的每个数, 得到下表:
城市 | 服装 A | 服装 B | 服装 C | 服装D | 产量/套 |
---|---|---|---|---|---|
I | 0 | 5 | 4 | 3 | 2500 |
II | 2 | 8 | 3 | 4 | 2500 |
III | 1 | 7 | 6 | 2 | 5000 |
采购量/套 | 1500 | 2000 | 3000 | 3500 | 10000\10000 |
最后可得最优解为
城市 | 服装 A | 服装 B | 服装 C | 服装D | 产量/套 |
---|---|---|---|---|---|
I | 2000 | 500 | 2500 | ||
II | 2500 | 2500 | |||
III | 1500 | 3500 | 5000 | ||
采购量/套 | 1500 | 2000 | 3000 | 3500 | 10000\10000 |
最大利润为
\[\begin{gathered} 1500 \times 9 \text { 元 }+2000 \times 5 \text { 元 }+500 \times 6 \text { 元 }+2500 \times 7 \text { 元 } \\ +3500 \times 8 \text { 元 } =72000 \text { 元 } \end{gathered} \]3.3 考研试题2
某自行车制造公司设有两个装配厂, 且在四个地区有销售公司。两个装配厂的有关数据如表I所示,四个销售公司的需求量如表II所示,从两个装配厂到四个销售公司的运价表如表所示。各家销售公司需要的自行车应由哪个厂装配,才能保证公司获得最大利润?
\[\begin{array}{c|c|c} \hline 表I\quad 装配厂 & A & B \\ \hline 产量 / 辆 & 1100 & 1000 \\ \hline 装配费用 / (元 /辆 ) & 45 & 55 \\ \hline \end{array} \]\[\begin{array}{c|c|c|c|c} \hline 表II \quad 销售公司 & 1 & 2 & 3 & 4 \\ \hline 需求量 / 辆 & 500 & 300 & 550 & 650 \\ \hline \end{array} \]\[\begin{array}{c|c|c|c|c} \hline 表III \quad 装配厂 \quad 销售公司 & 1 & 2 & 3 & 4 \\ \hline 装配厂A & 9 & 4 & 7 & 18 \\ \hline 装配厂B & 2 & 17 & 15 & 8 \\ \hline \end{array} \]解 本题是求公司的最大利润, 但题目没有告诉每辆自行车的售价, 可以把价格看作是确定的 (因为生产量是确定的),求利润最大,其实就是求成本最小。此题有装配费用,但由于生产量是确定的,所以装配费用也是确定的。
本题两个装配广生产量为 2100 辆, 而四个销售公司的需求量为 2000 辆。为了达到产销平衡,虚拟一个销售公司 5,它的销售量为 100 辆。
装配厂到虚拟销售公司的运价为 0。产销平衡的单位运价表如下所示。
装配厂 | 销售公司1 | 销售公司2 | 销售公司3 | 销售公司4 | 销售公司5 | 生产量 / 辆 |
---|---|---|---|---|---|---|
装配厂 A | 9 | 4 | 7 | 18 | 0 | 1100 |
装配厂 B | 2 | 17 | 15 | 8 | 0 | 1000 |
销售量 / 辆 | 500 | 300 | 550 | 650 | 100 | 2100 \2100 |
应用表上作业法求出最优解,见下表所示。
\[\begin{array}{c|c|c|c|c|c|c} \hline 装配厂\quad 销售公司 & 1 & 2 & 3 & 4 &5 & 生产量/辆 \\ \hline 装配厂 A & 150 & 300 & 550 & & 100 & 1100 \\ \hline 装配厂 B & 350 & & & 650 & & 1000\\ \hline 销售量 / 辆 & 500 & 300 & 550 & 650 & 100 & \\ \hline \end{array} \]注 本题也可以把装配费用加到运价表中,所得的最优解是相同的。这是因为在运输问题的单位运价表的某一行加上一个常数,最优解不变。
三、案例练习
3.1 练习1
某化学公司有甲、乙、丙、丁四个化工厂生产某种产品,产量分别为 \(200 、 300、400、100(\mathrm{t})\),供应I、II、III、IV、V、VI六个地区的需要, 需要量分别为 \(200、150、400、100、150、150(t)\)。由于工艺、技术等条件差别,各厂每 \(\mathrm{kg}\) 产品成本分别为1.2、1.4、1.1、1.5(元),又由于行情不同,各地区销售价分别为 \(2.0、2.4、1.8、2.2、1.6、2.0(\) 元 \(/ \mathrm{kg})\) 。已知从各厂运往各销售地区每 \(\mathrm{kg}\) 产品运价如下表所示。如第III个地区至少供应100t,第IV个地区的需要必须全部满足,试确定使该公司获利最大的产品调运方案。
\[\begin{array}{c|c|c|c|c|c|c} \hline 工厂\quad 地区 & I & II & III & IV & V & VI \\ \hline 甲 & 0.5 & 0.4 & 0.3 & 0.4 & 0.3 & 0.1 \\ 乙 & 0.3 & 0.8 & 0.9 & 0.5 & 0.6 & 0.2 \\ 丙 & 0.7 & 0.7 & 0.3 & 0.7 & 0.4 & 0.4 \\ 丁 & 0.6 & 0.4 & 0.2 & 0.6 & 0.5 & 0.8 \\ \hline \end{array} \]假设:\(x_{ij}\)为从工厂\(i\)运往地区\(j\) 的产品量(以千克为单位),\(c_{ij}\)为从工厂\(i\)运往地区\(j\) 每千克产品的运价,\(s_i\)为工厂\(i\) 生产的产品总量(以千克为单位),\(d_j\) 为地区\(j\)的需求量(以千克为单位),\(p_i\)为工厂\(i\) 生产的每千克产品的成本,\(r_j\)为地区\(j\)销售的每千克产品的价格。数学模型如下:
\[max\sum_{i=1}^4\sum_{j=1}^6(r_j−p_i−c_{ij})x_{ij}\]约束条件:
每个工厂的产品供应不能超过其产量:\(\sum_{j=1}^{6} x_{ij} \leq s_i\),其中 \(i=1,2,3,4\);
每个地区的需求必须得到满足:\(\sum_{i=1}^{4} x_{ij} \geq d_j\),其中 \(j=1,2,3,4,5,6\);
第III个地区至少供应100t:\(x_{i3}\geq 100\),其中 \(i=1,2,3,4\);
第IV个地区的需求必须全部满足:\(\sum_{i=1}^{4} x_{i4} = d_4\)。
这样建立的数学模型可以通过线性规划方法求解,得到使公司获利最大的产品调运方案。
3.2 练习2
3.3 练习3
四、最小配置问题
某航运公司承担六个港口城市 \(A、B、C、D、E、F\) 的四条固定航线的物质运输任务。已知各条航线的起点、终点城市及每天航班数见表1。
\[\begin{array}{|c|c|c|c|} \hline 表1 \quad 航线 & 起点城市 & 终点城市 & 每天航班数 \\ \hline 1 & E & D & 3 \\ 2 & B & C & 2 \\ 3 & A & F & 1 \\ 4 & D & B & 1 \\ \hline \end{array} \]假定各条航线使用相同型号的船只,又各城市间的航程天数见表2。
\[\begin{array}{|l|l|l|l|l|l|c|} \hline 从 到 & A & B & C & D & E & F \\ \hline A & 0 & 1 & 2 & 14 & 7 & 7 \\ B & 1 & 0 & 3 & 13 & 8 & 8 \\ C & 2 & 3 & 0 & 15 & 5 & 5 \\ D & 14 & 13 & 15 & 0 & 17 & 20 \\ E & 7 & 8 & 5 & 17 & 0 & 3 \\ F & 7 & 8 & 5 & 20 & 3 & 0 \\ \hline \end{array} \]又知每条船只每次装卸货的时间各需1天,则该航运公司至少应配备多少条船, 才能满足所有航线的运货需求?
解 该公司所需配备船只分两部分。(1) 载货航程需要的周转船只数。例如航线1,在港口E装货 1 天, \(\mathrm{E} \rightarrow \mathrm{D}\) 航程17天,在D卸货1天,总计19天。每天3航班,故该航线周转船只需57条。各条航线周转所需船只数见表2。
\[\begin{array}{|c|c|c|c|c|c|c|} \hline 表2 \quad 航线 & 装货天数 & 航程天数 & 卸货天数 & 小计 & 航班数 & 需周转船只数 \\ \hline 1 & 1 & 17 & 1 & 19 & 3 & 57 \\ \hline 2 & 1 & 3 & 1 & 5 & 2 & 10 \\ \hline 3 & 1 & 7 & 1 & 9 & 1 & 9 \\ \hline 4 & 1 & 13 & 1 & 15 & 1 & 15 \\ \hline \end{array} \](2)各港口间调度所需船只数。有些港口每天到达船只数多于需要船数,例如港口D,每天到达3条,需求1条; 而有港口到达数少于需求数, 例如港口B。各港口每天余缺船只数的计算见表3。
\[\begin{array}{|c|c|c|c|} \hline 表4 \quad 港口城市 & 每天到达 & 每天需求 & 余缺数 \\ \hline A & 0 & 1 & -1 \\ B & 1 & 2 & -1 \\ C & 2 & 0 & 2 \\ D & 3 & 1 & 2 \\ E & 0 & 3 & -3 \\ F & 1 & 0 & 1 \\ \hline \end{array} \]为使配备船只数最少, 应做到周转的空船数为最少。因此建立以下运输问题, 其产销平衡表见表4。
\[\begin{array}{|c|c|c|c|c|} \hline 港 口 & A & B & E & 每天多余船只 \\ \hline C & & & & 2 \\ D & & & & 2 \\ F & & & & 1 \\ \hline 每天缺少船只 & 1 & 1 & 3 & \\ \hline \end{array} \]单位运价表应为相应各港口之间的船只航程天数,见表5。
\[\begin{array}{|c|c|c|c|} \hline 港口 & A & B & E \\ \hline C & 2 & 3 & 5 \\ D & 14 & 13 & 17 \\ F & 7 & 8 & 3 \\ \hline \end{array} \]用表上作业法求出空船的最优调度方案见表6。
\[\begin{array}{|c|c|c|c|c|} \hline 港 口 & A & B & E & 每天多余船只 \\ \hline C & 1 & & 1 & 2 \\ D & & 1 & 1 & 2 \\ F & & & 1 & 1 \\ \hline 每天缺少船只 & 1 & 1 & 3 & 5 \\ \hline \end{array} \]由表6知最少需周转的空船数为
\[2 \times 1+13 \times 1+5 \times 1+17 \times 1+3 \times 1=40 \text { 条。 } \]这样在不考虑维修、储备等情况下, 该公司至少应配备 \(40+91=131\) 条船。
四、总结
最小化运输问题还可以在物流管理、城市规划、资源优化等方面找到广泛的应用。通过有效地解决这一问题,组织和企业可以实现运营成本的降低、资源利用的最大化,从而提高竞争力和效率。
\[\begin{array}{|c|c|c|c|c|c|} \hline 表II\quad 产地 & \mathrm{B}_1 & \mathrm{~B}_2 & \mathrm{~B}_3 & \mathrm{~B}_4 & \text { 产量 } \\ \hline \mathrm{A}_1 & 5 & 3 & 10 & 4 & 90 \\ \hline \mathrm{A}_2 & 2 & 6 & 9 & 6 & 40 \\ \hline \mathrm{A}_3 & 14 & 10 & 5 & 7 & 70 \\ \hline \text { 销量 } & 30 & 50 & 100 & 40 & \\ \hline \end{array} \]参考文献
1. 运输规划求最大值问题示例
2.运输问题之最小配置问题
3.Python数学建模PuLP库线性规划入门示例详解