卫星开关.ppt
《卫星开关.ppt》由会员分享,可在线阅读,更多相关《卫星开关.ppt(21页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2004年浙江大学数学建模竞赛年浙江大学数学建模竞赛(B题)通讯卫星上的开关设置题)通讯卫星上的开关设置 地面上存在着n个接收站与n个发送站,而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示,若卫星可接收发送站i发射的信息并将信息传送回地面的接收站j时,矩阵中的元素pij=1,否则pij=0。通讯卫星上的接收发送任务也可以用一个矩阵T=(tij)来表示,其元素tij为需经通讯卫星传递的由i发点发送到j接收点的信息量的传送时间长度。由于技术上的原因,当发送站i在发送给接收站j信息时,它不能同时发送给别的接收站信息;同样,当接收站j在接收发送站i的信息时,也不能同时接收其
2、他发送站发送的信息。你的任务是:n设计一组开关模式,k=1,r(注:r应当尽可能小),使得对任意给定的任务矩阵T,卫星开关设置均能完成要求的发接收任务。n设计一个算法,在发接收任务T给出后,可根据你设计的开关模式(k=1,r)求出各开关的使用时间k,使得在完成预定传送任务的前提下使用各开关模式的总时间最短。n同样由于技术上的原因,开关模式的总数r有一个上限。当需要传送的任务数数量较大时,仍无法分派任务。请你想一些办法来解决这一困难,(当然,这时你可能要作出一些牺牲,即传送时间可能会增加一些)。问题及模型问题及模型问题的标准形式为:在地面上存在着问题的标准形式为:在地面上存在着n个收站与个收站与
3、n个发战,而在通讯卫星上个发战,而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵则设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示,若卫星可接来表示,若卫星可接收发射站收发射站i发射的信息并将信息传送回地面的接收站发射的信息并将信息传送回地面的接收站j时,矩阵元素时,矩阵元素pij=1,否,否则则pij=0。通讯卫星的接发任务也可用一矩阵。通讯卫星的接发任务也可用一矩阵T=(tij)来表示,其元素)来表示,其元素tij为需为需经通讯卫星传递的由经通讯卫星传递的由i发点发送到发点发送到j接受点的信息量的传送时间长度。问题要接受点的信息量的传送时间长度。问题要求求求求r并设计一组开
4、关模式并设计一组开关模式Pk,k=1,r及模式及模式Pk的使用时间的使用时间k,使得在完,使得在完成预定传送任务的前提下各开关模式使用的总时间最短,即要求求解下面成预定传送任务的前提下各开关模式使用的总时间最短,即要求求解下面的问题:的问题:例例1 1 设设 这是一个有这是一个有3个发送站与个发送站与3个接收站的实例,个接收站的实例,tij在矩阵中已给出,例如在矩阵中已给出,例如由发站由发站1传送到收站传送到收站1的通讯量为的通讯量为3单位时间等。单位时间等。分析分析 容易看出,三个发站需传送的时间分别为容易看出,三个发站需传送的时间分别为6、5、5;而三个收站需接;而三个收站需接收的时间分别
5、为收的时间分别为6、3、7。为完成全部传送任务,通讯卫星总传送时间至少。为完成全部传送任务,通讯卫星总传送时间至少应为应为7单位时间,即的下界为单位时间,即的下界为7。由于技术上的原因,当发站由于技术上的原因,当发站i在发送给收站在发送给收站j信息时,它不能同时发送给别的信息时,它不能同时发送给别的收站信息;同样,当收站收站信息;同样,当收站j在接收发站在接收发站i的信息时,也不能同时接收其他发站的信息时,也不能同时接收其他发站发送的信息。这一要求说明,任一开关模式发送的信息。这一要求说明,任一开关模式Pk应具有以下性质:(应具有以下性质:(1)Pk的的每一行中有且只有一个每一行中有且只有一个
6、1,每一列中也有且只有一个,每一列中也有且只有一个1;(;(2)所有的)所有的1均位均位于不同的行列中。于不同的行列中。满足(满足(1)、()、(2)的矩阵)的矩阵 被称为置换矩阵,被称为置换矩阵,n阶置换矩阵阶置换矩阵Pk共有共有n!个,当个,当n较大时,我们不可能在通讯卫星上设置这么多种不同的开关模式。因而,为较大时,我们不可能在通讯卫星上设置这么多种不同的开关模式。因而,为了设计出切实可行的开关模式,我们还得另想办法。了设计出切实可行的开关模式,我们还得另想办法。(设计方法(设计方法1)注意到注意到Pk每行(或列)元素之和均为每行(或列)元素之和均为1,故不管如何指派开关的使用时间,故不
7、管如何指派开关的使用时间(即不论如何取(即不论如何取k),矩阵),矩阵均具有某些特殊的性质,例如其行和(及列和)均为同一常数。这样的矩均具有某些特殊的性质,例如其行和(及列和)均为同一常数。这样的矩阵构成一个线性空间(参见逻辑模型第一节阵构成一个线性空间(参见逻辑模型第一节 Drer魔方),为减少开关模魔方),为减少开关模式的种类,可取此空间的一组基底作为开关模式。在使用这种开关模式时,式的种类,可取此空间的一组基底作为开关模式。在使用这种开关模式时,无论无论T的元素的元素tij怎么取,通讯卫星对每一发(收)点的开通时间总和是恒定怎么取,通讯卫星对每一发(收)点的开通时间总和是恒定的。在这种开
8、关模式下,可按如下方式指派各开关模式的使用时间:的。在这种开关模式下,可按如下方式指派各开关模式的使用时间:步步1 先将先将T改变为改变为 ,满足:满足:(1)T(2)记)记 ,步步2 用用Pk表示表示 ,即将,即将 分解为分解为(r为空间的维数)为空间的维数)将将T化为化为 的方法一般有无穷多种,如可如下化法:的方法一般有无穷多种,如可如下化法:令令 事实上,事实上,(即通讯卫星传送总时间的下界)。,(即通讯卫星传送总时间的下界)。令令 其中其中 用这种方法化例中的用这种方法化例中的T,得到,得到的任一行(或列)中元素之和均为的任一行(或列)中元素之和均为7。定义定义1 1称行和、列称行和、
9、列%和均相等的矩阵为双随机矩阵(和均相等的矩阵为双随机矩阵(Doubly stochastic matrix)定理定理1 1(Birkhoff定理,定理,1944)任一)任一n阶双随机矩阵均可写成至多阶双随机矩阵均可写成至多 (n1)2+1个置换矩阵的非线性组合。个置换矩阵的非线性组合。的分解可如下进行:的分解可如下进行:步步1 选取由选取由Pij0可推出可推出 0的置换矩阵的置换矩阵P步步2 确定确定 步步3 取取 ,用,用 代替代替步步4 若若 =0,停;否则,返回步,停;否则,返回步1。例例2.2.为方便起见,我们来分解一个元素均为非负整数的为方便起见,我们来分解一个元素均为非负整数的3
10、阶双随机矩阵,阶双随机矩阵,(由(由Birkhoff定理,定理,r5)解:取解:取 ,=min 1,3,3 =1分解成分解成,再取,再取 因因min 5,5,3=3,又有,又有,取,取 于是又有于是又有 易得分解结果为:易得分解结果为:尚需解决的问题是如何求尚需解决的问题是如何求P,使得,使得Pij0必有必有 。读者不难发现,此问。读者不难发现,此问题可以通过求解一个两分图上的最大流(或最大匹配)来实现,计算量题可以通过求解一个两分图上的最大流(或最大匹配)来实现,计算量为为O(n4),是多项式时间可解的。具体方法为:作一两分图,若,是多项式时间可解的。具体方法为:作一两分图,若 ,则作边(则
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 卫星 开关
限制150内