数学建模之运筹学问题

深藏阁楼爱情的钟 2022-11-01 04:25 195阅读 0赞

**目录**

1、引言

2、常见模型与算法

3、问题描述

4、遗传算法

5、仿真结果

--------------------

# 1、引言 #

> 运筹学问题，包括任务规划、分配、决策，是数学建模比赛中常见的问题（参见2018年“高教杯”数学建模B题、2019年美赛MCM B题）。今天小编就和大家分享一下数学建模中运筹学问题的常见解决方法与技巧。本文相对适用于刚刚入门的小白同学以及对于数学建模有些接触的同学，当然也欢迎大神们交流讨论。
> 
> 本文主要概述一下比赛中可能出现的问题，同时分享了遗传算法在运筹学问题中的应用。
> 
> 另外小编也整理了一些参考文献，也是数学建模比赛时非常有用的参考，论文里面加上一定能让你脱颖而出的哦，想要的话请留言哦。

# 2、常见模型与算法 #

> 首先是运筹学中一些常见的模型与算法。大家如果不感兴趣可以直接跳到第二部分哈。常见的运筹学模型包括**车辆路由问题**（Vehicle Routing Problem，VRP）、**旅行商问题**（Travelling Salesmen Problem，TSP）及**多旅行商问题**（Multiple Travelling Salesmen Problem，MTSP）、**网络优化问题**（Network Flow Optimization，NFO）、**混合整数线性规划**（Mixed Integer Linear Programming，MILP）、**协同多任务分配问题**（Cooperative Multiple Task Assignment Problem，CMTAP）等。
> 
> 对于单一类型的运筹学问题，例如最大流、最短路径问题，常常使用VRP、TSP 和 MTSP 模型。针对具体的任务需求以及任务约束，常常需要在基本的VRP、TSP 模型的基础上建立相应的扩展模型，如考虑时间窗的 VRPTW 和 TWMTSP 模型。
> 
> NFO 以及动态 NFO 模型最早产生于邮递行业的分配。其受实际物流网的启发，以任务执行者为供应商，将待分配、执行的任务作为网格中的物流，以任务代价作为网络流中流动的代价，建立商业供需网格并通过最小化网络流的总代价实现多任务的协同分配。
> 
> MILP 模型和 CMTAP 模型主要适用于任务关系复杂、多种约束下的运筹学问题。MILP 模型中问题的是由二进制变量和连续变量共同描述的，可以有效解决任务分配中的约束问题，CMTAP 是一种建立在 NFO 和 MILP 模型基础上的组合优化模型，能够处理不同任务间的时序关系与促进关系，广泛应用于多类型运筹学问题。
> 
> 运筹学问题在数学上是一类组合优化问题，求解这类组合优化问题的方法包括经典整数规划与现代智能算法。**分支定界方法**（Branch and Bound，BNB）是任务分配中应用最广泛的一种经典整数规划方法。BNB通过分枝-定界-剪枝，逐步缩小搜索区域，对于小规模的问题可以在较短时间内获得满意的可行解。然而由于任务分配问题的NP（Non-deterministic Polynomial）特性，随着问题约束以及维度的增加，以BNB为首的经典整数规划算法难以获得较好的可行解。相比于确定性的经典算法，具有概率特性的智能优化算法在高维问题上体现出了一定的优势。现代智能算法包括**遗传算法**（Genetic Algorithm，GA）、**差分进化**（Differential Evolution Algorithm，DEA）等进化类算法和**粒子群优化**（Particle Swarm Optimization，PSO）、**蚁群算法**等群智能算法。本文主要讲解一下遗传算法在运筹学问题中的应用，当然一些局部优化算法也是可以使用的，而且在比赛时使用一些局部算法会有意想不到的惊喜，本文暂且不表，放到下一次进行讲解。

# 3、问题描述 #

> 以一个任务分配为例，任务分配的优化变量通常为整数，在实际建模过程中通常有两种表示：
> 
> 一是采用分配序号向量：
> 
> ![图片][ac00c9820024513043a349b772e3e44d.png]
> 
> 二是采用0-1分配矩阵：
> 
> ![图片][64fa270782c4948f346b264a68000956.png]
> 
> 同时对于任务分配问题，还需要有优化的目标，通常为时间最优或者成本最少。

# 4、遗传算法 #

> 遗传算法是一种全局优化方法，理论上具备寻找到全局最优解的能力。通常使用遗传算法需要对问题变量进行编码，由于任务分配问题本身决策变量就是一串整数，因此可以直接用决策变量作为基因编码进行优化。
> 
> ![图片][8cbf07ce24b195178f5ba500f8512bab.png]

# 5、仿真结果 #

> 下面给出一个旅行商问题的仿真计算。假设地图上有50座城市，一个商人需要遍历所有城市并最终回到起点，优化目标为总距离最短。这个问题的决策变量可以由1到50的排列序列的向量表示，该向量可以直接作为遗传算法的基因编码。在仿真中，城市位置随机选取，种群个数为60个，迭代次数为10000次。
> 
> 下图给出了50个城市的坐标位置：
> 
> ![图片][750609e50e312f9c89796ec9ed9021a3.png]
> 
> 使用遗传算法迭代过程：
> 
> ![图片][848a64732402cc2d1d63fd442ef3fa4d.gif]
> 
> 最终优化结果：
> 
> ![图片][bf711e7f54b95205dc1a00b052167f98.png]
> 
> 以及使用遗传算法迭代时的适应度曲线：
> 
> ![图片][5c5ed43ef85ebd0afeb2b0afc8d539c5.png]
> 
> 使用matlab运算大概只需要几秒钟就能算出啦。

[ac00c9820024513043a349b772e3e44d.png]: /images/20221024/b5590e2d39fb410793a14517430c7cb1.png
[64fa270782c4948f346b264a68000956.png]: /images/20221024/0febd309e71b48dfaa6bca7c887da3e1.png
[8cbf07ce24b195178f5ba500f8512bab.png]: /images/20221024/eb9f50b37947434c852da970c20bd7c5.png
[750609e50e312f9c89796ec9ed9021a3.png]: /images/20221024/b136f1044b8f42d1b63b2e0c83632e4f.png
[848a64732402cc2d1d63fd442ef3fa4d.gif]: /images/20221024/fc7500e0260b460ab085c8ed8412220f.png
[bf711e7f54b95205dc1a00b052167f98.png]: /images/20221024/5d97d2469a8246929b5ebddcfbcd3b1e.png
[5c5ed43ef85ebd0afeb2b0afc8d539c5.png]: /images/20221024/4669ef3dcd9b432eb155ea807f8787a5.png