在旅行商问题(TSP)中为scipy.optimize.linprogPython函数定义线性规划约束

xzv2uavs 于 2023-06-04 发布在 Python

关注(0)|答案(1)|浏览(254)

我正在尝试使用Python中的scipy.optimize.linprog来解决旅行商问题（TSP）的线性规划公式。
This document清楚地定义了这个问题，尽管我理解这个想法，但我不知道如何将其转换为所需的参数。
我已经把距离矩阵变平了，所以函数应该没问题。那么约束矩阵和约束向量呢？
我试过了...

n = len(d)

TSP_c = [d[i][j] for i in range(n) for j in range(n)]

E = [(i,j) for i in range(len(d)) for j in range(len(d))]
TSP_A = [[1 if k in (i, j) else 0 for (i, j) in E] for k in range(n)]
TSP_b = [2] * n

TSP_res = linprog(TSP_c, TSP_A, TSP_b, bounds = bounds, method = 'simplex')
TSP_res

...试图复制这个example（顺便说一下，我不知道如何使用panda）。
更新：

无边界：一些变量等于2，空函数
Bounds：'bounds = [（0，1）] * n'返回ValueError：linprog的输入无效：无法解释此维度元组的边界：（10，2）。
正确界限：'bounds = [（0，1）] （nn）'，变量等于1或0但仍然为空函数+似乎只有对角线（例如，变量（i，j）=（0，0），（1，1）...）等于1

python

来源：https://stackoverflow.com/questions/76358116/defining-the-linear-programming-constraints-in-the-traveling-salesman-problem-t

1条答案

按热度按时间

41zrol4v1#

这个方法的作用是：

d = [[distance_ij(coord_rad,i,j) for j in range(len(coord_rad))] for i in range(len(coord_rad))]

n = len(d)
E = [[i, j] for i in range(n) for j in range(n)]

TSP_A_eq = []

for k in range(n) :
    TSP_A_eq.append([1 if i == k and k != j else 0 for [i, j] in E]) # somme des arêtes sortantes
    TSP_A_eq.append([1 if k == j and i != k else 0 for [i, j] in E]) # somme des arêtes rentrantes

for i in range(n) :
    TSP_A_eq.append([1 if i == j else 0 for [i, j] in E]) # pas d'arête (i, i)

TSP_c = [d[i][j] for [i, j] in E]
TSP_b_eq = [1] * (2 * n) + [0] * n
bounds = [(0, 1)] * (n * n)

TSP_res = linprog(c=TSP_c, A_eq=TSP_A_eq, b_eq=TSP_b_eq, bounds=bounds, method='simplex', integrality=1)

然后是subtour消除约束...

赞(0）回复(0）举报 2023-06-04

我来回答

在旅行商问题(TSP)中为scipy.optimize.linprogPython函数定义线性规划约束

1条答案

相关问题

热门标签

最新问答