案例六设施选址案例4.ppt

选址问题，是现代地理学研究的主要问题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。 选址问题的数学模型取决于两个方面的条件 ：可供选址的范围、条件；怎样判定选址的质量。 本节的讨论仅限于选址的范围是一个地理网络，而且选址位置位于网络图的某一个或几个顶点上。 对这样的选址问题，根据其选址的质量判据，可以将其归纳为求网络图的中心点与中位点两类问题。 四、中心点选址问题 五、中位点选址问题 中位点选址问题的质量判据 使最佳选址位置所在的顶点到网络图中其他各个顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小。 中位点选址问题的数学描述  设G＝（V，E）是一个简单连通赋权无向图，连接两个顶点的边的权值为该两顶点之间的距离；对于每一个顶点vi（i＝1，2，…，n），有一个正的负荷a(vi)，而且它与其他各顶点之间的最短路径长度为di1，di2，…，din。那么，中位点选址问题，就是求图G的中位点 ，使得 六、动态仓库选址 需求和成本模式会随时间变化，今天最优的方案明天可能不是最优的。 通常有几种方法： 使用现期条件和未来几年的预期情况找出仓库的最佳位置； 按照当前的最优情况进行网络布局。在新的一年到来时，根据实际情况找出新的布局，如果效益的增加大于搬迁成本，则考虑搬迁； 根据将来的效益及搬迁成本情况，找出最优的布局路径。 动态规划介绍 一个小游戏 桌上有30根火柴，两个人依次从中拿取，每次拿取的数目必须是1、2或3。 谁拿了最后一根，就算输了。 问：如果你先拿，如何保证你赢？ 最短路的另一种解法 关键思想 从A到B的最优路径满足以下条件： 路径上任意一点到B的子路径是该点到B的最优路径。 SA=min[1+SC, 2+SD] SC=min[5+SE, 2+SF]; SD=min[6+SF, 3+SG]; SE, SF 和 SG未知 ，但是可以根据SH, SI , SJ 和SK 算出； SH, SI , SJ 和SK未知 ，但是可以根据SL, SM和 SN 算出； SL, SM and SN未知 ，但是可以根据SO, SP算出； SO 和 SP 是已知的。 例，根据未来五年的需求预测，利用重心法得到仓库最优选址点分别为A、B、C、D和E点，每年的利润折现值（第n年的利润/(1+r)n）(千美圆)如下表所示： 假设从一个地址搬到另一地址均需耗费100千美圆。资金成本为每年20% 我们从第五年年初开始计算， 假设年初选在A点，则不同的方案可以得到不同的利润： AA：1336 AB：1398.2-100/(1.2)4=1350.2 AC：1457.6-100/(1.2)4=1409.2 AD：1486.6-100/(1.2)4=1438.2 AE：1526-100/(1.2)4=1477.8 这样，我们算得最佳方案为AE，同理算得BE，CE，DD，EE 再考虑第四年年初，如果仓库在A点，则可以算出各种方案的累计利润： AA-AE：671.1+1477.8=2148.9 AB-BE：750-100/(1.2)3+1477.8=2127.8 AC-CE：862.2-100/(1.2)3+1477.8=2240 AD-DD：973.3-100/(1.2)3+1486.6=2402 AE-EE：892.8-100/(1.2)3+1526=2360.9 这样，我们算得最佳方案为AD-DD，同理算得BD-DD，CD-DD，DD-DD，EE-EE 再考虑第三年年初，如果仓库在C点，则可以算出各种方案的累计利润： CA-AD-DD：623.2-100/(1.2)2+2402=2955.8 CB-BD-DD：743.4-100/(1.2)2+2402=3076 CC-CD-DD：836.4+2402=3238.4 CD-DD-DD：756.1-100/(1.2)2+2459.9=3146.6 CE-EE-EE：715.5-100/(1.2)2+1418.8=2064.9 这样，我们算得最佳方案为CC-CD-DD，同理算得AC-CD-DD，BC-CD-DD，DD-DD-DD，EC-CD-DD …最后我们可以算得最优方案是：前三年在C，第四年年初搬往D，第四、五年留在D。 七、启发式方法（Ardalan Heuristic Method） 　　计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部目标。 例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。 有时候人们