数学建模校赛latex⽂档
垃圾csdn没有latex⾼亮
% !Mode:: "TeX:UTF-8"
% !TEX program  = xelatex
% \documentclass{cumcmthesis}
\documentclass[withoutpreface,bwprint]{cumcmthesis} %去掉封⾯与编号页，电⼦版提交的时候使⽤。
\usepackage[framemethod=TikZ]{mdframed}
\usepackage{url}  % ⽹页链接
\usepackage{subcaption} % ⼦标题
\usepackage[section]{placeins}%浮动题在section前输出
\title{基于双层模拟退⽕算法的运动场选址问题解决⽅案}
\tihao{A}
\baominghao{4321}
\schoolname{XX⼤学}
\membera{杨丽冰 }
\memberb{ }
\memberc{ }
\supervisor{ }
\yearinput{2020}
\monthinput{08}
\dayinput{22}
\begin{document}
\maketitle
\begin{abstract}
随着城市的不断发展，城市环境的改善对于众⽣活⽔平的提升越发重要，以运动场为例的城市设施是提升城市环境的⼀重要途径。本⽂通过研究运动场建设位置合理选址，建⽴了运动场选址模型，计算出了最佳新运动场的选址。此外，还综合既有运动场选定地址，对其合理性进⾏了分析和评价。
⾸先，我们基于\textbf{P-中值模型}，针对运动场建设成本建⽴了模型。由于P中值模型仅仅考虑到了设施与需求点之间的运输成本，⽽实际上除了运输成本，现实中还有其他的成本，实⽤性具有⼀定的限制，我们在P中值模型的基础上进⾏了扩展，考虑了设施的建设成本、设施的容量限制。当设施的容量达到上限时，居民会选择前往其他的运动场。
其次，针对居民从居民区到运动场的成本消耗问题，我们将距离最短的路径利⽤\textbf{Dijkstra算法}，建⽴了最短路模型。
基于这两个模型，我们的到了⽬标函数，由于⽬标函数的解有两部分组成，我们采⽤\textbf{双层模拟退⽕算法}，分为两个层次，⾃下⽽上求解。
针对问题⼀，我们在所建设运动场数量为4时，运⽤双层模拟退⽕算法求得了最优解与其对应的选址的
集合，最优选址为2，3，4，7。
针对问题⼆，为了分析原来的选址是否合理，我们结合\textbf{Topsis优劣解距离法}，通过计算得到了最优选址与原选址的误差值，对原选址做出了较优的评价。
针对问题三，其本质仍是最⼩化相关费⽤的前提下，从可选设施集合中确定设施的修建位置。因此，我们仍沿⽤问题⼀所建⽴的数学模型，在选择设施位置的领域函数上做出改动。随后，我们使⽤迭代搜索，在最低计算开销下到最优解。再不超过运动场容量限制的情况下，内层模拟退⽕算法为居民点分配对应的运动场，使得加权距离和最⼩。最终，我们求出了最优解与其对应的选址的集合，选址为2，6，12，15，18。
最后，在模型的评价中，我们对模型的局限与优缺点进⾏了分析。
\keywords{规划问题\quad  双层模拟退⽕算法\quad  最短路\quad  p-中值模型\quad Topsis优劣解距离法}
\end{abstract}
%⽬录  2019 明确不要⽬录，我觉得这个规定太好了
%\tableofcontents
%\newpage
\section{问题重述}
城市环境是包括居住环境、交通环境在内的⼀个地域综合体。随着我国经济社会的不断发展，城市环境成为评价众⽣活质量的⼀个重要指标，
⽽如运动场等配套设施的建设成为了提升城市环境的⼀重要途径。如何在合理地规划城市环境、建设城市周边配套设施的同时⼜节约开⽀，以求达到城市建设者与众多⽅利益最⼤化，成为了需要解决的⼀⼤难题。
本题是以给定地点区域简化图为基础，寻求新建运动场选址，并探求既有运动场建设合理性。从本题区域简化图中可以得知各居民点的位置信息，包括连通
本题是以给定地点区域简化图为基础，寻求新建运动场选址，并探求既有运动场建设合理性。从本题区域简化图中可以得知各居民点的位置信息，包括连通关系、距相邻居民点的距离。从题⽬给出的数据中亦可得到个点居民数。该区域既有4块运动场，分别位于4，6，12，15号居民点。
在模型中，我们需要考虑运动场建设成本问题、⼈均出⾏时间与距离成本，运动场容量等多⽅⾯问题。
最后，根据模型得出的结果与既有运动场选址点进⾏对⽐，分析既有选址点选址的合理性，并对新建选址给出科学的指导性意见。
\section{问题分析}
\subsection{对问题⼀的分析}
问题⼀要求建⽴合适的选址模型。选址问题类似于⾮线性规划以及组合优化问题。选址模型可以⼤致分为定性和定量两⼤类。⽬前较常见的⽅法包括重⼼法、层次分析法、最短路径法。重⼼法只考虑单个设施，层次分析法没有相关数据⽀撑，最短路径法仅考虑了居民点距离运动场的距离。选址问题属于np难题，在求解规模较⼤的选址问题上计算成本很⾼。
故本⽂采取双层模拟退⽕算法求解，外层对运动场选址⽅案进⾏优化，内层在确定运动场位置的情况下，进⾏居民运动需求的分配优化。
该⽅法收敛速度快，且能得到更符合实际情况的最优解。
\subsection{对问题⼆的分析}
问题⼆要求分析题⽬给定的⽅案是否合理。可以通过的建⽴模型求得最优解。本⽂结合了Topsis优劣解距离法，在此基础上通过最优解偏差百分⽐来评价题⽬给定⽅案是否合理。
\subsection{对问题三的分析}
问题三要求确定新增运动场的最佳位置。解决思路为：枚举运动场位置，再确定运动场位置的前提下，通过模拟退⽕算法求得⽤户需求的最佳分配⽅案。
\section{模型假设}
\begin{itemize}
\item 假设每个居民点的所有居民会选择⼀个长期固定的运动场；
\item 假设居民去运动场时均⾛最短路径；
\item 假设居民前往运动场的成本与距离成线性关系；
\item 假设运动场的固定建设成本与地理位置及容量有关。相较于边缘位置，中⼼位置的成本更⾼；
\item 假设每个运动场运动场有容量限制，且各运动场容量⼤⼩成正态分布；
\item 假设运动场建设成本和容量成正相关；
\end{itemize}
\section{符号说明}
\begin{table}[!htbp]
\caption{符号定义}\label{tab:003} \centering
\begin{tabular}{ccccc}
\toprule[1.5pt]
符号 & 定义\\
\midrule[1pt]
$N$ & 居民区的数量\\
$M$ & 运动场的数量\\
$I$ & 居民区位置的集合\\
$J$ & 运动场可选位置的集合\\
$C_{ij}$ & 从居民地i到运动场j的最短距离\\
$D_i$ & 居民区i的运动需求量\\
$A_j$ & 运动场j的容量\\
$X_{ij}$ & 从居民地i是否去运动场j的决策变量，去为1，不去为0\\
$F_j$ & 建设运动场j所需固定费⽤\\
$Y_j$ & 是否建设运动场j，建设了运动场时为1，否则为0\\
\bottomrule[1.5pt]
\end{tabular}
\end{table}
\section{模型的建⽴和求解}
\subsection{⽬标函数}
P-中值模型是给定数量、位置的需求集合、候选设施位置的集合下，分别为P个设施到
合适位置并分配给每个需求点之间的运输总成本达到最低\cite{001}。该问题是⼀个N-P难题。
由于P-中值模型仅仅考虑到了设施与需求点之间的运输成本，⽽实际上除了运输成本，现实中还有其他的成本，
实⽤性具有⼀定的限制。于是我们在P-中值模型的基础上进⾏了扩展，考虑了设施的建设成本，以及设施的容量限制。
当设施的容量达到上限时，居民会选择前往其他的运动场。
于是基于P-中值模型，建⽴了⼀个选址模型的⽬标函数$Z$：
\begin{equation}
min Z = \sum_{i = 1}^{N} \sum_{j = 1}^{N}D_iC_{ij} X_{ij}+ \sum_{j = 1}^{N}F_jY_j
\label{eq:a}
\end{equation}
约束条件：
\begin{equation}
\sum_{j = 1}^{N} X_{ij} = 1,\forall i\in I
\label{eq:b}
\end{equation}
\begin{equation}
\sum_{i = 1}^{N} D_iX_{ij} \leqslant A_j ,\forall i\in I,\forall j\in J
\end{equation}
\begin{equation}
X_{ij} \leqslant Y_j,\forall j\in J
\end{equation}
\begin{equation}
\sum_{j = 1}^{N} Y_j = M ,\forall j\in J
\end{equation}
\begin{equation}
X_{ij}=
\begin{cases}
1 &  \text{居民地i去运动场j}\\
0 &  \text{居民地i不去运动场j}\\
\end{cases}
,i \in I,j \in J
\end{equation}
\begin{equation}
Y_j=
\begin{cases}
0 &  \text{在居民地i不建运动场}\\
1 &  \text{在居民地i建运动场}
\end{cases}
,j \in J
\end{equation}
上⾯式（2）保证了每个居民区都只去⼀个运动场，式（3）保证了不超过过运动场的容量，式（4）保证了只有运动场已经建设，
居民才能选择该运动场，式（5）保证了总共选择建设了M个运动场。
该模型的⽬标函数包括两部分，第⼀部分是居民去运动场的成本，第⼆部分是建设运动场的成本。解的形式也主要包括两部分，⼀个为是否修建运动场的决策变量$Y_i$，另⼀个是居民是否选择运动场的决策变量$X_{ij}$,
并由$Y_j$最终决定$X_{ij}$。
第⼀部分的成本主要由最短距离决定，第⼆部分成本与位置点的度，和容量⼤⼩成正相关。
\subsection{最短路模型建⽴}
在考虑居民从居民区到运动场的成本消耗时，我们将距离最短$C_{ij}$作为⽬标函数的⼀个重要因素，针对该问题我们采⽤的是图论中的
最短路算法Dijkstra求解。
V和E分别是图的定点集合$ V=\{v_1,v_2,v_3……v_n\}$；
图中边的集合$ E=\{e_1,e_2,e_3……e_n\}$；
图中起始点到定点的距离集合为$dis = \{dis_1,dis_2,dis_3……dis_n\} $;
Dijkstra算法采⽤的是⼀种贪⼼的策略，解决的是带权重的有向图上单源最短路径问题，改算法要求所有边的权重都为⾮负值。
Dijkstra算法在运⾏过程中维持的关键信息是⼀组节点集合$S$。从源节点$s$到集合中每⼀个节点间的最短路径已被到。
算法重复从节点集$V-S$中选择最短路径估计最⼩的节点u，将u加⼊到集合$S$，然后对所有从u发出的边进⾏松弛\cite{004}。
步骤为：初始时，原点 s 的路径权重被赋为 0 。若对于顶点 s 存在能直接到达的边E（s,m），则把$dis_m$设为w（s, m），同时把所有其他（s不能直接到达的）顶点的路径长度设为⽆穷⼤。初始时，集合S只有顶点s。centering
然后，从dis集合选择最⼩值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加⼊到S中，此时完成⼀个顶点，
然后，我们需要看看新加⼊的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否⽐源点直接到达短，如果是，那么就替换这些顶点在di s中的值。
然后，⼜从dis中出最⼩值，重复上述动作，直到S中包含了图的所有顶点。
通过Dijkstra算法，求解得到了⼀个$18\times18$的最短路矩阵$C_{ij}$。
\subsection{双层模拟退⽕模型建⽴}
\subsection{双层模拟退⽕模型建⽴}
\subsubsection{模拟退⽕算法}
模拟退⽕算法(SA)是⼀种通⽤的随机搜索算法，它来源于固体退⽕原理。将固体加温⾄充分⾼，再让其徐徐冷却，加温时，固体内部粒⼦随温升变为⽆序状，内能增⼤，⽽徐徐冷却时粒⼦渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最⼩\cite{006}。
SA算法⽤于解决组合优化问题的算法，物理中固体物质的退⽕过程与⼀般组合优化问题具有相似性。⽤固体退⽕模拟优化问题，将内能模拟为⽬标函数，温度演化为控制参数。
组台优化问题解空间⼱的每⼀点都代表⼀个解．不同的解有着不同的成本函数值。所谓优化，
就是在解空问中寻成本函数值最⼩(或最⼤)的解\cite{002}。在解空间内结合概率特性寻最优解。
模拟退⽕算法于初始值⽆关，并且具有收敛性，已经在理论上证明以⼀种概率1收敛于全区最优解。所需的⼏个控制参数为：
初始温度$T_0$：为了接近最优解，应该设置的较⼤，本⽂中设置$T_0 = 5000$;
温度降温系数$\Delta T$：是⼀个⼩于1且接近的值，本⽂中设置为$\Delta T = 0.95$；
最⼤迭代次数$ML$：最⼤迭代次数，令$ML = 400$；
当前迭代次数$NL$：对于每个T，当前迭代的次数；
迭代停⽌条件：本为中，当$NL\geqslant ML$时，令程序迭代停⽌。
\subsubsection{双层模拟退⽕算法解的更新⽅法}
模拟退⽕中其中的重要⼀步是解的更新，上⽂中提到，模型的解包括了两部分。因此我们的算法需要对模型分为两个层次进⾏求解。
双层模拟退⽕算法采⽤⾃下向上的求解过程，并采⽤模拟Metropolics准则，接受领域解，直到满⾜终⽌条件。
Metropolics准则常表⽰为\cite{003}：
\begin{equation}
p =
\begin{cases}
1 &  ,E_{n+1} < E_n\\
exp(-\frac{E_{n+1} -E_n }{T} ) &  ,E_{n+1} \geqslant  E_n
\end{cases}
\label{eq:Metropolics}
\end{equation}
从\cref{eq:Metropolics}式中可以看出，如果移动后可以获得更优解，总是接受新的解；如果不是最优解，则会以⼀个随着温度降低⽽减⼩的概率接受新的解，可以
避免限⼊局部最优，从⽽可以获得全局最优解。
外层的初始解，被选择建设运动场的集合为随机分配的4个点组成，例如F=\{1,2,3,4\}。该集合表⽰的含义为居民区1,2,3,4被选择建造运动场，
其他居民区不建造运动场。在每次更新集合的时候，采取的操作为：在未被选择的居民点集合中随机选择⼀个居民点，与集合F中的任⼀点进⾏交换。这样就完成了每次⽣成新的解。
对于内层来说，对于每⼀个新的外层集合，随机选择⼀个决策变量$X_{ij}$置为1，更新时，选择⼀个新的$j\`'$，满⾜$X_{ij\`'} =0$并且不会超过运动场的容量限制，
令新的$X_{ij\`'} =1$，原来的$X_{ij\`'} =0$替换原来的居民需求决策变量。更新时，内层退⽕算法的参数可以直接使⽤外层的退⽕参数。
\subsubsection{双层模拟退⽕算法具体实现步骤}
(1)初始化：初始化温度$T_0$，温度降温系数$\Delta T$，最⼤迭代次数$ML$，随机⽣成初始初始解。
(2)执⾏外层领域函数，得到新的运动场建造决策变量$Y_i$。
(3)以当前$Y_i$为最优解，执⾏内层邻域函数，得到新的居民区$i$选择运动场$j$的决策变量$X_{ij}$。
(4)如果内层新的选择的加权距离和优于内层最优解，更新内层最优解。
(5)如果内层新的选择的加权距离和优于内层选址旧解，更新内层旧解，否则在[0,1] 产⽣⼀个均匀分布的随机数 $e$，如果$e<p$($p$是前⾯定义的接受概率），也更新内层最优解。
(6)根据Metropolics准则，接受内层解则内层迭代次数加⼀，否则返回步骤(3)。
(7)如果内层迭代次数⼤于最⼤迭代次数，满⾜终⽌条件，返回外层，否则返回步骤(3)。
(8)如果当前的$Y_i$和$X_{ij}$⽬标函数总花费⼩于保存的全局最优解，更新全局最优解。
(9)如果新的外层建造运动场选址优于旧解，接受外层解，否则在区间 [0,1] 产⽣⼀个均匀分布的随机数 $e$，如果$e<p$，这种转移也将被接受。
(10)根据Metropolics准则，如果接受新的外层解，则温度下降，迭代次数加⼀，否则返回步骤(2)。
(11)如果迭代次数⼤于最⼤迭代次数，满⾜终⽌条件，算法结束，输出当前全局最优解，否则返回步骤(2)。
对于外层其算法实现流程图如\cref{fig:001}所⽰。
\FloatBarrier
\begin{figure}
\centering
\includegraphics[scale=0.33]{1.png}
\caption{外层算法流程图}
\label{fig:001}
\end{figure}
\FloatBarrier
% \FloatBarrier
% \begin{figure}
%    \centering
%    \includegraphics[scale=0.4]{untitled.png}
%    \caption{最优解-迭代次数图像}
%    \label{fig:002}
% \end{figure}
% \FloatBarrier
% \begin{figure}
%    \centering
%    \includegraphics[scale=0.5]{untitled1.png}
%    \caption{题⽬中结论在全部答案中的⽔平}
%    \label{fig:003}
% \end{figure}
\subsection{问题⼀}
基于上⽂中的模型，我们在$M=4$的情况下，对模型求解，解得⽬标函数$Z$的最优解为13467，选址的集合为\{2，3，4，7\}。
同时
得到居民地选择运动场的对应关系见\cref{fig:xz4}、最短距离如\cref{tab:result01}所⽰。
\FloatBarrier
\begin{table}[!htbp]
\caption{建造4个运动场结果展⽰}\label{tab:result01} \centering
% \resizebox{100mm}{70mm}{
\begin{tabular}{ccccc}
% \specialrule{10}{10}
\toprule[1.5pt]
居民区下标$i$ & 运动场下标$j$ & 最短距离$C_{ij}$\\
\midrule[1pt]
1  &
2 &  20 \\
2  &  2 &    0\\
3  &  3 &    0\\
4  &  4 &    0\\
5    & 4 &  18\\
6  &  4 &  18\\
7    & 7  &  0\\
8    & 4&    50\\
9  &  2  &  30\\
10    & 2    &28\\
11  &  2  & 30\\
12  &  3  & 20\\
13  &  3  & 48\\
14  &  3  &  26\\
15  &  4  & 42\\
16    & 3  &  38\\
17    & 4  &  48\\

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。