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

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

摘  要
 本文研究通讯卫星上的开关设置问题，具体的讨论了开关模式的优化设计方法。
 在发送接收任务矩阵给出后，我们证明了在完成预定任务的前提下，开关模式使用总时间的下界是的最大行列和，并利用双随机矩阵的特殊性质，证明了总存在一组开关模式使得使用总时间等于的最大行列和，同时给出了相应的算法，对任意给定的任务，设计出相应的开关模式组及对应的使用时间，使得使用总时间达到最小；对于最少开关模式数，本文得出如下结论：当中零元素个数小于时，；对一般的任务矩阵，，此时只要求出完全覆盖中非零元素的一组开关模式，，使得尽量小即可，最后我们分析给出了最小值的一个上界。
 针对任务三中给出的四个任务矩阵，模型求解结果如下：
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
 至此，定理1.2得到证明。
 对任务一，当发送接收任务给出后，先利用算法1将转化为双随机矩阵，再利用算法2将分解为，这样我们得到一组开关模式，及模式的使用时间，满足条件，以上分析已经证明，这样得到的是最小的。
任务二
 求  
     
若T中任意元素都大于零
     此时只要找到一组，，且尽可能小即可，因为此时只要令=就能满足，而由置换矩阵的特点总可以找到n个置换矩阵，那么要满足条件（2 .1），.
若中含有零元素，则可能减小，对一般的，要满足， 显然有.
 令，，由以上分析问题转化为
 
 
 若满足条件（2.2），同1）只要令=就能满足，
 阶置换矩阵共有个，当较小时直接搜索容易求得结果，例如任务三中的，。
   事实上直接求解问题（2.2）是NP难的，当太大时问题无法直接求解。
   我们考虑怎样使r尽可能的小。因为当T中所有元素都非零时，，随着零元素个数的增加将引起的减小。显然当零元素个数小于时仍然有成立。
   定义2.1  对置换矩阵，若任意可推出，则称被零覆盖。
   容易理解，随着中零元素个数的增加，当正好有个互不重叠（任两个没有位置重合的1）的置换矩阵，被T零覆盖，则。
 与算法2类似，可按如下方式求得：
 算法3：
   Step1 ，选取有可推出的置换矩阵，若不存在，终止，返回；否则，执行Step2
   Step2  ，， ，返回Step1
    例如对任务三中的的求解结果满足。 
任务三
 对题中给出的任务矩阵，，，分别求解第一问和第二问。
 由任务一和任务二中得出的结论，解答如下：
:
求最小
  利用算法1和算法2将T转化为再分解如下：
 
 , 对应的. 
求最小
   不含零元素，取一组满足条件（2.1）的开关模式
 
 min ，对应的,   .
:
求最小:
      同:
   
  min, 对应的.
求最小:
      取一组满足条件（2.2）的开关模式如下：
 
    ，对应的.
:
求最小
       同以上两问：
      , 对应的.  
求最小:
 取一组满足条件（2.2）的开关模式如下：
       
  ，对应的 .
: 
,对应的模式数。
不含零元素，只需满足条件（2.1）即可。
     任选一组满足条件的开关模式，得到,对应的总使用时 间 。                                                                           
 （对应的开关模式组及相应的使用时间见附录）
模型检验与结果分析
 
  通过对任务三中四个给定任务的求解已经很好的检验了我们建立的模型。
   第一问求最短使用总时间，四个任务矩阵的结果都已经达到总使用时间的下界，并给出了相应的开关模式组，及对应的使用时间，这已经
是最优的结果。求解过程中使用的算法都是多项式时间内可解的，具有实际可行性。
                       
模型对问题的求解 最短时间 18 3 13 509 
 最少模式数 3 3 3 8 
参考答案 最短时间 18 3 13 509 
 最少模式数 7 3 5 58 
 第二问求最少开关模式数，我们解出的结果较参考答案更优。
 模型对问题的求解结果与参考答案比较如下：
 
 求解结果很好的验证了我们所得结论的合理性和可操作性。
模型的进一步讨论
    对于问题第二问求最少开关模式数，我们分别对任务矩阵是否含有非零元素的情况做了讨论，得出了一些相应的结论。当任务矩阵所含零元素个数小于时，能够很好的得出最优的结果。当零元素较多且较大时，直接求解难度太大，近似结论并不能满足结果最优。设计复杂度较低的算法或者研究更高精度的近似解法是有待进一步改进的关键之处。
    实际问题中卫星上不便设置太多的开关模式。我们求得的最短使用总时间对应的开关模式数可达到，当较大时将对实际使用造成困难。同样当达到最小时使用总时间将会变得较大，严重降低了卫星的工作效率。我们可以考虑对模型进行适当的改进，在开关模式数和使用总时间之间取得一个平衡，使得卫星上设置的开关模式数不太多又具有较高的工作效率。
    现代通讯卫星已经允许一个发射站同时向多个接收站发送信息，有兴趣的读者可做相应的改进。1987年J.L.Lewandowski和C.L.Liu对此问题进行了较深入的研究，读者可参考相关论文。
模型优缺点
优点：
 方法简洁，可操作性强，对题中所给任务均能取得较好的结果。
缺点：
        对于最小的求解，没有给出对所有任务都适用的方法，只能得到其范围，当较大时不能保证能求得最优解。
 参考文献
 [1]Roger A.Horn,Charles R.Johnson著,杨奇译,矩阵分析, 机械工业出版社, 2005
  [2]姜启源，数学建模，高等教育出版社，1998
 附录
解答:
 求最小:
     利用算法1和算法2将T转化为再分解如下
 
 
   ,   对应的. 
   求最小:
因为不含零元素，只需满足条件（2.1）即可，任选一组满足条件的开关模式

      
      对应的,   .

【研究通讯卫星上的开关设置问题(一)】相关文章：

现代企业绩效管理问题研究05-03

中国家庭伦理剧情节设置的雷同性研究05-29

论组织学习研究的若干问题06-04

新刑诉法下社区矫正问题研究09-05

感知无线电的关键问题研究05-30

刑事二审程序的若干问题研究05-11

大学生文学素养降低问题研究论文04-24

中国农村留守老年人保障问题研究05-11

浅析中小企业招聘存在的问题及对策研究04-21

森林旅游面临的主要问题及对策研究开提报告06-04