整数规划——分支界定算法（旅行商问题，规约矩阵求解）-Toy模板网

这篇具有很好参考价值的文章主要介绍了整数规划——分支界定算法（旅行商问题，规约矩阵求解）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、普通优化问题分枝定界求解

题目的原问题为

lcbb规约矩阵求解tsp问题,算法,矩阵,matlab

在计算过程中，利用MATLAB中的linprog（）函数进行求解最优解，具体的计算步骤如下：

A为约束系数矩阵，B为等式右边向量，C为目标函数的系数向量。

进行第一次最优求解以A=[2 9;11 -8],B=[40;82],C=[-3,-13]利用linprog函数求解。解得x1=9.2，x2=2.4，都不是整数，选定x1进行分枝操作。以x1<=9，x1>=10为约束条件进行下一次的分枝，此时求得的最大值为-58.8。

对于x1<=9 以A=[2 9;11 -8;1 0],B=[40;82;9],C=[-3,-13]进行求解，求得的解x1=9，x2=2.444，最大值为-58.7778。x110以A=[2 9;11 -8;-1 0],B=[40;82;-10],C=[-3,-13]求解，发现无界。接下来对x2进行分枝，以x2<=2，x2>=3进行分枝操作。

对于x2<=2以A=[2 9;11 -8;1 0；0 1],B=[40;82;9;2],C=[-3,-13]进行求解，求得的解x1=8.9，x2=2.0，最大值为-52.7273。由于是在x1<=9的条件下进行分枝的，此次迭代中不能再对x1进行分枝，转而x2>=3以A=[2 9;11 -8;1 0；0 -1],B=[40;82;9;-3],C=[-3,-13]进行求解，求得的x1=6.5，x2=3，最大值为-58.5，x2为整数，所以接下来对x1继续进行分枝，以x1<=6，x1>=7进行分枝操作。

对于x1<=6以A=[2 9;11 -8;1 0；0 -1;1 0],B=[40;82;9;-3;6],C=[-3,-13]进行求解，解得x1=6，x2=3.111，求得的最大值为-58.444，因为x1为常数，则接下来对x2进行分枝操作。对于x1>=7以A=[2 9;11 -8;1 0；0 -1;-1 0],B=[40;82;9;-3;-7],C=[-3,-13]进行求解，发现无解。接下来以x2<=3，x2>=4进行分枝操作。

对于x2<=3以A=[2 9;11 -8;1 0;0 -1;1 0;0 1],B=[40;82;9;-3;6;3],C=[-3,-13]进行求解，解得x1=6，x2=3，求得的最大值为-57，求得的解和最大值都为整数。对于x2>=4，以A=[2 9;11 -8;1 0;0 -1;1 0;0 -1],B=[40;82;9;-3;6;-4],C=[-3,-13]进行求解，解得x1=2，x2=4，求得的最大解为-58，求得的解和最大值也都为整数。相较于x2<=3和x2>=4的情况x2>=4的情况时求得的最大值更大，此时解和最大值都为整数，所以不再进行分枝。最后，得到最优解为（2 ;4），最大值为58，分枝定界完毕。为了接下来更清楚的观察整个过程，将展示树图的分枝定界。

lcbb规约矩阵求解tsp问题,算法,矩阵,matlab

二、旅行商问题（规约矩阵）

旅行商问题是一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。旅行商问题可以通过好多方法来求解，这里主要应用分支界定法来进行求解。原问题如下所示，求解五个城市之间的TSP问题。 lcbb规约矩阵求解tsp问题,算法,矩阵,matlab