400-893-5552

以 TSP 问题为例,了解运筹学的决策方式

 
2017-04-28 17:59:44所属分类:行业动态

在 Wikipedia 中,对运筹学的解释是「一门应用数学学科,利用统计学和数学模型等方法,寻找复杂问题中的最佳或近似最佳的解答」。具体来说,运筹学是一门研究怎样处理事情更有效的学科(因此达成「优化」或「最优化」常常是运筹学的目标),关注的往往是当今社会经济发展的热点,如航空公司的定价、超售问题,物流中的调度问题,共享经济中的资源调配问题等等。

但凡涉及「决策」,就会有运筹学的用武之处。起源于第二次世界大战的运筹学,是因英美两国为有效配置资源,召集科学家研究军事作业规划而诞生。团队的研究成果帮助盟军打赢「不列颠空战」、「北大西洋战争」、「太平洋岛屿战争」,战后研究成果转移为和平用途。如今,从管理、金融、计算机、军事到日常生活的具体问题,运筹学都能给出可实施的解决方案。

想要更形象的理解运筹学,旅行推销员问题(Travelling salesman problem, TSP)是个不错的例子。作为运筹学经典模型之一,它描述的是「给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路」。

 

\

 

1930 年,TSP 问题被首次形式化,成为最优化中研究最深入的问题,许多优化方法都以此为基准

运筹学的解决方法,是先将 TSP 问题用数学形式写出,即构建模型;第二步则是通过模型算出哪个线路可以达成预定目标,如优化时间、遍历所有城市等等,即算法。在现实生活中,TSP 问题往往有很多附加条件,比如必须在某时间窗口前往某城市,或者必须先前往 A 城市才能去 B 城市等等,这些约束条件同样需要反应在构建的模型中。

「对于现实中的项目,需要根据实际业务场景需求提出的合适模型,这些模型往往是在经典模型上作修改。怎么修改模型会最有效、能求解,正是决策学背景的用武之处。」

Copyright © 2013-2018 合肥彼岸互联信息技术有限公司 All Rights Reserved地址:合肥市高新区亚夏汽车大厦17楼
工信部备案号: 皖B2-20150071-4    增值电信业务经营许可证:皖B2-20150071-4 安全联盟认证 安全联盟认证 安全联盟实名认证

copyright@2015 合肥彼岸互联信息技术有限公司

电话:400-893-5552 0551-65371998 QQ:800022936

地址:合肥市高新区亚夏汽车大厦17楼