分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。对于两个变量的整数规划问题，使用网格的方法有时更为简单。 [1] 通常，把全部可行解空间反复地分割为越来越小的子集，称为分支；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

matlab解决线性规划时，无法求得整数解，可通过分支定界法求解

题目描述和数据都打包了。作业题，matlab实现。 某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城 市。甲城市与乙城市之间共有 n 座城市，互相以公路连通。甲城市、乙 城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵 M1 给出。 每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩 阵M2 给出。 请给出在需付养路费总额不超过 1500 的情况下，该公司货车运送其 产品从甲城市到乙城市的最短运送路线。

运用matlab软件，使用分支定界法编程，求解整数规划问题。