白话Excel函数公式 Office易学宝微视频教程合集(Excel+Word+PPT)
笨办法学VBA(从入门到精通) 高效办公必会的Office实战技巧
财务总监的Excel私房课 Excel数据透视表实战秘技
Excel图表神技
查看: 14456|回复: 38

[综合技巧] 如何利用excel的规划求解解决货郎担问题?

[复制链接]
发表于 2010-8-8 17:49:42 | 显示全部楼层 |阅读模式
如何利用excel的规划求解解决货郎担问题?回答这个分三步走:

    1、什么是货郎担问题?
    2、什么是规划求解?
    3、如何解决?


1、什么是货郎担问题?

    货郎担问题是运筹学中一个古老而著名的问题,有重要的研究和使用价值,货郎担问题是指货郎从一个城市出发,经过其他所有城市,并且一个城市只能经过一次,最后回到出发点,求解货郎在城市间销售的最短回路问题。

    货郎担问题又称为旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

       TSP问题是一个组合优化问题。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。找出货郎问题最优解的算法可以通过完全枚举,即通过完全枚举城市集合的全排列,计算出每种排列相应销售回路的长度,从中找出最短的回路,这种完全枚举算法的时间复杂性函数是城市N的指数形式。还有贪心算法、动态规划、回溯法、分支定界法等,条条大路通罗马。

    下文要阐述的是利用excel的规划求解功能如何解决此问题。

2、什么是规划求解?

     规划求解是在一定的限制条件下,利用科学方法进行运算,使对前景的规划达到最优的方法,他是现代管理科学的一种重要手段,是运筹学的一个分支。利用规划求解,可以解决产品组合问题、配料问题、下料问题、物资调运问题、任务分配问题、投资效益问题、合理布局问题等。


    线性规划模型由3个基本部分组成:

决策变量(variable)
目标函数(objective)
约束条件(constraint)

    单纯的概念太抽象,下面我结合一个实例来说明

3、货郎担问题如何利用规划求解?

(实例)某货郎要从A城市分别去B、C、D、E城市卖货,最后再回到A城市,路线要形成一个封闭回路,如何才能使路线最短?

步骤1:设计电子表格

表格中的999代表无限远(即某城市作为出发地就不能作为到达地)

问题设计表.jpg

使用Excel求解线性规划问题时,电子表格是输入和输出的载体,因此设计良好的布局,更加易于阅读。本例的电子表格设计布局及公式如下图所示:

C12:G16区域的每个单元格代表每两个城市之间的路程长度,用二进制的1表示最短路程;
某个出发地只对应一个到达地,所以C17:G17区域的每个单元格最大为1;
某个到达地只对应一个出发地,所以H12:H16区域的每个单元格最大为1;

设计表格布局.jpg

设计公式.jpg

步骤2:加载宏安装规划求解;

2003版本:
单击菜单“工具”--“加载宏”,出现“加载宏”对话框,如下图所示。选择“规划求解加载项”,单击“确定”。

加载规划求解2003.gif

2007版本:
单击左上角Office按钮--》excel选项--》加载项--》规划求解加载项--》转到--》勾选“规划求解加载项”--》确定。

然后在菜单的数据--》分析--》规划求解

加载规划求解2007.gif

步骤3:将设计表格的各个单元格与规划求解的三个组成部分对号入座;

1:决策变量(variable)    C12:G16
2:目标函数(objective)  I17
3:约束条件(constraint)C17:G17,H12:H16

步骤4:应用规划求解;

单击工具--规划求解--设计相应的参数:

求解参数.jpg

选项可以根据具体需求来设置。这里我勾选“采用线性模型”和“假定非负”,其余保持默认;

求解选项.jpg

步骤5:求解;

     设置好参数后,单击“规划求解参数”对话框中的“求解”按钮;单击“确定”可以保存解决方案。

求解结果.jpg

     如果问题没有可行解,规划求解将会显示明确的信息“规划求解找不到有用的解”。如果最优目标值超出界限,规划求解将会显示不太明确的信息“设置目标单元格的值未收敛”。这些情况都表明模型构造的公式有错误。

附上操作动画及实例以帮助理解。

2003版本:

求解2003.gif

2007版本:

求解2007.gif

         需要说明的是,对于用规划求解出来的最优方案,并不一定是唯一的,但差异仅存在于路线选择,最终的最优路线长度一定是一致的(假设最优路线长度为m,m1=m2);

     而对于excel给出的最优方案m,我们要进一步分析是不是符合实际要求,比如是不是一个封闭回路?

     如果出现分支(2各回路),一般的方法是对较短回路进行条件限制,使其并入较长的回路中。这样出现的结果(n)才是满足实际需要的最短路程,但这个值n一定是大于m的。

规划求解.rar

20.18 KB, 下载次数: 113

评分

参与人数 1登攀 +150 红花 +1 收起 理由
beiyunli + 150 + 1 非常不错的实例加动G

查看全部评分

回复

使用道具 举报

发表于 2010-8-10 17:58:56 | 显示全部楼层
楼主在这里是怎么实现图文混排的呢?我今天是屡试屡败,:LL :LL
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-8-10 19:06:23 | 显示全部楼层
插入图片.jpg

上传附件以后,前面会有“【插入】”,光标定位在拟插入图片位置后,单击“插入”即可。
回复 支持 反对

使用道具 举报

发表于 2010-8-10 19:08:00 | 显示全部楼层
回复 支持 反对

使用道具 举报

发表于 2010-8-11 09:56:37 | 显示全部楼层
这是个不错的知识,认真学习一下。
回复 支持 反对

使用道具 举报

发表于 2010-8-11 14:13:15 | 显示全部楼层

回复 2楼 leroy 的帖子

插入图片不就好了啊
回复 支持 反对

使用道具 举报

发表于 2010-8-11 15:38:37 | 显示全部楼层
回复 支持 反对

使用道具 举报

发表于 2010-8-13 16:59:01 | 显示全部楼层
回复 支持 反对

使用道具 举报

发表于 2010-8-14 13:31:27 | 显示全部楼层
卖货郎问题,excel在变量少的情况可以,稍微计算量大点就不行了。
规划求解用过来还是lingo好。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-8-14 14:40:45 | 显示全部楼层

回复 9楼 冻豆腐 的帖子

冻大师说的没错,Lingo 是建立和求解线性、非线性和整数最佳化模型最具效率的综合工具了。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 入学

本版积分规则

快速回复 返回顶部 返回列表