研究通讯卫星上的开关设置问题(一)

摘  要
 本文研究通讯卫星上的开关设置问题，具体的讨论了开关模式的优化设计方法。
 在发送接收任务矩阵给出后，我们证明了在完成预定任务的前提下，开关模式使用总时间的下界是的最大行列和，并利用双随机矩阵的特殊性质，证明了总存在一组开关模式使得使用总时间等于的最大行列和，同时给出了相应的算法，对任意给定的任务，设计出相应的开关模式组及对应的使用时间，使得使用总时间达到最小；对于最少开关模式数，本文得出如下结论：当中零元素个数小于时，；对一般的任务矩阵，，此时只要求出完全覆盖中非零元素的一组开关模式，，使得尽量小即可，最后我们分析给出了最小值的一个上界。
 针对任务三中给出的四个任务矩阵，模型求解结果如下：
T1：最少模式数3，最短时间18（两者可同时达到）
T2：最少模式数3，最短时间3（两者可同时达到） 
T3：最少模式数3，最短时间13（两者不能同时达到[9，13]或[3，14]）
T4：最少模式数8，最短时间509（两者不能同时达到，[8，671]或[50，509]）
  

问题重述
 早期的通讯卫星只允许单向发送信息，且一个接收站同一时刻只能接收一个发送站的信息。问题的数学模型可以描述为：
 在地面上存在着n个接收站与n个发送站，而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵来表示，若卫星可接收发射站发射的信息并将信息传送回地面的接收站时，矩阵元素，否则。通讯卫星的接发任务也可用一矩阵来表示，其元素为需经通讯卫星传递的由发点发送到接受点的信息量的传送时间长度。问题要求在发送接受任务给出后设计一组开关模式，及模式的使用时间， 完成以下任务：
任务一：
在发送接受任务给出后,设计一组开关模式，,使得在完成预定任务前提下各开关模式使用时间的总时间最短,即求解下列优化问题:
   
 
任务二：
在发送接受任务给出后, 设计一组开关模式，,使得在完成预定任务前提下尽可能小, 即求解下列优化问题:
 
     
任务三:
就以下给出的四组任务矩阵，分别求一，二问，给出相应的开关模式组及每个模式对应的传送时间。
    
 
假设
开关模式之间切换时间为零
发送站和接收站一直处于正常工作状态
符号说明
             开关模式数
 ，     由个开关模式组成的一个开关模式组
                 通讯卫星上的发送接收任务矩阵
              对应的双随机矩阵
                  第个开关模式的使用时间
                   任务矩阵的最大行列和
问题分析
 问题要求设计一组开关模式，及模式的使用时间，使其满足相应的条件。对给定的任务，首先必须满足。我们很自然的想到模式数和使用总时间之间存在相互制约的关系，即限制开关模式数量会导致  增大。
 在本题的求解中，对任务一，为了获得最短使用时间我们不考虑开关模式数量；同样对任务二，为了使尽量小，模型不对各个开关模式的使用时间做限制。
 因为开关模式具有的特殊性质，无论怎样选取，矩阵的每一行列和将为，这样的矩阵称为双随机矩阵。因此当任务不是双随机矩阵时条件中的等号是不会成立的。我们考虑对做适当的转化以利用双随机矩阵的性质解决问题。
模型建立与求解
 由于技术上的原因，当发送站在发送给接收站信息时，它不能同时发送给别的接收站信息；同样，当接收站在接收发送站的信息时，也不能同时接收其他发送站发送的信息。这一要求说明，任一开关模式应具有以下性质：
的每一行中有且只有一个1，每一列中也有且只有一个1；
所有的1均位于不同的行列中。
 定义1   称满足性质（1），（2）的矩阵为置换矩阵。
任务一
 求
     
 
 定理1.1  对给定的任务矩阵，满足条件的开关使用总时间的下界为的最大行列和。
    上述定理显然是成立的，对任务矩阵，发送站需要使用卫星传送信息的时间为，同样接收站需要使用卫星接收信息的时间为，为了完成全部传送任务，通讯卫星要传送完所有信息至少需要时间为，
   定理1.2   总存在一组开关模式，，满足条件且。
 为了证明定理1.2，下面引入双随机矩阵的概念。
 定义1.1   称行列和均为同一个数的矩阵为双随机矩阵。
 由置换矩阵的特殊性质，无论怎样选取，总是一个双随机矩阵，其行列和恒为。
 对于双随机矩阵还有如下定理：
 定理1.3 （Birkhoff定理，1944）任一阶双随机矩阵均可写成至个置换矩阵的线性组合。（证明见参考文献[1]）
 这样如果任务矩阵是一个双随机矩阵我们就可以将其分解为若干置换矩阵的线性组合，即，且此时等于的行列和。但是一般的任务矩阵是无法进行以上分解的，因此先将转化为双随机矩阵，满足条件：
；
=（），==，为的最大行列和
 这样我们总能将分解为，且满足=，而由定理1.1, 已经是的下界。
 由以上分析，只要设计出将转化为和将分解为的方法就可以很好的解决任务一。
 下面给出算法1和算法2，算法1将转化为，算法2将双随机矩阵分解成的线形组合。
 算法1：
 令 
 ，，
 
 按如上方式求得=，满足，且。
 算法2：
   Step1 选取有可推出的置换矩阵
   Step2 令
 Step3 取，
 Step4 若，中止；否则，返回Step1