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

 至此，定理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.Le

首页 上一页 1 2 3 下一页 尾页 2/3/3

研究通讯卫星上的开关设置问题(二)相关范文