通讯卫星的开关设置.doc

《通讯卫星的开关设置.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、通讯卫星的开关设置早期的通讯卫星只允许单向发送信息，且任何一个发送站不能同时给多个接收站发送信息。因此，其数学模型可以描述为如下的标准形式：在地面上存在着n个接收站与n个发送站，而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示，若卫星可接收发射站i发射的信息并将信息传送回地面的接收站j时，矩阵元素pij=1，否则pij=0。通讯卫星需要接收并转发的任务也可用一个矩阵T=（tij）来表示，其元素tij为需经通讯卫星传递的由i发送站发送到j接收站的信息量的传送时间长度。问题要求求出卫星开关模式的数量r、设计

2、一组开关模式Pk，k=1,…,r，并设计一个算法，以便在给定发送任务矩阵T后能求得模式的Pk使用时间λk，使得在完成预定传送任务的前提下各开关模式使用的总时间最短，即要求求解下面的优化问题：mins.t（1）（注：设计定后将安装在通讯卫星上，卫星发射升天后是不可更改的）。本处讨论的课题曾用作2004年浙江大学学生数学建竞赛B题，为进一步说明题意，让我们先来看一个例题：例1设这是一个有3个发送站与3个接收站的实例，tij已在矩阵中给出，例如要求由发射站1传送到接收站1的通讯量为3单位时间等等。分析：由于技术上的原因，当发射站i在发

3、送给接收站j信息时，它不能同时发送给别的接收站信息；同样，当接收站j在接收发射站i的信息时，也不能同时接收其他发射站发送的信息。即每一发送站都不能同时给不同的接收站发送信息，而每一接收站也不能同时接收不同发送站发来的信息。容易看出，三个发送站需要使用卫星传送信息的时间分别为6、5、5；而三个接收站需要接收的时间分别为6、3、7。为完成全部传送任务，通讯卫星要传送完所有信息至少需要7单位时间，即所需时间的下界为7。上述要求还说明，任意一个开关模式Pk应具有以下性质：（1）Pk的每一行中有且只有一个1，每一列中也有且只有一个1（2）

4、所有的1均位于不同的行列中。同时满足（1）、（2）的矩阵被称为置换矩阵，n阶置换矩阵Pk共有n!个，当n较大时，我们不可能在通讯卫星上设置这么多种不同的开关模式。因而，为了设计出切实可行的开关模式，我们还得想些办法。（问题1）（卫星上至少要安装多少个不同的开关模式）传送任务矩阵T是根据顾客的需求而每天变动的，但开关模式装置的设计是在卫星发射前完成的，一经发射将无法变动。为了使任意一对发射站与接收站之间的传送均为可能实现的，自然应要求Pk满足（2）右面的矩阵有n2个值为1的分量，而每一Pk恰有n个1分量，故卫星上至少要安装n只不同

5、的开关，即。为了使开关模式尽可能地少，我们应当尽量使各中的1分布在不同的位置上，以避免出现重复的1，并使开关模式的数量恰好为n。避免出现重复取1的构造法有无穷多种，具体实现非常容易，例如，以n=3为例，可以如下构造：（设计方法1）注意到Pk每行（或列）元素之和均为1，故不管如何指派开关的使用时间（即不论如何取λk），矩阵均具有某些特殊的性质，例如其行和（及列和）均为同一常数。这样的矩阵构成一个线性空间，关于此类线性空间的一个较为详细的讨论可参阅我们编著的“数学建模”（高教出版社，2005年5月出版）一书中第4.2节中的Dürer

6、魔方（或幻方）问题。为减少开关模式的种类，可取此空间的一组基底作为开关模式。在使用这种开关模式时，无论T的元素tij怎么取，通讯卫星对每一发送点（接收点）的开通时间总和是恒定的，即行和列和均相等。在这种开关模式下，可按如下方式指派各开关模式的使用时间：步1先将T改为，满足：（1）（2）记，则（）步2用表示，即将分解为：（注：求解要比将困难得多，这是我们要在步1中将T化为的原因）将T化为的方法有无穷多种，例如可以如下进行：令事实上，为通信卫星开关使用时间总和的一个下界。令其中用这种方法转化例1中的T为，得到：（3）中的行和与列和均

7、为7。定义.1称行和、列和均为同一个数的矩阵为双随机矩阵（Doublystochasticmatrix）定理.1（Birkhoff定理，1944）任意一个n阶双随机矩阵均可写成至多（n－1）2+1个置换矩阵的线性组合。（注：这一定理说明，由全体双随机矩阵所构成的线性空间的维数为（n－1）2+1）的分解可如下进行：步1选取由Pij>0可推出>0的置换矩阵P（注：要做到这一点，通常需要求解一个指派问题或最大流问题，见后）步2确定步3取，用代替步4若，停；否则，返回步1例2为方便起见，我们来分解一个元素均为非负整数的3阶双随机矩阵，（

8、由Birkhoff定理，r≤5）令解：取λ=min{1,3,3}=1分解后取因min{5,5,3}=3，又有取于是又有，易得分解结果为：尚需解决的问题是如何求P，使得Pij>0必有>0。读者不难发现，此问题可以通过求解一个两分图上的最大流（或最大匹配）来实现，计