A-A+
证明：旅行推销员问题的数学模型(混合整数线性规划问题)中的第三组约束能够防止多于一个的互不连
问题详情
证明：旅行推销员问题的数学模型(混合整数线性规划问题)中的第三组约束能够防止多于一个的互不连通的回路出现，同时又不会排除任何符合问题要求的回路．
参考答案
假如出现多于一个的互不连通的回路，则必有一回路不通过v0，设它通过的城市序列为vi1，vi2，…，vik，vik．这时按第三组约束，应有下列各式成立：
ui1-ui2+n≤n-1，ui2-ui3+n≤n-1，…，uik-uil+n≤n-1．将以上各式相加，即可得出n≤n-1的矛盾．
另一方面，对于符合问题要求的任一回路都存在ui(i=1，2，…，n)的值满足第三组约束．如对于合理回路v0，vi1，vi2，…，vin，v0，令uik=k(k=1，2，…，n)，则可验证此组ui值满足第三组约束．
