首页 文章

代表旅行推销员作为线性表达

提问于
浏览
6

我在网上看到,人们可以将旅行商问题写成线性表达式,并使用CPLEX for java等软件进行计算 .

我有1000个城镇,需要找一小段距离 . 我计划将这1000个城镇划分为约100个城镇的集群,并在这些单独的集群上执行一些线性规划算法 .

我的问题是,我究竟如何将其表示为线性表达式 .

所以我有100个城镇,我相信每个人都知道TSP是如何工作的 .

我完全不知道如何编写满足TSP的线性约束,目标和变量 .

有人可以向我解释这是如何完成的,或者给我一个清楚解释它的链接,因为我一直在研究很多,似乎找不到任何东西 .

编辑:

我找到了一些额外的信息:

我们用数字0到n标记城市并定义矩阵:

enter image description here

这会为5个城镇产生以下矩阵吗?

enter image description here

限制是:

i)每个城市都来自其他城市

ii)从每个城市出发前往另一个城市

iii)该路线不会分成不同的岛屿 .

同样,这对我来说是完全合理的,但我仍然无法将这些约束写为线性表达式 . 显然它是一个简单的矩阵 .

谢谢你的帮助 !

2 回答

  • 2

    根据这个Wikipedia article,旅行商问题可以建模为整数线性程序,我认为这是问题的关键问题 . 我们的想法是在 {0,1} 中设置允许值的决策变量,该变量对图中的选定边进行建模 . 合适的约束必须确保所选边缘覆盖每个节点,所选边缘形成一组循环,并且只有一个连接组件(总的来说,这意味着只有一个循环包含每个节点) . 请注意,该文章还给出了明确的表述,并解释了约束的解释 .

    由于旅行商问题是 NP -hard,除非 P=NP ,否则无法通过(非整数)线性编程解决 .

  • 1

    由于其组合性质,TSP问题是一个相当复杂的整数规划问题 . 有几种(精确的和近似的)技术可以解决它 . Wikipedia中的模型只是其中之一:它具有约束以确保每个节点中只有一个传入和传出弧,而具有u变量的约束用于防止解决方案中的子循环 . 还有几种方法可以编写这个子循环来防止约束,其中一些可以在article的第4.1节中找到 . 本节介绍了TSP问题的一些模型(所有这些模型都可以使用CPLEX,Gurobi,MATLAB或其他整数/线性编程软件来解决 .

    希望我可以提供任何帮助 . (=

相关问题