Can you summarize the following document?
        
  

  可以用无向加权图来对TSP建模,则城市是图的顶点,道路是图的边,道路的距离就是该边的长度。它是起点和终点都在一个特定顶点,访问每个顶点恰好一次的最小化问题。通常,该模型是一个完全图(即每对顶点由一条边连接)。如果两个城市之间不存在路径,则增加一条非常长的边就可以完成图,而不影响计算最优回路。

  在"对称TSP问题"中,两座城市之间来回的距离是相等的,形成一个无向图。这种对称性将解的数量减少了一半。在"非对称TSP问题"中,可能不是双向的路径都存在,或是来回的距离不同,形成了有向图。交通事故、单行道和出发与到达某些城市机票价格不同等都是打破这种对称性的例子。

  单钻头的运动可以看成是典型的TSP问题。TSP可以用整数线性规划来形式化。 用数字 0,..., "n" 标记这些城市(打孔位置),并定义:  对于 "i" = 0,..., "n",令 formula_2 为一人工变量,最后把 formula_3 作为从城市 "i" 到 "j" 的距离。那么TSP可以写成下面的整数线性规划问题:  第一组等式要求每个城市都能另一个城市前来,而第二组等式要求每个城市都能出发。最后的约束迫使覆盖所有城市的路径只有一条,而不是两条或者多条分散的路径在一起覆盖的。要证明这一点,下面会去证 (1)每个可行解包含只有一条封闭城市序列,以及(2)对于每条覆盖所有城市的单独路径,虚拟变量 formula_2 有值可以满足约束。  证明可行解中的每个子回路经过0号城市(注意到等式保证了只有一条这样的路径),就能证明所有可行解只包含一个封闭城市序列。对于若我们对所有 formula_6 对应的不等式求和的话,对 "k" 步不经过0号城市的任何子回路,我们得到:  这构成矛盾。  必须证明对每个覆盖所有城市的单独回路,虚拟变量 formula_2 有值可以满足约束。  为了不失一般性,定义起始点为0号城市。如果在第 "t" 步访问城市 "i" 后 ("i", "t" = 1, 2,..., n) 选取 formula_9。则  由于 formula_2 不大于 "n" 而 formula_12 不小于1;因此,每当 formula_13 时满足约束。对于 formula_6,我们有:  满足约束。
行商问题(最短路径问题)(英语:travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。 TSP是旅行购买者问题与车辆路径问题的一种特殊情况。