用Excel来优化网络问题

用Excel来优化网络问题
今天的作家，迭戈奥本海默，一个项目经理对Excel的团队，深入研究了一些更先进功能的Excel解决一个富有挑战性的问题。该文件中使用这一博客帖子中可以找到的附件底部的这一职务。

在这整个未来的博客帖子我将利用一种工具，是所谓的与Excel求解。欲了解更多有关求解请访问Office Online的网站（ http://office.microsoft.com/en-us/excel/HP051983681033.aspx?pid=CH010004571033 ） 。

背景：

我目前正在规划建设度假探索华盛顿州。理想在短期内大量的时间我已经关闭我想要做的许多加息的可能。我将开始从西雅图和整理在壶东瀑布西澳。一路上我已经确定了4种可能停车的地方，我感兴趣的从停止停止我已经研究了多少息我能做的一路上每个人之间，我停止。随着一个工具像微软Live地图我可以很容易的阴谋之间距离最短西雅图和水壶瀑布，但我更感兴趣的优化我的行程，包括许多加息的可能。

为此我已决定使用简单的原则，线性规划，并建立网络模型与Excel这将最大限度地发挥我的徒步旅行时间对我即将到来的假期。这个问题，图论中的定义是最短路径的问题。最短路径算法，用于网页绘图软件，如活地图。

为了更好的图形理解我的征程我建立下面的地图：

  

没有任何“倒退”我已经改为所有可能的组合停下来停止由Seattle ， WA ，以水壶瀑布，西澳。我也有我的站从左至右，方便参照在我的工作簿。

我建立下面的表格提供快速的参考，对行车时间之间的不同的停车点。您会发现，我已提出了一些在括号（十）代表的人数加息对这一特定部分旅程：

例如：西雅图Darrington -时间： 1 .4小时， 2息，我将是很有意思的在做的事情。


西雅图
  Longmire
  Darrington
亚基马
韦纳奇
水壶瀑布
  
西雅图
  X
  4 （ 5 ）
  1.4 （ 2 ）
  2.2 （ 3 ）
  2.5 （ 5 ）
  5.5 （ 6 ）
  
Longmire
  4 （ 5 ）
  X
  4.2 （ 2 ）
  2.3 （ 2 ）
  4 （ 2 ）
  6.3 （ 4 ）
  
Darrington
  1.4 （ 2 ）
  4.2 （ 2 ）
  X
  3.4 （ 3 ）
  3.3 （ 5 ）
  7 （ 3 ）
  
亚基马
  2.2 （ 3 ）
  2.3 （ 2 ）
  3.4 （ 3 ）
  X
  2 （ 1 ）
  4.4 （ 3 ）
  
韦纳奇
  2.5 （ 5 ）
  4 （ 2 ）
  3.3 （ 5 ）
  2 （ 1 ）
  X
  4.2 （ 2 ）
  
水壶瀑布
  5.5 （ 6 ）
  6.3 （ 4 ）
  7 （ 3 ）
  4.4 （ 3 ）
  4.2 （ 2 ）
  x
  

安装：

鉴于我爱爬山我想设立这个优化，以便能够重复使用任何数量的停止我想。我只包括6日在此版本保持简单。

首先让我们创建一个表格，标签号码和我们停止，以使我们创造下列表格开始臭氧：停止
名字
  
1
西雅图
  
二
  Longmire
  
三
  Darrington
  
四
亚基马
  
五
韦纳奇
  
6日
水壶瀑布
  


大现在让我们来创造我们的可能途径就座。此表将代表路径我提请了我的地图也将载有关于估计时间（小时）和若干加息。

  

我们可以看到，现在的表所有可能的路线我可以考虑，也估计的时间之间的道路，以及一些加息的每个路径。现在，我们可以对B3的增加我们的路线选择将是一个二进制开关（ 1为真， 0为假） ，将代表的路径是否被选为与否。现在让我们初始化所有这些价值为0 。

  

求解将改变我们的布尔值的路由选择栏，使一个简单的方法找出有多少总数小时，以及有多少人总数加息我能做我最优路径我可以使用函数SUMPRODUCT 。

SUMPRODUCT将返回的总和产品的两个范围我在这种情况下（线路选择X数字的远足） 。

因此，让标签C17为“数远足” ，并插入下列公式C18分析：

= SUMPRODUCT （路由选择X数字的远足）

或在此范例

  

凡表是我们可能路由表，路由选择的范围是从B3 ： B12和数量远足是从的D4 ： D12 。

玉如此概括我们有可能的路线表和我们仍然有我们的臭氧停止号码和停止的名字。

下一步是建立约束制度，是必要的解决这一问题。在简单的英语，我们需要建立的制约，使求解只会找到解决方案，遵循这些规则：

我总是离开华盛顿州西雅图。
我总是到达水壶瀑布，西澳。
如果我到达某个节点的下一个步骤，必须离开该节点。 （除西雅图和水壶瀑布） 。
最简单的方式做到这一点是要创造再次二元选择在1表明到达的位置和-1表明留下了位置。我们新的网络图将像这样：

  

最后，我们将确定我们的流柱用SUMIFs 。 SUMIF将特定的细胞由一组给定的条件。在我们的情况下，条件是，我们的所有站“净流入”是0 ，除非我们的出发点和终结点。

= SUMIF （ ToStopRange ，停止，路线选择范围） -S UMIF（ F romStopRange，停止， R outeSelect幅度） 。

因此，在第三季度我们将开始了一系列名为“流” 。我们将确定我们的流柱用SUMIFs 。 SUMIF将特定的细胞由一组给定的条件。在我们的情况下，条件是，我们的所有站“净流入”是0 ，除非我们的出发点和终结点。

  

我们复制此公式从第三季度到六题。

由于流动范围是确定的价值路线选择，我们仍然需要给予解决的参考范围相匹配的流动我在图图。因此，毗邻流我会创造我的约束栏和手动输入的值为-1西雅图， 0我所有的中间节点和1的水壶瀑布，西澳。


建立Solver.Finally

为了使求解： http://blogs.msdn.com/excel/archive/2006/09/06/743902.aspx

我们有3个这样的任务时，设立求解：

设定的目标细胞：在这里，我们将选择权的细胞旁边的一些加息，因为我们要最大限度地发挥这个数目，我们选择“最大” 。

通过改变变量细胞：

细胞的变化是我们的路线选择范围。

制约因素：

在这里，我们将具体的限制，我们讨论过：

流动栏必须是平等的制约栏。选择流量范围=约束范围
路由选择的范围必须是“ = 0 （我们只想要正数） 。
路由选择必须包含二进制值。
  

我们正在做最后确定了我们求解。没有，我们只要按一下“解决”和工作要做。我们现在有一个优化的远足旅行计划。

如果您复制所有的号码我用你应该得到最高的14加息和您理想的旅行路径是：

西雅图Longmire
Longmire以Darrington
Darrington以韦纳奇
韦纳奇以水壶瀑布
结论：

所以，现在我们已经建立了道路优化，一个很容易被扩大（添加更多的节点）或变更围绕优化像其他变数估计的旅行时间。虽然这个例子很简单（是一个地图和一些简单的算术将提供更快的结果）的价值，这些方法发挥作用时，分析大量的节点。类似的原则，对那些在这讨论后用于优化各种制造业，交通运输和分配系统。