用单纯形法求解线性规划(linear programming)问题，速度到底有多快呢？

我们最早接触到的与运筹学相关的知识可能就是线性规划问题了。求解线性规划问题的基本方法是单纯形法(Simplex algorithm)，与单纯形法相关的方法我们已经有许多推文介绍啦感兴趣的小伙伴可以去看一看。在学习过程中，老师可能会告诉大家这是求解速度比较快的一类问题。但是说归说，有的同学可能对此会有些不解。用单纯形法求解线性规划问题到底有多快呢？随着问题规模的变化，求解所耗的时间是怎么变化的呢？

那今天呢我们来解个线性规划问题让大家直观地感受一下线性规划问题的求解速度。开始之前按惯例先给大家看一下线性规划的定义。

接下来我们就要抓个问题来解一解，就决定是你了--------

带时间窗约束的车辆路径规划问题

为什么要选择这个问题呢，因为它名字很长而且有现成代码足够复杂。要是太简单了一两秒不到跑完了那大家不会有什么感觉，太复杂了求解时间长了也没必要。关于这个问题我们之前专门做了一篇推文来介绍以及求解的，详情可见

“干货|十分钟快速掌握CPLEX求解VRPTW数学模型（附Java代码及CPLEX安装流程）”

解问题之前来先看看这是个什么问题。

“

车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

时间窗就是一种约束，车辆除了要满足VRP问题的限制之外，还必须满足需求点的时间窗约束（例如服务只能在早上八点到十点之间开始），而需求点的时间窗限制可以分为两种，一种是硬时间窗（Hard Time Window ），硬时间窗要求车辆必须要在时间窗内开始服务客户，早到必须等待，而迟到则拒收；另一种是软时间窗（Soft Time Window ），不一定要在时间窗内开始服务，但是在时间窗之外开始服务的话会受到处罚，以处罚替代等待与拒收是软时间窗与硬时间窗最大的不同。

”

问题模型如下：

上述模型的决策变量带整数约束，本次求解其线性松弛解。求解线性松弛解可以调用CPLEX这一求解器中的单纯形法进行求解。小编是在Eclipse上用Java语言调用的。

算例使用的是solomon的扩展算例（RC122），该算例共有200个点。分别取前25、50、75、100、125、150、175、200个顾客节点进入模型求解，并且在每次求解完成后释放缓存以避免已有信息的干扰。在得到线性最优解的情况下，记录求解时间和迭代次数。

求解结果

不同顾客节点数量对应的决策变量数量如下：

不同顾客节点数量对应的模型约束数量如下：

不同顾客节点数量求解所花费的求解时间以及迭代次数如下：

相信通过这些对比，大家心里应该能够有个印象了。需要注意的是求解的时间与机器的性能有关系，小编所使用的电脑运行内存为4G，部分硬件参数如下：

关于内存与CPLEX求解速度的关系小编在网上看到有一种说法指出当CPLEX发现仅剩有限的内存可供使用时将会自动运行算法进行调整补偿，这些调整几乎都会降低速度。小编在跑代码的过程中也发现虚拟内存文件的大小有比较大的扩充，这会损失相当可观的性能。所以如果你的电脑性能好，就能得到更快的求解速度。

---The End---