网站开发微信授权登录,网站制作模板免费下载,wordpress 在线演示,简单的企业网站cms问题描述
给定一系列城市和每对城市之间的距离#xff0c;求解访问每座城市一次并回到起始城市的最短回路。 数学建模
集合#xff1a; V V V#xff1a;城市集合
常量#xff1a; c i j c_{ij} cij#xff1a;城市 i i i到城市 j j j之间距离, i ≠ j i \neq j i…问题描述
给定一系列城市和每对城市之间的距离求解访问每座城市一次并回到起始城市的最短回路。 数学建模
集合 V V V城市集合
常量 c i j c_{ij} cij城市 i i i到城市 j j j之间距离, i ≠ j i \neq j ij
变量 x i j x_{ij} xij是否从城市 i i i走到城市 j j j ∑ i ∈ S ∑ j ∈ S , j ≠ i c i j x i j s . t . ∑ i ∈ S , i ≠ j x i j 1 , ∀ j ∈ S ∑ j ∈ S , j ≠ i x i j 1 , ∀ i ∈ S ∑ i , j ∈ S x i j ≤ ∣ S ∣ − 1 , 2 ≤ ∣ S ∣ ≤ n − 1 , S ∈ V \sum_{i \in S}\sum_{j \in S,j \neq i} c_{ij}x_{ij} \\ s.t. \sum_{i \in S, i \neq j} x_{ij} 1, \forall j \in S \\ \sum_{j \in S, j \neq i} x_{ij} 1, \forall i \in S \\ \sum_{i,j \in S}x_{ij} \leq \vert S\vert - 1, 2 \leq\vert S\vert\leq n-1,S\in V i∈S∑j∈S,ji∑cijxijs.t.i∈S,ij∑xij1,∀j∈Sj∈S,ji∑xij1,∀i∈Si,j∈S∑xij≤∣S∣−1,2≤∣S∣≤n−1,S∈V
目标函数表示最小化旅行距离第一个约束表示每个城市只能进入一次第二个约束表示每个城市只能出发一次第三个约束是去除子环路的约束仅允许所有点都被包含进来的子环存在。
参考资料
运筹优化常用算法、模型及案例实战PythonJava 实现. 刘兴禄熊望祺臧永森段宏达曾文佳陈伟坚.旅行推销员问题Traveling with a Quantum Salesman