最优无线电信道分配.pdf

第3 卷 第3 期数学的实践与认识 0 0 1 年 5 月MAT HE MATI CS I N P R ACTI C E AND THE ORY V 1 3 1 N s M v 2 0 0 1 最 优 无 线 电 信 道 分 配 方海燕 u 金使职业大学 艺 南通工学院 郭跃华 髯 2 2 0 0 01 2 2 6 0 0 7 摘要 本文 讨论2 0 0 0 年M C M B 题的扩展 给出了 无 线电 信道配m 模V k 0全部的最优解及部分is明 关健词 MC M 路度 最优解 本文讨论2 0 0 年MC M B题扩展 即相邻传送站频道相差k以上 隔一个传送站的频 道相差 1 以上 1 超I k 的情况 找到了全部最优解 并给出了部分证明 1 k k 模型和 k 1 模型 1 k k 模型 任选一个小正六边形为中心的一圈共七个小格 它们两两或相邻 或隔开一个格子 按 要求这七个格子配置的七个频道两两至少相差k 则这七个正整数至少是 l k 十1 2 k 干1 3 k 1 4 k 十1 S k 1 6 k 十1 故s p a n 6 k 十1 又找到一组周期可行解 图I 因而s p a n 6 k 斗1 所以s p a n 6 k 1 月r 记J 其 图 1图 2 2 2 1 模型 易证 两圈以上s p a n 9 又找到一组周期可行解 图2 因而s p a n 9 所以s p a n 9 3 3 1 模型 k 异3 时 显然任一个小正六边形为中心的第一圈中最多只能用三个连续自然数 易证 收粗9期 2 0 0 2 0 2 2 s 万方数据 3 1 2 数学的实践与认识3 1 卷 一圈时 若中心为3 7 8 9 则s p a n 1 2 二圈以上时 s p a n 1 2 证反证法 设s p a n 1 7 由前面结论 3 7 8 9 这四个数不能用 这样只能用 1 2 4 5 6 1 0 1 1 这七个数 因此无解 因为这些数中 没有一个数可作为中心 中心与其周围六个 数至少差 3 上述七个数中每个数至少与另一个数相连 所以s p a n l 2 又找到 一 组周期 可行解 图3 因而s p a n 1 2 所以s p a n 1 2 1 4 1 模型 易证 此时 若中心为4 5 6 9 1 0 1 1 的一圈 则s p a n 1 5 二圈以上时 s p a n 1 5 证反证法 设s p a n 1 4 由前面结论 4 5 6 9 1 0 1 1 这六个数不能用 这样只能用1 2 3 7 8 1 2 1 3 1 4 这八个数 这八个数中只有7 或8 能作为中心 其周围一圈六个格子只能用7 2 3 1 2 1 3 1 4 这六个数 而这六个数都不能作为中心 故无法向外扩展 所以s p a n 1 5 又找到一组周期可行解 图4 因而s p a n l 5 所以s p a n 1 5 2 3 一7 1 0 1 i t 认 1 l 5卜 6 峨仑 图 3图 4 5 k l 模型 k 5的整数 任选三个两两相邻的小正六边形 三个频道是x y z 则x y z 两两至少相差k 设1 镇 二 k 则y 二 十k 二 y k x 2 k 称二属于O k 段 Y 属于l k 段 二属于2 k以上段 故最优 解中一定含有 O k 段 1 k段 2 k以上段中的数 易证 一圈时 若以k l k 2 k 6 k 7 为中心 则 s p a n 异2 k 8 故在 k 1 模型 中 若s p a n 2 k 7 则 1 k 段只能用k 3 k 4 k 十5 这三个数 若用k 5 则以此为中心的 一圈s p a n 2 k 7 见图5 若 s p a n 2 k 十6 由上面讨论知 l k段只能用k 3和k 4 此时 2 k 6 无法成为中心 见图6 无可行解 综合上述讨论 s p a n 2 k 十7 又找到一组周期可行 解 图 7 因而 s p a n 若2 k 7 所以 k l 模型中s p a n 2 k 7 图 5 万方数据 3期方海燕等 最优无线电信道分配 3 1 3 k 3 酬 图 7 综合上述讨论 得到 定理 1 在 k 1 模型中 span k 1 一 6 k 1 3 k 3 2 k 7 k 1 k 2 3 k 4 2 下面考虑 k 1 模型 其中k 妻l k l 均为正整数 任选一个小正六边形的中心建立如图8 所示的坐标系 则所有传送站 小正六边形的中 心 均位于 i 力 其中i 十 j 为偶数 A i j 里 位于 i r 力处的传送站频道 t j 为偶数时 0 i j 为奇数时 约束条件可表示为 1 I A i p j 4 A i j I i k i i 为偶数p 一士1 且4 士1 或p 0 且9 一士 2 2 1 A i s j 一 A i 川 l 汁j 为偶数 一 且t 士4 或 士1 且L 士3 或 士2 且 t 士2 或 s 士2 且 t 0 满足条件 ll 2 且使得 m a x A 9 1 0 A i j 最小的一组A i j 称为最优解 引理1 若最优解中一定不含自然数a 则最优解也一定不含自然数s p a n 1 a 证 A s 入 i j A s p a n 1 一 A i j 二 y 一A i j l s p a n 1 一A i 二 J y 一 s p a n 1 一A i j I I A i X j y 一A i j 若A i j 为 最 优 解 由 上 式 知入 i j 是 可 行 解 又A i j 为 最 优 解 有1 A i j 或A i s j 十约 x O 则将二换成与其最接近的且比其小 的形式为 1 k 十1 l l 的数 其它元素不变 则条件 1 2 仍满足 且频道最大值不变 仍是最 优解 若z 1 i 干 p 心 十 q o m k 牛n 上 1 干1 或二 1 十 j 十 t m k 十刀 1 十1 则 由 1 得x n 一1 k r n l l 由2 得x m 沪 L n十1 l 十1 将二 换成与 其最接近的且比其小的形式为 k 1 l 十1 的数 其余元素不变 则 1 i 户 仍是可行解 又频道最大值不变 所以 1 i 户 仍是最优解 如此进行下去不符合上述形式 频道会越来越少 命题得证 定理 3 在 k 1 模型 其中k 一n l m为正整数 中 f 6 k r 1 m 1 s p a n 一 3 k 止2 1 牛 1 2 k 韦6 1 干7 m 2 3 n 妻4 证由定理2 知 此时最优解可表示为A 力 a l 十 1 十 J 为偶数 a 为非负整数 令 4 i 户 Q 干l 则用反证法易证A i j 是 k l 问 题最优解的充 要条件是A i 是 二 1 问 题的最优解 由定理 1 sn an m 1 土 1 2 3因 4 1 j 一 了 一 1 l 2 m 十 7 1 乒 4 6 k 1 I n I 故s p a n k l 梢 3 k 今2 1 十1 m二2 3 k m l 1 2 k 6 1 1 4 定理4 在模型 k l 中 k v n l r O r l s p a n m t l 毛s p a n k 1 s p a n M一1 l 1 证因为 m十1 1 1 问题的最优解一定是 k 月问题的可行解 k 1 问题的最优解也 一定是 m 1 1 间题的可行解 所以s p a n m l I s p a n k 1 s p a n m十1 l l 定理5 当3 1 k 4 1 时 s p a n k l 二3 k 2 1 1 证首先找到一组周期可行解 图9 因而s p a n 镇3 k 十2 1 1 任取三个两两相邻的小正六边形 三个频道两两至少相差k 即最优解至少用三个k 段 以二为中心一圈内同一k 段最多只能同时用三个元素 分别讨论如下 二为正整数 O k 段 当3 1 十1 z 3 k 2 1 1 1 k段 当二 k l k 1 十1 时 s p a n 3 k 2 1 十1 当k l x k 十1 1 和k 十l 十1 二 3 k 2 1 十1 万方数据 方海燕等 最优无线电信道分配 31 5 3期 2 k 段 x 2 k 十1 2 k 十1 1 2 k 2 1 十1 时 s p a n 3 k 一2 1 1 当 2 k 1 x 2 k 十1 1 2 k 十1 十1 二 2 k 2 1 十1 2 k 2 1 1 二 3 k 2 1 1 故 若最优解 s p a n 3 k 十2 1 1 O k段可用 1 1 1 2 1 1 l k 段可用 k l k 斗l l k 斗2 1 1 6 1 1 k 3 1 l 7 1 十1 2 k段可用 2 k r 1 2 k 1 1 2 k 十2 1 1 2 k 3 1 十1 1 0 1 十1 k 7 1 1 1 1 1 1 若s p a n 3 k 2 1 十1 因而这二个数也不能用 在这种情况下 2 k 十 1 2 k 1 十1 2 k 2 1 十1 2 k 丰3 1 十1 也不能用 图示说明 格子中 b即a k b l 1 图 9 一 一 一 一 一 卜 一 一 一司 甲 卜 砂 1 12 3 1 ik i k 卜 k 之 卜 k 3 1 1 2 k 1 2 k 1 1a l e 2 1 1 2 k 3 1 1 3 k 1 此时3 k以下段只能用 O k段 1 1 干1 1 k段 6 1 1 7 1 1 2 k 段 1 0 1 1 k 7 1 1 1 1 1 1 故s p a n 4 1 时 s p a n k I 2 k 6 1 1 证由定理 4 知 最优解中至少有三个 k段 首先 找到一组周期可行解 如图1 0 因而s p a n 2 k 6 1 1 现考察 1 k段 若k 十1 x 2 k 十6 1 1 为中心一圈s p a n 2 k 十6 1 1 图1 1 以 k 十4 1 1 若s p a n 2 k 6 1 十1 则 l k 段同时只能用二个频道 如k 十2 1 十l k 3 1 1 此时无可行 解 图1 2 故s p a n 2 k 6 1 1 所以s p a n k I 2 k 6 1 1 洲一叭 图 1 0 图 1 1 图 1 2 万方数据 3 1 6数学的实践与认识3 1 卷 定理 7 在 k l 模型中 6 k占 1 8 1 1 音 音 k 2 1 s p a a k l 一 4 k未 1 1 1 1牛 1 k 1 1 14 1 3 1 3 k 2 1 l 2 k 6 1十 1 当1 k 3 1 时 证明较长 另文给出 3 1 k 4 1 k 4 1 参考文献 姜启源数学模型 第二版 朱道元数学建棋精品案例 北京 高等教育出版社 1 9 9 3 东南大学出版社 1 9 9 9 O p t i m a l R a d i o C h a n n e l A s s i g n m e n t s F A N H a i y a n G U O Y u e h u a 1 N a n j in g P o l y t e c h n ic C o l l e g e 2 N a n t o n g I n s t i t u t e o f T e c h n o l o g y Na n j i n g 2 1 0 0 0 1 N a n t o n g 2 2 6 0 0 7 A b s t r a c t T h i s p a p e r d i s c u s s e d t h e e x t e n s i o n o f t h e