运筹学经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的效率。 研究运筹学的基础知识包括实分析、矩阵论、随机过程、离散数学和算法基础等。而在应用方面，多与仓储、物流、算法等领域相关。因此运筹学与应用数学、工业工程、计算机科学、经济管理等相关专业。运筹学中转运问题就是网络图与线性规划模型问题。将所有产地、中间转运站、销地都可以看做产地,又可看做销地,把整个问题当做一个扩大的运输问题处理。
一、转运问题
处理常规的运输路线，运输是还可能包括发点到发点、收点到收点，甚至收点到发点的运输，这类运输问题考虑复杂的运输网络，称为转运问题。转运问题是指除了供给点和需求点之外运输时的中间节点，并且可以转化为一个运输问题。
供给点（supply point）是指可以发货但不能收货的点
需求点（demand point）是指可以收货但不能发货的点
转运点（transshipment point）是同时可以收货和发货的点
二、转运问题的数学模型
设有\(m\)个地点(称为产地或发地)\(A_i\)的某种物资调至\(n\)个地点(称为销地或收地)\(B_{m+j}\)，各个产地需要调出的物资量分别为\(a_i\)单位，各个销地需要调进的物资量分别为\(b_j\)单位，且$$ \sum_{i=1}^{m}a_i = \sum_{j=1}^{n}b_j=Q$$
现各个产地和销地之间可以转运，将产地和销地重新编号，就变成共有\(m+n\)个产地和\(m+n\)销地的运输问题，已知每个产地\(i\)到每个销地\(j\)的物资单位调运价格为\(c_{ij}\);各个运输节点的单位转运费\(c_i,i=1,2,...,m+n\);各个运输节点的转运量为\(t_i,i=1,2,...,m+n\)，现问如何安排调运，才能使总运费最小。
根据上面变量表，可建立有转运的运输问题的数学模型
\[\begin{aligned} & \min z=\sum_{\substack{i=1 \\ i\neq j}}^{m+n} \sum_{j=1\\ j \neq i}^{m+n} c_{i j} x_{i j}+\sum_{i=1}^{m+n} c_i t_i \\ & \left\{\begin{array}{c} \sum_{j=1,j\neq i}^{m+n}x_{ij} =a_i+t_i \quad i=1,2, \cdots, m \\ \sum_{j=1,j\neq i}^{m+n}x_{ij}=t_i \quad i=m+1, m+2, \cdots, m+n \\ \sum_{i=1,i\neq j}^{m+n}x_{ij}=t_j \quad j=1,2, \cdots, m \\ \sum_{i=1,i\neq j}^{m+n}x_{ij} =b_j+t_j \quad j=m+1, m+2, \cdots, m+n \\ x_i \geq 0,(i \neq j) Q \geq \mathrm{t}_i, \mathrm{t}_j \geq 0 \end{array}\right. \\ & \end{aligned} \]做变换，令\(x_{ii}=Q-t_i\)，\(c_{ii}=-c_i\)，代入上面模型，得
\[\begin{aligned} & \min z=\sum_{i=1}^{m+n} \sum_{j=1}^{m+n} c_{i j} x_{i j} \\ & \left\{\begin{array}{c} \sum_{j=1}^{m+n}x_{ij} =Q+a_i \quad i=1,2, \cdots, m \\ \sum_{j=1}^{m+n}x_{ij}=Q \quad i=m+1, m+2, \cdots, m+n \\ \sum_{i=1}^{m+n}x_{ij}=Q \quad j=1,2, \cdots, m \\ \sum_{i=1}^{m+n}x_{ij} =Q+b_j\quad j=m+1, m+2, \cdots, m+n \\ x_i \geq 0,(i \neq j) Q \geq \mathrm{t}_i, \mathrm{t}_j \geq 0 \end{array}\right. \\ & \end{aligned} \]
三、转运问题实例
【实例】求下列转运问题的最小费用。
3.1 建立转运矩阵
| A | B | C | D | E | 供应量 | |
|---|---|---|---|---|---|---|
| A | 0 | 3 | 12 | 10 | 4 | 47 |
| B | 3 | 0 | 6 | 10 | 5 | 34 |
| C | 12 | 6 | 0 | 2 | 3 | 27 |
| D | 10 | 10 | 2 | 0 | 6 | 27 |
| E | 4 | 5 | 2 | 6 | 0 | 27 |
| 需求量 | 27 | 27 | 36 | 36 | 36 |
3.2 Python求解
import pulp
import numpy as np
from pprint import pprint
def transport_problem(costs, x_max, y_max):
row = len(costs)
col = len(costs[0])
prob = pulp.LpProblem('Transportation Problem', sense=pulp.LpMinimize) # Changed to minimize
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()) # Objective function
for i in range(row):
prob += (pulp.lpSum(var[i])) == x_max[i] # Modified constraint: Equality instead of inequality
for j in range(col):
prob += (pulp.lpSum(var[i][j] for i in range(row))) == y_max[j] # Modified constraint: Equality instead of inequality
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([[0, 3, 12, 10, 4],
[3, 0, 6, 10, 5],
[12, 6, 0, 2, 3],
[10, 10, 2, 0, 6],
[4, 5, 2, 6, 0]])
max_plant = [47, 34, 27, 27, 27]
max_cultivation = [27, 27, 36, 36, 36]
res = transport_problem(costs, max_plant, max_cultivation)
print(f'最小值为{res["objective"]}')
print('各变量的取值为: ')
pprint(res['var'])
最小值为162.0
各变量的取值为:
[[27.0, 0.0, 0.0, 0.0, 20.0],
[0.0, 27.0, 7.0, 0.0, 0.0],
[0.0, 0.0, 18.0, 9.0, 0.0],
[0.0, 0.0, 0.0, 27.0, 0.0],
[0.0, 0.0, 11.0, 0.0, 16.0]]