| 楼主 lrlxxqxa |
Q：如何利用excel的规划求解解决货郎担问题？ A：回答这个分三步走： 1、什么是货郎担问题？ 2、什么是规划求解？ 3、如何解决？ 1、什么是货郎担问题？ 货郎担问题是运筹学中一个古老而著名的问题，有重要的研究和使用价值，货郎担问题是指货郎从一个城市出发，经过其他所有城市，并且一个城市只能经过一次，最后回到出发点，求解货郎在城市间销售的最短回路问题。 货郎担问题又称为旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。找出货郎问题最优解的算法可以通过完全枚举，即通过完全枚举城市集合的全排列，计算出每种排列相应销售回路的长度，从中找出最短的回路，这种完全枚举算法的时间复杂性函数是城市N的指数形式。还有贪心算法、动态规划、回溯法、分支定界法等，条条大路通罗马。 下文要阐述的是利用excel的规划求解功能如何解决此问题。 2、什么是规划求解？ 规划求解是在一定的限制条件下，利用科学方法进行运算，使对前景的规划达到最优的方法，他是现代管理科学的一种重要手段，是运筹学的一个分支。利用规划求解，可以解决产品组合问题、配料问题、下料问题、物资调运问题、任务分配问题、投资效益问题、合理布局问题等。 线性规划模型由3个基本部分组成： 单纯的概念太抽象，下面我结合一个实例来说明 3、货郎担问题如何利用规划求解？ （实例）某货郎要从A城市分别去B、C、D、E城市卖货，最后再回到A城市，路线要形成一个封闭回路，如何才能使路线最短？ 步骤1：设计电子表格 表格中的999代表无限远（即某城市作为出发地就不能作为到达地）  使用Excel求解线性规划问题时，电子表格是输入和输出的载体，因此设计良好的布局，更加易于阅读。本例的电子表格设计布局及公式如下图所示： C12：G16区域的每个单元格代表每两个城市之间的路程长度，用二进制的1表示最短路程； 某个出发地只对应一个到达地,所以C17:G17区域的每个单元格最大为1； 某个到达地只对应一个出发地，所以H12：H16区域的每个单元格最大为1；   步骤2：加载宏安装规划求解； 单击左上角Office按钮--》excel选项--》加载项--》规划求解加载项--》转到--》勾选“规划求解加载项”--》确定。 然后在菜单的数据--》分析--》规划求解  步骤3：将设计表格的各个单元格与规划求解的三个组成部分对号入座； 步骤4：应用规划求解； 单击工具--规划求解--设计相应的参数：  选项可以根据具体需求来设置。这里我勾选“采用线性模型”和“假定非负”，其余保持默认； 步骤5：求解； 设置好参数后，单击“规划求解参数”对话框中的“求解”按钮；单击“确定”可以保存解决方案。 如果问题没有可行解，规划求解将会显示明确的信息“规划求解找不到有用的解”。如果最优目标值超出界限，规划求解将会显示不太明确的信息“设置目标单元格的值未收敛”。这些情况都表明模型构造的公式有错误。 附上操作动画及实例以帮助理解。   规划求解之货郎担讲解.rar |
| 2楼 lrlxxqxa |
Q：如何利用excel的规划求解解决货郎担问题？ A：回答这个分三步走： 1、什么是货郎担问题？ 2、什么是规划求解？ 3、如何解决？ 1、什么是货郎担问题？ 货郎担问题是运筹学中一个古老而著名的问题，有重要的研究和使用价值，货郎担问题是指货郎从一个城市出发，经过其他所有城市，并且一个城市只能经过一次，最后回到出发点，求解货郎在城市间销售的最短回路问题。 货郎担问题又称为旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。找出货郎问题最优解的算法可以通过完全枚举，即通过完全枚举城市集合的全排列，计算出每种排列相应销售回路的长度，从中找出最短的回路，这种完全枚举算法的时间复杂性函数是城市N的指数形式。还有贪心算法、动态规划、回溯法、分支定界法等，条条大路通罗马。 下文要阐述的是利用excel的规划求解功能如何解决此问题。 2、什么是规划求解？ 规划求解是在一定的限制条件下，利用科学方法进行运算，使对前景的规划达到最优的方法，他是现代管理科学的一种重要手段，是运筹学的一个分支。利用规划求解，可以解决产品组合问题、配料问题、下料问题、物资调运问题、任务分配问题、投资效益问题、合理布局问题等。 线性规划模型由3个基本部分组成： 单纯的概念太抽象，下面我结合一个实例来说明 3、货郎担问题如何利用规划求解？ （实例）某货郎要从A城市分别去B、C、D、E城市卖货，最后再回到A城市，路线要形成一个封闭回路，如何才能使路线最短？ 步骤1：设计电子表格 表格中的999代表无限远（即某城市作为出发地就不能作为到达地）  使用Excel求解线性规划问题时，电子表格是输入和输出的载体，因此设计良好的布局，更加易于阅读。本例的电子表格设计布局及公式如下图所示： C12：G16区域的每个单元格代表每两个城市之间的路程长度，用二进制的1表示最短路程； 某个出发地只对应一个到达地,所以C17:G17区域的每个单元格最大为1； 某个到达地只对应一个出发地，所以H12：H16区域的每个单元格最大为1；   步骤2：加载宏安装规划求解； 单击菜单“工具”--“加载宏”，出现“加载宏”对话框，如下图所示。选择“规划求解加载项”，单击“确定”。  步骤3：将设计表格的各个单元格与规划求解的三个组成部分对号入座； 步骤4：应用规划求解； 单击工具--规划求解--设计相应的参数：  选项可以根据具体需求来设置。这里我勾选“采用线性模型”和“假定非负”，其余保持默认； 步骤5：求解； 设置好参数后，单击“规划求解参数”对话框中的“求解”按钮；单击“确定”可以保存解决方案。 如果问题没有可行解，规划求解将会显示明确的信息“规划求解找不到有用的解”。如果最优目标值是**的，规划求解将会显示不太明确的信息“设置目标单元格的值未收敛”。这些情况都表明模型构造的公式有错误。 附上操作动画及实例以帮助理解。  salesman.rar |
| 3楼 lrlxxqxa |
对于用规划求解出来的最优方案，并不一定是唯一的，但差异仅存在于路线选择，最终的最优路线长度一定是一致的（假设最优路线长度为m，m1=m2）； 而对于excel给出的最优方案m，我们要进一步分析是不是符合实际要求，比如是不是一个封闭回路？ 如果出现分支（2各回路），一般的方法是对较短回路进行条件限制，使其并入较长的回路中。这样出现的结果（n）才是满足实际需要的最短路程，但这个值n一定是大于m的。 |
| 4楼 顺便 |
非常好的贴，呵呵呵。我正准备在工作中运用。 |
| 5楼 mjgdxx |
学习了，谢谢 |
| 6楼 sjz76meizi |
讲得够详细，精彩！ |
| 7楼 larkzh |
详细，学习了。 |
| 8楼 andrewyang |
 为什么要和'二进制" 挂钩，不懂 不懂 |
| 9楼 bensonlei |
学习了。 |