显然,当城市个数较大(大于30)时,该混合整数线性规划问题的 规模会很大,从而给求解带来很大问题。TSP已被证明是N难问题, 目前还没有发现多项式时间的算法。对小规模问题,求解这个混合 整数线性规划问题的方式还是有效的。 TSP是一个重要的组合优化问题,除了有直观的应用外,许多其它 看似无联系的优化问题也可转化为TSP。例如: 问题1现需在一台机器上加工n个零件(如烧瓷器),这些零件可 按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时 间尽可能少。由于加工工艺的要求,加工零件j时机器必须处于相 应状态S;(如炉温)。设起始未加工任何零件时机器处于状态S, ,且当所有零件加工完成后需恢复到S状态。已知从状态S;调整到 状态S1(i≠j需要时间C。零件j本身加工时间为D。为方便起见 引入一个虚零件0,其加工时间为0,要求状态为S0,,则{0,1 ,2,…,n}的一个圈置换π就表示对所有零件的一个加工顺序, 在此置换下,完成所有加工所需要的总时间为 ∑(c4+p)=∑c+2 =0 ∑ P,是一个常数,故该零件的加工顺序问题变成TSP显然，当城市个数较大（大于30）时，该混合整数线性规划问题的 规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题， 目前还没有发现多项式时间的算法。对小规模问题，求解这个混合 整数线性规划问题的方式还是有效的。 TSP是一个重要的组合优化问题，除了有直观的应用外，许多其它 看似无联系的优化问题也可转化为TSP。例如： 问题1 现需在一台机器上加工n个零件（如烧瓷器），这些零件可 按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时 间尽可能少。由于加工工艺的要求，加工零件j时机器必须处于相 应状态Sj（如炉温）。设起始未加工任何零件时机器处于状态S0， ，且当所有零件加工完成后需恢复到S0状态。已知从状态Si调整到 状态Sj(i≠j)需要时间Cij 。零件j本身加工时间为pj。为方便起见 ，引入一个虚零件0，其加工时间为0，要求状态为S0， ，则{0，1 ，2，…，n}的一个圈置换π就表示对所有零件的一个加工顺序， 在此置换下，完成所有加工所需要的总时间为 由于 是一个常数，故该零件的加工顺序问题变成TSP。 ( ( ) ( ) ) ( ) 0 0 0    = = =    + = + n n n i i i i i j i i j C p C p =0  n j j p