Python 使用线性规划求解旅行商问题 (TSP) 示例

import numpy as np\nfrom scipy.optimize import linprog\n\n# 城市数量\nn = 34\n\n# 城市之间的直线距离（代价矩阵）\ndistances = np.array([[0, 1230, 0, ..., 0],# 第1个城市到其他城市的距离\n[1230, 0, 0, ..., 0],# 第2个城市到其他城市的距离\n...\n[0, 0, 0, ..., 0]# 第34个城市到其他城市的距离])\n\n# TSP问题的线性规划模型\nc = distances.flatten()# 目标函数系数\nA_eq = np.zeros((n, n2))# 等式约束矩阵\nb_eq = np.ones(n)# 等式约束右侧向量\nA_eq[:, ::n] = np.eye(n)# 每个城市只能被访问一次的约束\nA_eq = A_eq[:, :-n]# 去除最后一个城市的约束\nbounds = [(0, 1)] * (n2)# 变量的取值范围\n\n# 使用线性规划求解TSP问题\nresult = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')\n\n# 解码最优路径\ntour = np.argmax(result.x.reshape((n, n)), axis=1) + 1\n\n# 输出最优路径\nprint("最优旅行路径：")\nfor i, city in enumerate(tour):\nprint(f"第{i+1}天：城市{city}")