通讯卫星的开关设置.doc

通讯卫星的开关设置早期的通讯卫星只允许单向发送信息，且任何一个发送站不能同时给多个接收站发送信息因此，其数学模型可以描述为如下的标准形式：在地面上存在着n个接收站与n个发送站，而在通讯卫星上则设置了若干种开关模式开关模式可用矩阵P=(pij)来表示，若卫星可接收发射站i发射的信息并将信息传送回地面的接收站j时，矩阵元素pij =1，否则pij =0通讯卫星需要接收并转发的任务也可用一个矩阵T=（tij）来表示，其元素tij为需经通讯卫星传递的由i发送站发送到j接收站的信息量的传送时间长度问题要求求出卫星开关模式的数量r、设计一组开关模式Pk，k=1, …,r，并设计一个算法，以便在给定发送任务矩阵T后能求得模式的Pk使用时间λk，使得在完成预定传送任务的前提下各开关模式使用的总时间最短，即要求求解下面的优化问题： min s .t （1）（注：设计定后将安装在通讯卫星上，卫星发射升天后是不可更改的）本处讨论的课题曾用作2004年浙江大学学生数学建竞赛B题，为进一步说明题意，让我们先来看一个例题：例1 设 这是一个有3个发送站与3个接收站的实例，tij已在矩阵中给出，例如要求由发射站1传送到接收站1的通讯量为3单位时间等等。

分析：由于技术上的原因，当发射站i在发送给接收站j信息时，它不能同时发送给别的接收站信息；同样，当接收站j在接收发射站i的信息时，也不能同时接收其他发射站发送的信息即每一发送站都不能同时给不同的接收站发送信息，而每一接收站也不能同时接收不同发送站发来的信息容易看出，三个发送站需要使用卫星传送信息的时间分别为6、5、5；而三个接收站需要接收的时间分别为6、3、7为完成全部传送任务，通讯卫星要传送完所有信息至少需要7单位时间，即所需时间的下界为7上述要求还说明，任意一个开关模式Pk应具有以下性质：（1）Pk的每一行中有且只有一个1，每一列中也有且只有一个1（2）所有的1均位于不同的行列中同时满足（1）、（2）的矩阵被称为置换矩阵，n阶置换矩阵Pk共有n!个，当n较大时，我们不可能在通讯卫星上设置这么多种不同的开关模式因而，为了设计出切实可行的开关模式，我们还得想些办法问题1）（卫星上至少要安装多少个不同的开关模式）传送任务矩阵T是根据顾客的需求而每天变动的，但开关模式装置的设计是在卫星发射前完成的，一经发射将无法变动为了使任意一对发射站与接收站之间的传送均为可能实现的，自然应要求Pk满足 （2）右面的矩阵有n2个值为1的分量，而每一Pk 恰有n个1分量，故卫星上至少要安装n只不同的开关，即。

为了使开关模式尽可能地少，我们应当尽量使各中的1分布在不同的位置上，以避免出现重复的1，并使开关模式的数量恰好为n避免出现重复取1的构造法有无穷多种，具体实现非常容易，例如，以n = 3为例，可以如下构造： （设计方法1）注意到Pk每行（或列）元素之和均为1，故不管如何指派开关的使用时间（即不论如何取λk），矩阵 均具有某些特殊的性质，例如其行和（及列和）均为同一常数这样的矩阵构成一个线性空间，关于此类线性空间的一个较为详细的讨论可参阅我们编著的“数学建模”（高教出版社，2005年5月出版）一书中第4.2节中的 Dürer魔方（或幻方）问题为减少开关模式的种类，可取此空间的一组基底作为开关模式在使用这种开关模式时，无论T的元素tij怎么取，通讯卫星对每一发送点（接收点）的开通时间总和是恒定的，即行和列和均相等在这种开关模式下，可按如下方式指派各开关模式的使用时间： 步1 先将T改为，满足：（1）（2）记，则 （）步2 用表示，即将分解为：（注：求解要比将困难得多，这是我们要在步1中将T化为的原因）将T化为的方法有无穷多种，例如可以如下进行：令 事实上，为通信卫星开关使用时间总和的一个下界。

令 其中 用这种方法转化例1中的T为，得到： （3）中的行和与列和均为7定义.1 称行和、列和均为同一个数的矩阵为双随机矩阵（Doubly stochastic matrix）定理.1 （Birkhoff定理，1944）任意一个n阶双随机矩阵均可写成至多（n－1）2+1个置换矩阵的线性组合注：这一定理说明，由全体双随机矩阵所构成的线性空间的维数为（n－1）2+1）的分解可如下进行：步1 选取由Pij > 0可推出 > 0 的置换矩阵P（注：要做到这一点，通常需要求解一个指派问题或最大流问题，见后）步2 确定 步3 取，用 代替 步4 若 ，停；否则，返回步1例2 为方便起见，我们来分解一个元素均为非负整数的3阶双随机矩阵，（由Birkhoff定理，r≤5）令 解： 取 λ=min {1, 3, 3 } =1 分解后 取因min{ 5, 5, 3} = 3，又有 取 于是又有， 易得分解结果为：尚需解决的问题是如何求P，使得Pij >0必有 > 0 。

读者不难发现，此问题可以通过求解一个两分图上的最大流（或最大匹配）来实现，计算量为O(n4)，是多项式时间可解的具体方法为：作一个一边是n个发送点，另一边是n个接收点的两分图，若 > 0 ，则作边（i, j），令边容量为1，这样，可以作出P的充分必要条件是该最大流问题的最大流量为n由于 的特殊性质及Birkhoff定理，上述分解必能在不超过r= (n－1)2 + 1步内终止，（线性空间中任意向量按坐标分解的表达式是唯一的）上述开关设计方法要求在通讯卫星上设置(n－1)2 + 1种不同的开关模式（即Pk），当n稍大时，(n－1)2 + 1仍显得太大而使得使用时不便例如，当n=41时，(n－1)2 + 1=1601为实用方便，人们又研究了限止开关模式个数的相应问题设计方法2）（限制开关模式数量的问题）由前，必须有若要求开关模式的个数不超过n，即要求通讯卫星上至多设置n种开关模式，则应当恰好设置n种开关模式，而问题则转化为令r≤n，求不超过n个置换矩阵Pk及λk，使之满足： min s .t （4）容易看出，上式隐含着T的每一元素只能被唯一的P复盖，即T的元素在分解中是不可分割的（因为任意位置只能被中的一个所覆盖），这当然是一个好性质，使实际操作时较为方便。

但可惜的是，对一般的双随机矩阵T，分解 时很可能无解例3 若取 T已是双随机矩阵，行和列和均为10 问题 min s .t 的解为=3, =4, =5, ， 而 因为双随机矩阵空间的维数为(n－1)2 + 1而不是n，等号经常不会成立假如读者仔细考虑一下，不难发现这里有一个新产生的问题：将转换成有无穷多种方法，不同的转换方法会得到不同的卫星开关使用时间例如，对于例1中的，假如我们用前面的方法将它转换成（3），则有：= ， 但如果我们将转换成 则有 ， 究竟应当怎样将转化为才能使卫星开关的总使用时间最小呢？1985年，F·Rendel证明，在给定满足（2）的置换矩阵P1,…,Pn后，求解问题（1）是NP难的，从而不可能存在多项式时间算法，除非P = NP如果一定要限制开关模式的数量不超过n，如前所述，开关模式的总租用时间可能会增大得较多，从而降低通讯卫星的工作效率此时，一项有意义得工作是设计尽可能好的近似算法，（即使得卫星开关的总租用时间尽可能少）并进行最坏情况界分析，由于篇幅的限制，本处略去了这方面的讨论。

人们很自然会想到，如果增加开关模式的数量，也许能减少卫星的租用时间读者不难发现，由于开关模式的对称性，要增加开关模式，就应当增加n只，即要求r ≤2n，（事实上，我们总会取），因为，如果增加的开关数小于n，我们总可以举出这样的例子，开关数的增加并不降低它租用开关的总时间一种自然而方便的开关设置为引入两组有n个开关模式的置换矩阵P1,…,Pn，Q1,…,Qn，满足： 例如，当n=3时，可令： （注：虽然矩阵集合P1,…,Pn，Q1,…,Qn是线性相关的，但不难证明，其中任意n-1个矩阵均线性无关，并构成相应线性空间的基底易见P1,…,Pn，Q1,…,Qn具有很好的对称性，用它们作为通信卫星上的开关设置使用起来会更加方便，不失为一种明智的做法现在，我们来分解例3中的双随机矩阵 ，令 = 求出各对角线与反对角线上的三个元素之和，并作一些简单的消去运算；将矩阵的所有元素相加，可得下面的方程组：空间 的维数为 5，故 之一可任取，（稍加注意即可保持非负性），例如，令μ3=0，求得： 故有 ，对应地有 读者不难验证，上述方法可推广到n是奇数的一般情况。

事实上，由各对角线元素之和可导出n－1个方程，由各反对角线元素之和又可导出n－1个方程，加上矩阵所有元素之和导出的等式，共计可导出2 n－1个方程，并易知它们是独立的另一方面，空间 的维数恰为2 n－1，故 之一可任取，而通过方程组解得所有的 ，（只须注意保持其非负性即可）当n为偶数时，情况就不大相同了让我们先来观察一下n = 4的情况当n = 4时， 易见， 具有非常特殊的结构，一般的偶数阶双随机矩阵，即使其元素是非负整数，也无法用Pk、Qk来分解当 具有上述结构时，能否用Pk和Qk来分解呢？让我们来考察一个实例 例4. 令 易见，由各对角线元素之和可导出：另外，由反对角线元素之和又可导出上述方程中只有6个是独立的，且已不可能再得出新的独立方程，（读者可自行分析之）故可选取其中2个的值，进而可解出其余例如，若令4= 3=0，可得2=1，1=0，进而可求得1=2，4=3，3=3及2=4， 已经达到下界易见，P1 + P3 = Q2 + Q4，P2 + P4 = Q1 + Q3。

容易证明空间 的维数为6，与上面的分析是一致的读者可将上述讨论推广到n为一般偶数的情况，分析方法是完全类似的当n是偶数时，我们虽无法将一般的双随机矩阵分解为Pk 、Qk的非负组合，但上述讨论仍然是十分有意义的首先，要求完成的任务矩阵是T，在将T转换成时有无穷多种方法，我们可尽量使具有上述特殊结构（注：有兴趣的读者可自行研究这一问题），只要能做到这一点，即可给出一个达到下界的开关模式的指派方式其次，即使这样的努力没有成功，也容易给出一个具有上述特殊结构的矩阵，并使 尽可能地小，即给出一种开关指派的近似最佳方法或近似最佳方法，由此即可设计出各种效果较好的近似算法，对这些问题，读者均可开展进一步的研究注：对一般性问题，如何将转化为才能使卫星租用时间最少的问题同样是NP难的，因而，也存在着如何设计效果较好的近似算法的问题）由于技术水平的提高，目前通讯卫星传送信息已经允许一个发射站同时向多个接收站发送信息了，当然，同时发送的信息条数具有某一上。