二十世纪六十年代美国学者Cooper正式提出设施选址问题,该问题在区域规划、经济管理、通信、计算机科学、仓库选择和供应链管理等领域有着广泛的应用背景,如今主要应用还包括网络服务器的配置。从而,四十多年来,设施选址问题一直是组合优化领域中的热点问题之一,吸引了大批国内外运筹学、管理科学和计算机科学等领域学者的研究兴趣。最经典的设施选址问题是无容量设施选址问题,该问题是要从给定的地址集合中选择一些地址,用来建立设施来服务给定的顾客,使得所有顾客的需求都得到满足,且开设设施的开设费用(或开放费用)和服务顾客的服务费用(或连接费用,也称指派费用)之和最小。这个问题可以用一个简单的且容易分析的整数规划模型来刻画。但UFLP是NP-困难问题,研究者们只能利用一些技巧设计该问题的近似算法。设计UFLP的近似算法常用的技巧主要有三种:线性规划舍入,原始对偶和局部搜索。UFLP问题中的连接费用是指顾客和设施之间的距离。按照距离所满足的条件,无容量设施选址问题(UFLP)的研究主要有两个方面:一是距离可度量的,即距离满足非负性,对称性和三角不等式;二是距离平方度量的,即除了非负性和对称性,距离的平方根满足三角不等式。尽管UFLP结构简单,但不能直接应用于实际,为了满足不同实际问题的需要,出现了诸多该问题的变形问题,本论文主要研究随机容错设施布局问题、带惩罚风险可调的两阶段设施选址问题、平方度量的多层设施选址问题和仓储零售网络设计博弈,这几个问题都是经典的无容量设施选址问题的变形,论文所采用的方法主要是线性规划舍入。随机设施选址问题是在信息不完全或不确定条件下的UFLP问题,经典的随机设施选址问题分为两个阶段,事先给定一个设施地址的集合和一个场景的集合,每个场景由一定数量的顾客和设施地址组成,第一阶段根据潜在的顾客信息(即场景的概率信息)选择一些地址开设设施,第二阶段根据给定的一些场景发生的概率信息在每个场景中增加开设一些设施,一般地,同一设施第二阶段的开设费用会比第一阶段的开设费用略高,我们需要在两个阶段中分别选择一些地址开设设施,将每个顾客连接到第一阶段开设的设施或第二阶段顾客所属场景开设的设施上,使得总的开设费用和连接费用的期望值达到最小。而容错设施布局问题,是UFLP的又一种形式的推广。该问题中一个顾客可以有多个需求,每个地址上可以开设多个设施,目标是每个顾客的所有需求都连接到不同的开设设施上。我们综合考虑随机设施选址问题和容错设施布局问题的已有结果,研究随机容错设施布局问题,采用线性规划舍入的技巧设计近似算法,分析并证明其近似比是5。引入风险厌恶参数可得到风险可调的随机设施选址问题。该问题也分两个阶段,第一阶段先选择一些地址开设设施,第二阶段用SAA方法抽取有限个独立场景,在每个场景中再选择一些地址开设设施,每个场景中的顾客只可以与场景内的设施和第一阶段的设施相连,其中第二阶段的费用与风险厌恶参数有关。如果第二阶段允许一些顾客拒绝连接到任意的开设设施上而支付惩罚费用,就得到带惩罚的风险可调的随机设施选址问题,我们将给出该问题的数学模型,并设计基于线性规划舍入技巧的6-近似算法。多层设施选址问题中,我们研究带软容量限制的设施选址问题,每个开设设施有容量限制,但可以多次开放,同一设施所连接的顾客不能超过它的容量限制。地址位于KK个不同层,就得到KK层软容量设施选址问题,我们要决策在每一层上选择一些地址开设设施,将每个顾客连接到位于不同层上的KK个设施,并且每个设施所连接的顾客不能超过它的容量,最终使得设施的开设费用和顾客与KK层设施之间的连接费用之和最小。我们将研究平方度量的KK层软容量设施选址问题,对基于线性规划舍入技巧设计的KK层软容量设施选址问题的近似算法重新分析,并利用平方根三角不等式的条件,证明其近似比是12.2216。同时对于平方度量的KK层设施选址问题,我们将证明其线性规划舍入算法的近似比是9。仓贮网络设计问题是经典的无容量设施选址问题的又一种变形,该问题是当今市场经济下大型商品公司在营销过程中所面临的主要问题之一。我们主要研究仓贮网络设计博弈,在该问题中,给定一个包含有限个零售商的集合,每一个零售商的需求率是确定的,给定一个包含有限个仓库的集合,同时存在一个外在的供应商,问题的目标首先是从仓库集合中选择有限个开放用于存储供应商提供的商品,其次是每一个零售商都要从开放的仓库中选择唯一的仓库提供其商品,同时决策仓库和零售商之间的费用分摊策略,最终使得总的仓库营业费用、商品运输费用和两级(仓库和零售)存储费用最小。通过定义推广的距离函数,我们给出仓储网络设计博弈问题的费用分摊算法,并证明该算法产生的费用分摊函数满足交叉单调性和竞争性,同时证明算法是3近似费用补偿的。