论文总字数：20251字

摘 要

本篇论文主要关注的是树上1-重心选址的逆问题，其中有客户点集合以及候选设施位置集合，它们被假定为基础树顶点的两个选择性子集。在经典的重心选址问题中，目标是找到并建立一个设施的最佳位置，并且还要满足从客户到设施的加权距离之和最小。由此出发，相应的逆问题的任务是，以最小的总成本增加或减小点的权重，直到预定的设施位置成为树的1-重心，包括修改客户的权重，以最小范围内的特定供应商为中心的修正位置问题。

对于树上1-重心选址的逆问题，在加权范数和加权瓶颈哈明距离下都分别有线性算法， 本文提出了一种新的逆问题模型——在加权模及哈明距离组合模下的树上的1-重心选址逆问题，我们分析了其性质，利用其与加权范数和加权瓶颈哈明距离下逆问题的关系，同样设计了时间复杂度为O(n)多项式时间算法。此外，我们又研究了三个添加约束条件下的树上在模下的1-重心选址的逆问题，分别为加权范数、加权瓶颈哈明距离和组合模的约束条件，通过设定不同的点权调整上界向量，我们都将其转化为树上在模下的1-重心选址的逆问题，从而得到时间复杂度为O(n)多项式时间算法。

关键词：1-重心选址逆问题，逆优化问题，树，哈明距离， 模, 模

Abstract

This paper focuses on the inverse 1-median problem on trees, where there is a set of customer points and a set of candidate facility locations, which are assumed to be two selective subsets of the base tree vertices. In the classic problem of location problems, the goal is to find and establish the best location for a facility, and also to minimize the sum of the weighted distances from the customer to the facility. From this point of departure, the task of the corresponding inverse problem is to increase or decrease the weight of the point with the minimum total cost until the predetermined facility location becomes the 1-median of the tree, including modifying the weight of the customer.

For the inverse 1-median problem on trees, there are linear time algorithms to solve them when the modification are measured by weighted norm and weighted bottleneck-Hamming distance. We propose a new model, in which the modification are measured by the sum of weighted norm and weighted bottleneck-Hamming distance. We analyze the properties of the new model and the relationship among the combined norm and the two respective norms. We present an algorithm to solve the new model which runs in O(n) time. Furthermore, we consider the inverse 1-median problem on trees under norm by adding three norm constraints. For each constrained inverse 1-median problem, we devise a new upper-bound vector and then convert the constrained inverse into the inverse under norm, which runs in linear time.

KEY WORDS: Inverse 1-median problem, inverse optimization, Trees, Hamming distance, norm, norm

目录

摘要 I

Abstract II

第一章 介绍 1

1.1 文献综述 1

1.2 知识储备 3

1.2.1 经典选择性重心选址问题及其逆问题 3

1.2.2 1-重心选址问题及其逆问题 4

第二章 加权范数下的1-重心选逆问题 6

2.1 问题研究 6

2.2 O(n)时间算法 7

第三章 加权瓶颈哈明距离下的1-重心选址逆问题 10

3.1 问题研究 10

3.2 O(n)时间算法 10

第四章 加权哈明距离组合模下的1-重心选址逆问题 12

4.1 问题研究 12

4.2 O(n)时间算法 16

第五章 模下添加约束条件的树上1-重心选址逆问题 18

5.1 添加模下的约束条件的树上1-重心选址逆问题 18

5.2 添加瓶颈型哈明距离下的约束条件的树上1-重心选址逆问题 19

5.3 添加组合模下的约束条件的树上1-重心选址逆问题 20

第六章 总结与展望 22

致谢 23

参考文献 24

介绍

文献综述

设施选址问题属于运筹学的基本模型，它们在实践和理论上的重要应用一直受到广泛的关注。这些问题要求确定在系统上建立一个或多个设施的最佳位置，以便尽可能以最好的方式为现有客户提供服务。选址问题所涉及到的研究内容十分广泛，从城市、产业带、经济技术开发区、跨国经济集团分公司到机场、水利设施、人类居住区、销售网点以及仓库、配送中心等的区位决策都是选址问题研究的范畴，涉及经济、政治、社会、管理、心理及工程地质等多门学科。

设施选址是众多选址问题的一个重要研究领域。所研究的设施是指与生产、商业流通及人类生活有关的用地规模相对较小的具体网点、场所，例如工厂、仓库、消防站、变电站、污水处理中心，加油(气)站等设施。研究方法主要依靠运筹学、拓扑学、管理学等计量方法，这是设施选址与其他选址问题的重要区别。

设施选址问题可以追溯到1909年，由Weber首先提出并研究，他研究了在平面上确定一个仓库的位置使得仓库与多个顾客之间的总距离最小的问题（称为韦伯问题） ，正式开始了选址理论的研究。

剩余内容已隐藏，请支付后下载全文，论文总字数：20251字