一下数学建模中运筹学问题的常见解决方法与技巧（一）

1、简介

运筹学问题，包括任务规划、分配、决策等，是数学建模竞赛中的常见问题（见2018“高教杯”数学建模题B，2019美赛MCM题B）。今天小编就给大家分享一下数学建模中运筹学问题的常用解决方法和技巧。这篇文章比较适合刚入门的新手和对数学建模有一定接触的同学。当然，也欢迎各位大神交流讨论。

本文主要概述了比赛中可能出现的问题，并分享了遗传算法在运筹学问题中的应用。

2、常用模型和算法

首先是运筹学中一些常见的模型和算法。常见的运筹学模型包括车辆路径问题（VRP）、旅行商问题（TSP）、多旅行商问题（MTSP）、网络流优化（NFO）、混合整数线性规划（MILP）、合作多任务分配问题（CMTAP） ) 等。对于单一类型的运筹学问题，如最大流量、最短路径问题，通常使用 VRP、TSP 和 MTSP 模型。针对具体的任务要求和任务约束，往往需要在基本的 VRP 和 TSP 模型的基础上建立相应的扩展模型，例如考虑时间窗的 VRPTW 和 TWMTSP 模型。NFO 和动态 NFO 模型最早是在邮政行业的配送中发展起来的。受实际物流网络的启发，

MILP模型和CMTAP模型主要适用于任务关系复杂、约束条件多的运筹学问题。MILP模型中的问题用二元变量和连续变量来描述，可以有效解决任务分配中的约束问题。CMTAP 是基于 NFO 和 MILP 模型的组合优化模型，可以处理不同任务之间的时间序列。关系和促进关系广泛用于许多类型的运筹学问题。运筹学问题在数学上是一类组合优化问题，解决此类组合优化问题的方法包括经典整数规划和现代智能算法。分支定界（BNB）是任务分配中使用最广泛的经典整数规划方法。BNB通过分支-定界-剪枝逐渐缩小搜索范围，对于小规模问题可以在较短的时间内得到满意的可行解。然而，由于任务分配问题的NP（Non-deterministic Polynomial）特性，随着问题约束和维数的增加，以BNB为首的经典整数规划算法难以获得更好的可行解。与确定性经典算法相比，具有概率特征的智能优化算法在高维问题上具有一定的优势。现代智能算法包括进化算法，如遗传算法（GA）、差分进化算法（DEA）、群智能算法，例如粒子群优化 (PSO) 和蚁群算法。本文主要讲解遗传算法在运筹学问题中的应用。当然也可以使用一些局部优化算法，在比赛中使用一些局部算法会带来意想不到的惊喜。本文暂时不一一列举。

3、问题描述

以任务分配为例，任务分配的优化变量通常是整数，在实际建模过程中通常有两种表示形式：

一种是使用分配序号向量：

第二种是使用0-1分布矩阵：

同时，对于任务分配问题，需要有一个优化目标，通常是最优时间或最小成本。

4、遗传算法

遗传算法是一种全局优化方法，理论上具有寻找全局最优解的能力。通常，遗传算法需要对问题变量进行编码。由于任务分配问题的决策变量本身是一串整数，因此决策变量可以直接作为遗传密码进行优化。

5、模拟结果

下面给出旅行商问题的模拟计算。假设地图上有50个城市，一个商人需要遍历所有城市，最后回到起点，优化目标是总距离最短。这个问题的决策变量可以用一个从 1 到 50 的排列序列向量来表示，在遗传算法中可以直接编码为基因。模拟中随机选取城市位置多目标差分进化算法 matlab，人口数为60，迭代次数为10000。

下图给出了50个城市的坐标：

使用遗传算法的迭代过程：

最终优化结果：

以及使用遗传算法迭代时的适应度曲线：

使用matlab计算只需几秒钟。

受疫情影响，铁子一定要抓住在线数学建模大赛的机会，该大赛含金量高，有助于提高考研分数。

继全国赛和美赛之后的第三届大赛，被多所高校推广，甚至被列为全国大赛选拔：

2022第七届维度杯数学建模挑战赛正在报名中

进群领取历年赛题、优秀论文等相关备考资料多目标差分进化算法 matlab，获取大赛最新资讯