（运筹学与控制论专业论文）基于网络选址问题的对策、决策模型的算法研究.pdf

基于网络选址问题的对策、决策模型的算法研究 摘要 选址问题是组合优化理论中一个有意义的、重要的研究领域。本文讨 论两种基于选址问题的对策、决策模型：k 一控制集对策模型和设施选址决策 模型。 对于七一控制集对策，我们着重研究了两种k 一控制集对策模型，讨论了 它们的关系，并给出了有关核心的非空性证明，主要结果有 给出了两种t 一控制集对策模型，讨论了两种k 一控制集对策核心的 内在联系，证明了在一类特殊网络上它们的核心一定非空，以及构 造核心元素的多项式时间算法。 对于设施选址决策模型，我们推广了现有的模型，研究了在多数原则 下决策解的性质和有关算法问题，主要结果有 给出了决策解的定义，特别对于树型网络，我们给出了寻找该决策 模型中的决策解的快速算法。 讨论了一般网络图上决策模型中的决策解存在的计算复杂性，以及 设施数目被看作问题的输入规模时决策解存在的计算复杂性。 关键词：控制集对策；核心；决策解：多项式时间算法；咿困难 o nt h ea i g o t i t h m i co o m p i e x i t yo fg a m ea n dd e c is i o f t i a k i n gm o d e i sa r is i n gf r o mn e t w o r kl o c a t i o np r o b l e m s a b s t r a c t l o c a t i o nt h e o r yi sas i g n i f i c a n tf i e l di nc o m b i n a t o r i a lo p t i m i z a t i o n 血t h i s t h e s i s w cc o n s i d e rt w oc l a s s e so fl o c a t i o nm o d e l sa r i s i n gf r o ml o c a t i o np r o b l e m s ： k - d o m i n a t i n gs e tg a m ea n d d e c i s i o nm a k i n gm o d e lu n d e rt h em a j o r i t yr u l e f o rt h ek - d o m i n a t i n gs e tg a m e ，w ei n v e s t i g a mt w ok - d o m i n a t i n gs e tg a m e m o d e l s ，d i s c u s st h er e l a t i o n s h i pb e t w e e n b o t hg a m e sa n dt h eb a l u n c e d n e s so f t h e m ，a n do b t a i nt h ef o l l o w i n gm a i nr e s u l t s w bi n t r o d u c et w ok - d o m i m t i n gs e tg a m em o d e l s ，a n dd i s c u s st h e r e l a t i o n s h i pb e t w e e n t h e i rc o t e s ；s h o wt h a tt h eb a l a n c o d n e s so fb o t h g a m e so nas p e c i a ln e t w o r k , w ep r e s e n tp o l y n o m i a ll i m ea t g o r i t h m f o r c o m p u t i n g a l le l e m e n to fc o l e f o rd e c i s i o nm a k i n gm o d e l s ，w es t u d ) t h ec o m p l e x i t yp r o b l e m so fd e c i s i o n s o l u t i o nu n d e rt h em a j o r i t yr u l e ，a n do b t a i nt h ef o l l o w i n gm a i nr e s t f l t s w e g i v et h ed e t - m i t i o no f d e c i s i o ns o l u t i o n p r e s e n taf a s ta l g o r i t h mf o r c o m p u t i n gad e c i s i o ns o l u t i o nf o rt r e en e t w o r k f o rt h ee x i s t e n c eo fd e c i s i o ns o l u t i o no ng e n e r a n e t w o r ka n dt h e n u m b e ro ff a c i l i t yt ob el o c a t e di sc o n s i d e r e d 勰t h ei n p u ts i z e w e d i s c u s sc o m p l e x i t yi s s u e sf o rc o m p u t i n gad e c i s i o ns o l u t i o n k e yw o r d s ；d o m i n a t i n g s e tg a m e ；c o r e ；d e c i s i o ns o i n t i o n tp o l y n o m i a ll i m e a l g o r i t h m ；, n p - h a r d 基于同络选址同题的对策、决策 奠型的算法研究 第一章综述 1 1 选址问题的背景 选址问题，是指在一定区域内选择一个或几个服务设施的建设位置，使得在 满足一定条件下，达到最优的目标。这类问题，在规划建设中经常可以碰到，这 里所谓服务设施，可以是某些公共服务设施，如医院、消防站等。也可以是生产 服务设施，如仓库，转运站等等。而区域则可以通过网络形式来表示服务设施所 服务的范围及其关联关系。可以认为，选址问题，就是把服务设施与服务对象， 反映于统一的网络中，以便用网络的关系进行研究。尽管对选址的目标、要求有 不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到、节省 费用则是共同的。 从不同的角度出发可得不同的选址模型。比如可按建设服务设施数目的多少 来分类；按服务设施的性质来分类，比方说它们是固定的还是移动的；按选择的 离散程度来分有连续选址模型和离散选址模型；还可按决策是按“领导拍板原则” ( 一个人来决策) 还是多数原则来分类；还可按投资者与受益者是否一致来分类； 公共设施的容量( 吞吐能力) 是有限制还是无限制来分类等等。选址问题就是按 某一既定的标准来选符合这一标准的最优解决方案。 ， 在网络选址模型中，我们通常考查树形网络和一般网络上建立的模型。任意 两个顶点之间有且仅有一条路的简单图称为树，即树是不含圈的连通图。人们关 注于树型网络上的选址问题主要出于以下两个方面的原因：首先，许多现实生活 中的问题都可以用树型网络来描述。例如，把联结某些地区的高速公路看成边， 地区看成节点，则可以用树来描述这些地区之间最简单的联结关系。又如在某些 城市之问建立通信线路，而最基本的要求就是保证各城市之间的联通性，这样的 联结关系也可以用树来描述。其次，树是最简单的一种网络构型，由此可以引出 在一般网络上相应问题的研究方法。因此，树形网络往往是人们研究的出发点。 从安排设施的管理者角度来看，他需要一个最优的方案。例如在满足消费者 的要求下使建造设施的总费用最小。这就自然地提出了一个问题：如何在各个消 费者之间合理地分配总费用，即费用的分摊问题。比如一个城镇要建造图书馆、 基于网络选址问题的对策，决策模型的算法研究 体育馆，使各小区的居民可以得到更好的服务，当然他们就必须为这样的服务来 支付费用。如何将总的建设费用分配给消费者，这就是合作对策理论要解决的闯 题。 另一方面，如果设施的地址由多个消费者通过投票来选择，这就是一个决策 模型。在决策模型中每个消费者都希望所建立的服务设施最好地为自己服务，并 支付最少的花费，这就必然导致不同的决策机制。例如可以按照多数原则来进行 决策，也可以按照排序、打分等原则进行决策。 本论文将针对若干由网络选址问题引出的对策和决策模型进行讨论，并将研 究的重心放在模型的求解算法和计算复杂性上。 1 2 计算复杂性理论 在解决最优化问题时，算法的有效性往往是我们首要关心的问题。所谓有效 算法，或称多项式算法，是指其基本运算步数由输入规模的多项式所界定的算法。 例如，解线性规划问题的椭球算法，解指派问题的匈牙利方法等都是有效算法。 然而，还有许多优化问题，如货郎担问题，顶点覆盖问题和可适定性问题等，它 们的算法设计如此之难，以至于人们无法知道是否存在有效算法。为此，c o o k e 8 和k a r p 9 在七十年代初提出了n p 完备性理论，将这些有效算法的存在性难题 统一成一个深刻的数学猜想。 考虑最优化问题的判定形式一判定问题，即答案为“是”或“否”的问题我 们用尸表示用多项式时间算法所能解决的判定阿题，即尸是相对容易的判定向题 类。n p 则是一类更广泛的判定问题类。称判定问题a 是 p 类的，如果工是问题 a 的答案为“是”的实例，则存在对工的一个简短( 即其长度以j 的长度的多 项式为界) 证明，使得能在多项式时间内检验这个证明的真实性。显然， 尹包 含只而且还包含人们所关心的许多困难问题，如上面提到的货郎担问题，适定 性问题和顶点覆盖问题等。人们普遍认为尸是胗的真子集，但至今无人能够证 明。p n p 被认为是当今数学和计算机科学中最重要的猜想之一。 k a r p 在1 9 7 2 年首先提出了如下n p 一完备问题的定义。判定问题a 多项式变 2 基于网络选址问题的对策、决策 莫型的算法研究 换到另一个判定问题暑，如果给定a 的任意实例工，在多项式时间内能构造出占 的一个实例y ，使得x 是a 的“是”实例当且仅当y 是口的是实例。一个判 定问题a 尸称为n p 完备的，如果所有其他的 p 问题都能多项式地变换到a 。 也就是说，如果问题a 是n p 完备的，那么它具有很强盼眭质：若a 有有效算法， 则每个 p 问题也有有效算法。n p 完备问题的存在性由c o o k 8 首先得到，他 证明了第一个n p 完备问题一适定性问题。 n p 完备问题概念的实际意义就在于人们普遍相信，正确求解n p 完备问题的 任何算法，在最好的情况下也需要指数量级的基本运算步数，从而除规模很小的 实例外，是不实用的。“难计算”是这些问题的固有性质。还有一些问题，虽 然不属于 b 但我们可以证明它们至少与任意的n p 完备问题同样困难，因此很 可能是难解决的，我们把它们称为n p - 难的。将问题按其算法复杂性进行分类： 只n p 完备或者n p 一困难等，是最优化问题研究的一个重要方面。 在面对一个新的组合优化问题时，人们总设法给出一些求解这个问题的充分 ，必要条件。如果所给的充分必要条件可在多项式时间内得到验证，那么常常由此 构造出解决该问题的有效算法。但是对于许多问题，人们无法找到这种可在多项 式时间内验证的充要条件，这时n p 完备性或者n p 一困难性的证明便可使人们相信 该问题不可能有有效算法求解。在这种情况下，人们会转而寻求其他解决闯题的 方法，比如对一些特殊情形给出有效算法，或设计近似算法等。总之，算法复杂 性分析可以帮助人们选择适当的解决问题的途径。 刍c o o k 8 和k a r l 9 提出 n p 完备性概念以来，这一理论得到了迅速的发展。g a r e y 和j o h n s o n 在他们的 书 z o 中列举了几百个n p 完备问题，其中包括图论，数学规划，逻辑，数论等 学科中的问题。 近年来，在对策、决策模型的研究中，d e n g 和p a p a d i m i t r i o u 2 5 提出 将计算复杂性作为评价和衡量解的合理性的一种尺度，这是因为局中人或决策人 在寻求决策方案时，不愿意也不可能花费指数次长度的时间。本文将从算法和复 杂性角度讨论基于网络选址问题的对策、决策模型。 基于网络选址问题的对繁，决策漠型的算法研究 1 3 基于网络选址问题的控制集合作对策模型 。1 3 1 合作对策的基本概念 设n = f 1 ，2 ，1 ) 是局中人集合，v ：2 ”斗r 满足 v ( 扔= o ，y ( ) v ( t i d 。 i = l 称r ：( ，r ) 为弹人合作对策。v 称为r 特征函数。对于任意子集s e n ，称之为 一个联盟，特征函数值v ( s ) 表示在无其它局中人帮助的情况下，子联盟s 作为合 作整体可得到的最大利益或最小费用。以下我们假设所考虑的对策r 均满足旁支 付( s i d ep a y m e n t ) 条件，即每个联盟获得的收益可按任意方式分配给该联盟的成 员。当特征函数v 表示利益时，我们称相应的对策为收益对策，而当特征函数v 表 示费用时，我们称相应的对策为费用对策。这里我们对费用对策给出相应的定义， 收益对策的相关定义可类似给出。 在对策r 中，给定一个矗维向量工= 玉屯，) ，如果它满足 1 。而= v ( ) ， 2 v i n ，均有五sv ( f ) 则称工为对策r 一个分配( i m p u t a t i o n ) 。对于总费用v ( n ) 分配的不同的公平合 理性要求，对应着不同的对策解的概念。例如，核心( c o r e ) 1 l 】，核子( n u c l e o l u s ) 1 2 ，1 3 ，1 4 ，核( k 咖e 1 ) 1 5 ，1 6 ，1 7 】和s h a p l e y 值 1 8 ，1 9 等等。其中核心是最 重要的对策解的概念。 核心的概念是在子联盟的合理性的基础上引入的。给定对策r = ( ，y ) ， 其核心定义为 c ( r ) = 扛r ：工( ) = v ( ) 且毒( s ) “s ) ，v s n j 这里我们记盖( s ) = 。而即对核心中的一个分配来说，如果局中人的任何子 联盟从整体联盟中分离出来进行合作，都不会得到更好的利益。着对策r 的核 4 基于两碧选址问题的对策、决策虞型的算法研究 心非空，我们称之为均衡的。 s i m o n 在【2 2 】中对分配提出了类在实际应用中非常重要的合理性要求 “限定合理性”( b o u n d e dr a t i o n a l i t y ) ，即局中人不能无限制的花费资源来获 得。最优”的收益分配。而计算复杂性作为一类重要的“限定合理性”，首先由 p a p a d i m i t r i o u 和y a n n a k a k i s 【2 3 】提出，他们将是否存在多项式算法及计算复杂 性作为衡量对策解的合理性的一个尺度。在这方面，有许多早期的工作。m e g i d d o 首先明确提出了用多项式算法来求对策的解【2 4 】。d e n g 和p a p a d i m i 砸o u 则讨论 了一个具体对策模型的各种解的计算复杂性【2 5 】。 对于一个合作对策模型的核心，从算法和计算复杂性角度人们主要关注以下 几个问题 1 非空性( 均衡性) 地判定：给定某个对策模型，能否在多项式时间 内判定其核心的非空性? 2 核心元素的判定：给定某个对策模型和它的一个分配，能否在多项 式时间内判定该分配属于对策的核心? 3 核心元素的构造：给定某个对策模型，能否在多项式时间内构造一 个其核心中的分配? 1 3 2 基于网络选址问题的合作对策模型 在对策r ：( ，r ) 中，特征函数的定义域的规模是2 ，如果把y 明确的 表示出来，对策i _ 的输入规模是局中人个数的指数函数。这里我们讨论一类输 入规模由局中人个数的多项式所限定的对策模型：组合优化对策。其特点是 1 局中人个数j j 有限； 2 任给联盟s ，v ( s ) 是s 在所掌握的资源限制下某组合优化问题的 最优值，而该优化问题的输入规模由局中人个数l 的多项式所限定。 这里，求解v ( s ) 可能不存在多项式算法，其复杂性取决于该组合优化问题本身 的复杂性。近来，许多基于组合优化问题的对策模型得到了深入的研究。如 基于网络选址问题的对策、挟第 莫型的算法研究 t a m i r 3 ，g o e 蝴s 和s k u t e l l a 4 研究了设施选址对策模型；d e n g 5 等人提 出了一类建立在图上的填装覆盖对策模型；y e l z e n 6 研究了由图的控制集问 题引出的控制集对策模型。 一般的设施选址对策 ， 在设施选址问题中，设是消费者集合，需要服务设施提供服务，比如在 社区中建火车站、体育馆、图书馆、超市等。设f 是可能的设旖选址集合。对于 每个可能建设旎的地点都有建设费用，而对每个消费者他达到某个设施地点也需 要相应的连接费用。我们考虑在设施的建立能够确保每个消费者得到服务的前提 下，使得总的连接费用和建设费用最小。在许多选址模型中，往往还带有其它限 制。如服务设施只能为有限数目的消费者服务，比方说设施i 只能最多为k 。个消 费者服务。某些设施不能为某些消费者服务，比如说它们之间的距离太远。当消 费者情况比较特殊时也会导致带有约束条件，比如说至少要有4 0 的女消费者在 里面，或者消费者需要设施提供多种服务而一个设旌只能提供一种服务的情况。 在网络上的设施选址问题可以简化地描述如下：设g = ( y ，毋是一个无向 图，其中y 是顶点集合，e 是边集合。帆，y v ，d ( x ，y ) 表示工与y 之间的最 短路。d ； p l ，p 1 y 表示消费者集合，c = 乱，g 。 v 表示建造服务 设施的候选地址集合，( 0 1 0 表示在鼋，建造一个服务设施需要的花费 ( j = l ，是) 。消费者热需要在距离自己0 的范围内才能够接受服务 ( i = l ，m ) 。 假定每个消费者都能够接受服务，网络选址问题就是找一个费用最小的建造 服务设施方案使每一个消费者都能接受服务。在此优化问题的基础上，我们定义 设施选址对策r g = ( d ，v ) ，其中d 为消费者集合。v s d ，v ( s ) 表示满足给s 中 的消费者提供服务而建造服务设旋的最小花费。我们可以用整数线性规划来表示 v ( s ) ，即 6 基于网络选址问题的对策、决策模型的算j 圭研究 t y ( s ) = m i n e s j y j i = i 8 j 1 y ，i i ，s ：l ，七 i ( a y ) i 其中矩阵a = ( ) 定义如下 f 1 d ( p ；，q ，) 扛1 ，m ，= l ，k a u2 1 0 否则 t a m i r 和g o e m a n s 研究了这类对策模型及其核心，给出了如下结论 定理1 1 跚如果g 是树形网络，则设施选址对策r o 的核心一定非空，且核心 中的元素就是下述线性规划的对偶最优解集。 t m i n 国，y a y ) l l ，扛1 ，m ；yz o i i 定理i i 说明在树形网络上对应的设施选址对策模型核心元素的构造和分配 是否归属核t l , 的判定都是多项式时间可解的。 定理1 2 对于一般图g 上定义的设施选址对策k ，核心的非空性及分配是否 归属核一t l , 的判定问题都是n p 完备的。 控制集对策 控制集问题有很强的实际背景，并在在图论中有着广泛的研究 1 2 。设 g = ( y ，e ；功是一个无向图，其中y 是顶点集合，e 是边集合，国：v 哼砖是顶 点权重函数。若顶点y 的一个子集r 满足：y 中的任何顶点至少与t 中的k 个顶 点相邻，则称r 为图g 的一个髓控制集。而顶点权重和最小k - 控制集的称为最小 控制集。 我们考虑如下实际问题。已知一些地区和这些地区之间的联结关系。人们希 望在其中一些地区建立公共设施，如公共图书馆、超市、车站等，使得每个地区 7 基于网络硅址问题的对策、决策填型的算法研究 周围至少有k 个公共设施为它服务。由于每个设施的建立均需一定费用，由此就 提出一个最优化问题：在满足上述要求的前提下，如何选择建设公共设旄地点， 使得总建设费最小。而这个同题就是地区联结图上的最小缸控制集问题。与这个 优化问题密切相关的另一个问题是：如何在得到服务的各地区之间分配总的建设 费用。这个问题可以描述成控制集合作对策模型。 ， 给定图g = ( y ，e 妫，其中y 表示图g 的顶点集合，e 表示图g 的边集合， 国：v r + ，国表示在顶点v | 建个设施的费用。我们考虑两类对策模型。在 紧县控制集对策f = ( v ，d 中，y 表示局中人集合，既是消费者集合又是可能建 造服务设施的集合。v ( s ) 表示只能在导出子图g s 1 上选择可能建造服务设旖的 地点以使联盟s 中的消费者得到相应的服务的最小费用，即g s 】上的最小七- 控 制集的权重。在松砖隆制集对策f = ( v ，爷) 中，y 表示局中人集合，哥( s ) 表示在 整个图g 所有的顶点上选择可能建造服务设旋的地点，使得联盟s 中的消费者得 到相应的服务的最小费用，即5 中的项点可以被七控制的整个联盟的最小费用。 当= l 时的对策模型为控制集对策模型。v e l z e n 6 研究了紧的和松的控制 集对策及它们的核心非空性：当且仅当控制集问题的整数规划模型的线性规划松 弛有整数最优解时，这两种对策的核心非空。 定理1 3 吲给定图g 和相应的松、紧控制集对策，则以下命题等价 ( 1 ) 控制集f 句题的整数规划模型的线性规划松弛有整数最优解； ( 2 ) 紧控制集对策是均衡的； ( 3 ) 松控制集对策是均衡的。 我们在v e l z e n t 作的基础上提出了“腔制集对策，是对v e l z e n 的模型的推 广。由于v e l z e n 的证明方法在推广的女控制集对策模型中不再适用，我们在对策 核心的非空性讨论中给出了新的证明方法。得到的主要结果有 核心的非空性证明 s 基于网络选j 七问题的对策、决策漠型的算法研究 核心元素构造的多项式时间算法 1 4 一类基于网络选址问题的决策模型 对于公共设旄的选址问题，d e m a n g e 2 1 1 建立了一些连续和离散的网络模 型，并在公共选举机制上研究了决策解的存在性和性质。d e m a n g e 的离散网络 模型可以描述如下：给定一个网络g = ( ( y ，功，( e ，z ) ) ，其中每个顶点f v 代表一 个社区，m ( o 代表社区i 的人数。每条边p = ( f ，d e 代表连接社区i 和，之间有 联系，旦，( p ) 0 表示它们之间的距离。要在这些社区中间建一些公共服务设旅 如图书馆，体育馆等，而每个社区的居民当然希望服务设施离自己越近越好，因 此我们要考虑的决策机制是通过选举来确定建造服务设施的地址。并且决策过程 遵循多数原则，即同意这一选举方案的人数至少应占总选举人数的一半。 d e n g 2 6 , t i ：) t ：究了离散的d e m a n g e 网络模型给出了相应的决策解的定义，并 得到有关对策解求解的算法和计算复杂性结果。 设图g = ( y ，司的顶点集f f ：为v = v l ，v ，给定一个顶点y 。v ，则由吨 导出了顶点集合中所有顶点的一个偏序关系，任意给工，y v ，膏乏y 当且仅当 如( u ，石) s d a ( 唯，y ) ，其中d g ( q ，曲表示顶点h 和工之间的最短距离 c o n d o r c e t 决策解的定义：给一个图g - - ( v ，刃和v 上的一个偏序关系 ( ) 。，一个顶点v o v 称作： ( 1 ) 弱伪c o n d o r c e t 决策解，如果对任意的顶点v ，“v o ，有 毗批啦川) 竿，i e 她m 峨y o ) 竿 ( 2 ) 强伪c o n d o r c e t 决策解，如果对任意的顶点“v ，“v o ，有 吡幽v 口- , u d 竿，i e a g v , m 峨删 l 球 ) 珊( ( v j v ：距 iv o ) ( 4 ) 强c o n d o r c e t 决策解，如果对任意的顶点h e y ，m v o ，有 棚( ( v y ：v o 球 ) 国( ( v ；v ：“ lv o ) 定理i 4 ”6 每个树型网络中都有一个弱伪c o n d o r c e t 决策解，或者两个 相邻的弱伪c o n d o r c e t 决策解。我们可以在线性时间内找到。 而对一般网络图g 的决策模型有如下结论 定理1 5 ”日给定一般网络图g ，并设设施个数为| i ( 常数) ，c o n d o r c e t 决 策解可以在多项式时间内找到。 定理1 6 2 6 1给定一般网络图g ，若公共设旄的数目k 被看作问题的一部 分，c o n d o r c e t 决策解的求解是n p 一妇r d 的；与之相关的问题：判定一个候选 方案是否是一个c o n d o r c e t 决策解是c 口一n p 一完备的 在第三章中，我们考查一个推广的d e m a n g o 的离散网络模型：在上述 d e m a n g e 网络模型基础上在每个社区f y 上加一个正的赋权z ( 0 ，代表在社区f 建造一个公共服务设施的人均建造费用，且用，( 力 0 , e = ( f ，j 3 表示连接社区i 和 ，的路费。在此模型下我们给出决策解的定义，并讨论了相关的算法和计算复杂 性问题。主要结果有 树型网络上的c o n d o r c e t 决策解的算法； 一般网络上的c o n d o r c e t 决策解的算法复杂性。 l o 基于网络选址问题的对策、决策漠型昀算击研究 第二章卜控制集对策 本章考虑两类从图的一控制集问题引出的合作对策模型，并着重讨论它们 的核心。我们首先给出了两类对策模型的定义及他们核心之间的关系，其次利用 整数线性规划和线性规划对偶理论讨论了其核心的非空性。 ， 七- 控制集问题有着很强的实际背景，并得到了广泛的研究 1 2 。我们考虑 如下实际问题。已知一些地区和这些地区之间的联结关系。人们希望在其中一些 地区建立公共设旖，如公共图书馆超市、车站等，使得每个地区周围至少有k 个公共设旖为它服务。由于每个设簏的建立均需一定费用，由此就提出一个最优 化闯题：在满足上述要求的前提下，如何选择建设公共设施地点，使得总建设费 最小。而这个问题就是地区联结图上的最小b 控制集问题。 与这个优化问题密切相关的另一个问题是：如何在得到服务的各地区之间分 配总的建设费用。本文将利用合作对策理论来讨论这个分配问题。我们引入两类 相关的合作对策模型：紧岳控制集对策和松七- 控制集对策，并讨论它们核心之间 的关系和非空性。 我们在v e l z e n t 作的基础上提出了“控制集对策，是对v e l z e n 的模型的推 广。由于v e l z e n 的证明方法在推广的七_ 控制集对策模型中不再适用，我们在对策 核心的非空性讨论中给出了新的证明方法。 2 1 卜控制集对策模型 设g = ( v ，西是一个无向图，其中y 是顶点集合，e 是边集合。对于不同的 顶点，y e v ，若有( ，层，则称它们是邻接的。对于非空子集v c _ v ，v 的导出 子图是以y 作为顶点集，以两个端点均在v 中的边的全体为边集的子图，记作 g 】。任给v v ，其闭邻域定义为l v v = i “v ：l f l ，e u v 。 对于给定的图g = ( y ，d 和正整数t ，若顶点子集t s y 满足v ，v ，均有 基于网络选址同琶的对策、决策模型的算法研究 l n v n t i i 成立，则称r 为图g 的一个t - 控制集。t 控制集闻题是寻找一个顶 点个数最少的缸控制集，即最小b 控制集。我们把最小b 控制集中的顶点个数称 为图g 的缸控制数，记作以( g ) 。本文我们假定所讨论的图中均存在矗控制集。 以下我们引入两类b 控制集对策。给定图g = ( v ，d ，则相应的紧缸控制集 对策r = ( v ，v ) 定义为 1 ) 局中人集合为图g 的顶点集合y 2 ) v s y ， v 岱) = j 以( g f j 】) 若g s 】有k 一控制集 i + 否则 在紧缸控制集对策中，任何联盟s 只能用自己对应的顶点来达到控制自己的 要求。如果我们去掉这一限制就得到了另一类b 控制集对策：松加陉制集对策。 对于顶点子集s y ，t m _ v ，若它们满足：v v s ，均有i m n r 眨t ，则称子 集r 可以七_ 控制子集s 。给定图g = ( y ，d ，则相应的松七控制集对策r = ( y ，亭) 定义为 1 ) 局中人集合为图g 的顶点集合y 2 ) v s 量v ，移( s ) = m i n y k ( g t ) i t 可以k 一控制s ，ts v l 显然，对于却岱匕v ，石( s ) “s ) ；而对整个联盟y ，1 ，( y ) = 石( y ) = y k ( g ) 。 因此，由核心的定义可知 c ( r ) c ( r ) 。 ( 1 ) 我们看下面的例子，如图所示，取七= 2 。考虑两类七控制集对策。 c - ) _ o l 2 3 基于网络选址问题的对簟、决策模型的算法研究 易见，鹕= 哟= 哟= 呦= 悯地乃= “z 3 = zk 1 , 2 , 3 ) = 3 ，而 哥( 1 ) = 哥( 2 ) = 哥( 3 ) = 爷( 1 2 ) = 哥( 2 ，3 ) = 2 ，看( 1 3 = 爷( 1 2 ，3 ) = 3 。 在下面的定理2 2 中，我们将给出这两类矗控制集对策核心之间的进一步 关系。 引理2 1给定图g = ( v ，曰，设f = ( y ，歹) 为相应的松七- 控制集对策。则 垤旭( 两，均有工o 。 证明由哥的定义可知，v s c _ t c v ，有哥( s ) 石( r ) 。则对任意的工c o r e ( f ) ， 而= # ( d 一_ ；( ”一哥( y 、m ) 2 0 ，即石o 。证毕。 定理2 2 给定图g = ( y ，奶，设 = ( y ，爷) 和r = ( y ，叻分别为相应的松七- 控制集 对策和紧七- 控制集对策，则有它们核心之间的如下关系 c c h = c ( d f i r ：。 ( 2 ) 证明v x c ( 而，由引理2 1 知工o ，且由( 1 ) 式可得c ( 两c _ c ( r ) f l r ： 另一方面，v x c ( d n 硝，有颤y ) = 芗( ”= p ( y ) ；且c v ，若蚕盯) 。k ” ( 3 ) 我们把整数条件限制去掉，得到线性规划松弛( l p ) 和它的对t s ( d l p ) ： r a i n ” ( l p )s t a y k 1 0 o 是松的，。则原始条件y ，= l 必是紧的，y ，= l o 是松的，则必有相应的对 偶条件( z a ) ，一；= l 成立。证毕。 引理2 9 设( z ，“) 为( d l p ) ( 5 ) 的一个最优解，若z o ，则有 基于网络选址问题的对肇、决策摸型的算法研究 k l ( j l a o | o 证明假设存在z ： o ，有女 o ) 叶2 k 否则 令岛 o 足够小，使得乏o ，蠡o ，易验证( 三，五) 是( d l p ) ( 5 ) 的一个可行解t 且 ( j ，互) 目标函数值 砭一蟊；z kz ：- k s , 一。：+ i ，i 盯一o k i ( ) j di = id1 i 与( z ，) 最优性矛盾。证毕。 下面我们来证明定理2 7 ： 设( z ，“) 为( d l p ) ( 5 ) 的一个最优解，则 圪( g ) = 孑( y ) = t z ；- z “； 记，= j l u ： o ，则由引理7 知v j e r ，( z a ) ，一“；= l 令 ，= f i y l e 与j 中的点均不邻接或者= o 且j = v 、， 构造凡维向量工= ( ，屯，工) 仁删眦喘i 川e 1 其中，n 【f 】为对应； o 的那些约束中吩取1 的那些指标集，由前面的引理2 8 知这些约束条件必取等号。下证工c ( 西。 ( 1 ) 由引理2 9 可知，k _ - l ( j l a 俨； o l ，故工o 。 ( 2 ) 其次e x ( v ) = 石( y ) 。因为 基于网络选址问题的对策、决策漠型的算法研究 帮) = 砑+ 碍一 ldd1 = 碍- x ( i - - i i ot t 吼i 、 ( i - ，n 【8 1 ) z ：一洲i j i 】= 喜磁弓( 帅研司d z 一硎i j i ( 3 ) 最后b t x ( s ) 爷( 5 ) v s c 。因为 删2 萋昏磊z ：一* 2 善k ：京 ” n rl “ k z 卜1 ，n 【1 1 k ：+ l j i j u i “1 ， 另一方面，石( s ) 是下述整数线性规划的最优目标函数值 舌( s ) = m i n y ， c 邸，s t 鼢荨涎s 考查它的( l p ) 松弛和它的对偶( d l p ) c s t 般兰涎了 ( d l p ( s ) ) s t n 因为a 是均衡矩阵，我们有a p t ( z l p ( s 9 = a p t ( l p ( s ) ) = o p t ( d l p ( s ) ) = 哥( d 。我们 将利用( d l p ) ( 5 ) 的最优解( z + ，“) 构造( d l p ( s ) ) 的一个可行解( 乏，i ) 。令 )彤 v = 斛 一 碍 。试 = d 一 晋 巧 m mm j d d 芦 吁加呜舷 基于同络选址问题的对策、决策模型的算法研究 f ，+ f s 磊2 i o f 星s f “：i _ ， ，2 酬胂 【0j 鹰j 则：a ) 易证三o ，孑o ，且( 芝，孑) 是( d l p ( s ) ) 的可行解。 b ) ( 三，茁) 的目标函数值为 舌( s ) = 砭一磊，= tz 卜( 一z ：) = kz 【( z a ) ，- 1 一z j t j ，- l i e j ，t j培l i e $ ，t l 【 = tz ? 一( z 卜1 ) = kz 卜t j n i v f l tz ? + i ，眨颤s ) i e $ i di “b i v j t s l t s n l 上面最后一个不等式是根据( 6 ) 式得到的，从而x ( s ) 哥( s ) ，综合( 1 ) 工2 ) ，( 3 ) 可知， 松缸控制集对策于：，) 的核心非空。证毕。 推论2 1 0 给定图g = ( y ，d ，设g 的闭邻域矩阵a 是均衡的，则相应的紧七- 控 制集对策f = ( n v ) 的核心非空。 定理2 1 1 对于松、紧矗控制集对策，我们可以在多项式时间内构造出核心元素 注：当图g 是一般图时，当露= 1 时，已经证明找最小权重控制集是n p 困难的 2 0 。我们猜测对任意的正整数k ，判定线性规划( 4 ) 是否有整数最优解，即 判定两种七- 控制集对策的核心非空性是n p 困难的。另一方面，当核心非空时， v e l z e n 的结论说明核心是由线性规划( l p l ) 的对偶规划的最优解集得到。 但当k 2 ，对于七- 控制集对策并不是所有的核心元素都能由对偶最优解得到。 因此，我们猜测判定一个给定的分配是否属于核心是n p 一困难的。 基于阿络选址问题的对策、决策漠型的算岳研窀 第三章一类基于网络选址问题的决策模型的算法研究 对于公共设施的选址问题，d e m a n g e 【3 0 】建立了一些连续和离散的网络模 型，并在公共选举机制上研究了决策解的存在性和性质。d e m a n g e 的离散网络 模型可以描述如下：给定一个网络g = ( ( y ，功，( e ，d ) ，其中每个顶点f y 代表一 个社区，以力代表社区f 的人数。每条边p = ( f ，d e 代表连接社区i 和，之间有 联系，且l ( e ) 0 表示它们之间的距离。要在这些社区中间建一些公共服务设施 如图书馆，体育馆等，而每个社区的居民当然希望服务设施离自己越近越好，因 此我们要考虑的决策机制是通过选举来确定建造服务设施的地址。并且决策过程 遵循多数原则，即同意这一选举方案的人数至少应占总人数的一半。 在这一章中，我们考查一个推广的d e m e m g e 的离散网络模型：在上述 d e m a n g e 网络模型基础上在每个社区f v 上加个正的赋权兄( 0 ，代表在社区i 建造一个公共服务设施的人均建造费用，且用，( 力 0 , e = 以办表示连接社区i 和 ，的路费。在此模型下我们给出决策解的定义，并讨论了相关的算法和计算复杂 性问题。 3 1c o n d o r c e t 决策解的定义 设g = ( v ，司是一个无向图，其中y 是顶点集合，e 是边集合。g 的顶点数 为n ，每个顶点都有两个正的赋权国，a 。其中叫v 。) 0 表示顶点h 的人数， 旯( y ；) o 表示在顶点y l 建造一个公共服务设施的人均建造费用。而边权，( 力 0 ( p = ( u ，”j ) e ) 可表示连接顶点屹和0 的路费我们定义d g ( “，力是连接图g 中如v 两点的最小费用。对任意的顶点集合r _ c v ，我们记烈r ) = ，。c o ( v ) 。特 2 1 基于网络选址问题的对策、决策摸型的算法研究 别地，当r = v 时，我们用烈g ) 代替以y ) 。若顶点y 在图g 中只有一个邻接点， 我们称顶点y 为悬挂点。 设图g = ( y ，d 的顶点集合为y = v 。，v ：，p 。 ，给定一个顶点吃v ，则由n 导出了顶点集合中所有顶点的一个偏序关系，任意给x , y v ，莘 fy 当且仅当 d g ( v t , x ) + 五( d g ( v i ，y ) + 旯( y ) 。 定义1 ：给一个图g - - - ( v ，毋和y 上的一个偏序关系( ) 。，一个顶点v 称作： ( 5 ) 弱伪c o n d o r c e t 决策解，如果对任意的顶点h v ，“，有 咖弘 ) 竽，i e 地m 峨) 竿 ( 6 ) 强伪c o n d o r c e t 决策解，如果对任意的顶点“v ，有 舯f y ：蝙啪 竿i e 口( v ie y ：峨蚶) 球 ) 烈【h v ：“ iy o ” ( 8 ) 强c o n d o r c e t 决策解，如果对任意的顶点“v ，“y o ，有 反 y v ：v o “1 ) 国( 1 v l v ：u fv o ) ) 例子对于完全图置：来说，烈q ) ，丘( h ) 是常值，有弱c o n d o r c e t 决策 解，因此有弱伪c o n d o r c e t 决策解，无强伪c o n d o r c e t 决策解，所 以无强c o n d o r c e t 决策解。对于完全图蜀来说，国( v t ) ，五( y i ) 是常 值，有弱伪c o n d o r c e t 决策解，弱c