手动实现运输规划问题遇OverflowError：无法转无穷大为整数

问题背景 #

我尝试不使用scipy.optimize.linprog库直接实现运输问题：

（运输问题）：需将m个产地的产品（产量分别为a₁,a₂,…,aₘ）运往n个目的地（需求量分别为b₁,b₂,…,bₙ），从产地i运往目的地j的单位运输成本为cᵢⱼ，目标是确定各产运量xᵢⱼ，满足供需要求并最小化总运输成本。
（注：我来自法语国家，英文表述欠佳）

原始实现代码（含法语注释） #

import numpy as np
import matplotlib.pyplot as plt

# Données du problème
m = 3  # Nombre d'origines
n = 4  # Nombre de destinations
a = np.array([20, 30, 25])  # Offres des origines
b = np.array([10, 15, 25, 15])  # Demandes des destinations
c = np.array([
    [5, 4, 7, 6],
    [8, 6, 9, 7],
    [6, 3, 4, 5]
])  # Coûts d'expédition

# Matrice des variables de décision (quantités à expédier)
x = np.zeros((m, n))

# Algorithme du transport initial
while np.sum(x) < np.sum(b):
    min_supply = np.min(a)
    min_demand = np.min(b)
    
    i, j = np.unravel_index(c.argmin(), c.shape)
    quantity = min(min_supply, min_demand)
    
    x[i, j] = quantity
    a[i] -= quantity
    b[j] -= quantity
    c[i,j]= np.inf

# Affichage de la solution
print("Solution optimale (quantités à expédier) :")
print(x)

# Affichage du graphique de la solution
plt.imshow(x, cmap='Blues', interpolation='nearest')
plt.colorbar()
plt.title("Quantités à expédier")
plt.xlabel("Destinations")
plt.ylabel("Origines")
plt.xticks(range(n), [f"Destination {i+1}" for i in range(n)])
plt.yticks(range(m), [f"Origine {i+1}" for i in range(m)])
plt.show()

运行错误信息 #

OverflowError                             Traceback (most recent call last)
Cell In[2], line 29
     27     a[i] -= quantity
     28     b[j] -= quantity
---> 29     c[i,j]= np.inf
     31 # Affichage de la solution
     32 print("Solution optimale (quantités à expédier) :")

OverflowError: cannot convert float infinity to integer

问题原因 #

c数组默认是整数类型（因为初始元素都是整数），而np.inf是浮点数类型，无法将浮点数无穷大赋值给整数数组的元素，因此触发类型转换溢出错误。

修复方案 #

有两种可行的修复方式：

方式1：将成本数组初始化为浮点数类型 #

在创建c数组时，显式指定dtype=np.float64，这样就可以正常赋值np.inf。

方式2：用超大整数替代无穷大 #

如果希望保持整数类型，可以用一个远大于所有成本值的整数（比如10**18）代替np.inf，确保后续不会再选中该运输路径。

修复后的完整代码（中文注释+方式1实现） #

import numpy as np
import matplotlib.pyplot as plt

# 问题数据
m = 3  # 产地数量
n = 4  # 目的地数量
a = np.array([20, 30, 25])  # 各产地供应量
b = np.array([10, 15, 25, 15])  # 各目的地需求量
# 单位运输成本矩阵，指定为浮点数类型
c = np.array([
    [5, 4, 7, 6],
    [8, 6, 9, 7],
    [6, 3, 4, 5]
], dtype=np.float64)

# 决策变量矩阵（存储各产地到目的地的运输量）
x = np.zeros((m, n))

# 初始运输规划算法
while np.sum(x) < np.sum(b):
    min_supply = np.min(a)
    min_demand = np.min(b)
    
    # 找到当前成本最低的运输路径
    i, j = np.unravel_index(c.argmin(), c.shape)
    # 确定该路径的运输量（取供应量和需求量中的较小值）
    quantity = min(min_supply, min_demand)
    
    x[i, j] = quantity
    a[i] -= quantity
    b[j] -= quantity
    # 将该路径的成本设为无穷大，避免重复选择
    c[i,j] = np.inf

# 输出最优运输量矩阵
print("最优运输量矩阵：")
print(x)

# 可视化运输量分布
plt.imshow(x, cmap='Blues', interpolation='nearest')
plt.colorbar()
plt.title("运输量分布")
plt.xlabel("目的地")
plt.ylabel("产地")
plt.xticks(range(n), [f"目的地 {i+1}" for i in range(n)])
plt.yticks(range(m), [f"产地 {i+1}" for i in range(m)])
plt.show()

运行效果 #

修复后代码可正常执行，输出各产地到目的地的最优运输量矩阵，并弹出热力图直观展示运输量分布。

内容的提问来源于stack exchange，提问作者Andy MWEPU