#import "../template/template.typ":*
#import "../template/utils.typ"
= 模型的建立与求解
== 模型准备
本文从PCI冲突、PCI混淆和PCI模3干扰三方面降低不利影响，MR数作为指标，即从冲突MR数、混淆MR数和模3干扰的MR数这三个方面讨论。因此需要明确这三种情况发生的条件，冲突矩阵、混淆矩阵和干扰矩阵的概念以及其中的MR数的计算方式。

=== 发生条件
PCI冲突，主小区和其同频的邻小区之间由于被分配到了相同的PCI的情况下导致用户错误的连接。

PCI混淆，两个或多个同频小区之间由于被分配的PCI相同导致的信号连接错误，导致网络质量下降。

PCI模3干扰，同样是发生在同频的两个邻小区之间，他们接收到的信号差，在一个给定的门限范围内。

=== 明确概念
三个矩阵中的MR数：MR是一个作为衡量PCI复用后产生损失的指标。一旦两个小区之间确定，相应的MR的值不会改变。也就是说，如果两个小区满足PCI冲突的条件，那么这两个小区就会产生一定的代价——冲突MR数增加；如果两个小区满足PCI混淆的条件，那么这两个小区之间就会产生一定的代价——混淆MR数增加；如果满足PCI模3干扰的条件，那么这两个小区就会产生一定的代价——干扰MR数增加。

相应MR数增加的计算规则：若小区 $i$ 和小区 $j$ 分配的PCI相同，则冲突数增加 $a_(i j) + a_(j i)$，混淆数增加 $b_(i j) + b_(j i)$ ，若小区 $i$ 和小区 $j$ 分配的PCI模3相同，则干扰数增加 $c_(i j) + c_(j i)$ ，对应的优化小区和相关联小区之间的计算规则就是若小区$i$和小区$j$分配的PCI相同，则冲突数增加 $d_(i j) + d_(j i)$ ，混淆数增加 $e_(i j) + e_(j i)$ ，若小区 $i$ 和小区 $j$ 分配的PCI模3相同，则干扰数增加 $f_(i j) + f_(j i) $。

== 问题一模型的建立与求解
=== 数据处理
#img(
  image("../figures/fig1.png", width:85%), caption: "问题一的数据处理示意图"
  )<fig1>

在构建冲突矩阵A的时候，需要筛选出2067个优化小区，因此需要对附件1表格中的小区进行筛选。同时，由于在第一问中仅考虑这2067个的PCI分配，不考虑主控小区在外部，或对应邻小区在外部的情况，因此需要对附件2和附件3的数据进行清洗，仅保留这2067个小区之间的冲突、混淆和干扰的情况。接着依次将对应的MR数填入三个矩阵中，构造出冲突矩阵A、混淆矩阵B、干扰矩阵C。

这2067个小区之间的冲突矩阵部分如下图（完整表格见支撑材料）：


#tbl(
  table(
    columns:((1fr,)*10),
    align: center+horizon,
    [#h(1em)],..range(1,9).map(str),[$...$],
    ..(1,0,85594,21328,1109,109,102,0,0).map(str),table.cell(rowspan: 8)[$...$],
    ..(2,106137,0,24365,3100,1043,296,0,0).map(str),
    ..(3,10363,75422,0,8290,21,51,0,0).map(str),
    ..(4,6,8292,17734,0,65895,141985,0,0).map(str),
    ..(5,369,8138,0,88787,0,85208,1282,8).map(str),
    ..(6,0,69,0,77623,75856,0,11,0).map(str),
    [7],..((0,0)*2).map(str),..(3169,0,0,47693).map(str),
    [8],..((0,0)*2).map(str),..(425,0,57757,0).map(str),
    [...],table.cell(colspan: 8)[$......$],[0]
  ),
  caption: [2067个小区之间的冲突A矩阵]
)<tab1>

#indent 该2067×2067的矩阵中的序号对应的是附件一筛选后的优化小区按照升序排列的顺序标号，因此在后续分配PCI时该索引还需要对照优化小区信息按顺序找出对应小区编号。

用同样的方法构造出混淆矩阵B：

#tbl(
  table(
    columns:((1fr,)*10),
    align: center+horizon,
    [#h(1em)],..range(1,9).map(str),[$...$],
    ..(1,0,67265,16414,3105,803,271,0,0).map(str),table.cell(rowspan: 8)[$...$],
    ..(2,0,0,43523,35824,13458,4318,12,1).map(str),
    ..(3,0,0,0,36555,106,2703,11,8).map(str),
    [4],..((0,0)*2).map(str),..(78644,62645,0,1).map(str),
    [5],..((0,0)*2).map(str),..(0,132045,6738,2671).map(str),
    [6],..((0,0)*3).map(str),..(51,9).map(str),
    [7],..((0,0)*3).map(str),..(0,75203).map(str),
    [8],..((0,0)*4).map(str),
    [$...$],table.cell(colspan: 8)[0],[0]
  ),
  caption: [2067个小区之间的混淆矩阵B]
)

#indent 同样的数据处理方式，将干扰MA数填入干扰矩阵C中：


#tbl(
  table(
    columns:((1fr,)*10),
    align: center+horizon,
    [#h(1em)],..range(1,9).map(str),[...],
    ..(1,0,25899,1196,31,1,1,0,0).map(str),table.cell(rowspan: 8)[...],
    ..(2,18155,0,5801,1007,835,76,0,0).map(str),
    ..(3,550,13123,0,3500,2,10,0,0).map(str),
    ..(4,0,3405,4588,0,13639,10446,0,0).map(str),
    ..(5,62,2101,0,21093,0,16772,457,1).map(str),
    ..(6,0,64,0,10042,17122,0,1,0).map(str),
    [7],..((0,)*4).map(str),..(878,0,0,3732).map(str),
    [8],..((0,)*4).map(str),..(86,0,4472,0).map(str),
    [$...$],table.cell(colspan: 8)[$...$],[0]
  ),
  caption: [2067个小区之间的干扰矩阵C]
)<tab2>


=== 蒙特卡洛模拟
1. 模型引入

#indent 为了在2067个小区之间分配1008个PCI，每个小区有且仅有一个PCI编号，那么每个小区有1008种可能，有2067个小区，则有 $1008^(2067)$ 种分配PCI的方式。由于数据量巨大，直接遍历每一种情况是不实际的。而蒙特卡洛模拟 @wx4 提供一种解决方案——即选取合理分布的随机数进行随机模拟，从而获得问题的近似解 @wx5 。它是一种随机模拟的方法，以概率和数理统计理论为基础的一种计算方法，其原理是大数定理，当样本容量足够大的时候，事件发生的频率就是它的概率。所以在可信度较高的情况下，选取一定的样本数估计出的结果便可以认为是一个满意解。本文将采用蒙特卡洛模拟的方法进行模拟。

#img(
  image("../figures/fig2.png", width: 85%),
  caption: [蒙特卡洛模拟流程图]
)<fig2>

由于每次PCI的分配是独立的，在重复多次实验后可以看成是均匀分布的，因此采用均匀分布的随机数进行模拟。

2. 可信度验证
#indent 蒙特卡洛模拟的次数越多，计算的结果将更加准确，但同时运行时间将会增加。在本问题中枚举出所有的结果是不可行的，因此需要找出一个合理可行的次数，使得近似结果更趋近于实际情况。

假设共有 $M$ 种结果，其中有 $N$ 种解是不理想的，则有 $(M-N)$ 个理想解。在进行 $lambda$ 次试验后，取到的都是非理想解的概率为 $p=(N / M)^(lambda)$ ，那么在这 $lambda$ 次试验后，至少有一组是理想解的概率为 $p=1-(N / M)^(lambda)$ 。

假设需要达到可信度为 $theta$ ，即

#equation(
  $ 1-(N / M)^(lambda)>= theta $
)

#equation(
  $ ln(1-theta)>=ln(N / M)^(lambda) $,
)

#equation(
  $ lambda>= (ln(1-theta)) / (ln(N / M)) $
)<eq1>



#indent 假设可信度为99.999%，即至少有一组理想解的概率大于等于99.999%，在理想解占比所有解的比例达到0.00001或更小的时候，次数 $lambda$ 至少要达到 $10^6$ 次。故本文采用蒙特卡洛模拟的次数为$10^6$

3. 生成1×2067的PCI分配矩阵
#indent PCI的分配因为不具某种特殊的分布，为了更加准确的反应最终的结果，本文采用均匀分布的方式生成1×2067的PCI分配矩阵，每个值的范围是[0,1007]。

根据上面对蒙特卡洛次数的分析，一共生成 次PCI分配矩阵，将每次算出的结果对应的总MR数算出来，更新最小值，便可以得到满意的解。

=== 引入0-1矩阵
为了算出总MR数，就需要知道三种情况是否发生，分别发生在哪两个小区之间。PCI的复用，会导致每两个使用相同PCI的小区产生PCI冲突、混淆，每两个小区的PCI值模3相同还会产生PCI干扰。那么需要引入两个2067×2067的0-1矩阵——矩阵 和矩阵 $x$ 。矩阵 $x$ 反应PCI冲突和PCI混淆的情况，根据二者发生的条件，相同PCI值的小区记为1，不同PCI值的小区记为0。矩阵 $y$ 反应PCI干扰的情况，根据其发生的条件，PCI模3相同的小区记为1，不同PCI值记为0。

在蒙特卡洛模拟的过程中，对于每一次求解，针对PCI冲突和PCI混淆的情况，首先在PCI分配矩阵中获取PCI值相同的小区索引号，每两个小区之间的 $x_(i j)$ 记为1，其余记为0。于是 $x*(A+B)$ 就表示了冲突MR数和混淆MR数的和。

针对PCI干扰的情况，首先现对PCI分配矩阵中的作PCImod3的运算，得到PCI模3相同的小区索引号，每两个小区之间的 $y_(i j)$ 记为1，其余都为0。于是 $y*C$ 表示了干扰MR数。


=== 模型求解

本文建立数学规划模型：

#equation(
  $ 
  min f = 
  sum_(j = 1) ^(2067)sum_(i = 1)^(2067) x_(i j) dot a_(i j) + 
  sum_(j = 1) ^(2067)sum_(i = 1)^(2067) x_(i j) dot b_(i j)+
  sum_(j = 1) ^(2067)sum_(i = 1)^(2067) y_(i j) dot c_(i j)
  $ 
)

#equation(
  $ s.t.cases(
    sum_(j = 1)^(2067) x_(i j) = 1\,#h(1em) i = 1\, 2\,3 ...\, 2067,
    0<=P C I <= 1007
  ) $ 
)

其中 $f$ 为总MR数

#equation(
  $ x_(i j) = cases(
    1 \,#h(1em) #[第 $i$ 个小区与第 $j$ 个小区的 $P C I$ 相同] ,
    0 \,#h(1em) #[else]
  ) $
)


#equation(
  $ y_(i j) = cases(
    1 \,#h(1em) #[第$i$个小区与第$j$个小区的 $P C I$ 模的值相同] ,
    0 \,#h(1em) #[else]
  ) $
)

#indent 上述目标函数可以简写为
#equation(
  $
 M = x*(A+B)+y*C 
  $
)

#indent 其中 是一个2067×2067的矩阵， $M_(i j)$ 反映了小区 $i$ 和小区 $j$ 之间的，冲突MR数、混淆MR数、干扰MR数的总和。若小区 $i$ 和小区 $j$ 分配的PCI相同，则冲突数增加 $a_(i j)+a_(j i)$ ，混淆数增加 $b_(i j) + b_(j i)$ ，若小区 $i$ 和小区 $j$ 分配的PCI模3相同，则干扰数增加 $c_(i j)+c_(j i)$ ，因此只需要将矩阵 $M$ 中每个元素相加即可得到总MR数 $f$。


通过前面介绍的蒙特卡洛的模拟方法，引入0-1矩阵，经过 次试验，比对求得最终的总MR数。经过几轮蒙特卡洛试验发现总MR数的最优值稳定在五千两百万左右，由于要让总MR数最小，取几次试验得最小值的MR总数为50899984，对应的PCI分配如下表（完整结果见计算结果文档）：



#let tab_pci = (
  735,718,494,817,647,243,182,43,956,85,79,776,616,668,
  547,78,465,841,330,536,145,310,475,257,14,317,563,537,
  238,929,689,1003,581,135,713,338,185,914,692,941,930,935,420,
  108,985,483,537
).map(str)

#tbl(
  table(
    columns: (1fr,)*4,
    align: center+horizon,
    stroke: none,
    table.hline(stroke: 1.5pt),
    table.header()[*小区编号*][*分配的$ P C I$*][*小区编号*][*分配的$ P C I$*],
    table.hline(stroke: 1.0pt),
    ..range(62613,62701).map(str).zip(tab_pci).flatten(),
    [#sym.dots.h.c],[#sym.dots.h.c],
    table.hline(stroke: 1.5pt)
  ),
  caption: [第一问的问题结果]
)<tab4>

== 问题二模型的建立与求解
=== 数据处理
本问题考虑的仍然是2067个小区之间的PCI冲突、PCI混淆和PCI干扰，因此冲突矩阵A、混淆矩阵B、干扰矩阵C仍然与问题一中的相同。

=== 分层序列的多目标规划
该问题在问题一的基础上考虑了三种情况的优先级，因此这是一个多目标规划问题，即有三个目标函数，冲突MR数 $f_1$ 越小越好、混淆MR数 $f_2$ 越小越好、干扰MR数 $f_3$ 越小越好，再这个基础上依次降低其优先级。

给这三种MR数加权重值可以解决这个问题，即冲突MR数权重系数最大最重要，混淆MR的系数次之，干扰MR的系数最低优先级最低，但由于确定系数是一件困难的事，无法主观给定三个系数的比例从而使得模型更加客观。因此，本文采用分层序列模型进行求解。

首先确保冲突MR数降到最低：

#equation(
  $ min f_1 = sum_(j = 1)^(2067) sum_(i = 1)^(2067) x_(i j) a_(i j) $
)

#equation(
  $ 
  s.t. cases(
    sum_(j = 1)^(2067) x_(i j) = 1\, #h(1em) i=1\,2\,3\,...\,2067,
    0<=P C I <= 1007
  )
   $
)

#indent 其次考虑：
#equation(
  $ min f_2 = sum_(j = 1)^(2067) sum_(i = 1)^(2067) x_(i j) b_(i j) $
)

#equation(
  $ 
  s.t. cases(
    sum_(j = 1)^(2067) x_(i j) = 1\, #h(1em) i=1\,2\,3\,...\,2067,
    0<=P C I <= 1007
  )
   $
)
#indent 最后考虑

其中
#equation(
  $ x_(i j) = cases(
    1 \,#h(1em) #[第 $i$ 个小区与第 $j$ 个小区的 $P C I$ 相同] ,
    0 \,#h(1em) #[else]
  ) $
)


#equation(
  $ y_(i j) = cases(
    1 \,#h(1em) #[第$i$个小区与第$j$个小区的 $P C I$ 模3的值相同] ,
    0 \,#h(1em) #[else]
  ) $
)

=== 三个目标函数按优先级依次考虑
+ 首先考虑第一个目标函数

#indent 争对冲突MR数最小的PCI分配问题，仍然是应用蒙特卡洛模拟算法求解0-1整数规划的方法：

对于一次完整的模拟过程：采用均匀分布的方式生成1×2067的PCI分配矩阵，每个值的范围是[0,1007]。找到PCI相同的小区，每两个之都发生冲突，记为1，从而生成矩阵 $x$ 。矩阵 $x$ 反应PCI冲突，根据PCI冲突的发生条件，相同PCI值的小区之间记为1，不同PCI值的小区记为0。每次计算首要目标函数 $x_(i j)*a_(i j)$ 的值，经过 $10^6$ 次的模拟后，把每次的模拟结果用散点图表示出来，可以发现明显的疏密分布，且中间有较大的空隙，分水岭大约在80000处，在80000以下的点比较稀疏，大约有10个，取最小的5组。

#img(
  image("../figures/fig3.png"),
  caption: [问题二中第一条分水岭]
)<fig3>

2. 考虑第二个目标函数
#indent 在考虑了冲突MR数尽可能的基础上，取到了五组值，对这五组的PCI分配情况进行混淆MR数计算，即对每组的 $sum_(j=1)^2067 sum_(i=1)^2067 x_(i j) b_(i j)$ 值进行比较，这就是在解第二个（次优先级）目标函数。同样的方法作出散点图，发现中间有较大的空隙，可以找到一条分水岭大约在30万处，取最小的3组PCI数据。

#img(
  image("../figures/fig4.png"),
  caption: [问题二中第二条分水岭]
)<fig4>

3. 考虑最后一个目标函数
#indent 经过两次筛选可以得到三组PCI数据，对于每一组来说，先进行模3处理，找到模3后相同的小区序号。创建 $y$ 矩阵反应PCI冲突情况，模3相同的小区之间记为1，不同的记为0。对每组计算的干扰MR数 $sum_(j=1)^2067 sum_(i=1)^2067 y_(i j) c_(i j)$ 进行比对，取最小的干扰数的一组记为此时的结果,此时的干扰MR数最小为54186656。



#let tab_pci2 = (
  317,877,379,856,86,304,847,398,227,448,766,967,167,160,269,
  505,340,596,346,753,904,202,841,945,995,966,433,680,291,536,6,913,950,568,
  921,450,681,585,941,488,367,53,906,605,275
).map(str)

#tbl(
  table(
    columns: (1fr,)*4,
    align: center+horizon,
    stroke: none,
    table.hline(stroke: 1.5pt),
    table.header()[*小区编号*][*分配的$ P C I$*][*小区编号*][*分配的$ P C I$*],
    table.hline(stroke: 1.0pt),
    ..range(62613,62701).map(str).zip(tab_pci2).flatten(),
    [#sym.dots.h.c],[#sym.dots.h.c],
    table.hline(stroke: 1.5pt)
  ),
  caption: [第一问的问题结果]
)<tab5>

== 问题三模型的建立与求解
=== 数据处理
在构建冲突矩阵A的时候，需要对附件1表格中的小区进行筛选，删除其他非优化且无关联的小区，有2857个小区。附件2和附件3直接反应了20857个小区之间的冲突、混淆和干扰的情况。接着依次将对应的MR数填入三个矩阵中，构造出冲突矩阵D、混淆矩阵E、干扰矩阵F。

这2067个小区之间的冲突矩阵部分如下图（完整表格见附录）：

#tbl(
  table(
    columns: (1fr,)*9,
    align: center+horizon,
    [#h(1em)],[...],..range(18,24).map(str),[...],
    [18],table.cell(rowspan: 6)[...],..(0,85594,21328,1109,109,102).map(str),table.cell(rowspan: 6)[...],
    [19],..(106137,0,24365,3100,1043,296).map(str),
    [20],..(10363,75422,0,8290,21,51).map(str),
    [21],..(6,8292,17734,0,65895,141985).map(str),
    [22],..(369,8138,0,88787,0,85208).map(str),
    [23],..(0,69,0,77623,75856,0).map(str),
    [...],table.cell(colspan: 8)[...]
  ),
  caption: [第三问中的冲突矩阵D]
)<tab6>

#v(1.0em)

#tbl(
  table(
    columns: (1fr,)*9,
    align: center+horizon,
    [#h(1em)],[...],..range(18,24).map(str),[...],
    [18],table.cell(rowspan: 6)[...],..(0,85594,21328,1109,109,102).map(str),table.cell(rowspan: 6)[...],
    [19],..(106137,0,24365,3100,1043,296).map(str),
    [20],..(10363,75422,0,8290,21,51).map(str),
    [21],..(6,8292,17734,0,65895,141985).map(str),
    [22],..(369,8138,0,88787,0,85208).map(str),
    [23],..(0,69,0,77623,75856,0).map(str),
    [...],table.cell(colspan: 8)[...]
  ),
  caption: [第三问中的混淆矩阵C]
)<tab7>

#v(1.0em)

#tbl(
  table(
    columns: (1fr,)*9,
    align: center+horizon,
    [#h(1em)],[...],..range(18,24).map(str),[...],
    [18],table.cell(rowspan: 6)[...],..(0,85594,21328,1109,109,102).map(str),table.cell(rowspan: 6)[...],
    [19],..(106137,0,24365,3100,1043,296).map(str),
    [20],..(10363,75422,0,8290,21,51).map(str),
    [21],..(6,8292,17734,0,65895,141985).map(str),
    [22],..(369,8138,0,88787,0,85208).map(str),
    [23],..(0,69,0,77623,75856,0).map(str),
    [...],table.cell(colspan: 8)[...]
  ),
  caption: [第三问中的干扰矩阵E]
)<tab8>


=== 蒙特卡洛模拟
生成1 $times$ 2857 的PCI分配矩阵

PCI的分配因为不具某种特殊的分布，为了更加准确的反应最终的结果，本文采用均匀分布的方式生成1×2857的PCI分配矩阵，每个值的范围是[0,1007]。

根据上面对蒙特卡洛次数的分析，一共生成 次PCI分配矩阵，将每次算出的结果对应的总MR数算出来，更新最小值，便可以得到满意的解。

=== 引入0-1矩阵
为了算出总MR数，就需要知道三种情况是否发生，分别发生在哪两个小区之间。PCI的复用，会导致每两个使用相同PCI的小区产生PCI冲突、混淆，每两个小区的PCI值模3相同还会产生PCI干扰。那么需要引入两个2857×2857的0-1矩阵（矩阵 $m$ 和矩阵 $n$ ）。矩阵 $m$ 反应PCI冲突和PCI混淆的情况，根据二者发生的条件，相同PCI值的小区记为1，不同PCI值的小区记为0。矩阵 $n$ 反应PCI干扰的情况，根据其发生的条件，PCI模3相同的小区记为1，不同PCI值记为0。

在蒙特卡洛模拟的过程中，对于每一次求解，针对PCI冲突和PCI混淆的情况，首先在PCI分配矩阵中获取PCI值相同的小区索引号，每两个小区之间的 $m_(i j)$ 记为1，其余记为0。于是 $m*(D+E)$ 就表示了冲突MR数和混淆MR数的和。

针对PCI干扰的情况，首先现对PCI分配矩阵中的作PCImod3的运算，得到PCI模3相同的小区索引号，每两个小区之间的 $n_(i j)$ 记为1，其余都为0。于是 $n*F$ 表示了干扰MR数。


=== 模型求解
本文建立数学规划模型：

#equation(
  $ 
  min z = 
  sum_(j = 1) ^(2857)sum_(i = 1)^(2857) m_(i j) dot d_(i j) + 
  sum_(j = 1) ^(2857)sum_(i = 1)^(2857) m_(i j) dot e_(i j)+
  sum_(j = 1) ^(2857)sum_(i = 1)^(2857) m_(i j) dot f_(i j)
  $ 
)

#equation(
  $ s.t.cases(
    sum_(j = 1)^(2067) m_(i j) = 1\,#h(1em) i = 1\, 2\,3 ...\, 2857,
    0<=P C I <= 1007
  ) $ 
)

其中 $z$ 为总MR数

#equation(
  $ m_(i j) = cases(
    1 \,#h(1em) #[第 $i$ 个小区与第 $j$ 个小区的 $P C I$ 相同] ,
    0 \,#h(1em) #[else]
  ) $
)


#equation(
  $ n_(i j) = cases(
    1 \,#h(1em) #[第$i$个小区与第$j$个小区的 $P C I$ 模3的值相同] ,
    0 \,#h(1em) #[else]
  ) $
)

#indent 上述目标函数可以简写为
#equation(
  $
 R = m*(D+E)+n*F
  $
)

其中 $R$ 是一个2857×2857的矩阵， $R_(i j)$ 反映了小区 $i$ 和小区 $j$ 之间的，冲突MR数、混淆MR数、干扰MR数的总和。若小区 $i$ 和小区 $j$ 分配的PCI相同，则冲突数增加 $d_(i j) + d_(j i)$ ，混淆数增加 ，若小区 $i$ 和小区 $j$ 分配的PCI模3相同，则干扰数增加 $f_(i j) + f_(j i)$ ，因此只需要将矩阵 $R$ 中每个元素相加即可得到总MR数 $z$ 。

通过前面介绍的蒙特卡洛的模拟方法，引入0-1矩阵，经过 $10^6$ 次试验，比对求得最终的总MR数。经过几轮蒙特卡洛试验发现总MR数的最优值稳定在五千两百万左右，由于要让总MR数最小，取几次试验得最小值的MR总数为50899984，对应的PCI分配如下表（完整结果见计算结果文档）：

#let tab_pci = (
  735,718,494,817,647,243,182,43,956,85,79,776,616,668,
  547,78,465,841,330,536,145,310,475,257,14,317,563,537,
  238,929,689,1003,581,135,713,338,185,914,692,941,930,935,420,
  108,985,483,537
).map(str)

#tbl(
  table(
    columns: (1fr,)*4,
    align: center+horizon,
    stroke: none,
    table.hline(stroke: 1.5pt),
    table.header()[*小区编号*][*分配的$ P C I$*][*小区编号*][*分配的$ P C I$*],
    table.hline(stroke: 1.0pt),
    ..range(62613,62701).map(str).zip(tab_pci).flatten(),
    [#sym.dots.h.c],[#sym.dots.h.c],
    table.hline(stroke: 1.5pt)
  ),
  caption: [第三问的问题结果]
)<tab9>

== 问题四模型的建立与求解
=== 数据处理
本问题考虑的仍然是2857个小区之间的PCI冲突、PCI混淆和PCI干扰，因此冲突矩阵D、混淆矩阵E、干扰矩阵F仍然与问题一中的相同。

=== 分层序列的多目标规划
该问题在问题三的基础上考虑了三种情况的优先级，因此这是一个多目标规划问题，即有三个目标函数，冲突MR数 $z_1$ 越小越好、混淆MR数 $z_2$ 越小越好、干扰MR数 $z_3$ 越小越好，再这个基础上依次降低其优先级。

首先确保冲突MR数降到最低：

#equation(
  $ min z_1 = sum_(j = 1)^(2857) sum_(i = 1)^(2857) m_(i j) d_(i j) $
)

#equation(
  $ 
  s.t. cases(
    sum_(j = 1)^(2857) m_(i j) = 1\, #h(1em) i=1\,2\,3\,...\,2857,
    0<=P C I <= 1007
  )
   $
)

#indent 其次考虑：
#equation(
  $ min z_2 = sum_(j = 1)^(2857) sum_(i = 1)^(2857) m_(i j) e_(i j) $
)

#equation(
  $ 
  s.t. cases(
    sum_(j = 1)^(2857) m_(i j) = 1\, #h(1em) i=1\,2\,3\,...\,2857,
    0<=P C I <= 1007
  )
   $
)
#indent 最后考虑：

其中
#equation(
  $ m_(i j) = cases(
    1 \,#h(1em) #[第 $i$ 个小区与第 $j$ 个小区的 $P C I$ 相同] ,
    0 \,#h(1em) #[else]
  ) $
)


#equation(
  $ n_(i j) = cases(
    1 \,#h(1em) #[第$i$个小区与第$j$个小区的 $P C I$ 模3的值相同] ,
    0 \,#h(1em) #[else]
  ) $
)

=== 三个目标函数按优先级求解
1. 考虑第一个目标函数
#indent 争对冲突MR数最小的PCI分配问题，仍然是应用蒙特卡洛模拟算法求解0-1整数规划的方法：

对于一次完整的模拟过程：采用均匀分布的方式生成1×2857的PCI分配矩阵，每个值的范围是[0,1007]。找到PCI相同的小区，每两个之都发生冲突，记为1，从而生成矩阵 $m$ 。矩阵 $m$ 反应PCI冲突，根据PCI冲突的发生条件，相同PCI值的小区之间记为1，不同PCI值的小区记为0。每次计算首要目标函数 $m_(i j)*d_(i j)$ 的值，经过 $10^6$ 次的模拟后，把每次的模拟结果用散点图表示出来，可以发现明显的疏密分布，且中间有较大的空隙，分水岭大约在80000处，在80000以下的点比较稀疏，大约有10个，取最小的5组。

#img(
  image("../figures/fig5.png"),
  caption: [问题四中第一条分水岭]
)

2. 考虑第二个目标函数
#indent 在考虑了冲突MR数尽可能的基础上，取到了五组值，对这五组的PCI分配情况进行混淆MR数计算，即对每组的 $sum_(j = 1)^2857 sum_(i = 1)^2857 m_(i j)dot e_(i j)$ 值进行比较，这就是在解第二个（次优先级）目标函数。同样的方法作出散点图，发现中间有较大的空隙，可以找到一条分水岭大约在120万处，取最小的4组PCI数据。

3. 考虑第三个目标函数
#indent 经过两次筛选可以得到四组PCI数据，对于每一组来说，先进行模3处理，找到模3后相同的小区序号。创建 矩阵反应PCI冲突情况，模3相同的小区之间记为1，不同的记为0。对每组计算的干扰MR数 $sum_(j=1)^2857 sum_(i=1)^2857 n_(i j) dot f_(i j)$ 进行比对，取最小的干扰数的一组记为此时的结果,此时的冲突MR数为41415，混淆MR数为1024166，干扰MR数为58765303，其MR数总和为59830884。


#let tab_pci = (
  735,718,494,817,647,243,182,43,956,85,79,776,616,668,
  547,78,465,841,330,536,145,310,475,257,14,317,563,537,
  238,929,689,1003,581,135,713,338,185,914,692,941,930,935,420,
  108,985,483,537
).map(str)

#tbl(
  table(
    columns: (1fr,)*4,
    align: center+horizon,
    stroke: none,
    table.hline(stroke: 1.5pt),
    table.header()[*小区编号*][*分配的$ P C I$*][*小区编号*][*分配的$ P C I$*],
    table.hline(stroke: 1.0pt),
    ..range(62613,62701).map(str).zip(tab_pci).flatten(),
    [#sym.dots.h.c],[#sym.dots.h.c],
    table.hline(stroke: 1.5pt)
  ),
  caption: [第四问的问题结果]
)<tab10>
