论文总字数：54998字
% !TEX TS-program = xelatex
% !TEX encoding = UTF-8 Unicode
% !Mode:: "TeX:UTF-8"
\documentclass[bachelor,nocolorlinks, printoneside]{seuthesis} % 本科
% \documentclass[master]{seuthesis} % 硕士
% \documentclass[doctor]{seuthesis} % 博士
% \documentclass[engineering]{seuthesis} % 工程硕士
\usepackage{CJK,CJKnumb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{bm}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{subfigure}
\usepackage{amssymb,amsthm}
\usepackage{listings}
\usepackage{setspace}
\usepackage{longtable,booktabs}
\usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\newtheorem{thm}{定理}[section]
\newtheorem{defn}{定义}[section]
\newtheorem{lemma}{引理}[section]
\newtheorem{prop}{命题}[section]
\newtheorem{rem}{备注}[section]
\floatname{algorithm}{算法}
\renewcommand{\algorithmicrequire}{\textbf{输入:}}
\renewcommand{\algorithmicensure}{\textbf{输出:}}
% 这里是导言区
\setlength{\baselineskip}{22pt}
\begin{document}
\categorynumber{000} % 分类采用《中国图书资料分类法》
\UDC{000} %《国际十进分类法UDC》的类号
\secretlevel{公开} %学位论文密级分为"公开"、"内部"、"秘密"和"机密"四种
\studentid{07315119} %学号要完整，前面的零不能省略。
\title{在无穷模下圈图上的1-重心选址逆问题}{}{The inverse 1-median location problem on a cycle under $l_\infty$ norm}{subtitle}
\author{郭雨微}{Yuwei Guo}
\advisor{关秀翠}{教授}{Xiucui Guan}{Prof.}
%\coadvisor{副导师}{副教授}{Co-advisor's Name}{Associate Prof.} % 没有
% \degree{工学硕士} % 详细学位名称
\major[12em]{统计学}
\defenddate{答辩日期}
\authorizedate{学位授予日期}
\department{数学}{department name}
\duration{2019年1月1日—2019年5月30日}
\address{东南大学李文正图书馆数学学院}
%\thanks{本论文获国家XXX计划项目（2012AA00A00）和国家杰出青年科学基金项目（01234567）资助。}
\maketitle
\begin{abstract}{选址逆问题，圈， 1-重心，线性规划，原始-对偶算法}
选址问题是运筹学领域的一个重要问题，指如何在网络中对公共设施进行最优选址以提高效率。本文研究圈上$l_\infty$模下调整点权的 1-重心选址逆问题(简记为 $(I1MC_\infty)$ ): 在 $l_\infty$模下以最小费用改变点权，使得圈图上一个预先指定的顶点成为1−重心。首先将该问题转化为一个线性规划模型, 然后用原始对偶算法求解。其基本思想是：每次迭代由$(I1MC_\infty)$的对偶问题$(D)$的一个可行解$\pi$出发，确定该解对应的允许集的集合J,求得限定原问题的对偶问题$(DRP)$的最优解$\hat{\pi}$, 确定参数$\theta$, 更新得到新的对偶可行解$\pi_{new}=\pi \theta \hat{\pi}$。直到问题$(DRP)$的最优目标值为零，就得到问题$(D)$的最优解，并且通过互补松紧性得到原逆问题的最优解。最后，将原始对偶算法进行数值实验。对于一个含有 $9$个顶点的圈图，我们将通过原始对偶算法求解对偶问题$(D)$得到的解与用线性规划直接求解问题$(D)$的最优解进行对比，最优目标函数值相等，两个最优解中只有一个分量不同，而该分量的价值系数为0，说明两个最优解都是正确的。接着，我们又随机生成了实例，分别测算了$n=15,20,30,50$个顶点的圈图上的逆问题，都能在不足0.5秒的时间内求出最优解，说明了该算法的有效性。
\end{abstract}
\begin{englishabstract}{The inverse location problem, circle, 1-median Linear programming, Primitive-dual algorithm}
The location problem is an important issue in the field of operations research. It is to study how to set the public facilities in the network, so that the efficiency is optimized.\\
In this paper, we focus on the inverse 1-median problem on a cycle under $l_\infty$ norm (denoted by $(I1MC_\infty)$ ) by modifying the weights of vertices. We aim to modify the weights of vertices as less as possible under $l_\infty$ norm so that a prescribed vertex becomes a q-median of the given cycle.\\
We first formulate the problem $(I1MC_\infty)$ as a linear programming problem, then solve it by a primal-dual algorithm. The basic idea is as follows. In each iteration, we start from a feasible solution $\pi$ of the dual problem $(D)$ of $(I1MC_\infty)$, then determine the admissible set $J$, solve the dual problem $(DRP)$ of restricted primal problem generated by $J$ and obtain an optimal solution $\hat{\pi}$. After obtaining the parameter $\theta$, we can update the dual feasible solution $\pi_{new}=\pi \theta \hat{\pi}$ of problem $(D)$. The iterations will be terminated when the current optimal objective value of $(DRP)$ is zero, in which case, we can obtain an optimal solution of the dual problem $(D)$, as well as, the inverse problem $(I1MC_\infty)$ by complementary slackness conditions.
Finally, we do some numerical experiments. Firstly, we apply the primal-dual algorithm to a cycle with 9 vertices. Comparing the optimal objective value obtained by primal-dual algorithm and linear program function, we can conclude that they have the same objective values and there is only one different element in the two optimal solutions, whose cost coefficient is zero, which means both of the two solutions are optimal. Secondly, we generate randomly some instances with number of vertices $n=15,20,30,50$, respectively. We can all obtain the optimal solutions in CPU time less than 0.5 seconds, which shows the effectiveness of the primal-dual algorithm.
\end{englishabstract}
\tableofcontents
\begin{Main} % 开始正文
\chapter{绪论}
\section{研究背景}
\par{选址问题是运筹学的一个重要分支，是研究如何在网络中对公共设施进行最优选址，使得效率提高的问题。选址问题的研究内容十分广泛，上到学校和政府机关部门选址、医疗和消防等相关服务部门的选址，下到网络服务器搭建、商圈和生产仓库以及物流配送中心的选址。如果能够将所有公共设施都按照最优性条件进行选址，那么国民生活效率、经济利润将会得到大幅度的提升。选址问题的正式理论研究最早可追溯到1909年的weber问题。weber在考虑一个仓库选址时提出，如何选址使得最终仓库点与服务对象之间的距离和最小的问题。从此，选址问题开始活跃在大众眼中，而对此的理论研究也逐步发展起来。1964年，S.L.Hakimi\cite{Hakimi}首次提出$p-center$问题和$p-median$问题，这极大促进了选址问题的理论研究，而$p-center$问题和$p-median$问题也从此正式成为选址问题中的两个基本类别，在选址问题中占据极其重要的地位，其他选址问题也大多基于这两个问题进行展开。}
\subsection{选址问题的原问题和逆问题}
\par{选址优化问题就是运用最优化的理论与算法，使得选址达到最优，即找到一个顶点，使得其他顶点到该点的加权距离和最小。这适用于公共服务设施还未搭建的情况，在周边环境既定的情况下选择最优点设址。但对于公共服务设施已搭建完成，且迁移费用巨大时，周围环境的变化使得该点偏离最优选址点时，就需要借助本文所要研究的“优化问题的逆问题”进行解决。优化问题的逆问题，就是以最小费用调整各参数使得给顶点成为最优选址中心。1992年，Burton和Toint\cite{BurtonToint}在研究一个地质问题中提出最短路径问题的逆问题。他们研究的是在某一给定的网络中，在使边长调整量尽在某种模意义下可能少的情况下，
使得到的新的路径为最短路径。如下所示的$l_0$、$l_1$、$l_2$和$l_{\infty}$是目前最常研究的几种模：}
\begin{flalign}
l_{0}\text{模:~~~} amp;\|\overline{c}-c\|_{0}=\#\left\{j | c_{j} \neq \overline{c}_{j}\right\}=\sum_{j} H\left(c_{j}, \overline{c}_{j}\right)\\
l_{1}\text{模:~~~} amp;\|\overline{c}-c\|_{1}=\sum_{j} w_{j}\left|\overline{c}_{j}-c_{j}\right|\\
l_{2}\text{模:~~~} amp;\|\overline{c}-c\|_{2}=\sqrt{\sum_{j} w_{j}\left(\overline{c}_{j}-c_{j}\right)^{2}}\\
l_{\infty}\text{模:~~~}amp;\|\overline{c}-c\|_{\infty}=\max _{j}\left\{w_{j}\left|\overline{c}_{j}-c_{j}\right|\right\}
\end{flalign}
\par{
另外，传统的选址优化主要是事先在地图上进行选址，再进行人为实地考察。而这一方法大量耗费人力物力，并且产生一定程度上不可逆转的后果，更重要的是难以充分考虑全部影响因素，造成效率低迷。因此基于地图选址、人为考察的最优化选址算法也被一一挖掘出来。选址问题按照候选点的不同性质可以分为离散选址、连续选址和网络选址。离散选址问题致力于解决待当选区内只有若干有限个候选点时的选址问题，这与实际情况十分契合；连续选址问题则致力于解决当待选区内有若干无限个候选点的选址问题，在理论上表示候选区内的点地位相同，任意一个都可以当作候选点，这种情况更加偏向理论研究。网络选址区别于二者，致力于研究在某个网络上的若干个候选点的选址问题。运用网络选址，可以避免实地选址偏离最优选址而造成的浪费，以及再进行地点迁移所带来的费用。目前主流的网络图包括树图、圈图、星图、网络图、三维内平面图以及各种组合图，其中研究最多的是树图和圈图。}
\par{
连通图$G$的树图满足如下定义。假设连通图$G=(V,E)$有$p$个生成树$T_1,T_2,\dots,T_P$,则可求出与它们一一对应的$p$个顶点$v_1,v_2,\dots,v_p$
。记$l_i$为路径$E_i$的边长，当且仅当顶点$v_i\text{和}v_j$对应的两棵生成树$T_i\text{和}T_j$间的距离等于
1时,即$d(T_i,T_j)= 1,(i,j= 1,2,\dots,p)$,得到的一个新图称作图$G$的树图,记做$T(G)=(V_t,E_t)$。目前已有众多学者对于树图上的$p=1,2$的$p-center$和$p-median$逆问题进行了研究，也得到了大量结论和多种算法，计算时间复杂度也一直在下降。}
\par{
对于圈图上的选址问题，假设图$G(V,E)$有$n 1$个顶点，每个顶点的权重都非负，每条边的变长都为正。那么圈上的逆1-重心问题的解决可以从调整点权、调整变长以及两者同时调整着手。本文则重点从以最小费用调整点权来使得一预先给定的顶点成为$1-median$。这一理论研究结果可以运用于许多方面，例如在环城高速公路上设置加油站或服务区站点、在旅游景点设置公共厕所等。但对于圈图上的逆问题的研究文献目前却不是十分充足\cite{suihao}，因此本论文将重点研究$l_{\infty}$模下圈图上的逆$1-median$问题，希望能够用自己的绵薄之力填补这一学术空缺。
}
\subsection{理论研究意义和实际应用价值}
\par{
选址问题涉及到的范围十分广泛，从城市建设、产业链、经开区、跨国经济集团国内公司建设到机场火车站、水利设施和消防点、人类适宜居住区、销售线下网点以及仓库、物流配送中心等的区位选址决策都属于选址问题研究的范畴，涉及学科也从政治、经济、管理、社会到工程地质、心理、数学、计算机等多门学科。在众多选址问题中，设施选址占据了十分重要的角色，是一个重要研究领域。那些与人类生活生产、商业流通、文化素质培养等事物相关，且占地规模相对较小的具体网点、场所就称为社会设施，包括生产工厂、货运仓库、消防中心、变电站、垃圾处理中心、加油站、图书馆、博物馆等。对一个给定条件约束限制的组合优化问题，逆优化问题致力于研究如何用最少的花费以改变原问题中的权重或参数，使得那些原问题的可行解成为改变参数后新问题的最优解。许多学者对这类问题产生了高度重视，发表大量论文进一步研究逆优化问题的理论价值，并运用于解决实际问题。}
\par{
首先，目前为止鲜少有已发表的且影响力重大的论文对在$l_{\infty}$模下圈图上的$1-median$选址逆问题进行研究。其次，通过对选址逆问题的研究建立起数学模型，可以在理论上优化实际选址，避免造成资源和人力不必要的浪费。理论上的网络选址能够随着相关条件的变化和人类知识储备的发展，通过调整相关变量和参数，更好地适应新环境。且对其运用到的算法也能进行进一步的优化和延伸，使其理论研究价值发挥淋漓尽致。同时，由于初步选址停留在理论层面，这将为人们提供更多在实际建设中无法考虑到的思路，刺激创新。最后，本文运用原始-对偶法，借助MATLAB软件解决这一问题，进一步拓宽了原始-对偶法的运用范围，并且为后人提供了一种新的原始-对偶迭代算法用以解决逆优化问题。}
\par{
在实际生活中，随着周围网络环境的发展变化，建立一段时间后的公共设施可能会逐渐偏离网络重心位置。若不对它们进行迁移，那势必会影响人们的生产生活效率，造成资源配置失调。可一旦对公共设施进行迁移，那么迁移费用、人们的适应成本等不能不被考虑进去，这些费用的总和将远大于对网络连接的改进费用。为应对这一问题，$p-median$问题的逆问题应运而生。这一问题致力于解决如何耗费尽可能小的费用修改网络上的权重和参数，使得其他顶点到该网络上p个事先给定的设施点中最近一个的加权距离和不大于一预先给定的上界。换言之，$p-median$问题能够解决如何运用最小费用改变网络连接权参数或运输费用的同时，使得已经搭建完成的设施保持原址，避免迁移带来的巨大损失。
}
\section{文献综述}
\subsection{$p-median$问题的研究综述}
\par{
$p-median$问题是一类最基本的选址问题，它在研究选址问题中占据了十分重要的地位。黎青松\cite{liqingsong}等人整理了$p-median$问题的性质、算法设计思想等现有的研究成果，并指出了选址问题未来的研究方向。记$G(V,E)$为网络中有n个顶点、m条边的无向图，其中$V={(v_1,v_2,\dots,v_n)}$为顶点集，$E={(E_1,E_2,\dots,E_m)}$为边集。记$d(i,j)$为两个顶点$v_i\text{与}v_j$之间的最短路径。于是$p-median$问题就可以表示为：设点集$X\subset{G},|X|=p, X=\{x_{1}, x_{2}, \dots, x_{p} | x_{i} \in G, i=1,2,\dots,p\}$，对任意既定函数$f_i,\forall v_i\in V$，定义函数$f(X)=\sum_{v_{i} \in V} f_{i}\left(D\left(v_{i}, X\right)\right)$,求$X^{*}=\{x_{1}^{*}, x_{2}^{*}, \cdots, x_{p}^{*} | x_{i{}}^{*} \in G, i=1,2,\dots,p\}$和$g(X^*)$，满足$g\left(X^{*}\right)=\min \{f(X) :|X|=p,X\subset{G}\}$。若其中$X\subset{V}$，则称该问题为$p-median$问题。
}
\par{
剩余内容已隐藏，请支付后下载全文，论文总字数：54998字
该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找;
